mlsanityData to 14 Oct 2026

Provably Efficient Q-Learning with Low Switching Cost

arXiv 1905.12849 ↗First posted 30 May 2019cs.LG cs.AI stat.MLcited by 78

Not on the map. Why?

Cited by 20 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

We take initial steps in studying PAC-MDP algorithms with limited adaptivity, that is, algorithms that change its exploration policy as infrequently as possible during regret minimization. This is motivated by the difficulty of running fully adaptive algorithms in real-world applications (such as medical domains), and we propose to quantify adaptivity using the notion of local switching cost. Our main contribution, Q-Learning with UCB2 exploration, is a model-free algorithm for H-step episodic MDP that achieves sublinear regret whose local switching cost in K episodes is O(H3SAlog K), and we provide a lower bound of Omega(HSA) on the local switching cost for any no-regret algorithm. Our algorithm can be naturally adapted to the concurrent setting, which yields nontrivial results that improve upon prior work in certain aspects.

Key facts. Cited by 78 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 12; 2023: 18; 2024: 15; 2025: 9; 2026: 6.

78 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  4. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  5. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 80
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  7. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 62
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  10. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  11. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  12. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
38 more
  1. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  2. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  3. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  4. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  5. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  6. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  7. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  8. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  9. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16
  10. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
  11. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  12. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  13. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  14. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  15. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  16. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  17. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  18. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  19. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  20. 2022Provable Sim-to-real Transfer in Continuous Domain with Partial Observationscited by 9
  21. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  22. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  23. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  24. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  25. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  26. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  27. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  28. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6
  29. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  30. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 6
  31. 2021Dealing with Non-Stationarity in MARL via Trust-Region Decompositioncited by 5
  32. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  33. 2021MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learningcited by 4
  34. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  35. 2023Sample Efficient Reinforcement Learning with Partial Dynamics Knowledgecited by 4
  36. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  37. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  38. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 3

50 most cited of 78 All 78 (JSON)