# Provable Policy Gradient Methods for Average-Reward Markov Potential Games

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 9 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

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

- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [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)
- [Reinforcement Learning with Sparse Rewards using Guidance from Offline Demonstration](https://mlsanity.com/paper/2202.04628/) (2022)
- [Multi-agent Reinforcement Learning for Networked System Control](https://mlsanity.com/paper/2004.01339/) (2020)
- [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)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games](https://mlsanity.com/paper/2202.00872/) (2022)
- [Average-Reward Reinforcement Learning with Trust Region Methods](https://mlsanity.com/paper/2106.03442/) (2021)
- [Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games](https://mlsanity.com/paper/2310.09727/) (2023)
- [Reward Biased Maximum Likelihood Estimation for Reinforcement Learning](https://mlsanity.com/paper/2011.07738/) (2020)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)

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

- [Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Games](https://mlsanity.com/paper/2404.00045/) (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)
- [Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Games](https://mlsanity.com/paper/2503.22779/) (2025)
- [Independent policy gradient-based reinforcement learning for economic and reliable energy management of multi-microgrid systems](https://mlsanity.com/paper/2511.20977/) (2025)

## Abstract (arXiv)

We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an ε-Nash equilibrium with time complexity O(frac1ε2), given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with tildeO(frac1mins,aπ(a|s)δ) sample complexity to achieve δ approximation error w.r.t~the ℓ2 norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of tildeO(1/ε5). Simulation studies are presented.