Structure-Induced Information for Rerooting Levin Tree Search

Subgoal-based policy tree search, which uses a policy to guide search, is effective for complex single-agent deterministic problems but often relies on explicit subgoal generation that can incur substantial overhead and hinders scalability. In this paper, we overcome these limitations by using a learned ``rerooter'' through the recently-introduced $\sqrt{\text{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 having to explicitly reconstruct and reason 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.

Many artificial intelligence systems solve problems by searching through possible choices, but this can become very slow when the problem is large or complex. In this work, we study how to make that search more efficient by helping the system decide which parts of the search space deserve more attention. Rather than requiring the system to generate explicit intermediate goals, our approach uses patterns in the problem structure and estimates of progress toward the goal to guide the search. Across several challenging puzzle-like domains, this made training faster and more scalable than previous approaches. This research matters because it helps AI systems solve difficult planning problems more efficiently, using less computation while still finding high-quality solutions.