Provably Efficient Q-Learning with Low Switching Cost
This addresses the challenge of deploying adaptive RL algorithms in sensitive domains by reducing policy changes, though it is incremental as it builds on existing PAC-MDP frameworks.
The paper tackles the problem of reinforcement learning algorithms requiring too many policy changes during exploration, which is impractical in real-world applications like medical domains, by proposing a Q-learning algorithm with UCB2 exploration that achieves sublinear regret with a local switching cost of O(H^3SA log K) and proves a lower bound of Ω(HSA) for any no-regret algorithm.
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^3SA\log 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.