論文の概要: From Finite to Countable-Armed Bandits
- arxiv url: http://arxiv.org/abs/2105.10721v1
- Date: Sat, 22 May 2021 13:09:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-25 15:28:57.308053
- Title: From Finite to Countable-Armed Bandits
- Title（参考訳）: 有限から可算のバンディットへ
- Authors: Anand Kalvit and Assaf Zeevi
- Abstract要約: 有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。
武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。
我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.099977107670918
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a stochastic bandit problem with countably many arms that belong
to a finite set of types, each characterized by a unique mean reward. In
addition, there is a fixed distribution over types which sets the proportion of
each type in the population of arms. The decision maker is oblivious to the
type of any arm and to the aforementioned distribution over types, but
perfectly knows the total number of types occurring in the population of arms.
We propose a fully adaptive online learning algorithm that achieves O(log n)
distribution-dependent expected cumulative regret after any number of plays n,
and show that this order of regret is best possible. The analysis of our
algorithm relies on newly discovered concentration and convergence properties
of optimism-based policies like UCB in finite-armed bandit problems with "zero
gap," which may be of independent interest.
- Abstract（参考訳）: 有限個の型に属する腕を数え切れないほど多く持つ確率的バンディット問題を,それぞれに一意な平均報酬を特徴とする。
さらに、腕の個体群におけるそれぞれのタイプの割合を設定する型に対する固定分布が存在する。
意思決定者は、いかなる腕の型や、前述の種類に対する分布にも従わないが、腕の集団で起こるタイプの総数を完全に知っている。
我々は,O(log n)分布依存の累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案し,この後悔の順序が最善であることを示す。
アルゴリズムの解析は, 有限武装バンディット問題におけるUTBのような楽観主義に基づく政策の, 新たに発見された集中度と収束度に依拠する。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget [6.759124697337311]
有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-09T14:36:05Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。
非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
論文 参考訳（メタデータ） (2021-10-23T02:47:55Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。