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

Feb 2, 2026

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

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.

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

Ask PDF

May 19, 2026

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of

\smash{\tilde{O}(dH^2\sqrt{T})}

(Li et al., 2024), where

d

is the feature dimension,

H

the episode length, and

T

the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant

\barσ\_T \leq 1/2

, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of

\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}

, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs,

\barσ\_T = O(H^{-1})

, reducing the horizon dependence by a factor

H

. We further establish a matching

\smash{Ω(dH^2\barσ\_T\sqrt{T})}

lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.

Pierre Boudart, Pierre Gaillard, Alessandro Rudi

SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3

Regret Minimization in RL Markov Decision Processes Reinforcement Learning Minimax Regret

Ask PDF

Jul 22, 2026

Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with

S

states,

A

actions, horizon

H

, and per-trajectory total reward bounded by

1

. We propose a new algorithm and prove a regret upper bound

\tilde O(\sqrt{SAK}+S^8A^3)

with failure probability

δ

, where

K

is the number of episodes and

\tilde O(\cdot)

hides

\mathsf{poly}\log(S,A,K,1/δ)

. Thus, the regret is

H

-free and asymptotically optimal, matching the contextual-bandit lower bound

Ω(\sqrt{SAK})

up to logarithmic factors. This completely removes the

\log H

dependence from the previous

\tilde O(\sqrt{SAK\log H}+S^2A\log H)

guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret

\tilde O(\sqrt{S^9A^3K})

of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions

\{V_h^*\}_{h=1}^H

are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional

\min\{\log H,S\}

factor. We avoid this factor by (i) exploiting the monotonicity of

V_h^*

h

and (ii) non-trivially projecting the value functions onto an

S

-dimensional grid. Our analysis relies on three additional ingredients. First, we introduce a horizon-truncation argument that enables reward-based exploration and removes the cost of a separate reward-free exploration phase. Second, we design a cutting bonus that preserves both optimism and the monotonicity needed for planning. Third, we prove a new bound on total deviation for time-homogeneous MDPs, which controls the clipped variance terms in the cutting bonus with adjustable polynomial dependence on

S

and without any dependence on

H

. Together, these tools yield an asymptotically optimal horizon-free regret guarantee.

Runlong Zhou, Zihan Zhang, Maryam Fazel +1

University of Washington. · Hong Kong University of Science and Technology. · §University of Washington. +1

Regret Minimization in RL Markov Decision Processes Reinforcement Learning

Ask PDF

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