mlsanityData to 7 Oct 2026

Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost

arXiv 2202.06385 ↗First posted 13 Feb 2022cs.LG cs.AI stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

We study the problem of reinforcement learning (RL) with low (policy) switching cost - a problem well-motivated by real-life RL applications in which deployments of new policies are costly and the number of policy updates must be low. In this paper, we propose a new algorithm based on stage-wise exploration and adaptive policy elimination that achieves a regret of widetildeO(√H4S2AT) while requiring a switching cost of O(HSA loglog T). This is an exponential improvement over the best-known switching cost O(H2SAlog T) among existing methods with widetildeO(poly(H,S,A)√T) regret. In the above, S,A denotes the number of states and actions in an H-horizon episodic Markov Decision Process model with unknown transitions, and T is the number of steps. As a byproduct of our new techniques, we also derive a reward-free exploration algorithm with a switching cost of O(HSA). Furthermore, we prove a pair of information-theoretical lower bounds which say that (1) Any no-regret algorithm must have a switching cost of Omega(HSA); (2) Any widetildeO(√T) regret algorithm must incur a switching cost of Omega(HSAloglog T). Both our algorithms are thus optimal in their switching costs.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 27 of its 45 references that are in the map. First posted on arXiv 13 Feb 2022.

Builds on

27 of 45 references.

References · 27

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2021Reinforcement learning based recommender systems: A surveycited by 187
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  12. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
15 more
  1. 2019Batched Multi-armed Bandits Problemcited by 97
  2. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  3. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  4. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  5. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  6. 2020Adaptive Reward-Free Explorationcited by 77
  7. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  8. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  9. 2019Regret Bounds for Batched Banditscited by 49
  10. 2018Experience-driven Networking: A Deep Reinforcement Learning based Approachcited by 41
  11. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  12. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  13. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  14. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  15. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 10; 2024: 9; 2025: 4; 2026: 3.

32 papers.

Sort:

By area:

  1. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  2. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  3. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  4. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  5. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  6. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  7. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  8. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  9. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  10. 2022Doubly Fair Dynamic Pricingcited by 8
  11. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  12. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
20 more
  1. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  2. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  3. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  4. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  5. 2023Sample Efficient Reinforcement Learning with Partial Dynamics Knowledgecited by 4
  6. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  7. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  8. 2024Batched Nonparametric Contextual Banditscited by 3
  9. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  10. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  11. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  12. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  13. 2024To Switch or Not to Switch? Balanced Policy Switching in Offline Reinforcement Learningcited by 1
  14. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  15. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  16. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Datacited by 0
  17. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0
  18. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  19. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0
  20. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0