mlsanityData to 7 Oct 2026

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

arXiv 2102.08903 ↗First posted 17 Feb 2021cs.LG cs.GT math.OCcited by 18

Not on the map. Why?

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.

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

Builds on

29 of 61 references.

References · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2017Learning with Opponent-Learning Awarenesscited by 218
  5. 2017Training GANs with Optimismcited by 217
  6. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  7. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  8. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  9. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  10. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  11. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  12. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
17 more
  1. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  2. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  3. 2018Multi-Agent Generative Adversarial Imitation Learningcited by 99
  4. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  5. 2018Solving Imperfect-Information Games via Discounted Regret Minimizationcited by 68
  6. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  7. 2019A Geometric Perspective on Optimal Representations for Reinforcement Learningcited by 54
  8. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  9. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  10. 2019ELF OpenGo: An Analysis and Open Reimplementation of AlphaZerocited by 37
  11. 2017Traffic Light Control Using Deep Policy-Gradient and Value-Function Based Reinforcement Learningcited by 33
  12. 2019Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descentcited by 31
  13. 2019Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Gamescited by 14
  14. 2016Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Gamescited by 13
  15. 2018Near-Optimal Communication Lower Bounds for Approximate Nash Equilibriacited by 6
  16. 2013On the Communication Complexity of Approximate Nash Equilibriacited by 5
  17. 2014Computing Approximate Nash Equilibria in Polymatrix Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 8; 2024: 2; 2025: 0; 2026: 3.

18 papers.

Sort:

  1. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  2. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  3. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  4. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  5. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  6. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  7. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  8. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  9. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  10. 2022Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Gamescited by 1
  11. 2023Differentiable Arbitrating in Zero-sum Markov Gamescited by 1
  12. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
6 more
  1. 2024A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimizationcited by 1
  2. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  3. 2023A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Gamescited by 0
  4. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  5. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  6. 2026Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chainscited by 0