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

Haochen Zhang; Zhong Zheng; Lingzhou Xue

stat.MLFeb 23, 2026

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

Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue

Organizations: Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame

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 $\tilde{O}(d\sqrt{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 $\tilde{O}(d^2H^3/Δ_{\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 $Ω(d^2H^3/Δ_{\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 $Δ_{\min}$ is tight up to logarithmic factors. Beyond this algorithmic class, we establish a general gap-dependent lower bound $Ω(dH^3\log K/Δ_{\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.

Figures & tables

Algorithm	$\mathbb{E}[\text{Regret}(T)]$
LSVI-UCB	$\tilde{O}(d^{3}H^{5}/\Delta_{\min})$ ( He et al., 2021 )
UCRL-VTR	$\tilde{O}(d^{2}H^{5}/\Delta_{\min})$ ( He et al., 2021 )
LSVI-UCB	$\tilde{O}(d^{3}H^{5}/\Delta_{\min})$ ( Papini et al., 2021 )
Cert-LSVI-UCB	$\tilde{O}(d^{3}H^{5}/\Delta_{\min})$ ( Zhang et al., 2024a )
LSVI-UCB++	$\tilde{O}(d^{2}H^{3}/\Delta_{\min}+d^{6}H^{5})$ (Ours)

Table 1: Comparison of gap-dependent expected regret bounds for different RL algorithms with linear function approximation. We use

T

to denote the total number of steps,

d

as the feature dimension,

H

as the horizon length, and

\Delta_{\min}

as the minimum gap. The notation

\tilde{O}(\cdot)

hides logarithmic factors.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: Log-normalized regret $\operatorname{Regret}(T)/\log(K+1)$ on random synthetic linear MDPs. Each curve is averaged over ten MDP instances, with shaded 10th–90th percentile intervals.

Panel of Figure 2 — Figure 2: Log-normalized regret $\operatorname{Regret}(T)/\log(K+1)$ on controlled-gap linear MDPs with $(S,A,H,d)=(10,10,10,8)$ . Each curve is averaged over ten MDP instances, with shaded 10th–90th percentile intervals.

Regret Minimization in RL

Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.

See all 56 papers

Oct 3, 2026

Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning

We study model-free online reinforcement learning (RL) for episodic tabular Markov decision processes, focusing on both gap-dependent regret and policy switching cost. While fine-grained gap-dependent analysis has been established for model-free RL algorithms using Hoeffding-type exploration bonuses, such results for model-free algorithms with variance-based exploration bonuses remain unknown, despite their superior worst-case and coarse-grained gap-dependent guarantees. In this paper, we resolve this open problem by establishing the first fine-grained gap-dependent regret upper bound for UCB-Bernstein+, a refined UCB-Bernstein algorithm, in variance-aware model-free online RL. Moreover, by integrating a stage-wise policy update design into our fine-grained framework and using refined variance-based bonuses, we achieve the best-known gap-dependent local switching cost to date. In addition, our analysis yields improved worst-case guarantees for both regret and local switching cost over the original UCB-Bernstein algorithm. Numerical experiments further demonstrate that UCB-Bernstein+ achieves favorable empirical performance in both regret and local switching cost.

Haochen Zhang, Lingzhou Xue, Zhong Zheng

Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame

Reinforcement Learning Model-Free RL Regret Minimization in RL RL Exploration

Ask PDF

Mar 25, 2026

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the

γ

-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form

\tilde{O}( \sqrt{SA\,\text{Var}} + \text{lower-order terms})

, where

S,A

are the state and action space sizes, and

\text{Var}

captures cumulative transition variance. This implies minimax-optimal average-reward and

γ

-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span

\Vert h^\star\Vert_\text{sp}

, our algorithm obtains lower-order terms scaling as

\Vert h^\star\Vert_\text{sp} S^2 A

, which we prove is optimal in both

\Vert h^\star\Vert_\text{sp}

and

A

. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than

\Vert h^\star \Vert_\text{sp}^2 S A

, and we provide a prior-free algorithm whose lower-order terms scale as

\Vert h^\star\Vert_\text{sp}^2 S^3 A

, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on

\Vert h^\star\Vert_\text{sp}

in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.

Guy Zamir, Matthew Zurek, Yudong Chen

Department of Computer Sciences, University of Wisconsin–Madison

Regret Minimization in RL Average-Reward RL Minimax Regret

Ask PDF

Oct 5, 2026

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of

\widetilde O\big(dRS(M+1)+σd\sqrt T\big)

, where

T

is the learning horizon,

d

is the parameter dimension,

M

is the memory length,

R

and

S

bound the memory-map operator norm and reward-parameter norm, respectively, and

σ

is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Jingyuan Liu, Huiwen Jia

Department of Industrial Engineering and Operations Research, University of California, Berkeley

Multi-Armed Bandits Non-Stationary Bandits Generalized Linear Bandits Bandit Learning

Ask PDF

Abstract

Regret Minimization in RL

Explore similar work

Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory