Exponential Speedups by Rerooting Levin Tree Search
Laurent Orseau, Marcus Hutter, Levi H. S. Lelis · 2024
Read Exponential Speedups by Rerooting Levin Tree Search by Laurent Orseau, Marcus Hutter, Levi H. S. Lelis (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05196.txt.
Introduction
Laurent Orseau, Marcus Hutter, and Levi Lelis present a faster form of a guided tree search method, in a paper from twenty twenty-four. The older method, Levin Tree Search, walks a tree of choices using a user-given policy to steer it. Its cost depends on how good that steering is. The new method quietly starts a fresh search at every node of the tree at once.
A second tool, called a rerooter, gives each of those searches a weight, and effort is split by weight. This split breaks the big search into smaller tasks without naming them in advance. The authors prove the cost stays close to the best such split, and in the best case the speedup is huge. Both the policy and the rerooter can be learned from data.
Catalog record
| CREATOR | Laurent Orseau, Marcus Hutter, Levi H. S. Lelis |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-05196
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exponential Speedups by Rerooting Levin Tree Search Laurent Orseau, Marcus Hutter, Levi H. S. Lelis Abstract 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 lts \sqrt{\mathrm{\textnormal{{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 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 lts \sqrt{\mathrm{\textnormal{{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 T , in the best case with q q rerooting points, lts \sqrt{\mathrm{\textnormal{{lts}}}} only takes time O ( q T q ) O(q\sqrt[q]{T}) . Like the policy, we expect that the rerooter can be learnt from data, making lts \sqrt{\mathrm{\textnormal{{lts}}}} applicable to a wide range of domains. Keywords informed search, planning, efficiency guarantees, anytime algorithms, rerooting, Sokoban 1 Introduction 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 ; Silver et al., 2017b ; Silver et al., 2017a ) — 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 cost-to-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 node visits 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. n_{1} n_{a} n_{b} n_{c} n_{d} n^{*} Figure 1 : A schematic representation of the binary tree of Example 1 with four clue nodes n_{a},n_{b},n_{c},n_{d} at depth 50, and the solution node n^{*} at depth 100. Example 1 (1000-Clues) . The search space is a perfect binary tree of depth 100, and the single solution node is one of the leaves. Without any further information, no tree search algorithm can do better than searching through the 2^{100} leaf nodes in the worst case. Fortunately, at depth 50 there are 1000 random clue nodes , and the solution node is a descendant of one of these clue nodes. That is, only one clue node is helpful, and 999 clue nodes are misleading. See Figure 1 . The search algorithm can discover whether a node n is a clue node only upon visiting it. 1 1 1 Clues could be observed also upon node generation, that is, when the parent is visited — see Eq. 2 . How can we leverage this information to search faster? A simple algorithm first finds all the 1000 clue nodes, which takes about 2^{50} steps, then starts a new search under each clue node for about 2^{50} steps each until finding the solution node. This algorithm would visit about 1001\times 2^{51} nodes in the worst case, which is far less than the 2^{100} steps required on average when the clues are not used. ∎ In Section A.1 , we show that A* and WA* cannot make use of clues in general, while retaining their bounded-suboptimality guarantees. Policy-guided algorithms like LTS use a probability distribution over the available actions at any node of the tree: LTS is a best-first search with visits the nodes in increasing order of their cost n\mapsto d(n)/\pi(n) where d(n) is the depth of a node n , and \pi(n) is the product of the edge (or ‘action’) probabilities from the root to n . On Example 1 , it can be shown that LTS needs to visit at least 2^{99} nodes in the worst case until visiting n^{*} — see Section A.2 . Reward-based algorithms such as AlphaZero are greedy in the sense that they spend most of their search time in the subtree rooted in the first high-reward node they visit. This greedy behavior can lead to taking double-exponential time (with the solution depth) to recover from misleading rewards/clues ( Coquelin and Munos, 2007 ; Orseau and Munos, 2024 ) — see Section A.3 . In this paper, we propose the \sqrt{\mathrm{\textnormal{{lts}}}} algorithm (pronounced root-LTS), which solves the kind of clue environments described in Example 1 and much more. \sqrt{\mathrm{\textnormal{{lts}}}} uses both a policy and a new guiding construct called rerooter . The rerooter assigns a rerooting weight to each visited node. This weight can depend on whatever information is available when visiting the node, including whether the node is a clue node, or how many clue nodes have been visited up to this node, or any other feature of the current and previously-visited nodes. Intuitively, the rerooting weight of a node informs \sqrt{\mathrm{\textnormal{{lts}}}} what fraction of its search time should be devoted to the tree rooted in this node. \sqrt{\mathrm{\textnormal{{lts}}}} comes with formal guarantees on the number of node visits required to reach a solution node, depending on the quality of the policy and of the rerooter. Like the LTS policy, we expect that the rerooter may be learnt from data or designed by the user, but this is beyond the scope of this paper. While \sqrt{\mathrm{\textnormal{{lts}}}} does not specifically require clues since only the rerooting weights matter, clues are still a useful concept both for intuition and perhaps to design rerooters. We envision that clues could be given whenever the search is ‘on the right path’. This is related to rewards and shaping rewards