Structure-Induced Information for Rerooting Levin Tree Search
This work provides a more scalable and efficient tree search method for complex single-agent deterministic problems, benefiting researchers and practitioners in AI planning and search.
This paper addresses the scalability limitations of subgoal-based policy tree search in complex single-agent deterministic problems by introducing a learned "rerooter" within the $\\sqrt{\ ext{LTS}}$ algorithm. This approach implicitly decomposes problems into soft subtasks without explicit subgoal generation, leading to state-of-the-art online training efficiency on tested domains.
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.