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

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

## Key facts

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

## Builds on (most cited first, 30 of 53)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Open Problems in Cooperative AI](https://mlsanity.com/paper/2012.08630/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [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)
- [Off-Policy Multi-Agent Decomposed Policy Gradients](https://mlsanity.com/paper/2007.12322/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (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)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)

## Built on by (most cited first, 30 of 57)

- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games](https://mlsanity.com/paper/2212.14449/) (2022)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordination](https://mlsanity.com/paper/2310.05208/) (2023)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games](https://mlsanity.com/paper/2310.09727/) (2023)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence](https://mlsanity.com/paper/2210.12812/) (2022)
- [Efficiently Computing Nash Equilibria in Adversarial Team Markov Games](https://mlsanity.com/paper/2208.02204/) (2022)
- [Provably Learning Nash Policies in Constrained Markov Potential Games](https://mlsanity.com/paper/2306.07749/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Players](https://mlsanity.com/paper/2408.08075/) (2024)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)
- [Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem](https://mlsanity.com/paper/2410.05673/) (2024)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.04819/) (2023)

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