論文の概要: Selfish Robustness and Equilibria in Multi-Player Bandits
- arxiv url: http://arxiv.org/abs/2002.01197v2
- Date: Fri, 19 Jun 2020 08:02:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 02:31:37.442868
- Title: Selfish Robustness and Equilibria in Multi-Player Bandits
- Title（参考訳）: マルチプレイヤーバンドにおける利己的ロバスト性と平衡
- Authors: Etienne Boursier and Vianney Perchet
- Abstract要約: ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
- 参考スコア（独自算出の注目度）: 25.67398941667429
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by cognitive radios, stochastic multi-player multi-armed bandits
gained a lot of interest recently. In this class of problems, several players
simultaneously pull arms and encounter a collision - with 0 reward - if some of
them pull the same arm at the same time. While the cooperative case where
players maximize the collective reward (obediently following some fixed
protocol) has been mostly considered, robustness to malicious players is a
crucial and challenging concern. Existing approaches consider only the case of
adversarial jammers whose objective is to blindly minimize the collective
reward. We shall consider instead the more natural class of selfish players
whose incentives are to maximize their individual rewards, potentially at the
expense of the social welfare. We provide the first algorithm robust to selfish
players (a.k.a. Nash equilibrium) with a logarithmic regret, when the arm
performance is observed. When collisions are also observed, Grim Trigger type
of strategies enable some implicit communication-based algorithms and we
construct robust algorithms in two different settings: the homogeneous (with a
regret comparable to the centralized optimal one) and heterogeneous cases (for
an adapted and relevant notion of regret). We also provide impossibility
results when only the reward is observed or when arm means vary arbitrarily
among players.
- Abstract（参考訳）: 認知ラジオに触発されて、確率的なマルチプレイヤーのマルチアームバンディットが最近注目を集めた。
このタイプの問題では、複数のプレイヤーが同時に腕を引っ張り、同時に同じ腕を引っ張る場合、0の報酬で衝突に遭遇する。
プレイヤーが集団報酬を最大化する協調的なケース(一部の固定されたプロトコルに従っている)は、主に検討されているが、悪意のあるプレイヤーに対する堅牢性は重要かつ困難な懸念である。
既存のアプローチでは、集団報酬を盲目的に最小化することを目的とした敵ジャマーの場合のみを考える。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
アーム性能が観測された場合,自発的プレイヤー(すなわちナッシュ平衡)にロバストな最初のアルゴリズムを対数的後悔で提供する。
衝突も観測された場合、Grim Trigger型戦略はいくつかの暗黙的なコミュニケーションベースのアルゴリズムを可能にし、同質な(集中的な最適なものと同等の後悔を伴う)不均一な(適応的で関連する後悔の考えのために)2つの異なる設定でロバストなアルゴリズムを構築する。
また、報酬のみを観測した場合や、腕の手段がプレイヤー間で任意に変化する場合にも、不可能な結果が得られる。
関連論文リスト
- Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-08-20T13:57:00Z) - Multi-Player Approaches for Dueling Bandits [58.442742345319225]
Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。
また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
論文 参考訳（メタデータ） (2024-05-25T10:25:48Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Competing for Shareable Arms in Multi-Player Multi-Armed Bandits [29.08799537067425]
本稿では,プレイヤーが自尊心を持ち,自己報酬を最大化することを目的とした,新しいマルチプレイヤーマルチアームバンディット(MPMAB)について検討する。
本稿では, 平均アロケーション (SMAA) を用いた新たな自己中心型MPMABを提案する。
我々は,一人の利己的なプレイヤーが,逸脱によって報酬を著しく増加させることはできず,また,他のプレイヤーの報酬に有害な影響も与えないことを確認した。
論文 参考訳（メタデータ） (2023-05-30T15:59:56Z) - 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) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳（メタデータ） (2022-10-24T09:32:40Z) - Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms:
Learning Algorithms & Applications [32.313813562222066]
本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。
既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。
衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
論文 参考訳（メタデータ） (2022-04-28T13:46:59Z) - An Instance-Dependent Analysis for the Cooperative Multi-Player
Multi-Armed Bandit [93.97385339354318]
マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。
まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。
第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
論文 参考訳（メタデータ） (2021-11-08T23:38:47Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文 参考訳（メタデータ） (2020-10-29T07:13:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。