Intelligent Agent Foundations Forumsign up / log in
by Alex Mennen 203 days ago | link | parent

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\)



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

When considering an embedder
by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
by Abram Demski on Policy Selection Solves Most Problems | 0 likes

Looking "at the very
by Abram Demski on Policy Selection Solves Most Problems | 0 likes

Without reading closely, this
by Paul Christiano on Policy Selection Solves Most Problems | 1 like

>policy selection converges
by Stuart Armstrong on Policy Selection Solves Most Problems | 0 likes

Indeed there is some kind of
by Vadim Kosoy on Catastrophe Mitigation Using DRL | 0 likes

Very nice. I wonder whether
by Vadim Kosoy on Hyperreal Brouwer | 0 likes

Freezing the reward seems
by Vadim Kosoy on Resolving human inconsistency in a simple model | 0 likes

Unfortunately, it's not just
by Vadim Kosoy on Catastrophe Mitigation Using DRL | 0 likes

>We can solve the problem in
by Wei Dai on The Happy Dance Problem | 1 like

Maybe it's just my browser,
by Gordon Worley III on Catastrophe Mitigation Using DRL | 2 likes

At present, I think the main
by Abram Demski on Looking for Recommendations RE UDT vs. bounded com... | 0 likes

In the first round I'm
by Paul Christiano on Funding opportunity for AI alignment research | 0 likes

Fine with it being shared
by Paul Christiano on Funding opportunity for AI alignment research | 0 likes

I think the point I was
by Abram Demski on Predictable Exploration | 0 likes

RSS

Privacy & Terms