Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
This work addresses a key bottleneck in reinforcement learning by providing tighter regret bounds for episodic MDPs, with implications for algorithm design in domains like robotics and gaming.
The paper tackles the problem of over-exploration in tabular MDPs by introducing the Adaptive Multi-step Bootstrap (AMB) algorithm, which achieves a gap-dependent regret bound scaling with the sum of inverse sub-optimality gaps, avoiding an additional Ω(S/Δ_min) regret suffered by UCB algorithms.
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 $Ω\left(\frac{S}{Δ_{min}}\right)$ regret due to over-exploration where $Δ_{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}|}{Δ_{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}|}{Δ_{min}}$ is unavoidable for any consistent algorithm. This lower bound also implies a separation between reinforcement learning and contextual bandits.