Intelligent Agent Foundations Forumsign up / log in
Formal Open Problem in Decision Theory
post by Scott Garrabrant 59 days ago | Marcello Herreshoff, Sam Eisenstat, Vadim Kosoy, Jessica Taylor, Patrick LaVictoire and Stuart Armstrong like this | 13 comments

In this post, I present a new formal open problem. A positive answer would be valuable for decision theory research. A negative answer would be helpful, mostly for figuring out what is the closest we can get to a positive answer. I also give some motivation for the problem, and some partial progress.

Open Problem: Does there exist a topological space \(X\) (in some convenient category of topological spaces) such that there exists a continuous surjection from \(X\) to the space \([0,1]^X\) (of continuous functions from \(X\) to \([0,1]\))?


Motivation:

Topological Naturalized Agents: Consider an agent who makes some observations and then takes an action. For simplicity, we assume there are only two possible actions, \(A\) and \(B\). We also assume that the agent can randomize, so we can think of this agent as outputting a real number in \([0,1]\), representing its probability of taking action \(A\).

Thus, we can think of an agent as having a policy which is a function from the space \(Y\) of possible observations to \([0,1]\). We will require that our agent behaves continuously as a function of its observations, so we will think of the space of all possible policies as the space of continuous functions from \(Y\) to \([0,1]\), denoted \([0,1]^Y\).

We will let \(X\) denote the space of all possible agents, and we will have a function \(f:X\rightarrow [0,1]^Y\) which takes in an agent, and outputs that agent’s policy.

Now, consider what happens when there are other agents in the environment. For simplicity, we will assume that our agent observes one other agent, and makes no other observations. Thus, we want to consider the case where \(Y=X\), so \(f:X\rightarrow [0,1]^X\).

We want \(f\) to be continuous, because we want a small change in an agent to correspond to a small change in the agent’s policy. This is particularly important since other agents will be implementing continuous functions on agents, and we would like any continuous function on policies to be able to be considered valid continuous function on agents.

We also want \(f\) to be surjective. This means that our space of agents is sufficiently rich that for any possible continuous policy, there is an agent in our space that implements that policy.

In order to meet all these criteria simultaneously, we need a space \(X\) of agents, and a continuous surjection \(f:X\rightarrow[0,1]^X\).

Unifying Fixed Point Theorems: While we are primarily interested in the above motivation, there is another secondary motivation, which may be more compelling for those less interested in agent foundations.

There are (at least) two main clusters of fixed point theorems that have come up many times in decision theory, and mathematics in general.

First, there is the Lawvere cluster of theorems. This includes the Lawvere fixed point theorem, the diagonal lemma, and the existence of Quines and fixed point combinators. These are used to prove Gödel’s incompleteness Theorem, Cantor’s Theorem, Löb’s Theorem, and achieve robust cooperation in the Prisoner’s Dilemma in modal framework and bounded variants. All of these can be seen as corollaries of Lawvere’s fixed point theorem, which states that in a cartesian closed category, if there is a point-surjective map \(f:X\rightarrow Y^X\), then every morphism \(g:Y\rightarrow Y\) has a fixed point.

Second, there is the Brouwer cluster of theorems. This includes Brouwer’s fixed point theorem, The Kakutani fixed point theorem, Poincaré–Miranda, and the intermediate value theorem. These are used to prove the existence of Nash Equilibria, Logical Inductors, and Reflective Oracles.

If we had a topological space and a continuous surjection \(X\rightarrow[0,1]^X\), this would allow us to prove the one-dimensional Brouwer fixed point theorem directly using the Lawvere fixed point theorem, and thus unify these two important clusters.

Thanks to Qiaochu Yuan for pointing out the connection to Lawvere’s fixed point theorem (and actually asking this question three years ago).


Partial Progress:

Most Diagonalization Intuitions Do Not Apply: A common initial reaction to this question is to conjecture that such an \(X\) does not exist, due to cardinality or diagonalization intuitions. However, note that all of the diagonalization theorems pass through (some modification of) the same lemma: Lawvere’s fixed point theorem. However, this lemma does not apply here!

For example, in the category of sets, the reason that there is no surjection from any set \(X\) to the power set, \(\{T,F\}^X\), is because if there were such a surjection, Lawvere’s fixed point theorem would imply that every function from \(\{T,F\}\) to itself has a fixed point (which is clearly not the case, since there is a function that swaps \(T\) and \(F\)).

However, we already know by Brouwer’s fixed point theorem that every continuous function from the interval \([0,1]\) to itself has a fixed point, so the standard diagonalization intuitions do not work here.

Impossible if You Replace \([0,1]\) with e.g. \(S^1\): This also provides a quick sanity check on attempts to construct an \(X\). Any construction that would not be meaningfully different if the interval \([0,1]\) is replaced with the circle \(S^1\) is doomed from the start. This is because a continuous surjection \(X\rightarrow (S^1)^X\) would violate Lawvere’s fixed point theorem, since there is a continuous map from \(S^1\) to itself without fixed points.

Impossible if you Require a Homeomorphism: When I first asked this question I asked for a homeomorphism between \(X\) and \([0,1]^X\). Sam Eisenstat has given a very clever argument why this is impossible. You can read it here. In short, using a homeomorphism, you would be able to use Lawvere to construct a continuous map that send a function from \([0,1]\) to itself to a fixed point of that function. However, no such continuous map exists.


Notes:

If you prefer not to think about the topology of \([0,1]^X\), you can instead find a space \(X\), and a continuous map \(h:X\times X\rightarrow[0,1]\), such that for every continuous function \(f:X\rightarrow[0,1]\), there exists an \(x_f\in X\), such that for all \(x\in X\), \(h(x_f,x)=f(x)\).

Many of the details in the motivation could be different. I would like to see progress on similar questions. For example, you could add some computability condition to the space of functions. However, I am also very curious which way this specific question will go.

This post came out of many conversations, with many people, including: Sam, Qiaochu, Tsvi, Jessica, Patrick, Nate, Ryan, Marcello, Alex Mennen, Jack Gallagher, and James Cook.




From discussions I had with Sam, Scott, and Jack:

To solve the problem, it would suffice to find a reflexive domain \(X\) with a retract onto \([0, 1]\).

This is because if you have a reflexive domain \(X\), that is, an \(X\) with a continuous surjective map \(f :: X \rightarrow X^X\), and \(A\) is a retract of \(X\), then there’s also a continuous surjective map \(g :: X \rightarrow A^X\).

Proof: If \(A\) is a retract of \(X\) then we have a retraction \(r::X\rightarrow A\) and a section \(s::A \rightarrow X\) with \(r\circ s = 1_A\). Construct \(g(x) := r \circ f(x)\). To show that \(g\) is a surjection consider an arbitrary \(q \in A^X\). Thus, \(s \circ q :: X \rightarrow X\). Since \(f\) is a surjection there must be some \(x\) with \(f(x) = s \circ q\). It follows that \(g(x) = r \circ f(x) = r \circ s \circ q = q\). Since \(q\) was arbitrary, \(g\) is also a surjection.

reply

by Jessica Taylor 58 days ago | Vadim Kosoy likes this | link

If I were studying this, I would be looking at domain theory, in which (among other things) there has been found a topological space \(X\) homeomorphic with \(X^X\). The page I linked links to some notes at the bottom. (h/t Qiaochu for pointing out domain theory)

reply

by Stuart Armstrong 55 days ago | Scott Garrabrant likes this | link

Can you argue that \(X\) must have a semi-metric compatible with the topology by using \(d(x,y)=sup_{z\in X}|h(x,z)-h(y,z)|\)?

I’m wondering if you can generalise this to some sort of argument that goes like this. Using X, project down via \(\pi\) from \(X^0=X\) to \(X^1=X^0/d\). Let \(\phi\) be our initial surjection; it’s now a bijection between \(X^1\) and maps from \(X^0\) to \([0,1]\).

If the projection is continuous, then every map from \(X^1\) to \([0,1]\) lifts to a map from \(X^0\) to \([0,1]\). Restricting to the subset of maps that are lifts like this, and applying \(\phi^{-1}\), gives a subset \(X^2 \subset X^1\). We now have a new equivalence relationship, maps from \(X^1\) that are equal to each other on \(X^2\). Project down from \(X^2\) by this relationship, to generate \(X^3\). Continue this transfinitely often (?) to generate a space \(X'\) where \(\phi\) is a homeomorphism, and find a contradiction?

This feels dubious, but maybe worth mentioning…

reply

by Alex Mennen 55 days ago | Scott Garrabrant and Stuart Armstrong like this | link

I haven’t checked that argument carefully, but that sounds like it should give you \(X'\) with a continuous bijection \(\phi:X'\rightarrow[0,1]^{X'}\), which might not necessarily be a homeomorphism.

reply

by Stuart Armstrong 55 days ago | link

Yes, you’re right.

reply

by Stuart Armstrong 54 days ago | Scott Garrabrant likes this | link

A small note: it’s not hard to construct spaces that are a bit too big, or a bit too small (raising the possibility that a true \(X\) lies between them).

For instance, if \(I\) is the unit interval, then we can map \(I\) onto the countable-dimensions hypercube \(I^\omega\) ( https://en.wikipedia.org/wiki/Space-filling_curve#The_Hahn.E2.80.93Mazurkiewicz_theorem ). Then if we pick an ordering of the dimensions of the hypercube and an ordering of \(\mathbb{Q}\cap I\), we can see any element of \(I^\omega\) - hence any element of \(I\) - as a function from \(\mathbb{Q}\cap I\) to \(I\).

Let \(C(I)\) be the space of continuous functions \(I \to I\). Then any element of \(C(I)\) defines a unique function \(\mathbb{Q}\cap I \to I\) (the converse is not true - most functions \(\mathbb{Q}\cap I \to I\) do not correspond to continuous functions \(I \to I\)). Pulling \(C(I)\) back to \(I\) via \(I^\omega\) we define the set \(Y \subset I\).

Thus \(Y\) maps surjectively onto \(C(I)\). However, though \(C(I)\) maps into \(C(Y)\) by restriction (any function from \(I\) is a function from \(Y\)), this map is not onto (for example, there are more continuous functions from \(I - \{1/2\}\) than there are from \(I\), because of the potential discontinuity at \(1/2\)).

Now, there are elements of \(I-Y\) that map (via \(I^\omega\)) to functions in \(C(Y)\) that are not in \(C(I)\). So there’s a hope that there may exist an \(X\) with \(Y \subset X \subset I\), \(C(I) \subset C(X) \subset C(Y)\), and \(X\) mapping onto \(C(X)\). Basically, as \(X\) `gets bigger’, its image in \(C(Y)\) grows, while \(C(X)\) itself shrinks, and hopefully they’ll meet.

reply

by Marcello Herreshoff 54 days ago | Scott Garrabrant likes this | link

“Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere’s Theorem” by Jorge Soto-Andrade and Francisco J. Varela seems like a potentially relevant result. In particular, they prove a converse Lawvere result in the category of posets (though they mention doing this for \([0,1]\) in an unsolved problem.) I’m currently reading through this and related papers with an eye to adapting their construction to \([0, 1]\) (I think you can’t just use it straight-forwardly because even though you can build a reflexive domain with a retract to an arbitrary poset, the paper uses a different notion of continuity for posets.)

reply

by Scott Garrabrant 48 days ago | link

I give a stronger version of this problem here.

reply

by Alex Mennen 7 days ago | link

This comment is to explain partial results obtained by David Simmons in this thread, since the results and their proofs are difficult to follow as a result of being distributed across multiple comments, with many errors and corrections. The proofs given here are due to David Simmons.

Statements

Theorem 1: There is no metric space \(X\) and uniformly continuous function \(f:X\times X\rightarrow[0,1]\) such that every uniformly continuous function \(X\rightarrow[0,1]\) is a fiber of \(f\).

Theorem 2: There is no metric space \(X\) and function \(f:X\times X\rightarrow[0,1]\) that is uniformly continuous on bounded sets, such that every function \(X\rightarrow[0,1]\) which is uniformly continuous on bounded sets is a fiber of \(f\).

Theorem 3: There is no locally compact Polish space \(X\) and continuous function \(f:X\times X\rightarrow[0,1]\) such that every continuous function \(X\rightarrow[0,1]\) is a fiber of \(f\).

Commentary

Theorem 1 says that there is no solution to the version of Scott’s problem with continuity in topological spaces replaced with uniform continuity in metric spaces. A plausible reason that this version of the problem might be important is that if an agent has to be able to compute what its policy says to do to any desired precision using an amount of computational resources that does not depend on the input, then its policy must be uniformly continuous. The gist of the proof is that for any uniformly continuous \(f:X\times X\rightarrow[0,1]\), it is possible to construct a uniformly continuous function \(g:X\rightarrow[0,1]\) that requires greater precision in its input than \(f\) does to determine the output to any desired precision. I suspect it might be possible to adapt the proof to work in uniform spaces rather than just metric spaces, but I have not studied uniform spaces.

Theorem 2 is similar to theorem 1, but with uniform continuity replaced with uniform continuity on bounded subsets. I was not convinced that this is an important notion in its own right, but theorem 2 is useful as a lemma for theorem 3. See the thread under David Simmons’s comment for more discussion about what sort of continuity assumption is appropriate. The gist of the proof is to apply the proof of theorem 1 on a bounded set. The function \(g\) constructed will be uniformly continuous everywhere, so the proof actually shows a stronger result that unifies both theorems 1 and 2: there is no \(f:X\times X\rightarrow[0,1]\) that is uniformly continuous on bounded sets and admits every uniformly continuous function \(X\rightarrow[0,1]\) as a fiber.

Theorem 3 almost says that Scott’s problem cannot be solved with Polish spaces. It doesn’t quite say that, because there are Polish spaces that are not locally compact. However, non-locally-compact Polish spaces are not exponentiable, so in the version of the problem in which we want a surjection \(X\rightarrow[0,1]^X\), it isn’t even clear whether there exists an exponential object \([0,1]^X\), which may mean that non-exponentiable spaces are not promising, although I’m not sure. A reason to restrict attention to Polish spaces is that effective Polish spaces provide a topological setting in which there is a good notion of computability, so the nonexistence of a solution in Polish spaces would make it impossible to provide a computable solution in that sense. That said, there may be other notions of computability in topological spaces (domain theory?), which I am unfamiliar with. The gist of the proof is to find a metric in which bounded sets are compact, and apply theorem 2.

Proofs

Proof of theorem 1: Let \(X\) be a metric space, and \(f:X\times X\rightarrow[0,1]\) be uniformly continuous. If \(X\) is uniformly discrete, then all functions from \(X\) are uniformly continuous, so there is a uniformly continuous function \(X\rightarrow[0,1]\) that is not a fiber of \(f\) by Cantor’s theorem.

So assume that \(X\) is not uniformly discrete. Let \((x_n,y_n)_{n\in\mathbb{N}}\) be such that \(\forall k\) \(d(x_{k+1},y_{k+1})\leq\frac{1}{6}d(x_k,y_k)\). Note that for all \(k\) and \(\ell>k\), either (A) \(d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\) and \(d(x_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)\) or (B) \(d(y_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\) and \(d(y_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)\). By extracting a subsequence we can assume that which of (A) or (B) holds depends only on \(k\) and not on \(\ell\). By swapping \(x_k\) and \(y_k\) if necessary we can assume that case (A) always holds.

For each \(z\) there is at most one \(k\) such that \(d(z,x_k)<\frac{1}{6}d(x_k,y_k)\), because if \(d(z,x_k)<\frac{1}{6}d(x_k,y_k)\) and \(d(z,x_\ell)<\frac{1}{6}d(x_\ell,y_\ell)\) with \(\ell>k\), then \(d(x_k,x_\ell)<\frac{1}{3}d(x_k,y_k)\), a contradiction.

It follows that by extracting a further subsequence we can assume that \(d(y_k,x_\ell)\geq\frac{1}{6}d(x_\ell,y_\ell)\) for all \(\ell>k\).

Since \(f\) is uniformly continuous, there is a function \(\delta:(0,\infty)\rightarrow(0,\infty)\) such that \(\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon\). By extracting a further subsequence, we can assume that \(d(x_k,y_k)<\delta(2^{-k})\) for all \(k\). Let \(j:[0,\infty)\rightarrow[0,\infty)\) be an increasing uniformly continuous function such that \(j(0)=0\) and \(j(\frac{1}{6}d(x_k,y_k))>2^{-k}\) for all \(k\). Finally, let \(g(z):=\inf_kd(z,y_k)\). Then for all \(k\) we have \(g(y_k)=0\). On the other hand, for all \(\ell>k\) we have \(d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\), for \(\ell=k\) we have \(d(x_k,y_\ell)=d(x_k,y_k)\), and for \(\ell<k\) we have \(d(x_k,y_\ell)\geq\frac{1}{6}d(x_k,y_k)\). Thus \(g(x_k)=\inf_\ell j(d(x_k,y_\ell))\geq j(\frac{1}{6}d(x_k,y_k))>2^{-k}\). Clearly, \(g\) cannot be a fiber of \(f\). Moreover, since the functions \(j\) and \(z\mapsto\inf_kd(z,y_k)\) are both uniformly continuous, so is \(g\). \(\square\)

Proof of theorem 2: Let \(X\) be a metric space, and \(f:X\times X\rightarrow[0,1]\) be uniformly continuous on bounded sets. If all bounded subsets of \(X\) are uniformly discrete, then all functions from \(X\) are uniformly continuous on bounded sets, so there is a function \(X\rightarrow[0,1]\) that is uniformly continuous on bounded sets but not a fiber of \(f\) by Cantor’s theorem. Otherwise, let \(B\subseteq X\) be a bounded set that is not uniformly discrete, take a sequence \((x_n,y_n)_{n\in\mathbb{N}}\) in \(B\) as in the proof of theorem 1, and a function \(\delta:(0,\infty)\rightarrow(0,\infty)\) such that \(\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon\) for \((u,v),(w,z)\in B\times B\), and define \(j\) and \(g\) as in the proof of theorem 1. \(g\) is uniformly continuous, but not a fiber of \(f\). \(\square\)

Proof of theorem 3: Let \(d\) be a metric for \(X\). Let \(f(x):=\sup\{r|B(x,r)\text{ is compact}\}\), where \(B(x,r)\) is the closed ball around \(x\) of radius \(r\). Let \(F(x,y):=f(x)/[f(x)-d(x,y)]\) if \(f(x)>d(x,y)\), and \(F(x,y):=\infty\) otherwise. Next, let \(g(y):=\min_n[n+F(x_n,y)]\), where \((x_n)_{n\in\mathbb{N}}\) enumerates a countable dense set. Then \(g\) is continuous and everywhere finite. \(g^{-1}([0,N])\subseteq\bigcup_{n\leq N}B(x_n,(1-\frac{1}{N})f(x_n))\), and is thus compact. It follows that with the metric \(d'(x,y):=d(x,y)+|g(y)-g(x)|\), which induces the same topology, bounded sets are compact. Thus theorem 3 follows from theorem 2 applied to \((X,d')\). \(\square\)

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

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

RSS

Privacy & Terms