# MDPGT: Momentum-based Decentralized Policy Gradient Tracking

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 52 references that are in the map.
- First posted on arXiv 6 Dec 2021.

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

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications](https://mlsanity.com/paper/1812.11794/) (2018)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Multi-agent Reinforcement Learning for Networked System Control](https://mlsanity.com/paper/2004.01339/) (2020)
- [Faster Non-Convex Federated Learning via Global and Local Momentum](https://mlsanity.com/paper/2012.04061/) (2020)
- [Reducing Overestimation Bias in Multi-Agent Domains Using Double Centralized Critics](https://mlsanity.com/paper/1910.01465/) (2019)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Multi-Agent Actor-Critic with Hierarchical Graph Attention Network](https://mlsanity.com/paper/1909.12557/) (2019)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization](https://mlsanity.com/paper/2005.07041/) (2020)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning](https://mlsanity.com/paper/2006.04338/) (2020)
- [Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances](https://mlsanity.com/paper/1912.03821/) (2019)
- [Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environments](https://mlsanity.com/paper/2005.05441/) (2020)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1901.09326/) (2019)
- [A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1907.03053/) (2019)
- [F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2004.11145/) (2020)

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

- [Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergence](https://mlsanity.com/paper/2401.03489/) (2024)
- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)
- [DePAint: A Decentralized Safe Multi-Agent Reinforcement Learning Algorithm considering Peak and Average Constraints](https://mlsanity.com/paper/2310.14348/) (2023)
- [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)
- [Distributed Direct Preference Optimization](https://mlsanity.com/paper/2605.20696/) (2026)

## Abstract (arXiv)

We propose a novel policy gradient method for multi-agent reinforcement learning, which leverages two different variance-reduction techniques and does not require large batches over iterations. Specifically, we propose a momentum-based decentralized policy gradient tracking (MDPGT) where a new momentum-based variance reduction technique is used to approximate the local policy gradient surrogate with importance sampling, and an intermediate parameter is adopted to track two consecutive policy gradient surrogates. Moreover, MDPGT provably achieves the best available sample complexity of O(N-1ε-3) for converging to an ε-stationary point of the global average of N local performance functions (possibly nonconcave). This outperforms the state-of-the-art sample complexity in decentralized model-free reinforcement learning, and when initialized with a single trajectory, the sample complexity matches those obtained by the existing decentralized policy gradient methods. We further validate the theoretical claim for the Gaussian policy function. When the required error tolerance ε is small enough, MDPGT leads to a linear speed up, which has been previously established in decentralized stochastic optimization, but not for reinforcement learning. Lastly, we provide empirical results on a multi-agent reinforcement learning benchmark environment to support our theoretical findings.