論文の概要: Solving Zero-Sum Convex Markov Games

• arxiv url: http://arxiv.org/abs/2506.16120v1
• Date: Thu, 19 Jun 2025 08:12:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:04.991379
• Title: Solving Zero-Sum Convex Markov Games
• Title（参考訳）: ゼロサム凸マルコフゲームの解決
• Authors: Fivos Kalogiannis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ian Gemp, Georgios Piliouras,
• Abstract要約: 本研究では,Nash equilibria (NE) に独立手法を用いて,2プレーヤゼロサムゲーム (cMG) におけるグローバルコンバージェンスを初めて保証する。 NC-pおよび両側pPL条件下での一般的な制約付きmin-max問題に対処する。
• 参考スコア（独自算出の注目度）: 38.68653814645517
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We contribute the first provable guarantees of global convergence to Nash equilibria (NE) in two-player zero-sum convex Markov games (cMGs) by using independent policy gradient methods. Convex Markov games, recently defined by Gemp et al. (2024), extend Markov decision processes to multi-agent settings with preferences that are convex over occupancy measures, offering a broad framework for modeling generic strategic interactions. However, even the fundamental min-max case of cMGs presents significant challenges, including inherent nonconvexity, the absence of Bellman consistency, and the complexity of the infinite horizon. We follow a two-step approach. First, leveraging properties of hidden-convex--hidden-concave functions, we show that a simple nonconvex regularization transforms the min-max optimization problem into a nonconvex-proximal Polyak-Lojasiewicz (NC-pPL) objective. Crucially, this regularization can stabilize the iterates of independent policy gradient methods and ultimately lead them to converge to equilibria. Second, building on this reduction, we address the general constrained min-max problems under NC-pPL and two-sided pPL conditions, providing the first global convergence guarantees for stochastic nested and alternating gradient descent-ascent methods, which we believe may be of independent interest.
• Abstract（参考訳）: 我々は、独立ポリシー勾配法を用いて、2プレイヤゼロサム凸マルコフゲーム(cMG)におけるナッシュ平衡(NE)へのグローバル収束の証明可能な最初の保証を貢献する。 近ごろ Gemp et al (2024) によって定義された凸マルコフゲームは、マルコフ決定プロセスをマルチエージェント設定に拡張する。 しかし、cMG の基本的な min-max の場合でさえ、本質的に非凸性、ベルマンの一貫性の欠如、無限の地平線の複雑さなど、大きな課題を呈している。 2段階のアプローチを踏襲する。 まず、隠蔽凸-隠蔽凸関数の性質を利用して、単純な非凸正則化が、min-max最適化問題を非凸-近位ポリアック-ロジャシエヴィチ(NC-pPL)目的に変換することを示す。 重要なことに、この正規化は独立政策勾配法の反復を安定化させ、最終的に平衡に収束させる。 第二に、NC-pPLと両側pPL条件下での一般的な制約されたmin-max問題に対処し、確率的ネストおよび交互勾配勾配上昇法に対する最初の大域収束保証を提供する。

関連論文リスト

• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  本稿では,最小化問題と最小化問題の両方に対して,MC-SGMの包括的一般化解析を行う。 我々はスムーズかつ非スムーズなケースに対して最適な過剰人口リスク境界を確立する。 コンベックス・コンケーブ問題に対する最初期のほぼ最適な収束率を期待と高い確率で開発する。
  論文  参考訳（メタデータ） (2022-09-16T15:42:51Z)
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs [21.347689976296834]
  我々は、割引された最適レート問題を解くために、自然政策勾配法を用いる。 また、2つのサンプルベースNPG-PDアルゴリズムに対して収束と有限サンプル保証を提供する。
  論文  参考訳（メタデータ） (2022-06-06T04:28:04Z)
• Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction [18.95829896746939]
  目的と制約の両方を状態行動占有度尺度の凹凸関数として定義したコンケーブCMDPについて検討する。 本稿では, 基本変数をポリシー勾配の上昇により更新し, 二次変数を予測下次降下により更新する, 可変生成プライマル・デュアルポリシー勾配を提案する。
  論文  参考訳（メタデータ） (2022-05-22T02:50:16Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)

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

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