A putative new idea for AI control; index here.

This is technical note explaining how to define counterfactuals on partially observable Markov decision processes (POMDP).

The POMDP formalism is explained here. This note will just sketch out how counterfactuals are defined; the full details will be in the final paper.

Taking another action

Suppose that an agent has been active for $n$ turns on POMDP $\mu$, and has seen history $h_n$. Then suppose it wants to estimate the counterfactual of what would have happened if had done other actions after timestep $t<n$. So what is the counterfactual probability of history $h_m$, $t<m$, which can be written as:

• $\mu (h_m\mid (h_n{)}^c,h_t)$.

This rather clunky notation (let me know if there's a better way of writing this) is trying to estimate the probability of $h_m$, given that $h_n$ is the counterfactual history, and both $h_n$ and $h_m$ start with $h_t$ before diverging.

It might seem surprising that no policy is mentioned in that expression - after all, the probability of a history is given by the environment $\mu$ and the agent's action choices. But histories like $h_m$ include action choices, so these don't need to be specified separately.

The first thing to notice is that $\mu$ and $h_n$ give a probability distribution over $s_t$, the (hidden) state at timestep $t$. And the value of $s_t$ can change the subsequent probability of $h_m$. So the counterfactual probability is defined as:

• $\mu (h_m\mid (h_n{)}^c,h_t)={\sum }_{s\in S}\mu (s_t=s\mid h_n\left)\mu \right(h_m\mid h_t,s_t=s)$.

Counterfactual equivalence

Though the counterfactual probability is defined in terms of the states, the expression itself only involves histories.

Thus if $\mu$ and ${\mu }^{\prime }$ are two POMDPs with the same sets of actions and observations (but potentially different sets of states) we can say they are counterfactually equivalent if they generate the same counterfactual probabilities:

• $\forall h_m,h_n,h_t:\mu (h_m\mid (h_n{)}^c,h_t)={\mu }^{\prime }(h_m\mid (h_n{)}^c,h_t)$.

Consider the simple POMDP $\mu$ (actually, an MDP, since it's fully observable), defined as:

The reasons for the notation will be explained in a later post; but here, starting from a single state, the agent can take one of two actions, and each action has a $0.5$ chance of ending up in one of two states.

Now consider the POMDP ${\mu }^{\prime }$, defined as:

Here there are one of two initial states, each equally likely, and then each action will lead with certainty to another state that comes from the initial hidden state and the action choice.

Note that there are four possible histories on $\mu$ and ${\mu }^{\prime }$, and two are compatible with each action, and those two are equally probable given that action. So every history will appear with equal probability on $\mu$ and ${\mu }^{\prime }$: they are observationally equivalent.

However, they are not counterfactually equivalent. For instance, $\mu (o_0{a}^w{o}^{w0}\mid o_0{a}^r{o}^{r1},o_0)=0.5$, but

• ${\mu }^{\prime }(o_0{a}^w{o}^{w0}\mid o_0{a}^r{o}^{r1},o_0)={\sum }_{i=0}^1{\mu }^{\prime }(s_0=s_0^i\mid o_0{a}^r{o}^{r1}){\mu }^{\prime }(o_0{a}^w{o}^{w0}\mid s_0=s_0^i)=0\cdot 1+1\cdot 0=0$.

Conversely, if we consider the POMDP ${\mu }^{\prime \prime }$:

Then it's not hard to check that it's counterfactually equivalent with $\mu$.