Proof Section to Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

[Brittany Gelb]

This proof section accompanies Formalizing Newcombian problems with fuzzy infra-Bayesianism. We prove the following result.

Theorem [Alexander Appel (@Diffractor), Vanessa Kosoy (@Vanessa Kosoy)]:

Let $\nu :{\Pi }_H\times O^{<H}\to \Delta O$ be a Newcombian problem of horizon $H\in N$ that satisfies pseudocausality. Let $M_{\nu }=(S,{\Theta }_0,A,O,T,B)$ denote the associated supra-POMDP with infinite time horizon and time discount $\gamma \in [0,1).$ Then

$$\underset{\gamma \to 1}{lim}|\underset{\pi \in \Pi }{min}{E}_{M_{\nu }^{\pi }}\left[L^{\gamma }\right]-\underset{\pi \in \Pi }{min}{E}_{{\nu }^{\pi }}\left[L^{\gamma }\right]|=0.$$

Furthermore, if $\{{\pi }_{\gamma }{\}}_{\gamma \in [0,1)}$ is a family of policies such that ${lim}_{\gamma \to 1}{E}_{M_{\nu }^{{\pi }_{\gamma }}}\left[L^{\gamma }\right]-{min}_{\pi \in \Pi }{E}_{M_{\nu }^{\pi }}\left[L^{\gamma }\right]=0,$ then

$$\underset{\gamma \to 1}{lim}{E}_{{\nu }^{{\pi }_{\gamma }}}\left[L^{\gamma }\right]-\underset{\pi \in \Pi }{min}{E}_{{\nu }^{\pi }}\left[L^{\gamma }\right]=0.$$

Proof: Let $\lambda$ denote the empty history. Given a supracontribution $\Theta$, let $max\left(\Theta \right)$ denote the set of maximal extreme points of $\Theta .$ First we remark that for any supra-POMDP, without loss of generality, a set of copolicies $\Xi$ can always be replaced by

$$\{\tau \in \Xi |\tau (\lambda )\in max({\Theta }_0),\forall h\ne \lambda \in (S\times A{)}^{\ast },\tau \left(h\right)\in max\left(T\right(s,a\left)\right)\}.$$

Given an episode policy $\pi \in {\Pi }_H,$ let ${\tau }_{\pi }$ denote the episode copolicy that initializes the state to $(\pi ,\lambda ),$ i.e.${\tau }_{\pi }\left(\lambda \right)={\delta }_{\pi \times \lambda }.$ Let ${\tau }_{\pi }^{\pi }\in \Delta (A\times O{)}^H$ denote the distribution over outcomes determined by the interaction of $\pi$ and ${\tau }_{\pi }.$ Note that the expected loss with respect to ${\tau }_{\pi }^{\pi }$ is equal to the expected loss for the Newcombian problem, i.e.

$$E_{{\tau }_{\pi }^{\pi }}\left[L\right]=E_{{\nu }^{\pi }}\left[L\right].$$

Recall that throughout this sequence, we assume that $O$ is finite. By the remark at the beginning of the proof, the expected loss in one episode for the corresponding supra-POMDP can be written as a maximum expected loss over a finite set of $M_{\nu }$-copolicies $\tau .$ Namely,

$$E_{M_{\nu }^{\pi }}\left[L\right]=\underset{\tau }{max}{E}_{{\tau }^{\pi }}\left[L\right].$$

Then

$$\underset{\tau }{max}{E}_{{\tau }^{\pi }}\left[L\right]\ge E_{{\tau }_{\pi }^{\pi }}\left[L\right]=E_{{\nu }^{\pi }}\left[L\right],$$

and thus for any episode policy $\pi \in {\Pi }_H,$

$$E_{M_{\nu }^{\pi }}\left[L\right]\ge E_{{\nu }^{\pi }}\left[L\right].$$

We now extend this analysis to the optimal loss over $n$ episodes for $n\in N.$^[1] Let $L^{\ast }:={min}_{\pi \in {\Pi }_H}{E}_{{\nu }^{\pi }}\left[L\right]$ denote the episode optimal loss for $\nu .$ Let ${\pi }_n\in \Pi$ be an arbitrary policy for $n$ episodes of $M_{\nu }.$ Then as before,

$$E_{M_{\nu }^{{\pi }_n}}\left[L_n^{\gamma }\right]=\underset{{\tau }_n}{max}{E}_{{{\tau }_n}^{{\pi }_n}}\left[L_n^{\gamma }\right]$$

where the maximum is over a finite set of $n$-episode copolicies ${\tau }_n.$ By the single episode case,

$$\underset{{\tau }_n}{max}{E}_{{{\tau }_n}^{{\pi }_n}}\left[L_n^{\gamma }\right]\ge (1-\gamma )\sum _{k=0}^{n-1}{\gamma }^k{L}^{\ast }=L^{\ast },$$

and thus ${min}_{{\pi }_n\in \Pi }{E}_{M_{\nu }^{{\pi }_n}}\left[L_n^{\gamma }\right]\ge L^{\ast }.$

It remains to show that the opposite inequality holds in the many-episode and $\gamma \to 1$ limit.

Recall that given $\pi \in {\Pi }_H,$ we define

$$C_{\pi }:=\{h\in (A\times O{)}^H|\forall \text{prefixes}{h}^{\prime }a\in (A\times O{)}^{\ast }\times A\text{of}h,a=\pi (h^{\prime }\left)\right\}.$$

Recall that since $\nu$ satisfies pseudocausality, there exists a $\nu$-optimal policy ${\pi }^{\ast }\in {\Pi }_H$ such that for all $\pi \in {\Pi }_H,$ if $\text{supp}\left({\nu }^{\pi }\right)\subseteq C_{{\pi }^{\ast }},$ then $\pi$ is also optimal for $\nu .$ Consequently, for any episode copolicy $\tau ,$ either $E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]\le L^{\ast }$ or $E_{{\tau }^{{\pi }^{\ast }}}\left[1\right]<1.$ To see this, suppose there exists an episode copolicy $\tau$ such that $E_{{\tau }^{{\pi }^{\ast }}}\left[1\right]=1.$ Then there exists a policy ${\pi }^{†}$ such that $\text{supp}\left({\nu }^{{\pi }^{†}}\right)\subseteq C_{{\pi }^{\ast }}$ and $E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]=E_{{\nu }^{{\pi }^{†}}}\left[L\right]$. By pseudocausality, $E_{{\nu }^{{\pi }^{†}}}\left[L\right]=L^{\ast }.$ Thus $E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]\le L^{\ast }.$

Define

$$\alpha :=\underset{\tau :E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]>L^{\ast }}{max}{E}_{{\tau }^{{\pi }^{\ast }}}\left[1\right].$$

By the remark at the beginning of the proof, the relevant set of copolicies in the definition of $\alpha$ is finite, and thus $\alpha$ is well-defined. If $E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]>L^{\ast }$ then $E_{{\tau }^{{\pi }^{\ast }}}\left[1\right]<1.$ Thus $\alpha \in [0,1).$

Consider the iterated Newcombian problem over $n$ episodes. Let ${\pi }_n^{\ast }$ denote the multi-episode policy such that ${\pi }_n^{\ast }$ restricted to every episode is ${\pi }^{\ast }.$ Let ${\tau }_n$ denote an arbitrary copolicy that interacts with ${\pi }_n^{\ast }.$ Furthermore, let $m\le n$ denote the number of episodes for which the episode-restriction $\tau$ of ${\tau }_n$ interacting with ${\pi }_n^{\ast }$ satisfies $E_{{\tau }^{{\pi }^{\ast }}}\left[L\right]>L^{\ast }.$^[2]

We have

$$E_{{\tau }_n^{{\pi }_n^{\ast }}}\left[L_n^{\gamma }\right]\le E_{{\tau }_n^{{\pi }_n^{\ast }}}\left[1\right]\le {\alpha }^m.$$

Furthermore,

$$\begin{array}{cc}{E}_{{\tau }_n^{{\pi }_n^{\ast }}}\left[L_n^{\gamma }\right]& \le (1-\gamma )(\sum _{t=0}^{m-1}{\gamma }^t\cdot 1+\sum _{t=m}^{n-1}{\gamma }^t\cdot L^{\ast })\\ & =(1-\gamma )(\frac{1-{\gamma }^m}{1-\gamma }+L^{\ast }{\gamma }^m\cdot \frac{1-{\gamma }^{n-m}}{1-\gamma })\\ & =1-{\gamma }^m+L^{\ast }({\gamma }^m-{\gamma }^n).\end{array}$$

We leave it to the reader to verify that

$$\underset{\gamma \to 1}{lim}\underset{n\to \infty }{lim}{E}_{{\tau }_n^{{\pi }_n^{\ast }}}\left[L_n^{\gamma }\right]\le \underset{\gamma \to 1}{lim}\underset{n\to \infty }{lim}\underset{m\le n}{max}min({\alpha }^m,1-{\gamma }^m+L^{\ast }({\gamma }^m-{\gamma }^n\left)\right)=L^{\ast }.\square$$

1. ^

   Recall that if $n\in N$ and $h\in (A\times O{)}^{nH}$ is given by $h=a_0{o}_0\dots a_{nH-1}{o}_{nH-1},$ then the loss over $n$ episodes with geometric time discount $\gamma \in [0,1)$ is defined by

   $$L_n^{\gamma }\left(h\right)=(1-\gamma )\sum _{k=0}^{n-1}{\gamma }^{k}L(a_{kH}{o}_{kH}\cdots a_{kH+H-1}{o}_{kH+H-1}).$$
2. ^

   A copolicy can depend on the past, meaning it can depend on the policy. Thus $m$ can depend on ${\pi }_n^{\ast }$.