Frank_R comments on The Learning-Theoretic Agenda: Status 2023

[Frank_R]

I have discovered another minor point. You have written at the beginning of Direction 17 that any computable utility function $U:(O\times A{)}^{\omega }\to [0,1]$ is automatically continuous. This seems to be not always true.

I fix some definitions to make sure that we talk about the same stuff. For reasons of simplicity, I assume that $O$and $A$ are finite. Let $(O\times A{)}^{\omega }$ be the space of all infinite sequences with values in $O\times A$. The $i$-th projection $p_i:(O\times A{)}^{\omega }\to O\times A$ is given by

$$p_i(o_1{a}_1{o}_2{a}_2\dots )=o_i{a}_i$$

The product topology is defined as the coarsest topology such that all projection maps are continuous. A base of this topology consists of all sets $S$ such that there are finitely many indices $i_1,\dots ,i_n\in N$ and subsets $S_1,\dots ,S_n\subseteq O\times A$ with

$$S=\left\{\right(o_n{a}_n{)}_{n\in N}|o_{i_j}{a}_{i_j}\subseteq S_j\forall j=1,\dots ,n\}$$

In particular, any open set contains such an $S$ as a subset, which means that its image under $p_i$ is $O\times A$ for all but finitely many $i$. For my counterexample, let $O=A=\{0,1,2\}$. Let $s=(s_n{)}_{n\in N}$ be a sequence with values in $\{0,1,2\}$. If $s_n$ is never 2, we define

$$U\left(s\right)=\sum _{k=1}^{\infty }{s}_k{2}^{-k-1}$$

Otherwise, we define $U\left(s\right)=\frac{3}{4}$. $U$ is computable in the sense that for any $ϵ>0$ we find a finite program $P$whose input is a sequence such that $|P\left(s\right)-U\left(s\right)|<ϵ$ and $P$ uses only finitely many values of $s$. The preimage of the open set $(0,\frac{1}{2})$ is

$$\left\{\right(s_n{)}_{n\in N}\in \{0,1,2{\}}^{\omega }|s_n\in \{0,1\}\forall n\in N,s_n\ne 0000\dots ,s_n\ne 1111\dots \}$$

which is not open since its $i$th projection is always $\{0,1{\}}^2\ne O\times A$. Therefore, $U$ is not contiuous. However, we have the following lemma:

Let $r:(O\times A{)}^{\ast }\to [0,1]$ be a reward function and let $U:(O\times A{)}^{\omega }\to [0,1]$ be given by

$$U(o_0{a}_0{o}_1{a}_1\dots )=(1-\gamma )\sum _{t=0}^{\infty }{\gamma }^{t}r(o_0{a}_0{o}_1{a}_1\dots o_t{a}_t)$$

where $0<\gamma <1$ is the time discount rate. Then $U$ is continuous with respect to the product topology.

Proof: Since the open intervals are a base of the standard topology of $R$, it suffices to prove that the preimage of any interval $(a,b)$, $(a,1]$, $[0,b)$ or $[0,1]$ with $0<a<b<1$ is open in $(O\times A{)}^{\omega }$. For reasons of simplicity, we consider only $(a,b)$. The other cases are analogous. Let $o_0{a}_0{o}_1{a}_1\dots \in (O\times A{)}^{\omega }$ such that $u:=U(o_0{a}_0{o}_1{a}_1\dots )\in (a,b)$. Moreover, let $ϵ>0$ such that $(u-ϵ,u+ϵ)\subseteq (a,b)$. Finally, we choose an $n\in N$ such that ${\gamma }^{n+1}<ϵ$. We define the set

$$M=\{o_0^{\prime }{a}_0^{\prime }{o}_1^{\prime }{a}_1^{\prime }\dots \in (O\times A{)}^{\omega }|o_0^{\prime }=o_0,a_0^{\prime }=a_0,\dots ,a_n^{\prime }=a_n\}$$

$M$ is an open subset of $(O\times A{)}^{\omega }$. Since the reward is non-negative, we have

$$0\le U(o_0{a}_0{o}_1{a}_1\dots )-r(o_0{a}_0{o}_1{a}_1\dots o_n{a}_n)\le {\gamma }^{n+1}<ϵ$$

and for any $o_0^{\prime }{a}_0^{\prime }{o}_1^{\prime }{a}_1^{\prime }\dots \in M$, we have

$$0\le U(o_0^{\prime }{a}_0^{\prime }{o}_1^{\prime }{a}_1^{\prime }\dots )-r(o_0{a}_0{o}_1{a}_1\dots o_n{a}_n)\le {\gamma }^{n+1}<ϵ,$$

too. Therefore,

$$\left|U\right(o_0^{\prime }{a}_0^{\prime }{o}_1^{\prime }{a}_1^{\prime }\dots )-U(o_0{a}_0{o}_1{a}_1\dots \left)\right|<ϵ$$

and furthermore $M\subseteq U^{-1}(u-ϵ,u+ϵ)\subseteq U^{-1}(a,b)$. All in all, any $o_0{a}_0{o}_1{a}_1\dots \in U^{-1}(a,b)$ has an open neighborhood that is a subset of $U^{-1}(a,b)$. Therefore, $U^{-1}(a,b)$ is open.

That a utility function $U:(O\times A{)}^{\omega }\to [0,1]$ is continuous roughly means that for any $ϵ>0$ there are only finitely many events that have an influence of more than $ϵ$ on the utility. This could be a problem for studying longtermist agents with zero time discount rate. However, studying such agents is hard anyway since there is no guarantee that the sum of rewards converges and we have to deal with infinity ethics. As far as I know, it is standard in learning theory to avoid such situations by assuming a non-zero time discount rate or a finite time horizon. Therefore, it should not be a big deal to add the condition that $U$ is continuous to all theorems.

[Vanessa Kosoy]

Your alleged counterexample is wrong, because the $U$ you constructed is not computable. First, “computable” means that there is a program $P$ which receives $s$ and $ϵ\in Q$ as inputs s.t. for all $s$ and $ϵ$, it halts and

$$|P(s,ϵ)-U\left(s\right)|<ϵ$$

Second, even your weaker definition fails here. Let $ϵ=\frac{1}{2}$. Then, there is no program that computes $U$ within accuracy $ϵ$, because for every $n$, $U\left(0^n{20}^{\omega }\right)=\frac{3}{4}$ while $U\left(0^{\omega }\right)=0$. Therefore, determining the value of $U\left(s\right)$ within $ϵ$ requires looking at infinitely many elements of the sequence. Any program would that outputs $0$ on $0^{\omega }$ has to halt after reading some finite $m$ symbols, in which case it would output $0$ on $0^m{20}^{\omega }$ as well.

[Frank_R]

You are right and now it is clear, why your original statement is correct, too. Let $U$ be an arbitrary computable utility function. As above, let $u=U(o_0{a}_0{o}_1{a}_1\dots )$ and $(u-ϵ,u+ϵ)\subseteq (a,b)$ with $ϵ>0$ and $ϵ\in Q$. Choose $P$ as in your definition of “computable”. Since $P(s,ϵ)$ terminates, its output depends only on finitely many $o_{i_1},\dots ,o_{i_k},a_{j_1},\dots ,a_{j_l}$. Now

$$\{s^{\prime }=o_0^{\prime }{a}_0^{\prime }{o}_1^{\prime }{a}_1^{\prime }\dots |o_{i_1}^{\prime }=o_{i_1},\dots ,a_{j_l}^{\prime }=a_{j_l}\}$$

is open and a subset of $U^{-1}(u-ϵ,u+ϵ)$, since $|P(s^{\prime },ϵ)-u|<ϵ$.