論文の概要: Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update
- arxiv url: http://arxiv.org/abs/2403.15935v1
- Date: Sat, 23 Mar 2024 21:39:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-26 20:22:33.331625
- Title: Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update
- Title（参考訳）: 新しいアプローチによる完全分散型MARL政策評価 : ローカルTD更新
- Authors: Fnu Hairi, Zifan Zhang, Jia Liu,
- Abstract要約: 我々は,MARL-PEのサンプルと通信の複雑さを下げる上で,複数の局所的なTD更新ステップが効果的であることを示す。
理論的には、最適なサンプル複雑性に到達するために、局所的なTD更新アプローチの通信複雑性は$mathcalO (1/epsilon1/2log (1/epsilon))$である。
- 参考スコア（独自算出の注目度）: 4.881380918771884
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In actor-critic framework for fully decentralized multi-agent reinforcement learning (MARL), one of the key components is the MARL policy evaluation (PE) problem, where a set of $N$ agents work cooperatively to evaluate the value function of the global states for a given policy through communicating with their neighbors. In MARL-PE, a critical challenge is how to lower the sample and communication complexities, which are defined as the number of training samples and communication rounds needed to converge to some $\epsilon$-stationary point. To lower communication complexity in MARL-PE, a "natural'' idea is to perform multiple local TD-update steps between each consecutive rounds of communication to reduce the communication frequency. However, the validity of the local TD-update approach remains unclear due to the potential "agent-drift'' phenomenon resulting from heterogeneous rewards across agents in general. This leads to an interesting open question: Can the local TD-update approach entail low sample and communication complexities? In this paper, we make the first attempt to answer this fundamental question. We focus on the setting of MARL-PE with average reward, which is motivated by many multi-agent network optimization problems. Our theoretical and experimental results confirm that allowing multiple local TD-update steps is indeed an effective approach in lowering the sample and communication complexities of MARL-PE compared to consensus-based MARL-PE algorithms. Specifically, the local TD-update steps between two consecutive communication rounds can be as large as $\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$ in order to converge to an $\epsilon$-stationary point of MARL-PE. Moreover, we show theoretically that in order to reach the optimal sample complexity, the communication complexity of local TD-update approach is $\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$.
- Abstract（参考訳）: 完全に分散化されたマルチエージェント強化学習(MARL)のためのアクター批判フレームワークでは、MARLポリシー評価(PE)問題が鍵となる。
MARL-PEにおいて重要な課題は、サンプルと通信の複雑さを下げることであり、これは、ある$\epsilon$-stationaryポイントに収束するのに必要な訓練サンプルと通信ラウンドの数として定義される。
MARL-PEにおける「自然な」アイデアは、通信周波数を減少させるために、連続する通信ラウンド間で複数の局所的なTD更新ステップを実行することであるが、エージェント間の不均一な報酬から生じる「エージェントドリフト」現象が原因で、局所的なTD更新アプローチの有効性は明らかになっていない。
局所的なTD更新アプローチは、低いサンプルと通信の複雑さを伴いますか?
本稿では,この根本的な疑問に答える最初の試みを行う。
我々は,多くのマルチエージェントネットワーク最適化問題に動機づけられた,平均報酬を伴うMARL-PEの設定に焦点をあてる。
理論的および実験的結果から,複数の局所的なTD更新ステップが可能であることは,MARL-PEアルゴリズムと比較して,MARL-PEのサンプルと通信の複雑さを低下させる上で有効なアプローチであることが明らかとなった。
具体的には、2つの連続する通信ラウンド間の局所的なTD更新ステップは、MARL-PEの$\epsilon$-stationaryポイントに収束するために$\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$にできる。
さらに、最適なサンプル複雑性に到達するために、局所的なTD更新アプローチの通信複雑性は$\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$であることを示す。
関連論文リスト
- The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity [2.845817138242963]
DGT(Decentralized Gradient Tracking)とDGD(Decentralized Gradient Descent)の2つの基本的な分散最適化手法を再検討する。
K > 1$ ローカル更新のステップを組み込むことで通信の複雑さを低減できることを示す。
論文 参考訳（メタデータ） (2024-03-23T00:01:34Z) - A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical
Federated Learning [24.60603310894048]
コミュニケーション効率は学習における大きな課題である
MTCD(Multi-Token Coordinate Descent)を提案する。
MTCDは、半分散垂直連邦設定のための調整可能な通信効率である。
論文 参考訳（メタデータ） (2023-09-18T17:59:01Z) - DFedADMM: Dual Constraints Controlled Model Inconsistency for
Decentralized Federated Learning [52.83811558753284]
分散学習(DFL)は、中央サーバーを捨て、分散通信ネットワークを確立する。
既存のDFL手法は依然として、局所的な矛盾と局所的な過度なオーバーフィッティングという2つの大きな課題に悩まされている。
論文 参考訳（メタデータ） (2023-08-16T11:22:36Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Federated Learning with Regularized Client Participation [1.433758865948252]
Federated Learning(FL)は、複数のクライアントが協力して機械学習タスクを解決する分散機械学習アプローチである。
FLの主な課題の1つは、多くのクライアントがトレーニングプロセスに関与しているときに発生する部分的な参加の問題である。
本稿では,新しい手法を提案し,新しいクライアント参加方式を設計する。
論文 参考訳（メタデータ） (2023-02-07T18:26:07Z) - STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal
Sample and Communication Complexities for Federated Learning [58.6792963686231]
フェデレートラーニング(FL)とは、複数のワーカノード(WN)がローカルデータを用いてジョイントモデルを構築するパラダイムを指す。
WNの最小更新方向、最初のミニバッチサイズ、ローカル更新頻度をどうやって選択するかは明らかになっていない。
局所的な更新頻度と局所的なミニサイズとの間にはトレードオフ曲線があることを示し、上記の複雑さを維持できることを示す。
論文 参考訳（メタデータ） (2021-06-19T06:13:45Z) - Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
論文 参考訳（メタデータ） (2021-03-24T12:48:08Z) - Multi-Agent Trust Region Policy Optimization [34.91180300856614]
TRPOのポリシー更新は,マルチエージェントケースに対する分散コンセンサス最適化問題に変換可能であることを示す。
マルチエージェントTRPO(MATRPO)と呼ばれる分散MARLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-15T17:49:47Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳（メタデータ） (2020-10-02T10:41:59Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - F2A2: Flexible Fully-decentralized Approximate Actor-critic for
Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。
本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。
当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
論文 参考訳（メタデータ） (2020-04-17T14:56:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。