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. Moreover, MDPGT provably achieves the best available sample complexity of $\mathcal{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
Multi-Agent Reinforcement Learning (MARL) is a critical framework for solving complex tasks involving multiple autonomous entities, from robotic swarms to distributed power grids. However, MARL is inherently difficult due to the "non-oblivious" nature of the environment: as one agent updates its policy, the environment effectively changes for all other agents. This non-stationarity, coupled with the high variance typical of policy gradients, makes convergence guarantees elusive.
In decentralized settings, the challenge is compounded. Agents possess local reward functions and can only communicate with immediate neighbors within a network topology. Bridging the gap between centralized sample complexity—often reaching $\mathcal{O}(\epsilon^{-3})$—and the slower $\mathcal{O}(\epsilon^{-4})$ typically seen in decentralized model-free RL is a primary goal of this work.
The MDPGT Framework
The proposed algorithm, Momentum-based Decentralized Policy Gradient Tracking (MDPGT), integrates two powerful mechanisms to stabilize learning and improve efficiency:
- HIS-SARAH (Hybrid Importance Sampling SARAH): This is a momentum-based variance reduction technique. By using importance sampling to "correct" gradients from previous iterations, HIS-SARAH provides a stable gradient estimate without the need for the prohibitively large batches often required by standard variance reduction methods.
- Gradient Tracking (GT): In a decentralized network, local gradients are inherently biased because agents lack a global view of the system's rewards. GT is a consensus-based mechanism that allows agents to track the average gradient of the entire network through local communication, effectively neutralizing local bias.
By nesting these engines, MDPGT addresses both the environmental variance and the communication constraints of decentralized networks. Notably, the algorithm operates with $\mathcal{O}(1)$ mini-batches, making it computationally practical for real-world applications.
Theoretical Breakthroughs: Complexity and Linear Speedup
A significant contribution of this research is the theoretical proof that decentralized MARL can match the best available sample complexity of centralized RL. As shown in the comparison below, MDPGT (specifically the version with momentum-based initialization, MDPGT-MI) achieves a sample complexity of $\mathcal{O}(\epsilon^{-3})$.
Beyond complexity, the paper establishes a linear speedup property. This means that as the number of agents ($N$) increases, the sampling complexity decreases proportionally ($N^{-1}$). In essence, a larger network of agents learns more efficiently than a single agent, a property previously established in stochastic optimization but not in the context of reinforcement learning.
Empirical Evaluation
The researchers validated MDPGT using benchmark environments including Cooperative Navigation (Gridworld) and Lineworld. In these tasks, agents must coordinate to reach goals while avoiding collisions, receiving rewards based on their collective proximity to targets.
The results demonstrate that MDPGT significantly outperforms standard Decentralized Policy Gradient (DPG) and a version of the algorithm without gradient tracking (MDPG). The tracking mechanism proved vital as the number of agents scaled, particularly in environments where local rewards were highly diverse. Furthermore, the algorithm showed remarkable robustness across various network topologies, including ring, bipartite, and fully-connected graphs.
Conclusion
MDPGT represents a significant step forward in decentralized MARL, providing the first theoretical and empirical evidence that decentralized systems can achieve $\mathcal{O}(\epsilon^{-3})$ sample complexity with linear speedup. Future work will focus on extending these variance reduction techniques to more complex, high-dimensional environments and exploring the robustness of these consensus-based methods against adversarial actors in the network.
Summary updated