mlsanityData to 7 Oct 2026

Gradient play in stochastic games: stationary points, convergence, and sample complexity

arXiv 2106.00198 ↗First posted 1 Jun 2021cs.LG cs.GT cs.MAcited by 32

Not on the map. Why?

Abstract (arXiv)

We study the performance of the gradient play algorithm for stochastic games (SGs), where each agent tries to maximize its own total discounted reward by making decisions independently based on current state information which is shared between agents. Policies are directly parameterized by the probability of choosing a certain action at a given state. We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting, and give a local convergence rate around strict NEs. Further, for a subclass of SGs called Markov potential games (which includes the setting with identical rewards as an important special case), we design a sample-based reinforcement learning algorithm and give a non-asymptotic global convergence rate analysis for both exact gradient play and our sample-based learning algorithm. Our result shows that the number of iterations to reach an ε-NE scales linearly, instead of exponentially, with the number of agents. Local geometry and local stability are also considered, where we prove that strict NEs are local maxima of the total potential function and fully-mixed NEs are saddle points.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 23 of its 78 references that are in the map. First posted on arXiv 1 Jun 2021.

Builds on

23 of 78 references.

References · 23

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  3. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2017Learning with Opponent-Learning Awarenesscited by 218
  7. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  8. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  9. 2019A Review of Cooperative Multi-Agent Deep Reinforcement Learningcited by 147
  10. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  11. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  12. 2013Projection onto the probability simplex: An efficient algorithm with a simple proof, and an applicationcited by 65
11 more
  1. 2018On Gradient-Based Learning in Continuous Gamescited by 46
  2. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  3. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  4. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  5. 2019Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approachcited by 33
  6. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  7. 2019Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Informationcited by 12
  8. 2015Dynamic Potential Games in Communications: Fundamentals and Applicationscited by 7
  9. 2014A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamicscited by 5
  10. 2020Stochastic Potential Gamescited by 4
  11. 2020Dynamic network congestion gamescited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

32 papers.

Sort:

By area:

  1. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  2. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  3. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  4. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  5. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  6. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  7. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  8. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  9. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  10. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  11. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  12. 2023AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimationcited by 10
20 more
  1. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  2. 2023Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RLcited by 7
  3. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  4. 2022Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Gamescited by 6
  5. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  6. 2023Markov α-Potential Gamescited by 6
  7. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Surveycited by 5
  8. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  9. 2022Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Gamescited by 1
  10. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  11. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularizationcited by 1
  12. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  13. 2026Markov Potential Game and Multi-Agent Reinforcement Learning for Autonomous Drivingcited by 1
  14. 2025Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Gamescited by 0
  15. 2025Online Multi-Agent Control with Adversarial Disturbancescited by 0
  16. 2025Independent policy gradient-based reinforcement learning for economic and reliable energy management of multi-microgrid systemscited by 0
  17. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  18. 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Gamescited by 0
  19. 2026Meta-Multi-Agent Reinforcement Learning for Fast Adaptation of Interactive Policies with Applications to Autonomous Drivingcited by 0
  20. 2026Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chainscited by 0