Universal Algorithmic Intelligence

Logistics

We’re starting a reading group on universal search. See here for a list of readings we’re planning to go through.

The reading group will meet weekly on Mondays starting on March 9th. The normal start time will be 1 PM EST, but for the first session on March 9th we’ll start at 12 PM EST due to a time conflict with a research talk. The group calendar has been updated with the reading group meetings. 

The link for the meetings is in the group description area of the UAI, AIT and ML WhatsApp group. Note that the link is different from the one used for the biweekly research meetings. If you would like to join the reading group sessions and aren’t a part of the WhatsApp group, please send an email to Cole Wyeth at colewyeth@gmail.com. 

For those considering joining, please note that although I’m organizing the reading group, I’m not an expert on universal search and will be learning the material along with everyone else. So I’m not qualified to “teach” the material, and I won’t be more likely to know the answer to a given question than anyone else in the group. Nevertheless, my hope is that: (1) the questions and confusions of attendees aren’t perfectly overlapping, so that we are able to answer each other’s questions to some degree, and (2) we can have interesting discussions about the material. I’m also reaching out to some of the authors of the papers we’ll be reading to see if they’d be willing to come to the sessions covering their papers. 

Overview of Material We’ll Cover

Roughly speaking, a “universal search” algorithm is an algorithm that can be used to solve a broad family of problems in a way that is optimally resource efficient, in some sense. 

We will start by covering Levin and Hutter search, which are algorithms that are able to solve very broad classes of problems in time that is asymptotically optimal (i.e. as fast as the fastest algorithm for solving the problem, except for multiplicative and/or additive constants). While Levin and Hutter search are amazing and elegant, the multiplicative and additive constants that asymptotic optimality ignores are typically enormous, which makes these algorithms impractical. 

With this limitation in mind, we’ll also cover some search algorithms that are inspired by Levin and Hutter search, but that are designed to be more practical. These include: (1) The Optimal Ordered Problem Solver, which seeks to exploit information gained from solving prior instances of a type of problem to more efficiently solve that type of problem in the future, and (2) Levin Tree Search, which is designed to effectively exploit prior information about the problem domain. 

Last, we’ll cover the Gödel machine, which is a self-referential, self-improving reinforcement learning system. This is worth studying in the context of universal search for at least two reasons. 

First, one component of the Gödel machine is a proof searcher that looks for changes the Gödel machine could make to its code that it can prove would increase expected utility. Such changes could include both changes to the policy the Gödel machine uses to interact with the external environment and also changes to the proof searcher itself. So the Gödel machine proof searcher could be initialized with one of the universal search algorithms mentioned above, but this algorithm would be “self-improving” in the sense that it could replace itself with something else as soon as it can prove this would increase expected utility. 

Second, the Gödel machine connects universal search with general reinforcement learning and universal AI. For example, a Gödel machine could initially use an approximation of AIXI as its policy, but could modify or replace this policy as soon as the proof searcher finds a change it can prove would increase expected utility. 

Because finding a formal proof that a change would improve expected utility can be difficult, a recent variant of the Gödel machine called the Huxley-Gödel machine instead uses empirical performance to decide when and how to change its code. We’ll cover this as well.