論文の概要: Multi-Player Bandits Robust to Adversarial Collisions
- arxiv url: http://arxiv.org/abs/2211.07817v1
- Date: Tue, 15 Nov 2022 00:43:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 13:41:24.176166
- Title: Multi-Player Bandits Robust to Adversarial Collisions
- Title(参考訳): 対向衝突に頑健なマルチプレイヤーバンディット
- Authors: Shivakumar Mahesh, Anshuka Rangi, Haifeng Xu and Long Tran-Thanh
- Abstract要約: マルチプレイヤーマルチアーメッドバンドは近年広く研究されている。
本稿では,協力者による報酬の最大化を阻害する悪意あるプレイヤー(または攻撃者)の存在を,故意に連携させることで検討する。
攻撃者からのC$の衝突数が増加するにつれて、性能が良好に低下するディフェンダーに対して、最初の分散型で堅牢なアルゴリズムRESYNCを提供する。
- 参考スコア(独自算出の注目度): 31.349615523580518
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by cognitive radios, stochastic Multi-Player Multi-Armed Bandits
has been extensively studied in recent years. In this setting, each player
pulls an arm, and receives a reward corresponding to the arm if there is no
collision, namely the arm was selected by one single player. Otherwise, the
player receives no reward if collision occurs. In this paper, we consider the
presence of malicious players (or attackers) who obstruct the cooperative
players (or defenders) from maximizing their rewards, by deliberately colliding
with them. We provide the first decentralized and robust algorithm RESYNC for
defenders whose performance deteriorates gracefully as $\tilde{O}(C)$ as the
number of collisions $C$ from the attackers increases. We show that this
algorithm is order-optimal by proving a lower bound which scales as
$\Omega(C)$. This algorithm is agnostic to the algorithm used by the attackers
and agnostic to the number of collisions $C$ faced from attackers.
- Abstract(参考訳): 認知ラジオに触発された確率的マルチプレイヤーマルチアーマッドバンドは近年広く研究されている。
この設定では、各プレイヤーは腕を引っ張り、衝突がなければ腕に対応する報酬、すなわち1人のプレイヤーによって選択された腕を受け取る。
プレイヤーは、衝突した場合は報酬を受け取らない。
本稿では、協力者(または守備者)が故意に協力して報酬を最大化することを妨げる悪意あるプレイヤー(または攻撃者)の存在を考察する。
我々は,攻撃者からの衝突回数が増加するにつれて,その性能が$\tilde{O}(C)$として優雅に低下するディフェンダーに対して,最初の分散型で堅牢なアルゴリズムRESYNCを提供する。
このアルゴリズムは、$\omega(c)$ でスケールする下限を証明し、オーダー最適であることを示す。
このアルゴリズムは攻撃者が使用するアルゴリズムに非依存であり、攻撃者が直面する衝突の数に非依存である。
関連論文リスト
- Heterogeneous Multi-Player Multi-Armed Bandits Robust To Adversarial Attacks [19.184883255588126]
システム内のプレイヤーが受ける報酬に負の影響を及ぼそうとする敵の存在下で、マルチプレイヤーバンディットの設定を考える。
衝突(複数のプレイヤーが同じ腕を選択している)が発生した場合、すべての衝突したユーザーは報酬を受け取らない。
敵は、プレイヤーが受ける報酬、すなわち敵が腕を攻撃した場合、その腕を選択するプレイヤーはゼロの報酬を受ける。
論文 参考訳(メタデータ) (2025-01-21T08:51:23Z) - Corrupted Learning Dynamics in Games [62.73758165845971]
すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。
本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
論文 参考訳(メタデータ) (2024-12-10T02:23:44Z) - 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) - 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) - Composite Adversarial Attacks [57.293211764569996]
敵対攻撃は、機械学習(ML)モデルを欺くための技術です。
本論文では,攻撃アルゴリズムの最適組み合わせを自動的に探索するための複合攻撃法(Composite Adrial Attack,CAA)を提案する。
CAAは11の防衛でトップ10の攻撃を破り、時間の経過は少ない。
論文 参考訳(メタデータ) (2020-12-10T03:21:16Z) - Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal
Regret With Neither Communication Nor Collisions [4.974932889340056]
我々は、多腕バンディット問題の協調型マルチプレイヤー版を考える。
これらの特性は,任意の数の選手や腕に対して達成可能であることを示す。
論文 参考訳(メタデータ) (2020-11-08T03:14:19Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳(メタデータ) (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。