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

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. 

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, 

Then

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

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,

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

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

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

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

Furthermore,

We leave it to the reader to verify that

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 }$.