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

arXiv: https://arxiv.org/abs/2303.03095 · HTML: https://mlsanity.com/paper/2303.03095/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013)

## Built on by (most cited first, 9 of 9)

- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula](https://mlsanity.com/paper/2311.01642/) (2023)
- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [Robust Adversarial Reinforcement Learning with Risk Sensitivity and Critic Consistency Regularization](https://mlsanity.com/paper/2609.27667/) (2026)

## 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.