[R] Marcus Hutter's work on Universal Artificial Intelligence

Marcus Hutter, a senior researcher at Google DeepMind, has written two books on Universal Artificial Intelligence (UAI), one in 2005 and one hot off the press in 2024. The main goal of UAI is to develop a mathematical theory for combining sequential prediction (which seeks to predict the distribution of the next observation) together with action (which seeks to maximize expected reward), since these are among the problems that intelligent agents face when interacting in an unknown environment. Solomonoff induction provides a universal approach to sequence prediction in that it constructs an optimal prior (in a certain sense) over the space of all computable distributions of sequences, thus enabling Bayesian updating to enable convergence to the true predictive distribution (assuming the latter is computable). Combining Solomonoff induction with optimal action leads us to an agent known as AIXI, which in this theoretical setting, can be argued to be a mathematical incarnation of artificial general intelligence (AGI): it is an agent which acts optimally in general, unknown environments. More generally, Shane Legg and Marcus Hutter have proposed a definition of "universal intelligence" in their paper https://arxiv.org/abs/0712.3329

In my technical whiteboard conversation with Hutter, we cover aspects of Universal AI in detail:

https://preview.redd.it/o6700v1udrzc1.png?width=3329&format=png&auto=webp&s=c00b825dbd4d7c266ffec5a31d994661348bff49

Youtube: https://www.youtube.com/watch?v=7TgOwMW_rnk&list=PL0uWtVBhzF5AzYKq5rI7gom5WU1iwPIZO

Outline:

I. Introduction

• 00:38 : Biography
• 01:45 : From Physics to AI
• 03:05 : Hutter Prize
• 06:25 : Overview of Universal Artificial Intelligence
• 11:10 : Technical outline

II. Universal Prediction

• 18:27 : Laplace’s Rule and Bayesian Sequence Prediction
• 40:54 : Different priors: KT estimator
• 44:39 : Sequence prediction for countable hypothesis class
• 53:23 : Generalized Solomonoff Bound (GSB)
• 57:56 : Example of GSB for uniform prior
• 1:04:24 : GSB for continuous hypothesis classes
• 1:08:28 : Context tree weighting
• 1:12:31 : Kolmogorov complexity
• 1:19:36 : Solomonoff Bound & Solomonoff Induction
• 1:21:27 : Optimality of Solomonoff Induction
• 1:24:48 : Solomonoff a priori distribution in terms of random Turing machines
• 1:28:37 : Large Language Models (LLMs)
• 1:37:07 : Using LLMs to emulate Solomonoff induction
• 1:41:41 : Loss functions
• 1:50:59 : Optimality of Solomonoff induction revisited
• 1:51:51 : Marvin Minsky

III. Universal Agents

• 1:52:42 : Recap and intro
• 1:55:59 : Setup
• 2:06:32 : Bayesian mixture environment
• 2:08:02 : AIxi. Bayes optimal policy vs optimal policy
• 2:11:27 : AIXI (AIxi with xi = Solomonoff a priori distribution)
• 2:12:04 : AIXI and AGI 2:12:41 : Legg-Hutter measure of intelligence
• 2:15:35 : AIXI explicit formula
• 2:23:53 : Other agents (optimistic agent, Thompson sampling, etc)
• 2:33:09 : Multiagent setting
• 2:39:38 : Grain of Truth problem
• 2:44:38 : Positive solution to Grain of Truth guarantees convergence to a Nash equilibria
• 2:45:01 : Computable approximations (simplifying assumptions on model classes): MDP, CTW, LLMs
• 2:56:13 : Outro: Brief philosophical remarks