# Exponential Speedups by Rerooting Levin Tree Search

arXiv: https://arxiv.org/abs/2412.05196 · HTML: https://mlsanity.com/paper/2412.05196/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 21 references that are in the map.
- First posted on arXiv 6 Dec 2024.

## Builds on (most cited first, 7 of 7)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Efficient tracking of a growing number of experts](https://mlsanity.com/paper/1708.09811/) (2017)
- [Levin Tree Search with Context Models](https://mlsanity.com/paper/2305.16945/) (2023)
- [Super-Exponential Regret for UCT, AlphaGo and Variants](https://mlsanity.com/paper/2405.04407/) (2024)

## Built on by (most cited first, 1 of 1)

- [Structure-Induced Information for Rerooting Levin Tree Search](https://mlsanity.com/paper/2605.30664/) (2026)

## Abstract (arXiv)

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 (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 √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, √LTS only takes time O(q√[q]T). Like the policy, the rerooter can be learnt from data, and we expect √LTS to be applicable to a wide range of domains.