# Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 15 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [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)
- [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)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [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)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Learning in Nonzero-Sum Stochastic Games with Potentials](https://mlsanity.com/paper/2103.09284/) (2021)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (2021)
- [Building a Foundation for Data-Driven, Interpretable, and Robust Policy Design using the AI Economist](https://mlsanity.com/paper/2108.02904/) (2021)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games](https://mlsanity.com/paper/2202.00872/) (2022)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Learning Parametric Closed-Loop Policies for Markov Potential Games](https://mlsanity.com/paper/1802.00899/) (2018)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)

## Built on by (most cited first, 13 of 13)

- [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)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [Natural Gradient VI: Guarantees for Non-Conjugate Models](https://mlsanity.com/paper/2510.19163/) (2025)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization](https://mlsanity.com/paper/2405.02769/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2605.07101/) (2026)
- [Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games](https://mlsanity.com/paper/2410.20075/) (2024)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Cooperative Multi-agent RL with Communication Constraints](https://mlsanity.com/paper/2601.12518/) (2026)
- [Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games](https://mlsanity.com/paper/2604.00433/) (2026)
- [Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2610.01181/) (2026)

## Abstract (arXiv)

This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the textitsuboptimality gap, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an ε-Nash Equilibrium (NE) within O(1/ε) iterations. This improves upon the previous best result of O(1/ε2) iterations and is of the same order, O(1/ε), that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.