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

In the abstract, should the definition of delta_min be restricted to (h,s,a) that delta_h(s,a) > 0 as is discussed in more detail later in the part of the paper?

In line 181, should the reference be to Definition 2?

I’m particularly interested in the gap between the upper and lower bounds presented in the paper. Line 261 refers to Appendix H for further discussion, but I couldn’t locate it in the supplementary material. Could you provide clarification or additional insights on this point?

We thank the reviewer for identifying these typographical and referencing issues. We will correct them in the camera-ready version, should the paper be accepted. Specifically:

• In the abstract, the definition of $\Delta_{\min}$ is indeed intended to apply only to $(s,a,h)$ tuples with $\Delta_h(s,a) > 0$, consistent with the more detailed discussion later in the paper.

• The citation on line 181 should refer to Definition 2, not Definition 1.

• The reference on line 261 should point to Appendix C, not Appendix H. Appendix C contains the formal proof of Theorem 3 and elaborates on the gap between the upper and lower bounds.

In Definition 2, the summation starts from h'=1 and it is conditioned on a potentially later step s_h, which feels somewhat unconventional. Could you provide some intuition on why this formulation is important and how it plays a role in the regret bound?

We agree that the formulation of conditional total variance in Definition 2 may appear unconventional, as it conditions on a future state $s_h$, which breaks the usual Markov structure. However, this definition is crucial to our analysis.

The summation from $h'=1$ to $h$ quantifies the variance accumulated before reaching the state-action pair $(s,a,h)$. The conditioning on $s_h$ reflects that this quantity is only meaningful along trajectories that actually visit $(s,h)$. This captures the following phenomenon: to obtain sufficiently accurate estimates at $(s,a,h)$ and avoid regret from under-sampling, the agent may need to visit earlier states more frequently than would be necessary. This additional sampling effort is encoded in the conditional variance, making it central to understanding and bounding the regret.

The favorable bounds of the MVP algorithm shown in this work is very interesting, however, does this tight bound mean the MVP algorithm is very close to an optimal algorithm? Do you think we should still try to develop newer RL algorithms, or just focus on adapting existing ones into practical problems?

We believe there is still significant room for developing new RL algorithms. A result by Simchowitz et al. shows that a regret term of order $S/\Delta_{\min}$ is unavoidable for any optimistic algorithm—this limitation is reflected in the second term of our regret bound. In contrast, Xu et al. propose the AMB algorithm, which reduces this term to $|\mathcal Z_{\mathrm{mul}}|/\Delta_{\min}$ in a variance-independent setting, where $|\mathcal{Z}_{\mathrm{mul}}|$ is a more refined structural quantity (equal to zero when every state has a unique optimal action). This comparison suggests that there may be unexplored algorithmic directions that combine the variance-awareness of MVP with the structural adaptivity of AMB. Hence, we are optimistic about future algorithmic advances beyond MVP.

Is there any empirical evidence showing that MVP works much better than alternative RL algorithms? (perhaps even in some special MDPs)

Empirical comparisons between MVP and other RL algorithms are nontrivial, especially in finite-horizon tabular MDPs. The performance is often sensitive to constant factors and logarithmic terms, which makes isolating the impact of the theoretical improvements quite difficult. At this stage, we do not have conclusive empirical results supporting a performance advantage for MVP. A rigorous experimental study, particularly on carefully designed MDPs that highlight the role of variance, is an important direction for future work.

How easily will the analysis made in the paper be extended to other more general MDP settings?

We believe the techniques in our analysis can be extended to other gap-dependent settings without significant difficulty. The key challenge typically lies in identifying appropriate weighting schemes that lead to tight bounds. Once those are identified, our framework for incorporating conditional variance could likely be reused or adapted with modest effort.

Does these theoretical results bring insight on how to better adapt MVP (or similar model-based algorithms) to settings with function approximation or large state spaces?

To our knowledge, there has not yet been an attempt to generalize the analysis of MVP—or other similar model-based algorithms—to the function approximation setting. We view this as an important and open problem. While our theoretical results provide some insight into how variance affects regret in the tabular case, extending these insights to large or continuous state spaces will likely require new techniques. We consider this a promising avenue for future research.

Why did the authors choose to present only the informal version of the regret bound in the main paper and leave the formal theorem to the appendix? The formal version of the lower bound is particularly different than the informal version presented in Theorem 3. I strongly recommend including the complete technical theorem in the main paper.

The abstract includes the mathematical expression for regret bounds. Mathematical expressions are not displayed properly when the abstract is shown outside the PDFs (for e.g., openreview website). Hence, the authors might want to consider rewriting the abstract with fewer (or none) mathematical expressions to improve readability.

We would like to thank the reviewer for their helpful suggestions regarding the presentation of our main theorem and the rendering of the abstract. These issues will be addressed in the camera-ready version, should the paper be accepted.

While the upper bound proof of the regret is well written, it was challenging to follow the presentation of the lower bound, due to the following reasons.

We apologize for any confusion caused by the proof of the lower bound. We are happy to clarify any specific concerns. If any part of the proof remains unclear, please indicate the exact step or argument that you find troubling, and we will provide a detailed explanation.

A lot of details (including assumptions) are missing from the informal version of the lower bound theorem (Theorem 3).

We chose to present an informal statement of the lower-bound theorem in the main text to balance precision and clarity. The formal version, which includes all technical details and assumptions, is available in the Appendix for interested readers.

Instead of giving a summarized, intuitive idea of the proof in the proof sketch, a simplified instance is discussed, which does not give much insight into how the instance can be generalized.

The example in the proof sketch captures the key behavior of the MDP used in the formal lower-bound proof: the agent starts in the main state $\texttt A$, transitions once with high probability to an action state $\texttt B$, and then makes a decision. This structure generalizes to arbitrary $S,A,H$ by introducing more action states, as detailed in the Appendix.

Even though I am well aware of the multi-armed bandits lower bound proof (Lai & Robbins, 1985) utilized in appendix C, it was difficult to see how to it utilized to get a lower bound here, I request authors to expand and provide more detailed and easy to follow proof of the lower bound in the appendix.

Finally, the lower bound for multi-armed bandits is used to bound the regret incurred in each action state. Summing these contributions yields a valid lower bound for the regret in the MDP setting.

A detailed discussion about the significance of conditional variance is needed. e.g., what are some cases where conditional variance is significantly small? (better still , small experiments to depict this intuition)

Why is this a tighter or more appropriate notion than unconditional total variance (Def 1).

Thank you for raising this point about the distinction between conditional and unconditional variance. In Appendix C, we construct an MDP instance that matches our lower bound, where the unconditional variance is significantly smaller than the conditional variance. This demonstrates that the unconditional variance fails to capture the complexity relevant to gap-dependent regret, making it inadequate for deriving tight lower bounds in such settings. We will clarify this distinction more explicitly in the camera-ready version, should the paper be accepted.

That said, empirical investigation of MVP is not straightforward. Currently, we lack conclusive evidence that changes in performance can be attributed specifically to differences in (un)conditional variance, as other factors—such as suboptimality gaps or constant scaling—may dominate. As a result, designing meaningful experiments to illustrate this point remains an open challenge.

How does the MVP algorithm behave with small \Delta_min.

We suspect you are referring to the second term \sum_{\Delta_h(s,a)=0}\frac{H^2\wedge \texttt V\texttt a\texttt r_c^*}{\Delta_\min} in our bound. While this term does not appear in our lower bound, Simchowitz et al. (2021) established that a regret term of order $\frac{S}{\Delta_{\min}}$ is unavoidable for any optimistic algorithm. Our $\Delta_{\min}$-dependent term reflects this intrinsic limitation. For a more in-depth discussion, we refer you to the aforementioned work.

Can the authors comment if there are other lower instance dependent lower bounds which may not be "variance-aware" ? How does their lower bounds compare with those?

To the best of our knowledge, there are no other instance-dependent lower bounds that incorporate both suboptimality gaps and variance information. However, there are bounds that focus solely on the suboptimality gaps. As mentioned earlier, Simchowitz et al. derive a lower bound of $O(\sum_{\Delta_h(s,a)>0} \frac{1}{\Delta_h(s,a)} + \frac{S}{\Delta_{\min}})$ for optimistic algorithms. Xu et al. later generalized this bound to cover all algorithms when $S$ is logarithmically small. Our work extends this line of research by introducing conditional variance as an additional key factor.

Do the authors make any changes to MVP algorithm ? or one should consider this paper as proving properties for the MVP algorithm?

The MVP algorithm analyzed in our paper is a slightly modified version of the original algorithm proposed by Zhang et al., which includes a doubling update trick. We believe this trick is intended to reduce update costs in the minimax setting and is not essential for the gap-dependent analysis considered here. Therefore, we omit it in our version. Relevant discussion can be found in the footnote on page 6.