From Levin’s Universal Search to Policy-Guided Tree Search

Levin’s universal search embodies a striking principle: when a solution is efficiently verifiable, one can allocate search effort across candidate procedures according to a prior and obtain performance competitive (up to constant) with the best procedure in the reference class first published in (Levin, 1972). The accompanying video and Levin’s paper (Levin 2023) describe the history of this seminal result from the first-person perspective. While Andrey Kolmogorov passed away in 1987, Kolmogorov’s last student, Leonid Levin, systematically developed the theory of Kolmogorov complexity, including universal search. This perspective revisits the conceptual core of Levin-style universal search and finds its relationship to Solomonoff induction, a universal Bayesian framework for prediction that mixes over all computable hypotheses. Like Solomonoff induction, which serves as a spiritual foundation of large language models (LLMs), the Levin universal search has found important applications in AI. In this paper, we will follow one thread of this research on deterministic planning and reinforcement learning via policy-guided tree search.