Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games

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 f

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyorulmaz2025near

Related papers

• \(\widetilde{o}(t^{-1})\) Convergence To (coarse) Correlated Equilibria In Full-information General-sum Markov Games (2024)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34
• Decentralized MARL For Coarse Correlated Equilibrium In Aggregative Markov Games (2026)0.00
• Provably Efficient Reinforcement Learning In Decentralized General-sum Markov Games (2021)0.00
• Policy Optimization For Markov Games: Unified Framework And Faster Convergence (2022)0.00
• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26