Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

Abstract

This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-dependent regret bound. The first innovation is to estimate the optimal $Q$-function by combining an optimistic bootstrap with an adaptive multi-step Monte Carlo rollout. The second innovation is to select the action with the largest confidence interval length among admissible actions that are not dominated by any other actions. We show when each state has a unique optimal action, AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. In contrast, Simchowitz and Jamieson (2019) showed all upper-confidence-bound (UCB) algorithms suffer an additional $\Omega \left(\frac{S}{{\Delta }_{min}}\right)$ regret due to over-exploration where ${\Delta }_{min}$ is the minimum sub-optimality gap and $S$ is the number of states. We further show that for general MDPs, AMB suffers an additional $\frac{|Z_{mul}|}{{\Delta }_{min}}$ regret, where $Z_{mul}$ is the set of state-action pairs $(s,a)$'s satisfying $a$ is a non-unique optimal action for $s$. We complement our upper bound with a lower bound showing the dependency on $\frac{|Z_{mul}|}{{\Delta }_{min}}$ is unavoidable for any consistent algorithm. This lower bound also implies a separation between reinforcement learning and contextual bandits.

arXiv commentAccepted for presentation at the Conference on Learning Theory (COLT) 2021

References in corpus (8)

• Playing Atari with Deep Reinforcement Learning
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Exploration in Structured Reinforcement Learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• $Q$-learning with Logarithmic Regret

Cited by in corpus (9)

• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• Can Q-Learning be Improved with Advice?
• Gap-Dependent Bounds for Two-Player Markov Games