Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon Shaolei Du

Tsinghua University· University of Washington· HKUST

Reinforcement learning gap-dependent variance-dependent instance-dependent

Abstract

We consider gap-dependent regret bounds for episodic MDPs.

We show that the Monotonic Value Propagation (MVP) algorithm (Zhang et al. 2024) achieves a variance-aware gap-dependent regret bound of $

\tilde{O} ((\sum_{Δ_{h} (s, a) > 0} \frac{H ^{2} l o g K \land Var m a x ^{c}}{Δ _{h} ( s , a )} + \sum_{Δ_{h} (s, a) = 0} \frac{H ^{2} \land Var}{Δ _{min}} m a x^{c}

+SAH4(S∨H))logK),

w h ere

i s t h e pl annin g h or i zo n,

i s t h e n u mb ero f s t a t es,

i s t h e n u mb ero f a c t i o n s,

i s t h e n u mb ero f e p i so d es, an d

\tilde{O}

hi d es

\mathsf{poly} \log (S, A, H, 1 / \Delta\_{\mathrm{min}}, 1 / \delta)

t er m s . Here,

\Deltah(s,a) =Vh^ (a) - Qh^ (s, a) $re p rese n t s t h es u b o pt ima l i t y g a p an d$ \Delta{\mathrm{min}} := \min{\Deltah (s,a) > 0} \Deltah(s,a) $. T h e t er m$ \mathtt{Var}\_{\max}^{\textup{c}} $d e n o t es t h e ma x im u m co n d i t i o na lt o t a l v a r ian ce, c a l c u l a t e d a s t h e ma x im u m o v er a ll$ (\pi, h, s) $t u pl eso f t h ee x p ec t e d t o t a l v a r ian ce u n d er p o l i cy$ \pi $co n d i t i o n e d o n t r aj ec t or i es v i s i t in g s t a t e$ s $a t s t e p$ h $.$ \mathtt{Var}\_{\max}^{\textup{c}} $c ha r a c t er i zes t h e ma x im u m r an d o mn esse n co u n t ere d w h e n l e a r nin g an y$ (h, s)$ pair.

Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms.

To complement the study, we establish a lower bound of $

Ω (\sum_{Δ_{h} (s, a) > 0} \frac{H ^{2} \land Var m a x ^{c}}{Δ _{h} ( s , a )} \cdot lo g K),

$d e m o n s t r a t in g t h e n ecess i t yo fd e p e n d e n ceo n$ \mathtt{Var}\_{\max}^{\textup{c}} $e v e n w h e n t h e ma x im u m u n co n d i t i o na lt o t a l v a r ian ce (w i t h o u t co n d i t i o nin g o n$ (h, s)$) approaches zero.