Structure-Induced Information for Rerooting Levin Tree Search

# Structure-Induced Information for Rerooting Levin Tree Search
Source: [https://arxiv.org/html/2605.30664](https://arxiv.org/html/2605.30664)
###### Abstract

Subgoal\-based policy tree search, which uses a policy to guide the search, is effective for complex single\-agent deterministic problems but often relies on explicit subgoal generation, which can incur substantial overhead, hindering scalability\. In this paper, we overcome these limitations by using a learned “rerooter” through the recently introducedlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}algorithm\. A*rerooter*implicitly decomposes the problem into soft subtasks\. While previous work focused on the formal guarantees for given or handcrafted rerooters, in this work, we propose three rerooter designs: \(i\) a clustering\-based rerooter that exploits global state\-space structure, \(ii\) a heuristic\-based rerooter that leverages learned cost\-to\-go estimates, and \(iii\) a hybrid that combines both signals\. Our framework avoids explicitly reconstructing and reasoning over generated subgoals, thereby enabling scalable allocation of search effort with significantly lower computational overhead\. Empirically, our rerooting\-based methods scale to complex environments where subgoal\-based policy tree search fails, and achieve state\-of\-the\-art online training efficiency on the domains tested\.

Machine Learning, ICML

\\declaretheorem

\[name=Theorem,numberwithin=section\]thm

## 1Introduction

Complex discrete planning problems remain difficult to solve at scale, driving increasing interest in learning\-guided search methods\. Levin Tree Search \(LTS\)\(Orseauet al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib3)\), a tree search algorithm that uses a learned policy to guide the search \(a probability distribution over actions\), has shown success in addressing these types of problems\. A key property of LTS is that it provides an upper bound on the number of search steps required before finding a solution, which depends on the*quality*of the policy\. This, in turn, enables policies to be learned with the explicit objective of minimizing search effort\. Policy Guided Heuristic Search \(PHS\*\)\(Orseau and Lelis,[2021](https://arxiv.org/html/2605.30664#bib.bib4)\)extends LTS by combining a learned policy with a learned heuristic function\.Orseau and Lelis \([2021](https://arxiv.org/html/2605.30664#bib.bib4)\)provide a similar bound forPHS\*, and also show that a policy can be learned while minimizing this bound\.

Although LTS andPHS\*are theoretically well\-founded, they rely primarily on the learned policy and heuristic functions and, without additional structural guidance, can struggle to solve complex problems\. A common approach when scaling to complex problem domains, inspired by how humans plan\(Botvinicket al\.,[2009](https://arxiv.org/html/2605.30664#bib.bib8); Donnarummaet al\.,[2016](https://arxiv.org/html/2605.30664#bib.bib10); Correaet al\.,[2023](https://arxiv.org/html/2605.30664#bib.bib9)\), is to decompose the problem into easier subtasks and subgoals\. Subgoals help address this limitation by structuring the search and extending its reach beyond what the initial policy can support\. Building on this insight, prior work has introduced subgoal\-based policy tree search methods, includingHIPS\-ε\\varepsilon\(Kujanpääet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib14)\)and Subgoal\-Guided Policy Heuristic Search \(SGPS\)\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\), which generate intermediate target states and condition low\-level policies on these generated subgoals to guide the search\. By explicitly reasoning over such subgoals, these approaches can improve early\-stage exploration and learning efficiency\. However, they also introduce additional modeling complexity and computational overhead, as search performance becomes tightly coupled to the quality of subgoal reconstruction and the policies conditioned on them\. As we will show, this issue becomes increasingly pronounced as the domain complexity increases\.

lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\(Orseauet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib6)\), read as “root\-LTS”, is a policy tree search algorithm that implicitly starts an LTS search at each node in the search tree\. The overall search effort is split between each of these searches, and the proportion of time allocated to each is given through a*rerooter*\. This mechanism implicitly decomposes the search into subtasks, foregoing the complexity of the subgoal modeling ofHIPS\-ε\\varepsilonandSGPSthat makes those methods costly when scaling to complex domains\.Orseauet al\.\([2024](https://arxiv.org/html/2605.30664#bib.bib6)\)showed that the bound on the number of node expansions beforelts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}finds a solution can be exponentially better than that of LTS\.

In this work, we revisit rerooting as a general mechanism for exploiting structure in the underlying state space in policy tree search and study how to derive rerooting weights in practice to guide search effectively\. Within this framework, we present three instantiations\. The first two capture complementary structural information: a global approach that induces structure via state\-space clusters identified using Leiden clustering\(Traaget al\.,[2019](https://arxiv.org/html/2605.30664#bib.bib18)\), and a lightweight local approach that derives structure from learned heuristic cost information\. We then show how an additive rerooter can take advantage of the strengths each rerooter provides, and instantiate this as a hybrid rerooter of the previous two\. In contrast to the subgoal baseline methods, which depend on computationally expensive subgoal generation using high\-capacity models\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\), our approach does not require learning or invoking separate subgoal networks\. Instead, we instantiate rerooters from structure already present in the search tree, with the clustering rerooter running on demand during search\. Empirical results show that our rerooters substantially improve online training sample efficiency over non\-rerooting baselines\. These results establish rerooting as a scalable approach for exploiting structure in search, while avoiding explicit subgoal generation of previous work\.

Our contributions can be summarized as follows\. We provide automated methods for learning rerooters from the structure of the search tree and show that even lightweight structural signals can achieve strong performance\. Finally, we provide a novel theoretical guarantee on the number of node expansions until the first solution node is found bylts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}using additive rerooters, which highlights howlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}can take advantage of the*synergies*of multiple rerooters\. The experiments conducted show that our method can scale to complex environments during online training and achieve state\-of\-the\-art training efficiency for methods that use the bootstrap method, whereas previous methods that rely on subgoal reconstruction fall short\.

## 2Preliminaries

Policy tree search algorithms solve single\-agent deterministic problems by incrementally constructing a search tree\. These problems are represented as a tuple\(𝒮,𝒜,T,s1,𝒮g,ℓ\)\(\\mathcal\{S\},\\mathcal\{A\},T,s\_\{1\},\\mathcal\{S\}\_\{g\},\\ell\), where𝒮\\mathcal\{S\}denotes the state space,𝒜\\mathcal\{A\}is a finite actions set, andT:𝒮×𝒜→𝒮T\\ :\\ \\mathcal\{S\}\\times\\mathcal\{A\}\\to\\mathcal\{S\}is a deterministic transition function\. The initial state is given bys1∈𝒮s\_\{1\}\\in\\mathcal\{S\}, and𝒮g\\mathcal\{S\}\_\{g\}is the set of goal states\. The search problem induces a directed graphG=\(𝒮,A\)G=\(\\mathcal\{S\},A\), where an edge\(s,s′\)∈A\(s,s^\{\\prime\}\)\\in Aexists whenever there is an actiona∈𝒜a\\in\\mathcal\{A\}such thatT​\(s,a\)=s′T\(s,a\)=s^\{\\prime\}\.

The set of nodes in the search tree is𝒩\\mathcal\{N\}\. The set of children nodes of a nodennis𝒞​\(n\)\\mathcal\{C\}\(n\), and its parent ispar​\(n\)\\mathrm\{par\}\(n\)\. All nodes have exactly one parent, except for the root noden1n\_\{1\}, which corresponds to the initial states1s\_\{1\}\. The set of ancestors of a nodennisanc​\(n\)\\mathrm\{anc\}\(n\), and we defineanc∗​\(n\)=anc​\(n\)∪\{n\}\\mathrm\{anc\}\_\{\*\}\(n\)=\\mathrm\{anc\}\(n\)\\cup\\\{n\\\}\. Similarly, the set of descendants of a nodennisdesc​\(n\)\\mathrm\{desc\}\(n\), anddesc∗​\(n\)=desc​\(n\)∪\{n\}\\mathrm\{desc\}\_\{\*\}\(n\)=\\mathrm\{desc\}\(n\)\\cup\\\{n\\\}\. We also use the notationn′≺nn^\{\\prime\}\\prec nforn′∈anc​\(n\)n^\{\\prime\}\\in\\mathrm\{anc\}\(n\), andn′⪯nn^\{\\prime\}\\preceq nforn′∈anc∗​\(n\)n^\{\\prime\}\\in\\mathrm\{anc\}\_\{\*\}\(n\)\. The set of nodes representing goal states𝒮g\\mathcal\{S\}\_\{g\}is denoted𝒩g\\mathcal\{N\}\_\{g\}\. The search algorithm incurs a loss ofℓ:𝒩→\(0,∞\]\\ell:\\mathcal\{N\}\\to\(0,\\infty\]for each node expansion\. For any nodenn, the*path loss*is defined asg​\(n\)=∑n′⪯nℓ​\(n′\)g\(n\)=\\sum\_\{n^\{\\prime\}\\preceq n\}\\ell\(n^\{\\prime\}\),i\.e\.the sum of losses from the root tonn\. We assume that all algorithms discussed in this work incur lossℓ​\(n\)=1\\ell\(n\)=1for all nodesnn, resulting in path lossg​\(n\)g\(n\)being equivalent to node depthd​\(n\)\+1d\(n\)\+1\.

A policyπ\\piassigns probabilities to child nodes, whereπ\(⋅\|n\)\\pi\(\\cdot\|n\)is a distribution over𝒞​\(n\)\\mathcal\{C\}\(n\)\. The induced*path probabilities*are defined byπ​\(n¯\|n¯\)=π​\(n¯\|n\)​π​\(n\|n¯\)\\pi\(\\underline\{n\}\|\\overline\{n\}\)=\\pi\(\\underline\{n\}\|n\)\\pi\(n\|\\overline\{n\}\)for anyn¯⪯n⪯n¯\\overline\{n\}\\preceq n\\preceq\\underline\{n\}, withπ​\(n\|n\)=1\\pi\(n\|n\)=1\. We defineπ​\(n\|n¯\)=0\\pi\(n\|\\overline\{n\}\)=0whenn¯⋠n\\overline\{n\}\\npreceq n\. For convenience, we denoteπ​\(n\)=π​\(n\|n1\)\\pi\(n\)=\\pi\(n\|n\_\{1\}\)\. Some search algorithms utilize a*heuristic*h:𝒩→ℝ≥0h:\\mathcal\{N\}\\to\\mathbb\{R\}\_\{\\geq 0\}which assigns non\-negative values to nodes which estimate the path loss from the current node to a goal node\.

### 2\.1Background

Best\-First Search \(BFS\)\. BFS\(Pearl,[1984](https://arxiv.org/html/2605.30664#bib.bib7)\)expands nodes by increasing*cost*\. The search is initialized with the root node in a priority queue\. In each search step, the lowest cost node is removed from the queue and is expanded, with the generated nodes added into the queue\. A node is not expanded by BFS if its underlying state has previously been expanded\. BFS will halt when either there are no nodes left in the queue, a solution is found, or a search budget \(in terms of the number of expansions\) has been exceeded\.

Levin Tree Search\. Levin Tree Search \(LTS\)\(Orseauet al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib3)\)is a BFS algorithm which uses

φLTS​\(n\)=d​\(n\)\+1π​\(n\)\\varphi\_\{\\mathrm\{LTS\}\}\(n\)=\\frac\{d\(n\)\+1\}\{\\pi\(n\)\}\(1\)as the cost function\. LTS is guaranteed to expand no more than\(d​\(n∗\)\+1\)/π​\(n∗\)\\left\(d\(n^\{\*\}\)\+1\\right\)/\\pi\(n^\{\*\}\)nodes until the first solution noden∗∈𝒩gn^\{\*\}\\in\\mathcal\{N\}\_\{g\}has been generated\(Orseauet al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib3)\)\.

Thelts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}Algorithm\.lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\(Orseauet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib6)\)is a*rerooting*algorithm which implicitly starts an LTS search rooted at every node of the tree\. For any nodenn, the base cost functionctr​\(n\)c\_\{t\}^\{r\}\(n\)represents the cost ofnnwith respect to the instantiated LTS search rooted at nodent≺nn\_\{t\}\\prec n:

ctr​\(n\)=∑nt≺n′⪯n1π​\(n′\|nt\)\.c\_\{t\}^\{r\}\(n\)=\\sum\\limits\_\{n\_\{t\}\\prec n^\{\\prime\}\\preceq n\}\\dfrac\{1\}\{\\pi\(n^\{\\prime\}\|n\_\{t\}\)\}\.\(2\)Arerooterassigns a*rerooting weight*to each of these LTS searches, whichlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}uses to split the overall search effort between these searches proportional to their assigned weight\. Like LTS,lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}is a BFS algorithm using the cost function

cr​\(n\)=minnt≺n⁡1wt​ctr​\(n\),c^\{r\}\(n\)=\\min\\limits\_\{n\_\{t\}\\prec n\}\\frac\{1\}\{w\_\{t\}\}c\_\{t\}^\{r\}\(n\),\(3\)wherewt≥0w\_\{t\}\\geq 0is the rerooting weight for the LTS search anchored at the ancestorntn\_\{t\}ofnn\.

Orseauet al\.\([2024](https://arxiv.org/html/2605.30664#bib.bib6)\)also provide theoretical guarantees on the number of node expansions required until the first solution node has been found, which depends on the quality of the policy and the rerooter\. Supposelts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}finds the solution noden∗n^\{\*\}at some stepTT\. A*subtask decomposition*of the path fromn1n\_\{1\}ton∗n^\{\*\}is a subset of the ancestors ofn∗n^\{\*\}, which must include bothn1n\_\{1\}andn∗n^\{\*\}, viewed as subtask boundaries\. For example, for the game of Sokoban, one subtask decomposition is all the ancestors where the agent has pushed a box on a goal spot\. Let𝒟​\(n∗\)\\mathcal\{D\}\(n^\{\*\}\)be the set of all such subtasks decompositions ofn∗n^\{\*\}\. ForD∈𝒟​\(n∗\)D\\in\\mathcal\{D\}\(n^\{\*\}\), the selected ancestors ofn∗n^\{\*\}are expanded at stepsT1,T2,…,T\|D\|T\_\{1\},T\_\{2\},\\dots,T\_\{\|D\|\}, where necessarilyT1=1T\_\{1\}=1andT\|D\|=TT\_\{\|D\|\}=T\. Then the number of search stepsTTthatlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}takes to visitn∗n^\{\*\}is bounded by\(Orseauet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib6), Corollary 12, adapted\)

T≤1\+minD∈𝒟​\(n∗\)⁡maxi<\|D\|⁡w<TwTi​cTir​\(nTi\+1\),\\displaystyle T\\leq 1\+~\\min\_\{D\\in\\mathcal\{D\}\(n^\{\*\}\)\}~\\max\_\{i<\|D\|\}~\\frac\{w\_\{<T\}\}\{w\_\{T\_\{i\}\}\}~c^\{r\}\_\{T\_\{i\}\}\(n\_\{T\_\{i\+1\}\}\)\\,,\(4\)wherew<T=∑j<Twtw\_\{<T\}=\\sum\_\{j<T\}w\_\{t\}is the cumulative rerooting weight of the nodes expanded up to stepTT\(excluded\),wTi/w<Tw\_\{T\_\{i\}\}/w\_\{<T\}is the time share allocated to the LTS instance started at theiith \(shallowest\) ancestor ofn∗n^\{\*\}in the subtask decomposition,cTir​\(nTi\+1\)c^\{r\}\_\{T\_\{i\}\}\(n\_\{T\_\{i\+1\}\}\)is the bound on the number of search steps this LTS instance takes to reach the next subtask boundarynTi\+1n\_\{T\_\{i\+1\}\}, andmaxi<D\\max\_\{i<D\}corresponds to the most ‘difficult’ subtask in the decomposition\. This subtask decomposition can allowlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}to expand exponentially fewer nodes than LTS; see\(Orseauet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib6)\)for a detailed description oflts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\. See[Appendix˜J](https://arxiv.org/html/2605.30664#A10)for an example\.

### 2\.2Problem Definition

Our objective formulation is the same as given inOrseau and Lelis \([2021](https://arxiv.org/html/2605.30664#bib.bib4)\)andTueroet al\.\([2025](https://arxiv.org/html/2605.30664#bib.bib5)\), which is to solve a setKKof problem instances as*quickly*as possible\. We use the*total search loss*as our objective metric\. The*search loss*L​\(S,n\)L\(S,n\)of algorithmSSis the sum of lossesℓ​\(n′\)\\ell\(n^\{\\prime\}\)incurred for each noden′n^\{\\prime\}expanded up to and includingnn\. Here,nncould either be a solution node in𝒩g\\mathcal\{N\}\_\{g\}or the last node expanded before a given budget is exceeded\. The*total search loss*∑k∈KL​\(S,nk\)\\sum\_\{k\\in K\}L\(S,n\_\{k\}\)is the sum of individual search losses algorithmSSincurs on problemkk\. We assumeℓ​\(n\)=1\\ell\(n\)=1everywhere, thus minimizing the search loss corresponds to minimizing the total number of expansions\.

## 3Structure\-Induced Rerooters

In this section, we describe how rerooting can be instantiated in practice to exploit structural information during policy tree search\.Orseauet al\.\([2024](https://arxiv.org/html/2605.30664#bib.bib6)\)focused on analyzing the formal properties oflts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}for a*given*rerooter, and left open the question of how to define or learn the rerooter\. We address this gap by presenting two complementary rerooters that derive rerooting weights from signals available during search: a clustering\-based rerooter that captures global structure in the state space, and a heuristic\-based rerooter that leverages local cost\-to\-go information\. Together, these designs illustrate how rerooting can be learned or instantiated automatically, without the complexities of explicit subgoal reconstruction, and provide a practical foundation for scalable rerooting in complex domains\.

### 3\.1Global Structure–Induced Rerooting

Motivation\. Progress in many planning problems is characterized by transitions between distinct regions of the state space\. When search reaches a new region, it is often beneficial to concentrate effort there; when it keeps expanding within the same region without making progress, effort should be redirected elsewhere in the tree\. Such transitions may correspond to events like entering a new room or acquiring a key that unlocks additional states\. To capture this behavior, the global rerooter derives rerooting weights from coarse state\-space structure by clustering states based on connectivity\. It then allocates effort across clusters rather than individual nodes, reflecting global organization while relying only on state observations and a Boolean goal test, without explicit subgoal reconstruction during search\.

Global Structure\. A key part of our method is the Leiden clustering algorithm\(Traaget al\.,[2019](https://arxiv.org/html/2605.30664#bib.bib18)\), which is an improvement over the Louvain clustering algorithm\(Blondelet al\.,[2008](https://arxiv.org/html/2605.30664#bib.bib15)\), both in terms of runtime complexity and cluster quality\. The Leiden algorithm is an iterative algorithm that creates a hierarchy of graphs\(G1,…,GN\)\(G\_\{1\},\\dots,G\_\{N\}\)whereGi\+1G\_\{i\+1\}is a clustering of graphGiG\_\{i\}\. In each iterationii, a hierarchical cluster graphGi\+1=\(Vi\+1,Ei\+1\)G\_\{i\+1\}=\(V\_\{i\+1\},E\_\{i\+1\}\)is created fromGi=\(Vi,Ei\)G\_\{i\}=\(V\_\{i\},E\_\{i\}\), whereVi\+1V\_\{i\+1\}is a partition ofViV\_\{i\}with eachv∈Vi\+1v\\in V\_\{i\+1\}being a part in the partition, andEi\+1E\_\{i\+1\}containing edges\(vi\+1,vi\+1′\)\(v\_\{i\+1\},v^\{\\prime\}\_\{i\+1\}\)forvi\+1,vi\+1′∈Vi\+1v\_\{i\+1\},v^\{\\prime\}\_\{i\+1\}\\in V\_\{i\+1\}if there is au∈vi\+1u\\in v\_\{i\+1\}andv∈vi\+1′v\\in v^\{\\prime\}\_\{i\+1\}such that\(u,v\)∈Ei\(u,v\)\\in E\_\{i\}\. The process continues until either there is no progress made \(i\.e\.,Gi\+1=GiG\_\{i\+1\}=G\_\{i\}\) orGi\+1G\_\{i\+1\}contains a single node\.

Our first rerooter, which we denotelts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}, uses the Leiden clustering algorithm to find structures in the induced subgraph of the state space\. During the search, the induced subgraph of the underlying state space is constructed iteratively as the tree is built\. When the search generates a tree\-node representing an unseen state, it adds a graph\-node to the induced subgraph with an edge linking to the graph\-node represented by the parent tree\-node\. When the search generates a tree\-node representing a previously seen state, it adds an edge to the induced subgraph linking the graph\-node represented by the parent tree\-node to the graph\-node representing the state of the generated tree\-node\.

The Leiden algorithm creates cluster graphs at increasing levels of the hierarchy by maximizing the*modularity*, a metric that quantifies the relation between the edge connectivity within a cluster and the connectivity between clusters\. High modularity results in dense clusters with many connections within each cluster, and sparse connections between clusters\.Evans and Şimşek \([2023](https://arxiv.org/html/2605.30664#bib.bib2)\)found that the Louvain algorithm using this modularity metric finds meaningful structures in the state spaces they studied, such as two neighboring clusters corresponding to states of two adjacent rooms in a gridworld environment\.

![Refer to caption](https://arxiv.org/html/2605.30664v1/x1.png)

Figure 1:lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}Rerooter\. Each node in the tree is assigned a color corresponding to the cluster it is associated with in the cluster graph at levelkkof the hierarchy\. The rerooting weight for the expanded node is then computed using the color count map\.Rerooting Weight\. Thelts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}rerooter is visually depicted in Figure[1](https://arxiv.org/html/2605.30664#S3.F1)\. We invoke the Leiden algorithm at search stepsγi\\gamma^\{i\}fori∈ℤ≥0i\\in\\mathbb\{Z\}\_\{\\geq 0\}on the incrementally induced subgraphG0G\_\{0\}, with hyperparameterγ\>0\\gamma\>0\. From the resulting hierarchy, we select a cluster graphGk=\(Vk,Ek\)G\_\{k\}=\(V\_\{k\},E\_\{k\}\)at hierarchy levelkk\(a hyperparameter\), where each nodeU∈VkU\\in V\_\{k\}corresponds to a set of nodes inG0G\_\{0\}\(and thus to a set of search\-tree nodes\)\. We assign each tree nodenna colorc∈\{1,…,\|Vk\|\}c\\in\\\{1,\\dots,\|V\_\{k\}\|\\\}indicating the nodeUUthat contains it; we refer to this assignment as a*coloring*\. Colors may change across invocations: a nodenncan have coloriion the\(τ\)\(\\tau\)th invocation, and colorj≠ij\\neq ion the\(τ\+1\)\(\\tau\+1\)th invocation\.

At search steptt, the Leiden algorithm has been invokedτ=⌊logγ⁡\(t\)⌋\\tau=\\lfloor\\log\_\{\\gamma\}\(t\)\\rfloortimes, resulting inτ\\taucolorings, with the most recent coloring occurring on search stept′=⌊γτ⌋≤tt^\{\\prime\}=\\lfloor\\gamma^\{\\tau\}\\rfloor\\leq t\. For the search steps betweent′t^\{\\prime\}andtt, some nodes may be expanded which do not have a color, as they were not present in the induced subgraph when the most recent\(τ\)\(\\tau\)th coloring occurred\. For these nodes, we assume that they belong to the same clustering as their parent and are thus given their parent’s color\. Using a proxy value to defer expensive computations has been used previously in heuristic search, such as when computing the edge cost\(Narayanan and Likhachev,[2017](https://arxiv.org/html/2605.30664#bib.bib17)\)or the heuristic value\(Karpaset al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib16)\)is costly\.

LetMτ,cM\_\{\\tau,c\}be the number of nodes with colorccfrom the\(τ\)\(\\tau\)th coloring, and

δτ,c=\|\{⌊γτ⌋<ℓ≤t:cℓ=c\}\|\\delta\_\{\\tau,c\}=\\left\|\\\{\\lfloor\\gamma^\{\\tau\}\\rfloor<\\ell\\leq t:c\_\{\\ell\}=c\\\}\\right\|\(5\)be the count of nodes expanded since step⌊γτ⌋\\lfloor\\gamma^\{\\tau\}\\rfloorwhich also have colorcc\. Then,lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}assigns the rerooting weightwtw\_\{t\}for the nodentn\_\{t\}expanded at search stepttas

wt=1Mτ,ct\+δτ,ctw\_\{t\}=\\frac\{1\}\{M\_\{\\tau,c\_\{t\}\}\+\\delta\_\{\\tau,c\_\{t\}\}\}\(6\)wherectc\_\{t\}is the color associated withntn\_\{t\}\. The value ofMτ,ct\+δτ,ctM\_\{\\tau,c\_\{t\}\}\+\\delta\_\{\\tau,c\_\{t\}\}approximates the size of the clusterctc\_\{t\}\. Note that the cluster size is only approximate because the search will potentially generate and expand nodes that were not inG0G\_\{0\}during the last execution of the clustering algorithm\.

This gives us the desirable property that a low color count results in a larger weightwtw\_\{t\}and lower search cost\. Similarly, a higher color count results in a smaller weightwtw\_\{t\}, and higher cost\. As the search expands more nodes with colorcc, the count increases and thus subsequent nodes expanded from the same cluster receive lower weights and higher costs\. See Algorithm[1](https://arxiv.org/html/2605.30664#alg1)in Appendix[A](https://arxiv.org/html/2605.30664#A1)for its pseudocode\.

Runtime Complexity\. While the induced subgraph of the state space is built incrementally, Leiden cluster graphs are recomputed on the most recent graph under a geometric update schedule to limit runtime overhead\. Although cluster assignments \(and sizes\) may change across updates, we keep the rerooting weights of previously expanded nodes as fixed: retroactively updating them would make the search tree internally inconsistent, since an ancestor could induce different costs for different descendants depending on when they were generated\. Although repeated clustering may appear expensive, we show thatlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}’s runtime matches BFS up to constant factors\. Unlike prior subgoal\-based approaches, it avoids queries to compute\-intensive models such as subgoal generators\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\)\.

###### Theorem 3\.1\.

LetNNbe the number of node expansions,DDthe depth of the max\-depth node afterNNexpansions,kkthe cluster hierarchy level,G=\(V,E\)G=\(V,E\)the underlying state space graph for environment domain\. Assume the environment has a uniform branching factorb<∞b<\\infty\. If Leiden clustering is invoked at search steps following a geometric schedule with factorγ\>1\+1/ϵ\\gamma\>1\+1/\\epsilonfor some constantϵ\>0\\epsilon\>0, thenlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}hasO​\(b​N​log⁡N\+D​N\)O\(bN\\log N\+DN\)time complexity\.

The proof is in Appendix[B](https://arxiv.org/html/2605.30664#A2)\. The uniform branching\-factor assumption is standard in tree\-search–based planning and control, where each state has a bounded number of successor states determined by the action set\.

### 3\.2Local Structure–Induced Rerooting

Motivation\. Global structural cues are not always needed for effective rerooting: local information at individual nodes can distinguish between otherwise similar regions of the search tree\. For example, if the root has two structurally identical subtrees, a rerooter based solely on structural expansion history would allocate equal effort to both; yet if one subtree is estimated to be closer to the goal, it should be prioritized\. We therefore consider a local rerooter that leverages heuristic cost\-to\-go estimates to assign weights reflecting the local geometry of the search space\.

Rerooting Weight\. The rerooter, which we denote aslts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}, uses the heuristic value of a node to define its rerooting weight directly\. The rerooting weight is given by

w1=1;wt=exp⁡\(−α​h​\(nt\)h​\(n1\)\),w\_\{1\}=1;\\quad w\_\{t\}=\\exp\\left\(\-\\alpha\\frac\{h\(n\_\{t\}\)\}\{h\(n\_\{1\}\)\}\\right\),\(7\)whereα\>0\\alpha\>0is a constant constant controlling how strongly rerooting effort is concentrated on nodes with low heuristic value, andh​\(nt\)h\(n\_\{t\}\)is the heuristic value corresponding to nodentn\_\{t\}\.

This choice is natural for several reasons\. First, it is monotone in the heuristic: ifh​\(ni\)<h​\(nj\)h\(n\_\{i\}\)<h\(n\_\{j\}\), thenwi\>wjw\_\{i\}\>w\_\{j\}\. Thus, nodes estimated to be closer to the goal receive a larger rerooting weight and therefore induce a lower rerooted search cost\. Normalizing by the root heuristich​\(n1\)h\(n\_\{1\}\)makes the rerooting weight depend on relative rather than absolute heuristic scale\. This is useful when different environments, or different instances within the same environment, exhibit substantially different effective solution\-length scales\. Second, the exponential map is smooth and strictly positive\. Even nodes with relatively poor heuristic values retain non\-zero weight, which is desirable when the heuristic is imperfect and should influence, rather than fully determine, the rerooting decision\. Third, the parameterα\\alphaacts as an inverse\-temperature parameter\. Whenα\\alphais small, the weights are more similar across nodes, so the rerooter behaves conservatively\. Asα\\alphaincreases, the weight mass becomes more concentrated on nodes whose heuristic values are small relative to the root, causing rerooting to focus more aggressively on regions that appear to have made substantial progress toward a goal\.

A useful consequence of this normalization is that this rerooting formulation is invariant to multiplicative rescaling of the heuristic\. The exponential form also gives the rerooter a useful normalized interpretation\. For any setIIof candidate rerooting points,

wt∑i∈Iwi=exp⁡\(−α​h​\(nt\)/h​\(n1\)\)∑i∈Iexp⁡\(−α​h​\(ni\)/h​\(n1\)\),\\frac\{w\_\{t\}\}\{\\sum\_\{i\\in I\}w\_\{i\}\}=\\frac\{\\exp\(\-\\alpha h\(n\_\{t\}\)/h\(n\_\{1\}\)\)\}\{\\sum\_\{i\\in I\}\\exp\(\-\\alpha h\(n\_\{i\}\)/h\(n\_\{1\}\)\)\},which is precisely a softmax over the scores−α​h​\(ni\)/h​\(n1\)\-\\alpha h\(n\_\{i\}\)/h\(n\_\{1\}\)\. Thus, the rerooter distributes search effort smoothly across candidate local roots, with larger shares assigned to nodes whose heuristic values are small relative to the root\. This is well aligned with the role of rerooting weights inlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}, where the weights determine how computation is shared among competing local searches\. See Algorithm[2](https://arxiv.org/html/2605.30664#alg2)in Appendix[A](https://arxiv.org/html/2605.30664#A1)for its pseudocode\.

### 3\.3Hybrid Structure–Induced Rerooting

Motivation\. While our global and local rerooters are each useful in isolation, they capture complementary aspects of the search problem and exhibit distinct limitations\. The heuristic\-based rerooter provides a lightweight goal\-directed signal, but on its own it depends entirely on local cost\-to\-go estimates and can therefore be sensitive to heuristic noise or miscalibration\. In particular, if the heuristic is only weakly informative in some region of the tree, the rerooter may overemphasize nodes whose low heuristic values do not correspond to meaningful structural progress\. By contrast, the clustering\-based rerooter relies on coarse connectivity in the induced state\-space graph and is agnostic to direct goal proximity, making it less responsive to local progress toward a solution\. Consequently, it may spread search effort across regions that are structurally distinct yet equally far from the goal\.

These two rerooters are therefore naturally complementary\. The global rerooter captures coarse structural bottlenecks and allocates effort across broader regions of the search space, while the local rerooter refines this allocation using heuristic information that reflects estimated progress within those regions\. This motivates a hybrid rerooter that combines both signals additively\.

![Refer to caption](https://arxiv.org/html/2605.30664v1/x2.png)

Figure 2:Average online training loss with respect to expansions \(top\) and time \(bottom\), in log\-scale\. Shaded regions show the minimum and maximum\. Time measures the sum an algorithm spends on each problem across all threads used during training\.Rerooter Weight\. The hybrid rerooter combines these signals by using global structure to set a stable coarse allocation of effort, and heuristic estimates to refine priorities within each region\. This yields a coarse\-to\-fine rerooting rule that is less sensitive to heuristic miscalibration while retaining goal\-directed adaptivity across domains\. We denote this hybrid rerooter aslts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}, and use the combined rerooting weights given by

wt=ua​1Mτ,ct\+δτ,ct\+ub​exp⁡\(−α​h​\(nt\)h​\(n1\)\),w\_\{t\}=u\_\{a\}\\frac\{1\}\{M\_\{\\tau,c\_\{t\}\}\+\\delta\_\{\\tau,c\_\{t\}\}\}\+u\_\{b\}\\exp\\left\(\-\\alpha\\frac\{h\(n\_\{t\}\)\}\{h\(n\_\{1\}\)\}\\right\),\(8\)wherectc\_\{t\}is the color associated withntn\_\{t\},Mτ,ctM\_\{\\tau,c\_\{t\}\}andδτ,ct\\delta\_\{\\tau,c\_\{t\}\}follow the same definition as in Equation[6](https://arxiv.org/html/2605.30664#S3.E6), anduau\_\{a\}andubu\_\{b\}are mixing coefficients\. Unless stated otherwise,lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}usesua=ub=1u\_\{a\}=u\_\{b\}=1\. As before, we setw1=1w\_\{1\}=1for the root node\. See Algorithm[3](https://arxiv.org/html/2605.30664#alg3)in Appendix[A](https://arxiv.org/html/2605.30664#A1)for its pseudocode\.

Additive Rerooter Guarantees\. The hybrid rerooter in Equation[8](https://arxiv.org/html/2605.30664#S3.E8)is not only a pragmatic way to blend rerooters, it also has a principled effect on howlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}allocates effort across subtasks\. Intuitively, adding rerooters allows the search to fall back on whichever signal is informative in a given region of the tree, provided the combination remains balanced so that one component does not dominate the overall time allocation\. The following result makes this precise by extending the standard subtask\-decomposition bound\.

###### Theorem 3\.2\.

Letwaw\_\{a\}andwbw\_\{b\}be two rerooters, with relative weightsua≥0u\_\{a\}\\geq 0andub≥0u\_\{b\}\\geq 0\. Letw=ua​wa\+ub​wbw=u\_\{a\}w\_\{a\}\+u\_\{b\}w\_\{b\}be the rerooter used bylts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\. When visiting the nodenTn\_\{T\}at stepTT, for anyC≥1C\\geq 1satisfying1C≤ua​wa,<Tub​wb,<T≤C\\frac\{1\}\{C\}\\leq\\frac\{u\_\{a\}w\_\{a,<T\}\}\{u\_\{b\}w\_\{b,<T\}\}\\leq C, then the number of node visits is bounded by

T≤1\+\(C\+1\)×minD∈𝒟​\(n∗\)⁡maxi<\|D\|⁡min⁡\{wa,<Twa,Ti,wb,<Twb,Ti\}​cTir​\(nTi\+1\)\.T\\leq 1\+\(C\+1\)\\times\\\\ ~\\min\_\{D\\in\\mathcal\{D\}\(n^\{\*\}\)\}~~\\max\_\{i<\|D\|\}~\\min\\left\\\{\\frac\{w\_\{a,<T\}\}\{w\_\{a,T\_\{i\}\}\},~\\frac\{w\_\{b,<T\}\}\{w\_\{b,T\_\{i\}\}\}\\right\\\}\\,c^\{r\}\_\{T\_\{i\}\}\(n\_\{T\_\{i\+1\}\}\)\.

The proof is in Appendix[J](https://arxiv.org/html/2605.30664#A10)\. The constantC≥1C\\geq 1can be controlled by adjusting the weightsuau\_\{a\}andubu\_\{b\}\.

## 4Experiments

The goal of our experimental evaluation is twofold\. First, we aim to establish rerooting as a flexible and scalable abstraction for exploiting structural information in policy tree search, avoiding explicit subgoal generation and reasoning while retaining much of their benefit through simple structural signals\. Second, we evaluate the practical impact of rerooting on learning efficiency by measuring improvements in online training sample efficiency relative to non\-rerooted baselines across a range of domains\.

### 4\.1Baselines

We compare our methods against LTS\(Orseauet al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib3)\), as at the time of this writing, there are no comprehensive empirical evaluations oflts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}variants against LTS\. We also compare againstLTS​\(πSG\)\\text\{LTS\}\(\\pi^\{\\text\{SG\}\}\)andPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\), two SGPS instantiations that can be trained online and use the same clustering method aslts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}\. SGPS is a key baseline because it \(i\) shares the same clustering component, \(ii\) generates discrete subgoals via a VQ\-VAE\(Van Den Oordet al\.,[2017](https://arxiv.org/html/2605.30664#bib.bib35)\)whereas our approach uses soft subtasks without explicit subgoal generation, and \(iii\) achieved state\-of\-the\-art results on the domains we consider\. Finally, we include Weighted A\* \(WA\*\)\(Pohl,[1970](https://arxiv.org/html/2605.30664#bib.bib23)\), a non\-policy method that can be trained online via the bootstrap process\. We use a weight of1\.51\.5for WA\*, which performs well in similar settings\(Orseau and Lelis,[2021](https://arxiv.org/html/2605.30664#bib.bib4); Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\)\. We omitHIPS\-ε\\varepsilonbecause it requires a solution dataset which is unavailable for the complex environment studied, and prior work foundLTS​\(πSG\)\\text\{LTS\}\(\\pi^\{\\text\{SG\}\}\)andPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)outperformed it\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\)\.

### 4\.2Environment Domains

BoulderDash: The agent collects a number of diamonds to unlock the exit\. Some diamonds are locked in rooms that require a key\. The environment contains dirt cells, which disappear when the agent walks over them, resulting in complex state observations and a large search space\.Tueroet al\.\([2025](https://arxiv.org/html/2605.30664#bib.bib5)\)provided a*standard*problem set and a*hard*problem set, and we use the more challenging hard problems in our analysis\.

CraftWorld: The agent collects raw materials and interacts with workbenches and furnaces to craft intermediary items, which can further be crafted into final products\(Andreaset al\.,[2017](https://arxiv.org/html/2605.30664#bib.bib20)\)\. The environment can be in a deadlocked state by crafting an incorrect item, since items are consumed once used in a recipe\. Similar to BoulderDash, we use the*hard*problems fromTueroet al\.\([2025](https://arxiv.org/html/2605.30664#bib.bib5)\)\.

Sokoban: The agent must push boxes into designated goal locations, avoiding deadlocks due to boxes getting stuck along walls\. Sokoban is PSPACE\-hard\(Culberson,[1997](https://arxiv.org/html/2605.30664#bib.bib36)\), and we use the first 50,000 training problems and 1,000 test problems from Boxoban\(Guezet al\.,[2018](https://arxiv.org/html/2605.30664#bib.bib21)\)\.

Traveling Salesman Problem \(TSP\): A gridworld version of the TSP where the agent must visit specified city locations, then return to the starting location\. To increase the difficulty of this domain, we use a modified version in which the agent deadlocks if it revisits a city other than the start city\. This prevents trivial solutions such as blindly visiting each city without planning the steps in between cities\.

### 4\.3Training and Testing Procedure

All methods use Bootstrap training\(Arfaeeet al\.,[2011](https://arxiv.org/html/2605.30664#bib.bib22)\)\. We randomly initialize neural networks for the policy and/or heuristic, then run each search algorithm on a subset of training problems with an initial expansion budget using the current policy/heuristic\. Algorithms update their policy/heuristic from solution trajectories on solved problems\. If an algorithm solves no new problems in a sweep over the training set, we increase the expansion budget and repeat the sweep\. After each sweep, we evaluate on a separate validation set under the current budget; training ends once at least 95% of validation problems are solved\. To handle methods which struggle to make progress, we impose a maximum training time of 1,000,000 seconds \(approximately 11\.5 CPU\-days\), stopping once this limit is reached\. Reported time is the sum of time each algorithm uses on each problem, over all the threads used during training\. Additional details are in Appendix[C](https://arxiv.org/html/2605.30664#A3)and Appendix[D](https://arxiv.org/html/2605.30664#A4)\.

Each domain uses 10,000 training problems and 1,000 validation problems, except Sokoban \(49,000 training and 1,000 validation\)\. We repeat training over 5 seeds, which determine network initialization and the train/validation splits\. For training\-efficiency plots, we report the min/mean/max number of outstanding problems versus expansions and wall\-clock time\. For final evaluation, we test on a held\-out test set with a budget of 512,000 node expansions and report \(averaged over seeds\) problems solved, expansions\-to\-solution, solution length, and wall\-clock time\.

### 4\.4Results

Table 1:Test results averaged over all seeds\. Time measures the sum an algorithm spends on each problem across all threads used during training, in seconds\.Table 2:Training results averaged over increasing complexity BoulderDash environments\. NPS stands for nodes per second, and time is measured in hours\.Search Efficiency\. Across all domains \(Figure[2](https://arxiv.org/html/2605.30664#S3.F2)\), our hybrid rerooter substantially improves the bootstrap training efficiency over LTS and prior subgoal\-generation approaches; comparisons among thelts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}rerooter variants are discussed separately below\. The results highlight the value of combining the rerooters: In BoulderDash,lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}is effective andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}matches its performance\. The remaining domains, Sokoban, CraftWorld, and TSP, all contain deadlock structure, where purely heuristic guidance can be less stable\. In these domains,lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}remains competitive but exhibits greater variability, suggesting that the learned heuristic can sometimes overcommit search effort to misleading regions of the tree during bootstrap training\. This effect is most pronounced in CraftWorld and TSP; in these environments, WA\* also requires substantially more time to complete training\. By contrast,lts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}is both the strongest and most stable method in these domains, indicating that the hybrid rerooter benefits from the heuristic signal when it is useful while retaining the structural robustness of the clustering rerooterlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}when the heuristic is unreliable\.lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}substantially outperformsLTS​\(πSG\)\\text\{LTS\}\(\\pi^\{\\text\{SG\}\}\)despite both using the same clustering technique and neither using heuristics\. The cost\-to\-go rerooterlts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}outperforms WA\* in every domain except Sokoban\. Runtime measurements further support Theorem[3\.1](https://arxiv.org/html/2605.30664#S3.Thmtheorem1): while all methods share BFS\-style asymptotic complexity, our rerooters incur the lowest overhead in practice\. Together, these results isolate the effect of rerooting, showing that gains come from how structural information is exploited, not clustering alone, and that our rerooters scale reliably across diverse domains\. For the full table of results from Figure[2](https://arxiv.org/html/2605.30664#S3.F2), see Table[8](https://arxiv.org/html/2605.30664#A11.T8)in Appendix[K](https://arxiv.org/html/2605.30664#A11)\.

Test Results\. To assess whether the training speedup degrades solution quality, we evaluate the trained models on held\-out test problems \(100 per domain; 1,000 for Sokoban; Table[1](https://arxiv.org/html/2605.30664#S4.T1)\)\. Methods that failed to complete training perform substantially worse, since their policies and heuristics remain largely uninformed\. Despite faster training, our rerooting methods achieve comparable test performance to prior approaches, indicating that the efficiency gains do not come at the expense of learned policy quality\. Moreover,lts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}consistently outperforms the clustering\-only rerooterlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}at test time, suggesting that combining global structure with local heuristic information improves generalization\. In TSP and Sokoban, our rerooting methods require more node expansions thanPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)in both and WA\* in Sokoban\. We suspect this reflects weaker state\-space clustering structure in these environments, and in Appendix[I](https://arxiv.org/html/2605.30664#A9)we perform an analysis to verify this conjecture\.

Environment Domain Complexity Scaling\. To test whether subgoal\-based policy tree search methods likePHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)scale poorly as problem complexity increases, we run a training\-efficiency experiment on BoulderDash while varying the fraction of dirt tiles which are task irrelevant elements that substantially enlarge the state\-space\.

As complexity increases,PHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)times out and makes no progress once levels contain 30% or more dirt elements \(Table[2](https://arxiv.org/html/2605.30664#S4.T2)\)\. We attribute this to its reliance on reconstructing grounded future states as subgoals: additional dirt shifts the reconstruction objective toward visually dense but task\-irrelevant structure, diverting capacity from critical elements such as keys or diamonds\. AlthoughLTS​\(πSG\)\\text\{LTS\}\(\\pi^\{\\text\{SG\}\}\)andPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)are more robust than earlier subgoal\-based methods likeHIPS\-ε\\varepsilonto invalid subgoal predictions\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\), their low\-level policies are still conditioned on generated subgoals, making learning increasingly brittle as state complexity grows\.

In contrast,lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}scales better by avoiding explicit subgoal reconstruction, though it eventually reaches a complexity threshold where training does not complete\.lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}remain robust across all tested levels, completing training even in the hardest settings with comparable performance\. For an analysis for whylts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}does not scale as well as compared tolts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}, see Appendix[I](https://arxiv.org/html/2605.30664#A9)for ablations on how the percentage of dirt elements affects the quality of the clusters found\. Overall, implicitly representing subtasks via rerooting scales substantially better than conditioning policies on explicitly generated subgoals\.

## 5Related Work

Subgoal Search\. Prior work has represented these through fixed\-length subtasks\(Czechowskiet al\.,[2021](https://arxiv.org/html/2605.30664#bib.bib11)\), multi\-model approaches that represent different subtask lengths by training a separate fixed\-horizon model for each length\(Zawalskiet al\.,[2022](https://arxiv.org/html/2605.30664#bib.bib12)\), and performing a high\-level search in subgoal\-space using a subgoal generator model for varying\-length subgoals\(Kujanpääet al\.,[2023](https://arxiv.org/html/2605.30664#bib.bib13)\)\. While these approaches show promising results, they all suffer from a lack of completeness,i\.e\., neither are guaranteed to find a solution even if one exists\.HIPS\-ε\\varepsilon\(Kujanpääet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib14)\)added completeness guarantees by augmenting the search space to include both subgoals and atomic actions\. Subgoal Guided Policy Heuristic Search \(SGPS\)\(Tueroet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib5)\)generates subgoals likeHIPS\-ε\\varepsilonbut performs search over atomic actions\. The generated subgoals are used to condition low\-level policies, which are mixed with a high\-level subgoal policy to produce a single policy usable by LTS orPHS\*\. A novelty of SGPS is that it can be trained online using the data from the search tree, even when a budget for the search causes early termination with no solution found\. BothHIPS\-ε\\varepsilonand SGPS are reliant on generated subgoals, and the performance of the search becomes tightly coupled to the quality of subgoal reconstruction and the policies conditioned on them\. As shown in our experiments, this becomes an issue when scaling to complex domains\.

State\-Space Structure for Search Control\. A complementary line of work leverages structural regularities in the state space, often via partitions or region abstractions, to guide how search allocates effort\. Cartesian Counterexample\-Guided Abstraction Refinement\(Clarkeet al\.,[2000](https://arxiv.org/html/2605.30664#bib.bib31); Seipp and Helmert,[2013](https://arxiv.org/html/2605.30664#bib.bib32)\)guides search in cost\-optimal planning through iteratively refining abstractions\. Recent work improves refinement strategies\(Speck and Seipp,[2022](https://arxiv.org/html/2605.30664#bib.bib33)\)and ways of combining multiple abstractions for stronger heuristics\(Salernoet al\.,[2025](https://arxiv.org/html/2605.30664#bib.bib34)\)\. In the options framework\(Suttonet al\.,[1999](https://arxiv.org/html/2605.30664#bib.bib26)\), methods exploit connectivity and bottleneck structure to create temporally extended actions that reduce planning complexity\. This includes using entropy to discover skills that capture key transition patterns in the state\-space\(Zenget al\.,[2023](https://arxiv.org/html/2605.30664#bib.bib27),[2025](https://arxiv.org/html/2605.30664#bib.bib30)\), and state\-space clustering\(Agostinelliet al\.,[2019](https://arxiv.org/html/2605.30664#bib.bib28); Rameshet al\.,[2019](https://arxiv.org/html/2605.30664#bib.bib29)\)\. In contrast, we exploit structure only to steer the search effort through rerooting, without constructing abstractions for heuristic computation or learning temporally extended actions\.

## 6Conclusions

In this work, we examined rerooting as a general mechanism for exploiting structure in policy tree search and demonstrated its effectiveness across a range of instantiations\. We introduced two complementary rerooters, and showed how they can be combined to take advantage of the benefits each provides while offsetting each of their downsides\. Our rerooter achieves state\-of\-the\-art performance in online training efficiency when using the bootstrap approach, foregoing the need to rely on costly subgoal generation models and state reconstruction\. Our results show that rerooting enables scalable and efficient search control by implicitly representing subtasks through weighted root selection rather than explicit subgoal reconstruction\.

Perhaps surprisingly, a simple heuristic\-based rerooter often outperforms a clustering\-based alternative despite relying on substantially less structural information, highlighting that lightweight local signals can be sufficient to guide effective rerooting\. At the same time, the heuristic rerooter is not without limitations: under certain conditions, normalization effects can cause rerooting weights to collapse, leading to degraded performance\. The hybrid rerooter addresses this tradeoff by combining global structural guidance with local heuristic information, achieving performance close to the heuristic\-based approach while being robust across domains\.

Together, these findings position rerooting as a flexible and practical abstraction, and suggest that combining complementary structural signals offers a reliable path toward scalable policy tree search\. We have demonstrated thatlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}with a simple transformation of the classical heuristic*cost\-to\-go*can be very efficient\. We have also successfully combined two rerooters\. This opens the door to incorporating different types of side information to define more capable rerooters\.

## Acknowledgements

This research was supported by Canada’s NSERC and the CIFAR AI Chairs program\. This research was enabled in part by support provided by the Digital Research Alliance of Canada\. The authors thank the anonymous reviewers for valuable feedback on this work\.

## Impact Statement

This work advances the field of machine learning by developing practical rerooting mechanisms that improve how policy\-guided tree search allocates effort in hard single\-agent problems\. Our contributions are primarily technical and evaluated in game\-like domains, but the core ideas may transfer to broader planning and decision\-making settings over time\. We do not foresee immediate societal harms, but any real\-world use should follow established ethical and safety practices\.

## References

- A\. Agostinelli, K\. Arulkumaran, M\. Sarrico, P\. Richemond, and A\. A\. Bharath \(2019\)Memory\-efficient episodic control reinforcement learning with dynamic online k\-means\.arXiv preprint arXiv:1911\.09560\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- J\. Andreas, D\. Klein, and S\. Levine \(2017\)Modular multitask reinforcement learning with policy sketches\.InInternational conference on machine learning,Cited by:[§4\.2](https://arxiv.org/html/2605.30664#S4.SS2.p2.1)\.
- S\. J\. Arfaee, S\. Zilles, and R\. C\. Holte \(2011\)Learning heuristic functions for large state spaces\.Artificial Intelligence175\(16\-17\),pp\. 2075–2098\.Cited by:[§4\.3](https://arxiv.org/html/2605.30664#S4.SS3.p1.1)\.
- V\. D\. Blondel, J\. Guillaume, R\. Lambiotte, and E\. Lefebvre \(2008\)Fast unfolding of communities in large networks\.Journal of statistical mechanics: theory and experiment2008\(10\)\.Cited by:[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p2.17)\.
- M\. M\. Botvinick, Y\. Niv, and A\. G\. Barto \(2009\)Hierarchically organized behavior and its neural foundations: a reinforcement learning perspective\.Cognition113\(3\),pp\. 262–280\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p2.1)\.
- E\. Clarke, O\. Grumberg, S\. Jha, Y\. Lu, and H\. Veith \(2000\)Counterexample\-guided abstraction refinement\.InInternational Conference on Computer Aided Verification,Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- C\. G\. Correa, M\. K\. Ho, F\. Callaway, N\. D\. Daw, and T\. L\. Griffiths \(2023\)Humans decompose tasks by trading off utility and computational cost\.PLoS computational biology19\(6\)\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p2.1)\.
- J\. Culberson \(1997\)Sokoban is PSPACE\-complete\.Cited by:[§4\.2](https://arxiv.org/html/2605.30664#S4.SS2.p3.1)\.
- K\. Czechowski, T\. Odrzygóźdź, M\. Zbysiński, M\. Zawalski, K\. Olejnik, Y\. Wu, Ł\. Kuciński, and P\. Miłoś \(2021\)Subgoal search for complex reasoning tasks\.Advances in Neural Information Processing Systems\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p1.3)\.
- F\. Donnarumma, D\. Maisto, and G\. Pezzulo \(2016\)Problem solving as probabilistic inference with subgoaling: explaining human successes and pitfalls in the tower of hanoi\.PLoS computational biology12\(4\)\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p2.1)\.
- J\. B\. Evans and Ö\. Şimşek \(2023\)Creating multi\-level skill hierarchies in reinforcement learning\.InThirty\-seventh Conference on Neural Information Processing Systems,Cited by:[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p4.1)\.
- A\. Guez, M\. Mirza, K\. Gregor, R\. Kabra, S\. Racaniere, T\. Weber, D\. Raposo, A\. Santoro, L\. Orseau, T\. Eccles, G\. Wayne, D\. Silver, T\. Lillicrap, and V\. Valdes \(2018\)An investigation of model\-free planning: boxoban levels\.Cited by:[§4\.2](https://arxiv.org/html/2605.30664#S4.SS2.p3.1)\.
- K\. He, X\. Zhang, S\. Ren, and J\. Sun \(2016\)Deep residual learning for image recognition\.InProceedings of the IEEE conference on computer vision and pattern recognition,Cited by:[Appendix D](https://arxiv.org/html/2605.30664#A4.p1.6)\.
- E\. Karpas, O\. Betzalel, S\. E\. Shimony, D\. Tolpin, and A\. Felner \(2018\)Rational deployment of multiple heuristics in optimal state\-space search\.Artificial Intelligence256,pp\. 181–210\.Cited by:[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p6.7)\.
- D\. P\. Kingma \(2014\)Adam: a method for stochastic optimization\.arXiv preprint arXiv:1412\.6980\.Cited by:[Appendix D](https://arxiv.org/html/2605.30664#A4.p1.6)\.
- K\. Kujanpää, J\. Pajarinen, and A\. Ilin \(2023\)Hierarchical imitation learning with vector quantized models\.InInternational Conference on Machine Learning,Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p1.3)\.
- K\. Kujanpää, J\. Pajarinen, and A\. Ilin \(2024\)Hybrid search for efficient planning with completeness guarantees\.Advances in Neural Information Processing Systems\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p2.1),[§5](https://arxiv.org/html/2605.30664#S5.p1.3)\.
- V\. Narayanan and M\. Likhachev \(2017\)Heuristic search on graphs with existence priors for expensive\-to\-evaluate edges\.InProceedings of the International Conference on Automated Planning and Scheduling,Cited by:[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p6.7)\.
- L\. Orseau, M\. Hutter, and L\. H\. Lelis \(2024\)Exponential speedups by rerooting levin tree search\.arXiv preprint arXiv:2412\.05196\.Cited by:[Example J\.1](https://arxiv.org/html/2605.30664#A10.Thmtheorem1.p1.9),[Appendix B](https://arxiv.org/html/2605.30664#A2.p2.9),[§1](https://arxiv.org/html/2605.30664#S1.p3.3),[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p3.6),[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p4.18),[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p4.28),[§3](https://arxiv.org/html/2605.30664#S3.p1.1)\.
- L\. Orseau and L\. H\. Lelis \(2021\)Policy\-guided heuristic search with guarantees\.InProceedings of the AAAI Conference on Artificial Intelligence,Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p1.1),[§2\.2](https://arxiv.org/html/2605.30664#S2.SS2.p1.12),[§4\.1](https://arxiv.org/html/2605.30664#S4.SS1.p1.8)\.
- L\. Orseau, L\. Lelis, T\. Lattimore, and T\. Weber \(2018\)Single\-agent policy tree search with guarantees\.Advances in Neural Information Processing Systems\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p1.1),[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p2.2),[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p2.3),[§4\.1](https://arxiv.org/html/2605.30664#S4.SS1.p1.8)\.
- A\. Paszke, S\. Gross, F\. Massa, A\. Lerer, J\. Bradbury, G\. Chanan, T\. Killeen, Z\. Lin, N\. Gimelshein, L\. Antiga, A\. Desmaison, A\. Kopf, E\. Yang, Z\. DeVito, M\. Raison, A\. Tejani, S\. Chilamkurthy, B\. Steiner, L\. Fang, J\. Bai, and S\. Chintala \(2019\)PyTorch: an imperative style, high\-performance deep learning library\.InAdvances in Neural Information Processing Systems 32,Cited by:[Appendix C](https://arxiv.org/html/2605.30664#A3.p1.1)\.
- J\. Pearl \(1984\)Heuristics: intelligent search strategies for computer problem solving\.Addison\-Wesley Longman Publishing Co\., Inc\.\.Cited by:[§2\.1](https://arxiv.org/html/2605.30664#S2.SS1.p1.1)\.
- I\. Pohl \(1970\)Heuristic search viewed as path finding in a graph\.Artificial intelligence1\(3\-4\),pp\. 193–204\.Cited by:[§4\.1](https://arxiv.org/html/2605.30664#S4.SS1.p1.8)\.
- R\. Ramesh, M\. Tomar, and B\. Ravindran \(2019\)Successor options: an option discovery framework for reinforcement learning\.arXiv preprint arXiv:1905\.05731\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- S\. Sahu, K\. Kothapalli, and D\. S\. Banerjee \(2024\)Fast leiden algorithm for community detection in shared memory setting\.InProceedings of the 53rd International Conference on Parallel Processing,Cited by:[Appendix B](https://arxiv.org/html/2605.30664#A2.p3.15)\.
- M\. Salerno, R\. Fuentetaja, D\. Speck, and J\. Seipp \(2025\)Merging Cartesian abstractions for classical planning\.InProceedings of the 28th European Conference on Artificial Intelligence \(ECAI 2025\),I\. Lynce and A\. Murano \(Eds\.\),Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- J\. Seipp and M\. Helmert \(2013\)Counterexample\-guided cartesian abstraction refinement\.InProceedings of the International Conference on Automated Planning and Scheduling,Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- D\. Speck and J\. Seipp \(2022\)New refinement strategies for cartesian abstractions\.InProceedings of the International Conference on Automated Planning and Scheduling,Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- R\. S\. Sutton, D\. Precup, and S\. Singh \(1999\)Between mdps and semi\-mdps: a framework for temporal abstraction in reinforcement learning\.Artificial intelligence112\(1\-2\),pp\. 181–211\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- V\. A\. Traag, L\. Waltman, and N\. J\. Van Eck \(2019\)From louvain to leiden: guaranteeing well\-connected communities\.Scientific reports9\(1\),pp\. 1–12\.Cited by:[§1](https://arxiv.org/html/2605.30664#S1.p4.1),[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p2.17)\.
- J\. Tuero, M\. Buro, and L\. Lelis \(2025\)Subgoal\-guided policy heuristic search with learned subgoals\.InForty\-second International Conference on Machine Learning,Cited by:[Appendix D](https://arxiv.org/html/2605.30664#A4.p1.6),[§1](https://arxiv.org/html/2605.30664#S1.p2.1),[§1](https://arxiv.org/html/2605.30664#S1.p4.1),[§2\.2](https://arxiv.org/html/2605.30664#S2.SS2.p1.12),[§3\.1](https://arxiv.org/html/2605.30664#S3.SS1.p9.1),[§4\.1](https://arxiv.org/html/2605.30664#S4.SS1.p1.8),[§4\.2](https://arxiv.org/html/2605.30664#S4.SS2.p1.1),[§4\.2](https://arxiv.org/html/2605.30664#S4.SS2.p2.1),[§4\.4](https://arxiv.org/html/2605.30664#S4.SS4.p4.4),[§5](https://arxiv.org/html/2605.30664#S5.p1.3)\.
- A\. Van Den Oord, O\. Vinyals,et al\.\(2017\)Neural discrete representation learning\.Advances in neural information processing systems\.Cited by:[§4\.1](https://arxiv.org/html/2605.30664#S4.SS1.p1.8)\.
- M\. Zawalski, M\. Tyrolski, K\. Czechowski, T\. Odrzygóźdź, D\. Stachura, P\. Piękos, Y\. Wu, Ł\. Kuciński, and P\. Miłoś \(2022\)Fast and precise: adjusting planning horizon with adaptive subgoal search\.arXiv preprint arXiv:2206\.00702\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p1.3)\.
- X\. Zeng, H\. Peng, A\. Li, C\. Liu, L\. He, and P\. S\. Yu \(2023\)Hierarchical state abstraction based on structural information principles\.arXiv preprint arXiv:2304\.12000\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.
- X\. Zeng, H\. Peng, D\. Su, and A\. Li \(2025\)Hierarchical decision making based on structural information principles\.Journal of Machine Learning Research26\(182\),pp\. 1–55\.Cited by:[§5](https://arxiv.org/html/2605.30664#S5.p2.1)\.

## Appendix ACompletelts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}Algorithm with Leiden and Heuristic Rerooters

Below details how thelts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\},lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}, andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}rerooters are integrated intolts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}search\. The policyπθ\\pi\_\{\\theta\}and heuristichωh\_\{\\omega\}are parameterized by neural networksθ\\thetaandω\\omegarespectively\.

Algorithm 1lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}1:Input:Root node

n1n\_\{1\}, budget

b\>0b\>0, policy

πθ\\pi\_\{\\theta\}, graph update factor

γ\>1\\gamma\>1, cluster level

kk
2:Output:Solution node, or status of failed search

3:

Q1←\{n1\}Q\_\{1\}\\leftarrow\\\{n\_\{1\}\\\}
4:

V0←\{n1\}V\_\{0\}\\leftarrow\\\{n\_\{1\}\\\},

E0←\{\}E\_\{0\}\\leftarrow\\\{\\\}
5:

t←1t\\leftarrow 1,

r←1r\\leftarrow 1,

τ←1\\tau\\leftarrow 1
6:while

Qt≠\{\}Q\_\{t\}\\neq\\\{\\\}and

t≤bt\\leq bdo

7:

nt=arg​minn∈Qt⁡minni≺n⁡1wi​\(∑ni≺n′⪯n1πθ​\(n′\|ni\)\)n\_\{t\}=\\operatorname\*\{arg\\,min\}\\limits\_\{n\\in Q\_\{t\}\}\\min\\limits\_\{n\_\{i\}\\prec n\}\\dfrac\{1\}\{w\_\{i\}\}\\left\(\\sum\\limits\_\{n\_\{i\}\\prec n^\{\\prime\}\\preceq n\}\\dfrac\{1\}\{\\pi\_\{\\theta\}\(n^\{\\prime\}\|n\_\{i\}\)\}\\right\)
8:if

is\_solution​\(nt\)\\texttt\{is\\\_solution\}\(n\_\{t\}\)then

9:return

ntn\_\{t\}
10:endif

11:// Find node’s color

12:if

is\_root​\(nt\)\\texttt\{is\\\_root\}\(n\_\{t\}\)then

13:

wt←1w\_\{t\}\\leftarrow 1
14:else

15:if

has\_color​\(nt\)\\texttt\{has\\\_color\}\(n\_\{t\}\)then

16:

ct←color​\(nt\)c\_\{t\}\\leftarrow\\texttt\{color\}\(n\_\{t\}\)
17:else

18:

ct←color​\(par​\(nt\)\)c\_\{t\}\\leftarrow\\texttt\{color\}\(\\texttt\{par\}\(n\_\{t\}\)\)
19:endif

20:

δτ,ct=\|\{ℓ:⌊γτ⌋<ℓ≤t,cℓ=ct\}\|\\delta\_\{\\tau,c\_\{t\}\}=\|\\\{\\ell:\\lfloor\\gamma^\{\\tau\}\\rfloor<\\ell\\leq t,\\ c\_\{\\ell\}=c\_\{t\}\\\}\|
21:

wt←1/\(Mτ,ct\+δτ,ct\)w\_\{t\}\\leftarrow 1/\\left\(M\_\{\\tau,c\_\{t\}\}\+\\delta\_\{\\tau,c\_\{t\}\}\\right\)
22:endif

23:// Incrementally update tree and induced graph

24:

Qt\+1←Qt\\\{nt\}∪𝒞​\(nt\)Q\_\{t\+1\}\\leftarrow Q\_\{t\}\\backslash\\\{n\_\{t\}\\\}\\cup\\mathcal\{C\}\(n\_\{t\}\)
25:

V0←V0∪𝒞​\(nt\)V\_\{0\}\\leftarrow V\_\{0\}\\cup\\mathcal\{C\}\(n\_\{t\}\)
26:

E0←E0∪\{\(nt,n′\):n′∈𝒞​\(nt\)\}E\_\{0\}\\leftarrow E\_\{0\}\\cup\\\{\(n\_\{t\},n^\{\\prime\}\):n^\{\\prime\}\\in\\mathcal\{C\}\(n\_\{t\}\)\\\}
27:// Clustering is expensive, we amortize the cost over the search steps using an exponential schedule

28:if

t=rt=rthen

29:// Cluster Step

30:

\{G1,…,GN\}←leiden​\(G0=\(V0,E0\)\)\\\{G\_\{1\},\\dots,G\_\{N\}\\\}\\leftarrow\\texttt\{leiden\}\(G\_\{0\}=\(V\_\{0\},E\_\{0\}\)\)
31:// Update node colors and color count map

32:

\(Vk,Ek\)←Gk\(V\_\{k\},E\_\{k\}\)\\leftarrow G\_\{k\}
33:for

i,Ui,Uinenumerate\(Vk\)\(V\_\{k\}\)do

34:for

vvin

UUdo

35:

color​\(v\)←i\\texttt\{color\}\(v\)\\leftarrow i
36:endfor

37:endfor

38:

Mτ\+1,c←\|\{v∈V0:color​\(v\)=c\}\|M\_\{\\tau\+1,c\}\\leftarrow\|\\\{v\\in V\_\{0\}:\\texttt\{color\}\(v\)=c\\\}\|for all

c∈\{1,…,\|Vk\|\}c\\in\\\{1,\\dots,\|V\_\{k\}\|\\\}
39:

r←⌈r∗γ⌉r\\leftarrow\\lceil r\*\\gamma\\rceil
40:

τ←τ\+1\\tau\\leftarrow\\tau\+1
41:endif

42:

t←t\+1t\\leftarrow t\+1
43:endwhile

44:returnFalse

Algorithm 2lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}1:Input:Root node

n1n\_\{1\}, budget

b\>0b\>0, policy

πθ\\pi\_\{\\theta\}, heuristic

hωh\_\{\\omega\}, heuristic temperature

α\\alpha
2:Output:Solution node, or status of failed search

3:

t←1t\\leftarrow 1
4:

Qt←\{n1\}Q\_\{t\}\\leftarrow\\\{n\_\{1\}\\\}
5:while

Qt≠\{\}Q\_\{t\}\\neq\\\{\\\}and

t≤bt\\leq bdo

6:

nt=arg​minn∈Qt⁡minni≺n⁡1wi​\(∑ni≺n′⪯n1πθ​\(n′\|ni\)\)n\_\{t\}=\\operatorname\*\{arg\\,min\}\\limits\_\{n\\in Q\_\{t\}\}\\min\\limits\_\{n\_\{i\}\\prec n\}\\dfrac\{1\}\{w\_\{i\}\}\\left\(\\sum\\limits\_\{n\_\{i\}\\prec n^\{\\prime\}\\preceq n\}\\dfrac\{1\}\{\\pi\_\{\\theta\}\(n^\{\\prime\}\|n\_\{i\}\)\}\\right\)
7:if

is\_solution​\(nt\)\\texttt\{is\\\_solution\}\(n\_\{t\}\)then

8:return

ntn\_\{t\}
9:endif

10:if

is\_root​\(nt\)\\texttt\{is\\\_root\}\(n\_\{t\}\)then

11:

wt←1w\_\{t\}\\leftarrow 1
12:else

13:

wt←exp⁡\(−α​hω​\(nt\)hω​\(n1\)\)w\_\{t\}\\leftarrow\\exp\\left\(\-\\alpha\\frac\{h\_\{\\omega\}\(n\_\{t\}\)\}\{h\_\{\\omega\}\(n\_\{1\}\)\}\\right\)
14:endif

15:

Qt\+1←Qt\\\{nt\}∪𝒞​\(nt\)Q\_\{t\+1\}\\leftarrow Q\_\{t\}\\backslash\\\{n\_\{t\}\\\}\\cup\\mathcal\{C\}\(n\_\{t\}\)
16:

t←t\+1t\\leftarrow t\+1
17:endwhile

18:returnFalse

Algorithm 3lts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}1:Input:Root node

n1n\_\{1\}, budget

b\>0b\>0, policy

πθ\\pi\_\{\\theta\}, graph update factor

γ\>1\\gamma\>1, cluster level

kk, heuristic temperature

α\\alpha, mixing coefficients

uau\_\{a\}and

ubu\_\{b\}\.

2:Output:Solution node, or status of failed search

3:

Q1←\{n1\}Q\_\{1\}\\leftarrow\\\{n\_\{1\}\\\}
4:

V0←\{n1\}V\_\{0\}\\leftarrow\\\{n\_\{1\}\\\},

E0←\{\}E\_\{0\}\\leftarrow\\\{\\\}
5:

t←1t\\leftarrow 1,

r←1r\\leftarrow 1,

τ←1\\tau\\leftarrow 1
6:while

Qt≠\{\}Q\_\{t\}\\neq\\\{\\\}and

t≤bt\\leq bdo

7:

nt=arg​minn∈Qt⁡minni≺n⁡1wi​\(∑ni≺n′⪯n1πθ​\(n′\|ni\)\)n\_\{t\}=\\operatorname\*\{arg\\,min\}\\limits\_\{n\\in Q\_\{t\}\}\\min\\limits\_\{n\_\{i\}\\prec n\}\\dfrac\{1\}\{w\_\{i\}\}\\left\(\\sum\\limits\_\{n\_\{i\}\\prec n^\{\\prime\}\\preceq n\}\\dfrac\{1\}\{\\pi\_\{\\theta\}\(n^\{\\prime\}\|n\_\{i\}\)\}\\right\)
8:if

is\_solution​\(nt\)\\texttt\{is\\\_solution\}\(n\_\{t\}\)then

9:return

ntn\_\{t\}
10:endif

11:// Find node’s color

12:if

is\_root​\(nt\)\\texttt\{is\\\_root\}\(n\_\{t\}\)then

13:

wt←1w\_\{t\}\\leftarrow 1
14:else

15:if

has\_color​\(nt\)\\texttt\{has\\\_color\}\(n\_\{t\}\)then

16:

ct←color​\(nt\)c\_\{t\}\\leftarrow\\texttt\{color\}\(n\_\{t\}\)
17:else

18:

ct←color​\(par​\(nt\)\)c\_\{t\}\\leftarrow\\texttt\{color\}\(\\texttt\{par\}\(n\_\{t\}\)\)
19:endif

20:

δτ,ct=\|\{ℓ:⌊γτ⌋<ℓ≤t,cℓ=ct\}\|\\delta\_\{\\tau,c\_\{t\}\}=\|\\\{\\ell:\\lfloor\\gamma^\{\\tau\}\\rfloor<\\ell\\leq t,\\ c\_\{\\ell\}=c\_\{t\}\\\}\|
21:

wt←ua​\(Mτ,ct\+δτ,ct\)−1\+ub​exp⁡\(−α​hω​\(nt\)hω​\(n1\)\)w\_\{t\}\\leftarrow u\_\{a\}\\left\(M\_\{\\tau,c\_\{t\}\}\+\\delta\_\{\\tau,c\_\{t\}\}\\right\)^\{\-1\}\+u\_\{b\}\\exp\\left\(\-\\alpha\\frac\{h\_\{\\omega\}\(n\_\{t\}\)\}\{h\_\{\\omega\}\(n\_\{1\}\)\}\\right\)
22:endif

23:// Incrementally update tree and induced graph

24:

Qt\+1←Qt\\\{nt\}∪𝒞​\(nt\)Q\_\{t\+1\}\\leftarrow Q\_\{t\}\\backslash\\\{n\_\{t\}\\\}\\cup\\mathcal\{C\}\(n\_\{t\}\)
25:

V0←V0∪𝒞​\(nt\)V\_\{0\}\\leftarrow V\_\{0\}\\cup\\mathcal\{C\}\(n\_\{t\}\)
26:

E0←E0∪\{\(nt,n′\):n′∈𝒞​\(nt\)\}E\_\{0\}\\leftarrow E\_\{0\}\\cup\\\{\(n\_\{t\},n^\{\\prime\}\):n^\{\\prime\}\\in\\mathcal\{C\}\(n\_\{t\}\)\\\}
27:// Clustering is expensive, we amortize the cost over the search steps using an exponential schedule

28:if

t=rt=rthen

29:// Cluster Step

30:

\{G1,…,GN\}←leiden​\(G0=\(V0,E0\)\)\\\{G\_\{1\},\\dots,G\_\{N\}\\\}\\leftarrow\\texttt\{leiden\}\(G\_\{0\}=\(V\_\{0\},E\_\{0\}\)\)
31:// Update node colors and color count map

32:

\(Vk,Ek\)←Gk\(V\_\{k\},E\_\{k\}\)\\leftarrow G\_\{k\}
33:for

i,Ui,Uinenumerate\(Vk\)\(V\_\{k\}\)do

34:for

vvin

UUdo

35:

color​\(v\)←i\\texttt\{color\}\(v\)\\leftarrow i
36:endfor

37:endfor

38:

Mτ\+1,c←\|\{v∈V0:color​\(v\)=c\}\|M\_\{\\tau\+1,c\}\\leftarrow\|\\\{v\\in V\_\{0\}:\\texttt\{color\}\(v\)=c\\\}\|for all

c∈\{1,…,\|Vk\|\}c\\in\\\{1,\\dots,\|V\_\{k\}\|\\\}
39:

r←⌈r∗γ⌉r\\leftarrow\\lceil r\*\\gamma\\rceil
40:

τ←τ\+1\\tau\\leftarrow\\tau\+1
41:endif

42:

t←t\+1t\\leftarrow t\+1
43:endwhile

44:returnFalse

## Appendix BProof of the Theorem[3\.1](https://arxiv.org/html/2605.30664#S3.Thmtheorem1)

In every search iteration, the following operations occur: the min\-cost node is removed from the priority queue, the rerooting weight is computed, and the children nodes are added back into the priority queue\.

Extracting the min\-cost node from a priority queue withMMitems isO​\(log⁡M\)O\(\\log M\)\. Computing the rerooting weight for the expanded node isO​\(d​\(n\)\)O\(d\(n\)\)with depthd​\(n\)d\(n\)\. Ifbbis the branching factor, then inserting thebbchildren into the priority queue isO​\(b​log⁡M\)O\(b\\log M\)\. The cost of each node is computed during insertion to the priority queue\. Equation[2](https://arxiv.org/html/2605.30664#S2.E2)requires a traversal of all ancestor nodes\. We note thatOrseauet al\.\([2024](https://arxiv.org/html/2605.30664#bib.bib6)\)show how this can be reduced to anO​\(1\)O\(1\)computation for most cases, but for the sake of this analysis we assume all ancestor node information is required\. OverNNsteps, the runtime for these computations is given by

O​\(∑i=1N\(1\+b\)​log⁡Mi\+di\),O\\left\(\\sum\_\{i=1\}^\{N\}\(1\+b\)\\log M\_\{i\}\+d\_\{i\}\\right\),\(9\)whereMiM\_\{i\}is the size of the priority queue at stepiianddid\_\{i\}is the depth of nodenin\_\{i\}\. SinceMi≤b​NM\_\{i\}\\leq bNanddi≤Dd\_\{i\}\\leq D, this simplifies toO​\(b​N​log⁡N\+N​D\)O\(bN\\log N\+N\\\!D\)\.

The frequency with which a Leiden clustering is performed follows a geometric series with common ratioγ\\gamma\. With a budgetNN, there are⌊logγ⁡\(N\)⌋\\lfloor\\log\_\{\\gamma\}\(N\)\\rfloorcalls toleiden\. The Leiden algorithm has a time complexity ofO​\(L​\|E\|\)O\(L\|E\|\), whereLLis the number of hierarchical cluster graphs created and\|E\|\|E\|is the number of edges in the input graph\(Sahuet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib19)\)\. Since the cluster levelL=kL=kis a constant, and the size of the edge set of the input graph is bounded by a constant factor of the size of the vertex set, each call toleidenhas complexityO​\(b​γk\)=O​\(γk\)O\(b\\gamma^\{k\}\)=O\(\\gamma^\{k\}\), whereγk\\gamma^\{k\}is the iterationleidenis called on a graph of sizeb​γkb\\gamma^\{k\}\. Over theNNsteps, the runtime for the calls toleidenis given by

O​\(∑i=0⌊logγ⁡N⌋b​γi\)=O​\(b​\(γ1\+logγ⁡N−1\)γ−1\)=O​\(b​N​γγ−1\),O\\left\(\\sum\_\{i=0\}^\{\\lfloor\\log\_\{\\gamma\}N\\rfloor\}b\\gamma^\{i\}\\right\)=O\\left\(\\frac\{b\\left\(\\gamma^\{1\+\\log\_\{\\gamma\}N\}\-1\\right\)\}\{\\gamma\-1\}\\right\)=O\\left\(\\frac\{bN\\gamma\}\{\\gamma\-1\}\\right\),\(10\)Which is linear so long asγ\>1\+1/ϵ\\gamma\>1\+1/\\epsilonwhereϵ\>0\\epsilon\>0is a constant\. Therefore, the overall runtime oflts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}isO​\(b​N​log⁡N\+N​D\)O\(bN\\log N\+N\\\!D\)as the additional cost of the Leiden algorithm has an amortized constant cost\.

## Appendix CImplementation and Machine Details

The algorithms and environment are implemented in C\+\+, adhering to the C\+\+23 standard\. The code111https://github\.com/tuero/siirlts2026is compiled using theGNU Compiler Collectionversion 15\.2\.0, and uses the PyTorch 2\.7 C\+\+frontend\(Paszkeet al\.,[2019](https://arxiv.org/html/2605.30664#bib.bib1)\)\. The Leiden clustering subroutine usesleidenalg222https://github\.com/vtraag/libleidenalg, an efficient open source implementation\. Where available, the official implementation of comparison methods are used\. All experiments used 8 threads for the bootstrap training and testing, and were conducted on an Intel i9\-7960X and Nvidia 3090, with 128GB of system memory running Ubuntu 24\.04\.

## Appendix DAdditional Experimental Details

During the online bootstrap training process, all algorithms start with an initial budget of 4,000 node expansions\. Batched inference is used during training, where generated nodes are placed into a queue before sending to the policy/heuristic networks for inference\. A batch size of 32 is used, with smaller batches being used if the open priority queue becomes empty before 32 additional nodes are generated\. In our experiments, all algorithms use ResNet\-based\(Heet al\.,[2016](https://arxiv.org/html/2605.30664#bib.bib24)\)networks\. Algorithms which use both a policy and heuristic use a single network with two heads\. The networks forWA\*,lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\},lts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}use 8 blocks of 128 ResNet channels, are trained using the Adam optimizer\(Kingma,[2014](https://arxiv.org/html/2605.30664#bib.bib25)\), with learning rate of 3E\-4 and L2\-regularization of 1E\-4\. The baselinesLTS​\(πSG\)\\text\{LTS\}\(\\pi^\{\\text\{SG\}\}\)andPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)are trained followingTueroet al\.\([2025](https://arxiv.org/html/2605.30664#bib.bib5)\)and use the open source implementation\.333https://github\.com/tuero/subgoal\-guided\-policy\-search

Forlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}, we use a graph update factor ofγ=1\.2\\gamma=1\.2for the geometric schedule for when the Leiden clustering procedure is run\. We use a cluster levelk=Nk=N\. Forlts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}, we useα=10\\alpha=10for the inverse\-temperature heuristic parameter\. For an ablation on the impact of the value ofα\\alphaused, see Appendix[H](https://arxiv.org/html/2605.30664#A8)\. All reported results useua=ub=1u\_\{a\}=u\_\{b\}=1forlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}\. For a sensitivity analysis on having balanced rerooters, see Appendix[G](https://arxiv.org/html/2605.30664#A7)\.

## Appendix EAblation: Impact of Clustering Level

The Leiden clustering algorithm takes a base graphG0G\_\{0\}and produces a hierarchy of cluster graph\{G1,…,GN\}\\\{G\_\{1\},\\dots,G\_\{N\}\\\}\. The selected graph at levelk∈\[1,N\]k\\in\[1,N\]influences what structures are used when coloring nodes, which the rerooterslts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}use to compute their rerooting weights\.

Table 3:Training results oflts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}over the BoulderDash 20% environments of varying cluster levels\.Table[3](https://arxiv.org/html/2605.30664#A5.T3)shows the bootstrap training loss forlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}over the BoulderDash 20% dirt environment of varying cluster levels\. A cluster level ofk=N/2k=N/2which corresponds to half the number of cluster graphs completes training in the fewest number of expansions and time, but usingk=Nk=Nis also competitive\. We note that this will be dependent on the implementation of the Leiden algorithm being used as different approximations and optimizations can be used\. See Appendix[C](https://arxiv.org/html/2605.30664#A3)for details and the specific implementation used\.

## Appendix FAblation: Impact of Graph Update Frequency

The cluster graphs from the Leiden algorithm are built using an update schedule which follows a geometric growth strategy with factorγ\\gamma\. How frequently the graphs are updated will have two major consequences\. One is the overall speed of the algorithm, where using a smallerγ\\gammawill result in more graphs being built under a fixed budget\. Creating cluster graphs more frequently means that more time is spent in theleidenprocedure than actually running the search, resulting in a lower number of nodes\-per\-second which can be achieved\. The second is that using a largerγ\\gammameans that there will be more expansions between graph updates, with a larger percentage of those nodes being generated after the most recent cluster graph\. If a node is expanded which does not have a color assigned to it \(as is the case when an expanded node was generated after the most recent graph clustering\), then an approximation is used where we assume that node gets the same color as its parent\. A largerγ\\gammameans that a larger percentage of the nodes will have an approximated color\.

Table 4:Test results oflts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}on the Sokoban environment of varying cluster graph update factors\.Table[4](https://arxiv.org/html/2605.30664#A6.T4)shows the test results of using the same trained policy on the Sokoban environment, but with varying values ofγ\\gamma\. In general, asγ\\gammaincreases, the nodes per second that the algorithm can achieve increases\. We also see that asγ\\gammadecreases, the number of expansions decreases, as expected, because because the rerooter can make greater use of the underlying state\-space structure to assign informative weights rather than relying on approximations\.

## Appendix GAblation: Balanced Rerooters

The constantC≥1C\\geq 1in Theorem[3\.2](https://arxiv.org/html/2605.30664#S3.Thmtheorem2)signals that the bound is related to how*balanced*the two sub\-rerooter components are\. Some natural questions to ask are how balanced are the two sub\-rerooters inlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}, and how sensitive are the observed node expansions to the factorCCin Theorem[3\.2](https://arxiv.org/html/2605.30664#S3.Thmtheorem2)\.

To answer these questions, we ran an additional sensitivity study in Sokoban, fixingub=1u\_\{b\}=1and varyinguau\_\{a\}, which are the*weighting*applied to each sub\-rerooter component\. These results are summarized in Table[5](https://arxiv.org/html/2605.30664#A7.T5)\. Performance varies only modestly across a broad range of ratios, suggesting that the hybrid rerooter is not highly sensitive to exact tuning\. The best results occur when the two signals are roughly balanced,i\.e\., whenwa,<T/wb,<T≈1w\_\{a,<T\}/w\_\{b,<T\}\\approx 1\. In practice,ua=ub=1u\_\{a\}=u\_\{b\}=1is a good default\. One can then inspect the observed ratiowa,<T/wb,<Tw\_\{a,<T\}/w\_\{b,<T\}and rescale if needed, but fine\-tuning is not critical\.

Table 5:Sensitivity analysis of unbalanced rerooters\.lts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}is tested on the Sokoban environment, with varying ratios ofuau\_\{a\}toubu\_\{b\}\. Time is measured in seconds\.
## Appendix HAblation: Heuristic Rerooter Temperature

The parameterα\\alphainlts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}acts as an inverse\-temperature parameter\. Whenα\\alphais small, the weights are more similar across nodes, so the rerooter behaves conservatively\. Asα\\alphaincreases, the weight mass becomes more concentrated on nodes whose heuristic values are small relative to the root, causing rerooting to focus more aggressively on regions that appear to have made substantial progress toward a goal\.

Table[6](https://arxiv.org/html/2605.30664#A8.T6)shows the result of varying theα\\alphainverse\-temperature parameter on the Sokoban environment for thelts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}algorithm\. The same trained policy and heuristic networks were used for all test runs, with\(ua,ub\)=\(0\.60,1\.00\)\(u\_\{a\},u\_\{b\}\)=\(0\.60,1\.00\)as this level of mixing resulted in balanced rerooters, as shown in Appendix[G](https://arxiv.org/html/2605.30664#A7)\. The value ofα=10\\alpha=10solves the Sokoban test problems in the fewest number of expansions, which is the value ofα\\alphaused in all other experiments\. Asα\\alphadecreases towards 1, the number of expansions increases due to the rerooting weight contribution from the heuristic rerooter being similar across all nodes\. Larger values ofα\\alphaallows the search to focus on areas of the tree where progress is being made towards the goal\. However, ifα\\alphabecomes too large, then the search can overcommit to what seems like progress being made but what could be a deadlocked subtree\.

Table 6:Sensitivity analysis of heuristic inverse\-temperature parameter\.lts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}is tested on the Sokoban environment, with varying values ofα\\alpha\. Time is measured in seconds\.
## Appendix IAblation: Analysis of Clustering\-based Rerooters

From the results in Table[1](https://arxiv.org/html/2605.30664#S4.T1)and Table[2](https://arxiv.org/html/2605.30664#S4.T2),lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}can perform quite a bit worse thanlts​\-H\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-H\}\}\}\}andlts​\-LH\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-LH\}\}\}\}\. The usefulness of the information provided by the clusters found whichlts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}relies on depends on the underlying structure of the state\-space\. The clustering rerooter is most effective when the induced state graph has well\-separated regions connected by narrow bottlenecks, because entering a new cluster then signals genuine progress\. When comparing againstPHS\*​\(πSG\)\\text\{PHS\*\}\(\\pi^\{\\text\{SG\}\}\)in Table[1](https://arxiv.org/html/2605.30664#S4.T1),lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}performs relatively worse in the Sokoban and TSP GridWorld environments\. Sincelts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}reached the time limit during training on the CraftWorld environment and did not fully complete the bootstrap process, we omit from this analysis\. In Table[2](https://arxiv.org/html/2605.30664#S4.T2), as the complexity of the BoulderDash environments increases,lts​\-L\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\{\\mathrm\{\\textnormal\{\{\-L\}\}\}\}continues to degrade relative to the other rerooters\.

Table 7:Average number of edges crossing different clusters\. A lower value indicates sharper separation between clusters\.To quantify this, we measured the average number of edges crossing each cluster boundary in the induced state graph, averaged over problems\. Lower values indicate sharper separation\. These results are given in Table[7](https://arxiv.org/html/2605.30664#A9.T7)\. Under this metric, BoulderDash exhibits a clear progression as the domain becomes less structured, CraftWorld remains relatively low, Sokoban and TSP are substantially higher\. In Sokoban, this helps explain why the clustering rerooter is less effective than the strongest baselines, and in TSP, the very large value is consistent with the strongest degradation, where the clustering rerooter requires nearly twice as many expansions as the heuristic/hybrid rerooters \(despite both test\-time results being overall low\)\. Overall, these results support our claim that the usefulness of clustering\-based rerooting depends strongly on the presence of sharp, bottleneck\-like state\-space structure, and that this metric provides a quantitative way to characterize when that structure is present or absent\.

## Appendix JAdditive Rerooters

In this section we demonstrate how additive rerooters can take advantage not just of the best of the sub\-rerooters, but more importantly of the*synergy*of the sub\-rerooters\. Let us start with an example, before giving the proof of[Theorem˜3\.2](https://arxiv.org/html/2605.30664#S3.Thmtheorem2)\.

###### Example J\.1\(Two rerooters\)\.

For example, supposed​\(n∗\)=30d\(n^\{\*\}\)=30in a perfect binary tree with a uniform policy\. Then the LTS bound tells us that LTS would take at most\(d​\(n∗\)\+1\)​230\(d\(n^\{\*\}\)\+1\)2^\{30\}node visits to findn∗n^\{\*\}, but the refined algorithm and bound usingc1rc^\{r\}\_\{1\}actually takes at mostc1r​\(n∗\)=1\+2\+4\+…​230=231−1c^\{r\}\_\{1\}\(n^\{\*\}\)=1\+2\+4\+\\dots 2^\{30\}=2^\{31\}\-1node visits\(Orseauet al\.,[2024](https://arxiv.org/html/2605.30664#bib.bib6)\)\. Letna≺n∗n^\{a\}\\prec n^\{\*\}such thatd​\(na\)=10d\(n^\{a\}\)=10\. Letnb≺n∗n^\{b\}\\prec n^\{\*\}such thatd​\(nb\)=20d\(n^\{b\}\)=20\.

Let us consider three rerooterswa,wb,wa​bw\_\{a\},w\_\{b\},w\_\{ab\}\.lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}withwaw\_\{a\}visitsnan^\{a\}at stepTa,aT\_\{a,a\}andn∗n^\{\*\}at stepTa∗T^\{\*\}\_\{a\}\.lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}withwbw\_\{b\}visitsnbn^\{b\}at stepTb,bT\_\{b,b\}andn∗n^\{\*\}at stepTb∗T^\{\*\}\_\{b\}\.lts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}withwa​bw\_\{ab\}visitsnan^\{a\}at stepTa​b,aT\_\{ab,a\}andnbn^\{b\}at stepTa​b,bT\_\{ab,b\}andn∗n^\{\*\}at stepTa​b∗T^\{\*\}\_\{ab\}\. We setwa,1=wb,1=wa,Ta,a=wb,Tb,bw\_\{a,1\}=w\_\{b,1\}=w\_\{a,T\_\{a,a\}\}=w\_\{b,T\_\{b,b\}\}, and 0 everywhere else\. Furthermore, definewa​b=wa\+wbw\_\{ab\}=w\_\{a\}\+w\_\{b\}\.

[Equation˜4](https://arxiv.org/html/2605.30664#S2.E4)tells us that forlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}with rerooterwaw\_\{a\}is competitive with the best subtask decomposition\. Therefore, it is also competitive with any subtask decomposition that is meaningful for analysis\. Let us compare it with the subtask decompositionn1≺na=nTa,a≺n∗n\_\{1\}\\prec n^\{a\}=n\_\{T\_\{a,a\}\}\\prec n^\{\*\}\(which happens to be the best one, in this case\), the noden∗n^\{\*\}is visited atTa∗T^\{\*\}\_\{a\}with

Ta∗−1≤wa,<Ta∗​max⁡\{c1r​\(na\)wa,1,cTa,ar​\(n∗\)wa,a\}=2​max⁡\{211−21,221−21\}=222−4\.\\displaystyle T^\{\*\}\_\{a\}\-1\\leq w\_\{a,<T^\{\*\}\_\{a\}\}\\max\\left\\\{\\frac\{c^\{r\}\_\{1\}\(n^\{a\}\)\}\{w\_\{a,1\}\},\\ \\frac\{c^\{r\}\_\{T\_\{a,a\}\}\(n^\{\*\}\)\}\{w\_\{a,a\}\}\\right\\\}=2\\max\\left\\\{\\frac\{2^\{11\}\-2\}\{1\},\\ \\frac\{2^\{21\}\-2\}\{1\}\\right\\\}=2^\{22\}\-4\\,\.This is already an improvement over the2312^\{31\}node visits of LTS\. Similarly, forlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}with rerooterwbw\_\{b\}, considering the subtask decompositionn1≺nb=nTb,b≺n∗n\_\{1\}\\prec n^\{b\}=n\_\{T\_\{b,b\}\}\\prec n^\{\*\}, the noden∗n^\{\*\}is visited at stepTb∗T^\{\*\}\_\{b\}with

Tb∗−1≤wb,<Tb∗​max⁡\{c1r​\(nb\)wb,1,cTb,br​\(n∗\)wb,b\}=2​max⁡\{221−21,211−21\}=222−4\.\\displaystyle T^\{\*\}\_\{b\}\-1\\leq w\_\{b,<T^\{\*\}\_\{b\}\}\\max\\left\\\{\\frac\{c^\{r\}\_\{1\}\(n^\{b\}\)\}\{w\_\{b,1\}\},\\ \\frac\{c^\{r\}\_\{T\_\{b,b\}\}\(n^\{\*\}\)\}\{w\_\{b,b\}\}\\right\\\}=2\\max\\left\\\{\\frac\{2^\{21\}\-2\}\{1\},\\ \\frac\{2^\{11\}\-2\}\{1\}\\right\\\}=2^\{22\}\-4\\,\.But forlts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}with rerooterwa​b=wa\+wbw\_\{ab\}=w\_\{a\}\+w\_\{b\}, we can consider the subtask decompositionn1≺na≺nb≺n∗n\_\{1\}\\prec n^\{a\}\\prec n^\{b\}\\prec n^\{\*\}since bothnan^\{a\}andnbn^\{b\}now have non\-zero rerooting weights:

Ta​b∗−1\\displaystyle T^\{\*\}\_\{ab\}\-1≤wa​b,<Ta​b​max⁡\{c1r​\(na\)wa​b,1,cTa​b,ar​\(nb\)wa​b,a,cTa​b,br​\(n∗\)wa​b,b\}=4​max⁡\{211−21,211−21,211−21\}=213−8\\displaystyle\\leq w\_\{ab,<T\_\{ab\}\}\\max\\left\\\{\\frac\{c^\{r\}\_\{1\}\(n^\{a\}\)\}\{w\_\{ab,1\}\},\\ \\frac\{c^\{r\}\_\{T\_\{ab,a\}\}\(n^\{b\}\)\}\{w\_\{ab,a\}\},\\frac\{c^\{r\}\_\{T\_\{ab,b\}\}\(n^\{\*\}\)\}\{w\_\{ab,b\}\}\\right\\\}=4\\max\\left\\\{\\frac\{2^\{11\}\-2\}\{1\},\\frac\{2^\{11\}\-2\}\{1\},\\frac\{2^\{11\}\-2\}\{1\}\\right\\\}=2^\{13\}\-8≈4​Ta∗\.\\displaystyle\\approx 4\\sqrt\{T^\{\*\}\_\{a\}\}\\,\.Hence, the hybrid rerooterwa​bw\_\{ab\}benefits from the synergy ofwaw\_\{a\}andwbw\_\{b\}together, by decomposing into 3 subtasks rather than two, leading to a512×512\{\\times\}speedup\. ∎

We propose a more general result, as a variant of the subtask decomposition bound of[Equation˜4](https://arxiv.org/html/2605.30664#S2.E4)that takes advantage of the synergy of*balanced*additive rerooters\.

###### Theorem J\.2\([Theorem˜3\.2](https://arxiv.org/html/2605.30664#S3.Thmtheorem2), Balanced additive rerooters\)\.

Letwaw\_\{a\}andwbw\_\{b\}be two rerooters, with relative weightsua≥0u\_\{a\}\\geq 0andub≥0u\_\{b\}\\geq 0\. Letw=ua​wa\+ub​wbw=u\_\{a\}w\_\{a\}\+u\_\{b\}w\_\{b\}be the rerooter used bylts\\sqrt\{\\mathrm\{\\textnormal\{\{lts\}\}\}\}\. When visiting the nodenTn\_\{T\}at stepTT, for anyC≥1C\\geq 1satisfying1C≤ua​wa,<Tub​wb,<T≤C\\frac\{1\}\{C\}\\leq\\frac\{u\_\{a\}w\_\{a,<T\}\}\{u\_\{b\}w\_\{b,<T\}\}\\leq C, then the number of node visits is bounded by

T≤1\+\(C\+1\)×minD∈𝒟​\(n∗\)⁡maxi<\|D\|⁡min⁡\{wa,<Twa,Ti,wb,<Twb,Ti\}​cTir​\(nTi\+1\)\.\\displaystyle T\\leq 1\+\(C\+1\)\\times~\\min\_\{D\\in\\mathcal\{D\}\(n^\{\*\}\)\}~~\\max\_\{i<\|D\|\}~\\min\\left\\\{\\frac\{w\_\{a,<T\}\}\{w\_\{a,T\_\{i\}\}\},~\\frac\{w\_\{b,<T\}\}\{w\_\{b,T\_\{i\}\}\}\\right\\\}\\,c^\{r\}\_\{T\_\{i\}\}\(n\_\{T\_\{i\+1\}\}\)\.

###### Proof\.

Using the assumption on the rerooters and assumingCCexists \(i\.e\., all quantities are strictly positive\),ua​wa,<T≤C​ub​wb,<Tu\_\{a\}w\_\{a,<T\}\\leq Cu\_\{b\}w\_\{b,<T\}andub​wb,<T≤C​ua​wa,<Tu\_\{b\}w\_\{b,<T\}\\leq Cu\_\{a\}w\_\{a,<T\}, sow<T=ua​wa,<T\+ub​wb,<T≤\(C\+1\)​ua​wa,<Tw\_\{<T\}=u\_\{a\}w\_\{a,<T\}\+u\_\{b\}w\_\{b,<T\}\\leq\(C\+1\)u\_\{a\}w\_\{a,<T\}and alsow<T≤\(C\+1\)​ub​wb,<Tw\_\{<T\}\\leq\(C\+1\)u\_\{b\}w\_\{b,<T\}\. Therefore,

w<Twt\\displaystyle\\frac\{w\_\{<T\}\}\{w\_\{t\}\}=w<Tua​wa,t\+ub​wb,t\\displaystyle=\\frac\{w\_\{<T\}\}\{u\_\{a\}w\_\{a,t\}\+u\_\{b\}w\_\{b,t\}\}≤min⁡\{w<Tua​wa,t,w<Tub​wb,t\}≤\(C\+1\)​min⁡\{ua​wa,<Tua​wa,t,ub​wb,<Tub​wb,t\}=\(C\+1\)​min⁡\{wa,<Twa,t,wb,<Twb,t\}\.\\displaystyle\\leq\\min\\left\\\{\\frac\{w\_\{<T\}\}\{u\_\{a\}w\_\{a,t\}\},\\,\\frac\{w\_\{<T\}\}\{u\_\{b\}w\_\{b,t\}\}\\right\\\}\\leq\(C\+1\)\\min\\left\\\{\\frac\{u\_\{a\}w\_\{a,<T\}\}\{u\_\{a\}w\_\{a,t\}\},\\,\\frac\{u\_\{b\}w\_\{b,<T\}\}\{u\_\{b\}w\_\{b,t\}\}\\right\\\}=\(C\+1\)\\min\\left\\\{\\frac\{w\_\{a,<T\}\}\{w\_\{a,t\}\},\\,\\frac\{w\_\{b,<T\}\}\{w\_\{b,t\}\}\\right\\\}\\,\.Plugging in to[Equation˜4](https://arxiv.org/html/2605.30664#S2.E4)gives the result\. ∎

As mentioned in the main text, the constantC≥1C\\geq 1can be controlled by adjusting the weightsuau\_\{a\}andubu\_\{b\}, such thatua​wa,<Tu\_\{a\}w\_\{a,<T\}andub​wb,<Tu\_\{b\}w\_\{b,<T\}are close to one another\.

## Appendix KComplete Training Results

Table 8:Average online training loss with respect to expansions and time\. Time measures the sum an algorithm spends on each problem across all threads used during training, in hours\.