論文の概要: Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2302.03673v3
• Date: Wed, 21 Jun 2023 21:15:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-23 17:43:16.420135
• Title: Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation
• Title（参考訳）: 大規模状態空間におけるマルチエージェントの呪いを破る:独立線型関数近似を持つマルコフゲームにおけるrl
• Authors: Qiwen Cui, Kaiqing Zhang, Simon S. Du
• Abstract要約: そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。 我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。 提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
• 参考スコア（独自算出の注目度）: 56.715186432566576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new model, independent linear Markov game, for multi-agent reinforcement learning with a large state space and a large number of agents. This is a class of Markov games with independent linear function approximation, where each agent has its own function approximation for the state-action value functions that are marginalized by other players' policies. We design new algorithms for learning the Markov coarse correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample complexity bounds that only scale polynomially with each agent's own function class complexity, thus breaking the curse of multiagents. In contrast, existing works for Markov games with function approximation have sample complexity bounds scale with the size of the \emph{joint action space} when specialized to the canonical tabular Markov game setting, which is exponentially large in the number of agents. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; (2) separating learning Markov equilibria and exploration in the Markov games, which allows us to use the full-information no-regret learning oracle instead of the stronger bandit-feedback no-regret learning oracle used in the tabular setting. Furthermore, we propose an iterative-best-response type algorithm that can learn pure Markov Nash equilibria in independent linear Markov potential games. In the tabular case, by adapting the policy replay mechanism for independent linear Markov games, we propose an algorithm with $\widetilde{O}(\epsilon^{-2})$ sample complexity to learn Markov CCE, which improves the state-of-the-art result $\widetilde{O}(\epsilon^{-3})$ in Daskalakis et al. 2022, where $\epsilon$ is the desired accuracy, and also significantly improves other problem parameters.
• Abstract（参考訳）: 本研究では,大規模状態空間と多数のエージェントを有するマルチエージェント強化学習のための独立線形マルコフゲームを提案する。 これは独立線型関数近似を持つマルコフゲームの一種であり、各エージェントは他のプレイヤーのポリシーによって疎外される状態-作用値関数に対して独自の関数近似を持つ。 マルコフ粗相関平衡(cce)とマルコフ相関平衡(ce)と、各エージェントの関数クラスの複雑性と多項式的にしかスケールしないサンプル複雑性境界を学習するための新しいアルゴリズムを設計し、マルチエージェントの呪いを破る。 対照的に、関数近似を持つマルコフゲームに対する既存の研究は、エージェント数で指数関数的に大きい正準タブ状マルコフゲームセッティングに特化する場合、サンプル複雑性は \emph{joint action space} のサイズと一致する。 我々のアルゴリズムは、2つの重要な技術革新に依存している: 1)複数のエージェントによって引き起こされる非定常性に取り組むポリシーリプレイと関数近似の使用。2)学習マルコフ平衡とマルコフゲームでの探索を分離することで、オラクルを学習するフル情報の非回帰を、より強固なバンディットフィードバックを学習するオラクルの代わりに使用できる。 さらに,独立線形マルコフポテンシャルゲームにおいて純粋マルコフナッシュ平衡を学習できる反復的最良応答型アルゴリズムを提案する。 図表の場合、独立線型マルコフゲームに対するポリシー再生機構を適応させることで、マルコフ CCE を学習するためのサンプル複雑性を$\widetilde{O}(\epsilon^{-2}) とするアルゴリズムを提案し、ダスカラキスらで $\widetilde{O}(\epsilon^{-3})$ と $\epsilon$ は所望の精度であり、他の問題パラメータも大幅に改善する。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
  一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。 この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
  論文  参考訳（メタデータ） (2022-04-08T10:51:01Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。