mlsanityData to 14 Oct 2026

On the convergence of policy gradient methods to Nash equilibria in general stochastic games

arXiv 2210.08857 ↗First posted 17 Oct 2022cs.GT cs.LG math.OCcited by 16

Not on the map. Why?

Abstract (arXiv)

Learning in stochastic games is a notoriously difficult problem because, in addition to each other's strategic decisions, the players must also contend with the fact that the game itself evolves over time, possibly in a very complicated manner. Because of this, the convergence properties of popular learning algorithms - like policy gradient and its variants - are poorly understood, except in specific classes of games (such as potential or two-player, zero-sum games). In view of this, we examine the long-run behavior of policy gradient methods with respect to Nash equilibrium policies that are second-order stationary (SOS) in a sense similar to the type of sufficiency conditions used in optimization. Our first result is that SOS policies are locally attracting with high probability, and we show that policy gradient trajectories with gradient estimates provided by the REINFORCE algorithm achieve an O(1/√n) distance-squared convergence rate if the method's step-size is chosen appropriately. Subsequently, specializing to the class of deterministic Nash policies, we show that this rate can be improved dramatically and, in fact, policy gradient methods converge within a finite number of iterations in that case.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 40 of its 106 references that are in the map. First posted on arXiv 17 Oct 2022.

Builds on

40 of 106 references.

References · 40

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  7. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 225
  8. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  9. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  12. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
28 more
  1. 2017Cycles in adversarial regularized learningcited by 124
  2. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  3. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  4. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 114
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  8. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  9. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  10. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  11. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  12. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  13. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  14. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  15. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  16. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  17. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 50
  18. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  19. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  20. 2020Fictitious play in zero-sum stochastic gamescited by 26
  21. 2020Reinforcement Learning based Control of Imitative Policies for Near-Accident Drivingcited by 23
  22. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 23
  23. 2014On the Characterization of Local Nash Equilibria in Continuous Gamescited by 22
  24. 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 19
  25. 2019Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Gamescited by 17
  26. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  27. 2022The Complexity of Infinite-Horizon General-Sum Stochastic Gamescited by 11
  28. 2019A Deep Reinforcement Learning Driving Policy for Autonomous Road Vehiclescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 3; 2026: 5.

16 papers.

Sort:

By area:

  1. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  2. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Surveycited by 5
  3. 2026Model-free policy gradient for discrete-time mean-field controlcited by 4
  4. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  5. 2024Learning to Steer Markovian Agents under Model Uncertaintycited by 2
  6. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  7. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  8. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 1
  9. 2024A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffscited by 0
  10. 2024Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Gamescited by 0
  11. 2024The Bounds of Algorithmic Collusion; Q-learning, Gradient Learning, and the Folk Theoremcited by 0
  12. 2025The Fair Game: Auditing & Debiasing AI Algorithms Over Timecited by 0
4 more
  1. 2025Adaptive Learning for Moving Target defence: Enhancing Cybersecurity Strategiescited by 0
  2. 2025Robust equilibria in continuous games: From strategic to dynamic robustnesscited by 0
  3. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Gamescited by 0
  4. 2026Equilibrium Selection in Multi-Agent Policy Gradients via Opponent-Aware Basin Entrycited by 0