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

Mingyi Li; Taira Tsuchiya; Kenji Yamanishi

cs.LGFeb 2, 2026

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

Authors: Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

Abstract

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.

Explore similar work

Jun 30, 2026cs.LG

Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic

Q

-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent

\mathrm{polylog}(T)

regret in the stochastic regime.

Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

Sublinear Regret Markov Decision Processes Policy Optimization Transitions

Ask PDF

May 19, 2026cs.AI

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

Sublinear Regret Markov Decision Processes Generalized Linear Bandit Minimax Regret

Ask PDF

May 27, 2026stat.ML

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

Reinforcement learning with multinomial logistic (MNL) function approximation has become an important framework due to its flexibility and broad applicability. While existing studies have established regret guarantees under worst-case analysis, they do not capture how performance depends on the variability of the interaction between the learner and the environment. In this paper, we develop a new theoretical analysis for MNL-based Markov decision processes that yields explicit variance-adaptive regret bounds. Our algorithm is computationally efficient and achieves the instance-wise optimal rate of regret, narrowing the gap between upper and lower bounds. Our numerical experiments validate that our method learns optimal policies more efficiently than conventional approaches.

Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1

Markov Decision Processes Optimal Policies Variance Reduction Worst-Case Sensitivity

Ask PDF