Finite-Time Convergence Rates of Decentralized Local Markovian Stochastic Approximation

Pengfei Wang, Nenggan Zheng, Suyang Hou, Yueyang Ding, Xiaobo Sun

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.

Illustration of the decentralized communication scheme with local updates.

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.

GridWorld environment and performance comparison of centralized vs. decentralized Q-learning.

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

BibTeX
@inproceedings{wang2024finite,
  author = {Pengfei Wang and Nenggan Zheng and Suyang Hou and Yueyang Ding and Xiaobo Sun},
  title = {{Finite-Time Convergence Rates of Decentralized Local Markovian Stochastic Approximation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure