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.

On Feb 29 Levi Lelis — Fellow and Canada CIFAR AI Chair at Amii, — presented “Policy-Guided Heuristic Search" at the AI Seminar.

Abstract: Lelis presents 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. He explores 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. He also presents some empirical results. In particular, Lelis shows what may be the fastest policy, learned from data, that is able to solve random instances of the Rubik's Cube.

Watch the full presentation below: