Intelligent Agent Foundations Forumsign up / log in
Formal Open Problem in Decision Theory
post by Scott Garrabrant 24 days ago | Marcello Herreshoff, Sam Eisenstat, Vadim Kosoy, Jessica Taylor, Patrick LaVictoire and Stuart Armstrong like this | 9 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 23 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 20 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 20 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 20 days ago | link

Yes, you’re right.

reply

by Stuart Armstrong 20 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 19 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 13 days ago | link

I give a stronger version of this problem here.

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

This isn't too related to
by Sam Eisenstat on Generalizing Foundations of Decision Theory II | 0 likes

I also commented there last
by Daniel Dewey on Where's the first benign agent? | 0 likes

(I replied last weekend, but
by Paul Christiano on Where's the first benign agent? | 0 likes

$g$ can be a fiber of $f$,
by Alex Mennen on Formal Open Problem in Decision Theory | 0 likes

>It seems like that can be
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

I disagree. I'm arguing that
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

But this could happen even if
by Paul Christiano on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

If I read Paul's post
by Daniel Dewey on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

I like this suggestion of a
by Patrick LaVictoire on Proposal for an Implementable Toy Model of Informe... | 0 likes

>It may generalize
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

I don't know what you really
by Paul Christiano on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

>“is trying its best to do
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

In practice, I'd run your
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

>that is able to give
by Stuart Armstrong on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

> good in practice, but has
by Paul Christiano on ALBA: can you be "aligned" at increased "capacity"... | 0 likes

RSS

Privacy & Terms