# Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 23 Sep 2021.

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

- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspective](https://mlsanity.com/paper/1404.4391/) (2014)
- [Privacy Amplification by Mixing and Diffusion Mechanisms](https://mlsanity.com/paper/1905.12264/) (2019)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019)
- [Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensus](https://mlsanity.com/paper/1903.09255/) (2019)
- [Exploiting Fast Decaying and Locality in Multi-Agent MDP with Tree Dependence Structure](https://mlsanity.com/paper/1909.06900/) (2019)
- [Policy Iteration for Factored MDPs](https://mlsanity.com/paper/1301.3869/) (2013)
- [On the Dynamics of Deterministic Epidemic Propagation over Networks](https://mlsanity.com/paper/1701.03137/) (2017)
- [Temporal starvation in multi-channel CSMA networks: an analytical framework](https://mlsanity.com/paper/1808.03602/) (2018)
- [Improving Gibbs Sampler Scan Quality with DoGS](https://mlsanity.com/paper/1707.05807/) (2017)

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

- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Scalable Multi-Agent Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2302.07938/) (2023)
- [Distributed Policy Gradient for Linear Quadratic Networked Control with Limited Communication Range](https://mlsanity.com/paper/2403.03055/) (2024)

## Abstract (arXiv)

Cooperative multi-agent reinforcement learning is a decentralized paradigm in sequential decision making where agents distributed over a network iteratively collaborate with neighbors to maximize global (network-wide) notions of rewards. Exact computations typically involve a complexity that scales exponentially with the number of agents. To address this curse of dimensionality, we design a scalable algorithm based on the Natural Policy Gradient framework that uses local information and only requires agents to communicate with neighbors within a certain range. Under standard assumptions on the spatial decay of correlations for the transition dynamics of the underlying Markov process and the localized learning policy, we show that our algorithm converges to the globally optimal policy with a dimension-free statistical and computational complexity, incurring a localization error that does not depend on the number of agents and converges to zero exponentially fast as a function of the range of communication.