- 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
-
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.
-
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 -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.
-
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 -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.
-
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 regression objectives per episode in signed mode and in absolute mode, independently of . 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:
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 : 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 , 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 (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
[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 rule | Last 100-episode return | Total runtime (s) |
|---|---|---|
| Uniform (episode-wise) | 4.139 ± 0.225 | 51.51 ± 0.42 |
| Uniform (stage-wise) | 4.112 ± 0.256 | 193.23 ± 1.63 |
| Max-over-ensemble | 4.076 ± 0.268 | 193.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 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 :
We clarify that we have not claimed that the overall computational or memory cost is independent of the ensemble size .
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 , and a feature dimension of , 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.
| Method | Last 100-episode return |
|---|---|
LSVI-UCB | 12.391 ± 1.755 |
LSVI-PHE | 15.292 ± 0.882 |
BooVI | 13.177 ± 0.869 |
OPT-RLSVI | 16.468 ± 0.558 |
LMC-LSVI | 14.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.
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. Each member has its own linear output head wj=(Wj,bj), giving Q~j(s,⋅)=Wjϕθ(s)+bj. 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 gj, which remains fixed and defines the regularizer ∣wj−gj∣22. Each collected transition (st,at,rt,st+1) also receives independent member-specific reward perturbations ξtjj∈[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, 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, 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 ℓ indexes transitions within the sampled segment and Vbootj is the member-specific continuation value. Signed mode uses Qj=Q~j, whereas absolute mode uses Qj=Q^j+∣Q~j−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=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) is the initial state-action pair of segment i. 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]) 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=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-LSVIwhile adapting its training procedure to neural networks.