Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation

We study gap-dependent regret for reinforcement learning with linear function approximation. While prior works have established gap-dependent guarantees in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound $\tilde{O}(d\sqrt{H^{3}K})$, where $d$ is the feature dimension, $H$ is the horizon length, and $K$ is the number of episodes. We bridge this gap by establishing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ he2023nearly, with an expected regret bound $\tilde{O}(d^2{H}^3/{\Delta }_{\min }+d^6{H}^5)$, improving the dependence on both $d$ and $H$ in the leading gap-dependent term compared with previous results. To understand the exploration cost induced by optimism, we establish a structural lower bound $\Omega (d^2{H}^3/{\Delta }_{\min })$ for a broad class of algorithms based on persistent ellipsoidal optimism. When specialized to LSVI-UCB++, this result shows that the leading dependence of our upper bound on $d$, $H$, and ${\Delta }_{\min }$ is tight up to logarithmic factors. Beyond this algorithmic class, we establish a general gap-dependent lower bound $\Omega (d{H}^3\log K/{\Delta }_{\min })$ for arbitrary learning algorithms, showing that the logarithmic dependence on $K$ and the cubic dependence on $H$ are intrinsic to gap-dependent expected regret in linear MDPs. Together, our results substantially narrow the gap between upper and lower bounds and provide a sharper characterization of gap-dependent learning and optimism-based exploration with linear function approximation.