mlsanityData to 14 Oct 2026

Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games

arXiv 2205.13746 ↗First posted 27 May 2022math.OC cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due to its formulation as a minimax optimization program, a natural approach to solve the problem is to perform gradient descent/ascent with respect to each player in an alternating fashion. However, due to the non-convexity/non-concavity of the underlying objective function, theoretical understandings of this method are limited. In our paper, we consider solving an entropy-regularized variant of the Markov game. The regularization introduces structure into the optimization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We explicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement the analysis with numerical simulations that illustrate the accelerated convergence of the algorithm.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 31 of its 52 references that are in the map. First posted on arXiv 27 May 2022.

Builds on

31 of 52 references.

References · 31

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  2. 2017Robust Adversarial Reinforcement Learningcited by 451
  3. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  6. 2017Training GANs with Optimismcited by 217
  7. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 186
  8. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 182
  9. 2017A unified view of entropy-regularized Markov decision processescited by 182
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  12. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
19 more
  1. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  2. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  3. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  4. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  5. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  8. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  9. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
  10. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  11. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
  12. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  13. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
  14. 2020Fictitious play in zero-sum stochastic gamescited by 26
  15. 2020A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learningcited by 25
  16. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  17. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  18. 2019On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimizationcited by 15
  19. 2017On Completely Mixed Stochastic Gamescited by 1

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 10; 2024: 1; 2025: 4.

18 papers.

Sort:

By area:

  1. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
  2. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 22
  3. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  4. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  5. 2023Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problemscited by 11
  6. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  7. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  8. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  9. 2023Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RLcited by 7
  10. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  11. 2023Abstracting Imperfect Information Away from Two-Player Zero-Sum Gamescited by 6
  12. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
6 more
  1. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  2. 2023Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergencecited by 4
  3. 2023Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theoremscited by 3
  4. 2023Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Controlcited by 2
  5. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  6. 2025Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysiscited by 1