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^{3}SA\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.

Published at NeurIPS 2019

References in corpus (5)

• Device Placement Optimization with Reinforcement Learning
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• Batched Multi-armed Bandits Problem
• Convergent Policy Optimization for Safe Reinforcement Learning
• Policy Certificates: Towards Accountable Reinforcement Learning

Cited by in corpus (11)

• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Understanding Domain Randomization for Sim-to-real Transfer
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning
• Collaborative Top Distribution Identifications with Limited Interaction
• Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Safe Reinforcement Learning with Linear Function Approximation