Technical Summary: Structure-Induced Information for Rerooting Levin Tree Search

Problem Definition

Complex discrete planning problems in single-agent deterministic environments remain difficult to solve at scale. While policy-guided tree search methods like Levin Tree Search (LTS) and Policy Guided Heuristic Search (PHS*) offer theoretical guarantees on search effort, they often struggle with complex domains without additional structural guidance.

A common strategy to address this is decomposing problems into subgoals. However, existing subgoal-based methods (e.g., HIPS-ε, SGPS) rely on explicit subgoal generation and reconstruction. This introduces significant modeling complexity and computational overhead, as search performance becomes tightly coupled to the quality of subgoal generation. As domain complexity increases, the cost of reconstructing and reasoning over these explicit subgoals becomes a bottleneck, hindering scalability.

The paper addresses the challenge of exploiting state-space structure to guide search efficiently without the computational cost of explicit subgoal generation. Specifically, it investigates how to derive effective "rerooting" weights for the $\sqrt{\text{LTS}}$ algorithm—a method that implicitly starts an LTS search at every node in the tree—using structural signals available during the search process.

Methodology

The authors propose a framework that utilizes Structure-Induced Rerooters to allocate search effort in $\sqrt{\text{LTS}}$. Instead of generating explicit subgoals, the framework derives rerooting weights from the search tree's structure and learned heuristics. The paper introduces three specific instantiations:

1. Global Structure-Induced Rerooting ($\sqrt{\text{LTS-L}}$)

This approach captures coarse, global structure in the state space using Leiden clustering.

• Mechanism: As the search tree is built, an induced subgraph of the state space is constructed. The Leiden algorithm is invoked periodically (on a geometric schedule) to cluster states based on connectivity.
• Weight Assignment: Nodes are assigned a "color" corresponding to their cluster. The rerooting weight for a node is inversely proportional to the size of its cluster (approximated by the count of nodes with that color).
• Rationale: This encourages the search to concentrate effort on under-explored regions (small clusters) and redirects effort away from over-explored regions (large clusters), effectively treating clusters as soft subtasks without explicit reconstruction.

2. Local Structure-Induced Rerooting ($\sqrt{\text{LTS-H}}$)

This approach leverages local cost-to-go estimates provided by a learned heuristic function.

• Mechanism: The rerooting weight is defined as an exponential function of the normalized heuristic value: $w_t = \exp(-\alpha \frac{h(n_t)}{h(n_1)})$.
• Rationale: This creates a "soft" prioritization where nodes estimated to be closer to the goal (lower heuristic values) receive higher weights. The normalization by the root heuristic ensures invariance to the absolute scale of the heuristic, while the exponential map ensures smooth, strictly positive weights that allow for imperfect heuristics.

3. Hybrid Structure-Induced Rerooting ($\sqrt{\text{LTS-LH}}$)

This method combines the global and local signals additively.

• Mechanism: The final weight is a linear combination of the clustering-based weight and the heuristic-based weight: $w_t = u_a w_{t, \text{cluster}} + u_b w_{t, \text{heuristic}}$.
• Rationale: The global rerooter provides stability against heuristic noise or miscalibration by identifying structural bottlenecks, while the local rerooter refines priorities within those regions based on estimated progress. This "coarse-to-fine" approach aims to balance robustness with goal-directed adaptivity.

Theoretical Guarantees

The paper extends the theoretical bounds on the number of node expansions required by $\sqrt{\text{LTS}}$. It provides a novel guarantee for additive rerooters, showing that the search complexity is bounded by the synergistic effect of multiple rerooters. Specifically, if the relative weights of the components are balanced, the bound depends on the minimum of the individual bounds, allowing the search to fall back on the most informative signal in any given region of the tree.

Key Contributions

1. Automated Rerooter Learning: The paper presents automated methods for deriving rerooting weights directly from search tree structure (via clustering) and learned heuristics, eliminating the need for separate, computationally expensive subgoal generation networks.
2. Three Rerooter Designs: It introduces and evaluates three distinct designs: a clustering-based global rerooter, a heuristic-based local rerooter, and a hybrid additive rerooter.
3. Theoretical Extension: It provides a new theoretical bound for $\sqrt{\text{LTS}}$ using additive rerooters, demonstrating how multiple structural signals can be combined to improve search efficiency.
4. Scalability Demonstration: The work demonstrates that rerooting can scale to complex environments where explicit subgoal-based methods fail, achieving state-of-the-art online training efficiency.

Experimental Results

The authors evaluated their methods on four domains: BoulderDash, CraftWorld, Sokoban, and a gridworld version of the Traveling Salesman Problem (TSP). They compared their methods against LTS, PHS*, subgoal-based variants (LTS($\pi_{SG}$), PHS*($\pi_{SG}$)), and Weighted A*.

• Training Efficiency: Across all domains, the hybrid rerooter ($\sqrt{\text{LTS-LH}}$) and the heuristic-based rerooter ($\sqrt{\text{LTS-H}}$) substantially improved online training sample efficiency compared to non-rerooting baselines and prior subgoal-based methods. In complex settings (e.g., BoulderDash with high dirt density), subgoal-based methods (PHS*($\pi_{SG}$)) failed to scale or timed out, whereas the rerooting methods completed training successfully.
• Test Performance: Despite faster training, the rerooting methods achieved comparable or superior test performance (measured by problems solved, expansions-to-solution, and solution length) to prior approaches.
• Robustness: The hybrid approach proved most robust, particularly in domains with deadlock structures (Sokoban, CraftWorld) where purely heuristic guidance could be unstable. The global clustering component helped stabilize the search when heuristics were unreliable.
• Complexity Scaling: In the BoulderDash complexity scaling experiment, the hybrid and heuristic rerooters maintained performance as the state space grew, while subgoal-based methods degraded significantly due to the difficulty of reconstructing relevant subgoals in visually dense but task-irrelevant environments.

Significance and Claims

The paper claims that rerooting is a scalable and flexible abstraction for exploiting structure in policy tree search. Its primary significance lies in demonstrating that:

• Implicit Subtasks: One can achieve the benefits of subtask decomposition (improved exploration and search guidance) without the computational overhead of explicit subgoal generation and reconstruction.
• Lightweight Signals: Even lightweight structural signals (like local heuristic values) can be sufficient to guide effective rerooting, often outperforming more complex global clustering approaches in isolation.
• Synergy: Combining complementary structural signals (global connectivity and local cost-to-go) creates a robust mechanism that adapts to varying domain complexities and heuristic qualities.

The authors conclude that $\sqrt{\text{LTS}}$ with simple structural transformations of classical heuristics offers a highly efficient path for scalable policy tree search, avoiding the bottlenecks associated with explicit subgoal modeling in complex domains.