mlsanityData to 14 Oct 2026

Independent Natural Policy Gradient Always Converges in Markov Potential Games

arXiv 2110.10614 ↗First posted 20 Oct 2021cs.LG cs.GTcited by 37

Not on the map. Why?

Abstract (arXiv)

Multi-agent reinforcement learning has been successfully applied to fully-cooperative and fully-competitive environments, but little is currently known about mixed cooperative/competitive environments. In this paper, we focus on a particular class of multi-agent mixed cooperative/competitive stochastic games called Markov Potential Games (MPGs), which include cooperative games as a special case. Recent results have shown that independent policy gradient converges in MPGs but it was not known whether Independent Natural Policy Gradient converges in MPGs as well. We prove that Independent Natural Policy Gradient always converges in the last iterate using constant learning rates. The proof deviates from the existing approaches and the main challenge lies in the fact that Markov Potential Games do not have unique optimal values (as single-agent settings exhibit) so different initializations can lead to different limit point values. We complement our theoretical results with experiments that indicate that Natural Policy Gradient outperforms Policy Gradient in routing games and congestion games.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Builds on 22 of its 33 references that are in the map. First posted on arXiv 20 Oct 2021.

Builds on

22 of 33 references.

References · 22

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2017Counterfactual Multi-Agent Policy Gradientscited by 751
  3. 2019Solving Rubik's Cube with a Robot Handcited by 734
  4. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 503
  5. 2017A Brief Survey of Deep Reinforcement Learningcited by 483
  6. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 268
  7. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  8. 2017Learning with Opponent-Learning Awarenesscited by 222
  9. 2021Trust Region Policy Optimisation in Multi-Agent Reinforcement Learningcited by 186
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 158
  12. 2019A Review of Cooperative Multi-Agent Deep Reinforcement Learningcited by 147
10 more
  1. 2018Deep Counterfactual Regret Minimizationcited by 103
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  3. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  4. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  5. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  6. 2021XDO: A Double Oracle Algorithm for Extensive-Form Gamescited by 34
  7. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  8. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 26
  9. 2019Neural Replicator Dynamicscited by 13
  10. 2020Stochastic Potential Gamescited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

37 papers.

Sort:

By area:

  1. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  2. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  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 22
  5. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  6. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 13
  7. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  8. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  9. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  10. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  11. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  12. 2022Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Gamescited by 7
25 more
  1. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 7
  2. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  3. 2023Markov α-Potential Gamescited by 6
  4. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  5. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  6. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  7. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  8. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  9. 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Gamescited by 3
  10. 2025The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomycited by 3
  11. 2022Learning Distributed and Fair Policies for Network Load Balancing as Markov Potential Gamecited by 2
  12. 2023Context-Aware Bayesian Network Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learningcited by 2
  13. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  14. 2026Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An α-Potential Approachcited by 2
  15. 2024Risk-Sensitive Multi-Agent Reinforcement Learning in Network Aggregative Markov Gamescited by 1
  16. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  17. 2026Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learningcited by 1
  18. 2026Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradientscited by 1
  19. 2022Conjugate Natural Selectioncited by 0
  20. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  21. 2024A Scalable Game Theoretic Approach for Coordination of Multiple Dynamic Systemscited by 0
  22. 2024Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Gamescited by 0
  23. 2024The Bounds of Algorithmic Collusion; Q-learning, Gradient Learning, and the Folk Theoremcited by 0
  24. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  25. 2026Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chainscited by 0