AIXI

According to Hutter, the word "AIXI" can have several interpretations. AIXI can stand for AI based on Solomonoff's distribution, denoted by $\backslash xi$ (which is the Greek letter xi), or e.g. it can stand for AI "crossed" (X) with induction (I). There are other interpretations.{{Cite web |last=Hutter |first=Marcus |title=Universal Artificial Intelligence |url=http://www.hutter1.net/ai/uaibook.htm |access-date=2024-09-21 |website=www.hutter1.net |language=en}}

AIXI is a reinforcement learning agent that interacts with some stochastic and unknown but computable environment $\backslash mu$. The interaction proceeds in time steps, from $t=1$ to $t=m$, where $m\; \backslash in\; \backslash mathbb\{N\}$ is the lifespan of the AIXI agent. At time step t, the agent chooses an action $a\_t\; \backslash in\; \backslash mathcal\{A\}$ (e.g. a limb movement) and executes it in the environment, and the environment responds with a "percept" $e\_t\; \backslash in\; \backslash mathcal\{E\}\; =\; \backslash mathcal\{O\}\; \backslash times\; \backslash mathbb\{R\}$, which consists of an "observation" $o\_t\; \backslash in\; \backslash mathcal\{O\}$ (e.g., a camera image) and a reward $r\_t\; \backslash in\; \backslash mathbb\{R\}$, distributed according to the conditional probability $\backslash mu(o\_t\; r\_t\; |\; a\_1\; o\_1\; r\_1\; ...\; a\_\{t-1\}\; o\_\{t-1\}\; r\_\{t-1\}\; a\_t)$, where $a\_1\; o\_1\; r\_1\; ...\; a\_\{t-1\}\; o\_\{t-1\}\; r\_\{t-1\}\; a\_t$ is the "history" of actions, observations and rewards. The environment $\backslash mu$ is thus mathematically represented as a probability distribution over "percepts" (observations and rewards) which depend on the full history, so there is no Markov assumption (as opposed to other RL algorithms). Note again that this probability distribution is unknown to the AIXI agent. Furthermore, note again that $\backslash mu$ is computable, that is, the observations and rewards received by the agent from the environment $\backslash mu$ can be computed by some program (which runs on a Turing machine), given the past actions of the AIXI agent.{{cite arXiv |last1=Veness |first1=Joel |author2=Kee Siong Ng |last3=Hutter |first3=Marcus |last4=Uther |first4=William |last5=Silver |first5=David |eprint=0909.0801 |title=A Monte Carlo AIXI Approximation |year=2009 |class=cs.AI}}

The only goal of the AIXI agent is to maximize $\backslash sum\_\{t=1\}^m\; r\_t$, that is, the sum of rewards from time step 1 to m.

The AIXI agent is associated with a stochastic policy $\backslash pi\; :\; (\backslash mathcal\{A\}\; \backslash times\; \backslash mathcal\{E\})^*\; \backslash rightarrow\; \backslash mathcal\{A\}$, which is the function it uses to choose actions at every time step, where $\backslash mathcal\{A\}$ is the space of all possible actions that AIXI can take and $\backslash mathcal\{E\}$ is the space of all possible "percepts" that can be produced by the environment. The environment (or probability distribution) $\backslash mu$ can also be thought of as a stochastic policy (which is a function): $\backslash mu\; :\; (\backslash mathcal\{A\}\; \backslash times\; \backslash mathcal\{E\})^*\; \backslash times\; \backslash mathcal\{A\}\; \backslash rightarrow\; \backslash mathcal\{E\}$, where the $*$ is the Kleene star operation.

In general, at time step $t$ (which ranges from 1 to m), AIXI, having previously executed actions $a\_1\backslash dots\; a\_\{t-1\}$ (which is often abbreviated in the literature as

:$$

a_t := \arg \max_{a_t} \sum_{o_t r_t} \ldots \max_{a_m} \sum_{o_m r_m} [r_t + \ldots + r_m] \sum_{q:\; U(q, a_1 \ldots a_m) = o_1 r_1 \ldots o_m r_m} 2^{-\textrm{length}(q)}

or, using parentheses, to disambiguate the precedences

:$$

a_t := \arg \max_{a_t} \left( \sum_{o_t r_t} \ldots \left( \max_{a_m} \sum_{o_m r_m} [r_t + \ldots + r_m] \left( \sum_{q:\; U(q, a_1 \ldots a_m) = o_1 r_1 \ldots o_m r_m} 2^{-\textrm{length}(q)} \right) \right) \right)

Intuitively, in the definition above, AIXI considers the sum of the total reward over all possible "futures" up to $m\; -\; t$ time steps ahead (that is, from $t$ to $m$), weighs each of them by the complexity of programs $q$ (that is, by $2^\{-\backslash textrm\{length\}(q)\}$) consistent with the agent's past (that is, the previously executed actions,

Let us break this definition down in order to attempt to fully understand it.

$o\_t\; r\_t$ is the "percept" (which consists of the observation $o\_t$ and reward $r\_t$) received by the AIXI agent at time step $t$ from the environment (which is unknown and stochastic). Similarly, $o\_m\; r\_m$ is the percept received by AIXI at time step $m$ (the last time step where AIXI is active).

$r\_t\; +\; \backslash ldots\; +\; r\_m$ is the sum of rewards from time step $t$ to time step $m$, so AIXI needs to look into the future to choose its action at time step $t$.

$U$ denotes a monotone universal Turing machine, and $q$ ranges over all (deterministic) programs on the universal machine $U$, which receives as input the program $q$ and the sequence of actions $a\_1\backslash dots\; a\_m$ (that is, all actions), and produces the sequence of percepts $o\_1\; r\_1\; \backslash ldots\; o\_m\; r\_m$. The universal Turing machine $U$ is thus used to "simulate" or compute the environment responses or percepts, given the program $q$ (which "models" the environment) and all actions of the AIXI agent: in this sense, the environment is "computable" (as stated above). Note that, in general, the program which "models" the current and actual environment (where AIXI needs to act) is unknown because the current environment is also unknown.

$\backslash textrm\{length\}(q)$ is the length of the program $q$ (which is encoded as a string of bits). Note that $2^\{-\backslash textrm\{length\}(q)\}\; =\; \backslash frac\{1\}\{2^\{\backslash textrm\{length\}(q)\}\}$. Hence, in the definition above, $\backslash sum\_\{q:\backslash ;\; U(q,\; a\_1\; \backslash ldots\; a\_m)\; =\; o\_1\; r\_1\; \backslash ldots\; o\_m\; r\_m\}\; 2^\{-\backslash textrm\{length\}(q)\}$ should be interpreted as a mixture (in this case, a sum) over all computable environments (which are consistent with the agent's past), each weighted by its complexity $2^\{-\backslash textrm\{length\}(q)\}$. Note that $a\_1\; \backslash ldots\; a\_m$ can also be written as $a\_1\; \backslash ldots\; a\_\{t-1\}a\_t\; \backslash ldots\; a\_m$, and

Let us now put all these components together in order to understand this equation or definition.

At time step t, AIXI chooses the action $a\_t$ where the function $\backslash sum\_\{o\_t\; r\_t\}\; \backslash ldots\; \backslash max\_\{a\_m\}\; \backslash sum\_\{o\_m\; r\_m\}\; [r\_t\; +\; \backslash ldots\; +\; r\_m]\; \backslash sum\_\{q:\backslash ;\; U(q,\; a\_1\; \backslash ldots\; a\_m)\; =\; o\_1\; r\_1\; \backslash ldots\; o\_m\; r\_m\}\; 2^\{-\backslash textrm\{length\}(q)\}$ attains its maximum.

The parameters to AIXI are the universal Turing machine U and the agent's lifetime m, which need to be chosen. The latter parameter can be removed by the use of discounting.

AIXI's performance is measured by the expected total number of rewards it receives.

AIXI has been proven to be optimal in the following ways.

• Pareto optimality: there is no other agent that performs at least as well as AIXI in all environments while performing strictly better in at least one environment.{{citation needed|date=June 2014}}
• Balanced Pareto optimality: like Pareto optimality, but considering a weighted sum of environments.
• Self-optimizing: a policy p is called self-optimizing for an environment $\backslash mu$ if the performance of p approaches the theoretical maximum for $\backslash mu$ when the length of the agent's lifetime (not time) goes to infinity. For environment classes where self-optimizing policies exist, AIXI is self-optimizing.

It was later shown by Hutter and Jan Leike that balanced Pareto optimality is subjective and that any policy can be considered Pareto optimal, which they describe as undermining all previous optimality claims for AIXI.{{cite conference|conference=Proceedings of the 28th Conference on Learning Theory|last1=Leike|first1=Jan|last2=Hutter|first2=Marcus|title=Bad Universal Priors and Notions of Optimality|date=2015|url=http://proceedings.mlr.press/v40/Leike15.pdf}}

However, AIXI does have limitations. It is restricted to maximizing rewards based on percepts as opposed to external states. It also assumes it interacts with the environment solely through action and percept channels, preventing it from considering the possibility of being damaged or modified. Colloquially, this means that it doesn't consider itself to be contained by the environment it interacts with. It also assumes the environment is computable.{{cite web|last1=Soares|first1=Nate|title=Formalizing Two Problems of Realistic World-Models|url=https://intelligence.org/files/RealisticWorldModels.pdf|website=Intelligence.org|access-date=2015-07-19|ref=MIRI}}

Like Solomonoff induction, AIXI is incomputable. However, there are computable approximations of it. One such approximation is AIXItl, which performs at least as well as the provably best time t and space l limited agent. Another approximation to AIXI with a restricted environment class is MC-AIXI (FAC-CTW) (which stands for Monte Carlo AIXI FAC-Context-Tree Weighting), which has had some success playing simple games such as partially observable Pac-Man.{{cite arXiv |last1=Veness |first1=Joel |author2=Kee Siong Ng |last3=Hutter |first3=Marcus |last4=Uther |first4=William |last5=Silver |first5=David |eprint=0909.0801 |title=A Monte Carlo AIXI Approximation |year=2009 |class=cs.AI}}[https://www.youtube.com/watch?v=yfsMHtmGDKE Playing Pacman using AIXI Approximation – YouTube]

• Gödel machine

{{reflist}}

• "Universal Algorithmic Intelligence: A mathematical top->down approach", Marcus Hutter, {{arXiv|cs/0701125}}; also in Artificial General Intelligence, eds. B. Goertzel and C. Pennachin, Springer, 2007, {{ISBN|9783540237334}}, pp. 227–290, {{doi|10.1007/978-3-540-68677-4_8}}.

Category:Optimal decisions

Category:Decision theory

Category:Machine learning