論文の概要: Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2511.02157v1
• Date: Tue, 04 Nov 2025 00:54:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.762045
• Title: Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games
• Title（参考訳）: 一般サムマルコフゲームにおける粗相関平衡の最適収束
• Authors: Asrin Efe Yorulmaz, Tamer Başar,
• Abstract要約: 非回帰学習力学はゲーム理論において中心的な役割を担い、均衡への分散収束を可能にする。 一般サムゲームにおけるCCEへの収束率を改善し、よりシャープな$mathcalO(log T / T)$からよりシャープな$mathcalO(log T / T)$に還元する。 これは、CEの最もよく知られた収束率と、$T$、反復数で一致し、アクションセットサイズへの依存も改善する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: No-regret learning dynamics play a central role in game theory, enabling decentralized convergence to equilibrium for concepts such as Coarse Correlated Equilibrium (CCE) or Correlated Equilibrium (CE). In this work, we improve the convergence rate to CCE in general-sum Markov games, reducing it from the previously best-known rate of $\mathcal{O}(\log^5 T / T)$ to a sharper $\mathcal{O}(\log T / T)$. This matches the best known convergence rate for CE in terms of $T$, number of iterations, while also improving the dependence on the action set size from polynomial to polylogarithmic-yielding exponential gains in high-dimensional settings. Our approach builds on recent advances in adaptive step-size techniques for no-regret algorithms in normal-form games, and extends them to the Markovian setting via a stage-wise scheme that adjusts learning rates based on real-time feedback. We frame policy updates as an instance of Optimistic Follow-the-Regularized-Leader (OFTRL), customized for value-iteration-based learning. The resulting self-play algorithm achieves, to our knowledge, the fastest known convergence rate to CCE in Markov games.
• Abstract（参考訳）: 非回帰学習力学はゲーム理論において中心的な役割を担い、粗相関平衡(CCE)や粗相関平衡(CE)といった概念の平衡への分散収束を可能にする。 本研究では、一般的なマルコフゲームにおけるCCEへの収束率を改善し、よりシャープな$\mathcal{O}(\log T / T)$からよりシャープな$\mathcal{O}(\log T / T)$に還元する。 これは、高次元の設定において、多項式から多対数収差指数的ゲインへのアクションセットサイズへの依存を改善しながら、反復数である$T$という観点で、CEの最もよく知られた収束率と一致する。 提案手法は, 実時間フィードバックに基づく学習率の調整を行うステージワイドスキームを用いて, 正規形式ゲームにおけるノンレグレットアルゴリズムの適応的なステップサイズ手法の最近の進歩を基盤として, マルコフ設定に拡張するものである。 我々は,OFTRL (Optimistic Follow-the-Regularized-Leader) の事例としてポリシーを更新する。 結果として得られる自己再生アルゴリズムは、マルコフゲームにおけるCCEへの最速の収束率を達成する。

関連論文リスト

• Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games [53.447182734351]
  Reverse Kullback-Leibler (KL) 正則化の下で, サンプル効率の向上を実現するアルゴリズムを開発し, 解析する。 我々は,2プレイヤーゼロサムマトリクスゲームとマルコフゲームの両方について検討する:マトリックスゲームでは,楽観的なボーナス付きベストレスポンスサンプリングに基づくアルゴリズムOMGを提案し,アルゴリズムSOMGを用いてマルコフゲームに拡張する。 両アルゴリズムは、標準の$widetildemathcalO(sqrtT)に加えて、KL正規化強度$beta$と共に逆スケールする$T$の対数後悔を実現する。
  論文  参考訳（メタデータ） (2025-10-15T01:00:54Z)
• Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games [44.95137108337898]
  我々は、相関平衡を計算するために、ほぼ最適の$tildeO(T-1)$収束率を得る未結合のポリシー最適化アルゴリズムを提供する。 我々のアルゴリズムは2つの主要素(スムーズな値更新)と(楽観的で規則化されたリーダーアルゴリズムとログバリア正規化器)を組み合わせることで構築される。
  論文  参考訳（メタデータ） (2024-01-26T23:13:47Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
  一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。 この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
  論文  参考訳（メタデータ） (2022-04-08T10:51:01Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)

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

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