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

arXiv: https://arxiv.org/abs/2602.20297 · HTML: https://mlsanity.com/paper/2602.20297/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 23 Feb 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Built on by (most cited first, 2 of 2)

- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning](https://mlsanity.com/paper/2610.04752/) (2026)

## Abstract (arXiv)

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.