論文の概要: Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget
- arxiv url: http://arxiv.org/abs/2202.04487v1
- Date: Wed, 9 Feb 2022 14:36:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-10 15:07:20.780683
- Title: Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget
- Title（参考訳）: 半帯域フィードバックと有限予算をもつ非確率的組合せバンディットにおける最適アームの探索
- Authors: Jasmin Brandt, Bj\"orn Haddenhorst, Viktor Bengs, Eyke H\"ullermeier
- Abstract要約: 有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.759124697337311
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the combinatorial bandits problem with semi-bandit feedback under
finite sampling budget constraints, in which the learner can carry out its
action only for a limited number of times specified by an overall budget. The
action is to choose a set of arms, whereupon feedback for each arm in the
chosen set is received. Unlike existing works, we study this problem in a
non-stochastic setting with subset-dependent feedback, i.e., the semi-bandit
feedback received could be generated by an oblivious adversary and also might
depend on the chosen set of arms. In addition, we consider a general feedback
scenario covering both the numerical-based as well as preference-based case and
introduce a sound theoretical framework for this setting guaranteeing sensible
notions of optimal arms, which a learner seeks to find. We suggest a generic
algorithm suitable to cover the full spectrum of conceivable arm elimination
strategies from aggressive to conservative. Theoretical questions about the
sufficient and necessary budget of the algorithm to find the best arm are
answered and complemented by deriving lower bounds for any learning algorithm
for this problem scenario.
- Abstract（参考訳）: 本稿では,有限サンプリング予算制約の下で,半帯域フィードバックによる組合せ帯域幅問題について考察する。
アームセットの選択がアクションであり、選択されたセットの各アームに対するフィードバックが受信される。
既存の研究とは異なり、この問題はサブセット依存のフィードバックを持つ非確率的な環境で研究され、すなわち、受信された半帯域フィードバックは、不利な敵によって生成され、また選択されたアームセットに依存する可能性がある。
さらに,数値ベースと選好ベースのケースの両方をカバーする一般的なフィードバックシナリオを検討し,学習者が探そうとする最適アームの認識可能な概念を保証するための健全な理論的枠組みを提案する。
提案手法は,攻撃的から保守的へのアーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
最適なアームを見つけるためのアルゴリズムの十分な予算に関する理論的疑問は、この問題シナリオに対する学習アルゴリズムの下位境界を導出することによって答え、補完される。
関連論文リスト
- Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。
この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。
我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
論文 参考訳（メタデータ） (2024-10-17T00:44:50Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits [1.4732811715354452]
我々は、各アームが選択時に異なるリソースを消費する、$Kの武器付きバンディット問題を考える。
我々はトンプソンサンプリングのようにランダム化される一連のアルゴリズムを提案するが、予算制約に関してより慎重に決定を最適化する。
論文 参考訳（メタデータ） (2024-08-28T04:56:06Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。
本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。
また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
論文 参考訳（メタデータ） (2022-11-27T08:58:16Z) - From Finite to Countable-Armed Bandits [8.099977107670918]
有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。
武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。
我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-22T13:09:50Z) - 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) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。