\(\widetilde{o}(t^{-1})\) Convergence To (coarse) Correlated Equilibria In Full-information General-sum Markov Games

Abstract

No-regret learning has a long history of being closely connected to game theory. Recent works have devised uncoupled no-regret learning dynamics that, when adopted by all the players in normal-form games, converge to various equilibrium solutions at a near-optimal rate of \(\widetilde\{O\}(T^\{-1\})\), a significant improvement over the \(O(1/\sqrt\{T\})\) rate of classic no-regret learners. However, analogous convergence results are scarce in Markov games, a more generic setting that lays the foundation for multi-agent reinforcement learning. In this work, we close this gap by showing that the optimistic-follow-the-regularized-leader (OFTRL) algorithm, together with appropriate value update procedures, can find \(\widetilde\{O\}(T^\{-1\})\)-approximate (coarse) correlated equilibria in full-information general-sum Markov games within \(T\) iterations. Numerical results are also included to corroborate our theoretical findings.

Stats

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

Related papers

• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34
• Policy Optimization For Markov Games: Unified Framework And Faster Convergence (2022)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Learning In Zero-sum Markov Games: Relaxing Strong Reachability And Mixing Time Assumptions (2023)0.00
• Learning Two-player Mixture Markov Games: Kernel Function Approximation And Correlated Equilibrium (2022)0.00
• The Harder Path: Last Iterate Convergence For Uncoupled Learning In Zero-sum Games With Bandit Feedback (2026)0.00