mlsanityData to 7 Oct 2026

Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games

arXiv 2102.04540 ↗First posted 8 Feb 2021cs.LG cs.AI stat.MLcited by 66

Not on the map. Why?

Abstract (arXiv)

We study infinite-horizon discounted two-player zero-sum Markov games, and develop a decentralized algorithm that provably converges to the set of Nash equilibria under self-play. Our algorithm is based on running an Optimistic Gradient Descent Ascent algorithm on each state to learn the policies, with a critic that slowly learns the value of each state. To the best of our knowledge, this is the first algorithm in this setting that is simultaneously rational (converging to the opponent's best response when it uses a stationary policy), convergent (converging to the set of Nash equilibria under self-play), agnostic (no need to know the actions played by the opponent), symmetric (players taking symmetric roles in the algorithm), and enjoying a finite-time last-iterate convergence guarantee, all of which are desirable properties of decentralized algorithms.

Key facts. Cited by 66 papers in the map (data through 7 Oct 2026). Builds on 19 of its 47 references that are in the map. First posted on arXiv 8 Feb 2021.

Builds on

19 of 47 references.

References · 19

  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. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  9. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  10. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  11. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  12. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
7 more
  1. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  2. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  3. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  4. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  5. 2020Fictitious play in zero-sum stochastic gamescited by 24
  6. 2019Learning to Collaborate in Markov Decision Processescited by 14
  7. 2020Linear Last-iterate Convergence in Constrained Saddle-point Optimizationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 23; 2023: 16; 2024: 5; 2025: 4; 2026: 6.

66 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  3. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  4. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  5. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  6. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  7. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  8. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  9. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  10. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  11. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  12. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
38 more
  1. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  2. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  3. 2021Independent Learning in Stochastic Gamescited by 20
  4. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  5. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  6. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  7. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  8. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  9. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  10. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 14
  11. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  12. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
  13. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  14. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  15. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  16. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  17. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  18. 2023Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problemscited by 11
  19. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  20. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  21. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  22. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  23. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  24. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  25. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  26. 2021MDPGT: Momentum-based Decentralized Policy Gradient Trackingcited by 6
  27. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  28. 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
  29. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  30. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  31. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  32. 2022Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Gamescited by 4
  33. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  34. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  35. 2025Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guaranteescited by 3
  36. 2025Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problemscited by 3
  37. 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 3
  38. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 3

50 most cited of 66 All 66 (JSON)