acceptodds
Under review as a conference paper at ICLR 2027

Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning

Abstract

Optimal Reinforcement Learning (RL) algorithms typically rely on carefully constructed count-based uncertainty estimates, such as bonuses or posterior distributions, to drive exploration. Although theoretically sound, such estimates are difficult to scale and therefore offer limited insight for designing exploration heuristics in practice. Meanwhile, ensembling has emerged as a practical approach, but remains without theoretical justification. Building on a recent ensemble-based method for Multi-Armed Bandits, we propose a quantile-based ensemble method for finite-horizon tabular MDPs. Our simple bonus-free approach achieves optimal variance-dependent regret bounds without explicit uncertainty estimation, providing theoretical grounding for ensemble-based exploration in RL.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, ensembles, tabular mdps, regret

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7QEAOpenReview ↗
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, B=260B=260, 100,000 observations per batch, and δ=e−10\delta=e^{-10}, the probability of satisfying the stated lower bound is approximately 0.740.74% compared with the required 99.99599.995%. 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 μ^b=∑i=1nbXinb+1\widehat \mu_b=\frac{\sum_{i=1}{n_b}X_i}{n_b+1} rather than the ordinary sample mean with denominator nbn_b. This has an important consequence: E[μ^b]=nbnb+1μ<μ\mathbb{E}[\widehat \mu_b]=\frac{n_b}{n_b+1}\mu<\mu when μ>0\mu>0. Thus, the individual estimators are already optimistically biased, even before quantile aggregation.

Questions for authors

N/A

6 comments

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/δ)\sqrt{\log(1/\delta)}. Lemma 1 applies it to each batch separately, at a fixed confidence level δ′=4.7⋅10−4\delta' = 4.7 \cdot 10^{-4} that does not depend on nn, BB, δ\delta, or any problem parameter. The missing factor is therefore just a number: the coefficient 1.71.7 becomes 2(e−2)log⁡(1/δ′)≈4.69≤4.72\sqrt{(e-2)\log(1/\delta')} \approx 4.69 \le 4.7, and the additive 8R8R 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=260B = 260, nb=105n_b = 10^5 samples per batch, δ=e−10\delta = e^{-10}), with exact binomial computations. Since n=Bnbn = Bn_b, the per-batch threshold is μ−c σ/nb−9/nb\mu - c\,\sigma/\sqrt{n_b} - 9/n_b, and batch bb fails if Sb/(nb+1)S_b/(n_b+1) falls below it, where Sb∼Bin(nb,1/2)S_b \sim \mathrm{Bin}(n_b, 1/2). The QoM estimate is the ⌈260/65⌉=4\lceil 260/65 \rceil = 4-th smallest batch, so the bound holds if and only if at most 3 of the 260 batches fail:

c=1.7c = 1.7 (erroneous)c=4.7c = 4.7 (corrected)
threshold0.497220.497220.492480.49248
batch fails iffSb≤49722S_b \le 49722Sb≤49248S_b \le 49248
per-batch failure qq0.0396>α=1/650.0396 > \alpha = 1/651.0⋅10−6≪α1.0 \cdot 10^{-6} \ll \alpha
expected failed batches10.310.32.6⋅10−42.6 \cdot 10^{-4}
P(bound holds)P(\text{bound holds})0.00740.00741−1.9⋅10−161 - 1.9 \cdot 10^{-16}

With 1.71.7, the bound holds far less often than the required 1−e−10≈0.999951 - e^{-10} \approx 0.99995, confirming the counterexample. With 4.74.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 BB 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)\mu/(n+1), is negligible compared with the statistical fluctuations of order σ/n\sigma/\sqrt{n}, so for large nn each member is optimistic with probability only about 1/21/2. High-probability optimism comes from the quantile over BB 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 pp close to one, a sample of nn ones gives a sample mean of 1>p1 > p, while the pseudocount gives n/(n+1)≤pn/(n+1) \le p for all n≤p/(1−p)n \le 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.

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 E[μ^b]<μ\mathbb{E}[\hat{\mu}^b] < \mu. However, a downward bias of μ/(nb+1)\mu/(n_b+1) 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 μ\mu, with constant probability. The quantile over independent batches then boosts this to probability 1−δ1-\delta. Consider Bernoulli$(p)$ samples and the plain sample mean Xˉn\bar{X}_n of a batch with n≥1n \ge 1 samples, without the pseudo-count. Then Xˉn≤p\bar{X}_n \le p exactly when the number of zeros, distributed as Bin(n,1−p)\mathrm{Bin}(n, 1-p), is at least its mean n(1−p)n(1-p). There are two phases:

  • Burn-in, n≤1/(1−p)n \le 1/(1-p). The plain mean is optimistic only if at least one zero was observed, which happens with probability 1−pn1 - p^n, between 1−p1-p and n(1−p)n(1-p). For fixed nn and pp close to 11, this is arbitrarily small. For example, Xˉ1=1>p\bar{X}_1 = 1 > p with probability pp.
  • After burn-in, n>1/(1−p)n > 1/(1-p). A binomial is at least its mean with probability greater than 1/41/4 once its mean exceeds 11 (Greenberg & Mohri, 2014). So the plain mean is optimistic with probability greater than 1/41/4, and the pseudo-count is no longer needed.

Hence, the plain mean is optimistic with probability at least min⁡{1−p,1/4}\min\{1-p, 1/4\} for every nn. For p≤12/13p \le 12/13, this is at least 1/131/13 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 1/21/2. More generally, for any fixed distribution with finite variance this probability tends to 1/21/2, 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., 1/(1−p)1/(1-p) 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 1/131/13 for every nn and every nonnegative distribution. Its only cost is an additive μ/(∣Db∣+1)\mu/(|\mathcal{D}^b|+1) in the bias of each batch, which turns the 8R8R term from Freedman's inequality into the 9R9R 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.

Reviewer_RRk2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers the ensemble technique to promote exploration in reinforcement learning, as a substitute for the classical exploration bonus with uncertainty quantification. The idea is to train multiple neural networks for Q values, independently, and then aggregate the Q values using quantiles of means. The result shows that in a finite tabular MDP, the regret compared to the bellman maximum, has a squared root dependency on the problem complexity (the maximum conditional variance) and the worst-case problem-dependent parameters, plus a linear dependency on the problem dependent parameter. The paper also examines the algorithm in numerical experiments, though in Appendix.

Critical strengths
  1. The ensemble framework is appealing for exploration promotion in RL, and thus the steps the authors take are meaningful steps.

  2. The authors seem to provide the relatively new result for the guarantee of ensemble methods, though the reviewer has certain concerns below.

Critical weaknesses
  1. One of the biggest concerns is that while the paper claims the guarantee reveals a logarithmic dependency on the ensemble size, the reviewer has been trying to find this term in Theorem 4. However it does not seem to show such effect of ensemble size; in fact, there appears no formal definition of ensemble size or a dependency on it. This is very critical for the paper's claim.

  2. The paper seems to have several over claims. First, the technical novelty of both the method and analysis is limited. Ensemble and the required techniques seem to be well developed, and the analysis relies heavily on many existing results. It is unclear what is the fundamental novelty that the authors would like to bring to the table. The authors clearly acknowledge that the analysis is direct and simple, but this may not be a valid justification for the novelty/originality. Second, the extension to heavy tailed is not supported by its accompanying results. The key lemma for this extension, Lemma 1, clearly assumes finite variance. For heavy tailed distirbutions, we may not have this nice property which is also why heavy tailed distributions by themselves are hard problems. Also, if such extension is claimed as a contribution, it may be more proper to have a formal statement and proofs.

Questions for authors
  1. What is the notation of the ensemble size, and what is the dependency of the regret on it?

  2. In all the high probability statements, what is the choice of δ\delta?

  3. Does the extension to heavy tailed distributions require finite variance?

  4. What is the dominating term in Theorem 4?

  5. What is the computational complexity of the method?

2 comments

We thank the reviewer for the feedback. The main concern is the ensemble size, which we clarify first.

Ensemble size (W1, Q1). The ensemble size is BB, the input of Algorithm 1 (see Section 4, paragraph before Algorithm 1). Our claim is not that the regret is logarithmic in BB, but that BB itself only needs to be logarithmic in the problem parameters: Theorem 4 sets B=⌈26log⁡(5SAHK/δ)⌉B = \lceil 26 \log(5SAHK/\delta) \rceil, which suffices for minimax-optimal regret. For general BB, the leading regret term scales as B\sqrt{B}, so the smallest admissible BB is best.

Novelty (W2). This is the first proof that a pure ensemble mechanism, with no bonuses or posterior, attains minimax-optimal regret in MDPs. The key ingredients are: (i) QoM gives optimism for any nonnegative distribution using only Feige's first-moment inequality, whereas prior ensemble analyses required symmetric or Bernoulli rewards; and (ii) optimism is needed only at the fixed V⋆V^\star, which avoids covering arguments and keeps BB logarithmic rather than linear in SS. The simplicity of the analysis is a result of this mechanism, and we see it as a strength.

Heavy tails (W2, Q3). Thank you; we renamed Appendix B to "Extension to Unbounded Losses", since it assumes finite variance. For finite (1+ε)(1+\varepsilon)-th moments, Appendix C.3 shows for bandits that replacing Freedman's inequality in Lemma 1 with a standard moment bound (von Bahr–Esseen and Markov inequalities) gives the optimal O~(K1/(1+ε))\tilde{O}(K^{1/(1+\varepsilon)}) rate, with the same algorithm and parameters.

Choice of δ\delta (Q2). The standard confidence parameter: all results hold with probability 1−δ1-\delta for any δ∈(0,1)\delta \in (0,1). Experiments use δ=0.05\delta = 0.05.

Dominating term (Q4). The first term, which grows as K\sqrt{K}. In the worst case it is O~(H3SAK)\tilde{O}(\sqrt{H^3SAK}), matching the minimax lower bound. The second term is a burn-in term independent of KK up to logarithmic factors.

Computational complexity (Q5). O(S2AHB)O(S^2AHB) per episode, a factor BB over value iteration, and parallelizable across members (see Section 4, paragraph before Algorithm 1).

The rebuttal period is nearing its end.

Has our response addressed your concerns?

If so, please consider raising your score.

Otherwise, we would be happy to provide additional clarifications and/or receive additional feedback that would help improve the paper.

Reviewer_u5tvOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies episodic tabular RL with unknown transitions and nonnegative losses: horizon HH, SS states, AA actions, and a fixed budget of KK episodes. Total loss is almost surely bounded by HH. QoM selects a low order statistic of disjoint batch means smoothed with a zero-loss pseudocount. VIBE applies QoM to Bellman targets, inducing optimism without explicit confidence bonuses or empirical variance calculations. For regret, the worst-case leading term matches the advertised minimax rate up to logarithms. The paper also gives an improved logarithmic bandit bound and finite-variance extensions.

Principal contribution. Smoothed, nonposterior low-quantile optimism combined with an episodic tabular regret analysis. The estimator needs neither symmetry nor a parametric prior. Experiments provide small tabular demonstrations.

Critical strengths

This paper proposes an algorithm with low-quantile optimism combined with an episodic tabular regret analysis. The idea of QoM applied to RL sounds interesting.

Critical weaknesses
  • Variance guarantees are not equivalent. The paper's sum of stagewise variance maxima can be substantially larger than the variance measure in Zhou et al. on compatible instances. Claims of the “same” variance guarantee or corresponding refined optimality are therefore overstated. This does not refute the worst-case leading-rate claim or establish worse actual regret. Location: pp. 2–3 and 6; Eq. (4), p. 5.
  • Missing stronger published benchmark. Zhang, Chen, Lee, and Du (COLT 2024) is uncited. Their Theorem 4 gives O~(min⁡{SAHKν+SAH2,HK})\widetilde O(\min\{\sqrt{SAHK\nu}+SAH^2,HK\}), with ν≤Q∗\nu\leq\mathcal Q^* on the common subclass of per-step losses in [0,1][0,1]. The additive term is smaller by a factor HSHS; their Theorem 1 also removes worst-case burn-in. QoM acknowledges deprioritizing burn-in but should quantify this gap. An MVP baseline appears in the plots; correspondence to the specific 2024 variant is undocumented. Location: pp. 2–3, 5–6, 10–12, 20.

Due to those prior works and better guarantees, the authors need more justification for the advantage of QoM.

Questions for authors

Mathematical correctness

  • M-01 — Incorrect concentration constants. Lemma 14's optimized martingale bound omits a square-root logarithmic factor.
  • M-02 — Leading-constant mismatch (minor; confirmed). The coefficient 22 in Theorem 4 does not follow from the final optimization in its proof.
  • M-03 — Missing scale condition. Appendix C's unrestricted nonnegative finite-variance bandit extension omits a necessary mean/loss-scale qualification. Location: p. 18, lines 929–931, following Theorem 16's statement.
  • M-04 — Unsupported uniform-value implication. The initial-state expected-total-loss bound does not justify uniform statewise value bounds in the claimed unchanged proof. Location: Appendix B, p. 17.
  • M-05 — Boundary and notation cleanup. Correct zero-mean strictness, the zero-quantile endpoint, batch-count rounding, zero-count conventions, tied-optimum notation, and indexing. Location: Corollary 2, p. 4; Eq. (1), p. 3; Algorithm 1, p. 6; Lemma 9, p. 15; Appendix C, pp. 17–18.

Code and algorithm correspondence

  • C-01 — The inspected learner differs from Algorithm 1. The runner selects SparseVIBE, whose batch statistics pool observations across stages, although Algorithm 1 keeps batches separately for each state-action-stage tuple. The implementation also uses NumPy's interpolated quantile instead of the specified order statistic.
  • C-02 — “Theoretical” ensemble size is inconsistent. Theorem 4 prescribes 26log⁡(5SAHK/δ)26\log(5SAHK/\delta), whereas the code and experimental description use 26log⁡(2SHK/δ)26\log(2SHK/\delta).
5 comments

We thank the reviewer for the careful review, and especially for catching several small but important mathematical issues, all of which are fixed in the revised PDF.

Both weaknesses concern how tight our bounds are compared with the sharpest bonus-based results. We want to clarify the goal of the paper. Our aim is not to improve the best bonus-based bounds. It is to show that the bonus-free ensemble mechanism used in practice provably achieves the minimax-optimal leading rate with a logarithmic number of members, and without bonuses, posteriors, variance estimates, or distributional assumptions. No prior ensemble method has such a guarantee, even in tabular MDPs. This mechanism is the advantage of QoM. We deliberately kept the analysis simple so this point stays clear, rather than chasing refinements that would complicate it. That said, we agree that some of our wording overstated the comparison, and we have revised it.

W1 (variance measure). Agreed: Q⋆\mathbb{Q}^\star is a stage-wise maximum, matching Zanette & Brunskill (2019), and can be larger than the measures of Zhou et al. (2023). We revised the wording accordingly and now state this comparison explicitly in the related work.

W2 (Zhang et al., 2024). Thank you for the pointer; we added it to the related work. Our lower-order term matches UCBVI (Azar et al., 2017), and improving it is beyond our scope.

M-01. Corrected. Lemma 1 applies Lemma 14 at a fixed per-batch confidence level that does not depend on any problem parameter, so the missing factor only changes numerical constants. No rate changes.

M-02. Corrected.

M-03. Thank you. Without a [0,1][0,1] bound, the pseudocount contributes a lower-order term that scales with the mean loss ℓ(a)\ell(a). We made this explicit in a short remark (Appendix C.3), which also notes that replacing Freedman's inequality in Lemma 1 with a standard moment bound (von Bahr–Esseen and Markov inequalities) extends Theorem 16 to finite (1+ε)(1+\varepsilon)-th moments. The algorithm, its parameters, and the rest of the proof are unchanged.

M-04. Thank you. The revised Appendix B now requires the expected-loss bound conditioned on any starting state-action pair, which gives Vhπ(s)≤HV_h^\pi(s) \le H uniformly over states. We also clarified that this extension targets finite-variance losses.

M-05. Fixed: α∈(0,1]\alpha \in (0,1], Corollary 2 for μ=0\mu = 0, integer BB, zero counts, tie-breaking, tied optima, and indexing. None of these affect the algorithm or the results.

C-01. SparseVIBE is equivalent to the dense VIBE implementation in our code. It is purely a computational speedup that stores and backs up only observed next states, which helps when each state-action pair has few possible next states. Both implementations differ from Algorithm 1 in two minor ways. First, all benchmark MDPs are time-homogeneous, so samples are pooled across steps hh, the same convention used by all baselines in Lee & Oh (2025). Second, the quantile uses NumPy's default interpolation instead of the exact order statistic, which has a negligible effect. We will clarify both points in Appendix D.

C-02. Thank you; we re-ran the experiments with the exact BB from Theorem 4 (see revised Appendix D). There is no noticeable change for the 1/e1/e configuration and only minor changes for the theoretical configuration, with all conclusions unchanged. Notably, Feige's 1/e1/e conjecture was recently proven in concurrent preprints (Fu et al., 2026; Nie & Wei, 2026), providing theoretical backing for the smaller ensemble size in our experiments.

Reviewer_u5tvOpenReview ↗

Reply to authors

Thank you to the authors for responding to my comments. The authors addressed all my concerns except the non-equivalent variance dependence. Regarding the variance dependence, the abstract and "TL;DR" still claim "optimal variance-dependent regret". I also suggest revising them.

The theoretical analysis of QoM will definitely be an important research question, and the authors are moving forward. However, such variance-dependent suboptimality still leaves a significant gap. I would have given a rating of 2.75 if the system had allowed it, and the final version is similar to the current one. I can increase it to 3 if the authors can demonstrate further understanding of the variance dependence, e.g., by rigorously justifying an intrinsic limitation of QoM for tabular models or by improving the result to truly optimal dependence. The other issues, including the auxiliary terms, are minor for me.

Thank you for the follow-up. The refinement to the finer variance measures of Zhou et al. (2023) takes only a few lines of proof, so we added it as a new appendix (Refined Variance-Dependent Bounds); it matches their variance-dependent lower bound. It needs extra definitions and discussion, so we kept it out of the main text, which now points to it. We hope this addresses your remaining concern and that you will consider raising your score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.