# Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 61 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [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)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [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)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [A Geometric Perspective on Optimal Representations for Reinforcement Learning](https://mlsanity.com/paper/1901.11530/) (2019)
- [Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games](https://mlsanity.com/paper/1906.00729/) (2019)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero](https://mlsanity.com/paper/1902.04522/) (2019)
- [Traffic Light Control Using Deep Policy-Gradient and Value-Function Based Reinforcement Learning](https://mlsanity.com/paper/1704.08883/) (2017)
- [Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent](https://mlsanity.com/paper/1903.05614/) (2019)
- [Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games](https://mlsanity.com/paper/1911.04672/) (2019)
- [Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Games](https://mlsanity.com/paper/1604.07095/) (2016)
- [Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria](https://mlsanity.com/paper/1805.06387/) (2018)
- [On the Communication Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1302.3793/) (2013)
- [Computing Approximate Nash Equilibria in Polymatrix Games](https://mlsanity.com/paper/1409.3741/) (2014)

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

- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.04819/) (2023)
- [One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning](https://mlsanity.com/paper/2205.15891/) (2022)
- [Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games](https://mlsanity.com/paper/2210.07651/) (2022)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions](https://mlsanity.com/paper/2312.08008/) (2023)
- [Differentiable Arbitrating in Zero-sum Markov Games](https://mlsanity.com/paper/2302.10058/) (2023)
- [Sample-Efficient Multi-Agent RL: An Optimization Perspective](https://mlsanity.com/paper/2310.06243/) (2023)
- [A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization](https://mlsanity.com/paper/2404.12312/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games](https://mlsanity.com/paper/2403.07890/) (2024)
- [Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games](https://mlsanity.com/paper/2602.00606/) (2026)
- [Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2610.01181/) (2026)

## Abstract (arXiv)

Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarantees for such algorithms. We present a new policy optimization algorithm with function approximation and prove that under standard regularity conditions on the Markov game and the function approximation class, our algorithm finds a near-optimal policy within a polynomial number of samples and iterations. To our knowledge, this is the first provably efficient policy optimization algorithm with function approximation that solves two-player zero-sum Markov games.