Abstract
This paper addresses the challenges of solving fixed-point equations in decentralized networks under Markovian noise, a common scenario in multi-agent reinforcement learning. We introduce two novel algorithms: Decentralized Local Markovian Stochastic Approximation (DLMSA) and its compressed counterpart (C-DLMSA). By utilizing local updates and an error-compensated communication mechanism, these algorithms achieve a near-optimal convergence rate of $\tilde{O}(1/T)$, matching the performance of centralized systems. Our theoretical analysis proves that the convergence rate is independent of network topology in the long run. Empirical results on a multi-task GridWorld environment demonstrate that C-DLMSA can reduce communication bandwidth by 99% while maintaining performance nearly identical to centralized Q-learning.
Introduction
Stochastic Approximation (SA) is a cornerstone of modern machine learning, particularly in Reinforcement Learning (RL). However, practical applications often face two significant hurdles: Markovian noise, where data samples are temporally dependent, and the need for decentralization in large-scale or peer-to-peer systems. Existing decentralized methods often suffer from sub-optimal convergence rates or high sensitivity to network topology. This work aims to bridge this gap by providing efficient, communication-aware algorithms with strong theoretical guarantees.
Methodology
We propose two primary frameworks to handle decentralized SA. The first, DLMSA, allows agents to perform $K$ local updates on their own data before synchronizing with neighbors. This reduces the frequency of communication required to reach consensus.
The second framework, C-DLMSA, incorporates message compression (e.g., quantization) to further save bandwidth. To prevent the accumulation of compression errors from hindering convergence, we implement an error-compensated mechanism. Our analysis utilizes a generalized Moreau envelope, allowing the convergence proofs to hold for arbitrary norms, such as the $\ell_\infty$-norm used in Q-learning.
Experimental Evaluation
We evaluated our methods using a Multi-task GridWorld simulation. In this setup, multiple agents are placed in separate $10 \times 10$ grids with varying goals and obstacles. The objective is to learn a unified Q-learning policy that generalizes across all environments.
Key Results and Discussion
Our theoretical and empirical findings yield several key insights:
- Near-Optimal Convergence: Both DLMSA and C-DLMSA achieve a convergence rate of $\tilde{O}(1/T)$, a significant improvement over previous $O(1/\sqrt{T})$ methods.
- Compression Efficiency: C-DLMSA achieves performance identical to uncompressed versions while using significantly less bandwidth. In our experiments, using only 1% of the original bandwidth (via
top1%compression) resulted in no loss of accuracy. - Topology Independence: While network connectivity affects initial transients, the dominant convergence rate is independent of the network's spectral gap for sufficiently large $T$.
Conclusion
DLMSA and C-DLMSA provide a robust framework for decentralized stochastic approximation under Markovian noise. Future work will focus on extending these methods to asynchronous communication and time-varying network topologies to better suit highly dynamic real-world environments.
Summary updated