Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Guy Zamir; Matthew Zurek; Yudong Chen

cs.LGMar 25, 2026

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Authors: Guy Zamir, Matthew Zurek, Yudong Chen

Organizations: Department of Computer Sciences, University of Wisconsin–Madison

Abstract

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.

Figures & tables

Algorithm	$\widetilde{O}(\cdot)$ Regret	Priorless?	Burn-In Cost	Tractable?	Type
UCRL2 ( Auer et al., 2008 )	$DS\sqrt{AT}$	✓	N/A	✓	EVI
REGAL ( Bartlett and Tewari, 2012 )	$\\|h^{\star}\\|_{\textnormal{sp}}S\sqrt{AT}$	$\times$	N/A	$\times$	EVI
SCAL ( Fruit et al., 2018 )	$\\|h^{\star}\\|_{\textnormal{sp}}S\sqrt{AT}$	$\times$	N/A	✓	EVI
KL-UCRL ( Talebi and Maillard, 2018 )	$\sqrt{ST\sum_{s,a}\mathbb{V}^{\star}_{s,a}}+D\sqrt{T}$	✓	N/A	✓	EVI
EBF ( Zhang and Ji, 2019 )	$\sqrt{\\|h^{\star}\\|_{\textnormal{sp}}SAT}$	$\times$	(*)	$\times$	EVI
UCB-AVG ( Zhang and Xie, 2023 )	$S^{5}A^{2}\\|h^{\star}\\|_{\textnormal{sp}}\sqrt{T}$	$\times$	N/A	✓	UCB

Table 1: Comparison of algorithms and regret bounds for average-reward MDPs. Here

\|h^{\star}\|_{\textnormal{sp}}

is the span of the optimal bias function and

D

is the diameter, which satisfy

\|h^{\star}\|_{\textnormal{sp}}\leq D

. We always have

\Gamma\leq S

, and

\Gamma=1

in deterministic MDPs.

\mathrm{Var}^{\star}_{1-1/T}

and

\mathbb{V}^{\star}_{sa}

are instance-dependent variance parameters, which in particular are

0

for deterministic MDPs. Also

\mathrm{Var}^{\star}_{1-1/T}\leq\widetilde{O}(\|h^{\star}\|_{\textnormal{sp}}T+\|h^{\star}\|_{\textnormal{sp}}^{2})

. Only the leading terms as

T\to\infty

of the regret bound are shown. The burn-in cost is defined as the smallest

T

for which the algorithm achieves a minimax-optimal regret of

\widetilde{O}(\sqrt{\|h^{\star}\|_{\textnormal{sp}}SAT})

, or N/A if this does not occur. Priorless means that an algorithm does not require prior knowledge about the value of

\|h^{\star}\|_{\textnormal{sp}}

. (*) The burn-in cost of EBF ( Zhang and Ji, 2019 ) is

\|h^{\star}\|_{\textnormal{sp}}^{6}S^{4}A^{4}+\|h^{\star}\|_{\textnormal{sp}}^{6}S^{6}A^{2}+\|h^{\star}\|_{\textnormal{sp}}^{3}S^{12}A^{3}

Panel of Figure 1 — Figure 1: An example of the MDPs used in the proof of Theorem 3.8 . Here each state-action pair is annotated with its reward. If the transition associated with a state-action pair is deterministic, it is denoted with a solid arrow. If it is stochastic, it is represented as a solid line splitting into multiple dashed arrows to different states, each annotated with the associated probability of that transition. The MDPs are parameterized by $B>2$ , both have starting state $1$ , and differ only in the transition distribution of the stay action of state $2$ . In $P_{1}$ an optimal stationary policy traverses to state $2$ and stays there, while in $P_{2}$ an optimal stationary policy remains in state $1$ .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: An example of a hard MDP construction for $S=14$ and $A=3$ . To avoid clutter, we omit an additional deterministic self-loop at each leaf state. We also omit the deterministic actions which transit from the leaf states to the root and from the good state to the root, as these actions only serve to keep the diameter bounded by $D$ .

Panel of Figure 3 — Figure 3: An example of the MDPs used in the proof of Theorem J.1 . If the transition associated with a state-action pair is deterministic, it is denoted with a solid arrow. If it is stochastic, it is represented as a solid line splitting into multiple dashed arrows to different states, each annotated with the associated probability of that transition. The MDPs are parameterized by $B>1.$ Some actions, such as those which transit from leaf states back to the root state, are omitted.

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

Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiRegret Minimization in RL Markov Decision Processes
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
Jul 22, 2026Runlong Zhou, Zihan Zhang, Maryam Fazel +1Regret Minimization in RL Markov Decision Processes
University of Washington. · Hong Kong University of Science and Technology. · §University of Washington. +1

Feb 2, 2026J/K move · Enter open · S save

Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan

Regret Minimization in RL Markov Decision Processes Reinforcement Learning Policy Optimization Follow-the-Regularized-Leader

Open paper AskPDF arXiv

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic

Q

-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.

Abstract

Regret Minimization in RL

Explore similar work

Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence