Exponential Speedups by Rerooting Levin Tree Search

We are interested in tree search algorithms for deterministic domains. Tree search algorithms such as all variants of best-first search -- including A* [Hart et al., 1968], Weighted-A* (WA*), and Greedy Best-First Search (GBFS) [Doran et al., 1966] -- and variants of MCTS -- such as UCT [Kocsis and Szepesvári, 2006], AlphaGo, AlphaZero and other variants [Silver et al., 2016, 2017b,a] -- explore the search tree starting at the root and can visit a node only if its parent has been visited first. These algorithms are often guided by some side information, such as with cost-to-go heuristic function for A*, WA* and GBFS, a reward/value function for UCT and AlphaZero, or a policy for AlphaZero, Levin Tree Search (LTS) [Orseau et al., 2018], and Policy-Guided Heuristic Search [Orseau and Lelis, 2021]. Such algorithms also sometimes come with different types of guarantees: A* and WA*, with an admissible heuristic function -- i.e., a function that never overestimates the optimal costto-go -- are guaranteed to return a solution that is cost-optimal (A*) or bounded-suboptimal (WA*), while UCT and AlphaZero are guaranteed to (eventually) have low regret in terms of cumulative reward during the search. LTS is guaranteed to return a solution within a number of search steps that depends on the quality of its policy. In this paper, we consider the latter type of guarantee, on the efficiency of the search process depending on the quality of the side information. To explain the main concepts of this paper, let us consider a kind of side information we call clues: some nodes are clue nodes, and a node can be known to be a clue node only when reaching it. A clue may be helpful if it is on the path toward a solution node, or misleading otherwise. The following example describes a minimalistic clue environment.