論文の概要: Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2210.01050v2
• Date: Tue, 4 Oct 2022 01:07:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 10:31:16.071356
• Title: Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームにおけるポリシー最適化のラストイテレート収束の高速化
• Authors: Shicong Cen, Yuejie Chi, Simon S. Du, Lin Xiao
• Abstract要約: 本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
• 参考スコア（独自算出の注目度）: 63.60117916422867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Reinforcement Learning (MARL) -- where multiple agents learn to interact in a shared dynamic environment -- permeates across a wide range of critical applications. While there has been substantial progress on understanding the global convergence of policy optimization methods in single-agent RL, designing and analysis of efficient policy optimization algorithms in the MARL setting present significant challenges, which unfortunately, remain highly inadequately addressed by existing theory. In this paper, we focus on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games, and study equilibrium finding algorithms in both the infinite-horizon discounted setting and the finite-horizon episodic setting. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method and the value is updated on a slower timescale. We show that, in the full-information tabular setting, the proposed method achieves a finite-time last-iterate linear convergence to the quantal response equilibrium of the regularized problem, which translates to a sublinear last-iterate convergence to the Nash equilibrium by controlling the amount of regularization. Our convergence results improve upon the best known iteration complexities, and lead to a better understanding of policy optimization in competitive Markov games.
• Abstract（参考訳）: マルチエージェント強化学習(marl:multi-agent reinforcement learning) — 複数のエージェントが共有動的環境で対話することを学ぶ – は、さまざまな重要なアプリケーションに浸透する。 単一エージェントRLにおけるポリシー最適化手法のグローバル収束の理解には大きな進歩があったが、MARLにおける効率的なポリシー最適化アルゴリズムの設計と分析は、残念ながら既存の理論によって高度に不十分に対処されている。 本稿では,競争的マルチエージェントrlの最も基本的な設定,すなわち2人プレイのゼロサムマルコフゲームに着目し,無限ホリゾンディスカウント設定と有限ホリゾンエピソディック設定の両方における均衡探索アルゴリズムについて検討する。 両エージェントの対称更新による単一ループポリシー最適化手法を提案する。この手法は,エントロピー規則化された楽観的乗算重み更新(OMWU)法を用いてポリシーを更新し,より遅い時間スケールで値を更新する。 本手法は,全情報表設定において,正則化量を制御することにより,正則化問題の量子化応答平衡に対する有限時間ラストイテレート線形収束をnash平衡にサブリニアラストイテレート収束に変換する。 我々の収束結果は最もよく知られたイテレーションの複雑さを改善し、競争的マルコフゲームにおけるポリシー最適化の理解を深める。

関連論文リスト

• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。 マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
  論文  参考訳（メタデータ） (2023-05-08T16:20:03Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。 自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
  論文  参考訳（メタデータ） (2022-03-14T17:24:03Z)
• Coordinated Proximal Policy Optimization [28.780862892562308]
  Coordinated Proximal Policy Optimization (CoPPO) は、オリジナルの Proximal Policy Optimization (PPO) をマルチエージェント設定に拡張するアルゴリズムである。 我々は,理論的な共同目的を最適化する際の政策改善の単調性を証明する。 そこで我々は,CoPPOにおけるそのような目的がエージェント間の動的信用割り当てを達成し,エージェントポリシーの同時更新時の高分散問題を軽減することができると解釈した。
  論文  参考訳（メタデータ） (2021-11-07T11:14:19Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization [40.21627891283402]
  本稿では,競争ゲームの均衡の計算問題について考察する。 エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
  論文  参考訳（メタデータ） (2021-05-31T17:51:15Z)
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence [60.20076757208645]
  本稿では,正規化RLを解くためのGPMDアルゴリズムを提案する。 我々は,このアルゴリズムが次元自由な方法で,全範囲の学習率に線形に収束することを実証した。
  論文  参考訳（メタデータ） (2021-05-24T02:21:34Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  安全強化学習(SRL)問題では、エージェントは期待される全報酬を最大化し、一定の制約の違反を避けるために環境を探索する。 これは、大域的最適ポリシーを持つSRLアルゴリズムの最初の分析である。
  論文  参考訳（メタデータ） (2020-11-11T16:05:14Z)
• Risk-Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance [3.062772835338966]
  本稿では,長期平均値を持つ無限段階離散時間マルコフ決定過程(MDP)の最適化問題について検討する。 性能差式が導出され、任意の2つの異なるポリシーの下で、MPPの平均分散結合メトリクスの差を定量化することができる。 最適政策の必要条件と決定論的政策の最適性が導出される。
  論文  参考訳（メタデータ） (2020-08-09T10:35:35Z)
• Convergence Guarantees of Policy Optimization Methods for Markovian Jump Linear Systems [3.3343656101775365]
  ガウスニュートン法は, 閉ループ力学を平均的に安定化させる制御器において, 線形速度で MJLS の最適状態フィードバック制御器に収束することを示す。 我々の理論を支持する一例を示す。
  論文  参考訳（メタデータ） (2020-02-10T21:13:42Z)

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

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