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

arXiv:2602.20297v2 Announce Type: replace-cross Abstract: 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 ilde{O}(dsqrt{H^3K}), 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 ilde{O}(d^2H^3/Delta_{min}+d^6H^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^2H^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(dH^3log 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.

Source: arXiv cs.LG | 2026-10-06