3
$\begingroup$

How does the MC-AIXI algorithm work? I tried to read the paper, but I got lost in the math. I understand the concept of AIXI very well, but I don't get two things:

1) Where does MC-AIXI get its models from?? Kolmogorov complexity is non-computable! Why can MC-AIXI get models?

2) How exactly does the decision tree work? I kinda get the concept, but how does it know what it will do in the future without doing another calculation, and so on ad infinitum?

I would like enough information do make my own version of it. Thank you so much for your help!

$\endgroup$
  • 3
    $\begingroup$ I think the math is always fancy in theoretical papers. And so are explanations. $\endgroup$ – padawan Jan 5 '16 at 20:01
  • 1
    $\begingroup$ @cagirici Theoretical papers are math. The math is as "fancy" as it needs to be to do the job. $\endgroup$ – David Richerby Jan 5 '16 at 20:13
  • $\begingroup$ @DavidRicherby "Theoretical papers are math". Can't argue with that. $\endgroup$ – padawan Jan 5 '16 at 20:16
8
$\begingroup$

I'll assume that the paper you're referring to is Veness et al. (2011) - A Monte-Carlo AIXI Approximation. The paper (and the AIXI model more generally) is rather technical, and so it is difficult to talk about without using much math. I'll do my best to explain informally here.

The question is in two parts, so I'll address each separately.

Models

The full mathematical formulation of AIXI makes use of Solomonoff induction to model the environment. Informally, Solomonoff induction involves enumerating every possible model (program) that is consistent with what has been observed, and weighting their likelihood by the inverse of their length. Solomonoff induction can be thought of as a theoretical upper limit on how well you can learn in the general setting while making no assumptions. As the question points out, it is of course incomputable.

We can relax the requirement that we model the world only using the Solomonoff prior, and introduce some other model class, which we will call $\xi$. Our agent is still a Bayesian expectation-maximizing reinforcement learner, but we can now plug it into a less powerful and less general (but computable) model. Hutter calls these agents AI$\xi$. In Veness et al.'s paper, they adapt the Context Tree Weighting (CTW) compression algorithm so that it can be used as a predictive mixture model of the form of $\xi$.

CTW is essentially a mixture over $n^{\text{th}}$-order Markov Models over bits, up to some finite order $N$. Each so-called context tree models dependencies in sequences of bits up to some finite depth. The CTW algorithm weights each context tree by its complexity (essentially how many nodes are in the tree). In this way, the CTW compressor can be made into an efficient, general, and fully Bayesian approximation of Solomonoff induction, and is great at learning short-term dependencies in bit sequences.

Veness et al. call their algorithm MC-AIXI-CTW, to emphasize that it is a two-fold approximation of AIXI: both in the planner (MC), and in the modelling (CTW). They could have used a different model, but they chose CTW because it makes no assumptions about the environment, and so is a general and principled choice. This allowed them to use the same model to learn to play various games, like rock-paper-scissors, cheesemaze, Pacman, and Tic-tac-toe.

Planner

The other side of the MC-AIXI-CTW implementation is the Monte Carlo planner. The algorithm that the authors develop is a straightforward generalization of the commonly used expectimax algorithm, called Monte Carlo tree search (MCTS). MCTS has been used in various AI applications over the last decade or so, and there are lots of online resources about it; the Wikipedia page is a decent starting point. I'll give my own short overview:

If you've studied game theory or introductory AI, then you'll be familiar with minimax. This algorithm can be used to compute the optimal next move when playing a deterministic two-player game. In the case of AIXI interacting with some environment, we can model this as a two-player game, but we must lift the deterministic assumption, as the environment is unknown, and in general stochastic; our models (which we use to plan with) are probabilistic, and so minimax won't cut it here. We instead use expectimax, which is the stochastic generalization of minimax. Instead of the other player adversarially (and deterministically) choosing the min action every turn, we now have to sample from some probability distribution.

MCTS is a sampling algorithm for doing just this. The general idea is that we plan ahead by simulating potential outcomes, using our model. Our objective is to compute the value of each of the moves available to us, so as to pick the best one. The value is in general a random variable, since our model is probabilistic. Hence we should choose the action that maximizes our expected value. The MCTS algorithm repeatedly plays out (simulates) a game tree, but instead of adversarially picking the opponent's moves, they are sampled from AIXI's model. As we collect more samples, our estimate of the value of each move will become more accurate.

Of course, we don't have infinite compute power, and so we can't simulate the agent-environment interaction ad infinitum; we have to stop at some depth of the MCTS tree. In simple game-playing, like chess, we would use heuristics to generate some intermediate value at this finite depth, so that we have something to work with to propagate up the search tree. In this general setting that MC-AIXI is trying to plan in, we have no such heuristics, and so we have no choice but to stop the search once we reach some finite (and typically small) depth.

This is the biggest limitation of the algorithm: planning is a huge computational bottleneck for MC-AIXI. In the absence of heuristics, it's hard to perform well in environments that demand long-term planning, since MCTS treats $\xi$ as a black-box environment model. To answer your question: once the planner reaches its planning horizon, it has to stop simulating ahead and make do with whatever it's sampled from that play-out. This is of course very limiting, but is unfortunately necessary, since doing anything else would require some kind of domain knowledge, which defeats the purpose of having a maximally general reinforcement learner.

Sorry if this answer is a bit long and hand-wavy. I interpreted the direction 'without using fancy math' in the strongest sense that I felt I could get away with. Hope it helps! Also, because I'm a new user to CS.SE, I'm limited to two links per answer. Once I've accumulated some points, I'll go back and edit this answer to include more links to external resources.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.