Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon Du
We consider the gap-dependent regret bounds for episodic MDPs.We show that the Monotonic Value Propagation (MVP) algorithm (\cite{zhang2024settling}) achieves a variance-aware gap-dependent regret bound of $$\tilde{O}\left(\left(\sum_{\Delta_h(s,a)>0} \frac{H^2 \land \cVarmax}{\Delta_h(s,a)} +\sum_{\Delta_h(s,a)=0}\frac{ H^2 \land \cVarmax}{\Delta_{\mathrm{min}}} + S^2AH^3 \right) \cdot \log K\right),$$ where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Here, $\Delta_h(s,a) =V_h^* (a) - Q_h^* (s, a)$ represents the sub-optimal gap and $\Delta_{\mathrm{min}} := \min_{(h,s,a)}\Delta_h(s,a)$.The term $\cVarmax$ denotes the maximum conditional total variance, calculated as the maximum over all $(\pi, h, s)$ tuples of the expected total variance under policy $\pi$ conditioned on trajectories visiting state $s$ at step $h$. This $\cVarmax$ characterizes the randomness encountered when learning a $(h, s)$ pair.Our result stems from a novel analysis of the weighted sum of the sub-optimal gap and can be potentially adapted for other algorithms.To complement the study, we establish a lower bound of $$\tilde{\Omega}\left( \sum_{\Delta_h(s,a)>0} \frac{H^2 \land \cVarmax}{\Delta_h(s,a)}\cdot \log(K)\right),$$ demonstrating the necessity of dependence on $\cVarmax$ even when the maximum unconditional total variance (without conditioning on $(h, s)$) approaches zero.