acceptodds
Under review as a conference paper at ICLR 2027

Provably Efficient Ensemble Sampling for Reinforcement Learning

Abstract

Ensemble sampling offers a simple and practical approach to exploration in reinforcement learning (RL), yet establishing regret guarantees is challenging when persistent perturbations influence subsequent data collection. We propose an ensemble sampling framework with two variants that maintain persistently perturbed datasets, uniformly select one ensemble member per episode, and execute its greedy policy. By retaining historical perturbations and fitting only the selected member, the proposed variants avoid repeated noise resampling and iterative posterior sampling, offering a simple design amenable to deep RL. We establish regret guarantees for both variants in linear Markov decision processes (MDPs). The signed variant achieves a leading regret term of with ensemble members, matching the leading regret rate of a Thompson sampling-type method for linear MDPs while retaining perturbations across episodes. Here, is the feature dimension, the episode horizon, and the total number of interaction steps. The absolute variant improves this leading regret term to with only members, at the cost of an additional reference regression at each step. Our analysis handles the dependence between persistent perturbations and adaptively collected data by establishing stochastic optimism through joint perturbation control across steps for the signed variant and recursive ensemble-average optimism for the absolute variant. Experiments demonstrate that the proposed algorithms achieve performance competitive with existing baselines despite the simplicity of their ensemble sampling mechanism.

Primary area:
learning theory
Keywords:
Reinforcement learning, ensemble sampling, regret analysis

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_KNGVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether ensemble-based exploration can achieve provable guarantees when perturbations are retained and influence subsequent data collection. It proposes ES-LSVI, which maintains persistently perturbed datasets and uniformly selects one ensemble member per episode. The analyzed algorithm fits the selected member through backward value iteration and follows its greedy policy. The paper develops signed and absolute variants and establishes high-probability regret bounds in linear MDPs with known features. By changing the perturbation construction, the absolute variant achieves better dependence on the planning horizon and a smaller sufficient ensemble size, at the cost of an additional reference regression at each stage. The analysis addresses the dependence between persistent perturbations and adaptively collected data. Experiments cover a tabular RiverSwim setting and neural MinAtar implementations. The latter jointly update all ensemble heads, differing from the selected-member fitting used in the analyzed algorithm.

Critical strengths
  1. The question is well motivated by practical ensemble exploration. Retained perturbations have already influenced the interaction history, so fresh-noise arguments cannot simply be applied conditionally on that history. The paper explicitly addresses this dependence.

  2. The signed analysis provides a substantive extension to RL. Gated occupancy measures reduce the initial-state value difference to cumulative perturbations and regression errors across stages. Stacking the perturbations into a dHdH-dimensional process permits uniform control of history-dependent directions despite member-dependent Bellman targets. A constant fraction of optimistic members then suffices to control conditional expected regret under uniform selection.

  3. The absolute-mode analysis offers a useful alternative through ensemble-average optimism. Average absolute perturbations offset regression errors, and linearity and monotonicity of the transition operator propagate optimism through the Bellman recursion. This closes with stagewise dd-dimensional control, explaining the smaller sufficient ensemble size and exploration scale. The ensemble average is an analytical device; the algorithm need not explicitly average member predictions.

  4. The experiments include all five MinAtar games, five training seeds, and reported uncertainty. Table 4 defines the final-window aggregation. RiverSwim includes separate validation and evaluation seeds, several baselines, and an ensemble-size ablation. The authors appropriately acknowledge that the stronger linear guarantee of the absolute mode does not imply uniformly better neural performance.

Critical weaknesses

1 The neural implementation is insufficiently specified to assess its correspondence to Algorithm 1

Remark 1 explains that selected-member fitting is possible because each member's backward recursion uses its own continuation values. Appendix D, however, states that the MinAtar implementation replaces exact regression with minibatch gradient updates and jointly updates all ensemble heads (p. 40, lines 2156–2159). A common convolutional architecture does not establish whether the members share trainable parameters or how their targets and losses are organized.

The issue extends beyond runtime. The linear analysis permits dependence through the shared interaction history, but defines member-specific regressions under a fixed, known feature map. Shared trainable representations, cross-member targets, or coupled losses would introduce changes whose relation to that structure needs explanation. These possibilities are currently unresolved, rather than demonstrated flaws.

Joint computation alone does not establish a mismatch in the member-specific mechanism. For exact linear regressions, computing every member through its prescribed recursion would leave the selected member's prediction unchanged; the analysis already defines such values for all members. For neural training, however, independent parameterization alone does not establish equivalence between updating all heads and updating only the selected head: finite optimization, initialization, and update schedules also matter.

Please provide the actual signed and absolute losses or pseudocode, including parameter sharing between members and reference predictors, continuation targets, persistent perturbations, and the timing of parameter updates relative to interaction. The behavior-head selection rule and within-episode updates should also be stated explicitly.

The value-bounding rule deserves particular clarification. Eq. (1) applies a common affine transformation across members at each state-action pair, using the shared Gram matrix. The absolute proof uses this property to preserve average optimism. Ordinary per-head upper clipping does not generally preserve optimism of an ensemble average. If the neural implementation uses another rule, the paper should explain that change rather than imply that the same proof applies.

Until these details are supplied, the MinAtar results support the viability of a neural variant with persistent perturbations and episode-level uniform member selection, but do not establish which member-specific properties of Algorithm 1 it preserves. I am asking for a precise description of this variant, not a nonlinear regret theorem.

2 The efficiency evidence should distinguish regression counts from the full cost of the implemented algorithm

Algorithm 1 requires HH regression objectives per episode in signed mode and 2H2H in absolute mode, independently of mm. Figure 2 measures the jointly updated neural implementation, so it does not directly test the computational benefit of selected-member fitting.

Even in the linear setting, the objective counts do not determine the full cost difference. The paper gives:

w~k,hj=w^k,hj+Λk,h−1sk,hj.\widetilde{w}^{j}_{k,h} = \widehat{w}^{j}_{k,h} + \Lambda_{k,h}^{-1}s^{j}_{k,h}.

For a fixed member, the reference and perturbed regressions share the Gram matrix and continuation values. Their reward targets differ through the retained reward noise, and their regularization centers differ through the initial perturbation. They can nevertheless reuse matrix factorizations and common continuation-value computations. The absolute mode's additional work therefore need not equal an entirely independent second regression.

Conversely, selected-member fitting does not remove costs that grow with mm: all members' perturbations must still be generated and maintained, and the implementation must retain the data or statistics needed to reconstruct Bellman targets. Neural gradient updates and memory costs also matter.

Please report the hardware, timing scope, update budget, batch size, and baseline ensemble sizes for Figure 2, and explain which operations dominate the measured costs. Existing implementation details and logs should be the first source of evidence. If the paper claims an advantage in scaling with mm, a limited comparison across ensemble sizes or update schemes would help; otherwise, the claim should be restricted to competitive runtime for the reported neural configuration. A large new experiment is unnecessary.

3 The linear-algorithm experiment covers only a tabular specialization; configuration reporting remains incomplete

RiverSwim uses one-hot state-action features with d=∣S∣,∣A∣=24d=|\mathcal{S}|\\,|\mathcal{A}|=24 (p. 39, lines 2086–2087). This is a valid linear MDP, but its orthogonal features do not test generalization across state-action pairs through shared linear features. The directly relevant linear experiment is thus tabular, while the neural experiments use the incompletely specified variant discussed above.

A small synthetic linear MDP with shared, lower-dimensional features would provide a more direct test of the non-tabular setting. This is a moderate coverage limitation, not evidence against the theorem. Alternatively, the authors can explicitly acknowledge the scope of the current experiments; I would not make a new experiment a prerequisite for acceptance.

Tables 2 and 3 list candidate ranges but omit final task-specific and baseline configurations and important aspects of MinAtar model selection. Please state the selection criterion, search budget, validation seeds and their relation to the final evaluation seeds, along with the network and update settings needed to interpret performance and timing. The current reporting prevents assessment of comparable tuning resources; it does not establish that the comparison was unfair. These reporting issues carry less weight than the theoretical and implementation questions above.

Questions for authors

Q1. What are the exact MinAtar losses and update rules for signed and absolute modes? Please clarify parameter sharing, member-specific continuation targets, reference predictors, persistent perturbations, and the value-bounding rule. Is the behavior head selected uniformly once per episode, and when do its parameters change? Which differences from Algorithm 1 arise from parameter coupling or optimization schedules?

Q2. What is included in Figure 2's timings, and what hardware, update budgets, batch sizes, and ensemble sizes are used? How does the linear implementation reuse Gram-matrix factorizations and common target computations? Can existing logs clarify the full cost, or can the computational claim be narrowed to the measured configuration?

Q3. Can the paper explicitly acknowledge that RiverSwim tests a one-hot/tabular specialization? A small shared-feature linear example would strengthen the empirical connection, but a clear scope limitation is also an acceptable response.

Q4. Please provide the final configurations and MinAtar model-selection protocol, including tuning resources, validation/evaluation seed separation, and the network, update, and evaluation settings that affect the reported results. Existing configurations and logs should address most of this request.

6 comments

We sincerely thank the reviewer for the careful and constructive assessment of our work. We particularly appreciate the recognition of our theoretical contributions. In response, we provide additional implementation details and further clarification of our experimental setup and results.


[Neural implementation]

We thank the reviewer for the opportunity to elaborate on our neural implementation. The detailed implementation procedures are provided in Appendix D.2 of the revison. We summarize the key details below.

Our neural implementation preserves member-specific perturbations and Bellman targets while sharing a trainable feature extractor to stabilize representation learning. All ensemble members share a convolutional feature extractor followed by a 512-unit fully connected layer with ReLU, yielding ϕθ(s)∈R512\phi_\theta(s)\in\mathbb{R}^{512}. Each member has its own linear output head wj=(Wj,bj)w^j=(W^j,b^j), giving Q~j(s,⋅)=Wjϕθ(s)+bj\tilde Q^j(s,\cdot)=W^j\phi_\theta(s)+b^j. Replay transitions, sampled minibatches, and feature computation are shared, while output-head parameters and regression targets are member-specific.

Each perturbed head is initialized at an independently sampled Gaussian anchor gjg^j, which remains fixed and defines the regularizer ∣wj−gj∣22\\|w^j-g^j\\|_2^2. Each collected transition (st,at,rt,st+1)(s_t,a_t,r_t,s_{t+1}) also receives independent member-specific reward perturbations ξtjj∈[m]\\{\xi_t^j\\}_{j\in[m]}, which are stored in replay and reused whenever that transition is sampled.

In the absolute mode, each member additionally maintains a reference head w^j\hat w^j, initialized and regularized toward zero. The perturbed and reference predictions are fitted separately to TD targets using perturbed and unperturbed rewards, respectively, with the same member-specific continuation value. With discount factor γ=0.99\gamma=0.99, the three-step regression targets for a sampled segment without an episode are

\begin{align*} \tilde y_i^j = \sum_{\ell=0}^{2}\gamma^\ell \bigl(r_{i,\ell}+\xi_{i,\ell}^j\bigr) + \gamma^3 V_{\mathrm{boot}}^j(s_{i,3}) , \quad \hat y_i^j = \sum_{\ell=0}^{2}\gamma^\ell r_{i,\ell} + \gamma^3 V_{\mathrm{boot}}^j(s_{i,3}) \, , \end{align*} where ℓ\ell indexes transitions within the sampled segment and VbootjV_{\mathrm{boot}}^j is the member-specific continuation value. Signed mode uses Qj=Q~jQ^j=\tilde Q^j, whereas absolute mode uses Qj=Q^j+∣Q~j−Q^j∣Q^j=\hat Q^j+|\tilde Q^j-\hat Q^j| for action selection. In both modes, the value-bounding operator is the identity, so action values are not clipped.

For a minibatch of size B=32B=32, we define the regularized TD losses as \begin{align*} L_{\mathrm{pert}}^j = \frac{1}{B}\sum_{i=1}^{B} \left( \tilde Q^j(s_i,a_i) - \tilde y_i^j \right)^2 + \lambda \|w^j-g^j\|_2^2 \, , \qquad L_{\mathrm{ref}}^j = \frac{1}{B} \sum_{i=1}^{B} \left( \hat Q^j(s_i,a_i)-\hat y_i^j \right)^2 + \lambda \|\hat w^j\|_2^2, \end{align*} where (si,ai)(s_i,a_i) is the initial state-action pair of segment ii. The total objectives are \begin{equation*} \mathcal L_{\mathrm{signed}} = \sum_{j=1}^{m}L_{\mathrm{pert}}^j \, , \qquad \mathcal L_{\mathrm{absolute}} = \sum_{j=1}^{m} \left( L_{\mathrm{pert}}^j + L_{\mathrm{ref}}^j \right). \end{equation*} At each learning update, we perform a single Adam step to jointly update all output heads and the shared feature extractor using the following gradients: \begin{align*} & \text{(signed)} \quad G_\theta = \frac{1}{m}\nabla_\theta \mathcal L_{\mathrm{signed}}, \qquad G_{w^j} = \nabla_{w^j}L_{\mathrm{pert}}^j , , \\ & \text{(absolute)} \quad G_\theta = \frac{1}{2m}\nabla_\theta \mathcal L_{\mathrm{absolute}}, \qquad G_{w^j} = \nabla_{w^j}L_{\mathrm{pert}}^j, \qquad G_{\hat w^j} = \nabla_{\hat w^j}L_{\mathrm{ref}}^j , . \end{align*} At the beginning of each episode, we sample J∼Unif([m])J\sim\mathrm{Unif}([m]) and select greedy actions using the corresponding member throughout the episode. After initially collecting 32 transitions, we alternate between collecting 10 new transitions and performing one learning update with a replay minibatch of size B=32B=32. Thus, the selected member index remains fixed within an episode, although its parameters and the shared representation may change through interleaved gradient updates.

Overall, the neural implementation preserves the core ensemble sampling mechanism of Algorithm 1. For neural function approximation, we replace exact regression with joint minibatch TD updates using a shared trainable feature extractor and adopt identity value bounding. These implementation choices retain the central exploration principles of ES-LSVI while adapting its training procedure to neural networks.

[Efficiency evidence]

Computational benefit of selected-member fitting: Our runtime experiment in Figure 2 evaluates the practical computational cost of the neural implementation used in the performance experiments. Even with joint updates of all ensemble heads, this implementation achieves comparable or lower runtime than the evaluated baselines under the benchmark conditions. We have clarified this distinction in the revision.

To evaluate the computational benefit of selected-member fitting, we additionally conduct an ablation study on RiverSwim (Figure 7), comparing (i) episode-wise uniform selection, which randomly selects and fits one member for the entire episode; (ii) stage-wise uniform selection, which fits all members and randomly selects one at each stage; and (iii) max-over-ensemble selection, which fits all members and selects the one with the highest estimated initial-state value. We evaluate each rule over 20,000 episodes, reporting the average episodic return over the final 100 episodes and the total wall-clock runtime.

Ensemble selection ruleLast 100-episode returnTotal runtime (s)
Uniform (episode-wise)4.139 ± 0.22551.51 ± 0.42
Uniform (stage-wise)4.112 ± 0.256193.23 ± 1.63
Max-over-ensemble4.076 ± 0.268193.64 ± 4.10

The results show that episode-wise uniform selection achieves comparable learning performance while reducing runtime by approximately 73%. This supports the computational advantage of fitting only the selected member rather than all ensemble members. We refer the reviewer to Appendix D.1.1 (Figure 7) of the revised manuscript for further details.

Reference and perturbed regression in Linear MDPs: As already expressed in Algorithm 2, the linear case admits a closed-form computation of the perturbed estimate w~k,hj\tilde w^j_{k,h} without solving two independent regression problems. The reference and perturbed estimates share the same Gram matrix and continuation values, allowing common computations to be reused.

Cost depending on mm: We clarify that we have not claimed that the overall computational or memory cost is independent of the ensemble size mm. Rather, as explained in Remark 1, the key advantage of ES-LSVI is that uniform member selection allows value iteration to fit only the selected member, without computing and aggregating value estimates across the entire ensemble, as required by several existing ensemble-based methods (Liu et al., 2021; Bai et al., 2021; Cassel et al., 2024; Cassel and Rosenberg, 2026). While ensemble-wide aggregation necessarily requires computing value estimates for all members, our uniform selection mechanism permits a computationally efficient implementation based on fitting only the selected member. The ensemble-selection ablation in Figure 7 directly supports this advantage, demonstrating substantially lower runtime with comparable learning performance.


[Experimental setup and implementations]

We have revised Appendix D to provide additional details including the experimental settings, implementation, and hyperparameter selection procedures. Please refer to Appendix D of the revised manuscript for further details.


[Linear MDP experiments]

We constructed a valid synthetic linear MDP with shared, low-dimensional state-action features and conducted additional experiments in Appendix D.3 (Figure 9). The environment consists of 10 states, 4 actions, a horizon of H=30H=30, and a feature dimension of d=6d=6, allowing generalization across state-action pairs through shared features. We evaluate each algorithm over 2,000 episodes and report the average episodic return over the final 100 episodes.

MethodLast 100-episode return
LSVI-UCB12.391 ± 1.755
LSVI-PHE15.292 ± 0.882
BooVI13.177 ± 0.869
OPT-RLSVI16.468 ± 0.558
LMC-LSVI14.206 ± 1.059
ES-LSVI (signed)16.429 ± 0.501
ES-LSVI (absolute)16.499 ± 0.494

Both variants of ES-LSVI rapidly achieve near-optimal performance, remaining competitive with OPT-RLSVI and outperforming the other baselines. These results complement the RiverSwim experiments and demonstrate the effectiveness of ES-LSVI beyond the tabular specialization.

We sincerely thank the reviewer for the time and effort devoted to reviewing our paper. We hope that our rebuttal has adequately addressed the questions and concerns raised in the initial review and clarified the main contributions of our work. As the discussion period is approaching its end, we would be happy to address any remaining questions or concerns and will respond as promptly as possible. If our responses have sufficiently resolved the reviewer’s comments, we respectfully ask the reviewer to reconsider their assessment in light of the theoretical and empirical contributions of our work. Thank you again for your thoughtful feedback and consideration.

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

The paper presents an ensemble sampling approach for exploration in episodic RL. The proposed algorithm (ES-LSVI) maintains an ensemble of perturbed datasets, but in each episode only one member of the ensemble is uniformly sampled, fitted with LS, and used for interaction through its greedy policy. The datasets are all augmented by independently perturbing the generated reward and storing the collected transitions. Two variants are considered: signed and absolute. The signed variant directly uses the perturbed prediction to construct the Q-value estimates, whereas the absolute variant adds the magnitude of the deviation from a reference prediction, which requires an additional regression at each step. Regret bounds are derived for both variants in linear MDPs.

Critical strengths
  • The paper establishes regret bounds in linear MDPs but with perturbations retained across episodes. This requires new analysis machinery which is perhaps the main contribution of this work. The signed variant's regret matches the leading regret term of an existing TS method and the absolute variant has a tighter regret with improvement by a factor of H\sqrt{H} and reduces the ensemble size by a factor of HH at the cost of an additional reference regression at each step.

  • The proposed algorithms are relatively simple. They require only one ensemble member to be fitted per episode in the signed variant and avoids repeated noise resampling or iterative posterior sampling.

Critical weaknesses
  • Novelty seems limited: The algorithm is quite closely related to existing ensemble sampling methods that use randomized members in exploration. To my understanding, the main contribution is the theoretical analysis with persistent retained perturbations across episodes. This analysis is interesting but how much of it is new compared to ensemble sampling in linear bandits and standard regret analysis? It is important to clarify what is fundamentally new in the analysis. I am also unclear about whether there is a particular technical gap that the paper is seeking to close.

  • As shown in Table 1 of the appendix, the proposed variants do not appear to improve the best available regret rates for linear MDPs. In fact, several existing methods such as LSVI-UCB, LSVI-PHE, and LSVI-ASE have better dependence on the feature dimension and/or horizon. Also, apart from the leading regret term, there are additive terms that may not be small. Therefore, I am unclear about the advantage that the proposed algorithms offer in terms of theoretical guarantees compared to existing methods.

  • Even in terms of practical advantages, I understand that the proposed approach avoids some computational operations present in other ensemble sampling methods, but the experiments show comparable performance to existing methods rather than clear consistent improvements. The computational gains are modest. It is again unclear whether the proposed algorithms offer improvement in tradeoffs between regret, computation, performance etc. The approach seems to be another exploration mechanism without a clear advantage over existing alternatives.

  • The paper lacks ablation studies to support the core contribution of the paper on persistent perturbations, uniform ensemble selection, and ensemble size and their effect on performance and computational cost.

  • This is not an entirely ensemble sampling algorithm as claimed. Specifically, the value bounding operator in (1) uses an explicit uncertainty measure to balance between estimates of Q-values and optimistic values. Isn't this an explicit optimism mechanism? How much of the guarantees can then be attributed to ensemble sampling?

Questions for authors

Please see my comments and questions above.

5 comments

We sincerely thank the reviewer for the careful evaluation of our manuscript and for recognizing the soundness of our work and the theoretical contribution of our analysis with persistent perturbations. We address each comment in detail below.


[Technical novelty]

Our key technical contribution is establishing regret guarantees for persistent ensemble sampling in linear MDPs, with explicit sufficient perturbation scales and finite ensemble sizes. These guarantees require addressing technical challenges that are not resolved by existing linear bandit analyses or standard RL regret arguments, particularly the interaction between persistent perturbations, adaptively collected data, and member-specific Bellman recursion.

First, RL introduces data-dependent Bellman regression targets. Unlike linear bandits, which estimate a fixed reward parameter, our regression targets involve rh+Vk,h+1j(s′)r_h+V_{k,h+1}^j(s'), where the continuation value depends on the collected data and persistent perturbations. While data-dependent Bellman targets have been studied in Jin et al. (2020), our setting additionally requires controlling their interaction with persistent ensemble perturbations.

Moreover, because ES-LSVI uniformly selects one member for the entire episode, stage-wise optimism does not directly guarantee that the selected member has an optimistic initial-state value. To address this, our signed-mode analysis establishes a lower bound on each member's initial-state value through its cumulative perturbations across all HH stages. We then stack the stage-wise perturbations into a dHdH-dimensional process and apply the uniform exceedance guarantee of Janz et al. (2026) to show that a constant fraction of ensemble members are optimistic at the initial state, despite the dependence between persistent perturbations and adaptively collected data. Finally, a pairwise Bellman telescoping argument converts this stochastic optimism into a regret bound under uniform member selection.

Second, the absolute mode requires a different analysis based on ensemble-average optimism. A key challenge is that each member has its own continuation value, so the Bellman regression targets differ across ensemble members. We establish optimism of the ensemble-averaged value functions through backward induction, using the linearity and monotonicity of the transition operator to handle these member-specific continuation values. Unlike the signed analysis, this argument requires controlling perturbations separately at each stage rather than jointly across all HH stages, yielding a smaller sufficient ensemble size and an improved regret bound.

More broadly, extending established bandit exploration principles to RL has led to substantial theoretical developments across several lines of research. Representative examples include:

  • UCB: OFUL (Abbasi-Yadkori et al., 2011) → LSVI-UCB (Jin et al., COLT 2020)
  • TS: LinTS [R1] → OPT-RLSVI (Zanette et al., AISTATS 2020)
  • PHE: LinPHE [R2] → LSVI-PHE (Ishfaq et al., ICML 2021)
  • LMC: LMC-TS [R3] → LMC-LSVI (Ishfaq et al., ICLR 2024)
  • ES: LinES (Janz et al., 2026) → ES-LSVI (this work)

These developments illustrate that extending bandit exploration principles to RL is not a straightforward application of existing bandit analyses, but requires additional theoretical arguments to handle Bellman recursion and error propagation. Our work closes the corresponding theoretical gap for persistent ensemble sampling by establishing two distinct optimism guarantees under member-specific Bellman recursion and adaptive dependence on retained perturbations. We therefore believe that our results constitute a substantial theoretical contribution beyond a direct extension of linear bandit ensemble sampling.

References

  • [R1] Abeille & Lazaric. "Linear thompson sampling revisited." AISTATS 2017.
  • [R2] Kveton et al. "Perturbed-history exploration in stochastic linear bandits." UAI 2020.
  • [R3] Xu et al. "Langevin monte carlo for contextual bandits." ICML 2022.

[Theoretical advantages]

We would like to note that our theoretical contribution is to establish provable efficiency for a simple exploration mechanism not covered by existing guarantees, rather than to improve the best known regret bounds for linear MDPs. Specifically, LSVI-UCB relies on explicit confidence bonuses that can lead to overly conservative exploration (Ishfaq et al., 2021). LSVI-PHE repeatedly resamples perturbations for all historical rewards, so the number of perturbations generated at each update grows linearly with the episode index. LSVI-ASE requires iterative posterior approximation, with sufficient cumulative sampling complexity in its theoretical analysis scaling quadratically or cubically with the number of episodes, depending on the sampler. These limitations motivate the development of exploration methods that avoid conservative confidence bonuses and repeated or iterative sampling procedures.

In contrast, ES-LSVI retains historical perturbations and uniformly selects a single ensemble member per episode, without requiring explicit exploration bonuses, repeated perturbation resampling, ensemble-wide prediction aggregation, or iterative posterior sampling. We establish that finite ensembles of size O~(dH)\tilde O(dH) in signed mode and O~(d)\tilde O(d) in absolute mode suffice for sublinear regret. Furthermore, our absolute mode achieves a tighter regret bound with a smaller ensemble through a distinct ensemble-average optimism analysis. These results provide theoretical guarantees for an exploration mechanism that is not addressed by existing regret analyses.

Regarding the additive terms, they arise from controlling high-uncertainty state-action pairs through the value-bounding operator and do not grow polynomially with the interaction horizon TT. Thus, both variants retain O~(T)\tilde O(\sqrt T) regret for fixed dd and HH, with the absolute mode further reducing the additive term by a factor of HH.

Overall, our results demonstrate that a simple and practical exploration procedure can achieve provably efficient learning in linear MDPs, providing theoretical support for the computational simplicity of ES-LSVI.


[Practical advantages]

We emphasize that the practical simplicity and effectiveness of ensemble sampling have already been demonstrated in deep RL (Osband et al., 2016; 2018). Our primary contribution is to establish regret guarantees for this practically established exploration mechanism while preserving its simple design.

Beyond the theoretical contributions discussed above, our experiments demonstrate concrete advantages in both performance and computational efficiency. On Asterix, ES-LSVI (signed) achieves the highest mean return with the shortest running time, reducing runtime by approximately 12%, 27%, and 36% compared with Adam LMCDQN, Bootstrapped DQN, and NoisyNet DQN, respectively. ES-LSVI (absolute) also achieves the highest mean return on Seaquest, while both variants rapidly approach oracle performance on RiverSwim.

Furthermore, to directly examine the computational benefit of our ensemble selection mechanism, we conducted an additional ablation study on RiverSwim comparing episode-wise uniform selection with stage-wise uniform and max-over-ensemble selection, which we discuss in greater detail in our response to the following comment. The results show that episode-wise uniform selection achieves comparable learning performance while reducing runtime by approximately 73%, as it requires fitting only the selected member rather than all ensemble members. We also observe that ES-LSVI (signed) reduces runtime by 31.3% compared with LSVI-PHE while achieving faster learning on RiverSwim. These additional results are presented in Appendix D.1.1 of the revised manuscript.

Taken together, our results demonstrate that ES-LSVI combines the simplicity of ensemble sampling with provable regret guarantees, effective exploration, and practical computational efficiency.

[Ablation studies]

We have added three ablation studies on RiverSwim to examine the effects of persistent perturbations, ensemble selection rules, and ensemble size on learning performance and computational cost.

Effect of persistent perturbations: To examine the practical implications of persistent perturbations, we compare ES-LSVI (signed) with LSVI-PHE, which resamples historical perturbations at each episode, and an empirical-mean baseline that performs greedy action selection without randomized exploration. We evaluate each rule over 20,000 episodes, reporting the average episodic return over the final 100 episodes and the total wall-clock runtime.

MethodLast 100-episode returnTotal runtime (s)
ES-LSVI (signed)4.139 ± 0.22551.51 ± 0.42
LSVI-PHE3.529 ± 0.27674.95 ± 0.73
Empirical-mean0.200 ± 0.00016.79 ± 0.41

ES-LSVI rapidly approaches oracle performance, whereas the empirical-mean baseline fails to explore effectively. Moreover, ES-LSVI reduces runtime by 31.3% compared with LSVI-PHE while achieving faster learning. These results suggest a favorable exploration–computation trade-off when using persistent perturbations.

Effect of ensemble selection rules: To evaluate the effect of ensemble selection rules, we compare (i) episode-wise uniform selection, which randomly selects and fits one member for the entire episode; (ii) stage-wise uniform selection, which fits all members and randomly selects one at each stage; and (iii) max-over-ensemble selection, which fits all members and selects the one with the highest estimated initial-state value.

Ensemble selection ruleLast 100-episode returnTotal runtime (s)
Uniform (episode-wise)4.139 ± 0.22551.51 ± 0.42
Uniform (stage-wise)4.112 ± 0.256193.23 ± 1.63
Max-over-ensemble4.076 ± 0.268193.64 ± 4.10

Episode-wise uniform selection achieves comparable learning performance while reducing runtime by approximately 73%. This demonstrates the computational advantage of fitting only the selected member without requiring ensemble-wide value estimation or comparison.

Effect of ensemble size: To examine the sensitivity to ensemble size, we extend the learning performance comparison in Figure 5 by additionally measuring runtime for both signed and absolute modes with m∈2,4,8,16,32m\in\\{2,4,8,16,32\\}.

Modem = 2m = 4m = 8m = 16m = 32
Signed2.48 ± 0.032.54 ± 0.042.65 ± 0.022.86 ± 0.013.30 ± 0.02
Absolute3.18 ± 0.053.24 ± 0.043.40 ± 0.043.58 ± 0.063.95 ± 0.07

Increasing the ensemble size from m=2m=2 to m=32m=32 adds only 0.82 seconds in signed mode and 0.77 seconds in absolute mode, while maintaining comparable learning performance. These results indicate that ES-LSVI can maintain larger ensembles with relatively small additional computational cost in this setting.

These additional experiments provide further empirical evidence supporting the effectiveness and computational efficiency of ES-LSVI. We appreciate the reviewer's suggestion, which has helped us strengthen the experimental evaluation. Detailed results are provided in Appendix D.1.1 of the revised manuscript.


[Value-bounding operator]

We would like to clarify that the value-bounding operator in Eq. (1) is primarily used to control error propagation through Bellman recursion, following prior randomized RL literature (Zanette et al., 2020; Wu and Sun, 2024), rather than to establish optimism. It prevents extreme value estimates from propagating across stages by preserving perturbed Q-values in low-uncertainty regions and applying an optimistic default in high-uncertainty regions.

In our regret analysis, the contribution from high-uncertainty regions is controlled by an additive term that does not grow polynomially with the number of episodes (see Lemma 7 and the proof of Theorem 2). The key stochastic optimism guarantees are established through persistent ensemble perturbations: a constant fraction of members are optimistic at the initial state in signed mode, while the ensemble-averaged value functions are optimistic in absolute mode. Thus, the value-bounding operator controls Bellman error propagation, whereas persistent ensemble perturbations provide the stochastic optimism central to our regret analysis.

Moreover, our MinAtar experiments use the identity value-bounding operator and still achieve competitive performance. These results further support the practical effectiveness of ensemble sampling without explicit value bounding.

Reviewer_bEjQOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies whether a finite ensemble with persistent perturbations and uniform member selection can provide efficient exploration in episodic reinforcement learning. The proposed ES-LSVI framework selects one member at the beginning of each episode and follows its greedy policy throughout that episode. Historical perturbations are retained rather than regenerated, and the theoretical algorithm fits only the selected member.

For linear MDPs, the signed variant achieves high-probability regret O~(d2H2T+d4H5)\widetilde{O}(d^2H^2\sqrt{T}+d^4H^5) with O~(dH)\widetilde{O}(dH) ensemble members, where TT denotes the total number of interaction steps. The absolute variant uses an additional reference regression and achieves O~(d2H3/2T+d4H4)\widetilde{O}(d^2H^{3/2}\sqrt{T}+d^4H^4) with O~(d)\widetilde{O}(d) members. The signed analysis establishes that a constant fraction of members are optimistic at the initial state, while the absolute analysis establishes recursive optimism of the ensemble-average value. Experiments on RiverSwim and five MinAtar games show competitive performance, supplemented by ensemble-size comparisons and wall-clock measurements.

Critical strengths
  1. The paper establishes regret guarantees for a simple exploration mechanism with persistent perturbations and uniform episode-wise member selection. The dependence between perturbations and adaptively collected data is an obstacle and the analysis addresses it while also handling stage-wise continuation values and the use of one member throughout an episode. This is a meaningful extension of persistent-ensemble analysis to linear MDPs.

  2. The absolute variant provides a reasonable theoretical contribution. Its ensemble-average optimism argument reduces the sufficient ensemble size by a factor of H and improves the leading regret term by (\sqrt H), up to logarithmic factors, at the cost of an additional reference regression. The comparison identifies a useful trade-off between computation and the strength of the guarantee.

  3. RiverSwim examines the linear setting, while MinAtar tests a neural adaptation against relevant randomized-exploration baselines. The reported results support competitive performance and show that the theoretically stronger absolute variant does not necessarily perform better on every task. Ensemble-size comparisons and measured runtimes provide additional practical context.

Critical weaknesses
  1. I believe the main limitation is the incomplete specification of the neural implementation. Appendix D states that exact regression is replaced by minibatch updates and that all ensemble heads are updated jointly, but the neural counterparts of the initial perturbation, reference regression, absolute perturbation term, and value-bounding operator are not described with the same precision as the linear algorithm. This limits reproducibility and makes it difficult to determine exactly which parts of the theoretical construction are retained.

  2. The reported neural runtimes remain valid measurements of that implementation. However, because all heads are updated jointly, they should not be interpreted as demonstrating the "selected member only" fitting advantage of the theoretical algorithm.

Questions for authors
  1. How are the initial perturbation, reference regression, absolute perturbation term, and value-bounding operator implemented in the neural experiments? Please identify which components of Algorithm 1 are that are retained and modified

  2. Which parameters and computations are shared across neural ensemble heads, and which are maintained separately? This would help clarify the practical implementation and the interpretation of its computational cost.

  3. What is the MinAtar hyperparameter-selection protocol, including the selection metric, separation between tuning and evaluation seeds, and selection of baseline configurations? The corresponding separation is explicit for RiverSwim but less clear for MinAtar.

4 comments

We sincerely thank the reviewer for the careful and thoughtful evaluation of our manuscript and for recognizing the theoretical contributions, soundness, and empirical strengths of our work. We address each comment in detail below.


[Neural implementation]

We describe the implementation procedure below and refer the reviewer to Appendix D.2 of the revised manuscript for further details.

We share a trainable feature extractor across ensemble members to stabilize representation learning, while maintaining member-specific output heads and perturbations to preserve diversity in value estimates. All ensemble members share a convolutional feature extractor followed by a 512-unit fully connected layer with ReLU, yielding ϕθ(s)∈R512\phi_\theta(s)\in\mathbb{R}^{512}. Each member has its own linear output head wj=(Wj,bj)w^j=(W^j,b^j), giving Q~j(s,⋅)=Wjϕθ(s)+bj\tilde Q^j(s,\cdot)=W^j\phi_\theta(s)+b^j. Replay transitions, sampled minibatches, and feature computation are shared, while output-head parameters and regression targets are member-specific.

Each perturbed head is initialized at an independently sampled Gaussian anchor gjg^j, which remains fixed and defines the regularizer ∣wj−gj∣22\\|w^j-g^j\\|_2^2. Each collected transition (st,at,rt,st+1)(s_t,a_t,r_t,s_{t+1}) also receives independent member-specific reward perturbations ξtjj∈[m]\\{\xi_t^j\\}_{j\in[m]}, which are stored in replay and reused whenever that transition is sampled.

In the absolute mode, each member additionally maintains a reference head w^j\hat w^j, initialized and regularized toward zero. The perturbed and reference predictions are fitted separately to TD targets using perturbed and unperturbed rewards, respectively, with the same member-specific continuation value. With discount factor γ=0.99\gamma=0.99, the three-step regression targets for a sampled segment without an episode are \begin{align*} \tilde y_i^j = \sum_{\ell=0}^{2}\gamma^\ell \bigl(r_{i,\ell}+\xi_{i,\ell}^j\bigr) + \gamma^3 V_{\mathrm{boot}}^j(s_{i,3}) , \quad \hat y_i^j = \sum_{\ell=0}^{2}\gamma^\ell r_{i,\ell} + \gamma^3 V_{\mathrm{boot}}^j(s_{i,3}), \end{align*} where ℓ\ell indexes transitions within the sampled segment and VbootjV_{\mathrm{boot}}^j is the member-specific continuation value. Signed mode uses Qj=Q~jQ^j=\tilde Q^j, whereas absolute mode uses Qj=Q^j+∣Q~j−Q^j∣Q^j=\hat Q^j+|\tilde Q^j-\hat Q^j| for action selection. In both modes, the value-bounding operator is the identity, so action values are not clipped.

For a minibatch of size B=32B=32, we define the regularized TD losses as \begin{align*} L_{\mathrm{pert}}^j = \frac{1}{B} \sum_{i=1}^{B} \left( \tilde Q^j(s_i,a_i) - \tilde y_i^j \right)^2 + \lambda \|w^j-g^j\|_2^2 \, , \quad L_{\mathrm{ref}}^j = \frac{1}{B} \sum_{i=1}^{B} \left( \hat Q^j(s_i,a_i) - \hat y_i^j \right)^2 + \lambda \|\hat w^j\|_2^2, \end{align*} where (si,ai)(s_i,a_i) is the initial state-action pair of segment ii. The total objectives are \begin{equation*} \mathcal L_{\mathrm{signed}} = \sum_{j=1}^{m}L_{\mathrm{pert}}^j \, , \qquad \mathcal L_{\mathrm{absolute}} = \sum_{j=1}^{m} \left( L_{\mathrm{pert}}^j+L_{\mathrm{ref}}^j \right). \end{equation*} At each learning update, we perform a single Adam step to jointly update all output heads and the shared feature extractor using the following gradients: \begin{align*} & \text{(signed)} \quad G_\theta = \frac{1}{m} \nabla_\theta \mathcal L_{\mathrm{signed}}, \qquad G_{w^j} = \nabla_{w^j}L_{\mathrm{pert}}^j \, , \\ & \text{(absolute)} \quad G_\theta = \frac{1}{2m}\nabla_\theta \mathcal L_{\mathrm{absolute}}, \qquad G_{w^j} = \nabla_{w^j}L_{\mathrm{pert}}^j, \qquad G_{\hat w^j} = \nabla_{\hat w^j}L_{\mathrm{ref}}^j \, . \end{align*}

At the beginning of each episode, we sample J∼Unif([m])J\sim\mathrm{Unif}([m]) and select greedy actions using the corresponding member throughout the episode. After initially collecting 32 transitions, we alternate between collecting 10 new transitions and performing one learning update with a replay minibatch of size B=32B=32. Thus, the selected member index remains fixed within an episode, although its parameters and the shared representation may change through interleaved gradient updates.

Overall, the neural implementation preserves the core ensemble sampling mechanism of Algorithm 1, including fixed initial perturbations, persistent reward perturbations, member-specific Bellman targets, and uniform episode-wise member selection. For neural function approximation, we replace exact regression with joint minibatch TD updates using a shared trainable feature extractor and adopt identity value bounding. These implementation choices retain the central exploration principles of ES-LSVI while adapting its training procedure to neural networks.

[Runtime]

Our runtime experiment in Figure 2 evaluates the practical computational cost of the neural implementation used in the performance experiments. Even with joint updates of all ensemble heads, this implementation achieves comparable or lower runtime than the evaluated baselines under the benchmark conditions. We have clarified this distinction in the revision.

The computational advantage of fitting only the selected member is further examined in our additional ablation study on ensemble selection rules in RiverSwim. Specifically, we compare three selection rules: (i) episode-wise uniform selection, which randomly selects and fits one member for the entire episode; (ii) stage-wise uniform selection, which fits all members and randomly selects one at each stage; and (iii) max-over-ensemble selection, which fits all members and selects the one with the highest estimated initial-state value. Unlike episode-wise uniform selection, the latter two rules require fitting all ensemble members, allowing us to assess the computational benefit of selected-member-only fitting. We evaluate each rule over 20,000 episodes, reporting the average episodic return over the final 100 episodes and the total wall-clock runtime.

Ensemble selection ruleLast 100-episode returnTotal runtime (s)
Uniform (episode-wise)4.139 ± 0.22551.51 ± 0.42
Uniform (stage-wise)4.112 ± 0.256193.23 ± 1.63
Max-over-ensemble4.076 ± 0.268193.64 ± 4.10

The results show that episode-wise uniform selection achieves comparable learning performance while reducing runtime by approximately 73%. We refer the reviewer to Appendix D.1.1 (Figure 7) of the revised manuscript for further details.


[Hyperparameter-selection protocol]

For each MinAtar game and each ES-LSVI variant, we conduct a grid search over candidate combinations of the hyperparameter values listed in Table 3. We first train each candidate configuration for 100,000100{,}000 environment steps using two validation seeds. We score each configuration by averaging the mean episodic returns across all evaluation checkpoints within each seed and then across the two seeds. We subsequently train the selected configurations for five million environment steps using five random seeds.

We also tune the baselines separately for each game using the same validation scoring criterion. We tune the random-prior scale for Bootstrapped DQN, the initial noise standard deviation for NoisyNet DQN, the learning rate and Langevin noise scale for Adam LMCDQN, and the learning rate and feel-good coefficient for FG-ULMCDQN. The highest-scoring configuration is retained for each baseline. The final selected hyperparameter configurations for each MinAtar game and algorithm are reported in Appendix D of the revised manuscript.

We sincerely thank the reviewer for the time and effort devoted to reviewing our paper. We hope that our rebuttal has adequately addressed the questions and concerns raised in the initial review and clarified the main contributions of our work. As the discussion period is approaching its end, we would be happy to address any remaining questions or concerns and will respond as promptly as possible. If our responses have sufficiently resolved the reviewer’s comments, we respectfully ask the reviewer to reconsider their assessment in light of the theoretical and empirical contributions of our work. Thank you again for your thoughtful feedback and consideration.

Dear Reviewer bEjQ,

Thank you again for your valuable feedback. We have made every effort to respond thoughtfully to your comments and would greatly appreciate any further feedback on our responses. If you have any additional questions, we would be happy to address them. As the author–reviewer discussion period is ending soon, we would like to ensure that we have sufficient time to provide any additional clarification you may need. Thank you again for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Key contributions

We sincerely thank all reviewers for their time, careful evaluation, and constructive feedback. As the discussion period draws to a close, we would like to revisit the main contributions of our paper and summarize the additional evidence provided during the rebuttal.


[Provable efficiency for a practically established exploration principle]

We formalize a persistent ensemble sampling framework for reinforcement learning and identifies sufficient conditions on perturbation scales and ensemble size for provably efficient learning in linear MDPs. The proposed ES-LSVI retains historical perturbations, uniformly selects one member per episode, and fits only the selected member, preserving a simple exploration procedure without repeated perturbation resampling, ensemble-wide value aggregation, or iterative posterior sampling.

Establishing these guarantees requires handling the dependence between persistent perturbations and adaptively collected data, together with member-specific, data-dependent Bellman targets. Moreover, the existence of an optimistic member at each stage does not ensure that one member selected at the beginning of an episode has an optimistic initial-state value. Our signed-mode analysis addresses this by controlling each member’s cumulative perturbation contributions across the entire episode. Applying a uniform exceedance guarantee to the resulting joint perturbation process, we establish that a constant fraction of ensemble members are optimistic at the initial state despite adaptive data collection. Uniform member selection therefore retains a constant probability of optimism, which we combine with Bellman error control to establish the regret guarantee.

[A new absolute-perturbation mechanism with stronger guarantees]

Beyond analyzing signed perturbations, we introduce an absolute mode that constructs action values by adding the absolute deviation between perturbed and reference predictions to the reference estimate. Its analysis establishes recursive ensemble-average optimism despite member-specific continuation values. This mechanism improves the leading regret term of the signed mode from O~(d2H2T)\widetilde O(d^2H^2\sqrt T) to O~(d2H3/2T)\widetilde O(d^2H^{3/2}\sqrt T), while reducing the sufficient ensemble size from O~(dH)\widetilde O(dH) to O~(d)\widetilde O(d), at the cost of an additional reference regression. Thus, absolute mode offers both a distinct exploration construction and an improved trade-off between the regret guarantee and the required ensemble size.

[Additional evidence for effective exploration and computational efficiency]

During the rebuttal, we expanded the empirical evaluation with a synthetic linear MDP in which multiple state-action pairs share low-dimensional features. Both ES-LSVI variants rapidly achieve near-optimal performance, providing evidence that their favorable behavior extends beyond the tabular specialization of RiverSwim. These results complement the competitive performance of our neural adaptation on MinAtar games.

Following Reviewer 4j7d's suggestion, we also added ablations studies examining persistent perturbations, ensemble selection rules, and ensemble size. In the selection-rule comparison, episode-wise uniform selection achieves comparable returns with approximately 73% lower runtime than the evaluated stage-wise uniform and max-over-ensemble implementations that fit all members. These results strengthen the empirical support for the exploration–computation trade-off motivating ES-LSVI.


In summary, we believe that our work makes a substantive contribution by establishing rigorous guarantees for a practically established exploration principle, introducing a new absolute-perturbation mechanism with stronger guarantees, and supporting these advances with additional empirical evidence. We thank the reviewers again for the discussion, which has helped us sharpen the presentation and strengthen the experimental evaluation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.