mlsanityData to 7 Oct 2026

Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games

arXiv 2401.15240 ↗First posted 26 Jan 2024cs.LG cs.GT math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve O(T-1/2) convergence rate to a correlated equilibrium and an accelerated O(T-3/4) convergence rate to the weaker notion of coarse correlated equilibrium. In this paper, we improve both results significantly by providing an uncoupled policy optimization algorithm that attains a near-optimal tildeO(T-1) convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i) smooth value updates and (ii) the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 21 of its 47 references that are in the map. First posted on arXiv 26 Jan 2024.

Builds on

21 of 47 references.

References · 21

  1. 2019The Hanabi Challenge: A New Frontier for AI Researchcited by 194
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  4. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  5. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  6. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  7. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  8. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  9. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  10. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  11. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  12. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
9 more
  1. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  2. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  3. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  4. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  5. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  6. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  7. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  8. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  9. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 6; 2026: 2.

11 papers.

  1. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  2. 2025Learning and Computation of Phi-Equilibria at the Frontier of Tractabilitycited by 3
  3. 2024Learning to Steer Markovian Agents under Model Uncertaintycited by 2
  4. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  5. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  6. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 1
  7. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  8. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  9. 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
  10. 2025Playing Markov Games Without Observing Payoffscited by 0
  11. 2025Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Gamescited by 0