論文の概要: A Novel Confidence-Based Algorithm for Structured Bandits
- arxiv url: http://arxiv.org/abs/2005.11593v1
- Date: Sat, 23 May 2020 19:52:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 03:18:00.274786
- Title: A Novel Confidence-Based Algorithm for Structured Bandits
- Title（参考訳）: 構造帯域に対する信頼度に基づく新しいアルゴリズム
- Authors: Andrea Tirinzoni, Alessandro Lazaric, Marcello Restelli
- Abstract要約: 両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 129.30402124516507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study finite-armed stochastic bandits where the rewards of each arm might
be correlated to those of other arms. We introduce a novel phased algorithm
that exploits the given structure to build confidence sets over the parameters
of the true bandit problem and rapidly discard all sub-optimal arms. In
particular, unlike standard bandit algorithms with no structure, we show that
the number of times a suboptimal arm is selected may actually be reduced thanks
to the information collected by pulling other arms. Furthermore, we show that,
in some structures, the regret of an anytime extension of our algorithm is
uniformly bounded over time. For these constant-regret structures, we also
derive a matching lower bound. Finally, we demonstrate numerically that our
approach better exploits certain structures than existing methods.
- Abstract（参考訳）: 各腕の報酬と他の腕の報酬を関連付ける有限腕の確率的バンディットについて検討した。
我々は、与えられた構造を利用して真のバンディット問題のパラメータの上に信頼セットを構築し、全ての準最適アームを迅速に破棄する新しいフェーズドアルゴリズムを導入する。
特に、構造を持たない標準的なバンディットアルゴリズムとは異なり、他のアームを引っ張ることで収集された情報により、サブオプティカルアームが選択された回数が実際に減少する可能性がある。
さらに,いくつかの構造において,アルゴリズムの時間的拡張の後悔は時間とともに一様に有界であることを示す。
これらの定数-回帰構造に対しては、一致する下界も導出する。
最後に,本手法が既存の手法よりも優れた構造を活用できることを数値的に示す。
関連論文リスト
- Best-Arm Identification in Unimodal Bandits [24.001611176749158]
本研究では, 固定信頼度ベストアーム識別問題について検討する。
我々は任意の境界の停止時間で2つ下げる。
腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
論文 参考訳（メタデータ） (2024-11-04T09:05:11Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳（メタデータ） (2020-12-07T08:23:08Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z) - On Regret with Multiple Best Arms [12.315392649501101]
バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。
我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
論文 参考訳（メタデータ） (2020-06-26T04:01:46Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳（メタデータ） (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。