論文の概要: Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
- arxiv url: http://arxiv.org/abs/2010.15390v2
- Date: Tue, 20 Jul 2021 00:27:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-01 22:09:14.557061
- Title: Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
- Title(参考訳): 不均一フィードバック集約によるマルチタスク帯域学習
- Authors: Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel D. Riek, Kamalika
Chaudhuri
- Abstract要約: 我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
- 参考スコア(独自算出の注目度): 35.923544685900055
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many real-world applications, multiple agents seek to learn how to perform
highly related yet slightly different tasks in an online bandit learning
protocol. We formulate this problem as the $\epsilon$-multi-player multi-armed
bandit problem, in which a set of players concurrently interact with a set of
arms, and for each arm, the reward distributions for all players are similar
but not necessarily identical. We develop an upper confidence bound-based
algorithm, RobustAgg$(\epsilon)$, that adaptively aggregates rewards collected
by different players. In the setting where an upper bound on the pairwise
similarities of reward distributions between players is known, we achieve
instance-dependent regret guarantees that depend on the amenability of
information sharing across players. We complement these upper bounds with
nearly matching lower bounds. In the setting where pairwise similarities are
unknown, we provide a lower bound, as well as an algorithm that trades off
minimax regret guarantees for adaptivity to unknown similarity structure.
- Abstract(参考訳): 多くの現実世界のアプリケーションでは、複数のエージェントがオンラインのバンディット学習プロトコルで、高度に関連し、わずかに異なるタスクを実行する方法を学びたいと考えている。
我々は、この問題を$\epsilon$-multi-player multi-armed bandit問題として定式化し、プレイヤーのセットが腕のセットと同時に相互作用し、各アームに対して、すべてのプレイヤーの報酬分布は似ているが必ずしも同一ではない。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼境界ベースアルゴリズム、ロバストagg$(\epsilon)$を開発した。
プレイヤー間での報酬分配の対方向の類似性に関する上限が分かっている場合、プレイヤー間での情報共有の快適性に依存するインスタンス依存の後悔保証を実現する。
これらの上界をほぼ一致する下界で補う。
ペア回りの類似性が不明な環境では、最小の後悔の保証から未知の類似性構造への適応性をトレードオフするアルゴリズムとともに、より低い境界を提供する。
関連論文リスト
- Leading the Pack: N-player Opponent Shaping [52.682734939786464]
我々は、複数のコプレーヤと複数のシェーピングエージェントを含む環境に、対向型シェーピング(OS)メソッドを拡張します。
多数のコプレーヤでプレイすると,OSメソッドの相対的な性能が低下し,OSメソッドが動作しない可能性が示唆された。
論文 参考訳(メタデータ) (2023-12-19T20:01:42Z) - Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms:
Learning Algorithms & Applications [32.313813562222066]
本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。
既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。
衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
論文 参考訳(メタデータ) (2022-04-28T13:46:59Z) - The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player
Multi-Armed Bandits with no Communication [10.446001329147112]
マルチプレイヤーのマルチアームバンディット問題について検討する。
この問題では、$m$プレーヤーは、合計報酬を$K > m$アームから最大化するために協力する。
ここで$Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
論文 参考訳(メタデータ) (2022-02-19T18:19:36Z) - An Instance-Dependent Analysis for the Cooperative Multi-Player
Multi-Armed Bandit [93.97385339354318]
マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。
まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。
第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
論文 参考訳(メタデータ) (2021-11-08T23:38:47Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳(メタデータ) (2021-01-21T10:35:09Z) - Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal
Regret With Neither Communication Nor Collisions [4.974932889340056]
我々は、多腕バンディット問題の協調型マルチプレイヤー版を考える。
これらの特性は,任意の数の選手や腕に対して達成可能であることを示す。
論文 参考訳(メタデータ) (2020-11-08T03:14:19Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳(メタデータ) (2020-03-06T20:34:42Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳(メタデータ) (2020-02-13T08:53:43Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳(メタデータ) (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。