Exponential Speedups by Rerooting Levin Tree Search
This work addresses the challenge of accelerating search algorithms for AI and planning domains, offering a novel method that can be applied broadly but is incremental in building upon existing Levin Tree Search.
The paper tackles the problem of improving search efficiency in deterministic environments by introducing a new algorithm, √LTS, which implicitly runs Levin Tree Search from every node with rerooting weights, leading to exponential speedups. It proves that √LTS achieves competitive node visits with the best decomposition into subtasks, with a best-case time complexity of O(q√[q]T) compared to LTS's time T, where q is the number of rerooting points.
Levin Tree Search (LTS) (Orseau et al., 2018) is a search algorithm for deterministic environments that uses a user-specified policy to guide the search. It comes with a formal guarantee on the number of search steps (node visits) for finding a solution node that depends on the quality of the policy. In this paper, we introduce a new algorithm, called $\sqrt{\text{LTS}}$ (pronounce root-LTS), which implicitly starts an LTS search rooted at every node of the search tree. Each LTS search is assigned a rerooting weight by a (user-defined or learnt) rerooter, and the search effort is shared between all LTS searches proportionally to their weights. The rerooting mechanism implicitly decomposes the search space into subtasks, leading to significant speedups. We prove that the number of node visits that $\sqrt{\text{LTS}}$ takes is competitive with the best decomposition into subtasks, at the price of a factor that relates to the uncertainty of the rerooter. If LTS takes time $T$, in the best case with $q$ rerooting points, $\sqrt{\text{LTS}}$ only takes time $O(q\sqrt[q]{T})$. Like the policy, the rerooter can be learnt from data, and we expect $\sqrt{\text{LTS}}$ to be applicable to a wide range of domains.