mlsanityData to 7 Oct 2026

The Sample-Communication Complexity Trade-off in Federated Q-Learning

arXiv 2408.16981 ↗First posted 30 Aug 2024cs.LG math.OC stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We consider the problem of federated Q-learning, where M agents aim to collaboratively learn the optimal Q-function of an unknown infinite-horizon Markov decision process with finite state and action spaces. We investigate the trade-off between sample and communication complexities for the widely used class of intermittent communication algorithms. We first establish the converse result, where it is shown that a federated Q-learning algorithm that offers any speedup with respect to the number of agents in the per-agent sample complexity needs to incur a communication cost of at least an order of frac11-γ up to logarithmic factors, where γ is the discount factor. We also propose a new algorithm, called Fed-DVR-Q, which is the first federated Q-learning algorithm to simultaneously achieve order-optimal sample and communication complexities. Thus, together these results provide a complete characterization of the sample-communication complexity trade-off in federated Q-learning.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 42 of its 70 references that are in the map. First posted on arXiv 30 Aug 2024.

Builds on

42 of 70 references.

References · 42

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 373
  6. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  7. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
  8. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  10. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  11. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  12. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
30 more
  1. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  2. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  3. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  4. 2021Federated Multi-Armed Banditscited by 59
  5. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  6. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  7. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  8. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  9. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  10. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  11. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  12. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  13. 2022FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergencecited by 29
  14. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  15. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  16. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  17. 2020A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learningcited by 24
  18. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 23
  19. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  20. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  21. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  22. 2019Gossip-based Actor-Learner Architectures for Deep Reinforcement Learningcited by 16
  23. 2019Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximationcited by 14
  24. 2023Distributed TD(0) with Almost No Communicationcited by 11
  25. 2023Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learningcited by 11
  26. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  27. 2020On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Biascited by 10
  28. 2014Optimality guarantees for distributed statistical estimationcited by 9
  29. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  30. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 2.

8 papers.

  1. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  2. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  3. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environmentscited by 2
  4. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  5. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  6. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  7. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  8. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0