mlsanityData to 7 Oct 2026

Can We Find Nash Equilibria at a Linear Rate in Markov Games?

arXiv 2303.03095 ↗First posted 3 Mar 2023cs.GT cs.LG math.OCcited by 9

Not on the map. Why?

Abstract (arXiv)

We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design a policy optimization algorithm for either agent satisfying two properties. First, the player does not need to know the policy of the opponent to update its policy. Second, when both players adopt the algorithm, their joint policy converges to a Nash equilibrium of the game. To this end, we construct a meta algorithm, dubbed as textttHomotopy-PO, which provably finds a Nash equilibrium at a global linear rate. In particular, textttHomotopy-PO interweaves two base algorithms textttLocal-Fast and textttGlobal-Slow via homotopy continuation. textttLocal-Fast is an algorithm that enjoys local linear convergence while textttGlobal-Slow is an algorithm that converges globally but at a slower sublinear rate. By switching between these two base algorithms, textttGlobal-Slow essentially serves as a ``guide'' which identifies a benign neighborhood where textttLocal-Fast enjoys fast convergence. However, since the exact size of such a neighborhood is unknown, we apply a doubling trick to switch between these two base algorithms. The switching scheme is delicately designed so that the aggregated performance of the algorithm is driven by textttLocal-Fast. Furthermore, we prove that textttLocal-Fast and textttGlobal-Slow can both be instantiated by variants of optimistic gradient descent/ascent (OGDA) method, which is of independent interest.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 26 of its 55 references that are in the map. First posted on arXiv 3 Mar 2023.

Builds on

26 of 55 references.

References · 26

  1. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  2. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  3. 2017Training GANs with Optimismcited by 217
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  5. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  6. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 167
  7. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  8. 2017Cycles in adversarial regularized learningcited by 122
  9. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  10. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  11. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  12. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
14 more
  1. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  3. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  4. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  5. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  6. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  7. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  8. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  9. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  10. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  11. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  12. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  13. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  14. 2013Optimal computational and statistical rates of convergence for sparse nonconvex learning problemscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 2; 2025: 2; 2026: 1.

9 papers.

  1. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  2. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  3. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  4. 2024Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexitycited by 10
  5. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  6. 2023Robust Adversarial Reinforcement Learning via Bounded Rationality Curriculacited by 9
  7. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  8. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  9. 2026Robust Adversarial Reinforcement Learning with Risk Sensitivity and Critic Consistency Regularizationcited by 0