acceptodds
Under review as a conference paper at ICLR 2027

Learning Where to Search: Subtree Exploration in Tree-Search

Abstract

In planning with tree search, how search budget is allocated across the tree determines the final decision. Standard Monte Carlo Tree Search (MCTS) allocates this computation implicitly through repeated local tree-traversal decisions that do not globally prioritize reaching the most informative region of the tree to explore next. We introduce Learning to Allocate Search Resources (LASER), a framework that separates *where* to search from *how* to search. Our method uses a graph neural network to explicitly select a node in the current search tree from which to further explore by a bounded local MCTS. We formulate this process as a metalevel decision problem and train the node selector from action-level supervision, without requiring annotations of where search should occur. On Sokoban and sliding puzzles, LASER consistently outperforms standard MCTS and alternative subtree-selection strategies under matched search budgets. We further integrate our approach into EfficientZero by training the selector concurrently with a world model, value function, and policy during reinforcement learning, and observe improved aggregate performance on Atari 100k over baseline search methods.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Planning, Search, Metareasoning

Reviews

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

This paper proposed LASER, which shows how to decouple where to do search from how to do search in MCTS. It splits a search into K rounds, and utilizes a GNN to read the whole tree in each round. During each round, a node will be picked and there will be a local MCTS rooted on this node. The selector is trained with REINFORCE on a meta-level MDP. LASER demonstrates great performance on multiple benchmarks.

Critical strengths
  1. The idea is clean, useful and insightful.
  2. The thorough ablations show consistent performance gain from LASER.
Critical weaknesses
  1. Gumbel MuZero-style search is the most relevant baseline and hope the experiments are reported in the paper.
  2. Is there any experiment to show the generalization of LASER?
Questions for authors
  1. The comparison with Gumbel Muzero-style search.
  2. What is the training cost for the selector? Relative to the planning cost?
  3. Could there be some comparison against MCTSnets or D-TSN? Or explain why they do not apply.
2 comments

Thank you for taking the time to review our paper and for your constructive feedback! We are glad you found the idea insightful and the experiments thorough.


[W1, Q1] Comparison with Gumbel MuZero-style search

Please see our common response above.


[W2] Experiment to show LASER generalization

In the paper, we showed that LASER with a selector trained with K=5 generalizes to larger K at test time (Figure 3). This experiment only tested generalization to larger search trees within the same domain. To assess cross-domain transfer, we evaluated each source-trained selector on each target domain in Table 11.

Source ↓ / Target →Sokoban15-puzzle24-puzzle35-puzzle
UCTSokoban56.80.00.00.0
15-puzzle44.292.589.23.6
24-puzzle41.389.289.485.6
35-puzzle45.988.889.290.1
Random selector41.70.00.00.0
PUCTSokoban87.299.048.28.2
15-puzzle83.399.999.640.8
24-puzzle83.899.8100.094.6
35-puzzle83.0100.099.899.4
Random selector83.199.345.37.7

Table 11. Transfer across domains under UCT and PUCT selection.

The selector transfers across problem sizes within the sliding-puzzle family, though transfer is weaker from the 15-puzzle to the 35-puzzle. Across families (Sokoban ↔ sliding puzzles), performance is generally close to or only slightly above the random-selector baseline. This pattern suggests that LASER learns allocation strategies that generalize within related tasks while adapting to the search characteristics of each domain. The limited transfer across families also supports the value of learning, as a single fixed scoring heuristic may struggle to capture the allocation strategies needed across these domains.


[Q2] What is the training cost for the selector? Relative to the planning cost?

In Sokoban and puzzles, training the selector is a one-time cost of ~0.5-1.2 GPU-hours under UCT and ~1.4-4 GPU-hours under PUCT until its performance saturates. Planning costs at most ~2 seconds per episode and scales linearly with the search budget, so the one-time training cost equals the planning cost of only a few thousand episodes. In Atari domain, the selector is learning in parallel with other components and the extra training time is negligible.


[Q3] Could there be some comparison against MCTSnets or D-TSN? Or explain why they do not apply.

MCTSnets and D-TSN address related questions, but a direct comparison would confound the effect of search-budget allocation with changes to the search algorithm or value network architecture.

MCTSnets is a learned version of MCTS trained on substantially more expert data than LASER on Sokoban (250K vs. 20K trajectories). LASER keeps local MCTS fixed and learns to allocate search to promising areas of the tree. MCTSnets could replace LASER’s local MCTS by providing a differentiable search procedure that might give the selector a denser training signal. The two approaches are therefore orthogonal. We leave this integration and its evaluation to future work.

D-TSN embeds best-first search in the value network to learn a more accurate value function from expert data. D-TSN therefore uses search to learn a value function and only indirectly to select the optimal action at the root. Given this incompatibility in purpose and mechanism, a direct comparison with LASER would not be indicative of LASER’s performance benefits.

AuthorsOpenReview ↗

Waiting for reply

Dear Reviewer,

Thank you again for reviewing our work. We have added experiments and clarifications addressing your concerns. We would appreciate your feedback on whether these revisions resolve your concerns and would be happy to clarify any remaining questions.

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

The paper discusses learned metaselection of subtrees within the setting of MCTS to choose where to proceed with another batch of simulations. Shifting the simulation start from the root to subtrees via a policy ought to improve the allocation of search resources and lead to higher-quality decision outcomes at the root state (possible because all search outcomes are fully backed up). The methodology requires expert (state, action) data for root decisions to imitate, provided by a higher-budget search, existing public data, or by its own top-scoring episodes. Evaluation is done over Sokoban, Sliding Tile puzzles, and Atari 100k against vanilla MCTS, DeepSearch's adapted scoring rule as a heuristic, and a uniform random selector of subtrees. Results favour the proposed method in the UCT setting strongly, while margins are much smaller in the PUCT setting. On Atari, the mean shows improvement, while the median and IQM gains are within conf. intervals.

Critical strengths
  • The addressed problem is meaningful and interesting: search allocation as an explicitly learnable deicsion over the whole MCTS tree instead of a side-effect of bandit choices at each node. The learner needs no supervision/labels for learning which subtree to explore further and avoids gradient backpropagation issues through the local search (black-box). This makes the method simply an extension of MCTS that incorporates vanilla MCTS at K=1 and works with all regimes of it (uct, puct, learned model...). A gain stemming from the allocation decision could thus be carried over to any MCTS-based system which comes with expert data for state-action traces; a direct relevance beyond benchmarks.

  • Evaluations are on a meaningful set of benchmarks and test sets, and failure reporting is candid. Reports are over multiple seeds, confidence intervals, and authors remark on where gains actually lie within statistical errors.

  • Reward derivations are clear and mostly straightforward to follow (although some clearer framing around how Reinforce exactly connects with the proposed method would have been welcome).

  • Architectural choices follow sound inductive biases (GNN over the entire tree; utilizing tree topology) and are ablated in the appendix.

Critical weaknesses
  • Large gains appear only in UCT, with a policy prior (PUCT) LASER improves the Sokoban solve rate by 3% over MCTS and by 1% over the DeepSearch-style heuristic. In the sliding puzzles, MCTS already reaches 94-97%. The individual components of the method are known too. If the added machinery has value, then that should show as empirical advantage in Alpha-/MuZero-style search. Where the paper evaluates this setting, the advantage is not compelling, especially due to the extra cost of expert demos and another training run for the selector.

  • The remaining gains are difficult to attribute to the learned selector. LASER and the MCTS baseline differ in three ways besides the selector: a) Q-readout: LASER picks argmax of completed Q vs. MCTS' most-visited action and neither choice received an ablation. LASER's is justified via arguments only, and the claim that visit counts suit MCTS better is made without concrete data. In Sokoban under UCT, where root visits are probably uniform-ish, a Q readout should help MCTS too. b) noise within search: LASER has noise at every search subroot, MCTS only at the global root -- this alone is worth up to 17% versus only 7% for MCTS according to figure 7, although this trend decreases over checkpoints 1 to 4. c) tuning: the exploration param was tuned only in sliding tile puzzles, where it is strong (81-87%). In sokoban, UCT-MCTS manages only 18–22% across all checkpoints, while PUCT achieves 42 to 84%. Moreover, random rerooting alone doubles the MCTS performance in Sokoban for UCT. App. C.5 says uniform selection favours deep candidates, which explains parts of the boon in Sokoban stemming from deeper exploration rather than a learned selector.

Generally, I would have also liked to see a comparison with Gumbel Sequential Halving which also targets the regret objective if I recall correctly.

Overall, the UCT results are the paper’s strongest evidence, while it is not as convincing in the more realistic and standard PUCT case. If part of that UCT margin stems from differently configured baselines, another part reflects rerooting structure rather than learning, and part of the PUCT margin from noise placements, the current experiments would not show a decisive advantage over well-configured baselines.

Questions for authors

Experiments that would change the verdict:

  • Please report MCTS with the completed-Q readout, with a tuned exploration constant in Sokoban under UCT, and under PUCT with exploration noise comparable to LASER’s (noise below the root or a tuned eps). How much of LASER’s margin over MCTS survives?

  • How does LASER compare with Gumbel Sequential Halving at 50 sims? How many sims does standard MCTS need to match LASER@50?

  • What is the DRC expert’s solve rate on your Sokoban eval? How does a PUCT baseline perform when its prior is fine-tuned on the same demonstrations, as in your sliding-puzzle control?

If LASER’s advantage holds under these tests, I would be inclined to raise my assessment.

For my clarification, do Random and DeepSearch selectors use the same completed-Q readout and subroot noise as LASER?

8 comments

Thank you for taking the time to review our paper and for your constructive feedback! We are glad you found the idea interesting, the evaluations realistic and meaningful, the method clear, and the architectural choices sound.


[W1] Smaller gains under PUCT and less compelling results in Atari domain

On Atari, we agree that the empirical advantage is less pronounced than in the setting with pretrained evaluators. We want to highlight that we used no expert demonstrations and instead trained the selector on the agent’s best previous experiences, in parallel with the other components, so the additional training time was negligible. Errors in the learned world model could also limit the performance gain, even with an optimal search strategy (please see the experiment reported in Table 3 and the accompanying discussion in our response to Reviewer X8QC.)

For Sokoban and the sliding puzzles, we expect LASER’s gains under PUCT to be smaller because the policy prior already guides search toward promising branches. These gains remain meaningful given the diminishing returns at high solve rates, where further improvements require solving increasingly difficult instances. We observe the same pattern when increasing the simulation budget of vanilla MCTS, with solve rates improving more slowly as they rise. For example, on the strongest Sokoban checkpoint, LASER raises the solve rate from 83.9% to 87.2% at the same simulation budget, a 3.3-point gain that reduces the failure rate by roughly 20%.


[W2] difficult to attribute gains to the learned selector

(a) Q-readout: We used completed Q-values for unvisited actions in all methods. For the final action, we used visit counts for standard MCTS because this readout performed slightly better on average. We report both readouts in Table 7 for completeness.

EnvUCT visitsUCT Q-valueUCT ΔPUCT visitsPUCT Q-valuePUCT Δ
Sokoban, C1C_118.120.0+1.941.7 ± 0.145.4 ± 0.4+3.7
Sokoban, C2C_218.724.0+5.357.9 ± 0.161.3 ± 0.3+3.4
Sokoban, C3C_318.923.8+4.974.4 ± 0.276.1 ± 0.3+1.7
Sokoban, C4C_421.625.8+4.283.9 ± 0.384.0 ± 0.4+0.1
15-puzzle86.885.8−1.094.7 ± 0.194.9 ± 0.1+0.2
24-puzzle84.880.4−4.493.5 ± 0.389.5 ± 0.2−4.0
35-puzzle81.062.6−18.496.9 ± 0.484.0 ± 0.4−12.9

Table 7. Visit-count vs Q-value readouts for MCTS. Δ is Q-value column minus visits.

As the reviewer anticipated, selecting the action with the highest completed Q-value slightly improves MCTS on Sokoban. MCTS still underperform LASER at every checkpoint. On the sliding puzzles, the Q-value readout generally reduces performance with a large drop in 35-puzzle.

(b, c) Noise and tuning exploration constant: As requested, we tuned exploration coefficient for standard MCTS separately under UCT and PUCT on Sokoban and added noise below the root for MCTS under PUCT. Although this setting favors MCTS, LASER still outperformed it at every checkpoint. We report the full results in our response to your question below.

Random rerooting: We agree that some of the gains come from the search structure itself, since Random generally outperforms standard MCTS on Sokoban under UCT. The gap between the random selector and LASER on Sokoban, together with the sliding-puzzle results, shows the additional gain from learning the selector. Under UCT, where there is no policy prior to guide search, both the random selector and the DeepSearch heuristic solve almost none of the sliding puzzles, while LASER solves about 90%. Under PUCT, both selectors perform well on the easier 15-puzzle with guidance from the prior. As the puzzles get larger and harder, their solve rates drop rapidly, while LASER maintains a solve rate near 100% across all three sizes.


[W3] comparison with Gumbel Sequential Halving

Please see our common response above.


We hope the new experiments and clarifications address your concerns. We discuss baseline tuning, the contribution of the learned selector, and noise placement in our responses to your specific questions and comments.

[Q1] MCTS with the completed-Q readout and tuned exploration constant in Sokoban with exploration noise similar to LASER

The reported MCTS results already use the completed-Q for missing Q-values.

In our experiments, we used the AlphaZero/MuZero default exploration constant c=1.25c=1.25 on Sokoban. Since this default did not work well on the sliding puzzles, we tuned c for standard MCTS on those tasks.

We believe the original noise settings are comparable. In standard MCTS, every simulation starts at the root, so noise at the root affects every simulation. In LASER, noise at the original root directly affects only the first round of local search. We therefore injected Dirichlet noise at each selected root to give it a similar effect in each round. We used the default noise fraction ε=0.25\varepsilon=0.25 from AlphaZero/MuZero/EfficientZero without tuning. We believe LASER benefits more from noise because a prior can dominate local search, making its outcome less sensitive to which starting node the selector chooses. Adding noise weakens this dependence on the prior and gives the selector more influence over the search outcome.

Nevertheless, as requested, we tuned c for standard MCTS on a small set of held-out Sokoban rooms under both UCT and PUCT in Table 8. Under PUCT, we also added noise below the root for standard MCTS. On a small set of held-out rooms, c=0.1c=0.1 worked best for standard MCTS under UCT and c=0.5c=0.5 under PUCT.

EnvMCTS, UCT (c=0.1c=0.1)LASER, UCT (c=0.1c=0.1)MCTS, PUCT (c=0.5c=0.5)LASER, PUCT (c=0.5c=0.5)
Sokoban, C1C_118.3 (+0.2)41.5 ± 0.8 (−1.7)45.8 ± 0.4 (+4.1)53.3 ± 0.2 (−1.5)
Sokoban, C2C_222.3 (+3.6)48.4 ± 1.0 (+0.8)63.2 ± 0.1 (+5.3)69.1 ± 0.1 (−0.1)
Sokoban,C3C_323.3 (+4.4)56.0 ± 0.7 (+1.9)76.7 ± 0.4 (+2.3)81.4 ± 0.3 (+0.1)
Sokoban, C4C_424.9 (+3.3)57.3 ± 0.7 (+0.5)83.4 ± 0.3 (−0.5)86.4 ± 0.1 (−0.8)

Table 8. Results for MCTS-tuned exploration constant and below the root exploration noise. Parentheses show the change in solve rate in percentage points relative to the corresponding c=1.25c=1.25 baseline. For MCTS with PUCT, the c=0.5c=0.5 setting also adds noise below the root.

This comparison favors standard MCTS because we used its best cc. Even so, LASER outperformed standard MCTS at every checkpoint under both UCT and PUCT.


[Q2] LASER comparison with Gumbel Sequential Halving and MCTS sims to match LASER@50

For a comparison against Gumbel Sequential Halving, please see our common response above.

We increased the number of simulations in standard MCTS to see how many it needs to match LASER@50 simulations (Table 9). Under UCT, it needs about 500-700 simulations to reach a comparable solve rate across all four checkpoints. Under PUCT, it needs about 250–1,000 simulations, depending on the policy prior.

SearchEnvLASER@50MCTS@50MCTS@100MCTS@250MCTS@350MCTS@500MCTS@700MCTS@1000Approx. sims to match
UCTSokoban, C1C_144.018.227.536.539.441.845.047.3700
Sokoban, C2C_248.418.831.841.444.947.250.552.9700
Sokoban, C3C_355.019.231.644.448.552.254.858.7700
Sokoban, C4C_455.721.733.044.849.853.257.060.0700
PUCTSokoban, C1C_154.941.245.650.150.852.253.655.21000
Sokoban, C2C_269.458.463.167.068.169.871.572.9500
Sokoban, C3C_382.174.678.581.081.982.683.283.8350
Sokoban, C4C_487.584.186.288.989.289.990.190.4250

Table 9. MCTS sims needed to match LASER@50.

At higher solve rates, even a small gap can take many additional MCTS simulations to close. Even with the most accurate prior, MCTS still needs about five times as many simulations to match LASER. We therefore argue that even the smaller solve-rate margin under PUCT still shows a substantial benefit in search efficiency.

[Q3] DRC expert and prior seeing expert demonstrations

The DRC expert solves 96% of the levels. We used DRC only to collect demonstrations on 20,000 rooms. The policy priors were trained for 10 to 500 millions of environment steps across all 900,000 training rooms.

As requested, we added an experiment for Sokoban analogous to the sliding-puzzle experiment (Table 10). We trained a policy prior from scratch on the same demonstrations used to train the selector and paired it with the pretrained value function from the final checkpoint. All three methods used this prior and value function.

MethodSuccess rate
MCTS71.1 ± 0.2
Gumbel MCTS72.7 ± 0.1
LASER76.8 ± 0.3

Table 10. Sokoban with a prior trained from scratch on DRC demonstrations.

With all three methods seeing the same information, LASER still outperforms baselines.


For my clarification, do Random and DeepSearch selectors use the same completed-Q readout and subroot noise as LASER?

Yes. All baselines used the same completed-Q readout as LASER for missing Q-values. The Random and DeepSearch selectors also used the same subroot noise as LASER.

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

The paper describes a new allocation mechanism for MCTS-like tree search methods that explicitly scores nodes for exploration, rather than relying on the implicit scoring provided by UCT.

Critical strengths

I believe the idea of treating node selection as a distinct and trainable step inside the search algorithm makes sense in principle. I also like the allusion to branch-and-bound methods which do explicitly split node selection, variable selection (≈\approx selecting the action inside a chosen node), and e.g. heuristics into different stages.

As a note: I do think there are more appropriate examples of this that make use of the tree a lot more e.g. the papers “Learning to Select Nodes in Branch-and-Bound via Tree-Aware Contrastive Learning”, “Reinforcement Learning for Node Selection in Branch-and-Bound”.

In the other direction, BnB has actually explored using MCTS like scoring for node selection in e.g. “Guiding Combinatorial Optimization with UCT”. (Mind you: I do not expect you to cite all of these papers, but I do think that the connection being made here is interesting and strengthens the motivation).

I recommend contrasting the BnB world (where UCT is explicitly deployed as a node selection mechanism) against the contents of this paper, where you explicitly aim to move away from using UCT as a selection mechanism.

Critical weaknesses

I do think the work has some weaknesses, specifically when it comes to contrasting the method against PUCT based selections: What is the theoretical difference between placing a prior on the UCT selection and placing a prior on the subtree selection, especially since you only use T=2 rounds of message passing?

In fact, I would expect that you can even rewrite the PUCT and node scoring objectives into each other by using the probability chain rule along the root-to-leaf paths. We can observe this exact similarity in the benchmarks as well: Switching from UCT to PUCT largely removes the advantage of the selection mechanisms over plain MCTS.

At the very least, I would expect more independent seeds to be necessary: The “Deep Reinforcement Learning at the Edge of the Statistical Precipice” paper cited in this work that robust statistics (i.e. IQM+bootstrap CI) start producing reasonable results at 10 seeds. Considering that the methods here are all quite close we would need at least those 10 seeds, perhaps more to make any inference.

I think this also affects the conclusions drawn in section 5.4

Its improvement over MCTS is most pronounced in the mean, with smaller gains, within statistical error, in the median and IQM and a comparable optimality gap.

In words: the method is only better when a very noise sensitive statistic is used and becomes indistinguishable when using the robust estimators of performance (median, IQM and optimality gap). This might be because robust statistics sacrifice some statistical power for repeatability, but then I would expect an increase in statistical power to reveal the advantage under robust statistics as well.

There is also a confounder in that LASER uses Danihelka et al.’s scoring method, which is known to outperform vanilla MCTS (especially for low number of planning rollouts as they are used here). At the very least you should test against MCTS with and without Danihelka’s scoring protocol to prevent spurious improvements caused by the more efficient scoring rule.

The results in table 2 are also a little bit strange: Even with additional tree traversal costs it makes, in my opinion, no sense that running an additional neural network is faster than the really cheap PUCT scoring rule. How expensive can a tree traversal possibly be? This has 50 trials, and the number of comparisons scales between n^2 and nlogn depending on how diverse the exploration is. LASER still needs K full views of the tree, which then produces 2N operations (due to message passing) without the logN reduction produced by the tree structure. Then it performs local MCTS there and propagates the information up (the “down” search is cheaper, the “up” broadcasting is more expensive). I cannot imagine that – at worst – 50 indexing operations into a tree will be more expensive than running a neural network. Do you have some standard deviation data? Could it be that there are some spikes which materially affect the results? (or, alternatively, which MCTS implementation is used and how optimized is it)

Questions for authors

See "weaknesses"

  • What happens if you increase the number of independent runs to the recommended 10?
  • What is the relation to PUCT's prior?
  • How do the results change when using Danihelka’s scoring for the traditional MCTS as well?
10 comments

Thank you for taking the time to review our paper and for your constructive feedback! We are glad you found the idea justified in principle. We will expand our discussion of BnB works you suggested and clarify their connections to our approach.


[W1, Q2]. Relation to PUCT's prior and smaller advantage under PUCT

Thank you for this insightful comment and for the opportunity to clarify the relationship between LASER and PUCT.

We agree that, on a fixed search tree, LASER’s distribution over starting nodes can be factored along root-to-node paths. Let p(u)p(u) be the probability LASER assigns to node u, and let S(u)S(u) be the total probability it assigns to candidates in the subtree rooted at u. Descending to child c with probability S(c)/S(u)S(c)/S(u) and stopping at u with probability p(u)/S(u)p(u)/S(u) reproduces LASER’s starting-node distribution exactly.

Implementing such a policy requires it to look ahead at the entire subtree of the current node. In standard PUCT, the prior sees only the environment state, and the search takes an argmax over scores that combine the prior with action values and visit counts, lacking the input features to implement the LASER distribution. Even if we give the prior access to the tree and sample from a softmax of the PUCT scores, learning a prior that induces the desired allocation through those scores remains nontrivial. LASER therefore provides a way to learn this more informative, tree-conditioned prior implicitly through the conditional routing probabilities induced by its learned node distribution.

Under PUCT, the policy prior already guides search toward promising branches, so we expect a smaller gain from learning where to allocate additional simulations. We also expect diminishing returns at high solve rates, where the remaining percentage points tend to require solving increasingly difficult instances. For example, on the strongest Sokoban checkpoint, LASER raises the solve rate from 83.9% to 87.2% at the same simulation budget. That 3.3-point gain reduces the failure rate by roughly 20%.


[W3, Q3]. Danihelka et al.’s scoring method

For clarification, the completed Q-values from Danihelka et al. only affect the Q-values assigned to unvisited actions during search. Different MCTS implementations handle these missing values differently, using a constant, a parent value estimate, completed Q-values, etc. We already used completed Q-values from Danihelka et al. for unvisited actions in standard MCTS and all other baselines.

To address this potential confounder, we added an experiment comparing completed Q-values with the simpler parent value estimate in Table 2.

SearchEnvMCTS QcompletedQ_{\text{completed}}MCTS V(parent(s))V(\text{parent}(s))LASER QcompletedQ_{\text{completed}}LASER V(parent(s))V(\text{parent}(s))
UCTSokoban, C1C_118.116.043.2 ± 0.744.5 ± 0.1
Sokoban, C2C_218.716.747.6 ± 0.249.7 ± 0.0
Sokoban, C3C_318.915.254.1 ± 0.956.5 ± 0.2
Sokoban, C4C_421.616.056.8 ± 0.958.7 ± 0.4
PUCTSokoban, C1C_141.7 ± 0.140.8 ± 0.354.8 ± 0.155.3 ± 0.3
Sokoban, C2C_257.9 ± 0.158.3 ± 0.369.2 ± 0.170.9 ± 0.2
Sokoban, C3C_374.4 ± 0.275.3 ± 0.181.3 ± 0.181.5 ± 0.3
Sokoban, C4C_483.9 ± 0.383.8 ± 0.287.2 ± 0.287.5 ± 0.2

Table 2. Completed Q-values vs parent value estimates for unvisited actions.

Replacing completed Q-values with the parent value estimate slightly increased LASER’s advantage over MCTS. This indicates that the gain does not depend on the completed-Q rule.

[W2, Q1]. Number of seeds

We agree that more independent seeds would strengthen the statistical evidence. In Section 5.4, we explicitly acknowledged that LASER’s improvement is most pronounced in the mean, while the median and IQM gains are within statistical error and the optimality gap is comparable.

Previous work on Atari 100k studies also used 3 to 5 seeds, including EfficientZero (Ye et al., 2021), SimPLe (Kaiser et al., 2020), IRIS (Micheli et al., 2023), STORM (Zhang et al., 2023), DreamerV3 (Hafner et al., 2024), DIAMOND (Alonso et al., 2024), and TWISTER (Burchi et al., 2025). With a fixed compute budget, we prioritized more environments over more seeds per environment to better assess performance across tasks and reduce sensitivity to environment selection. Each run takes approximately 16 hours on two GPUs. Evaluating four methods across 26 games with 10 seeds would require approximately 1,387 GPU-days, or nearly three months on 16 GPUs. This is beyond our available budget.

Although the mean is generally sensitive to noise, we believe it is informative in this setting. We used no expert data and instead trained the selector on the agent’s best previously collected experiences. We therefore expect larger gains in games where the baseline already performs well, since these experiences provide more useful training signals. This may explain why the improvement is larger in the mean than in the median or IQM.

Moreover, we only modify the planning component of a larger system, such that errors in other components may be constraining performance. To examine this, we increased the MCTS budget from the default 50 simulations to 100 and evaluated whether the baseline score improved in Table 3. We selected one environment where both methods perform poorly (PrivateEye), one where they perform comparably (Hero), and one where MCTS already achieves a high score (Asterix).

GameMCTS@100MCTS@50LASER
Asterix209.4 ± 6.4181.3 ± 36.2217.8 ± 17.8
Hero33.7 ± 1.832.1 ± 3.131.0 ± 2.3
PrivateEye0.01 ± 0.050.06 ± 0.020.11 ± 0.00

Table 3. Comparing human-normalized score of increased budget MCTS.

When the baseline performs poorly, increasing the search budget barely changes the human-normalized score. This suggests that better planning may yield limited bottom-line gains in some games, which could help explain the smaller changes in the median and IQM.

Having said that, we did increase the number of independent runs for MCTS and LASER to five, as reported in Table 4, and will extend the other baselines to five runs as well.

MetricMCTS (4 seeds)LASER (4 seeds)MCTS (5 seeds)LASER (5 seeds)
Mean1.672 ± 0.0701.831 ± 0.0851.646 ± 0.0651.847 ± 0.074
Median0.721 ± 0.1200.790 ± 0.1610.729 ± 0.1190.748 ± 0.134
IQM0.817 ± 0.0510.850 ± 0.0590.788 ± 0.0680.845 ± 0.054
Optimality gap ↓0.401 ± 0.0160.406 ± 0.0200.413 ± 0.0210.405 ± 0.018

Table 4. Increasing the number of independent runs to 5.

Increasing the number of seeds slightly narrowed the confidence intervals and made LASER’s gains over MCTS in mean and IQM more pronounced, while the median and optimality gap remained comparable.

In addition, we increased the number of independent runs to 10 for MCTS and LASER in eight games (Table 5). We selected four games where MCTS performed better and four where LASER performed better.

Game / MetricMCTS (4 seeds)LASER (4 seeds)MCTS (10 seeds)LASER (10 seeds)
Alien685 ± 47758 ± 115688 ± 37741 ± 64
BattleZone7844 ± 10917414 ± 2726875 ± 5256850 ± 306
Breakout384 ± 6462 ± 32389 ± 9478 ± 22
Gopher2838 ± 1702416 ± 1042124 ± 2462497 ± 90
Jamesbond453 ± 67368 ± 81383 ± 49305 ± 47
Pong15 ± 121 ± 016 ± 118 ± 1
PrivateEye55 ± 26100 ± 065 ± 1780 ± 20
Qbert13559 ± 89113030 ± 60812102 ± 93512296 ± 832
RoadRunner11320 ± 123720533 ± 114812856 ± 104621005 ± 983
Mean HNS2.186 ± 0.0362.577 ± 0.1122.152 ± 0.0422.610 ± 0.082
Median HNS1.008 ± 0.0411.002 ± 0.0400.898 ± 0.0631.007 ± 0.063
IQM HNS0.926 ± 0.0350.904 ± 0.0560.849 ± 0.0430.972 ± 0.044

Table 5. Performance of MCTS and LASER on eight selected games with 10 independent runs.

Although the confidence intervals did not narrow substantially on average, LASER’s advantage over MCTS became more pronounced, consistent with the five-seed results across all games in Table 4.

[W4]. Runtime advantage

Our experiments use two different MCTS implementations. For Sokoban and the sliding puzzles, we use a batched GPU implementation inspired by mctx [1], where the search trees for all episodes in a batch are stored as tensors, and every selection, expansion, and backup step is a batched tensor operation. For Atari 100k, we build on EfficientZero’s implementation, which stores the search tree as pointer-linked nodes in C++.

In the batched implementation, expansion and network evaluation are executed for the whole batch whenever any tree reaches a new leaf. A simulation’s cost therefore grows with the variation in leaf depths across the batch. Standard MCTS simulations start at the root and end at widely varying depths. LASER’s local simulations start at the selected frontier node and end within a few levels of it, so batched expansion and network evaluation are executed fewer times. The overhead of LASER’s lightweight selector and slightly longer backups is small in comparison, since backup operations are much cheaper than selection. In EfficientZero’s pointer-based C++ implementation, each tree is expanded individually, so this effect disappears and LASER is slightly slower.

In the paper we reported median runtimes, which are resistant to spikes. As requested, we also report the mean and standard deviation in Table 6.

EnvMCTS (ms)LASER (ms)
Sokoban20.52 ± 0.6417.48 ± 1.34
15-puzzle14.33 ± 0.2714.02 ± 0.29
24-puzzle14.58 ± 0.1413.25 ± 0.33
35-puzzle14.62 ± 0.1610.48 ± 0.44
Atari 100k74.10 ± 1.0480.00 ± 1.18
Table 6. Per-decision search time in milliseconds, reported as mean ± standard deviation.

[1] https://github.com/google-deepmind/mctx

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response

(Reviewer Prjb and n3gJ) Comparison with Gumbel MuZero-style search

Gumbel MuZero-style search targets a regime where the number of simulations is small relative to the number of actions, and addresses it in the setting where search supports policy learning. Our case is different in both aspects: we focus on test-time search with a given policy, with enough budget to cover all available actions. Nevertheless, we added an experiment comparing Gumbel MuZero-style search, adapted to our setting, with PUCT and LASER on Sokoban and the sliding puzzles in Table 1.

EnvPUCTGumbel MCTSLASER
Sokoban, C1C_141.7 ± 0.144.0 ± 0.354.8 ± 0.1
Sokoban, C2C_257.9 ± 0.165.8 ± 0.469.2 ± 0.1
Sokoban, C3C_374.4 ± 0.279.0 ± 0.281.3 ± 0.1
Sokoban, C4C_483.9 ± 0.385.4 ± 0.387.2 ± 0.2
15-puzzle94.7 ± 0.196.2 ± 0.199.9 ± 0.1
24-puzzle93.5 ± 0.390.8 ± 0.4100.0 ± 0.0
35-puzzle96.9 ± 0.469.0 ± 0.999.4 ± 0.1

Table 1. Gumbel MCTS with Sequential Halving vs LASER.

Gumbel MuZero-style search improves over PUCT on Sokoban and the 15-puzzle, but performs worse on the harder sliding puzzles. We believe this is because the policy prior becomes less accurate as the puzzles get harder, since the policy is trained on the same amount of data for each puzzle size. Gumbel MuZero-style search may be more sensitive to the prior than PUCT because Sequential Halving eliminates half the remaining actions at each round based on a ranking that is strongly influenced by the prior. LASER still outperforms Gumbel MuZero-style search on both Sokoban and the sliding puzzles, though the gap is smaller than against PUCT on Sokoban and the 15-puzzle.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.