- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies model-free online RL for episodic tabular MDPs. It proposes UCB-Bernstein+, which makes two changes to UCB-Bernstein. First, it adds the stage-wise lazy update of UCB-Advantage (Zhang et al., 2020). Second, it computes the Bernstein bonus from stage-wise samples only and caps it with a Hoeffding term. The main result (Theorem 3.1) is a fine-grained gap-dependent regret bound. Its per-triple term is . Here is the maximum conditional variance at step , and is an analysis parameter. The paper also gives a gap-dependent local switching cost bound (Theorem 3.2). It further gives a worst-case regret of (Theorem 3.3) and a worst-case local switching cost of (Theorem 3.4). The key tool is a pseudo value function that clips to . Experiments on random MDPs and GridWorld show lower regret and lower switching cost than the baselines.
Critical strengths
The question is natural. Fine-grained gap-dependent bounds previously existed only for Hoeffding-type model-free methods, and the paper clearly explains the technical obstacle in extending them to variance-based bonuses. The pseudo value function is a clean tool. It does not change the algorithm, it supports both the gap-dependent and the worst-case analyses, and it removes the superlinear term of the original UCB-Bernstein. The proofs are careful and track constants explicitly. The key steps, including the optimism argument in Lemma G.1, the variance decomposition in Eqs. (55)–(60), the recursion in Lemma H.3 and the switching-cost reduction in Appendix K, appear correct. In addition, the paper attains the best known worst-case local switching cost with a Bernstein-based algorithm.
Critical weaknesses
W1. With and , the bound has the same -dependence as the Hoeffding analysis of Zhang et al. (2026a), as the authors acknowledge. Bernstein bonuses usually help through the law of total variance, but this analysis does not use it. The reason is that is a per-step maximum over all . A single high-variance pair at step removes any gain at that step. The variance factor is therefore not fine-grained, and the title and abstract overstate the result.
W2. The bound is , not . The last term of Theorem 3.1 is . Since , this term is at least for any choice of , and it dominates the terms as grows. Section 5 says the flat curves are consistent with Theorem 3.1, which is inaccurate. Please state the -dependence explicitly and discuss whether is achievable.
W3. All synthetic MDPs have transitions drawn uniformly from the simplex, with one instance per scale. These instances are neither low-variance nor gap-controlled, so they say nothing about variance-awareness or gap dependence. Instances with controlled and are needed.
W4. The experiments use , and . The theory requires , , and . The tested algorithm is therefore not the analyzed one. Please state this and report at least one run with the theoretical constants.
W5. There are also a few minor presentation problems: Lemma I.1 is central to Theorem 3.2 but appears only in the last appendix. It should be moved to the main text. Theorem 3.2 is stated after setting , which hides its variance-aware form. In the introduction, is defined differently for Xu et al. and Zhang et al. within the same display. Theorem 3.1 also requires knowing in advance, through . The introduction says it is open whether UCB-Bernstein admits a gap-dependent bound. The paper analyzes a modified algorithm, so this question remains open.
[1] Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Q-learning with fine-grained gap-dependent regret. In International Conference on Learning Representations (ICLR), 2026.
Questions for authors
Q1. Can be replaced by a per-triple variance or by a total-variance term? If not, where does the argument fail?
Q2. How does the coarse-grained version of Theorem 3.1 compare with Zheng et al. (2025b) in , , and ?
[1] Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for Q-learning using reference-advantage decomposition. In International Conference on Learning Representations (ICLR), 2025. (Zheng et al., 2025b; cited in Q2)
6 comments
Rebuttal by Authors (Part II)
W3: Multiple-MDP Robustness and Controlled Gap/Variance Experiments
We thank the reviewer for this comment. In the revised version, we address this concern in two complementary ways.
First, in Appendix B.3, we repeat the main-algorithm and state-of-the-art baseline comparisons over five independently generated MDPs for each experimental scale, with 10 independent runs on each MDP. The results in Figures 5--7 remain consistent with the original experiments, supporting that the empirical advantages of UCB-Bernstein+ are not specific to a single randomly generated MDP.
Second, in Appendix B.4, we introduce a controlled family of synthetic MDPs in which the suboptimality-gap structure and the conditional variance are varied systematically. For each fixed variance level, the transition kernel and the complete conditional-variance table remain unchanged while the entire positive gap table increases coordinate-wise. Conversely, for each fixed gap level, the complete gap table remains unchanged while the conditional-variance table increases coordinate-wise. These properties are verified exactly using dynamic programming.
The corresponding results are shown in Figures 8--13. UCB-Bernstein+ maintains favorable regret and switching-cost performance across all nine controlled settings. Moreover, Figures 12--13 directly isolate the two effects: at a fixed gap table, regret increases with the conditional variance, while at a fixed transition kernel and variance table, regret decreases as the gap structure becomes more favorable, qualitatively consistent with Theorem 3.1.
Further details of the multiple-MDP robustness and controlled gap/variance experiments are provided in Appendices B.3 and B.4 of the revised paper.
W4: Theoretical coefficients
We thank the reviewer for pointing out this distinction. We agree that the parameterization used in our main experiments is a practical version of UCB-Bernstein+, rather than the parameterization used in the theoretical analysis. We have clarified this distinction in Section 5 of the revised paper.
The constants in the theoretical bonus are chosen to ensure the concentration and optimism properties needed for the high-probability analysis. They are consequently conservative for the finite interaction budgets considered in our experiments. In particular, the theoretical bonus contains both a variance-dependent term with coefficient and a lower-order term with coefficient , as well as a Hoeffding-type cap with coefficient . Together with the logarithmic factor , these terms can remain large during the early stages of learning. Since the -estimates are initialized optimistically and updated by taking a minimum with the new estimate, a large bonus can delay decreases in the -values and, in turn, changes in the greedy policy.
For illustration, consider and an outer failure probability . Under the high-probability setting in our analysis, . The theoretical Hoeffding-type cap is then , which is at least when the current stage count satisfies . Over this range, the lower-order term is also larger than . Hence, the resulting optimistic bonus can be large relative to the horizon and can delay informative value and policy updates.
At the finite interaction budgets considered in our experiments, directly using these theoretical constants would therefore leave a substantial initial portion of learning under an extremely conservative optimistic bonus, making such a performance comparison largely uninformative about the practical behavior of the algorithm. We therefore explicitly distinguish the theoretical and practical parameterizations and provide the calculation above to quantify the conservativeness of the theoretical choice.
For a reasonably fair empirical comparison across algorithms, our main experiments therefore use the same coefficient for the leading exploration terms and coefficient for the lower-order terms whenever applicable. This parameterization is intended to compare the practical behavior of the algorithms under comparable bonus scales, rather than to reproduce the conservative constants used in the theoretical analysis. Similar practical choices are made in [4,5]; moreover, some baseline analyses specify bonus coefficients only as sufficiently large universal constants.
We have also added a bonus-coefficient sensitivity experiment in the appendix. It varies the leading exploration coefficients over a common range while keeping the lower-order terms fixed, and the comparison remains consistent across these choices.
(continued in the next part)
Rebuttal by Authors (Part III)
W5: Presentation and Clarifications.
Thank you for pointing out these presentation issues. We have revised the manuscript accordingly.
First, we agree that Lemma I.1 is important for understanding the gap-dependent local switching-cost result. We have therefore moved its variance-aware statement to the main text immediately before Theorem 3.2, while retaining its detailed proof in the appendix.
Second, we have revised the presentation of Theorem 3.2 so that its variance-aware form is stated explicitly before taking the worst-case relaxation. In particular, the bound now retains its dependence on and the analysis parameter . The previous bound is then presented as a simplified consequence obtained by using and setting . This makes the variance adaptivity underlying the switching-cost result explicit.
Third, we have corrected the notation in the introduction. Previously, the same symbol was used for different notions of optimal triples in the bounds of Xu et al. and Zhang et al. We now use separate notation for the two quantities and state their definitions explicitly.
Fourth, we have clarified the dependence on the known time horizon. In our theoretical guarantees, the confidence parameter is chosen as a function of (e.g., in Theorem 3.1), and hence the theoretical parameter setting assumes that is known in advance. We now state this explicitly when introducing . This is separate from our experimental implementation, where is treated as a positive tuning parameter.
Finally, UCB-Bernstein is one of the simplest model-free algorithms using variance-based exploration bonuses, yet a fine-grained gap-dependent analysis for model-free algorithms with such bonuses was previously unavailable. This gap is an important motivation for our work. Starting from UCB-Bernstein+, a refined version of UCB-Bernstein that incorporates a stage-wise update design and a refined variance-based bonus, we introduce pseudo value functions to address the main technical difficulty arising from the state-action-dependent variance-based bonus structure and establish a fine-grained gap-dependent analysis. Although our current theorem is established for UCB-Bernstein+ rather than the original UCB-Bernstein, the pseudo-value-function technique is designed to handle the variance-aware bonus structure itself and may therefore be useful for analyzing variance-aware bonuses more broadly, potentially including the corresponding gap-dependent analysis of the original UCB-Bernstein. We have revised the introduction by removing the potentially ambiguous statement about the original UCB-Bernstein and clarifying that our contribution addresses the question of fine-grained gap-dependent analysis with variance-based bonuses.
Q2: Coarse-grained comparison
Our revised Theorem 3.1 contains two distinct levels of instance adaptivity that are absent from their coarse-grained bound.
First, the revised theorem retains the triple-specific conditional variances rather than replacing them by the global maximum conditional variance Second, our result is fine-grained in the suboptimality gaps: it depends on the individual , the step-dependent , and the structure of the optimal sets , rather than only on the global minimum gap . Therefore, if either the local variance structure or the fine-grained gap structure is favorable, Theorem 3.1 can be substantially smaller than its fully coarse-grained relaxation. In particular, a few high-variance triples do not force all triples to pay the global worst-case variance, and a few small-gap triples do not force all suboptimal triples to pay .
To obtain a direct coarse-grained comparison, we now remove both sources of instance adaptivity. Specifically, let for all , replace all positive gaps by , use , and upper bound . For the suboptimal-triple term, this gives
O\left(\frac{(\mathbb{Q}^{\star}+\beta^2)H^4SA}{\Delta_{\min}}\right).$$ Similarly, the optimal-pair contribution satisfies $$\sum_{h=1}^H\frac{H\left(\sum_{t=h+1}^H\sqrt{\sum_{(s,a)\in Z_{\mathrm{opt},t}}(\mathbb{V}_{s,a,t}(V_{t+1}^{\star})+\beta^2)}\right)^2}{\Delta_{\min,h}} \leq O\left(\frac{(\mathbb{Q}^{\star}+\beta^2)H^4SA}{\Delta_{\min}}\right).$$ Hence, the fully coarse-grained version of our Theorem 3.1 is $$O\left(\frac{(\mathbb{Q}^{\star}+\beta^2)H^4SA\log(SAT)}{\Delta_{\min}}+\frac{H^6SA\log^2(SAT)}{\beta}\right).$$ (continued in the next part)
Rebuttal by Authors (Part I)
We thank you for your thoughtful comments. Below are our responses.
W1 and Q1: Stepwise maximum variance
The step-wise maximum conditional variance is not essential to our proof. In fact, our original analysis first obtains a bound in terms of the triple-specific conditional variance Vs,a,h(Vh+1⋆), and only subsequently upper bounds it by Qh⋆=maxs,aVs,a,h(Vh+1⋆) to simplify the presentation.
Motivated by the reviewer’s comment, we have strengthened Theorem 3.1 in the uploaded revision by retaining the triple-specific conditional variances throughout the analysis. In particular, the suboptimal-triple contribution now depends on ∑h=1H∑Δh(s,a)>0Δh(s,a)(Vs,a,h(Vh+1⋆)+β2)H3ι1, rather than using the step-wise maximum variance for every state-action pair. Similarly, the contribution from optimal state-action pairs is refined from a term involving (Qt⋆+β2)∣Zopt,t∣ to one involving ∑(s,a)∈Zopt,t(Vs,a,t(Vt+1⋆)+β2). Thus, a single high-variance state-action pair no longer forces all pairs at the same step to pay the corresponding worst-case variance cost. This directly addresses the instance-adaptivity concern raised by the reviewer and gives an affirmative answer to Q1 through the per-triple variance refinement.
This refinement requires no change to UCB-Bernstein+ or to the main proof technique; it simply avoids the step-wise worst-case relaxation that was used in the previous presentation. The original step-wise bound follows immediately as a simpler corollary by upper bounding each local variance by Qh⋆. The strengthened result and its corresponding proof are provided in the updated version.
W2: Dependence on logT
By “approximately logarithmic” in Section 5, our intended meaning was that the empirical regret exhibits very slow, polylogarithmic-type growth in T, rather than polynomial growth. We did not intend this phrase to claim that Theorem 3.1 establishes an exact O(logT) regret rate. To make this intended meaning explicit, in the revised version we replace “suggesting approximately logarithmic cumulative regret growth” with “suggesting polylogarithmic-type cumulative regret growth.”
More precisely, the first two terms in Theorem 3.1 scale with ι1=log(SAT), while the residual term is βH6SAι12. Thus, for fixed problem-dependent quantities, Theorem 3.1 has a polylogarithmic dependence on T, with an O(log2T) lower-order residual term. The relatively flat Regret(T)/log(K+1) curves in Section 5 were intended to illustrate this slow empirical growth, rather than to distinguish between an exact O(logT) and O(log2T) dependence over the finite range of K considered in the experiments.
The O(log2T) dependence originates from the lower-order O(ι/n) term that commonly appears in variance-aware exploration bonuses, including those used in our algorithm and in [1,2,3,4]. The precise meaning of n depends on the algorithm: in our algorithm and [1], n is the number of visits collected in the preceding stage, while in non-stage-wise variance-aware algorithms [2,3,4] it typically denotes the cumulative number of visits to the corresponding state-action-step triple. In either case, the confidence factor ι itself contains a logarithmic dependence on T.
To bound regret, one needs to accumulate the exploration bonuses over the entire learning process. Consequently, the lower-order O(ι/n) component is also accumulated over all relevant updates and visits. This accumulation contributes another logarithmic dependence on T on top of the logarithmic dependence already contained in the confidence factor ι, resulting in the squared logarithmic dependence. In our analysis, this effect is captured by Lemma E.2 with α=1, which yields Equation (78):
\lesssim \frac{H^4SA\iota^2}{\beta}.$$ This contribution is subsequently incorporated into Equation (76) and ultimately gives rise to the $\iota^2$-dependent residual term in Theorem 3.1. Hence, the squared logarithmic dependence in the residual term is a natural consequence of accumulating the $O(\iota/n)$ component of the variance-aware exploration bonus throughout the learning process: one logarithmic dependence is contained in the confidence factor $\iota$, while the other arises from controlling the cumulative contribution of the inverse-visit-count term, as formalized by Lemma E.2 and Equation (78). Reducing the resulting $O(\log^2 T)$ dependence to $O(\log T)$ would require a sharper way of controlling this lower-order bonus contribution, and whether such a refinement is possible remains an open question.