論文の概要: Inference with the Upper Confidence Bound Algorithm

• arxiv url: http://arxiv.org/abs/2408.04595v1
• Date: Thu, 8 Aug 2024 17:11:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-09 14:58:04.769294
• Title: Inference with the Upper Confidence Bound Algorithm
• Title（参考訳）: 上信頼境界アルゴリズムによる推論
• Authors: Koulik Khamaru, Cun-Hui Zhang,
• Abstract要約: データを逐次的に収集する場合、推論タスクは困難になる。 この問題は、手前のシーケンシャルアルゴリズムが一定の安定性特性を満たす場合に緩和できると我々は主張する。 そのような場合、$fraclog Klog T rightarrow 0$, and the number of near-optimal arms is large。
• 参考スコア（独自算出の注目度）: 5.985204759362746
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we discuss the asymptotic behavior of the Upper Confidence Bound (UCB) algorithm in the context of multiarmed bandit problems and discuss its implication in downstream inferential tasks. While inferential tasks become challenging when data is collected in a sequential manner, we argue that this problem can be alleviated when the sequential algorithm at hand satisfies certain stability property. This notion of stability is motivated from the seminal work of Lai and Wei (1982). Our first main result shows that such a stability property is always satisfied for the UCB algorithm, and as a result the sample means for each arm are asymptotically normal. Next, we examine the stability properties of the UCB algorithm when the number of arms $K$ is allowed to grow with the number of arm pulls $T$. We show that in such a case the arms are stable when $\frac{\log K}{\log T} \rightarrow 0$, and the number of near-optimal arms are large.
• Abstract（参考訳）: 本稿では,アッパー信頼境界(UCB)アルゴリズムのマルチアームバンディット問題における漸近挙動について論じ,下流推論タスクにおけるその影響について論じる。 データを逐次的に収集する場合、推論タスクは困難になるが、手元のシーケンシャルアルゴリズムが一定の安定性特性を満たす場合、この問題は軽減できると論じる。 この安定性の概念は、Lai and Wei (1982) の楽譜から動機づけられている。 本研究の第一報は, UCBアルゴリズムの安定性が常に満足していることを示し, 結果として各アームのサンプル手段は漸近的に正常であることを示す。 次に、UCBアルゴリズムの安定性について、腕数$K$が腕数$T$で増大することを許すときの安定性について検討する。 そのような場合、$\frac{\log K}{\log T} \rightarrow 0$, and the number of near-optimal arms is large。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
  upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。 Lai-Robbins の後悔公式が真であることと、その部分最適性ギャップが$sigmasqrtKlog T/T$を超える場合に限ることを示す。 また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。
  論文  参考訳（メタデータ） (2024-12-09T01:14:02Z)
• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。 逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
  論文  参考訳（メタデータ） (2022-07-22T15:54:53Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
  利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。