論文の概要: Byzantine-Resilient Decentralized Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2310.07320v1
- Date: Wed, 11 Oct 2023 09:09:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-14 02:33:47.543522
- Title: Byzantine-Resilient Decentralized Multi-Armed Bandits
- Title（参考訳）: ビザンチン耐性分散多腕バンディット
- Authors: Jingxuan Zhu, Alec Koppel, Alvaro Velasquez, Ji Liu
- Abstract要約: エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合するアルゴリズムを開発する。
このフレームワークは、コンピュータネットワークの攻撃者をモデル化したり、攻撃的なコンテンツをレコメンデーターシステムに攻撃したり、金融市場のマニピュレータとして利用することができる。
- 参考スコア（独自算出の注目度）: 25.499420566469098
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In decentralized cooperative multi-armed bandits (MAB), each agent observes a
distinct stream of rewards, and seeks to exchange information with others to
select a sequence of arms so as to minimize its regret. Agents in the
cooperative setting can outperform a single agent running a MAB method such as
Upper-Confidence Bound (UCB) independently. In this work, we study how to
recover such salient behavior when an unknown fraction of the agents can be
Byzantine, that is, communicate arbitrarily wrong information in the form of
reward mean-estimates or confidence sets. This framework can be used to model
attackers in computer networks, instigators of offensive content into
recommender systems, or manipulators of financial markets. Our key contribution
is the development of a fully decentralized resilient upper confidence bound
(UCB) algorithm that fuses an information mixing step among agents with a
truncation of inconsistent and extreme values. This truncation step enables us
to establish that the performance of each normal agent is no worse than the
classic single-agent UCB1 algorithm in terms of regret, and more importantly,
the cumulative regret of all normal agents is strictly better than the
non-cooperative case, provided that each agent has at least 3f+1 neighbors
where f is the maximum possible Byzantine agents in each agent's neighborhood.
Extensions to time-varying neighbor graphs, and minimax lower bounds are
further established on the achievable regret. Experiments corroborate the
merits of this framework in practice.
- Abstract（参考訳）: 分散協調多腕バンディット(mab)では、各エージェントは異なる報酬の流れを観察し、他者と情報を交換し、後悔を最小限に抑えるために一連の武器を選択する。
協調設定のエージェントは、アッパー信頼境界(UCB)のようなMABメソッドを実行する単一のエージェントを独立して上回ることができる。
本研究では,未知のエージェントがビザンチン,すなわち報酬平均見積や信頼セットという形で任意に間違った情報を伝達できるような場合,このような有害な振る舞いを回復する方法について検討する。
このフレームワークは、コンピュータネットワークにおける攻撃者をモデル化したり、攻撃的コンテンツの扇動者をレコメンダシステムや金融市場のマニピュレータにモデル化したりすることができる。
我々の重要な貢献は、エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合させる、完全に分散化された高信頼境界(UCB)アルゴリズムの開発である。
このトランザクションステップにより、従来の単一エージェントucb1アルゴリズムよりも、各正規エージェントのパフォーマンスが損なわれず、さらに重要なこととして、すべての正規エージェントの累積後悔は、非協力的なケースよりも厳格に良い。
時変隣接グラフの拡張とミニマックス下限は、達成可能な後悔の上にさらに確立される。
実験は、実際にこのフレームワークのメリットを裏付けるものだ。
関連論文リスト
- Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions [6.234292942334148]
敵の汚職に頑健なマルチエージェント協調学習アルゴリズムを提案する。
副産物として,本アルゴリズムは,単一エージェントと同種マルチエージェントの両方のシナリオに還元した場合の,最先端の後悔境界も改善する。
論文 参考訳（メタデータ） (2024-11-12T20:20:26Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳（メタデータ） (2024-09-27T16:46:02Z) - Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
我々は,エージェント群を協調させようとする学習者の視点で,マルチエージェント模倣学習(MAIL)問題を研究する。
MAILの以前の作業のほとんどは、基本的には、デモのサポート内で専門家の振る舞いにマッチする問題を減らすものです。
エージェントが戦略的でないという仮定の下で、学習者と専門家の間の価値ギャップをゼロにするのに十分であるが、戦略的エージェントによる逸脱を保証するものではない。
論文 参考訳（メタデータ） (2024-06-06T16:18:20Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。
エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。
我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
論文 参考訳（メタデータ） (2022-06-01T00:44:53Z) - Private and Byzantine-Proof Cooperative Decision-Making [15.609414012418043]
協調バンディット問題は、多腕バンディットと同時に相互作用するエージェントのグループを含むマルチエージェント決定問題である。
本稿では、エージェントがアクションシーケンスに関して通信をプライベートにしたい場合と、エージェントがビザンチンになり得る場合の2つの設定の下で、バンドイット問題を調査する。
我々は,(a)微分プライベートかつ(b)プライベートでありながら,最適な後悔を得る高信頼有界アルゴリズムを提供する。
我々の分散アルゴリズムはエージェント間の接続のネットワークに関する情報を必要とせず、大規模な動的システムにスケーラブルにします。
論文 参考訳（メタデータ） (2022-05-27T18:03:54Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
本研究では,コミュニケーション制約下での運用を目的とした適応型分散学習戦略について検討する。
我々は,ストリーミングデータの連続的な観察から,オンライン最適化問題を解決しなければならないエージェントのネットワークを考える。
論文 参考訳（メタデータ） (2021-12-03T19:23:48Z) - Resilient Consensus-based Multi-agent Reinforcement Learning [22.774403531759592]
我々は、各エージェントがローカルな報酬を受け取り、グローバルな状態と行動を監視する、完全に分散されたネットワークを考える。
本研究では, ビザンティンエージェントの存在下では, 推定・通信戦略が完全に任意である場合, 協調エージェントの推定値が有界コンセンサス値と確率値とに収束することを示す。
本研究では, 協調エージェントの政策が, チーム平均目標関数の局所最大値付近の有界近傍に収束することを証明する。
論文 参考訳（メタデータ） (2021-11-12T15:38:01Z) - Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。
我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
論文 参考訳（メタデータ） (2020-07-07T22:27:30Z) - The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [20.259428328004738]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳（メタデータ） (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。