Structure-Induced Information for Rerooting Levin Tree Search

Computer Science > Artificial Intelligence [Submitted on 28 May 2026] Structure-Induced Information for Rerooting Levin Tree Search Jake Tuero, Michael Buro, Laurent Orseau, Levi H. S. Lelis 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. Comments: ICML 2026 Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.30664 [cs.AI]   (or arXiv:2605.30664v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.30664 Focus to learn more Submission history From: Jake Tuero [view email] [v1] Thu, 28 May 2026 23:51:21 UTC (1,560 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)