Provably Efficient Q-Learning with Low Switching Cost
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 $\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.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Benchmark for Low-Switching-Cost Reinforcement Learning
A ubiquitous requirement in many practical reinforcement learning (RL) applications, including medical treatment, recommendation system, education and robotics, is that the deployed policy that actually interacts with th…
Atari Gamesreinforcement-learningReinforcement LearningReinforcement Learning (RL)A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
Many real-world applications, such as those in medical domains, recommendation systems, etc, can be formulated as large state space reinforcement learning problems with only a small budget of the number of policy changes…
4kRecommendation SystemsNon-stationary Online Learning with Memory and Non-stochastic Control
We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions and thus captures temporal effects of learning problems. In this paper, we introduce dynamic p…
Near-Optimal Adversarial Reinforcement Learning with Switching Costs
Switching costs, which capture the costs for changing policies, are regarded as a critical metric in reinforcement learning (RL), in addition to the standard metric of losses (or rewards). However, existing studies on sw…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)SCaLE: Switching Cost aware Learning and Exploration
This work addresses the fundamental problem of unbounded metric movement costs in bandit online convex optimization, by considering high-dimensional dynamic quadratic hitting costs and $\ell_2$-norm switching costs in a …