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

Haochen Zhang; Lingzhou Xue; Zhong Zheng

stat.MLOct 3, 2026

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

Authors: Haochen Zhang, Lingzhou Xue, Zhong Zheng

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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Regret comparison of different algorithms.

Panel of Figure 2 — Figure 2: Local switching cost comparison of different algorithms.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: GridWorld results.

Panel of Figure 4 — Figure 4: Experimental comparison with state-of-the-art baselines.

Notation	Meaning
$\mathcal{S},\mathcal{A}$	State and action spaces, with $\|\mathcal{S}\|=S$ and $\|\mathcal{A}\|=A$ .
$H,K,T$	Horizon length, number of episodes, and total number of steps, respectively, where $T=KH$ .
$P_{h}(\cdot\|s,a)$	Transition distribution at step $h$ from state-action pair $(s,a)$ .
$\mathbb{P}_{s,a,h}f$	Conditional expectation $\mathbb{P}_{s,a,h}f:=\mathbb{E}_{s^{\prime}\sim P_{h}(\cdot\mid s,a)}[f(s^{\prime})]$ .
$\mathbb{V}_{s,a,h}(f)$	Conditional variance $\mathbb{V}_{s,a,h}(f):=\mathbb{P}_{s,a,h}f^{2}-(\mathbb{P}_{s,a,h}f)^{2}.$
$r_{h}(s,a)$	Reward associated with the state-action-step triple $(s,a,h)$ .

Appendix

Table 1: Basic MDP, value-function, and gap notation.

Notation	Meaning
$Q_{h}^{k}(s,a),V_{h}^{k}(s)$	Values of the algorithmic estimates $Q_{h}(s,a)$ and $V_{h}(s)$ at the beginning of episode $k$ .
$\pi_{h}^{k}(s)$	Greedy action induced by $Q_{h}^{k}$ : $\pi_{h}^{k}(s)\in\arg\max_{a\in\mathcal{A}}Q_{h}^{k}(s,a).$
$\mu_{h}(s,a)$	Stage-wise accumulator of the next-step value estimates.
$\sigma_{h}(s,a)$	Stage-wise accumulator of the squared next-step value estimates.
$t_{h}^{k}(s,a)$	Index of the stage associated with triple $(s,a,h)$ at episode $k$ .
$N_{h}^{k}(s,a)$	Total number of visits to $(s,a,h)$ in the first $t_{h}^{k}(s,a)-1$ completed stages for $k\in[K]$ .

Appendix

Table 2: Algorithmic quantities and stage-related notation.

Notation	Meaning
$\beta$	An analysis parameter in $(0,H]$ used to truncate the value-estimation error. It is not an algorithmic tuning parameter.
$\hat{V}_{h}^{k}(s)$	Pseudo value function $\hat{V}_{h}^{k}(s):=\max\!\left\{V_{h}^{\star}(s),\min\!\left\{V_{h}^{\star}(s)+\beta,V_{h}^{k}(s)\right\}\right\}.$
$\hat{\mathbb{E}}_{h,s,a,k}[f]$	Empirical average of a function $f$ over the $n_{h}^{k}(s,a)$ samples in the relevant stage: $\hat{\mathbb{E}}_{h,s,a,k}[f]:=\frac{1}{n_{h}^{k}(s,a)}\sum_{i=1}^{n_{h}^{k}(s,a)}f^{k_{l_{i}(s,a,h,k)}}\!\left(s_{h+1}^{k_{l_{i}(s,a,h,k)}}\right).$
$\hat{\mathbb{V}}_{h,s,a,k}[f]$	Corresponding stage-wise empirical variance: $\hat{\mathbb{V}}_{h,s,a,k}[f]:=\hat{\mathbb{E}}_{h,s,a,k}[f^{2}]-\left(\hat{\mathbb{E}}_{h,s,a,k}[f]\right)^{2}.$
$\hat{\mathbb{E}}[f]$ , $\hat{\mathbb{V}}[f]$	Shorthand for $\hat{\mathbb{E}}_{h,s,a,k}[f]$ and $\hat{\mathbb{V}}_{h,s,a,k}[f]$ when $(h,s,a,k)$ is clear from the context.

Appendix

Table 3: Pseudo value functions and empirical operators used in the variance analysis.

Notation	Meaning
$\{\omega_{h}^{k}\}_{k=1}^{K}$	A nonnegative initial weight sequence assigned to the estimation errors at the starting step $h$ .
$\omega_{h}(k^{\prime},h)$	Initial propagated weight at step $h$ , defined by $\omega_{h}(k^{\prime},h):=\omega_{h}^{k^{\prime}}.$
$\omega_{h}(k^{\prime},h^{\prime}+1)$	Weight assigned to the estimation error at episode $k^{\prime}$ and step $h^{\prime}+1$ after recursively propagating the weights from step $h^{\prime}$ . It captures the contribution of the episode- $k^{\prime}$ , step- $(h^{\prime}+1)$ estimation error when recursively bounding the cumulative weighted estimation error from step $h^{\prime}$ to step $h^{\prime}+1$ .
$\omega_{h}(k^{\prime},h^{\prime},s,a)$	State-action-specific propagated weight: $\omega_{h}(k^{\prime},h^{\prime},s,a):=\omega_{h}(k^{\prime},h^{\prime})\mathbb{I}[(s_{h^{\prime}}^{k^{\prime}},a_{h^{\prime}}^{k^{\prime}})=(s,a)].$ It isolates the contribution associated with state-action pair $(s,a)$ at step $h^{\prime}$ .
$\tilde{\omega}_{h}(k^{\prime},h^{\prime}+1,s,a)$	The state-action-specific propagated weight assigned to the episode- $k^{\prime}$ , step- $(h^{\prime}+1)$ estimation error when bounding the cumulative weighted estimation error associated with $(s,a)$ at step $h^{\prime}$ : $\tilde{\omega}_{h}(k^{\prime},h^{\prime}+1,s,a):=\omega_{h}(k^{\prime},h^{\prime}+1)\mathbb{I}[(s_{h^{\prime}}^{k^{\prime}},a_{h^{\prime}}^{k^{\prime}})=(s,a)].$
$\\|\omega_{h}(\cdot,h^{\prime})\\|_{1}$	The $\ell_{1}$ -norm of the propagated weights at step $h^{\prime}$ : $\\|\omega_{h}(\cdot,h^{\prime})\\|_{1}:=\sum_{k^{\prime}=1}^{K}\omega_{h}(k^{\prime},h^{\prime}).$

Appendix

Table 4: Recursive weights for propagating cumulative weighted estimation errors across steps.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
Feb 23, 2026Haochen Zhang, Zhong Zheng, Lingzhou XueRegret Minimization in RL Reinforcement Learning
Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame
Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
May 27, 2026Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1Regret Minimization in RL Reinforcement Learning
Chung-Ang University · Seoul National University · Columbia University

Mar 25, 2026J/K move · Enter open · S save

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Guy Zamir, Matthew Zurek, Yudong Chen

Department of Computer Sciences, University of Wisconsin–Madison

Regret Minimization in RL Average-Reward RL Minimax Regret

Open paper AskPDF arXiv

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.

Abstract

Reinforcement Learning

Explore similar work

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

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

Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation