EDT solves 5 and 10 with conditional oracles

jessicata

Introduction and motivation

The starting point for this post is a comment I wrote on Paul's post on EDT vs CDT:

One argument for CDT over EDT that you didn’t mention in this post: Suppose you live in a deterministic universe and know your own source code. Suppose you are deciding between taking a 5 dollar bill and a 10 dollar bill. Suppose your world model says you take the 5 dollar bill with 100% probability. Now conditioning on taking the 10 dollar bill gives you complete garbage, since you are conditioning on a probability 0 event. If you use EDT, then depending on other details of your decision procedure, this could lead to you always taking the 5 dollar bill. So then your world model would be accurate. (This is the “5 and 10” problem often discussed at MIRI; I don’t know if it has been written up anywhere)

CDT never generates undefined expected utility estimates like EDT does. It takes the 10 dollar bill in this problem. However, if it always takes the 10 dollar bill, then its counterfactual for taking the 5 dollar bill is strange because it is one in which a physical law is violated. The violation of a physical law could have important consequences other than which action the agent takes.

Both decision theories have trouble with this problem, but at least CDT always produces a defined answer.

Here’s another way of thinking about this problem. A fully Bayesian version of EDT must construct all possible worlds and then condition on taking a certain action. But each of these possible worlds contains a running copy of the EDT algorithm. So, absent some defined method for taking a fixed point, this leads to an infinite loop, and you can’t actually have a fully Bayesian version of EDT.

(What if you use reflective oracles to allow EDT to select some fixed point? We could specify that the reflective oracle returns arbitrary results when asked to condition on a probability 0 event (I think this is what the most natural way to emulate conditional queries on a reflective oracle results in, but I haven’t checked). Now there are multiple possible reflective oracles (i.e. fixed points); it’s possible to always take the 10 dollar bill and think bad things will happen conditional on taking the 5 dollar bill, and it’s also possible to always take the 5 dollar bill and think bad things will happen conditional on taking the 10 dollar bill.)

A fully Bayesian version of CDT must construct all possible counterfactuals. Each of these counterfactuals contains a running copy of CDT, so one might think the same problem applies. But in each of these counterfactuals, the output of the CDT algorithm is “thrown away”, since the agent’s action is controlled by a magic counterfactual intervention rather than its algorithm. So, if the CDT algorithm is sandboxed, the CDT’s world model can simply ignore the running CDT algorithm, as it has no effect. Thus, at least in single-agent problems (with no predictors etc), a fully Bayesian version of CDT is possible in principle, though obviously not in practice.

Some time during or after writing this comment, I noticed something: the equilibrium where the EDT agent thinks it always takes the 5 dollar bill, and therefore gets garbage (possibly low) estimates when considering taking the 10 dollar bill, and therefore never takes the 10 dollar bill, is extremely unstable. As soon as the agent assigns any probability at all to taking the 10 dollar bill, their conditional expected utility estimates are perfect. Can we use this fact to design a variant of EDT that always takes the 10 dollar bill?

Yes, yes we can.

Definitions and main theorem statements

Reflective conditional oracle distributions will be defined similar to in previous work such as reflective oracles and reflective oracle distributions. I recommend understanding reflective oracles before reading this post (understanding reflective oracle distributions is helpful but unnecessary).

Let be some finite subset of the set of probabilistic Turing machines that may query a conditional oracle (defined in the next paragraph). They must each always halt and return either 0 or 1.

Definition 1: A conditional oracle is a function $O : M^{4} \to {0, 1}$ .

Intuitively, $O (m_{1}, n_{1}, m_{2}, n_{2})$ asks whether $P (m_{1}^{O^{'}} () | n_{1}^{O^{'}} ())$ is greater or less than $P (m_{2}^{O^{'}} () | n_{2}^{O^{'}} ())$ , where $O^{'}$ is taken from some distribution over conditional oracles.

We make the assumption that machines in $M$ only ever query the oracle with an element of $M^{4}$ . All further definitions and lemmas/theorems are parameterized on some $M$ satisfying this assumption.

Definition 2: A conditional oracle distribution (COD) is a distribution over conditional oracles, of type $Δ (M^{4} \to {0, 1})$ .

Definition 3: A COD is fully-mixed if it assigns nonzero probability to each possible conditional oracle.

Since the number of conditional oracles is finite, there are fully-mixed CODs.

Definition 4: A COD $Q$ weakly leads to a COD $Q^{'}$ iff, for all $m_{1}, n_{1}, m_{2}, n_{2} \in M, p \in P$ :

$P_{Q} (m_{1}^{O} () = 1 \land n_{1}^{O} () = 1) P_{Q} (n_{2}^{O} () = 1) > P_{Q} (m_{2}^{O} () = 1 \land n_{2}^{O} () = 1) P_{Q} (n^{O} () = 1) \to P_{Q^{'}} (O (m_{1}, n_{1}, m_{2}, n_{2}) = 1) = 1$

$P_{Q} (m_{1}^{O} () = 1 \land n_{1}^{O} () = 1) P_{Q} (n_{2}^{O} () = 1) < P_{Q} (m_{2}^{O} () = 1 \land n_{2}^{O} () = 1) P_{Q} (n^{O} () = 1) \to P_{Q^{'}} (O (m_{1}, n_{1}, m_{2}, n_{2}) = 0) = 1$

(Here, the notation $P_{Q} (E)$ refers to the probability of event $E$ when $O \sim Q$ .)

Intuitively, $Q$ weakly leads to $Q^{'}$ iff $Q^{'}$ accurately answers conditional queries that are about $Q$ . If $n_{1}^{O} () = 1$ for some $O$ and also $n_{2}^{O} () = 1$ for some (possibly different) $O$ and $Q$ is fully-mixed, these conditions are equivalent to:

$P_{Q} (m_{1}^{O} () = 1 ∣ n_{1}^{O} () = 1) > P_{Q} (m - o^{O} () = 1 ∣ n_{2}^{O} () = 1) \to P_{Q^{'}} (O (m_{1}, n_{1}, m_{2}, n_{2}) = 1) = 1$

$P_{Q} (m_{1}^{O} () = 1 ∣ n_{1}^{O} () = 1) < P_{Q} (m - o^{O} () = 1 ∣ n_{2}^{O} () = 1) \to P_{Q^{'}} (O (m_{1}, n_{1}, m_{2}, n_{2}) = 0) = 1$

As notation, let $S t e p W e a k : Δ (M^{4} \to {0, 1}) \to P o w e r S e t (Δ (M^{4} \to {0, 1}))$ map a COD to the set of CODs it weakly leads to. This and related functions will be interpreted as set-valued when referring to their graphs.

Unfortunately, these conditional queries are not sensible when $P_{Q} (n_{1}^{O} () = 1) = 0$ or $P_{Q} (n_{2}^{O} () = 1) = 0$ ; the oracle is allowed to return any answer. We will define a stricter notion of "leading to" that will require these answers to be sensible.

Let $S t e p C l o s u r e : Δ (M^{4} \to {0, 1}) \to P o w e r S e t (Δ (M^{4} \to {0, 1}))$ be a set-valued function whose graph is the closure of (the graph of $S t e p W e a k$ restricted to $(Q, Q^{'})$ where $Q$ is fully-mixed). It will turn out that $S t e p C l o s u r e (Q) = S t e p W e a k (Q)$ for fully-mixed $Q$ .

Equivalently, $Q^{'} \in S t e p C l o s u r e (Q)$ iff there are infinite COD sequences $Q_{1}, Q_{2}, \dots$ and $Q_{1}^{'}, Q_{2}^{'}, \dots$ such that (a) each $Q_{i}$ is fully mixed, (b) each $Q_{i}$ weakly leads to $Q_{i}^{'}$ , (c) ${Q_{i}}_{i}$ limits to $Q$ , and (d) ${Q_{i}^{'}}_{i}$ limits to $Q^{'}$ .

Intuitively, $S t e p C l o s u r e$ is equivalent to $S t e p W e a k$ for fully-mixed $Q$ and generalizes to non-fully-mixed $Q$ through taking limits that involve only fully-mixed $Q$ values.

Define $S t e p H u l l (Q) := C o n v e x H u l l (S t e p C l o s u r e (Q))$ . It will turn out that $S t e p H u l l (Q) = S t e p C l o s u r e (Q) = S t e p W e a k (Q)$ for fully-mixed $Q$ .

(Why take the convex hull? This is to make $S t e p H u l l$ a Kakutani map. It might be the case that $S t e p C l o s u r e (Q)$ is always convex but I haven't proven this.)

Definition 5: A COD $Q$ leads to a COD $Q^{'}$ iff $Q^{'} \in S t e p H u l l (Q)$ .

Due to Theorem 1, it will turn out that a fully-mixed COD $Q$ leads to $Q^{'}$ iff it strictly leads to $Q^{'}$ . Leading to is a stronger condition than weak leading to, as will be proven.

At this point we are ready to define a reflection condition:

Definition 6: A COD is reflective iff it leads to itself.

Intuitively, a COD is reflective iff it accurately answers queries that are about itself.

This post's main results are the following (in addition to the proof that EDT beats 5 and 10):

Theorem 1: For any fully-mixed COD $Q$ , $S t e p W e a k (Q) = S t e p C l o s u r e (Q) = S t e p H u l l (Q)$ .

Theorem 2: If $Q$ leads to $Q^{'}$ , then it weakly leads to $Q^{'}$ .

Theorem 3: There is a reflective COD.

These are proven at the end of the post.

Defining EDT

EDT can be defined using a reflective COD; this decision theory will be called COEDT. Let the decision problem be described by a Turing machine with an embedded agent, where this Turing machine including its agent may randomize and call a conditional oracle, and which returns either 0 or 1 to represent the agent's utility (intermediate utilities can be emulated by randomizing). For example, for the 5 and 10 problem, we may define:

${F i v e T e n}^{O} (⌈ A ⌉) := A^{O} ()$

where $⌈ A ⌉$ is the source code of the agent $A$ .

COEDT is a function from the universe program (which already contains an embedded COEDT agent) to action. The following COEDT variant handles cases where there are only 2 actions:

$C O E D T^{O} (⌈ U ⌉) := O (⌈ U^{O} () ⌉, ⌈ C O E D T^{O} (⌈ U ⌉) ⌉, ⌈ U^{O} () ⌉, ⌈ 1 - C O E D T^{O} (⌈ U ⌉) ⌉)$

It uses the conditional oracle to determine if it has a higher chance of winning conditional on taking action 1 or action 0, and takes the action that it is more likely to win conditional on taking.

What does $C O E D T$ do on $F i v e T e n$ ? We can take a fixed point:

$U^{O} () := {F i v e T e n}^{O} (⌈ C O E D T^{O} (⌈ U ⌉) ⌉)$

Let the set of machines considered be

$M := {⌈ U^{O} () ⌉, ⌈ C O E D T^{O} (⌈ U ⌉) ⌉, ⌈ 1 - E D T^{O} (⌈ U ⌉)}$

Theorem 4: For any reflective COD $Q$ on $M$ , $P_{Q} (C O E D T^{O} (⌈ U ⌉) = 1) = 1$ .

Proof:

Informally, this is true because the agent must always take action 1 when queries are about any fully-mixed COD.

$Q \in S t e p H u l l (Q)$ , so it is a convex combination of CODs in $S t e p C l o s u r e (Q)$ . Let that convex combination be $\sum_{j = 1}^{k} λ^{j} {Q^{'}}^{j}$ .

Each ${Q^{'}}^{j} \in S t e p C l o s u r e (Q)$ , so we have COD sequences ${Q_{i}^{j}}_{i}$ limiting to $Q$ (with each being fully mixed) and ${{Q^{'}}_{i}^{j}}_{i}$ limiting to ${Q^{'}}^{j}$ such that each ${Q^{' j}}_{i} \in S t e p W e a k (Q_{i}^{j})$ .

For each $i, j$ , since $C O E D T^{O} (⌈ U ⌉)$ and $1 - C O E D T^{O} (⌈ U ⌉)$ both return 1 for some conditional oracles, and because $Q_{i}^{j}$ weakly leads to ${Q^{'}}_{i}^{j}$ , we have:

$P_{Q_{i}^{j}} (U^{O} () = 1 ∣ C O E D T^{O} (⌈ U ⌉) = 1) > P_{Q}$

AI ALIGNMENT FORUM
AF

27

EDT solves 5 and 10 with conditional oracles

27

Introduction and motivation

Definitions and main theorem statements

Defining EDT