mlsanityData to 7 Oct 2026

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

arXiv 2106.01969 ↗First posted 3 Jun 2021cs.LG cs.GTcited by 89

Not on the map. Why?

Abstract (arXiv)

Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent utilities are perfectly aligned with each other via a common potential function. Can this intuitive framework be transplanted in the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove fast convergence of independent policy gradient to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). Builds on 16 of its 46 references that are in the map. First posted on arXiv 3 Jun 2021.

Builds on

16 of 46 references.

References · 16

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  4. 2020Open Problems in Cooperative AIcited by 167
  5. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  6. 2017Cycles in adversarial regularized learningcited by 122
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  8. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  9. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  10. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  11. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  12. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
4 more
  1. 2021Learning in Matrix Games can be Arbitrarily Complexcited by 11
  2. 2018Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Alwayscited by 7
  3. 2020Stochastic Potential Gamescited by 4
  4. 2014Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Geneticscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 20; 2023: 20; 2024: 16; 2025: 10; 2026: 19.

89 papers.

Sort:

By area:

  1. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  3. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  4. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  5. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  6. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  7. 2022Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learningcited by 32
  8. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  9. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  10. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  11. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  12. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
38 more
  1. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  2. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  3. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  4. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  5. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  6. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  7. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  8. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  9. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  10. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  11. 2022Towards Multi-Agent Reinforcement Learning driven Over-The-Counter Market Simulationscited by 10
  12. 2023AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimationcited by 10
  13. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  14. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  15. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  16. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  17. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  18. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 6
  19. 2022Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Gamescited by 6
  20. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  21. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  22. 2023Markov α-Potential Gamescited by 6
  23. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  24. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  25. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  26. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  27. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  28. 2025Towards Principled Unsupervised Multi-Agent Reinforcement Learningcited by 4
  29. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  30. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  31. 2023Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistencecited by 3
  32. 2023Federated Reinforcement Learning for Resource Allocation in V2X Networkscited by 3
  33. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  34. 2024Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learningcited by 3
  35. 2024Toward Finding Strong Pareto Optimal Policies in Multi-Agent Reinforcement Learningcited by 3
  36. 2024Policy Gradient for Robust Markov Decision Processescited by 3
  37. 2025The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomycited by 3
  38. 2022Learning Distributed and Fair Policies for Network Load Balancing as Markov Potential Gamecited by 2

50 most cited of 89 All 89 (JSON)