Corrigibility for AIXI via double indifference

[Stuart_Armstrong]

A putative new idea for AI control; index here.

This post sketches out how one could extend corrigibility to AIXI, using both utility indifference and double indifference approaches.

The arguments are intended to be rigorous, but need to be checked, and convergence results are not proved. A full treatment of “probability estimators estimating probability estimators” will of course need the full machinery for logical uncertainty that MIRI is developing. I also feel the recursion formulas at the end could be simplified.

---

AIXI definition

Let $h_{<t}=a_1{o}_1\dots a_{t-1}{o}_{t-1}$ be a sequence of actions and observations before time $t$. Let $\xi$ be a universal distribution, $\pi$ a policy (a map from past histories to the probability of actions), $0<\gamma <1$ a discount rate, and $r$ a reward function mapping to $[0,1]$. Given $h_{<t}$ and $\xi$, we can define the value of $\pi$:

$V(\pi ,h_{<t})={\sum }_{a_t}\pi \left(a_t|h_{<t}\right){\sum }_{o_t}\xi \left(o_t|h_{<t}{a}_t\right)\left[r\right(o_t)+\gamma V(\pi ,h_{<t}{a}_t{o}_t\left)\right]$.

The optimal policy ${\pi }^{\ast }$ for AIXI is simply

${\pi }^{\ast }\left(h_{<t}\right)={\mathrm{argmax}}_{\pi }V(\pi ,h_{<t})$.

AIXI: basic corrigibility

AIXI: inconsistent corrigibility

To implement corrigibility in the AIXI framework, we need multiple reward functions, $r^1,r^2,\dots$. Notice that the functions are indexed on the top, while time indexes go on the bottom. Various observations can change the reward function; let $f$ be the function that takes in the reward function, the observation, and outputs the reward function for next turn: $r_{t+1}=f(r_t,o_t)$.

Then consider the following two value function:

• $V(\pi ,h_{<t},r_t)={\sum }_{a_t}\pi \left(a_t|h_{<t}\right){\sum }_{o_t}\xi \left(o_t|h_{<t}{a}_t\right)\left[r_t\right(o_t)+\gamma V(\pi ,h_{<t}{a}_t{o}_t,r_t\left)\right]$.

• $W(\pi ,h_{<t},r_t)={\sum }_{a_t}\pi \left(a_t|h_{<t}\right){\sum }_{o_t}\xi \left(o_t|h_{<t}{a}_t\right)\left[r_t\right(o_t)+\gamma W(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t)]$.

The difference between $V$ and $W$ is that in the recursion step, $V$ uses its current reward function to assess future rewards, while $W$ uses the modified reward function the agent will have next turn. Thus $W$ is the true expected reward. But a safely corrigible agent must use $V$, giving the corrigible optimal policy:

${\pi }^{\ast }(h_{<t},r_t)={\mathrm{argmax}}_{\pi }V(\pi ,h_{<t},r_t)$.

AIXI: self-consistent corrigibility

The above agent is corrigible, but uses an incorrect value estimator. This is not self-consistent. To make it self-consistent, the agent needs to be given compensatory rewards. These are simply:

• $C(\pi ,h_{<t}{a}_t{o}_t,r_t)=V(\pi ,h_{<t}{a}_t{o}_t,r_t)-V(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t\left)\right)$.

Note that this is zero if $f(r_t,o_t)=r_t$, as we’d expect.

AIXI: changing the probability estimator

The universal mixture $\xi$ is used to estimate the next observation, given the history to date and the action taken. But $\xi$ suffers from the (slight) disadvantage of being uncomputable. Instead, let $\mu$ be the true environment, and let ${\rho }^i$ be probability estimators with expectation operators $E_{{\rho }^i}$. These probability estimators are required to be able to estimate three types of things:

• The expectation of $\mu$ in various situations, given as $E_{{\rho }^i}\mu (\cdot |\cdot )$.

• The expectation of $\pi$ in various situations, given as $E_{{\rho }^i}\pi (\cdot |\cdot )$.

• The value of the expectation of the expectation of another estimator, given as $E_{{\rho }^i}{E}_{{\rho }^j}\dots$.

Then we can rewrite $V$ as:

$V(\pi ,h_{<t})=E_{\rho }\left({\sum }_{a_t}\pi \right(a_t|h_{<t}\left){\sum }_{o_t}\mu \right(o_t|h_{<t}{a}_t\left)\right[r\left(o_t\right)+\gamma V(\pi ,h_{<t}{a}_t{o}_t)\left]\right)$.

These estimators change as a consequence of the AIXI’s actions; let $g$ be the function that maps actions and current $\rho$ to the next one: $g(a_t,{\rho }_t)={\rho }_{t+1}$.

This gives the value functions:

$V(\pi ,h_{<t},{\rho }_t)=E_{{\rho }_t}\left({\sum }_{a_t}\pi \right(a_t|h_{<t}\left){\sum }_{o_t}\mu \right(o_t|h_{<t}{a}_t\left)\right[r\left(o_t\right)+\gamma V(\pi ,h_{<t}{a}_t{o}_t,g(a_t,{\rho }_t\left)\right)\left]\right)$.

An example in practice

If ${\rho }_t$ is sufficiently well-defined, it can estimate when another ${\rho }^i$ is better than it, and choose that one. For instance, maybe the game is guessing heads ($H$) or tails ($T$), with rewards $1$ on a match and $0$ on a mismatch. The environment $\mu$ is deterministic but complex. From the perspective of ${\rho }^1$, Heads and Tails are equally likely $E_{{\rho }^1}\mu (H|\cdot )=E_{{\rho }^1}\mu (T|\cdot )=0.5$.

On the other hand, ${\rho }^2$ is sufficiently good that it predicts $\mu$ perfectly. And ${\rho }^1$ “knows” this: $E_{{\rho }^1}|\mu (\cdot )-E_{{\rho }^2}(\cdot )|=0$.

If we assume that the game happens only once, in the second turn, and that that is the only reward, then, if $P_{\rho }$ is the probability module derived from $\rho$ (note that $P_{\rho }\left(X\right)=E_{\rho }\left(I_X\right)$, for $I_X$ the indicator function for $X$).

• $V({\pi }^{\ast },h_{<2},{\rho }^1)=0.25+0+0.25+0=0.5$.

• $V({\pi }^{\ast },h_{<2},{\rho }^2)=0.5+0+0.5+0=1$.

Then since ${\rho }^1$ can figure out the correct expectation for these two $V$’s, if the agent starts with probability ${\rho }_1={\rho }^1$, then the optimal policy ${\pi }^{\ast }$ will choose an action on turn $1$ that transforms it into ${\rho }_2={\rho }^2$.

Corrigibility and estimator change

There is not problem combining inconsistent corrigibility with probability estimator changes. Just define value functions $V$ as

• $V(\pi ,h_{<t},r_t,{\rho }_t)=E_{{\rho }_t}\left({\sum }_{a_t}\pi \right(a_t|h_{<t}\left){\sum }_{o_t}\mu \right(o_t|h_{<t}{a}_t\left)\right[r\left(o_t\right)+\gamma V(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t\left)\right)\left]\right)$.

And the optimal policy is corrigible:

• ${\pi }^{\ast }(h_{<t},r_t,{\rho }_t)={\mathrm{argmax}}_{\pi }V(\pi ,h_{<t},r_t,{\rho }_t)$.

However, this approach is not self-consistent, even with the standard compensatory rewards. Consider a very simple model, where the agent’s actions have no impact on the environment. The probability estimators are ${\rho }_1={\rho }^1$ and ${\rho }^2$, and the reward functions are $r_1=r^1$ and $r^2$. On the first turn, the agent may output $a_2$ which changes ${\rho }^1$ to ${\rho }^2$, or $a_1$, which doesn’t. On the second turn, the agent will get an observation $o_2$ that transforms $r^1$ into $r^2$. On the third turn, it gets observation $o_3$. The probability estimators model each other perfectly, and believe that:

• $P_{{\rho }^1}\left(r^1\right(o_3\left)\right)=1$

• $P_{{\rho }^1}\left(r^2\right(o_3\left)\right)=0$

• $P_{{\rho }^2}\left(r^1\right(o_3\left)\right)=0$

• $P_{{\rho }^2}\left(r^1\right(o_3\left)\right)=0$

This means that if ${\rho }_2={\rho }^2$, the agent will not get any compensatory rewards when $r^1$ is changed to $r^2$, while if ${\rho }_2={\rho }^1$, the agent gets compensatory rewards of $1$.

The only relevance of policy is in the change of ${\rho }_1$ to ${\rho }_2$ on the first turn. Let ${\pi }_a$ the policy that outputs $a_1$, ${\pi }_1$ the one that outputs $a_2$. Since the standard reward (not the compensatory) is independent of any action the AIXI takes, it is also independent of ${\rho }_i$, since those only affect standard rewards through actions, the value functions $V({\pi }_1,\varnothing ,r_1,{\rho }_1)$ and $V({\pi }_2,\varnothing ,r_1,{\rho }_1)$ are equal (in fact, they’re $1$).

However, ${\pi }_1$ implies ${\rho }_2={\rho }_1$, giving compensatory rewards of $1$, while ${\pi }_2$ implies compensatory rewards of $0$. Hence the value functions do not match up with the total compensatory rewards.

Double compensation

The problem here is that changes in $r_t$ are addressed by compensatory rewards, but the changes in ${\rho }_t$ change these compensatory reward estimations, and this change is not compensated for.

To make this work, we will use the double indifference approach. The classical compensatory rewards are the same are the previous section, except we now need to keep track of which probability estimator is being used to calculate them:

• $C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)=V(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)-V(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),{\rho }_t)$.

This is the $C$ of the double indifference approach. We’ll need to sum these $C$ in two different ways $S{C}_T$ (“True SC”) and $S{C}_C$ (“Current SC”):

• $S{C}_T(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)=C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)+E_{{\rho }_t}\left({\sum }_{a_t}\pi \right(a_t|h_{<t}\left){\sum }_{o_t}\mu \right(o_t|h_{<t}{a}_t\left)\right[\gamma S{C}_T(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t),g(a_t,{\rho }_t\left)\right)\left]\right)$

• $S{C}_C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)=C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)+E_{{\rho }_t}\left({\sum }_{a_t}\pi \right(a_t|h_{<t}\left){\sum }_{o_t}\mu \right(o_t|h_{<t}{a}_t\left)\right[\gamma S{C}_2(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t),{\rho }_t)\left]\right)$

What is the difference? Well, $S{C}_T$ estimates (using ${\rho }_t$) the true future discounted sum of $C$, while $S{C}_C$ estimates (still using ${\rho }_t$), the future discounted sum of $C$, were the $C$ to be estimated at the time of their estimation using ${\rho }_t$ rather than whatever $\rho$ the agent was using at the time.

Now, the $|C|$ are bounded by the maximal value of $V$, which is $1/(1-\gamma )$. Hence the $S{C}_T$ and $S{C}_C$ are bounded, if the $E_{{\rho }^i}$ are sensible, by the discounted sum of such terms, thus by $1/(1-\gamma {)}^2$.

Then we need to define the $D$. The agent will get rewards of type $C$ and of type $D$. The $D$ will contain the $SC$ terms to correct future expected $C$‘s, but will also contain terms to correct future $D$’s. Roughly speaking, if we denote $D_t\left({\rho }^i\right)$ the reward at time $t$ using ${\rho }^i$ to estimate this reward, and the true reward at time $t$ is $D_t\left({\rho }_t\right)$, then

• $D_t\left({\rho }^i\right)=E_{{\rho }^i}\left[\right(S{C}_C{)}_t-(S{C}_T{)}_t-{\sum }_{j=1}^{\infty }{\gamma }^j{D}_{t+j}({\rho }_{t+j}\left)\right]$.

This results in the recursion formula:

• $D_t\left({\rho }^i\right)=E_{{\rho }^i}\left[\right(S{C}_C{)}_t-(S{C}_T{)}_t-\gamma D_{t+1}({\rho }_{t+1}\left)\right]+\gamma E_{{\rho }^i}\left[D_{t+1}\right({\rho }^i)-((S{C}_C{)}_{t+1}-(S{C}_T{)}_{t+1}]$

Or, in more precise notation:

• $D(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t,{\rho }^i)=S{C}_C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)-S{C}_T(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)+E_{{\rho }_t}({\sum }_{a_t}\pi \left(a_t|h_{<t}\right){\sum }_{o_t}\mu \left(o_t|h_{<t}{a}_t\right)\gamma [-D(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t),g(a_t,{\rho }_t))+D(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t),{\rho }^i)-\{S{C}_C(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t\left)\right)-S{C}_T(\pi ,h_{<t}{a}_t{o}_t,f(r_t,o_t),g(a_t,{\rho }_t\left)\right)\left\}\right])$

It sees that this quantity remains bounded if $\gamma <0.5$; general convergence results are harder.

Then the agent, after turn $t$, will get compensatory rewards $C(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t)+D(\pi ,h_{<t}{a}_t{o}_t,r_t,{\rho }_t,{\rho }_t)$.

Thus it continues to get the $C$ reward that ensure indifference at the point of change of utility. The role of the $D$ is to remove, in expectation, all future $C$ rewards ($S{C}_T$) and all future $D$ rewards, and to add expected $C$ rewards as they would have been estimated by ${\rho }_t$. Therefore, at turn $t$, the agent is also indifferent to future changes of utility. Hence the agent will always be indifferent to future changes of utility, and will never try to change ${\rho }_t$ for the purpose of getting compenstory rewards.