mlsanityData to 7 Oct 2026

widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games

arXiv 2403.07890 ↗First posted 2 Feb 2024cs.GT cs.AI cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 widetildeO(T-1), a significant improvement over the O(1/√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 widetildeO(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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 45 references that are in the map. First posted on arXiv 2 Feb 2024.

Builds on

29 of 45 references.

References · 29

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  7. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  8. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  9. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  10. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  11. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  12. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
17 more
  1. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  2. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  3. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  4. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  5. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  6. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  7. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  8. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  9. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  10. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  11. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  12. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  13. 2020Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learningcited by 13
  14. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  15. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  16. 2014Policy Iteration for Decentralized Control of Markov Decision Processescited by 10
  17. 2020Reinforcement Learning in Decentralized Stochastic Control Systems with Partial History Sharingcited by 4

Built on by

Not cited yet.