Summary: Take the argmax of counterfactual expected utility, using a thin counterfactual which itself maximizes a priori expected utility.

Followup to: An environment for studying counterfactuals, Counterfactuals, thick and thin
Replacement for: Logical counterfactuals and differential privacy

In An environment for studying counterfactuals, I described a family of decision problems that elicit counterfactuals from an agent. In this post I'll redefine that family using reflective oracles, and define an optimal agent. I was aided in this work by discussions with Alex Appell, James Brooks, Abram Demski, Linda Linsefors, and Alex Mennen.

The problem

Here's the (not quite) Bayes net for the problem. I changed it a little from the last post, to make the thin counterfactuals more explicit:

$E$ controls exploration and $S$ is a hidden state. The observation $O$ is isomorphic as a random variable to $E\times S$, but the particular isomorphism $\hat{\kappa }$ used by the problem is unknown to the agent.

The agent is given $O$ and a prior $P$; it outputs a set $C$ of counterfactual expected utilities, one for each action. The agent's action $A$ is equal to the argmax of these expectations, unless it's overridden by $E$. The action and hidden state determine the utility $U$.

The dotted lines mean that $P$ is equal to the marginal over $E\times O\times A\times U$. The machinery of reflective oracles resolves the circularity.

Now I'll define this distribution in detail, using Python-like pseudocode. I ought to use a probabilistic programming language, but I don't know any of those. Note that if you have a reflective oracle, you can compute expectations of distributions in constant time, and you can compute argmaxes over sets of real numbers, with ties broken in an undetermined way. Real numbers and distributions can be represented by programs.

$environment\left(\right)$

The function $environment\left(\right)$ takes an agent and outputs a sample from a joint distribution over $E\times O\times A\times U$. The agent is a function that takes the environment and an observation and stochastically returns a set of counterfactual expectations, which is itself encoded as a function from actions to real numbers.

The environment samples $s$ from a uniform distribution. Usually $e$ is equal to the symbol $\ast$, meaning no exploration; but with probability $\epsilon$ it's a uniformly random action. It computes $o$ using the secret isomorphism $\hat{\kappa }$. It calls the agent to get its counterfactual expectations. It argmaxes over those expectations to get the action, unless $e$ overrides that. Finally, $u$ is sampled from a problem-dependent likelihood function that depends on $a$ and $s$.

define $environment\left(ag\right)$:

sample $s\sim Unif\left(S\right)$

sample $e\sim \epsilon Unif\left(A\right)+(1-\epsilon ){\delta }_{\ast }$

$o:=\hat{\kappa }(e,s)$

$c:=ag\left(curry\right(environment,ag),o)$

if $e\in A$: $a:=e$

else: sample $a\sim {argmax}_{a}c\left(a\right)$

sample $u\sim U|A=a,S=s$

return $(e,o,a,u)$

The agent

The agent's strategy is to choose a thin counterfactual that maximizes its a priori expected utility. We'll define a couple helper functions first.

$cfact\left(\right)$

The function $cfact\left(\right)$ takes a prior $P\in \Delta (E\times O\times A\times U)$, a thin counterfactual $\kappa :E\times S\approx O$, an observation $o\in O$, and an action $a\in A$, and deterministically outputs the expected utility conditional on $o$ and counterfactually conditional on $a$, taking the expectation with respect to $P$ and the counterfactual with respect to $\kappa$.

This is how to compute a thin counterfactual distribution: First condition on $O=o$ and use $\kappa$ to infer a posterior on $S$. Then forget $o$ but retain your posterior on $S$. Then condition on $A=a$. The reason this works is that $S$ is independent of $E$, so there's still a chance for $A=a$ by exploration.

define $cfact(P,\kappa ,o,a)$:

$s={pr}_S{\kappa }^{-1}\left(o\right)$

return $(E_P[U|O=\kappa (a,s\left)\right]P_P(E=a)+$

$E_P[U|O=\kappa (\ast ,s),A=a]P_P(A=a|O=\kappa (\ast ,s\left)\right)P_P(E=\ast ))/$

$(P_P(E=a)+P_P(A=a|O=\kappa (\ast ,s\left)\right)P_P(E=\ast ))$

$utility\left(\right)$

This function takes a prior and a thin counterfactual, and samples from the marginal on $U$ that would result if the agent used that thin counterfactual. The previous sentence uses the word "would", so you might think we need another thin counterfactual to make sense of it; but our agent is a program, and programs come with their own "thick" notion of counterfactual.

The calculation goes like this: Sample $e$ and $o$. If $e$ makes us explore, then that determines the action and we can sample a utility conditional on $e$ and $o$. Otherwise, we assume the action is chosen to maximize $cfact\left(\right)$.

define $utility(P,\kappa )$:

sample $e,o\sim P$

if $e\in A$: return $u\sim P|E=e,O=o$

else: return ${max}_{a}cfact(P,\kappa ,o,a)$

$agent\left(\right)$

The agent is given a prior and an observation, and outputs the expected utility conditional on $A=a$, for every $a$. This output is encoded in a program that takes an action and outputs a real number. The output may be stochastic because $agent\left(\right)$ contains an argmax which may be stochastic in case of ties.

The true thin counterfactual $\hat{\kappa }:E\times S\approx O$ determines a projection $O\to E$. The agent can deduce this projection by analyzing the prior: For every $o$, $P_P(E=e|O=o)=0$ for all but one value of $e$.

The argmax is taken over all isomorphisms $\kappa :E\times S\approx O$ that commute with projecting to $E$. I won't bother writing that out in the pseudocode:

define $agent(P,o)$:

$\kappa :={argmax}_{\kappa }{E}_P\left[utility\right(P,\kappa \left)\right]$

return $curry(cfact,P,\kappa ,o)$

Optimality theorems

One of the counterfactual expectations that the agent emits is factual. It's reasonable to ask whether that one is accurate.

Theorem: If $U$ is bounded by $U_{max}$ and $E=\ast$, then with probability $\ge 1-\sqrt{\epsilon }$, if we sample $a\sim A$, $s\sim S$, $o\sim O$, we have

$|agent(P,o)\left(a\right)-E[U|A=a,S=s]|<4U_{max}\sqrt{\epsilon }$

Proof: $agent(P,o)\left(a\right)=cfact(P,\kappa ,o,a)$ for some $\kappa$. That equals

$(E[U|O=\kappa (a,s\left)\right]P(E=a)+E[U|O=\kappa (\ast ,s),A=a]P[A=a|O=\kappa (\ast ,s\left)\right)P(E=\ast ))/D$

$=(E[U|O=\kappa (a,s\left)\right]\frac{\epsilon }{|A|}+E[U|O=o,A=a]P[A=a|O=o)(1-\epsilon ))/D$

where $s={pr}_S{\kappa }^{-1}\left(o\right)$ and $D=\frac{\epsilon }{|A|}+P(A=a|O=o)(1-\epsilon )$. With a little algebra, that gives us

$|agent(P,o)\left(a\right)-E[U|A=a,S=s]|<\frac{2U_{max}\epsilon }{\epsilon +(1-\epsilon )|A|P(A=a|O=o)}$

By the following lemma, with probability $\ge 1-\sqrt{(}\epsilon )$, we have $P(A=a|O=o)>\frac{\sqrt{\epsilon }}{|A|}$. A little more algebra concludes the proof. $■$

Lemma: Sample $x,y$ from a joint distribution over $X\times Y$. With probability $\ge 1-\epsilon$, we have $P(X=x|Y=y)>\frac{\epsilon }{|X|}$.

Now we'll prove that $agent\left(\right)$ gets an optimal amount of utility. First, a couple lemmas.

Lemma: $E\left[U\right]={max}_{\kappa }E\left[utility\right(P,\kappa \left)\right]$

Proof: By the definition of $environment\left(\right)$,

$E\left[U\right]={\Sigma }_{a}E[U|E=a]P(E=a)+(1-\epsilon )E_{o|e=\ast }{max}_{a}agent(P,o)\left(a\right)$

By definition of $agent\left(\right)$, this is

$=\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|E=a]+(1-\epsilon )E_{o|e=\ast }{E}_{\kappa }{max}_{a}cfact(P,\kappa ,o,a)$

where the expectation $E_{\kappa }$ is taken over the output distribution of ${argmax}_{\kappa }E\left[utility\right(P,\kappa \left)\right]$. By linearity of expectation,

$=E_{\kappa }[\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|E=a]+(1-\epsilon )E_{o|e=\ast }{max}_{a}cfact(P,\kappa ,o,a)]$

This is just

$=E_{\kappa }\left[utility\right(P,\kappa \left)\right]$

$={max}_{\kappa }E\left[utility\right(P,\kappa \left)\right]■$

Recall that $\hat{\kappa }$ is the secret isomorphism $E\times S\approx O$. The next lemma says that $utility(P,\hat{\kappa })$ represents the highest utility that an agent can get:

Lemma: $E\left[utility\right(P,\hat{\kappa }\left)\right]=\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|A=a]+(1-\epsilon )E[U|A={argmax}_{a}E[U|A=a,S=s\left]\right]$

Proof: Using the fact that

$E[U|O=\hat{\kappa }(a,s\left)\right]=E[U|A=a,S=s]$

and

$E[U|O=\hat{\kappa }(\ast ,s),A=a]=E[U|A=a,S=s]$

and the definition of $cfact\left(\right)$, we have

$cfact(P,\hat{\kappa },o,a)=E[U|A=a,S=s]$.

Plugging that in to the definition of $utility\left(\right)$, we get

$utility(P,\hat{\kappa })=\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|A=a]+(1-\epsilon )E{max}_{a}E[U|A=a,S=s]$

$=\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|A=a]+(1-\epsilon )E[U|A={argmax}_{a}E[U|A=a,S=s\left]\right]■$

Finally, this theorem says that the agent gets the highest possible utility:

Theorem: $E\left[U\right]=\frac{\epsilon }{|A|}{\Sigma }_{a}E[U|A=a]+(1-\epsilon )E[U|A={argmax}_{a}E[U|A=a,S=s\left]\right]$

Proof: Call the right-hand side $U_{opt}$. It's easy to see that $E\left[U\right]\le U_{opt}$. By the previous two lemmas, we also have

$E\left[U\right]={max}_{\kappa }E\left[utility\right(P,\kappa \left)\right]\ge E\left[utility\right(P,\hat{\kappa }\left)\right]=U_{opt}■$

What about Troll Bridge?

Troll Bridge is a problem that punishes exploration. You can't represent it in this framework because the action screens off exploration. But if you modified the framework to implement Troll Bridge, the agent would fail. (It would be afraid to cross the bridge.)

I suspect the solution to Troll Bridge is to use continuous exploration: Explore at every timestep of a logical inductor. If Troll Bridge punishes exploration at timestep $n$, then exploration at $n-1$ succeeds. I haven't worked this out yet.

What about counterfactual mugging?

This agent doesn't get counterfactually mugged. (This is bad.) This agent only exhibits one of the two types of updatelessness.

Next steps

The notion of "thin counterfactual" used here is more specific than it needs to be. I'd like to generalize it.

Once I do that, I might be able to formulate the symmetric Prisoner's Dilemma. I'm not sure how this agent does on that problem.

I also want to implement this agent in the setting of logical induction. I'm imagining traders getting licenses to participate in thin counterfactual markets, and the licenses prohibit them from learning the price of $A=a$. This will also involve some kind of continuous exploration.