mlsanityData to 7 Oct 2026

Gap-Dependent Bounds for Federated Q-learning

arXiv 2502.02859 ↗First posted 5 Feb 2025stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We present the first gap-dependent analysis of regret and communication cost for on-policy federated Q-Learning in tabular episodic finite-horizon Markov decision processes (MDPs). Existing FRL methods focus on worst-case scenarios, leading to √T-type regret bounds and communication cost bounds with a log T term scaling with the number of agents M, states S, and actions A, where T is the average total number of steps per agent. In contrast, our novel framework leverages the benign structures of MDPs, such as a strictly positive suboptimality gap, to achieve a log T-type regret bound and a refined communication cost bound that disentangles exploration and exploitation. Our gap-dependent regret bound reveals a distinct multi-agent speedup pattern, and our gap-dependent communication cost bound removes the dependence on MSA from the log T term. Notably, our gap-dependent communication cost bound also yields a better global switching cost when M=1, removing SA from the log T term.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 74 of its 99 references that are in the map. First posted on arXiv 5 Feb 2025.

Builds on

74 of 99 references.

References · 74

  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. 2017Federated Multi-Task Learningcited by 669
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2020Federated Learning of a Mixture of Global and Local Modelscited by 208
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
38 more
  1. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  2. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  3. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  4. 2019Batched Multi-armed Bandits Problemcited by 97
  5. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  6. 2017Device Placement Optimization with Reinforcement Learningcited by 84
  7. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  8. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  9. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  10. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  11. 2020Q-learning with Logarithmic Regretcited by 59
  12. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  13. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  14. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  15. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  16. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  17. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  18. 2018A Survey on Compiler Autotuning using Machine Learningcited by 40
  19. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  20. 2018Exploration in Structured Reinforcement Learningcited by 34
  21. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  22. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  23. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  24. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  25. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  26. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  27. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  28. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  29. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  30. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  31. 2020Federated Recommendation System via Differential Privacycited by 26
  32. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  33. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  34. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 23
  35. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  36. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  37. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  38. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20

50 most cited of 74 All 74 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  2. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  3. 2025Explainable reinforcement learning from human feedback to improve alignmentcited by 1
  4. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0