# Decentralized Natural Policy Gradient with Variance Reduction for Collaborative Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2022.

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

- [Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning](https://mlsanity.com/paper/2311.00201/) (2023)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)
- [Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradients](https://mlsanity.com/paper/2605.10909/) (2026)
- [Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2405.02456/) (2024)
- [CoCoL: A Communication Efficient Decentralized Collaborative Method for Multi-Robot Systems](https://mlsanity.com/paper/2508.20898/) (2025)
- [A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing](https://mlsanity.com/paper/2609.26783/) (2026)
- [DuoMind: Enabling Distributed Multi-Robot Coordination with Semantic Communication](https://mlsanity.com/paper/2610.02161/) (2026)

## Abstract (arXiv)

This paper studies a policy optimization problem arising from collaborative multi-agent reinforcement learning in a decentralized setting where agents communicate with their neighbors over an undirected graph to maximize the sum of their cumulative rewards. A novel decentralized natural policy gradient method, dubbed Momentum-based Decentralized Natural Policy Gradient (MDNPG), is proposed, which incorporates natural gradient, momentum-based variance reduction, and gradient tracking into the decentralized stochastic gradient ascent framework. The O(n-1ε-3) sample complexity for MDNPG to converge to an ε-stationary point has been established under standard assumptions, where n is the number of agents. It indicates that MDNPG can achieve the optimal convergence rate for decentralized policy gradient methods and possesses a linear speedup in contrast to centralized optimization methods. Moreover, superior empirical performance of MDNPG over other state-of-the-art algorithms has been demonstrated by extensive numerical experiments.