MDPGT: Momentum-Based Decentralized Policy Gradient Tracking

Zhanhong Jiang, Xian Yeow Lee, Sin Yong Tan, Kai Liang Tan, Aditya Balu, Young M. Lee, Chinmay Hegde, Soumik Sarkar

Abstract

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. MDPGT provably achieves the best available sample complexity of $O(N^{-1} \epsilon^{-3})$ for converging to an $\epsilon$-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 $\epsilon$ 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.

Introduction

In cooperative multi-agent reinforcement learning (MARL), a group of agents must collaborate to maximize the average of their individual long-term rewards. This is inherently challenging due to high variance in policy gradients—compounded by the non-stationary nature of multi-agent environments—and the constraints of decentralization, where agents only have access to local rewards and must communicate over a sparse graph. While centralized RL algorithms have reached a sample complexity of $O(\epsilon^{-3})$, decentralized versions have historically lagged at $O(\epsilon^{-4})$. This paper introduces MDPGT, closing this gap and providing a robust framework for decentralized MARL.

The MDPGT Algorithm

Momentum-Based Decentralized Policy Gradient Tracking (MDPGT) integrates two primary technical pillars to achieve its performance:

  • HIS-SARAH (Hybrid Importance Sampling SARAH): This momentum-based variance reduction technique adapts the SARAH algorithm for RL. By using Importance Sampling weights to "correct" trajectories from previous policies, it allows the algorithm to estimate the current gradient with significantly lower variance without requiring growing batch sizes.
  • Gradient Tracking (GT): This consensus mechanism ensures that each agent's local update "tracks" the global average gradient of the entire network. This effectively corrects the bias that would otherwise be introduced by the specific communication topology of the agents.
A comparison of MDPGT against existing decentralized policy gradient methods, highlighting its superior sample complexity and support for linear speedup.

Key Insights and Theoretical Results

A major theoretical finding is that MDPGT exhibits a linear speedup with respect to the number of agents ($N$). As more agents are added to the network, the number of samples required per agent to reach a target accuracy decreases proportionally. Furthermore, MDPGT is the first decentralized MARL algorithm to achieve $O(\epsilon^{-3})$ complexity for general non-concave performance functions using a constant batch size of $O(1)$ during main iterations.

Empirical Evaluation

The researchers evaluated MDPGT using a Cooperative Navigation Gridworld environment. Five agents were tasked with navigating to specific goal landmarks while avoiding collisions. The algorithm's performance was compared against standard Decentralized Policy Gradient (DPG) and a version without tracking (MDPG).

Rewards over trajectories for MDPGT compared to MDPG and DPG baselines, demonstrating faster convergence and higher stability.

Empirical results show that MDPGT converges faster and reaches higher average rewards with tighter confidence intervals than its predecessors. Ablation studies on the momentum coefficient ($\beta$) identified that values between 0.4 and 0.5 provide the best balance of stability and speed. Additionally, the algorithm proved robust across various network topologies, including fully-connected, ring, and bipartite graphs, confirming that long-term sample complexity remains independent of the specific communication structure.

Conclusion and Future Work

Momentum-Based Decentralized Policy Gradient Tracking successfully bridges the gap between centralized and decentralized RL sample complexity. While highly effective in gridworld benchmarks, future research will focus on scaling these variance reduction techniques to high-dimensional continuous control tasks and investigating robustness against adversarial or "Byzantine" agents within the network.

Summary updated

Abstract

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. MDPGT provably achieves the best available sample complexity of O(N -1 e -3) for converging to an e-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 e 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.
BibTeX
@inproceedings{jiang2022mdpgt,
  author = {Zhanhong Jiang and Xian Yeow Lee and Sin Yong Tan and Kai Liang Tan and Aditya Balu and Young M. Lee and Chinmay Hegde and Soumik Sarkar},
  title = {{MDPGT: Momentum-Based Decentralized Policy Gradient Tracking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=FHDDViDL6i},
}
Figure