論文の概要: Breaking the Curse of Multiagency: Provably Efficient Decentralized
Multi-Agent RL with Function Approximation
- arxiv url: http://arxiv.org/abs/2302.06606v1
- Date: Mon, 13 Feb 2023 18:59:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 14:19:03.866509
- Title: Breaking the Curse of Multiagency: Provably Efficient Decentralized
Multi-Agent RL with Function Approximation
- Title（参考訳）: マルチアジェンシーの呪いを破る: 関数近似を用いた効率的な分散マルチエージェントrl
- Authors: Yuanhao Wang, Qinghua Liu, Yu Bai, Chi Jin
- Abstract要約: 本稿では,マルチ緊急近似の呪いを確実に解決するMARLアルゴリズムの1行について述べる。
より弱いバージョンのCCEを学習する代わりに、このアルゴリズムは一般的な関数近似の下で幅広い問題に適用される。
我々のアルゴリズムは常にMarkov CCEを出力し、最適レートは$widetildemathcalO(epsilon-2)$で$epsilon$-optimal Solutionを見つける。
- 参考スコア（独自算出の注目度）: 44.051717720483595
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A unique challenge in Multi-Agent Reinforcement Learning (MARL) is the curse
of multiagency, where the description length of the game as well as the
complexity of many existing learning algorithms scale exponentially with the
number of agents. While recent works successfully address this challenge under
the model of tabular Markov Games, their mechanisms critically rely on the
number of states being finite and small, and do not extend to practical
scenarios with enormous state spaces where function approximation must be used
to approximate value functions or policies.
This paper presents the first line of MARL algorithms that provably resolve
the curse of multiagency under function approximation. We design a new
decentralized algorithm -- V-Learning with Policy Replay, which gives the first
polynomial sample complexity results for learning approximate Coarse Correlated
Equilibria (CCEs) of Markov Games under decentralized linear function
approximation. Our algorithm always outputs Markov CCEs, and achieves an
optimal rate of $\widetilde{\mathcal{O}}(\epsilon^{-2})$ for finding
$\epsilon$-optimal solutions. Also, when restricted to the tabular case, our
result improves over the current best decentralized result
$\widetilde{\mathcal{O}}(\epsilon^{-3})$ for finding Markov CCEs. We further
present an alternative algorithm -- Decentralized Optimistic Policy Mirror
Descent, which finds policy-class-restricted CCEs using a polynomial number of
samples. In exchange for learning a weaker version of CCEs, this algorithm
applies to a wider range of problems under generic function approximation, such
as linear quadratic games and MARL problems with low ''marginal'' Eluder
dimension.
- Abstract（参考訳）: マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)の独特な課題は、ゲームの記述長だけでなく、既存の学習アルゴリズムの複雑さがエージェントの数とともに指数関数的にスケールするという、マルチエージェントの呪いである。
最近の研究は、表型マルコフゲーム(英語版)のモデルの下でこの課題にうまく対処しているが、それらのメカニズムは有限かつ小さい状態の数に依存しており、関数近似が値関数やポリシーの近似に使われるような巨大な状態空間を持つ実用的なシナリオには拡張されない。
本稿では,関数近似の下でのマルチ緊急の呪いを確実に解消するMARLアルゴリズムの最初の行を示す。
我々は,マルコフゲームにおける線形関数近似の下での粗相関平衡(CCE)を学習するための最初の多項式サンプル計算結果を与える,ポリシ・リプレイによるVラーニング(V-Learning)を新たに設計する。
我々のアルゴリズムは常にMarkov CCEを出力し、$\epsilon$-optimal Solutionを見つけるために$\widetilde{\mathcal{O}}(\epsilon^{-2})$の最適なレートを達成する。
また、表のケースに制限された場合、マルコフ CCE を見つけるために現在の最良の分散結果 $\widetilde{\mathcal{O}}(\epsilon^{-3})$ よりも改善する。
さらに、多項式数のサンプルを用いてポリシークラス制限CCEを求める分散最適化政策ミラーDescentという別のアルゴリズムを提案する。
より弱いバージョンのCCEを学習する代わりに、このアルゴリズムは、線形二次ゲームや低次元の 'marginal' エルダー次元の MARL 問題など、一般的な関数近似の下での幅広い問題に適用する。
関連論文リスト
- RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model [15.596599935486534]
シミュレータへの局所アクセスを伴う粗相関平衡(CCE)を学習するための新しいアルゴリズムLin-Confident-FTRLを導入する。
状態空間のサイズに対数的依存がある限り、Lin-Confident-FTRLは証明可能な最適精度で$O(epsilon-2)$で$epsilon$-CCEを学ぶ。
本分析は,単一エージェントのローカルプランニング文献における仮想ポリシー境界を一般化する。
論文 参考訳（メタデータ） (2024-03-18T07:54:11Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - Breaking the Curse of Multiagents in a Large State Space: RL in Markov
Games with Independent Linear Function Approximation [56.715186432566576]
そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。
我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。
提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
論文 参考訳（メタデータ） (2023-02-07T18:47:48Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文 参考訳（メタデータ） (2022-10-30T22:58:22Z) - Sample and Communication-Efficient Decentralized Actor-Critic Algorithms
with Finite-Time Analysis [27.21581944906418]
Actor-critic (AC)アルゴリズムは分散マルチエージェントシステムで広く採用されている。
我々は、プライベートでサンプルと通信効率のよい2つの分散ACと自然交流(NAC)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-08T15:02:21Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。