EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Ming Li

Entropy · 13.04.2026 · 28 (4) · 434

DOI: 10.3390/e28040434 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Entropy, online erschienen am 13.04.2026. Verfasst von Ming Li. Beteiligte Einrichtung: School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Canadian NSERC, National Key Research and Development Program of China, Proteomic Navigator of the Human Body Project.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

Stichwörter der Autor:innen

Kolmogorov complexityLevin’s universal searchreinforcement learning

Autor:innen und Institutionen

  • School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada.

Förderung

  • Canadian NSERC
  • National Key Research and Development Program of China
  • Proteomic Navigator of the Human Body Project

Zitieren

APA

Li, M. (2026). From Levin’s Universal Search to Policy-Guided Tree Search. Entropy, 28(4), 434. https://doi.org/10.3390/e28040434

Vancouver

Li M. From Levin’s Universal Search to Policy-Guided Tree Search. Entropy. 2026;28(4):434. doi:10.3390/e28040434

BibTeX
@article{Li2026,
  author = {Li, Ming},
  title = {From Levin’s Universal Search to Policy-Guided Tree Search},
  journal = {Entropy},
  year = {2026},
  volume = {28},
  number = {4},
  pages = {434},
  doi = {10.3390/e28040434}
}
Kostenlos starten →