論文の概要: The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player
Multi-Armed Bandits with no Communication
- arxiv url: http://arxiv.org/abs/2202.09653v1
- Date: Sat, 19 Feb 2022 18:19:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 08:14:39.679873
- Title: The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player
Multi-Armed Bandits with no Communication
- Title（参考訳）: 通信のないマルチプレイヤーマルチアーマバンドにおけるインスタンス依存保証者のパレートフロンティア
- Authors: Allen Liu, Mark Sellke
- Abstract要約: マルチプレイヤーのマルチアームバンディット問題について検討する。
この問題では、$m$プレーヤーは、合計報酬を$K > m$アームから最大化するために協力する。
ここで$Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
- 参考スコア（独自算出の注目度）: 10.446001329147112
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the stochastic multi-player multi-armed bandit problem. In this
problem, $m$ players cooperate to maximize their total reward from $K > m$
arms. However the players cannot communicate and are penalized (e.g. receive no
reward) if they pull the same arm at the same time. We ask whether it is
possible to obtain optimal instance-dependent regret $\tilde{O}(1/\Delta)$
where $\Delta$ is the gap between the $m$-th and $m+1$-st best arms. Such
guarantees were recently achieved in a model allowing the players to implicitly
communicate through intentional collisions. We show that with no communication
at all, such guarantees are, surprisingly, not achievable. In fact, obtaining
the optimal $\tilde{O}(1/\Delta)$ regret for some regimes of $\Delta$
necessarily implies strictly sub-optimal regret in other regimes. Our main
result is a complete characterization of the Pareto optimal instance-dependent
trade-offs that are possible with no communication. Our algorithm generalizes
that of Bubeck, Budzinski, and the second author and enjoys the same strong
no-collision property, while our lower bound is based on a topological
obstruction and holds even under full information.
- Abstract（参考訳）: 確率的マルチプレイヤー・マルチアーム・バンディット問題について検討した。
この問題では、$m$プレイヤーが協力して$k > m$ armsの報酬を最大化する。
しかし、プレイヤーはコミュニケーションが取れず、同時に同じ腕を引っ張ると罰を受ける(例:報酬を受けない)。
ここで$\Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
このような保証は、プレイヤーが意図的な衝突を通じて暗黙的にコミュニケーションできるモデルで最近達成された。
コミュニケーションが全くない状態では、このような保証は驚くべきことに達成不可能であることを示します。
実際、$\Delta$のいくつかのレジームに対して最適な$\tilde{O}(1/\Delta)$後悔を得ることは、必然的に他のレジームにおける厳密な準最適後悔を意味する。
私たちの主な結果は、通信なしで可能なparetoの最適インスタンス依存トレードオフの完全な特徴付けです。
このアルゴリズムはbubeck, budzinski, and the second authorのそれを一般化し,同じ強い非衝突特性を享受する。
関連論文リスト
- Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-08-20T13:57:00Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits [6.732901486505047]
マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用を動機とした、ますます関連する意思決定問題である。
本稿では、前述のモデリング問題に対処することを目的とした、テキストマルチプレーヤのマルチアームウォーキングバンディットモデルを提案する。
論文 参考訳（メタデータ） (2022-12-12T23:26:02Z) - Multi-Player Bandits Robust to Adversarial Collisions [31.349615523580518]
マルチプレイヤーマルチアーメッドバンドは近年広く研究されている。
本稿では,協力者による報酬の最大化を阻害する悪意あるプレイヤー(または攻撃者)の存在を,故意に連携させることで検討する。
攻撃者からのC$の衝突数が増加するにつれて、性能が良好に低下するディフェンダーに対して、最初の分散型で堅牢なアルゴリズムRESYNCを提供する。
論文 参考訳（メタデータ） (2022-11-15T00:43:26Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal
Regret With Neither Communication Nor Collisions [4.974932889340056]
我々は、多腕バンディット問題の協調型マルチプレイヤー版を考える。
これらの特性は,任意の数の選手や腕に対して達成可能であることを示す。
論文 参考訳（メタデータ） (2020-11-08T03:14:19Z) - Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文 参考訳（メタデータ） (2020-10-29T07:13:28Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳（メタデータ） (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。