Free Will and Dodging Anvils: AIXI Off-Policy

[Cole Wyeth]

This post depends on a basic understanding of history-based reinforcement learning and the AIXI model.

I am grateful to Marcus Hutter and the lesswrong team for early feedback, though any remaining errors are mine.

The universal agent AIXI treats the environment it interacts with like a video game it is playing; the actions it chooses at each step are like hitting buttons and the percepts it receives are like images on the screen (observations) and an unambiguous point tally (rewards). It has been suggested that since AIXI is inherently dualistic and doesn’t believe anything in the environment can “directly” hurt it, if it were embedded in the real world it would eventually drop an anvil on its head to see what would happen. This is certainly possible, because the math of AIXI cannot explicitly represent the idea that AIXI is running on a computer inside the environment it is interacting with. For one thing, that possibility is not in AIXI’s hypothesis class (which I will write $M$). There is not an easy patch because AIXI is defined as the optimal policy for a belief distribution over its hypothesis class, but we don’t really know how to talk about optimality for embedded agents (so the expectimax tree definition of AIXI cannot be easily extended to handle embeddedness). On top of that, “any” environment “containing” AIXI is at the wrong computability level for a member of $M$: our best upper bound on AIXI’s computability level is ${\Delta }_2^0$ = limit-computable (for an $\epsilon$-approximation) instead of the ${\Sigma }_1^0$ level of its environment class. Reflective oracles can fix this but at the moment there does not seem to be a canonical reflective oracle, so there remains a family of equally valid reflective versions of AIXI without an objective favorite.

However, in my conversations with Marcus Hutter (the inventor of AIXI) he has always insisted AIXI would not drop an anvil on its head, because Cartesian dualism is not a problem for humans in the real world, who historically believed in a metaphysical soul and mostly got along fine anyway. But when humans stick electrodes in our brains, we can observe changed behavior and deduce that our cognition is physical—would this kind of experiment allow AIXI to make the same discovery? Though we could not agree on this for some time, we eventually discovered the crux: we were actually using slightly different definitions for how AIXI should behave off-policy.

In particular, let ${\xi }^{\text{AI}}$ be the belief distribution of AIXI. More explicitly,

$${\xi }^{\text{AI}}:=\sum _{\mu \in M}{2}^{-K\left(\mu \right)}\mu$$

I will not attempt a formal definition here. The only thing we need to know is that $M$ is a set of environments which AIXI considers possible. AIXI interacts with an environment by sending it a sequence of actions $a_1,a_2,...$ in exchange for a sequence of percepts containing an observation and reward $e_1=o_1{r}_1,e_2=o_2{r}_2,...$ so that action $a_t$ precedes percept $e_t$. One neat property of AIXI is that its choice of $M$ satisfies ${\xi }^{\text{AI}}\in M$ (this trick is inherited with minor changes from the construction of Solomonoff’s universal distribution).

Now let $V_{\mu }^{\pi }$ be a (discounted) value function for policy $\pi$ interacting with environment $\mu$, which is the expected sum of discounted rewards obtained by $\pi$. We can define the AIXI agent as

$${\pi }^{\text{AIXI}}:={\text{argmax}}_{\pi }{V}_{{\xi }^{\text{AI}}}^{\pi }$$

By the Bellman equations, this also specifies AIXI’s behavior on any history it can produce (all finite percept strings have nonzero probability under ${\xi }^{\text{AI}}$). However, it does not tell us how AIXI behaves when the history includes actions it would not have chosen. In that case, the natural extension is

$${\pi }^{\text{AIXI}}(\cdot |a{e}_{<t}):={\text{argmax}}_{\pi }{V}_{{\xi }^{\text{AI}}}^{\pi }\left(a{e}_{<t}\right)$$

so that AIXI continues to act optimally (with respect to its updated belief distribution) even when some suboptimal actions have previously been taken.

The philosophy of this extension is that AIXI acts exactly as if a dumb friend has been playing the video game poorly with AIXI watching both the button presses and the screen from a nearby armchair, and then suddenly passes AIXI the controller. This means that if some electrodes were stuck in AIXI’s “brain” and caused it to choose poor actions, afterwards it will act as if this is because its dumb friend decided to choose dumb actions (which says nothing whatsoever about the rules of the video game itself). I will call this sort of situation action corruption. It seems that dealing with action corruption reasonably may be sufficient to prevent an agent (or child) from dropping an anvil on its head, at least with some “paternalistic” guidance from engineers (or parents). When a little (carefully controlled, non-destructive) poking around in AIXI’s brain is revealed to corrupt actions according to the laws of physics, it is a sensible inference (supported by Ockham’s razor) that crushing AIXI’s brain with an anvil will lead to irrecoverable action corruption. However, we have just argued that AIXI is not ontologically capable of arriving at that inference. Therefore our naive extension of AIXI off-policy will not respond to action corruption reasonably and may fall prey to the anvil problem.

However, in a way this direct extension of AIXI to off-policy histories is not natural. After all, AIXI should be able to calculate the actions that it would have taken in the past recursively, so we can always determine whether action corruption has taken place. To be specific, let us fix a deterministic AIXI policy (by breaking ties between action values in some consistent way). Any deterministic $\pi$ can be treated as a function from histories to actions. Taking this view of ${\pi }^{\text{AIXI}}$, recursively define a mapping $a^{\ast }$ from (a finite string or infinite sequence of) percepts to the corresponding actions of ${\pi }^{\text{AIXI}}$:

$$a^{\ast }(e{)}_t:={\pi }^{\text{AIXI}}(a^{\ast }\left(e\right)e_{<t})$$

Now we can define an alternative off-policy version of AIXI that recalculates the optimal action sequence up to the current time and combines this with the (memorized) percepts to generate an alternative history:

$${\pi }_{\text{off}}^{\text{AIXI}}\left(a{e}_{<t}\right):={\pi }^{\text{AIXI}}\left(a^{\ast }\right(e\left)e_{<t}\right)$$

Note that ${\pi }_{\text{off}}^{\text{AIXI}}$ ignores the true action sequence $a$, or equivalently does not remember its previous actions. In case this waste of information bothers you, we will later integrate the true actions $a_t$ into the percepts $e_t$ and strengthen our conclusions.

This more complicated off-policy behavior does not harm the computability level of $\epsilon$-approximating AIXI because the recursive computation eventually settles on the right answer (by induction). The runtime to convergence scales up by about a factor of $t$ as one would expect.

It is worth reflecting here on which version of AIXI best describes humans. In particular, what is the meaning of our action sequence, and do we remember it? This discussion requires that we are careful about drawing the lines between a person and her environment. Certainly we observe and recall our own external actions (at some level of abstraction); we hear the words we say and we see our hands grasping and picking up objects. However, these events and even the feeling of performing them are actually a part of our percept stream, which both ${\pi }^{\text{AIXI}}$ and ${\pi }_{\text{off}}^{\text{AIXI}}$ maintain similar access to. We can call these self-observations which make up a part of our percepts $\text{im}\left(a\right)$ to stand for the image of our actions. Perhaps the “true” actions are the conscious decisions that precede physical acts—however, psychological experiments have shown that these decisions are predictable before we know that we have arrived at them. The difficulty of locating $a_{<t}$ suggests to me that perhaps memory only represents $\text{im}\left(a_{<t}\right)$, and the illusion of access to $a_{<t}$ is created online by retrospection—this is a much closer match to ${\pi }_{\text{off}}^{\text{AIXI}}$ than ${\pi }^{\text{AIXI}}$, though I think the argument is far from rigorous.

In fact, this discussion suggests the more radical solution of entirely throwing out the “internal” choices $a$ and constructing a universal distribution over $\text{im}\left(a\right)e^{\prime }$ (where $e^{\prime }$ is the rest of the percept). Then perhaps we can believe in free will only for the current time, and “myopically” choose the most favorable $\text{im}\left(a_t\right)$ in a kind of evidential decision theory that may appeal to behaviorists. This idea is close to “Self-Predictive Universal A.I.” which constructs the “Self-AIXI” policy ${\pi }_S$ (the difference is that the paper uses a product measure over belief distributions for policy and environment instead of a unified belief distribution for both). Perhaps there is an interesting connection between ${\pi }_S$ and ${\pi }_{\text{off}}^{\text{AIXI}}$, but I have not found one yet!

Intuitively, I expect that ${\pi }_{\text{off}}^{\text{AIXI}}$ avoids the anvil problem. It should learn that when engineers non-destructively mess with its brain, $\text{im}\left(a\right)$ does not always match $\text{im}\left(a^{\ast }\right)$, which is bad because physical consequences (and rewards) always depend directly on $\text{im}\left(a\right)$. However, outside of brain surgery, $a=a^{\ast }$ and $\text{im}\left(a\right)=\text{im}\left(a^{\ast }\right)$, meaning that $a^{\ast }$ determines the observed actions of the agent and leads to their consequences (remember that ${\pi }_{\text{off}}^{\text{AIXI}}$ does not directly see $a$). Since the physics of AIXI’s brain is computing the true action whether or not it is interfered with, one might expect that AIXI eventually decides that its chosen actions have no effect and it is only a passive observer. But in practice, the actions chosen by AIXI when its brain is not being messed with will be very difficult to predict with certainty from physics (this situation is made even worse because the existence of AIXI’s brain is necessarily outside of its own hypothesis class, at least without introducing a reflective oracle), where as by assumption $a^{\ast }$ is computed correctly with perfect certainty. So the “free will” hypothesis gains Bayes points over the naturalistic hypothesis under those conditions where AIXI performs reliably^[1]. In other words, ${\pi }_{\text{off}}^{\text{AIXI}}$ believes it has free will exactly when it has free will.

Formal Equivalence with an Uncorrupted AIXI

Now we will prove a formal result which describes exactly in what sense the informal statement above is true^[2]. For the moment we will step back and consider arbitrary policies and environments where the percepts need not contain images of the actions.

Given any policy $\pi$, define the corrupted policy $f\circ \pi$ as

$$(f\circ \pi )\left(a_t^{\prime }|a^{\prime }{e}_{<t}\right):=\sum _{a_t}f(a_t^{\prime }|a_{<t}^{\prime }{a}_t,e_{1:t})\pi \left(a_t|a^{\prime }{e}_{<t}\right)$$

That is, the probability that $f\circ \pi$ takes action $a_t^{\prime }$ given that it has so far chosen actions $a_{<t}^{\prime }$ and observed percepts $e_{<t}$, is the sum over the conditional probabilities given by $f$ when $\pi$ attempts to take any possible action $a_t$.

Now given an environment $\mu$ with $\mu \left(e_{1:t}||a_{1:t}\right):={\prod }_{i=1}^t\mu \left(e_i|e_{<i}{a}_i\right)$, we will also define an extended environment that includes the action corruption $f$:

$${\mu }^f\left(e_{1:t}||a_{1:t}\right):=\sum _{a_{1:t}^{\prime }}\mu \left(e_{1:t}||a_{1:t}^{\prime }\right)\prod _{i=1}^{t}f(a_i^{\prime }|a_{<i}^{\prime }{a}_i,e_{1:i})$$

Returning to our extended metaphor, the interpretation is that you are sitting in a room playing a video game on your controller, but your friend is watching you play from another room and sometimes (perhaps if you’re doing something he doesn’t like) he somehow hacks in and changes your actions $a$ to new actions $a^{\prime }$. From your perspective this is all part of the game, in the sense that it behaves exactly like an environment in AIXI’s hypothesis class. With the (minor) caveat that your actions are now moving your thumbs instead of pressing the buttons, this description includes the case that your friend actually grabs your controller (but it is worse in that you may not get to see what he does with it).

Now define the history distribution ${\mu }^{\pi }$ to be generated by the interaction of environment $\mu$ with policy $\pi$.

Theorem: ${\sum }_{a_{1:t}^{\prime }}{\mu }^{f\circ {\pi }_{\text{off}}^{\text{AIXI}}}\left(a^{\prime }{e}_{1:t}\right)=\left({\mu }^f{)}^{{\pi }^{\text{AIXI}}}\right(a^{\ast }\left(e\right)e_{1:t})$

We can further define ${\pi }_{\text{off}}$ for any deterministic $\pi$ and a version of the theorem holds, with its recursively calculated actions $a^{\pi }\left(e\right)$ instead of $a^{\ast }\left(e\right)$.

Proof:

$${\mu }^{f\circ {\pi }_{\text{off}}^{\text{AIXI}}}\left(a^{\prime }{e}_{1:t}\right):=\mu \left(e_{1:t}||a_{1:t}^{\prime }\right)\prod _{i=1}^t(f\circ {\pi }_{\text{off}}^{\text{AIXI}})\left(a_i^{\prime }|a^{\prime }{e}_{<i}\right)$$$$=\mu \left(e_{1:t}||a_{1:t}^{\prime }\right)\prod _{i=1}^t\sum _{a_t}f(a_i^{\prime }|a_{<i}^{\prime }{a}_i,e_{1:i}){\pi }_{\text{off}}^{\text{AIXI}}\left(a_i|a^{\prime }{e}_{<i}\right)$$$$=\mu \left(e_{1:t}||a_{1:t}^{\prime }\right)\prod _{i=1}^t\sum _{a_t}f(a_i^{\prime }|a_{<i}^{\prime }{a}_i,e_{1:i})[a_t={\pi }^{\text{AIXI}}(a^{\ast }\left(e\right)e_{<i}\left)\right]$$$$=\mu \left(e_{1:t}||a_{1:t}^{\prime }\right)\prod _{i=1}^{t}f\left(a_i^{\prime }|a_{<i}^{\prime }{a}^{\ast }\right(e{)}_i,e_{1:i})$$

taking the sum over $a_{1:t}^{\prime }$ we obtain ${\mu }^f\left(e_{1:t}||a^{\ast }\right(e{)}_{1:t})$ by definition, and this is equal to $\left({\mu }^f{)}^{{\pi }^{\text{AIXI}}}\right(a^{\ast }\left(e\right)e_{1:t})$ because ${\pi }^{\text{AIXI}}$ is deterministic.

The theorem says that the probability of the corrupted ${\pi }_{\text{off}}^{\text{AIXI}}$ producing any string of corrupted actions that give rise to the percept string $e_{1:t}$ is the same as the probability that ${\pi }^{\text{AIXI}}$ causes the environment to produce the same percept string $e_{1:t}$. In particular this means that $V_{\mu }^{f\circ {\pi }_{off}^{\text{AIXI}}}=V_{{\mu }^f}^{{\pi }^{\text{AIXI}}}$. My interpretation is that ${\pi }_{\text{off}}^{\text{AIXI}}$ deals with (computable) action corruption optimally.

Now assume that there is an invertible function $\text{im}$ such that the percepts contain $\text{im}\left(a\right)$ and with a slight abuse of notation $a={\text{im}}^{-1}\left(e\right)$. That is, assume AIXI can see itself in the mirror.

Corollary: When $\mu$ is chosen so that the percepts contain an image of the actions,

$${\mu }^{f\circ {\pi }_{\text{off}}^{\text{AIXI}}}\left({\text{im}}^{-1}\right(e\left)e_{1:t}\right)=\left({\mu }^f{)}^{{\pi }^{\text{AIXI}}}\right(a^{\ast }\left(e\right)e_{1:t})$$

And no other actions are consistent with these percepts under $\mu$, so $f\circ {\pi }_{\text{off}}^{\text{AIXI}}$ interacting with $\mu$ causes the percepts $e_{1:t}$ with the same probability that ${\pi }^{\text{AIXI}}$ would when interacting with the environment ${\mu }^f$ that sometimes visibly alters its actions according to $f$.

Closing Thoughts

I believe the off-policy modification of AIXI described above deals with action corruption “correctly.” In particular, we can formalize the intuition that ${\pi }_{\text{off}}^{\text{AIXI}}$ avoids the anvil problem. Since we have said little about the boundedly rational approximations of AIXI, the following argument is only on solid footing when we allow that a very good AIXI approximation has been physically implemented. Assume that before setting AIXI loose with powerful actuators, engineers both expose it to data about the external world and non-destructively tamper with its brain. Because brain surgery interferes with $\text{im}\left(a\right)$ according to the laws of physics, AIXI’s understanding of the laws of physics will increase the weight of environments of the form ${\mu }^f$ where $\mu$ captures the physics of the external world and $f$ involves the physics of AIXI’s brain (roughly, the conditional Kolmgorov complexity of such $f$ given $\mu$ is low). This suggests a serious risk of permanent interference from destructive interventions like a falling anvil (possibly resulting in 0 reward forever), so once AIXI is let loose it will strongly prefer not to run the experiment of dropping an anvil on its head. All of this holds even though AIXI is not capable of literally believing its action choices $a^{\ast }$ depend on its brain—it simply works out the physicality of the action corruptions.

I do not claim that ${\pi }_{\text{off}}^{\text{AIXI}}$ solves all problems of embeddedness. A real implementation of AIXI would not choose the optimal actions $a^{\ast }$ but instead some approximation of them. That approximation would get better with more compute. It is possible that under some approximation schemes, ${\pi }_{\text{off}}^{\text{AIXI}}$ approximations granted more compute view their past suboptimal actions as corrupted actions and conclude that seeking more compute reduces action corruption, but because of potential instabilities in convergence I have not been able to prove this. In any case, ${\pi }_{\text{off}}^{\text{AIXI}}$ can only “learn about its own embeddedness” through observing the effects of side-channels on its performance, but perhaps cannot entertain that it may be a part of the universe merely by observing the existence of computers. I am not certain whether this is even true, and if so I cannot think of any examples where it would be a defect in practice. It does seem that ${\pi }_{\text{off}}^{\text{AIXI}}$ is inherently unable to perform anthropic reasoning, but again I am not sure whether this a problem in practice or only a philosophical objection.

My more general stance is that the philosophical problems with AIXI are overstated, and theories of embedded agency should build off of AIXI. Though we certainly have no rigorously justified and fully satisfying theory of embedded agency (the closest may be Laurent Orseau and Mark Ring’s “Space Time Embedded Intelligence”), it is not clear that these requirements are well-posed enough to have a unique answer. The most promising path I see to explore the possibilities starts with understanding the variations on AIXI. The naive off-policy extension of AIXI may eventually destroy itself, but I expect relatively minor variations on AIXI (such as ${\pi }_{\text{off}}^{\text{AIXI}}$ and ${\pi }_S$ with carefully chosen environment and policy mixtures) to succeed in practice modulo computational boundedness, at least with a little guidance during early stages of development—and frankly I am surprised that their analysis hasn’t received more attention^[3]. If you are interested, please ask me about the many open problems in this area!

1. ^

   Most of this argument goes through for any Bayesian decision theorist. We implicitly rely on the flexibility of AIXI’s hypothesis class by arguing that it should be able to identify the cases when its brain is or is not being tampered with and combine different methods of prediction for each. This is an instance of the “AIXI = God Thesis” in which we assume that any (non-reflective) theory that we can easily describe has a reasonable prior weight under the universal distribution and in practice AIXI will eventually adopt and act based on those theories that are useful for prediction, and therefore perform at least as well as optimal action based on our informally stated theory.

2. ^

   The theorem that follows is inspired by the algebra of Samuel Alexander and Marcus Hutter’s “Reward-Punishment Symmetric Universal Artificial Intelligence.”

3. ^

   My guess is that rationalists tend to have an ambitious and contrarian streak, which causes us to reject a whole paradigm at the first sign of philosophical limitations and prefer inventing entirely new theories. For example, I am thinking of logical induction, infra-Bayesianism, and singular learning theory. Certainly there are some fascinating ideas here worth exploring for their own sake; but this research is often justified through relevance to A.I. safety. I have only passing knowledge of these topics, but as far as I can tell the connection tends to be pretty weak. In contrast, if any rigorous theory of A.I. safety is possible, it probably needs to factor through a good understanding of an embedded version of AIXI if only to avoid wireheading by locating the reward model or utility function at the right position in its ontology. Admittedly the areas I mention have justifications that sound about as good as mine, but engaging with them is outside the scope of this post.