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

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

where H is the planning horizon, S is the number of states, A is the number of actions, K is the number of episodes, and Õ hides poly logpS, A, H, 1∆ min , 1δq terms. Here, ∆ h ps, aq " V ˚ h paq ´Qh ps, aq represents the suboptimality gap and ∆ min :" min ∆ h ps,aqą0 ∆ h ps, aq. The term Var c max denotes the maximum conditional total variance, calculated as the maximum over all pπ, h, sq tuples of the expected total variance under policy π conditioned on trajectories visiting state s at step h. Var c max characterizes the maximum randomness encountered when learning any ph, sq 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

demonstrating the necessity of dependence on Var c max even when the maximum unconditional total variance (without conditioning on ph, sq) approaches zero.

we show that the gap-dependent regret depends on a variance quantity Var c max ď HQ ˚, and the worst-case dependency on H is H 2 . We improve the above-mentioned two factors simultaneously. Formally, with probability at least 1 ´δ, the regret in K episodes by MVP is bounded as r O ¨¨ÿ ph,s,aqPZ sub

To the best of our knowledge, we are the first to incorporate a tighter variance quantity into gapdependent regrets, and the worst-case dependency of H 2 in gap-dependent terms is also the stateof-the-art (see Table 1).

To complement our upper bound, we provide a lower bound (see Theorem 3) of

With this lower bound, we show that the first term in the upper bound (2) is tight (modulo log terms). This implies that (i) It is necessary to introduce the conditional total variance (see Definition 2) to derive a variance-aware gap-dependent bound. In comparison, the unconditional total variance (see Definition 1) is sufficient for variance-aware minimax bounds (e.g., Zhou et al. [2023]); (ii) When the first term in (2) dominates, the order of H cannot be improved.

We propose a new variance metric to describe the upper bound of regret in gap-dependent MDPs. Our version of variance metric considers the conditional total variance to allow for some states with small visiting probability to accumulate a large regret over the whole training progress.

To derive a tighter regret bound using our new metric, we utilize a novel analysis which reweighs the suboptimality gaps. Our approach does not require the clipping and recursion method in Simchowitz and Jamieson [2019] for the main bound; instead, we directly prove that a certain weight sum over all suboptimality gaps times the visitation counts is bounded by a lower-order term of visitation counts, and establish a congregated upper bound of all visitation counts. We believe our approach is novel and reveals fundamental facts about suboptimality gaps.

We also propose a more refined version of clipping for optimal actions. Our version of clipping utilizes the new conditional variance metric while also providing an OpH 2 q worst case bound for ∆ min -dependent terms.

Finally, we prove that the ∆ h ps, aq terms in our upper bound match the lower bound modulo log factors. The construction is based on a reduction to Bernoulli bandits. A key insight is that lowfrequency states, though often neglected in deriving minimax regret bounds, can still contribute substantially to regret in gap-dependent bounds.

Paper overview. In Section 2, we introduce previous research about gap-dependent regret bound.

In Section 3, we list the basic concepts of MDPs and define the conditional variance. In Section 4, we describe the MVP algorithm and provide a proof sketch of the gap-dependent regret upper bound. We conclude our paper in Section 5 with a matching lower bound.

2 Related works Gap-dependent regrets and sample complexities. Research on gap-dependent regrets originates from multi-armed bandits, which are special MDPs with H " S " 1. Auer et al. [2002] showed a ř aPZsub log K∆paq type regret when running an UCB algorithm on MABs. Bubeck et al. [2012] proposed algorithms achieving a ř aPZsub p∆paq `logp1εq∆paqq bounded regret given knowledge of the maximum reward max a rpaq as well as a lower bound ε ą 0 of ∆.

Aside from the works studying finite-horizon tabular MDPs mentioned in Section 1, there is a line of work under the setting of gap-dependent regrets for infinite-horizon tabular MDPs [Auer and Ortner,

for all s, a, h, k, where we recall the definition w h ps, aq " Var hps, aq, W " mint160H 2 logp4KpH `1qδq, Var c max u and F k,h is the σ-field generated by the first pk ´1q episodes and the first h steps of the k-th episode.