- Rating
- 3(+2)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
A bonus-free algorithm for finite-horizon tabular RL is introduced, named Value Iteration with Bootstrap Ensemble (VIBE). The central Idea is the Quantile of Means (QoM) estimator, which aggregates predictions from independent data partitions to induce optimism without explicitly computing confidence bonuses or posterior distributions. The authors' main claims are that VIBE achieves minimax-optimal, variance-dependent regret with only logarithmically many ensemble members, providing a theoretical foundation for ensemble-based exploration. Experiments on standard tabular RL benchmarks suggest competitive performance, particularly with a reduced ensemble size.
Critical strengths
1- The major strength is that the paper provides an alternative to traditional optimism-based exploration (to the best of my knowledge). They use quantile aggregation over independent data partitions rather than explicitly constructing exploration bonuses or posterior distributions.
2- The algorithm seems straightforward, and the theoretical guarantees are promising.
Critical weaknesses
1- My main concern is the validity of Lemma 1. The proof of the QoM bias bound relies on a concentration inequality that does not support the stated constants. The Freedman-type bound also omits a logarithmic confidence factor from its square-root term. As a counterexample, consider a Bernoulli, , 100,000 observations per batch, and , the probability of satisfying the stated lower bound is approximately compared with the required . Since this Lemma is used to establish the good event and control the estimation bias, this issue directly affects the justification of Theorems 4 and 16. Until this issue is resolved, I must reject the paper.
2- As quantile RL is fairly niche, it is worth exploring the existing literature. For example, consider the quantile definition of the quantile objective for cumulative rewards. There are several optimistic quantile RL algorithms that optimize quantiles of cumulative returns rather than using quantiles of ensemble estimates to induce optimism. I think it would be interesting to distinguish the difference to bold your contribution.
3- The paper repeatedly argues that optimism emerges naturally from quantile aggregation without explicitly constructed bonuses or priors. However, the proposed estimator is rather than the ordinary sample mean with denominator . This has an important consequence: when . Thus, the individual estimators are already optimistically biased, even before quantile aggregation.
Questions for authors
N/A
6 comments
Thank you for your time and considering my comment. For W1 and W2 I agree with you but I still think this needs to be acknowledged in the paper. For W3 I need more information if possible.
Thank you for the follow-up. We updated the paper as follows.
W1. We added the explicit constant calculation to the proof of Lemma 1.
W2. We added a paragraph on quantile and distributional RL to the related work.
W3. You are right that . However, a downward bias of in expectation does not yield optimism with high probability; this comes from the quantile over the ensemble. The pseudo-count only ensures that each batch is optimistic with constant probability uniformly over all nonnegative distributions, which matters only in an initial burn-in phase. A Bernoulli example makes this concrete.
Our optimism argument requires each batch mean to be optimistic, i.e., at most , with constant probability. The quantile over independent batches then boosts this to probability . Consider Bernoulli$(p)$ samples and the plain sample mean of a batch with samples, without the pseudo-count. Then exactly when the number of zeros, distributed as , is at least its mean . There are two phases:
- Burn-in, . The plain mean is optimistic only if at least one zero was observed, which happens with probability , between and . For fixed and close to , this is arbitrarily small. For example, with probability .
- After burn-in, . A binomial is at least its mean with probability greater than once its mean exceeds (Greenberg & Mohri, 2014). So the plain mean is optimistic with probability greater than , and the pseudo-count is no longer needed.
Hence, the plain mean is optimistic with probability at least for every . For , this is at least from the very first sample, so the pseudo-count is not needed at all. The same holds for any symmetric distribution, where this probability is at least . More generally, for any fixed distribution with finite variance this probability tends to , so the pseudo-count matters only in an initial phase. However, the length of this phase depends on the distribution and is unbounded across distributions (e.g., above), which is why a distribution-free guarantee needs it.
With the pseudo-count, Feige's inequality (Corollary 2) ensures that each batch is optimistic with probability at least for every and every nonnegative distribution. Its only cost is an additive in the bias of each batch, which turns the term from Freedman's inequality into the term in Lemma 1.
We added a discussion of the role of the pseudo-count, including this example, after Corollary 2 in the revised paper.
Rebuttal
We thank the reviewer for the careful review. The reviewer is right about the constant in Lemma 1. As we explain below, fixing it changes only numerical constants, not any rate or claim. All mathematical corrections are in the revised PDF.
W1 (constants in Lemma 1). The optimized form of Freedman's inequality in Lemma 14 omitted a factor log(1/δ). Lemma 1 applies it to each batch separately, at a fixed confidence level δ′=4.7⋅10−4 that does not depend on n, B, δ, or any problem parameter. The missing factor is therefore just a number: the coefficient 1.7 becomes 2(e−2)log(1/δ′)≈4.69≤4.7, and the additive 8R term is unchanged. The order-statistic step that follows is also unchanged, so the correction only affects the numerical constants of Lemma 8 and Theorems 4 and 16.
Revisiting the reviewer's example (Bernoulli$(1/2)$, B=260, nb=105 samples per batch, δ=e−10), with exact binomial computations. Since n=Bnb, the per-batch threshold is μ−cσ/nb−9/nb, and batch b fails if Sb/(nb+1) falls below it, where Sb∼Bin(nb,1/2). The QoM estimate is the ⌈260/65⌉=4-th smallest batch, so the bound holds if and only if at most 3 of the 260 batches fail:
With 1.7, the bound holds far less often than the required 1−e−10≈0.99995, confirming the counterexample. With 4.7, it holds well above that level. Since this issue was the main basis for the soundness score, we kindly ask the reviewer to reconsider it in light of the corrected proof.
W2 (quantile RL). Quantile (risk-sensitive) RL optimizes a quantile of the return distribution, which is a different objective. We optimize the standard expected loss, and use a quantile only across B independent estimates of the mean, as an exploration device that replaces bonuses.
W3 (the pseudocount). The pseudocount is not what creates optimism. Its effect, μ/(n+1), is negligible compared with the statistical fluctuations of order σ/n, so for large n each member is optimistic with probability only about 1/2. High-probability optimism comes from the quantile over B members. The pseudocount addresses a burn-in issue: before a rare low outcome is observed, the plain sample mean overestimates the true mean. For example, for Bernoulli$(p)$ with p close to one, a sample of n ones gives a sample mean of 1>p, while the pseudocount gives n/(n+1)≤p for all n≤p/(1−p). Together with Corollary 2, this ensures each member is optimistic with constant probability for every nonnegative distribution. We will clarify this after Corollary 2.