論文の概要: Multi-Agent Multi-Armed Bandits with Limited Communication
- arxiv url: http://arxiv.org/abs/2102.08462v1
- Date: Wed, 10 Feb 2021 06:28:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-13 16:26:19.471010
- Title: Multi-Agent Multi-Armed Bandits with Limited Communication
- Title（参考訳）: 通信が制限されたマルチエージェントマルチアームバンディット
- Authors: Mridul Agarwal, Vaneet Aggarwal, Kamyar Azizzadenesheli
- Abstract要約: 我々は、$N$エージェントが$K gg N$の$K$アームバンドイット問題のインスタンスと相互作用する問題を検討する。
エージェントは、合計でT$のタイムステップ、通信ラウンドの数、各通信ラウンドにおけるビット数について、すべてのエージェントに対する累積的後悔を同時に最小化することを目指している。
我々は、各エージェントがエポックの終わり後にのみ通信し、知っている最高の腕のインデックスを共有する2倍のエポックベースのアルゴリズムであるLimited Communication Collaboration - Upper Bound(LCC-UCB)を紹介します。
- 参考スコア（独自算出の注目度）: 41.63062883750805
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem where $N$ agents collaboratively interact with an
instance of a stochastic $K$ arm bandit problem for $K \gg N$. The agents aim
to simultaneously minimize the cumulative regret over all the agents for a
total of $T$ time steps, the number of communication rounds, and the number of
bits in each communication round. We present Limited Communication
Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based
algorithm where each agent communicates only after the end of the epoch and
shares the index of the best arm it knows. With our algorithm, LCC-UCB, each
agent enjoys a regret of $\tilde{O}\left(\sqrt{({K/N}+ N)T}\right)$,
communicates for $O(\log T)$ steps and broadcasts $O(\log K)$ bits in each
communication step. We extend the work to sparse graphs with maximum degree
$K_G$, and diameter $D$ and propose LCC-UCB-GRAPH which enjoys a regret bound
of $\tilde{O}\left(D\sqrt{(K/N+ K_G)DT}\right)$. Finally, we empirically show
that the LCC-UCB and the LCC-UCB-GRAPH algorithm perform well and outperform
strategies that communicate through a central node
- Abstract（参考訳）: 我々は、$n$エージェントが確率的$k$ arm bandit問題のインスタンスと$k \gg n$で協調的に相互作用する問題を考える。
エージェントは、合計でT$のタイムステップ、通信ラウンドの数、各通信ラウンドにおけるビット数について、すべてのエージェントに対する累積的後悔を同時に最小化することを目指している。
筆者らは, 各エージェントがエポック終了後にのみ通信し, 知っている最高の腕の指標を共有する, ダブルエポックなアルゴリズムであるLCC-UCB(Limited Communication Collaboration - Upper Confidence Bound)を提案する。
我々のアルゴリズムであるLCC-UCBでは、各エージェントは$\tilde{O}\left(\sqrt{({K/N}+ N)T}\right)$を後悔し、$O(\log T)$のステップで通信し、各通信ステップで$O(\log K)$のビットをブロードキャストする。
最大度 $K_G$ と直径 $D$ のグラフをスパースに拡張し、$\tilde{O}\left(D\sqrt{(K/N+ K_G)DT}\right)$ のリコールバウンドを楽しむLCC-UCB-GRAPHを提案します。
最後に, LCC-UCB と LCC-UCB- Graph アルゴリズムは, 中央ノードを介して通信する, 良好な, かつ, 優れた戦略を示す。
関連論文リスト
- Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - 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) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - 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) - Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。
我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
論文 参考訳（メタデータ） (2021-02-22T02:46:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。