The AI Seminar is a weekly meeting at the University of Alberta where researchers interested in artificial intelligence (AI) can share their research. Presenters include both local speakers from the University of Alberta and visitors from other institutions. Topics can be related in any way to artificial intelligence, from foundational theoretical work to innovative applications of AI techniques to new fields and problems.

Abstract:
In this talk, I will present Levin Tree Search (LTS) and some of its variants. LTS is a state-space search algorithm that uses a policy to guide its search. Variants of LTS use both a policy and a heuristic function to guide the search. Algorithms from the Levin family offer guarantees regarding the number of expansions required before finding a solution to search problems. These guarantees depend on the quality of both the policy and the heuristic function guiding the search. The guarantees are important because they offer a loss function---the Levin loss---that allows us to learn policies that minimize the size of the resulting search tree. We will explore learning schemas using neural networks and context models, with the latter offering additional guarantees. Specifically, the parameters of context models optimizing the Levin loss can be derived by solving a convex optimization problem. I will also present some empirical results. In particular, I will show what may be the fastest policy, learned from data, that is able to solve random instances of the Rubik's Cube. I aim to make this presentation highly accessible, comparable to a lecture from a 300-level undergraduate course in our department. The talk will summarize the findings of three papers, which are listed below, including the paper that received the Distinguished Paper Award at IJCAI'23. Single-Agent Policy Tree Search with Guarantees. Laurent Orseau, Levi Lelis, Tor Lattimore, and Theophane Weber. In the Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2018. Policy-Guided Heuristic Search with Guarantees. Laurent Orseau and Levi Lelis. In the Proceedings of the Conference on Artificial Intelligence (AAAI), 2021. Levin Tree Search with Context Models. Laurent Orseau, Marcus Hutter, and Levi Lelis. In the Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2023.

Presenter Bio:
Dr. Levi Lelis is an Assistant Professor at the University of Alberta, an Amii Fellow, and a CIFAR AI Chair.