Universal artificial intelligence, AIXI

AIXI [’ai̯k͡siː] is a thought experiment about “universal intelligence”. Think of it as “AI if compute were no object”, or, if we prefer, “AI at the asymptotic limit of the scaling laws”. It’s basically the most super-possible superintelligence.

It’s not meant to be implemented directly (it’s uncomputable); instead, it’s a gold-standard reference model: “what would a perfectly rational agent look like if it had unlimited computing power?”

The construction is simple in spirit: it combines Solomonoff induction (a universal Bayesian prior over all computable environments) with sequential decision theory (choose actions that maximize expected future reward).

Formally, the value of an action sequence \(a_{1:m}\), given history \(h_t = a_1 o_1 r_1 \dots a_{t-1} o_{t-1} r_{t-1}\), is

\[ V^{\pi}(h_t) \;=\; \mathbb{E}_{\mu \sim \xi} \Bigg[ \sum_{k=t}^{\infty} r_k \;\Big|\; h_t, a_{t:\infty} \sim \pi \Bigg], \]

where:

• \(r_k\) are the rewards,
• \(\pi\) is the policy,
• \(\mu\) ranges over all computable environment distributions,
• \(\xi\) is the Solomonoff mixture prior, weighting each \(\mu\) by \(2^{-K(\mu)}\) with \(K(\mu)\) the Kolmogorov complexity of the environment.

At each step, AIXI chooses the action that maximizes this universal expectation of future reward.

So in words: AIXI is the policy that, in every possible computable world, maximizes expected total reward, weighted by how simple the world’s description is. This makes AIXI maximally intelligent in a precise, technical sense.

But since Kolmogorov complexity is uncomputable, AIXI is uncomputable too. People study approximations such as AIXItl (time- and length-limited), but AIXI’s main role is theoretical: it’s a yardstick for general intelligence, and a source of theorems about what such agents would do.

A related dial to turn: replace Kolmogorov complexity in the prior with Levin’s time-penalized complexity \(Kt\), and the Solomonoff mixture becomes Schmidhuber’s Speed Prior — a computable (though far from cheap) cousin that favours worlds that are fast to compute, not merely short to describe. The substitution buys computability but not tractability: \(Kt\) is computable — Levin’s universal search (Levin 1973) finds the minimizing program in finite time — but the search costs time exponential in program length, so evaluating the Speed Prior (Schmidhuber 2002) lands where AIXItl does, computable in the technical sense while needing more compute than the universe contains. On self-modelling the substitution does more than it is usually credited with. A Speed-Prior agent is a computable (if slow) program, so an environment containing one is itself computable, and the diagonal argument that excludes AIXI from its own hypothesis class no longer goes through. What it leaves is a question rather than a theorem: the time penalty discounts an environment that simulates the agent by the agent’s own enormous runtime, so the agent’s world gets positive but minuscule prior weight, and no grain-of-truth or merging theorem seems to exist for Speed-Prior agents — results of that kind run through reflective oracles instead. Why computable-but-intractable still fails an agent that has to act on a budget is taken up in agency under bounded compute.