Variance-Reduced Q-Learning over Static and Time-Varying Networks

2026/07/24 by Sreejeet Maity, Feng Zhu, Aritra Mitra +1
#cs.LG #cs.SY #eess.SY

paper · pdf

Abstract

We investigate a decentralized reinforcement learning problem involving multiple agents that interact with the same Markov Decision Process (MDP). The agents can exchange information over a network to collectively learn the optimal state-action value function. For this setting, we introduce a novel epoch-based distributed Q-learning algorithm called VRDQ, where within each epoch, agents locally estimate the Bellman optimality operator and diffuse information using a consensus-based protocol. For both static and time-varying networks, we establish high-probability finite-time convergence rates for VRDQ that enjoy linear speedups from collaboration. Crucially, we prove that such speedups in sample-complexity require only O(1) communication, substantially improving upon the communication costs in prior work.

Related

• Best Possible Q-Learning
• The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond
• Federated Q-Learning: Linear Regret Speedup with Low Communication Cost
• Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD
• The Sample-Communication Complexity Trade-off in Federated Q-Learning