論文の概要: Policy Optimization for Markov Games: Unified Framework and Faster Convergence

• arxiv url: http://arxiv.org/abs/2206.02640v1
• Date: Mon, 6 Jun 2022 14:23:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 18:28:33.615564
• Title: Policy Optimization for Markov Games: Unified Framework and Faster Convergence
• Title（参考訳）: markov gamesのポリシー最適化:統一フレームワークとより高速なコンバージェンス
• Authors: Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, Yu Bai
• Abstract要約: このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
• 参考スコア（独自算出の注目度）: 81.3266426402464
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies policy optimization algorithms for multi-agent reinforcement learning. We begin by proposing an algorithm framework for two-player zero-sum Markov Games in the full-information setting, where each iteration consists of a policy update step at each state using a certain matrix game algorithm, and a value update step with a certain learning rate. This framework unifies many existing and new policy optimization algorithms. We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game, as long as the matrix game algorithms achieve low weighted regret at each state, with respect to weights determined by the speed of the value updates. Next, we show that this framework instantiated with the Optimistic Follow-The-Regularized-Leader (OFTRL) algorithm at each state (and smooth value updates) can find an $\mathcal{\widetilde{O}}(T^{-5/6})$ approximate NE in $T$ iterations, which improves over the current best $\mathcal{\widetilde{O}}(T^{-1/2})$ rate of symmetric policy optimization type algorithms. We also extend this algorithm to multi-player general-sum Markov Games and show an $\mathcal{\widetilde{O}}(T^{-3/4})$ convergence rate to Coarse Correlated Equilibria (CCE). Finally, we provide a numerical example to verify our theory and investigate the importance of smooth value updates, and find that using "eager" value updates instead (equivalent to the independent natural policy gradient algorithm) may significantly slow down the convergence, even on a simple game with $H=2$ layers.
• Abstract（参考訳）: 本稿では,マルチエージェント強化学習のためのポリシー最適化アルゴリズムについて検討する。 各イテレーションは、あるマトリックスゲームアルゴリズムを用いて各状態のポリシー更新ステップと、ある学習率の値更新ステップとからなる全情報設定において、2人のプレイヤーのゼロサムマルコフゲームのためのアルゴリズムフレームワークを提案することから始める。 このフレームワークは多くの既存および新しいポリシー最適化アルゴリズムを統合する。 このアルゴリズムの状態平均ポリシは,行列ゲームアルゴリズムが各状態において,値更新の速度によって決定される重みに関して,低重み付き後悔を達成する限り,ゲームのナッシュ均衡(NE)に収束することを示す。 次に、このフレームワークが各状態(およびスムーズな値更新)における最適化Follow-The-Regularized-Leader (OFTRL)アルゴリズムでインスタンス化され、$\mathcal{\widetilde{O}}(T^{-5/6})$ almost NE in $T$ iterations, which improves on the current best $\mathcal{\widetilde{O}}(T^{-1/2})$ rate of symmetric policy optimization type algorithm。 また、このアルゴリズムをマルチプレイヤー汎用マルコフゲームに拡張し、CCE(Coarse Correlated Equilibria)への$\mathcal{\widetilde{O}}(T^{-3/4})$収束率を示す。 最後に、本理論を検証し、滑らかな値更新の重要性を検討する数値例を示し、代わりに「イーガー」値更新(独立自然ポリシー勾配アルゴリズムに相当)を使用することで、h=2$の単純なゲームであっても収束が著しく遅くなる可能性があることを見出した。

関連論文リスト

• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。 目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-03-03T02:40:26Z)
• 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)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games [37.70703888365849]
  無限水平割引2プレイヤーゼロサムマルコフゲームについて検討する。 我々は,自己再生下でのナッシュ均衡に収束する分散アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-02-08T21:45:56Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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