Intelligent Agent Foundations Forumsign up / log in
A correlated analogue of reflective oracles
post by Jessica Taylor 27 days ago | Sam Eisenstat, Vadim Kosoy, Abram Demski and Scott Garrabrant like this | discuss

Summary: Reflective oracles correspond to Nash equilibria. A correlated version of reflective oracles exists and corresponds to correlated equilibria. The set of these objects is convex, which is useful.

(thanks to Sam for a lot of help with coming up with constructions)


Reflective oracles assign a probability to each query. The set of reflective oracles is not convex. For example, consider a machine \(M^O() := O(M, 0.5)\) (i.e. a machine that asks whether the probability that it returns 1 is at least 0.5). There are reflective oracles that assign probabilities 0, 0.5, and 1 to the query \(O(M, 0.5)\), and there aren’t reflective oracles that assign other probabilities. So the set of possible reflective oracles isn’t convex. This is for the same reason that the set of Nash equilibria isn’t always convex.

Related to the non-convexity, there isn’t in general a continuous way of mapping the numerical parameters of some Turing machines to a reflective oracle for those machines (or doing so as a Kakutani map). (Like there isn’t a way of Kakutani-mapping the parameters of a game to an \(\epsilon\)-approximate Nash equilibrium for that game).

This makes decision problems involving reflective oracles harder to analyze: the function mapping agents’ policies to the resulting reflective oracle will be discontinuous.

So to analyze these decision problems, it might be useful to construct a convex set analogous to the non-convex set of reflective oracles. Luckily, the set of correlated equilibria in a game is convex. This post presents an analogue of them in reflective oracle land.


An oracle (mapping from queries to answers) will be selected at random from some distribution. A query can ask about the distribution over oracles, conditional on the answer to that query.

Definitions: machines, oracles, queries

Let \(\mathcal{M}\) be some finite set of Turing machines that ZFC-provably halt on every input. (We could in principle deal with both infinite sets of Turing machines and possibly-non-halting Turing machines, as ordinary reflective oracles do, but this complicates things somewhat).

An oracle \(O\) maps each machine in \(\mathcal{M}\) to a natural number. The set of oracles is \(\mathcal{O} := \mathcal{M} \rightarrow \mathbb{N}\).

An oracle distribution \(D\) is a probability distribution over oracles. The set of oracle distributions is \(\mathcal{D} := \Delta \mathcal{O}\).

A query to an oracle is a way of asking about an oracle distribution in an “argmax” fashion. A query \(q\) is represented as a list of functions \(q_1, q_2, ..., q_{l(q)} : \mathcal{O} \rightarrow \mathbb{R}\). Write \(q(D) := \arg\max_{i \in \{1, 2, ..., k_q\}} \mathbb{E}_D[q_i(O)]\); in words, the query asks for some \(i\) such that \(q_i\) has maximum expectation on the oracle distribution. Note that:

  1. \(q(D)\) is non-empty for each \(D\)
  2. for each \(i \in \{1, 2, ..., k_q\}\), \(\{D | i \in q(D)\}\) is convex

Let \(\mathcal{Q}\) be the set of queries. Roughly, the set of allowed queries are those that partition the set of oracle distributions into a bunch of convex polygons; this allows for arbitrarily fine-precision queries about the distribution.

Let us interpret the output of each Turing machine (on the empty input) as a query. Some encoding scheme is necessary; I don’t think it matters much. So assume we have a map \(\mathrm{Eval} : \mathcal{M} \rightarrow \mathcal{Q}\). (The main reason for representing queries using Turing machines is to allow quining).

We will impose one additional restriction: for any machine \(M\), the query \(q\) it outputs must not depend on the distribution over \(O(M)\) (i.e. the query is actually only a function of the joint distribution over each \(O(M')\) value other than \(O(M)\) itself). This is to avoid liar’s paradoxes.


An oracle distribution \(D\) is reflective if, for each \(M \in \mathcal{M}\), and each \(a\) such that \(D(O(M) = a) > 0\):

\[a \in \mathrm{Eval}(M)(\mathrm{Condition}(D, M, a))\]

where \(\mathrm{Condition}(D, M, a)\) is an oracle distribution formed by conditioning the oracle distribution \(D\) on the event \(O(M) = a\).

In words, an oracle distribution is reflective if each possible answer to each query is correct thing to say about the distribution over oracles conditional on the answer to that query.

Theorem 1: A reflective joint oracle exists.


This oracle distribution will independently roll a die for each query to produce \(O\). Specifically, it is formed by a mapping \(\tilde{O} : \mathcal{M} \rightarrow \Delta \mathbb{N}\). Let the function \(d\) map \(\tilde{O}\) to an oracle distribution through independent sampling.

Define \(f(\tilde{O}) := \times_{M \in \mathcal{M}} \Delta (\mathrm{Eval}(M)(d(\tilde{O}))\), where \(\times\) indicates a Cartesian product, and \(\Delta S\) is the set of probability distributions over the set \(S\) (which is finite in this case). Note that \(f(\tilde{O})\) is always non-empty and that \(f\) is upper-hemicontinuous (by Berge’s Maximum Theorem). So by Kakutani’s Fixed Point Theorem, there is some mapping \(\tilde{O}\) such that \(\tilde{O} \in f(\tilde{O})\).

Consider the oracle distribution \(d(\tilde{O})\). For any \(M \in \mathcal{M}\), and \(O \in \mathrm{Support}(d(\tilde{O}))\), we have

\[O(M) \in \mathrm{Eval}(M)(d(\tilde{O})) = \mathrm{Eval}(M)(\mathrm{Condition}(d(\tilde{O}), M, O(M)))\]

where the second equality follows from (a) the fact that \(\mathrm{Eval}(M)\) does not depend on the distribution over \(O(M)\) and (b) the fact that all \(O(M)\) values are independent under \(d(\tilde{O})\). So \(d(O^*)\) is reflective.


Theorem 2: The set of reflective oracle distributions is convex.


Let \(D_0, D_1\) be reflective oracle distributions. Let \(\theta \in (0, 1)\). Define \(D_\theta := \theta D_0 + (1 - \theta) D_1\). This proof will show that \(D_\theta\) is reflective.

Let \(1 \leq i \leq n\). Let \(M \in \mathcal{M}\). Let \(a\) be such that \(D_\theta(O(M) = a) > 0\). Consider 3 cases:

  1. \(D_0(O(M) = a) > 0, D_1(O(M) = a) = 0\). Then \(a \in \mathrm{Eval}(M)(\mathrm{Condition}(D_0, M, a))\). But since \(D_1(O(M) = a) = 0\), we have \(\mathrm{Condition}(D_\theta, M, a) = \mathrm{Condition}(D_0, M, a)\). So \(a \in \mathrm{Eval}(M)(\mathrm{Condition}(D_\theta, M, a))\) as desired.
  2. \(D_0(O(M) = a) = 0, D_1(O(M) = a) > 0\). This is analogous to case 1.
  3. \(D_0(O(M) = a) > 0, D_1(O(M) = a) > 0\). We have \(a \in \mathrm{Eval}(M)(\mathrm{Condition}(D_0, M, a))\) and \(a \in \mathrm{Eval}(M)(\mathrm{Condition}(D_1, M, a))\). Note that \(\mathrm{Condition}(D_\theta, M, a)\) is a convex combination of \(\mathrm{Condition}(D_0, M, a)\) and \(\mathrm{Condition}(D_1, M, a)\) (this is a basic property of mixture distributions: the conditioning of a mixture of components is a mixture of the conditionings of the components). The set \(\{D | a \in \mathrm{Eval}(M)(D)\}\) is convex (from \(\mathrm{Eval}(M)\) being a query); therefore \(a \in \mathrm{Eval}(M)(\mathrm{Condition}(D_\theta, M, a))\), as desired.


Correspondence with correlated equilibria

Reflective oracle distributions can be used to find correlated equilibria. Say we have a normal-form game with \(n\) players, where each player \(i\) selects an action \(A_i \in \mathcal{A}_i\), and receives utility \(U_i(A_1, ..., A_n)\). Define queries as follows:

\[q_i(D) := \arg\max_{a \in \mathcal{A}_i} \mathbb{E}_D[U_i(O(M_1), ..., O(M_{i-1}), a, O(M_{i+1}), ..., O(M_n))]\]

where the machine \(M_i\) computes a representation of the query \(q_i\) (the recursion works through mutual quining). It’s easy to show that reflective oracle distributions (for the set of machines \(\{M_1, ..., M_n\}\)) correspond exactly with correlated equilibria in the game.

Thus, as ordinary reflective oracles naturally yield Nash equilibria when causal decision theorists using them play games with each other, so do reflective oracle distributions naturally yield correlated equilibria when causal decision theorists using them play games with each other.

\(\epsilon\)-approximate correlated equilibria can be computed in polynomial time (see lectures 17+18 here). I conjecture that \(\epsilon\)-approximate reflective oracle distributions over a finite set of queries can also be found in polynomial time, perhaps by reducing the problem of finding \(\epsilon\)-approximate reflective oracle distributions to the problem of finding \(\epsilon\)-approximate correlated equilibria.





The "benign induction
by David Krueger on Why I am not currently working on the AAMLS agenda | 0 likes

This comment is to explain
by Alex Mennen on Formal Open Problem in Decision Theory | 0 likes

Thanks for writing this -- I
by Daniel Dewey on AI safety: three human problems and one AI issue | 1 like

I think it does do the double
by Stuart Armstrong on Acausal trade: double decrease | 0 likes

>but the agent incorrectly
by Stuart Armstrong on CIRL Wireheading | 0 likes

I think the double decrease
by Owen Cotton-Barratt on Acausal trade: double decrease | 0 likes

The problem is that our
by Scott Garrabrant on Cooperative Oracles: Nonexploited Bargaining | 1 like

Yeah. The original generator
by Scott Garrabrant on Cooperative Oracles: Nonexploited Bargaining | 0 likes

I don't see how it would. The
by Scott Garrabrant on Cooperative Oracles: Nonexploited Bargaining | 1 like

Does this generalise to
by Stuart Armstrong on Cooperative Oracles: Nonexploited Bargaining | 0 likes

>Every point in this set is a
by Stuart Armstrong on Cooperative Oracles: Nonexploited Bargaining | 0 likes

This seems a proper version
by Stuart Armstrong on Cooperative Oracles: Nonexploited Bargaining | 0 likes

This doesn't seem to me to
by Stuart Armstrong on Change utility, reduce extortion | 0 likes

[_Regret Theory with General
by Abram Demski on Generalizing Foundations of Decision Theory II | 0 likes

It's not clear whether we
by Paul Christiano on Infinite ethics comparisons | 1 like


Privacy & Terms