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

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

## 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 (most cited first, 30 of 40)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [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)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)

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

- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey](https://mlsanity.com/paper/2401.04934/) (2024)
- [Model-free policy gradient for discrete-time mean-field control](https://mlsanity.com/paper/2601.11217/) (2026)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Learning to Steer Markovian Agents under Model Uncertainty](https://mlsanity.com/paper/2407.10207/) (2024)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs](https://mlsanity.com/paper/2405.09811/) (2024)
- [Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games](https://mlsanity.com/paper/2410.20075/) (2024)
- [The Bounds of Algorithmic Collusion; Q-learning, Gradient Learning, and the Folk Theorem](https://mlsanity.com/paper/2411.12725/) (2024)
- [The Fair Game: Auditing & Debiasing AI Algorithms Over Time](https://mlsanity.com/paper/2508.06443/) (2025)
- [Adaptive Learning for Moving Target defence: Enhancing Cybersecurity Strategies](https://mlsanity.com/paper/2508.17945/) (2025)
- [Robust equilibria in continuous games: From strategic to dynamic robustness](https://mlsanity.com/paper/2512.08138/) (2025)
- [Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games](https://mlsanity.com/paper/2604.04394/) (2026)
- [Equilibrium Selection in Multi-Agent Policy Gradients via Opponent-Aware Basin Entry](https://mlsanity.com/paper/2605.18078/) (2026)

## 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.