acceptodds
Under review as a conference paper at ICLR 2027

Recommender regret for improving regularised RL estimation with bandits and MCTS

Abstract

Regularised reinforcement learning (RL) algorithms rely on estimators, like Monte Carlo tree search or one-step look-ahead, to provide policy, value, or Q-value estimates in training and inference. However, existing bandit-based estimation frameworks evaluate sampling efficiency, not the quality of estimates. To evaluate the quality of a recommendation (estimate), we define regulariser-aware recommender regrets, analysing their lower bounds, and proving that simple algorithms like uniform sampling can achieve these bounds. Finally, we unify bandit- and search-based target improvement under Recommender MCTS. Across synthetic trees, arcade games, and scientific discovery tasks, recommenders yield faster target convergence and superior downstream performance. Our experiments characterise for the first time the potential of regularised MCTS in scientific applications.

Primary area:
reinforcement learning
Keywords:
Bandits, reinforcement learning, sampling, recommendations, recommender regret, simple recommender regret, MCTS, planning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_v4JnOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper presents related but notably distinct objective from the usual bandit exploration called recommender regret. This objective accounts for regularization in a RL settings, and basically says, under an exploration budget on samples, what is the best way to utilize them so that the final RL estimate is as accurate as possible? They derived lower and upper bounds for recommender regret and arrived at the conclusion that simple uniform sampling is theoretically valid for this estimation objective. These ideas were experimentally validated with synthetic trees, arcade games and biological sequence design and shown that uniform sampling indeed does well then other adaptive approaches.

Critical strengths
  • Good range of experiments from different domains
    • Moderately positive contribution
  • The theory covers different types of common regularizers
    • Minor strength to overall assessment
Critical weaknesses
  • Unsure on the actual contribution as a new algorithm
    • Given that the most of the conclusion is that uniform sampling is good, I am unable to see much value here
  • Tree-depth complexity issues
    • E.g. for real-world biological cases, going beyond one-step look ahead can be a major issue
  • Difficult to understand theoretical results and paper in general
    • Major readability issues, making this hard for me to see true value but I will still give some credit for the unusual perspective of bandits
Questions for authors
  1. What's the main practical difference between this approach and a naive regularized MCTS with uniform exploration?
  2. Beyond the experiments, if you were given the data and opportunity to apply your approach, which domain would actually be practical and valuable?
  3. In the arcade experiment, why were the filters added to remove some games (e.g. saturated quickly, didn't improve with search)? Could an aggregated measure be shown?
3 comments

We thank the reviewer for their feedback, and are glad to hear that they found the framework novel and unique. It is immensely valuable for us to understand and address any concerns or issues raised about the paper. We are sorry to hear that the paper was difficult to understand, we tried our best to write clearly but are open to any and all suggestions as to how we could improve our academic writing. Be it general feedback on the writing style itself, or even particular critiques, this would be immensely helpful.

Onto the weaknesses and questions.

In response to W1 and Q1. Unclear contribution and differences with regularised MCTS with uniform sampling. You are absolutely correct to state that we don’t present a new algorithm: this is regularised MCTS with uniform sampling. Our goal in this paper is to provide insights on generating recommendations in regularised RL. Our most important contribution with respect to bandits, and MCTS more generally, is that for the specific recommendation problem we study, uniform sampling seems to be optimal (in a sense). This is a very surprising result, since prior work (https://arxiv.org/abs/2507.10797) showed that exploration was almost unnecessary for a related type of problem. By generalising prior works, we expand the literature on recommendation problems, and the methods for solving them efficiently. We hope that this has addressed your concern. In particular, we want to highlight that the value of our work is not in the algorithm, but in showing that the algorithm is useful and interesting, despite prior work suggesting that uniform sampling should not be necessary.

In response to Q2. Practical domains for recommendation problems. We see practical applications of these sorts of recommendation algorithms all over regularised RL. Take soft actor-critic (SAC). It trains a “critic” network by generating Q-value estimates, and taking a loss against them. Our work can directly plug into an algorithm like SAC, where a Q-value estimate can be generated with a bandit or MCTS problem. The faster and more accurately this estimate converges, the better. Additionally, in works like AlphaZero, MCTS is used to iteratively train a value function and a policy function. A similar approach can be taken with our work, as we have just demonstrated that for regularised RL value and policy functions, MCTS with uniform sampling is in a sense optimal.

We also provide a list of practical applications (other than biological sequence design) in which Regularised RL which we believe our approach could be applied to (and we find interesting): LLM Fine Tuning, as in https://arxiv.org/abs/2310.04363, https://arxiv.org/pdf/2203.02155, https://openreview.net/forum?id=PXD3FAVHJT Combinatorial optimization, as in https://proceedings.neurips.cc/paper_files/paper/2023/hash/27571b74d6cd650b8eb6cf1837953ae8-Abstract-Conference.html Healthcare: https://dl.acm.org/doi/abs/10.1145/3580305.3599800

We amended the Introduction to reflect these domain applications and better motivate our contribution (see changes in red).

In response to W2. Tree depth complexity issues. We do agree in general that in real-world systems, performing an “action” would not be possible, or at least it would be highly expensive. However, the implicit assumption of MCTS (and many RL problems in general) is that a simulator of the environment is available for us to use, hopefully cheaply. So while we agree that in the real world, this sort of search is totally untenable for certain problems, all we require is a simulator and the search algorithms would be achievable. Such is the case in many real-world settings today (like in drug discovery).

In response to Q3. Environment filtering in the arcade game experiments. We filtered the OCTAX games to a representative subset which was meant to show the performance of MCTS in games that actually benefited from MCTS. In particular, a number of OCTAX games can be beaten quite easily, so MCTS doesn’t make any difference. See Airplane and Flight Runner in Figures 16 and 17 for instance, which demonstrate that these games are already well-played by the no-search agent, and MCTS doesn’t improve performance. Other games seemed not to benefit from search at all (e.g., Squash, Tetris, and Tank), while others like Rocket and Pong saw improved performance, but more search sims did not further improve performance. Thus, we chose to limit the games presented in the main body to the ones that saw improved performance and scaled with search sims. Per the aggregated measure, we did not design these experiments to achieve state-of-the-art performance in OCTAX games, rather we wanted to show that regularised MCTS with uniform and E3W achieve high performance in the games, and that they are competitive with one another across the choice of regulariser. In fact, during this rebuttal period, we ran experiments to measure the time-per-step of each search algorithm, and demonstrated that uniform sampling achieved the fastest results. Thus, if any statement of optimality is to be made, we believe that it should be this: in the OCTAX and scientific discovery tasks, uniform sampling achieved similar or better rewards than E3W and UCT, while also requiring less execution time.

On clarity (Weakness 3): We have added some intuition below Assumption 1 (p.5) as well as below Theorem 3 (p. 5), and additional explanations in Appendix A.3, A.4 and B. We would be grateful for any specific feedback on clarity so as to incorporate it.

We kindly request that you increase your score if our responses have answered your questions and concerns. Thank you again for your questions!

Thank you for the explanation. While I now understand the paper better, I will still continue to keep my current score on the grounds of novelty.

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

This paper studies how to allocate samples in bandits and Monte Carlo Tree Search (MCTS) to estimate regularized RL targets (the optimal policy, value and Q-values). Rather than measuring the cumulative regret of the sampling policy during exploration, the authors frame target estimation as a recommendation problem after TT samples. They define "simple recommender regret'' using divergences matched to the regularizer Ω\Omega (primal norms and Bregman divergences for policies, absolute error for values, and dual norms for Q-values). The paper contributes both theoretical regret bounds and extensive experimental studies.

Critical strengths

The mian strength of the paper is its well-motivated problem formulation. Separating the quality of the final target estimate from the cumulative cost of the sampling policy is a clean, useful distinction for RL target estimation. The two-point Bretagnolle-Huber lower-bound proofs are well-structured, and the observation that the value lower bound is independent of the action-space size KK is a nice insight.

Another strong aspect is the large number of experiments and candid reporting. The appendices report cases where uniform sampling does not always win (e.g., value and norm-based policy errors), explain how unvisited arms are handled, flag incomplete seed runs, and show wall-clock compute costs. Although I have question about some of these aspects (see weaknesses and questions below), it improves trust and transparency.

Critical weaknesses

A major weakness is that the E3W exploration schedule is not clearly consistent across the paper. The main text defines E3W with λt=ϵlog⁡(t+1)\lambda_t = \frac{\epsilon}{\log(t+1)}, while the experimental appendices use different forms of the schedule. In the synthetic-tree experiments, the KK factor is removed, whereas the OCTAX and biology experiments use a KK-dependent schedule of the form λst=ϵKlog⁡(Nt(st)+2)\lambda_{s_t} = \frac{\epsilon K}{\log(N_t(s_t)+2)}. The paper explains that the KK-dependent schedule can exceed 1, motivating the modification in the synthetic experiments, but the resulting differences in exploration across experiments should nevertheless be clarified. This is particularly relevant because the action-space size KK varies substantially across the synthetic experiments, and the authors themselves note that the algorithms' dependence on KK is not perfectly captured by their theoretical analysis. Moreover, although the appendix discusses insensitivity to ϵ\epsilon, no systematic ϵ\epsilon sweep is shown. More importantly, unvisited arms are assigned zero Q-values when evaluating the Q-value error. The authors explicitly acknowledge that this creates constant regret on unvisited arms and discuss parent-value mixing as an alternative. This evaluation choice therefore makes it important to understand how much of the observed advantage of uniform sampling is affected by the treatment of unvisited actions.

Furthermore, the downstream improvements are not fully convincing and appear somewhat overstated. In OCTAX, only a representative subset of the 19 games is shown in the main text, and games that saturated quickly or did not benefit from search were filtered out, while the full set of results is deferred to the appendix. At high simulation budgets, E3W and uniform sampling perform similarly, while MCTS incurs substantial additional wall-clock cost. I would therefore like to see compute-matched comparisons rather than comparisons based only on the number of simulations.

In the scientific discovery experiments, the gains over the no-search baseline are also modest in some cases. In Table 3, the best method, TENTS-Uniform, is within one standard deviation of the no-search baseline on two of the three tasks (AMP: 10.64±0.1410.64 \pm 0.14 vs.\ 10.17±1.7610.17 \pm 1.76, GFP: 1.62±0.011.62 \pm 0.01 vs.\ 1.61±0.021.61 \pm 0.02). Several reported configurations have fewer than 5 completed seeds, and uniform sampling does not consistently dominate E3W at lower simulation budgets. Given the computational cost of the search, the practical significance of these improvements would benefit from a more systematic compute-matched analysis.

Questions for authors

Q1. The E3W exploration schedule appears to differ across the paper. Equation (3) uses λt=ϵlog⁡(t+1)\lambda_t = \frac{\epsilon}{\log(t+1)}, the synthetic-tree experiments use a schedule without the KK factor, while the OCTAX and biology experiments use a KK-dependent schedule. Could you clarify why these schedules differ across experiments? In particular, could you report whether the synthetic-tree conclusions are robust to a clipped schedule such as

min⁡(1,ϵKlog⁡(Nt(st)+2)),\min\left( 1,\frac{\epsilon K}{\log(N_t(s_t)+2)}\right),

with ϵ\epsilon tuned for each action-space size KK?

Q2. With 32 to 512 simulations and uniform sampling, only a limited portion of a tree with KK possible actions per state can be explored. What effective search depth (or fraction of the tree) is reached in OCTAX and the scientific discovery tasks, and how do the methods compare under a compute-matched wall-clock budget?

Q3. Theorem 5 assumes deterministic transitions and deterministic non-leaf rewards, whereas the synthetic-tree experiments use stochastic rewards, ri(s,a)∼N(μs,a,1)r_i(s,a) \sim \mathcal{N}(\mu_{s,a},1), at every visit. How should the theoretical guarantee be interpreted for these experiments? Conversely, in the OCTAX and scientific-discovery experiments, the practical noise assumptions are not clearly specified. How do the sampling noise and reward uncertainty in these experiments correspond to the sub-Gaussian assumptions used in the bandit theory?

5 comments

We thank you for your detailed review, it really means a lot that you gave constructive feedback! Thank you also for highlighting the insights we generate from our theoretical bounds, and the transparency of our writing. We sought to write an honest paper that directly stated the limitations of our work and are glad that this didn’t go unnoticed :). The following points address the comments and questions in your review, we hope that they address your concerns.

In response to Q1, W1. On the E3W exploration schedule differences. As you correctly note, a tree search algorithm may not be robust to exploration schedules that depend on K. We originally used the E3W formulation as stated in the paper (https://arxiv.org/abs/2007.00391), but found that when scaling K to large values in the synthetic tree experiments (specifically K=90), the E3W policy would become negative, leading to artificially poor performance for E3W. This was easily remedied by removing K from the exploration schedule. The reason we didn’t want to use a clipped schedule, as you propose, is that it would essentially default to uniform sampling until t>exp⁡(ϵ∗K)−1t > \exp(\epsilon * K) - 1 steps. Of course, this would not be a fair comparison of E3W and uniform sampling. However, such schedules are used by the authors of (https://arxiv.org/pdf/2404.07732) in their implementation, which may explain some of the performance improvements observed in that paper. We do not change the exploration schedule in the OCTAX and scientific discovery experiments because the action spaces are too small to make a significant difference in sampling: with ϵ=0.1,K=20\epsilon = 0.1, K=20, we only need six simulations to satisfy feasible convex combinations for E3W. In addition, the OCTAX environments have small action spaces (K < 10), so we do not believe this is a concern. To test this hypothesis, we re-ran the scientific discovery experiments with the K-independent E3W schedule. The following tables list the results.

AMP (K=23K=23), top-100 diverse reward. No-search baseline: 10.17 ± 1.76. UCT: 4.54 ± 1.71 (32 sims), 6.81 ± 0.20 (128 sims), 7.47 ± 0.68 (512 sims), 7.94 ± 1.45 (1024 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM6.10 ± 0.244.73 ± 0.326.70 ± 1.03
MENTS6.53 ± 0.215.90 ± 0.097.09 ± 0.84
RENTS7.24 ± 0.088.55 ± 1.467.57 ± 0.05
TENTS6.76 ± 0.095.74 ± 0.346.30 ± 0.26
128SMM5.91 ± 0.255.15 ± 0.405.90 ± 0.15
MENTS6.72 ± 0.186.40 ± 0.286.82 ± 0.23
RENTS6.91 ± 0.147.82 ± 0.046.34 ± 0.12
TENTS7.54 ± 0.535.80 ± 0.437.38 ± 0.83
512SMM6.48 ± 0.325.73 ± 0.167.23 ± 0.64
MENTS7.66 ± 0.457.02 ± 0.238.07 ± 0.84
RENTS7.40 ± 0.117.77 ± 0.057.06 ± 0.12
TENTS8.47 ± 0.806.91 ± 0.248.60 ± 0.29
1024SMM6.63 ± 0.236.07 ± 0.287.69 ± 0.74
MENTS8.56 ± 0.487.56 ± 0.389.13 ± 0.98
RENTS7.57 ± 0.107.71 ± 0.087.40 ± 0.10
TENTS9.49 ± 0.077.20 ± 0.2910.64 ± 0.14

UTR (K=7K=7), top-100 diverse reward. No-search baseline: 4.13 ± 0.02. UCT: 4.20 ± 0.02 (32 sims), 4.13 ± 0.03 (128 sims), 4.07 ± 0.03 (512 sims), 4.00 ± 0.05 (1024 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM3.29 ± 0.033.11 ± 0.013.49 ± 0.01
MENTS3.34 ± 0.023.09 ± 0.023.46 ± 0.02
RENTS4.03 ± 0.014.07 ± 0.014.15 ± 0.01
TENTS3.70 ± 0.023.11 ± 0.034.08 ± 0.02
128SMM3.37 ± 0.023.18 ± 0.033.56 ± 0.01
MENTS3.47 ± 0.033.16 ± 0.033.55 ± 0.02
RENTS4.08 ± 0.014.05 ± 0.014.22 ± 0.01
TENTS3.91 ± 0.023.29 ± 0.024.17 ± 0.02
512SMM3.44 ± 0.023.28 ± 0.013.63 ± 0.01
MENTS3.61 ± 0.013.29 ± 0.013.62 ± 0.02
RENTS4.11 ± 0.004.07 ± 0.014.24 ± 0.01
TENTS4.04 ± 0.023.52 ± 0.014.23 ± 0.01
1024SMM3.47 ± 0.023.29 ± 0.023.66 ± 0.01
MENTS3.65 ± 0.013.34 ± 0.013.65 ± 0.01
RENTS4.12 ± 0.014.10 ± 0.014.24 ± 0.01
TENTS4.09 ± 0.023.60 ± 0.014.25 ± 0.01

GFP (K=23K=23), top-100 diverse reward. No-search baseline: 1.61 ± 0.02. UCT: 1.61 ± 0.04 (32 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM1.53 ± 0.011.52 ± 0.021.53 ± 0.01
MENTS1.53 ± 0.011.52 ± 0.021.53 ± 0.01
RENTS1.58 ± 0.011.61 ± 0.011.60 ± 0.01
TENTS1.61 ± 0.001.53 ± 0.011.62 ± 0.01

In these tables, the K-independent λtλ_t makes E3W worse. It loses to uniform selection everywhere for SMM, MENTS and TENTS, and only RENTS holds up. We have updated Table 3 in the paper to reflect this change as well as a discussion on the choice of schedule in Section 5. Thank you for noticing this!

In response to Q2: effective search depth and compute-matched comparison. This is a very interesting point that we hadn't considered. UCT is "greedier" than the regularised search algorithms, so we expect it to search deeper in pursuit of a single optimal trajectory. E3W sits in between: it mixes a "greedy" component, which samples from the regularised policy, with a uniform component, so we expect it to search deeper than uniform action selection. To test this, and to address compute matching, we ran additional experiments measuring the search depth and the wall-clock time per search step of every method on the three scientific discovery tasks (AMP, UTR, GFP) and on the four OCTAX environments in the main body (Brix, Filter, Submarine, Worm). Each configuration was run on a batch of 100 sequences/environments for 10 search steps on a single Quadro RTX 8000 GPU, at 32 and 128 simulations. The tables below report the time per search step, the maximum tree depth (averaged over steps) and the average depth at which a simulation ends.

Sequence design: search time and depth. Setup: ω=4\omega=4, depth cap 9, batch of 100 sequences, 10 search steps, Quadro RTX 8000. max: deepest node in the tree, averaged over steps. avg: average depth at which a simulation ends. Uniform and E3W entries are averaged over the four regularised algorithms (SMM, MENTS, RENTS, TENTS); UCT is a single configuration.

Task (KK)SimsMethodTime / step (s)maxavg
AMP (23)32Uniform0.402.31.5
E3W1.058.64.9
UCT1.008.77.5
128Uniform1.883.02.0
E3W4.969.05.7
UCT4.658.77.6
UTR (7)32Uniform0.454.02.4
E3W0.878.95.9
UCT0.759.05.8
128Uniform2.315.23.3
E3W3.949.06.9
UCT3.799.07.1
GFP (23)32Uniform2.942.31.5
E3W4.574.52.6
UCT7.829.07.9

OCTAX games: search time and depth. Setup: ω=5\omega=5, depth cap 10, batch of 100 environments, 10 search steps, Quadro RTX 8000. max: deepest node in the tree, averaged over steps. avg: average depth at which a simulation ends. Uniform and E3W entries are averaged over the four regularised algorithms (SMM, MENTS, RENTS, TENTS); UCT is a single configuration.

Game (KK)SimsMethodTime / step (s)maxavg
Submarine (2)32Uniform1.165.93.6
E3W1.539.46.5
UCT1.639.15.9
128Uniform6.728.45.4
E3W8.5210.08.3
UCT8.569.98.1
Brix (3)32Uniform1.054.52.8
E3W1.466.23.6
UCT1.566.83.7
128Uniform5.166.23.9
E3W8.398.25.2
UCT8.489.76.1
Filter (3)32Uniform1.044.42.7
E3W1.539.96.4
UCT1.589.64.5
128Uniform5.156.23.9
E3W7.268.65.2
UCT8.5810.07.1
Worm (5)32Uniform0.953.52.2
E3W1.104.52.6
UCT1.123.72.5
128Uniform4.184.83.0
E3W5.556.13.6
UCT5.504.73.4

Depth. Uniform action selection produces wide but shallow trees, whereas E3W and UCT concentrate their simulations and search considerably deeper. On AMP and UTR (depth cap 9), uniform selection reaches a maximum depth of 2.3–5.2, while E3W and UCT reach 8.6–9.0. On OCTAX (depth cap 10), E3W reaches 9.4–10.0 on Submarine and Filter, and searches deeper than uniform in every setting except Worm at 32 simulations, where the two are close. Uniform's shallowness follows from spreading visits evenly over all K children, so with 32–128 simulations the tree cannot grow much beyond log⁡K\log K of the budget, especially for large action spaces such as AMP and GFP (K=23K=23).

Compute. Since MCTS is used only at inference time, and all methods are JAX-compiled through the MCTX library, the methods differ in wall-clock cost only through the trees they build. Deeper trees cost more per step: uniform selection is the cheapest in every setting we tested, between 1.2× and 2.6× faster per step than E3W and UCT. As a result, comparing at equal numbers of simulations does not disadvantage uniform selection. On the scientific discovery tasks, uniform selection matches or exceeds E3W at equal simulations for most regularisers, so it is at least as good at equal wall-clock time. We have added a discussion of these results to Section 5.4. Thank you for suggesting this.

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

A theoretical paper on regularization in MCTS with applications to trees, games and biological sequence design.

Critical strengths
  • A theoretically well funded paper
  • Good empirical results on important problems such as biological sequence design
  • Both a theoretical and experimental paper
Critical weaknesses
  • The theoretical part is difficult to read
Questions for authors

This is surprising that uniform sampling is the best algorithm in combination with MCTS for biological sequence design. I would suppose that a learned policy works better. Do you have a simple explanation of the better performance of uniform sampling ?

1 comment

Thank you for your question and for reviewing our paper! In reply to Q1, we also found it surprising that uniform sampling could outperform greedy sampling in scientific discovery tasks. As for a simple explanation, we think the intuition of our paper is important here: uniform sampling is better at estimating regularised RL policies than greedy sampling. Since the scientific discovery experiments rely on estimating regularised RL policies, uniform sampling is the natural choice to achieve higher performance.

As for clarity (Weakness 1), we have added some intuition below Assumption 1 (p.5), under Theorem 3 (p. 5), and additional explanations in Appendix A.3, A.4 and B.,

Thanks again for your question, please do ask more if you have any further concerns, or specific hints as to what was difficult to understand. We kindly ask that you increase your score if we have satisfied your concerns.

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

This paper studies the allocation of sampling budgets for estimating regularized optimal policies, values, and action values. It introduces a unified notion of recommender regret, with losses chosen to reflect the geometry of the regularizer and the target being estimated. The paper presents lower and upper bounds for bandit recommendations and extends the analysis to regularized MCTS.

A central practical finding is that uniform sampling can be an effective allocation strategy for recommendation quality. The evaluation compares uniform sampling with E3W across several regularized backup operators, using synthetic trees, 19 OCTAX games, and three biological sequence-design benchmarks. Together, the formulation, theoretical analysis, and experiments provide a useful perspective on how sampling allocation affects the quality of targets used in regularized RL and planning.

Critical strengths
  1. The broader treatment of recommendation targets is an original and meaningful extension of the closest works examined. Xiao et al. study softmax value estimation under a different loss; Dam et al. develop regularized tree search; and Pedramfar and Ravanbakhsh analyze distribution-matching regrets in the entropy setting. This paper brings policy, value, and Q-value estimation into a common framework with regularizer-dependent losses. I consider this broader formulation and its accompanying analysis a substantive contribution. The proofs build on established concentration, change-of-measure, and convex-duality techniques, so their methodology is not entirely new. Nevertheless, the formulation and combined treatment offer useful additional understanding. Their potential impact is significant because they provide a common basis for evaluating and designing sampling allocation for several targets used in regularized RL.

  2. The empirical investigation gives the framework practical relevance. Comparing uniform sampling and E3W within multiple backup operators directly examines the role of allocation, while the synthetic experiments expose differences between policy, value, and Q-value errors. The OCTAX and sequence-design studies extend the evaluation beyond controlled estimation problems. In particular, the results suggest that simple allocation rules can be competitive and sometimes advantageous when combined with regularized search. The diversity-aware sequence-design evaluation is a valuable application, and the combination of theoretical motivation and broad empirical testing supports acceptance.

Critical weaknesses
  1. Several theoretical claims need a more precise scope. Theorem 3 requires additional conditions ensuring that the perturbed instances used in the proof belong to the target set Q. Assumption 1 alone does not provide this: a singleton target set can satisfy the assumption, while the stated lower bound can exceed the maximum possible policy error as the noise parameter increases. The authors should specify an appropriate richness or radius condition and the corresponding horizon/noise regime.

The optimality statements also need qualification. Maximizing the minimum sampling probability minimizes the derived upper bound, but this does not by itself establish minimax optimality for MCTS or the necessity of E3W's logarithmic penalty. I view these as important, potentially repairable limitations on the strongest statements. My positive assessment rests on the broader framework, its analysis within a correctly specified scope, and the empirical findings, rather than on an unrestricted optimality claim.

  1. The connection between the theoretical model and some algorithmic settings should be made explicit. The MCTS proof uses an empirical-mean concentration argument at the leaves, while Equation (9) also permits learned leaf estimates without clearly specifying the target and averaging assumptions. The synthetic experiments additionally use stochastic non-leaf rewards, outside the stated deterministic-reward assumptions of Theorem 5.

SMM requires particular care because its reference policy depends on Q; the displayed value and policy do not generally form the conjugate/gradient pair of one fixed regularizer when that dependence is included. The E3W exploration schedules also differ between the main text and experimental appendices. These points require corrections or explicit restrictions for correctness and reproducibility. They limit the current scope of the guarantees, but I do not regard them as eliminating the value of the overall contribution.

Questions for authors
  1. What condition on Q guarantees that the perturbations in Appendix A.3–A.4 are admissible? Please state the required horizon/noise regime. In the comparison with prior lower bounds, please also account explicitly for the dependence of the smoothness constant L on K.

  2. Which guarantees are intended to be minimax optimal: the dependence on T for fixed K, the joint dependence on K and T, or the tree-search dependence on K, T, and depth? Please distinguish these claims from minimizing the particular upper bound through ζ. The discussion should also acknowledge that Section 3.3 of Pedramfar and Ravanbakhsh already identifies simple policy-level regret as a pure-exploration problem; the broader targets and regularizers appear to be the relevant extension here.

  3. What averaging procedure and statistical assumptions connect the leaf update in Equation (9) to the base case in Appendix E? When a learned leaf evaluator is used, does the theorem concern the true regularized target or a target defined by that evaluator? How are the stochastic non-leaf rewards handled in the synthetic experiments?

4 comments

We thank you dearly for your review. Your feedback has been quite illuminating for our own understanding and framing of our work. We are particularly glad that you found our work novel and interesting both in our theoretical analysis and empirical evaluations. In the following, we address the points you brought up and have made changes in the manuscript in accordance with these points (see red text in the pdf).

In response to Q1, Weakness 1:The reviewer is correct in that there is a missing assumption on Q. We must assume that Q is such that there exists a non-empty ball around one of its elements. This very slightly changes the proof and the result. We amended the manuscript to now introduce a new quantity that depends on how much space there is around the worst-case instance that can be taken from Q (see Theorem 3, and Appendix A.3-4 (p. 17-19)). This quantity depends solely on the geometry of Q and is quite a realistic assumption. Given this, the new lower bound depends on the radius of the ball that exists within Q. Theorem 3 has now been restated with this new quantity, where the lower bound holds beyond a certain horizon T that depends on the radius of the ball. Note that this added assumption on the existence of a ball within Q is quite realistic, since as long as Q occupies its ambient space (a d-dimensional shape in a d-dimensional space) this holds naturally.

In response to Q1: The smoothness parameter L may indeed be dependent on K, and this relationship depends on the regularizer, so a general statement is out of scope for this paper. However, we acknowledge that in the case of Softmax policies (as in Pedramfar and Ravanbakhsh), which equate to entropy regularization and the primal norm being L1, then L∈Θ(K)L \in \Theta(K). As such, we amended Section 3.2, where we removed our hypothesis that Pedramfar and Ravanbakhsh’s lower bounds may be loose, and state that Theorem 3 matches their lower bound in rate in this specific case, while being more general, as it holds for policies other than softmax. We also amended the conclusion (Section 6) to reflect these changes. We provide an in-depth discussion on the relationship between L and K in the case of negative entropy regularization with L1 norm in Appendix M (p. 49-50) so as to make the comparison with Pedramfar & Ravanbakhsh’s work complete.

In response to Q2, W2. The optimality statements [on the upper bounds] need qualification + which guarantees are intended to be minimax optimal. You are absolutely correct. Our upper bounds are not shown to achieve minimax optimality since they are not tight in the rates dictated by the lower bounds of Section 3.2. As such, we have loosened the language surrounding these claims of optimality in the manuscript. Thank you for pointing this out, we did not intend to overclaim our results. We also provided extra discussion of the connection between our work and that of Pedramfar & Ravanbakhsh (2026), whose work originally proposes the policy recommender regret, as we call it.

SMM requires particular care. We agree that SMM does not technically fit into our setting. As was noted in Vucetic & Gidel (2026), the dual is not necessarily convex, meaning that it may not be generated via the Legendre-Fenchel dual, as is necessary in the Regularised MDP formulation of Geist et al. (2019). While this theoretical difficulty is true, we still wanted to include SMM in our experiments since it demonstrated good performance in Vucetic & Gidel (2026).

The E3W exploration schedule. It is true that we changed the E3W exploration schedule throughout our experiments section. This was mainly due to the trajectory that this project took, starting off with the exploration schedules originally proposed by Xiao et al. (2019) and Dam et al. (2021). Notably, these papers used the λt=epsilon∗K/log(t+1)\lambda_t = epsilon * K / log(t+1) schedule reported in the OCTAX and scientific discovery experiments. It was only after some experimentation that we found that this choice led to degenerate sampling policies, and modified it accordingly in the synthetic tree experiments.

Precisely, for E3W to be a valid convex combination, the coefficients need to be non-negative and add to one. However, this condition is only satisfied when t>exp⁡(ϵ∗K)−1t > \exp(\epsilon * K) - 1. This is a critical weakness of prior work that we inherited. Note that the exploration schedules in the OCTAX and scientific discovery experiments do not require many simulations to achieve feasibility: with ϵ=0.1,K=20\epsilon = 0.1, K=20, we only need six simulations to satisfy feasible convex combinations for E3W. The OCTAX environments have small action spaces (K < 10), while the scientific discovery experiments have action spaces K <= 20. As such, we decided to validate the results in the paper by running experiments on the scientific discovery tasks to demonstrate that this K-dependent schedule was not of utmost importance. The following tables list the difference between K-dependent and K-independent schedules in these experiments.

AMP (K=23K=23), top-100 diverse reward. No-search baseline: 10.17 ± 1.76. UCT: 4.54 ± 1.71 (32 sims), 6.81 ± 0.20 (128 sims), 7.47 ± 0.68 (512 sims), 7.94 ± 1.45 (1024 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM6.10 ± 0.244.73 ± 0.326.70 ± 1.03
MENTS6.53 ± 0.215.90 ± 0.097.09 ± 0.84
RENTS7.24 ± 0.088.55 ± 1.467.57 ± 0.05
TENTS6.76 ± 0.095.74 ± 0.346.30 ± 0.26
128SMM5.91 ± 0.255.15 ± 0.405.90 ± 0.15
MENTS6.72 ± 0.186.40 ± 0.286.82 ± 0.23
RENTS6.91 ± 0.147.82 ± 0.046.34 ± 0.12
TENTS7.54 ± 0.535.80 ± 0.437.38 ± 0.83
512SMM6.48 ± 0.325.73 ± 0.167.23 ± 0.64
MENTS7.66 ± 0.457.02 ± 0.238.07 ± 0.84
RENTS7.40 ± 0.117.77 ± 0.057.06 ± 0.12
TENTS8.47 ± 0.806.91 ± 0.248.60 ± 0.29
1024SMM6.63 ± 0.236.07 ± 0.287.69 ± 0.74
MENTS8.56 ± 0.487.56 ± 0.389.13 ± 0.98
RENTS7.57 ± 0.107.71 ± 0.087.40 ± 0.10
TENTS9.49 ± 0.077.20 ± 0.2910.64 ± 0.14

UTR (K=7K=7), top-100 diverse reward. No-search baseline: 4.13 ± 0.02. UCT: 4.20 ± 0.02 (32 sims), 4.13 ± 0.03 (128 sims), 4.07 ± 0.03 (512 sims), 4.00 ± 0.05 (1024 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM3.29 ± 0.033.11 ± 0.013.49 ± 0.01
MENTS3.34 ± 0.023.09 ± 0.023.46 ± 0.02
RENTS4.03 ± 0.014.07 ± 0.014.15 ± 0.01
TENTS3.70 ± 0.023.11 ± 0.034.08 ± 0.02
128SMM3.37 ± 0.023.18 ± 0.033.56 ± 0.01
MENTS3.47 ± 0.033.16 ± 0.033.55 ± 0.02
RENTS4.08 ± 0.014.05 ± 0.014.22 ± 0.01
TENTS3.91 ± 0.023.29 ± 0.024.17 ± 0.02
512SMM3.44 ± 0.023.28 ± 0.013.63 ± 0.01
MENTS3.61 ± 0.013.29 ± 0.013.62 ± 0.02
RENTS4.11 ± 0.004.07 ± 0.014.24 ± 0.01
TENTS4.04 ± 0.023.52 ± 0.014.23 ± 0.01
1024SMM3.47 ± 0.023.29 ± 0.023.66 ± 0.01
MENTS3.65 ± 0.013.34 ± 0.013.65 ± 0.01
RENTS4.12 ± 0.014.10 ± 0.014.24 ± 0.01
TENTS4.09 ± 0.023.60 ± 0.014.25 ± 0.01

GFP (K=23K=23), top-100 diverse reward. No-search baseline: 1.61 ± 0.02. UCT: 1.61 ± 0.04 (32 sims).

SimsAlgorithmE3W (original λt\lambda_t)E3W (corrected λt\lambda_t)Uniform
32SMM1.53 ± 0.011.52 ± 0.021.53 ± 0.01
MENTS1.53 ± 0.011.52 ± 0.021.53 ± 0.01
RENTS1.58 ± 0.011.61 ± 0.011.60 ± 0.01
TENTS1.61 ± 0.001.53 ± 0.011.62 ± 0.01

In these tables the K-independent λtλ_t makes E3W worse. Uniform selection seems to outperform for each of SMM, MENTS and TENTS, and only RENTS holds up. We have updated our table in the paper to reflect this change. Thank you for noticing this. We opted to keep the OCTAX experiments the same since KK is too small there to make a difference. We have highlighted this change, and added an explanation in Section 5.

In response to Q3. Leaf update in Equation (9) from a learned leaf evaluator function. The learned leaf evaluator R(s)R(s) is a constant, and thus can be viewed as an estimator V^(s)\hat{V}(s) of the value of a node. Since concentration occurs instantly on a constant (its mean remains the same regardless of the number of samples), it still fits into the theory. However, you are right to point out that the MCTS procedure then becomes an improvement operator over the estimator R(s)R(s) rather than of the true value, see Shah et al. (2022) for more details here.

In response to Q3. Handling stochastic non-leaf rewards and transitions. We handle stochastic non-leaf rewards by averaging the reward at each node, and we handle stochastic non-leaf transitions by using the chance node-decision node design that’s common in MCTS. We have added details on these points to the discussion subsection of the experiments to Section 5.4.

We kindly request that you increase your score if our responses have answered your questions and concerns. Thank you again for your questions!

Thank you very much for your thorough response and clarifications. I apologize for the delayed reply. I needed some time to double-check a few points that were unclear to me. The paper’s contributions are clearer to me now, though I still lean toward Weak Accept.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal reminder pt. 2

Hello PCs, ACs and reviewers,

As we have not received feedback yet, we would like to remind everyone that the discussion period draws to a close in about 24 hours. We believe our responses to the initial reviews successfully address the weaknesses and questions raised. We kindly ask the reviewers for their engagement in further discussions over this final day, and thank them for the effort.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.