Logical counterfactuals and differential privacy

[Nisan]

Edit: This article has major flaws. See my comment below.

This idea was informed by discussions with Abram Demski, Scott Garrabrant, and the MIRIchi discussion group.

Summary

For a logical inductor $P$, define logical counterfactuals by

$$P_n\left(\varphi |\psi \right):=\sum _y{P}_k(\varphi |\psi \wedge Y=y)P_n(Y=y)$$

for a suitable $k<n$ and a random variable $Y$ independent of $\psi$ with respect to $P_k$. Using this definition, one can construct agents that perform well in ASP-like problems.

Motivation

Recall the Agent Simulates Predictor problem:

$$U_n={10}^6{P}_{n-1}(A_n=1)+{10}^{3}1(A_n=2)$$

Naively, we want to solve this by argmaxing:

$$A_n={\mathrm{argmax}}_a{E}_n[U_n|A_n=a]$$

Hopefully, $P_n(A_n=1)\approx 1$, $P_{n-1}(A_n=1)\approx 1$, and $E_n[U_n|A_n=1]\approx {10}^6$. Also, two-boxing should be less attractive than one-boxing:

$$E_n[U_n|A_n=2]\approx {10}^3$$

However, if we make this well-defined with $\epsilon$-exploration, we’ll get

$$E_n[U_n|A_n=2]\approx {10}^6+{10}^3$$

and then the agent will two-box, contradiction. Instead we’d like to use predictable exploration and set

$$E_n[U_n|A_n=2]:=E_k[U_n|A_n=2]$$

for $k$ small enough that the right-hand side is sensible. Let’s see how.

Predictable exploration

Choose $k\ll n$ so that $P_k(A_n=2)\gg 0$. Our agent decides whether to explore at stage $k$, and uses its beliefs at stage $k$ as a substitute for counterfactuals:

$$\begin{array}{cc}{\mathrm{explore}}_0& :=P_k\left({\mathrm{explore}}_0\right)<\epsilon \\ {\mathrm{explore}}_1& :=\{\begin{array}{cc}1& P_k({\mathrm{explore}}_1=1)<\frac{1}{2}\\ 2& \text{otherwise}\end{array}\\ \forall a{E}_n(\varphi |A=a)& :=E_k(\varphi |A=a\wedge {\mathrm{explore}}_0)\text{if}{P}_n(A=a)<\delta \\ A_n& :=\{\begin{array}{cc}{\mathrm{explore}}_1& \text{if}{\mathrm{explore}}_0\\ {\mathrm{argmax}}_a{E}_n[U_n|A_n=a]& \text{otherwise}\end{array}\end{array}$$

Here $\epsilon ,\delta$ are small positive numbers. It’s easy to see that, under reasonable assumptions, this agent 1-boxes on Agent Simulates Predictor. But it can’t use the full strength of $P_n$ in its counterfactual reasoning, and this is a problem.

Differential privacy

To illustrate the problem, add a term to the utility function that sometimes rewards two-boxing:

$$\begin{array}{cc}{U}_n& ={10}^6{P}_{n-1}(A_n=1)+{10}^{3}1(A_n=2)+{10}^{6}1(A_n=2\wedge X_{n-1})\\ X_{n-1}& :=P_{n-1}\left(X_{n-1}\right)<\frac{1}{2}\end{array}$$

The agent should two-box if and only if $X$. Assuming that’s the case, and $P_{n-1}$ knows this, we have:

$$\begin{array}{cc}{P}_{n-1}(A_n=1)& =\frac{1}{2}\\ \neg X_{n-1}\to E_n[U_n|A_n=1]& =\frac{1}{2}{10}^6\\ \neg X_{n-1}\to E_n[U_n|A_n=2]& =E_k[U_n|A_n=2\wedge {\mathrm{explore}}_0]\\ & ={10}^3+\frac{1}{2}{10}^6\end{array}$$

So if $\neg X_{n-1}$, two-boxing is the more attractive option, which is a contradiction. (I’m rounding $\epsilon$ to zero for simplicity.)

The problem is that the counterfactual has to rely on $P_k$‘s imperfect knowledge of $X_{n-1}$. We want to combine $P_k$‘s ignorance of ${\mathrm{explore}}_0$ with $P_n$’s knowledge of $X_{n-1}$.

If $X$ is independent of $A$ conditioned on ${\mathrm{explore}}_0$ with respect to $P_k$, then we can do this:

$$\begin{array}{cc}{E}_k[U|A=a\wedge {\mathrm{explore}}_0]& =\sum _x{E}_k[U|A=a\wedge {\mathrm{explore}}_0\wedge X=x]P_k(X=x|A=a\wedge {\mathrm{explore}}_0)\\ & =\sum _x{E}_k[U|A=a\wedge {\mathrm{explore}}_0\wedge X=x]P_k(X=x|{\mathrm{explore}}_0)\end{array}$$

Then replace $P_k(X=x|{\mathrm{explore}}_0)$ with $P_n(X=x|{\mathrm{explore}}_0)$:

$$E_n[U|A=a\wedge {\mathrm{explore}}_0]:=\sum _x{E}_k[U|A=a\wedge {\mathrm{explore}}_0\wedge X=x]P_n(X=x|{\mathrm{explore}}_0)$$

This is more accurate than $E_n[U|A=a\wedge {\mathrm{explore}}_0]$, and unbiased.

If $X$ is not independent of $A$ conditional on ${\mathrm{explore}}_0$, we can introduce an auxilliary variable and construct a version of $X$ that is independent. This construction is a solution to the following differential privacy problem: Make a random variable $Y$ that is a function of $X$ and independent randomness, maximizing the mutual conditional information $H(X;Y|A)$, subject to the constraint that $A$ is independent of $Y$. Using the identity

$$H\left(X|A\right)=H(X;Y|A)+H\left(X|AY\right)$$

we see that the maximum is attained when $H\left(X|AY\right)=0$, which means that $X$ is a function of $A$ and $Y$.

Now here’s the construction of $Y$:

Let $X$ be the finite set of possible values of $X$, and let $A$ be the finite set of possible values of $A$. We’ll iteratively construct a set $Y$ and define a random variable $Y$ taking values in $Y$. To start with, let $Y=\varnothing$.

Now choose

$$(a,x):={\mathrm{argmin}}_{\begin{array}{c}a\in A\\ x\in X\\ P(X=x,Y\notin Y|A=a)>0\end{array}}P(X=x,Y\notin Y|A=a)$$

and for each $a^{\prime }\in A\setminus \left\{a\right\}$, choose some $f\left(a^{\prime }\right)\in X$ such that $P(X=f(a^{\prime }),Y\notin Y|A=a^{\prime })>0$. Then make a random binary variable $T_{a^{\prime }}$ such that

$$P(T_{a^{\prime }}\wedge X=f(a^{\prime })\wedge Y\notin Y|A=a^{\prime })=P(X=x\wedge Y\notin Y|A=a)$$

Then let $y$ be the event defined by

$$(X=x\wedge Y\notin Y\wedge A=a)\vee \underset{a^{\prime }\in A\setminus \left\{a\right\}}{\bigvee }(T_{a^{\prime }}\wedge X=f(a^{\prime })\wedge Y\notin Y\wedge A=a^{\prime })$$

and add $y$ to $Y$. After repeating this process $|X||A|$ times, we are done.

We can do this with a logical inductor as well. In general, to get a sentence $T$ such that $P_k(T\wedge B|C)\approx p$, take $T:=P_k(T\wedge B|C)<p\wedge B\wedge C$.

Now given random variables $U$ and $A$, and some informative sentences ${\varphi }_1,\dots ,{\varphi }_{\ell }$, let $X\in \{T,F{\}}^{\ell }$ be the random variable encoding the values of ${\varphi }_0,\dots ,{\varphi }_{\ell -1}$. The above construction works approximately and conditional on ${\mathrm{explore}}_0$ to give us a random variable $Y$ that is approximately independent of $A$ conditional on ${\mathrm{explore}}_0$ with respect to $P_k$. Now we define

$$E_n[U|A=a]:=\sum _y{E}_k[U|A=a\wedge {\mathrm{explore}}_0\wedge Y=y]P_n(Y=y|{\mathrm{explore}}_0)$$

whenever $P_n(A=a)<\delta$.

This succeeds on the problem at the beginning of this section: Assume $A_n=2\leftrightarrow X_{n-1}$, and assume that $P_{n-1}$ knows this. Then:

$$\begin{array}{cc}{P}_{n-1}(A_n=1)& =\frac{1}{2}\\ \neg X_{n-1}\to E_n[U_n|A_n=1]& =\frac{1}{2}{10}^6\\ \neg X_{n-1}\to E_n[U_n|A_n=2]& =E_k[U_n|A_n=2\wedge {\mathrm{explore}}_0\wedge \neg X_{n-1}]\\ & ={10}^3\\ X_{n-1}\to E_n[U_n|A_n=2]& =\frac{1}{2}{10}^6+{10}^3+{10}^6\\ X_{n-1}\to E_n[U_n|A_n=1]& =E_k[U_n|A_n=1\wedge {\mathrm{explore}}_0\wedge X_{n-1}\\ & ={10}^6\end{array}$$

which does not lead to contradiction. In fact, there are agents like this that do at least as well as any constant agent:

Theorem

Let $U_n(P,A)$ be a utility function defined with metasyntactic variables $n$, $P$, and $A$. It must be computable in polynomial time as a function of $A$, $P_{f_i\left(n\right)}(A=a)$, and $X:=P_{f_i\left(n\right)}\left(X\right)<p$, where $f_i$ can be any polytime functions that doesn’t grow too slowly and such that $f_i\left(n\right)<n$. Then there exists a logical inductor $P$ such that for every $n$, there exists $k<n$, $\epsilon ,\delta >0$, and a pseudorandom variable $Y$ such that the agent $A$ defined below performs at least as well on $U_n$ as any constant agent, up to a margin of error that approaches $0$ as $n\to \infty$:

$$\begin{array}{cc}{\mathrm{explore}}_0& :=P_k\left({\mathrm{explore}}_0\right)<\epsilon \\ {\mathrm{explore}}_1& :=\{\begin{array}{cc}{a}_1& \text{if}{P}_k({\mathrm{explore}}_1=a_1)<\frac{1}{\ell }\text{; else}\\ a_2& \text{if}{P}_k({\mathrm{explore}}_1=a_2)<\frac{1}{\ell }\text{; else}\\ ⋮& \\ a_{\ell }& \text{otherwise}\end{array}\\ \forall a{E}_n(\varphi |A=a)& :=\sum _y{E}_k(\varphi |A=a\wedge {\mathrm{explore}}_0\wedge Y=y)P_n(Y=y|{\mathrm{explore}}_0)\text{if}{P}_n(A=a)<\delta \\ A_n& :=\{\begin{array}{cc}{\mathrm{explore}}_1& \text{if}{\mathrm{explore}}_0\\ {\mathrm{argmax}}_a{E}_n[U_n|A_n=a]& \text{otherwise}\end{array}\end{array}$$

Proof sketch

Choose $k$ smaller than the strength parameter of the weakest predictor in $U_n$. If $a_n$ is the best constant policy for $U_n$, assume $A_n=a_n$. Since $P_n$ can compute $U_n$, our agent’s factual estimate $E_n[U_n|A_n=a_n]$ is accurate, and the counterfactual estimate $E_n[U_n|A_n=a^{\prime }]$ for $a^{\prime }\ne a_n$ is an accurate estimate of the utility assigned to the constant policy $a^{\prime }$, as long as we make $Y$ rich enough. So the agent will choose $a_n$. Thus we have an implication of the form “if $P$ believes $A_n=a_n$, then $A_n=a_n$ is true”, and so we can create a logical inductor $P$ that always believes that $A_n=a_n$ for every $n$ by adding a trader with a large budget that bids up the price of $A_n=a_n$.

Isn’t this just UDTv2?

This is much less general than UDTv2. If you like, you can think of this as an agent that at time $k$ chooses a program to run, and then runs that program at time $n$, except the program always happens to be “argmax over this kind of counterfactual”.

Also, it doesn’t do policy selection.

Next steps

Instead of handing the agent a pseudorandom variable $Y$ that captures everything important, I’d like to have traders inside a logical inductor figure out what $Y$ should be on their own.

Also, I’d rather not have to hand the agent an optimal value of $k$.

Also, I hope that these counterfactuals can be used to do policy selection and win at counterfactual mugging.

[Nisan]

This doesn’t quite work. The theorem and examples only work if you maximize the unconditional mutual information, $H(X;Y)$, not $H(X;Y|A)$. And the choice of $X$ is doing a lot of work — it’s not enough to make it “sufficiently rich”.