A correlated analogue of reflective oracles

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)

Motivation

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 $ϵ$ -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.

Setup

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 $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 $M$ to a natural number. The set of oracles is $O := M \to N$ .

An oracle distribution $D$ is a probability distribution over oracles. The set of oracle distributions is $D := Δ 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)} : O \to R$ . Write $q (D) := arg {max}_{i \in {1, 2, . . ., k_{q}}} 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:

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

Let $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 $E v a l : M \to 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.

Reflectivity

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

$a \in E v a l (M) (C o n d i t i o n (D, M, a))$

where $C o n d i t i o n (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.

Proof:

This oracle distribution will independently roll a die for each query to produce $O$ . Specifically, it is formed by a mapping $~ O : M \to Δ N$ . Let the function $d$ map $~ O$ to an oracle distribution through independent sampling.

Define $f (~ O) := \times_{M \in M} Δ (E v a l (M) (d (~ O))$ , where $\times$ indicates a Cartesian product, and $Δ S$ is the set of probability distributions over the set $S$ (which is finite in this case). Note that $f (~ 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 $~ O$ such that $~ O \in f (~ O)$ .

Consider the oracle distribution $d (~ O)$ . For any $M \in M$ , and $O \in S u p p o r t (d (~ O))$ , we have

$O (M) \in E v a l (M) (d (~ O)) = E v a l (M) (C o n d i t i o n (d (~ O), M, O (M)))$

where the second equality follows from (a) the fact that $E v a l (M)$ does not depend on the distribution over $O (M)$ and (b) the fact that all $O (M)$ values are independent under $d (~ O)$ . So $d (O^{*})$ is reflective.

$□$

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

Proof:

Let $D_{0}, D_{1}$ be reflective oracle distributions. Let $θ \in (0, 1)$ . Define $D_{θ} := θ D_{0} + (1 - θ) D_{1}$ . This proof will show that $D_{θ}$ is reflective.

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

$D_{0} (O (M) = a) > 0, D_{1} (O (M) = a) = 0$ . Then $a \in E v a l (M) (C o n d i t i o n (D_{0}, M, a))$ . But since $D_{1} (O (M) = a) = 0$ , we have $C o n d i t i o n (D_{θ}, M, a) = C o n d i t i o n (D_{0}, M, a)$ . So $a \in E v a l (M) (C o n d i t i o n (D_{θ}, M, a))$ as desired.
$D_{0} (O (M) = a) = 0, D_{1} (O (M) = a) > 0$ . This is analogous to case 1.
$D_{0} (O (M) = a) > 0, D_{1} (O (M) = a) > 0$ . We have $a \in E v a l (M) (C o n d i t i o n (D_{0}, M, a))$ and $a \in E v a l (M) (C o n d i t i o n (D_{1}, M, a))$ . Note that $C o n d i t i o n (D_{θ}, M, a)$ is a convex combination of $C o n d i t i o n (D_{0}, M, a)$ and $C o n d i t i o n (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 E v a l (M) (D)}$ is convex (from $E v a l (M)$ being a query); therefore $a \in E v a l (M) (C o n d i t i o n (D_{θ}, 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 A_{i}$ , and receives utility $U_{i} (A_{1}, . . ., A_{n})$ . Define queries as follows:

$q_{i} (D) := arg max a \in A_{i} 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.

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