A Monte Carlo AIXI Approximation
Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, David Silver
cs.AI, cs.IT, cs.LG
2009-09-04
MC-AIXI approximates AIXI via ρUCT planning and FAC-CTW prediction; it matches or beats U-Tree and Active-LZ on 9 POMDPs, 3.97 vs -0.97 for 1-ply on Extended Tiger.
AIXI is Hutter's Bayesian optimality notion for reinforcement learning in unknown environments. The world is any unknown but computable function. The agent mixes over Turing machines with a Solomonoff prior and chooses actions by finite-horizon expectimax. The formula is optimal in several technical senses and only asymptotically computable: it can be written down, it cannot be run. Until this paper it was unclear whether that theory could shape a practical algorithm, or would remain a principle on the wall.
MC-AIXI(fac-ctw) is the first computationally feasible direct approximation. Planning generalises UCT so that history stands in for state and expectimax is sampled. Learning generalises Context Tree Weighting into an action-conditional mixture that stands in for Solomonoff's universal prior. The tests are stochastic, partially observable POMDPs.
The AIXI line splits into two expensive pieces. Both get approximated.
Naive expectimax costs |A×X| to the power of the horizon. ρUCT takes Kocsis and Szepesvári's UCT off MDPs and onto histories. Decision nodes maximise. Chance nodes sample the next percept from an environment model ρ. Action selection uses UCB. Leaves estimate leftover return with a uniform random rollout. As the simulation count goes to infinity the tree converges to full expectimax and the chance of a suboptimal action goes to zero. A Bayesian mixture of environments is itself an environment model, so ρ can be that mixture. Model uncertainty then sits inside planning, and information-gathering actions appear when the horizon is long enough to cash them in.
The agent cannot mix over all Turing machines. FAC-CTW takes Willems et al.'s Context Tree Weighting, makes it action-conditional, and factors it across the bits of a percept. The model class is prediction suffix trees of depth at most D, a family of variable-order Markov models. The prior comes from a prefix code of the tree shape, so larger trees pay more: an Ockham prior. There are 2^{2^D} such trees. A naive mixture is doubly exponential; a weighted context tree maintains the whole mixture in O(D). FAC-CTW grows one tree per percept bit. An update costs O(D log(|O||R|)) and does not grow with history length t, so the agent can run for millions of cycles. After a ρUCT simulation the updates reverse in the same cost, restoring the original posterior without copying the tree.
At each step the agent runs ρUCT with the current FAC-CTW mixture Υ as ρ, picks an action with an exploration policy, then folds the new percept into Υ. If the true environment is a stationary ergodic n-Markov process, squared value error vanishes at O(log b / b) and the policy sequence is self-optimising for that class. Full Bayesian exploration is still intractable at useful horizons, so the implemented agent adds decaying ε-greedy.
Baselines are U-Tree and Active-LZ, two model-based general RL agents of that period. A learning phase builds a model under forced exploration. An evaluation phase then runs 5000 greedy cycles and reports average reward per cycle. Hardware was a dual 2.53 GHz Xeon with 24 GB of RAM.
MC-AIXI matches or beats both baselines on every domain the three algorithms could all run. Active-LZ improved steadily but more slowly; TicTacToe's observation space is too large for its symbol-level enumeration, so that number is missing. U-Tree did well on most domains, but split-testing cost so much that long runs lose data points. MC-AIXI and Active-LZ take time independent of t per cycle.
Resources listed for near-optimal evaluation-phase performance:
| Domain | Experience | Simulations | Search per cycle |
| 1d Maze | 5×10³ | 250 | 0.1s |
| Cheese Maze | 2.5×10³ | 500 | 0.5s |
| Tiger | 2.5×10⁴ | 25000 | 10.6s |
| Extended Tiger | 5×10⁴ | 25000 | 12.6s |
| 4×4 Grid | 2.5×10⁴ | 500 | 0.3s |
| TicTacToe | 5×10⁵ | 2500 | 4.1s |
| Biased RPS | 1×10⁴ | 5000 | 2.5s |
| Kuhn Poker | 5×10⁶ | 250 | 0.1s |
Most domains work with about 1000 simulations. Tiger and Extended Tiger, where the agent must listen and then open a door, need 25,000.
Swap ρUCT for a 1-ply rollout planner with the same simulation budget and Extended Tiger falls from 3.97 average reward to -0.97. Cheese Maze is 1.28 versus 1.25, biased RPS 0.25 versus 0.20, the rest almost tied. Kuhn Poker scores 0.06 against a known ceiling of 1/18 ≈ 0.056 for a second player facing a Nash first player.
Partially observable Pacman is the stress test: a 17×17 maze, about 10^{60} underlying states, unknown optimum. The agent sees a handful of bits for wall configuration, ghost line of sight, and food smell. Online average reward starts near -14 and climbs. With exploration off, more experience and more simulations push average reward toward 0 and slightly positive. Watching the agent, it learns not to walk into walls, to seek food, and to flee ghosts. It has not yet learned to hunt ghosts after a power pill.
This is the first yes to the question of whether AIXI can guide a practical agent. The construction is a compression-style context tree plus MCTS, and it runs on a 2010 workstation. Three pieces still matter for people who build model-based RL or MCTS planners. Treat history as the sufficient statistic and UCT can leave the MDP box. Drop a Bayesian mixture in as the generative model for search. An Ockham prior lets variable-order models predict before every context is full of data.
It is a workstation-scale existence proof, not a system that takes images or language. The model class is bounded PSTs. Once the world is not stationary n-Markov, the guarantees stop. Fine as a minimal runnable kernel of a universal agent. Not a modern agent stack.
The paper names two. The model class is narrow: if a bounded-depth PST cannot predict the world, performance collapses, and a large PST burns prohibitive experience. The authors say it is unrealistic to expect this approximation to handle real image or audio. Second, the full Bayesian answer to exploration is intractable unless the horizon is tiny, so practice falls back to a heuristic. That did not block optimal scores on these test domains. Harder problems may need something else.
A few more discounts follow from the text. The self-optimising theorem is stated for a countable class of stationary ergodic n-Markov environments, while the KT estimator is an uncountable mixture; the authors call the argument not fully rigorous and patch it with a discretisation story. U-Tree is a framework, not a fixed algorithm. Split criteria, lookback, and p-values were tuned in this paper, so the comparison is only as fair as that tuning. Most domains are small. 1-ply and ρUCT tie on most of them, and the authors admit that multi-step planning mattered less than learning an accurate model on this set. Extended Tiger is the clear counterexample. Pacman has no optimal baseline and no comparison against a planner that knows the true model. Claims about learned concepts come from watching a video, not from a metric.