mlsanityData to 14 Oct 2026

Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning

arXiv 2506.04626 ↗First posted 5 Jun 2025stat.ML cs.LGcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Motivated by real-world settings where data collection and policy deployment -- whether for a single agent or across multiple agents -- are costly, we study the problem of on-policy single-agent reinforcement learning (RL) and federated RL (FRL) with a focus on minimizing burn-in costs (the sample sizes needed to reach near-optimal regret) and policy switching or communication costs. In parallel finite-horizon episodic Markov Decision Processes (MDPs) with S states and A actions, existing methods either require superlinear burn-in costs in S and A or fail to achieve logarithmic switching or communication costs. We propose two novel model-free RL algorithms -- Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost -- that are the first in the literature to simultaneously achieve: (i) the best near-optimal regret among all known model-free RL or FRL algorithms, (ii) low burn-in cost that scales linearly with S and A, and (iii) logarithmic policy switching cost for single-agent RL or communication cost for FRL. Additionally, we establish gap-dependent theoretical guarantees for both regret and switching/communication costs, improving or matching the best-known gap-dependent bounds.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 80 of its 110 references that are in the map. First posted on arXiv 5 Jun 2025.

Builds on

80 of 110 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition10 Oct

Other references · 79

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  3. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 883
  4. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  5. 2017Federated Multi-Task Learningcited by 672
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  7. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  8. 2018Is Q-learning Provably Efficient?cited by 487
  9. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 379
  10. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  11. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  12. 2020Federated Learning of a Mixture of Global and Local Modelscited by 210
38 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2019Batched Multi-armed Bandits Problemcited by 98
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  9. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2020Variance-Reduced Methods for Machine Learningcited by 79
  12. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  13. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  14. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  15. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 63
  16. 2020Q-learning with Logarithmic Regretcited by 60
  17. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  18. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  19. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  20. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 54
  21. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  22. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  23. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  24. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  25. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  26. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  27. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  28. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  29. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  30. 2018Exploration in Structured Reinforcement Learningcited by 34
  31. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  32. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  33. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  34. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
  35. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  36. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  37. 2020Federated Recommendation System via Differential Privacycited by 26
  38. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 26

50 most cited of 79 All 79 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

2 papers.

  1. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  2. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  2. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
  5. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  6. 2023Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
  7. 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
  8. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learning