Provably Efficient Q-learning With Low Switching Cost

Abstract

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(H^3SAlog K)\), and we provide a lower bound of \(Ω(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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keybai2019provably

Related papers

• Q-learning With UCB Exploration Is Sample Efficient For Infinite-horizon MDP (2019)0.00
• A Nearly Optimal And Low-switching Algorithm For Reinforcement Learning With General Function Approximation (2023)0.00
• Provably Efficient And Agile Randomized Q-learning (2025)0.00
• Regret-optimal Q-learning With Low Cost For Single-agent And Federated Reinforcement Learning (2025)0.00
• A Provably-efficient Model-free Algorithm For Constrained Markov Decision Processes (2021)0.00
• Federated Q-learning: Linear Regret Speedup With Low Communication Cost (2023)0.00
• Provably Efficient Ucb-type Algorithms For Learning Predictive State Representations (2023)0.00
• Federated Q-learning With Reference-advantage Decomposition: Almost Optimal Regret And Logarithmic Communication Cost (2024)0.00