Principles of Solomonoff Induction and AIXI

Peter Sunehag, Marcus Hutter

Abstract

Solomonoff Induction and the AIXI agent represent the theoretical gold standards for universal sequence prediction and reinforcement learning, respectively. However, these models are frequently introduced as mathematical definitions without a foundational behavioral justification. This paper provides an axiomatic derivation of these frameworks based on four intuitive principles: computability, rationality, indifference, and time consistency. By proving that Solomonoff Induction and AIXI are the unique logical consequences of these principles, the authors establish a behavioral foundation for universal intelligence.

Introduction

In the field of Artificial General Intelligence (AGI), Solomonoff Induction (for sequence prediction) and AIXI (for reinforcement learning) are considered the "gold standards" of theory. However, they are often presented as mathematical definitions—like a sum over all possible computer programs—without a clear explanation of why those specific definitions are the "right" ones.

The authors aim to bridge the gap between abstract math and philosophical intuition. They ask: "What external behaviors should we demand from an intelligent agent?" By answering this, they show that if you want an agent to be rational, computable, unbiased, and consistent over time, you inevitably end up with Solomonoff Induction and AIXI.

The Axiomatic Approach

The authors use an axiomatic approach, defining four core principles and then mathematically proving that these principles lead directly to the established theories:

  1. Computability: The agent must use a computation procedure (a program for a Universal Turing Machine) to generate its predictions.
  2. Rationality: The agent’s choices must be internally consistent. Using the Hahn-Banach theorem, the authors prove that any "rational" decision-maker must behave as if they have probabilistic beliefs.
  3. Indifference: In the absence of information, the agent should not be biased. This is formalized using coding theory (prefix-free codes) to show that "indifference" at each bit of a program leads to the $2^{-length(p)}$ weighting used in the Solomonoff prior.
  4. Time Consistency: An agent shouldn't change its mind about its initial beliefs just because time has passed, provided the new data is consistent with its programs. This principle is shown to be equivalent to Bayesian conditioning.

Key Insights and Theoretical Results

The derivation yields several profound insights into the nature of intelligence:

  • Rationality implies Probability: One of the most striking insights is that you don't have to assume an agent has "beliefs." If an agent's choices regarding rewards and losses are consistent, they mathematically must be acting according to a probability distribution. This is formalized in Theorem 3 (Linear Separation).
  • The Origin of the Universal Prior: The "Universal Prior" (which favors shorter programs) is often seen as an arbitrary choice of Occam's Razor. The authors show it arises naturally from the Indifference Principle when applied to the way we represent programs as binary strings. Theorem 12 demonstrates that applying this principle to a Universal Turing Machine (UTM) representation yields the Solomonoff semi-measure.
  • Bayes as a Consistency Requirement: Bayesian updating is often taught as a "best practice." This paper frames it as a logical necessity: if you don't update your beliefs using Bayes' rule, you are violating "Time Consistency"—essentially contradicting your past self. This is formally proven in Theorem 15.
  • From Prediction to Action: The paper shows that by extending these principles from simple sequence prediction to an agent that can take actions, you naturally derive the AIXI agent, the theoretical model for a perfectly intelligent reinforcement learner. The AIXI decision rule is shown to be the only policy that satisfies these four principles in an active learning setting.

Discussion and Limitations

While the paper justifies the principles of AIXI, it does not solve the famous problem that AIXI is uncomputable. These principles define what "perfect" behavior looks like, but not how to approximate it efficiently in the real world.

Furthermore, the authors assume a reward structure where rewards eventually go to zero for increasingly complex environments (the $c_0$ space). They acknowledge this is somewhat restrictive and point to future work exploring larger spaces (like $\ell_\infty$) which might lead to "finitely additive" rather than "countably additive" measures. Finally, while they focus on deterministic programs, the Solomonoff mixture is equivalent to acting according to beliefs over a much larger set of stochastic environments.

Summary updated

BibTeX
@inproceedings{sunehag2011principles,
  author = {Peter Sunehag and Marcus Hutter},
  title = {{Principles of Solomonoff Induction and AIXI}},
  booktitle = {Algorithmic Probability and Friends},
  year = {2011},
  url = {https://openreview.net/forum?id=UUpBC9FEcph},
}

Loading related content...

Figure