論文の概要: Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property
- arxiv url: http://arxiv.org/abs/2312.12067v2
- Date: Thu, 21 Dec 2023 18:28:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 17:36:26.529381
- Title: Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property
- Title（参考訳）: シングルコントローラを用いたマルチプレイヤーマルコフゲームにおける最適ポリシー勾配:ミニティプロパティを超えての収束
- Authors: Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, Tuomas
Sandholm
- Abstract要約: 単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
- 参考スコア（独自算出の注目度）: 89.96815099996132
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Policy gradient methods enjoy strong practical performance in numerous tasks
in reinforcement learning. Their theoretical understanding in multiagent
settings, however, remains limited, especially beyond two-player competitive
and potential Markov games. In this paper, we develop a new framework to
characterize optimistic policy gradient methods in multi-player Markov games
with a single controller. Specifically, under the further assumption that the
game exhibits an equilibrium collapse, in that the marginals of coarse
correlated equilibria (CCE) induce Nash equilibria (NE), we show convergence to
stationary $\epsilon$-NE in $O(1/\epsilon^2)$ iterations, where $O(\cdot)$
suppresses polynomial factors in the natural parameters of the game. Such an
equilibrium collapse is well-known to manifest itself in two-player zero-sum
Markov games, but also occurs even in a class of multi-player Markov games with
separable interactions, as established by recent work. As a result, we bypass
known complexity barriers for computing stationary NE when either of our
assumptions fails. Our approach relies on a natural generalization of the
classical Minty property that we introduce, which we anticipate to have further
applications beyond Markov games.
- Abstract（参考訳）: ポリシーグラデーション手法は強化学習における多くのタスクにおいて強力な実用的性能を享受する。
しかし、マルチエージェント設定に関する理論的理解は、特に2人のプレイヤーの競争と潜在的なマルコフゲームを超えて、限定的のままである。
本論文では,マルチプレイヤーマルコフゲームにおける楽観的なポリシー勾配手法を単一コントローラで特徴付ける新しいフレームワークを開発する。
特に、ゲームが平衡崩壊を示すというさらに仮定の下では、粗相関平衡(CCE)の限界がナッシュ平衡(NE)を誘導するので、ゲームの自然パラメータの多項式因子を$O(\cdot)$が抑制するような固定的な$\epsilon$-NE in $O(1/\epsilon^2)$反復に収束することを示す。
このような平衡崩壊は、2つのプレイヤーゼロサムマルコフゲームでも現れることがよく知られているが、最近の研究で確立されたような、分離可能な相互作用を持つマルチプレイヤーマルコフゲームでも起こる。
その結果、仮定のいずれかが失敗すると、定常NEを計算するための既知の複雑性障壁を回避できる。
我々のアプローチは、導入した古典的なミンティの自然一般化に依存しており、マルコフゲーム以外の応用が期待できる。
関連論文リスト
- 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) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳（メタデータ） (2023-03-31T22:50:47Z) - 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) - 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) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-08-03T16:41:01Z) - 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) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。