Three New Rerooters for √LTS Cut Computation Overhead Drastically

Subgoal-based policy tree search has long been a powerful approach for complex planning problems, but its reliance on explicit subgoal generation introduces significant overhead and limits scalability. In a new paper accepted at ICML 2026, Jake Tuero, Michael Buro, Laurent Orseau, and Levi H. S. Lelis overcome this limitation by designing learned 'rerooters' within the √LTS (Levin Tree Search) framework. Instead of manually constructing subgoals, these rerooters implicitly decompose the problem into soft subtasks, leveraging structure in the state space to guide search more efficiently.

The authors propose three distinct rerooter designs: a clustering-based approach that exploits global state-space structure, a heuristic-based method using learned cost-to-go estimates, and a hybrid that combines both signals. All three avoid the computational burden of explicitly reconstructing subgoals, enabling scalable allocation of search effort. Empirically, the hybrid rerooter achieves state-of-the-art online training efficiency on challenging domains like Sokoban and sliding puzzles, outperforming previous methods that fail at larger problem sizes. This work opens the door to more scalable AI planning systems that can handle complex real-world tasks without manual engineering.