mlsanityData to 7 Oct 2026

Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games

arXiv 2511.02157 ↗First posted 4 Nov 2025cs.GT cs.AI cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 O(log5 T / T) to a sharper 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 30 references that are in the map. First posted on arXiv 4 Nov 2025.

Builds on

20 of 30 references.

References · 20

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2016Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collectioncited by 312
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  6. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  8. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  9. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  10. 2025MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learningcited by 80
  11. 2025ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learningcited by 78
  12. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
8 more
  1. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  2. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 40
  3. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  4. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  5. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  6. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  7. 2025Faster Rates for No-Regret Learning in General Games via Cautious Optimismcited by 10
  8. 2023Optimizing Trading Strategies in Quantitative Markets using Multi-Agent Reinforcement Learningcited by 7

Built on by

Not cited yet.