mlsanityData to 14 Oct 2026

Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization

arXiv 2105.15186 ↗First posted 31 May 2021math.OC cs.GT cs.ITcited by 63

Not on the map. Why?

Abstract (arXiv)

This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE) -- which are solutions to zero-sum two-player matrix games with entropy regularization -- at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent's actions directly. In addition, by controlling the knob of entropy regularization, the proposed algorithms can locate an approximate Nash equilibrium of the unregularized matrix game at a sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead to efficient policy extragradient algorithms for solving (entropy-regularized) zero-sum Markov games at similar rates. All of our convergence rates are nearly dimension-free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.

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

Builds on

31 of 59 references.

References · 31

  1. 2019A Theory of Regularized Markov Decision Processescited by 286
  2. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  3. 2017Training GANs with Optimismcited by 217
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  5. 2017A unified view of entropy-regularized Markov decision processescited by 182
  6. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  7. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  8. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  9. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  10. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  11. 2017Cycles in adversarial regularized learningcited by 124
  12. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
19 more
  1. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  3. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  4. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  5. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  6. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  7. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  9. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  10. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  11. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  12. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  13. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  14. 2017Stabilizing Adversarial Nets With Prediction Methodscited by 14
  15. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
  16. 2018Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Gamescited by 11
  17. 2019Entropy-Regularized Stochastic Gamescited by 5
  18. 2020Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Modelcited by 4
  19. 2020Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 18; 2023: 15; 2024: 9; 2025: 12; 2026: 3.

63 papers.

Sort:

By area:

  1. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 66
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  3. 2021Modeling Strong and Human-Like Gameplay with KL-Regularized Searchcited by 50
  4. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  5. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  6. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
  7. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  8. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  9. 2021Independent Learning in Stochastic Gamescited by 22
  10. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 22
  11. 2025Softmax is 1/2-Lipschitz: A tight bound across all ℓp normscited by 22
  12. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
38 more
  1. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  2. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  3. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
  4. 2025Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedbackcited by 16
  5. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  6. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  7. 2022An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Gamescited by 14
  8. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  9. 2023Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problemscited by 11
  10. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  11. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  12. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  13. 2023Robust Adversarial Reinforcement Learning via Bounded Rationality Curriculacited by 10
  14. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  15. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  16. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  17. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
  18. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  19. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  20. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 7
  21. 2021Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Gamescited by 6
  22. 2023Abstracting Imperfect Information Away from Two-Player Zero-Sum Gamescited by 6
  23. 2023Markov α-Potential Gamescited by 6
  24. 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
  25. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  26. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  27. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  28. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  29. 2025RSPO: Regularized Self-Play Alignment of Large Language Modelscited by 5
  30. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  31. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  32. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 4
  33. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  34. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 3
  35. 2025Aligned Multi Objective Optimizationcited by 3
  36. 2023Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methodscited by 2
  37. 2023Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Controlcited by 2
  38. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2

50 most cited of 63 All 63 (JSON)