mlsanityData to 7 Oct 2026

Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

arXiv 2202.04129 ↗First posted 8 Feb 2022cs.LG cs.GT cs.MAcited by 54

Not on the map. Why?

Abstract (arXiv)

We examine global non-asymptotic convergence properties of policy gradient methods for multi-agent reinforcement learning (RL) problems in Markov potential games (MPG). To learn a Nash equilibrium of an MPG in which the size of state space and/or the number of players can be very large, we propose new independent policy gradient algorithms that are run by all players in tandem. When there is no uncertainty in the gradient evaluation, we show that our algorithm finds an ε-Nash equilibrium with O(1/ε2) iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish O(1/ε5) sample complexity bound in a potentially infinitely large state space for a sample-based algorithm that utilizes function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoys convergence for both zero-sum Markov games and Markov cooperative games with the players that are oblivious to the types of games being played. Finally, we provide computational experiments to corroborate the merits and the effectiveness of our theoretical developments.

Key facts. Cited by 54 papers in the map (data through 7 Oct 2026). Builds on 53 of its 95 references that are in the map. First posted on arXiv 8 Feb 2022.

Builds on

53 of 95 references.

References · 53

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  3. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  5. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2020FACMAC: Factored Multi-Agent Centralised Policy Gradientscited by 178
  8. 2020Open Problems in Cooperative AIcited by 167
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  10. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  11. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  12. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
38 more
  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  3. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  4. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  5. 2020Off-Policy Multi-Agent Decomposed Policy Gradientscited by 97
  6. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  7. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  9. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  10. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  11. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  12. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  13. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  14. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  15. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  16. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  17. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  18. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  19. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  20. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  21. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  22. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  23. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  24. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  25. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  26. 2021Building a Foundation for Data-Driven, Interpretable, and Robust Policy Design using the AI Economistcited by 22
  27. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  28. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
  29. 2021Independent Learning in Stochastic Gamescited by 20
  30. 2018Decentralised Learning in Systems with Many, Many Strategic Agentscited by 19
  31. 2021Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Gamescited by 19
  32. 2020Chaos, Extremism and Optimism: Volume Analysis of Learning in Gamescited by 16
  33. 2020Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theorycited by 16
  34. 2019Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Gamescited by 15
  35. 2019Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizescited by 14
  36. 2019Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Gamescited by 14
  37. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  38. 2016On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regressioncited by 9

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 13; 2023: 14; 2024: 15; 2025: 3; 2026: 9.

54 papers.

Sort:

By area:

  1. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  3. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  4. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  5. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  6. 2023ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordinationcited by 23
  7. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  8. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
  9. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  10. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  11. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  12. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
38 more
  1. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  2. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  3. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  4. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  5. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  6. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  7. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  8. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  9. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  10. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  11. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  12. 2023Markov α-Potential Gamescited by 6
  13. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  14. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  15. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  16. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  17. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  18. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  19. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  20. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  21. 2025The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomycited by 3
  22. 2023Counterfactual Explanation Policies in RLcited by 2
  23. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  24. 2024Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspectivecited by 2
  25. 2024Learning to Steer Markovian Agents under Model Uncertaintycited by 2
  26. 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Gamescited by 2
  27. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  28. 2022How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Gamescited by 1
  29. 2024Risk-Sensitive Multi-Agent Reinforcement Learning in Network Aggregative Markov Gamescited by 1
  30. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  31. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
  32. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  33. 2026Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An α-Potential Approachcited by 1
  34. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamicscited by 1
  35. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  36. 2024Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Costcited by 0
  37. 2025Online Multi-Agent Control with Adversarial Disturbancescited by 0
  38. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0

50 most cited of 54 All 54 (JSON)