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 tildeO(d√H3K), 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++ (He et al., 2023), with an expected regret bound tildeO(d2H3/Deltamin+d6H5), 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(d2H3/Deltamin) 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 Deltamin is tight up to logarithmic factors. Beyond this algorithmic class, we establish a general gap-dependent lower bound Omega(dH3log K/Deltamin) 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.