論文の概要: The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
- arxiv url: http://arxiv.org/abs/2001.05452v4
- Date: Tue, 2 Jul 2024 23:36:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-05 15:33:04.817249
- Title: The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
- Title（参考訳）: Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
- Authors: Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, Sanjay Shakkottai,
- Abstract要約: N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
- 参考スコア（独自算出の注目度）: 20.259428328004738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of $N$ agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two novel algorithms, where each agent only plays from a subset of all the arms. Agents use the communication medium to recommend only arm-IDs (not samples), and thus update the set of arms from which they play. We establish that, if agents communicate $\Omega(\log(T))$ times through any connected pairwise gossip mechanism, then every agent's regret is a factor of order $N$ smaller compared to the case of no collaborations. Furthermore, we show that the communication constraints only have a second order effect on the regret of our algorithm. We then analyze this second order term of the regret to derive bounds on the regret-communication tradeoffs. Finally, we empirically evaluate our algorithm and conclude that the insights are fundamental and not artifacts of our bounds. We also show a lower bound which gives that the regret scaling obtained by our algorithm cannot be improved even in the absence of any communication constraints. Our results thus demonstrate that even a minimal level of collaboration among agents greatly reduces regret for all agents.
- Abstract（参考訳）: 我々は、N$エージェントからなる分散マルチエージェントマルチアームバンド(MAB)のセットアップを検討し、個々の累積後悔を最小限に抑えるために同じMABインスタンスを解決する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
我々は2つの新しいアルゴリズムを開発し、各エージェントはすべてのアームのサブセットからのみ演奏する。
エージェントは通信媒体を使用して、腕IDのみを推奨し(サンプルではない)、腕のセットを更新する。
エージェントが接続された任意のペアのゴシップ機構を介して$\Omega(\log(T))$ timesを通信した場合、すべてのエージェントの後悔は、コラボレーションがない場合と比較して$N$の小さな要素である。
さらに, 通信制約は, アルゴリズムの後悔に対する2次効果しか持たないことを示す。
次に、後悔とコミュニケーションのトレードオフの境界を導こうとする後悔のこの2次項を分析します。
最後に、我々のアルゴリズムを実証的に評価し、洞察は基本であり、境界の人工物ではないと結論付ける。
また, 通信制約がない場合でも, アルゴリズムによって得られた後悔のスケーリングは改善できないことを示す。
以上の結果から,エージェント間のコラボレーションが最小限であっても,すべてのエージェントに対する後悔が大幅に減少することが明らかとなった。
関連論文リスト
- 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-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳（メタデータ） (2024-02-23T06:27:12Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Doubly Adversarial Federated Bandits [7.23389716633927]
本稿では,複数のエージェントが通信ネットワークを介して協調する,非確率的フェデレーション型多武装バンディット問題について検討する。
我々のアルゴリズムは、Cesa-Bianchi et alで提案されたオープンな質問に対して肯定的な答えを与える。
論文 参考訳（メタデータ） (2023-01-22T22:36:43Z) - On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [7.23389716633927]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。
また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2022-11-30T16:46:41Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳（メタデータ） (2022-06-13T09:17:40Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。
我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
論文 参考訳（メタデータ） (2020-07-07T22:27:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。