論文の概要: Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2408.15173v1
- Date: Tue, 27 Aug 2024 16:11:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-28 13:13:36.175761
- Title: Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning
- Title(参考訳): 効率的なマルチエージェント強化学習のための爆発的近似対称性
- Authors: Batuhan Yardim, Niao He,
- Abstract要約: 我々は、任意の有限プレイヤー、おそらく非対称なゲームから「誘導MFG」に拡張する方法論を提供する。
まず、$N$-player の動的ゲームは、明示的な Kirszbraun 拡張によって、無限プレーヤ連続体に対称性を持ち、滑らかに拡張できることを示す。
単調性を満たす特定のゲームに対しては、$widetildemathcalO(varepsilon-6)$のサンプル複雑性を証明し、$N$エージェントゲームに対して、$varepsilon$-Nashを対称性バイアスまで学習する。
- 参考スコア(独自算出の注目度): 19.543995541149897
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Mean-field games (MFG) have become significant tools for solving large-scale multi-agent reinforcement learning problems under symmetry. However, the assumption of exact symmetry limits the applicability of MFGs, as real-world scenarios often feature inherent heterogeneity. Furthermore, most works on MFG assume access to a known MFG model, which might not be readily available for real-world finite-agent games. In this work, we broaden the applicability of MFGs by providing a methodology to extend any finite-player, possibly asymmetric, game to an "induced MFG". First, we prove that $N$-player dynamic games can be symmetrized and smoothly extended to the infinite-player continuum via explicit Kirszbraun extensions. Next, we propose the notion of $\alpha,\beta$-symmetric games, a new class of dynamic population games that incorporate approximate permutation invariance. For $\alpha,\beta$-symmetric games, we establish explicit approximation bounds, demonstrating that a Nash policy of the induced MFG is an approximate Nash of the $N$-player dynamic game. We show that TD learning converges up to a small bias using trajectories of the $N$-player game with finite-sample guarantees, permitting symmetrized learning without building an explicit MFG model. Finally, for certain games satisfying monotonicity, we prove a sample complexity of $\widetilde{\mathcal{O}}(\varepsilon^{-6})$ for the $N$-agent game to learn an $\varepsilon$-Nash up to symmetrization bias. Our theory is supported by evaluations on MARL benchmarks with thousands of agents.
- Abstract(参考訳): 平均場ゲーム(MFG)は、対称性の下で大規模マルチエージェント強化学習問題を解決する重要なツールとなっている。
しかし、正確な対称性の仮定はMFGの適用性を制限する。
さらに、MFGに関するほとんどの研究は、実世界の有限エージェントゲームでは容易に利用できない既知のMFGモデルへのアクセスを前提としている。
本研究では,任意の有限プレイヤ,おそらく非対称なゲームから「誘導的MFG」に拡張する方法論を提供することにより,MFGの適用性を広げる。
まず、$N$-player の動的ゲームは、明示的な Kirszbraun 拡張によって、無限プレーヤ連続体に対称性を持ち、滑らかに拡張できることを示す。
次に、近似置換不変性を含む動的集団ゲームの新しいクラスである$\alpha,\beta$-symmetricゲームの概念を提案する。
$\alpha,\beta$-symmetric game に対して、明示的な近似境界を確立し、誘導MFG のナッシュポリシーが$N$-player dynamic game の近似ナッシュであることを証明した。
我々は,TD学習が有限サンプル保証付き$N$-playerゲームのトラジェクトリを用いて小さなバイアスに収束することを示し,明示的なMFGモデルを構築することなく,対称性学習を可能にする。
最後に、単調性を満たす特定のゲームに対して、シンメトリゼーションバイアスに$\varepsilon$-Nashを学習するために$N$-agentゲームに対して$\widetilde{\mathcal{O}}(\varepsilon^{-6})$のサンプル複雑性を証明する。
我々の理論は、何千ものエージェントによるMARLベンチマークの評価によって支持されている。
関連論文リスト
- MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
本稿では,シーケンシャルゲームのナッシュ平衡計算のためのオンライン平均場強化学習アルゴリズムを提案する。
MFOMLは、ナッシュ平衡を実証的に解くための、最初の完全近似マルチエージェント強化学習アルゴリズムである。
副生成物として、モノトーン平均場ゲームの近似計算のための最初のトラクタブル大域収束計算も得られる。
論文 参考訳(メタデータ) (2024-05-01T02:19:31Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳(メタデータ) (2023-12-19T11:34:10Z) - Learning Discrete-Time Major-Minor Mean Field Games [61.09249862334384]
本稿では,M3FG(Major-minor MFG)の新たな離散時間バージョンと,実演に基づく学習アルゴリズムを提案する。
M3FGは一般的な雑音でMFGを一般化し、ランダムな異種環境状態だけでなく、メジャープレイヤーも扱える。
論文 参考訳(メタデータ) (2023-12-17T18:22:08Z) - Scalable and Independent Learning of Nash Equilibrium Policies in
$n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
独立な連鎖と未知の遷移行列を持つゲームについて研究する。
このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。
我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-04T03:04:09Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳(メタデータ) (2023-05-31T22:09:24Z) - Policy Mirror Ascent for Efficient and Independent Learning in Mean
Field Games [35.86199604587823]
平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。
ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
論文 参考訳(メタデータ) (2022-12-29T20:25:18Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳(メタデータ) (2022-08-22T17:24:55Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳(メタデータ) (2022-08-22T08:31:46Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳(メタデータ) (2022-07-25T18:29:16Z) - Evolutionary Game-Theoretical Analysis for General Multiplayer
Asymmetric Games [22.753799819424785]
不正確さなしに、ペイオフテーブルと動的分析のギャップを埋める。
いくつかの古典ゲームにおいて,本手法を最先端のゲームと比較する。
論文 参考訳(メタデータ) (2022-06-22T14:06:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。