論文の概要: Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits
- arxiv url: http://arxiv.org/abs/2110.05724v1
- Date: Tue, 12 Oct 2021 03:24:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-13 14:45:16.144333
- Title: Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits
- Title（参考訳）: 質問するな - 予算バンドに対する問題依存の保証
- Authors: Nadav Merlis, Yonathan Efroni, Shie Mannor
- Abstract要約: 後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 66.02233330016435
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a stochastic multi-armed bandit setting where feedback is limited
by a (possibly time-dependent) budget, and reward must be actively inquired for
it to be observed. Previous works on this setting assumed a strict feedback
budget and focused on not violating this constraint while providing
problem-independent regret guarantees. In this work, we provide
problem-dependent guarantees on both the regret and the asked feedback. In
particular, we derive problem-dependent lower bounds on the required feedback
and show that there is a fundamental difference between problems with a unique
and multiple optimal arms. Furthermore, we present a new algorithm called
BuFALU for which we derive problem-dependent regret and cumulative feedback
bounds. Notably, we show that BuFALU naturally adapts to the number of optimal
arms.
- Abstract（参考訳）: 我々は,フィードバックが(おそらく時間依存の)予算によって制限され,報酬が観察されるよう積極的に要求される確率的多腕バンディット設定を考える。
この設定に関する以前の作業は厳格なフィードバック予算を前提として、問題に依存しない後悔の保証を提供しながら、この制約に違反しないことに重点を置いていた。
本研究では,後悔とフィードバックの両方に対して,問題に依存した保証を提供する。
特に、要求されるフィードバックに対する問題依存下限を導出し、一意と複数の最適アームを持つ問題の間に根本的な違いがあることを示す。
さらに,問題依存的後悔と累積フィードバック境界を導出するbufaluと呼ばれる新しいアルゴリズムを提案する。
特に、BuFALUは最適なアームの数に自然に適応することを示す。
関連論文リスト
- Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳（メタデータ） (2024-02-23T06:27:12Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - BanditQ: Fair Bandits with Guaranteed Rewards [10.74025233418392]
古典的な非レグレットなマルチアームバンディットアルゴリズムは本質的に不公平である。
我々は、後悔と目標レート違反を容認しつつ、目標報酬率を達成する、BanditQと呼ばれる新しいオンラインポリシーを提案する。
提案手法は効率的で,公正な予測問題から標準逆MAB問題へのブラックボックス削減を許容する。
論文 参考訳（メタデータ） (2023-04-11T13:39:47Z) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳（メタデータ） (2022-05-25T01:22:36Z) - Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget [6.759124697337311]
有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-09T14:36:05Z) - Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
問合せ予算で意思決定問題を定式化する。
我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。
我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
論文 参考訳（メタデータ） (2021-02-05T19:56:31Z) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳（メタデータ） (2020-06-18T12:13:58Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳（メタデータ） (2020-02-13T08:53:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。