論文の概要: Tight Lower Bounds for Combinatorial Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2002.05392v3
- Date: Thu, 16 Jul 2020 11:26:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 09:53:42.785982
- Title: Tight Lower Bounds for Combinatorial Multi-Armed Bandits
- Title(参考訳): 組合せ多腕バンディットの厳密な下限
- Authors: Nadav Merlis, Shie Mannor
- Abstract要約: Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
- 参考スコア(独自算出の注目度): 72.56064196252498
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Combinatorial Multi-Armed Bandit problem is a sequential decision-making
problem in which an agent selects a set of arms on each round, observes
feedback for each of these arms and aims to maximize a known reward function of
the arms it chose. While previous work proved regret upper bounds in this
setting for general reward functions, only a few works provided matching lower
bounds, all for specific reward functions. In this work, we prove regret lower
bounds for combinatorial bandits that hold under mild assumptions for all
smooth reward functions. We derive both problem-dependent and
problem-independent bounds and show that the recently proposed Gini-weighted
smoothness parameter (Merlis and Mannor, 2019) also determines the lower bounds
for monotone reward functions. Notably, this implies that our lower bounds are
tight up to log-factors.
- Abstract(参考訳): Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドのアームを選択し、各アームのフィードバックを観察し、選択したアームの既知の報酬関数を最大化することを目的とした、シーケンシャルな意思決定問題である。
以前の研究では、この設定で一般的な報酬関数に対する後悔の上限が証明されたが、特定の報酬関数に対して、下限に一致するものはごくわずかであった。
本研究では,すべてのスムーズな報酬関数に対して軽度な仮定で成り立つ組合せ的包帯に対して,後悔の少ない境界を証明した。
問題依存境界と問題非依存境界の両方を導出し、最近提案されたgini-weighted smoothnessパラメータ(merlis and mannor, 2019)も単調報酬関数の下限を決定することを示した。
特にこれは、下位境界がログファクタに固まることを意味します。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳(メタデータ) (2024-10-08T09:49:47Z) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Regret Lower Bounds in Multi-agent Multi-armed Bandit [14.822625665220068]
Multi-armed Banditは、後悔の証明可能な上限を持つメソッドを動機付けている。
異なる設定にまたがる後悔の少ない境界について、初めて包括的な研究を行った。
論文 参考訳(メタデータ) (2023-08-15T21:20:24Z) - Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms [32.313813562222066]
マルチプレイマルチアームバンディット(MP-MAB)問題を共有アーム設定で一般化する。
各共有可能なアームは、有限報酬能力と'per-load'の報酬分布を有する。
本稿では,この問題に対処し,その後悔すべき上限を証明するためのオンライン学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-17T13:47:27Z) - Contextual Combinatorial Multi-output GP Bandits with Group Constraints [11.317136648551537]
連合型多武装バンディット問題では、クライアントを保護するための最小限のプライバシー要件を満たしながら、世界的報酬を最大化することが主な目標である。
我々は、グループやアクションセットの変更によるコンテキスト的バンディットの設定を検討し、そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、スーパーアームの報酬を最大化し、ベースアームが選択されたグループの報酬の制約を満たす。
次に、累積スーパーアーム報酬の最大化と充足のバランスをとる、Thresholded Combinatored upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-11-29T18:39:09Z) - Max-Min Grouped Bandits [48.62520520818357]
マルチアームバンディット問題であるmax-min grouped banditsを導入する。
ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。
この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
論文 参考訳(メタデータ) (2021-11-17T01:59:15Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-12T03:24:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。