Abstract
Levin Tree Search (LTS) 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 before finding a solution node, that depends on the quality of the policy. In this paper we consider augmenting the information available to the LTS algorithm with a rerooter, which imperfectly predicts at any given node $n$ whether to focus the search onto the descendants of $n$, which corresponds to rerooting the search at $n$. The rerooter thus implicitly decomposes the search space into subtasks, each subtask $i$ corresponding to finding a node $n^{i+1}$ when starting the search at the node $n^i$. The node $n^{i+1}$ can be seen as the goal of subtask $i$. This new algorithm, √LTS (pronounced root-LTS), is a simple best-first search with a special cost function that allows for √LTS rerooting to arise naturally from how the cost function prioritizes the nodes. We prove that the number of search steps that √LTS takes is competitive with the best decomposition into subtasks, at the price of a factor that relates to the uncertainty of the rerooter. The speed-up compared to LTS without a rerooter can be exponential, and even a single rerooting point can --- in the best case --- reduce the number of search steps to its square root. Like the policy, the rerooter can be learnt from data and we expect √LTS to be applicable to a wide range of domains.
Authors
Laurent Orseau, Levi H. S. Lelis*, Marcus Hutter
- *
- External author
Venue
arXiv