AIXI: Combining Induction and Decision Theory for AGI

Marcus Hutter's AIXI model serves as the gold standard mathematical formalism for universal artificial intelligence. This article provides an overview of how AIXI combines Solomonoff induction—a framework for optimal prediction—with sequential decision theory, which governs optimal action selection. By merging these two concepts, AIXI creates a theoretical agent capable of maximizing future rewards in any computable environment without prior knowledge, effectively defining what it means to be a universally intelligent agent.

To understand AIXI, one must first understand how an agent interacts with an unknown environment. In standard reinforcement learning, an agent takes an action, alters the environment, and receives an observation along with a numerical reward. The challenge is that the true rules of the environment are hidden. The agent must simultaneously learn how the environment works and decide which actions will yield the highest rewards over time.

AIXI solves the learning aspect of this challenge by utilizing Solomonoff induction. Developed by Ray Solomonoff, this theory of universal sequence prediction formalizes Occam's Razor. It considers every possible computer program (modeled as Turing machines) that could generate the history of observations the agent has seen so far. Solomonoff induction assigns a higher probability to shorter, simpler programs and a lower probability to longer, more complex ones, using a measure called Kolmogorov complexity. By taking a weighted average of all valid programs, the system predicts the next observation with the highest possible mathematical accuracy.

However, passive prediction is not enough for an active agent; the environment changes based on what the agent chooses to do. Hutter adapted Solomonoff's passive framework into an active one by replacing standard Turing machines with chronological Turing machines that accept the agent's actions as inputs before outputting observations and rewards. This creates a universal prior probability distribution over all possible reactive environments, known as the Solomonoff-Levin distribution.

With the prediction mechanism established, AIXI integrates sequential decision theory to handle action selection. Sequential decision theory relies on the Bellman equations, which dictate that the value of a given action is determined by the immediate reward it generates plus the expected value of all future actions that follow. To find the best action right now, an agent must look ahead at all possible future sequences of actions and observations up to a certain time horizon.

AIXI merges these two theories into a single master equation. At every time step, AIXI uses sequential decision theory to alternatingly maximize over its own future intended actions and average over the environment's possible future responses. Instead of knowing the true environment to calculate those averages, AIXI substitutes the Solomonoff-Levin distribution. It evaluates the expected reward of an action across every possible computable universe, weighted by the simplicity of that universe's underlying code.

By choosing the action that maximizes this universally weighted expected reward, AIXI achieves Pareto optimality. It balances exploration and exploitation seamlessly, learning the true nature of its environment as quickly as theoretically possible while acting to secure the maximum reward. While AIXI is incomputable in the real world—because calculating Kolmogorov complexity requires infinite computing power—it provides a rigorous, unambiguous mathematical target for what practical artificial general intelligence algorithms strive to approximate.