%&latex

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

This post continues the research programme of attacking the grain of truth problem by departure from the Bayesian paradigm. In the previous post, I suggested using Savage's minimax regret decision rule, but here I fall back to the simple minimax decision rule. This is because the mathematics is considerably simpler, and minimax should be sufficient to get IUD play in general games and Nash equilibrium in zero-sum two-player games. I hope to build on these results to get analogous results for minimax regret in the future.

We consider "semi-Bayesian" agents following the minimax expected utility decision rule, in oblivious environments with full monitoring (a setting that we will refer to as "forecasting"). This setting is considered in order to avoid the need to enforce exploration, as a preparation for analysis of general environments. We show that such agents satisfy a certain asymptotic optimality theorem. Intuitively, this theorem means that whenever the environment satisfies an incomplete model that is included in the prior, the agent will eventually learn this model i.e. extract at least as much utility as can be guaranteed for this model.

---

Appendix A contains the proofs of all results. Appendix B contains some theorems from the literature together with a corollary used in Appendix A.

##Notation

Given $X$ a topological space, $P\left(X\right)$ will denote the space of Borel probability measures on $X$. We regard it as a topological space using the weak${}^{\ast }$ topology. Given $x\in X$, ${\delta }_x\in P\left(X\right)$ is defined by ${\delta }_x\left(A\right):=\left[\right[x\in A\left]\right]$. Given $\mu ,\nu \in P\left(X\right)$, $d_{\text{tv}}(\mu ,\nu )$ stands for the total variation distance between $\mu$ and $\nu$. We denote $P_C\left(X\right)$ the set of non-empty convex compact subsets of $P\left(X\right)$.

Given $X$ a finite set, $X^{\ast }$ denotes the set of finite strings in alphabet $X$, i.e. $X^{\ast }:={⨆}_{n\in N}{X}^n$. $X^{\omega }$ denotes the set of infinite strings in alphabet $X$. Given $x\in X^{\ast }\bigsqcup X^{\omega }$, $\left|x\right|\in N\bigsqcup \left\{\infty \right\}$ is the length of string. Given $0\le n<\left|x\right|$, $x_n\in X$ is the $n$-th symbol in $x$. Given $0\le n\le \left|x\right|$, $x_{<n}$ is the prefix of $x$ of length $n$. Given $x,y\in X^{\ast }\bigsqcup X^{\omega }$, the notations $x⊏y$, $x⊑y$, $x⊏/y$ and $x⋢y$ mean "$x$ is a proper prefix of $y$", "$x$ is a prefix of $y$" and their negations. ${\lambda }_X\in X^{\ast }$ is the empty string and $X^{+}:=X^{\ast }\setminus {\lambda }_X$.

##Elementary properties of minimax

Fix $S$ and $E$ compact Polish spaces, $S$ representing the agent's pure policies and $E$ representing the pure environments. Let $u:S\times E\to R$ be a continuous utility function.

#Proposition 1

Consider $\Phi \subseteq P\left(E\right)$. There exists

$${\pi }^{\ast }\in \underset{\pi \in P\left(S\right)}{argmax}\underset{\mu \in \Phi }{inf}{E}_{\pi \times \mu }\left[u\right]$$

Moreover, let $\overline{\Phi }$ be the closure of the convex hull of $\Phi$. Then, the same ${\pi }^{\ast }$ satisfies

$${\pi }^{\ast }\in \underset{\pi \in P\left(S\right)}{argmax}\underset{\mu \in \overline{\Phi }}{min}{E}_{\pi \times \mu }\left[u\right]$$

We will say that such a ${\pi }^{\ast }$ is a minimax policy for $\Phi$.

#Proposition 2

Consider $\Phi ,{\Phi }^{\prime }\in P_C\left(E\right)$ and $p\in [0,1]$. Then, there is ${\nu }^{\ast }\in {\Phi }^{\prime }$ s.t. any minimax policy for $p\Phi +(1-p){\Phi }^{\prime }$ is a minimax policy for $p\Phi +(1-p){\nu }^{\ast }$.

---

In particular, Proposition 2 implies that a minimax policy for $\Phi$ is the optimal policy for some ${\mu }^{\ast }\in \Phi$.

Now we ask what policy is implemented by "subagents" created by a minimax policy. Suppose $S=S_1\times S_2$, where $S_2$ represents the pure policies of the subagent. Assume that there is a Borel set $A\subseteq E$ (the condition for the creation of the subagent), a finite set $T$ (the actions taken before the creation of the subagent), a Borel measurable mapping $\alpha :S_1\to T$ and continuous functions $u_1:S_1\times E\to R$ and $u_2:S_2\times T\times E\to R$ s.t.

$$u(s_1,s_2,e)=u_1(s_1,e)+{\chi }_A\left(e\right)u_2(s_2,\alpha (s_1),e)$$

Consider $\Phi \in P_C\left(E\right)$ and ${\pi }^{\ast }\in P\left(S\right)$ minimax for $\Phi$. Denote ${\mathrm{pr}}_{1,2}:S\to S_{1,2}$ the projection mappings. Define ${\pi }_1^{\ast }\in P\left(S_1\right)$ by

$${\pi }_1^{\ast }:={\mathrm{pr}}_{1\ast }{\pi }^{\ast }$$

Define ${\pi }_2^{\ast }:T\to P\left(S_2\right)$ by

$${\pi }_2^{\ast }\left(t\right):={\mathrm{pr}}_{2\ast }({\pi }^{\ast }\mid {\alpha }^{-1}(t)\times S_2)$$

If for some $t_0\in T$ we have ${\pi }^{\ast }\left({\alpha }^{-1}\right(t_0)\times S_2)=0$, then ${\pi }_2^{\ast }\left(t_0\right)$ can be arbitrary.

#Proposition 3

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{\mu \in \Phi }{min}\left(E_{{\pi }_1^{\ast }\times \mu }\right[u_1]+\mu (A\left)E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\right[E_{{\pi }_2\left(t\right)\times \mu \mid A}\left[u_2\right(t\left)\right]\left]\right)$$

---

It should also be possible to make do without $T$ and the associated decomposition of $u$ by instead decomposing ${\pi }^{\ast }$ into ${\pi }_1^{\ast }$ and a Markov kernel from $S_1$ to $S_2$.

##Asymptotic optimality

Fix finite sets $A$ (actions) and $O$ (observations). We now assume that $E=O^{\omega }$ and $S=O^{\ast }\to A$ with the product topology. We fix $\gamma :N\to R^{\ge 0}$ a time discount function satisfying ${\sum }_n\gamma \left(n\right)<\infty$ and $r:(A\times O{)}^{\ast }\to R$ a bounded reward function. Given $e\in O^{\ast }$ and $s:O^{\ast }\to A$, we define $e^s\in (A\times O{)}^{\omega }$ by

$$e_n^s:=\left(s\right(e_{<n}),e_n)$$

The utility function is then given by

$$u(s,e)=\sum _{n\in N}\gamma \left(n\right)r\left(e_{<n}^s\right)$$

We will need a notation for a combination of two policies where the agent switches from one to another when observing some $x\in O^{\ast }$. Given $s_1:O^{\ast }\to A$ and $s_2:O^{\ast }\to A$, we define $s_1{\times }_x{s}_2:O^{\ast }\to A$ by

$$\left(s_1{\times }_x{s}_2\right)\left(y\right):=\{\begin{array}{c}{s}_1\left(y\right)\text{if}y⋣x\\ s_2\left(z\right)\text{if}y=xz\end{array}$$

Consider any $\pi \in P(O^{\ast }\to A)$ and $\rho :A^{\left|x\right|}\to P(O^{\ast }\to A)$. We define $\pi {\otimes }_x\rho \in P(O^{\ast }\to A)$ as follows. For any Borel measurable $B\subseteq O^{\ast }\to A$:

$$\left(\pi {\otimes }_x\rho \right)\left(B\right):=\sum _{t\in A^{\left|x\right|}}{\mathrm{Pr}}_{\begin{array}{c}{s}_1\sim \pi \\ s_2\sim \rho \left(t\right)\end{array}}[s_1{\times }_x{s}_2\in B\wedge \forall n<|x|:t_n=s_1(x_{<n}\left)\right]$$

It is easy to see the above indeed defines a probability measure.

Note that changing the policy after a certain event cannot change utility more than $O\left(1\right)$ times the probability of the event times the corresponding time discount factor. That is, we have the following:

#Proposition 4

$$\left|E_{\left(\pi {\otimes }_x\rho \right)\times \mu }\right[u]-E_{\pi \times \mu }[u\left]\right|\le (supr-infr){\mathrm{Pr}}_{e\sim \mu }[x⊏e]\sum _{n>\left|x\right|}\gamma \left(n\right)$$

---

We are now ready to formulate the optimality theorem. Consider $\Phi ,{\Phi }^{\prime }\in P_C\left(O^{\omega }\right)$ and $p\in (0,1]$. Denote $\Psi =p\Phi +(1-p){\Phi }^{\prime }$. We think of $\Psi$ as the prior, $\Phi$ as one of the models in the prior (assigned probability $p$) and ${\Phi }^{\prime }$ as the convex combination of all other models. Let ${\pi }^{\ast }\in P(O^{\ast }\to A)$ be a minimax policy for $\Psi$. Define $v:O^{\ast }\to R$ by

$$v\left(x\right):=\underset{\rho \in A^{\left|x\right|}\to P(O^{\ast }\to A)}{max}\underset{\mu \in \Phi }{min}{E}_{\left({\pi }^{\ast }{\otimes }_x\rho \right)\times \mu }\left[u\right]$$

That is, $v$ is the expected utility that can be guaranteed by changing the policy following $x$, assuming that the true environment is in $\Phi$. We claim that if the true environment is in $\Phi$, then after sufficient time ${\pi }^{\ast }$ will achieve at least as much utility as can be guaranteed for $\Phi$ (guaranteed under the constraint of following ${\pi }^{\ast }$ until the point of making the current observations). That is, $v$ can only be greater than $E_{{\pi }^{\ast }\times \mu }\left[u\right]$ by a quantity that goes to 0 with probability 1, even after normalizing according to Proposition~5:

#Theorem 1

$$\forall \mu \in \Phi :{\mathrm{Pr}}_{e\sim \mu }[\underset{n\to \infty }{lim}max(\frac{v\left(e_{<n}\right)-E_{{\pi }^{\ast }\times \mu }\left[u\right]}{{\mathrm{Pr}}_{e^{\prime }\sim \mu }[e_{<n}⊏e^{\prime }]{\sum }_{m>n}\gamma \left(m\right)},0)=0]=1$$

##Appendix A

We will repeatedly use the standard fact that, given $X$ a compact Polish space, $P\left(X\right)$ is also a compact Polish space (it is metrizable by the Levy-Prokhorov metric, compact as a consequence of the Banach-Alaoglu theorem and the fact that any probability measure on a Polish space is Radon, and separability is also not hard to prove).

#Proposition A.1

Consider $X,Y$ compact Polish spaces, $f:X\times Y\to R$ continuous, $x_{\infty }\in X$ and a sequence $x_n\to x_{\infty }$. Define $g_n:Y\to R$ by $g_n\left(y\right):=f(x_n,y)$ and $g_{\infty }:Y\to R$ by $g_{\infty }\left(y\right):=f(x_{\infty },y)$. Then, $g_n$ converges to $g_{\infty }$ uniformly.

#Proof of Proposition A.1

Assume to the contrary that there is $ϵ>0$ and a subsequence $\{x_n^{\prime }\in X{\}}_{n\in N}$ of $\left\{x_n\right\}$ s.t.

$$\underset{y\in Y}{max}\left|f\right(x_n^{\prime },y)-f(x_{\infty },y\left)\right|>ϵ$$

This implies we can choose $\{y_n\in Y{\}}_{n\in N}$ s.t. $\left|f\right(x_n^{\prime },y_n)-f(x_{\infty },y_n\left)\right|>ϵ$. Let $\{n_k\in N{\}}_{k\in N}$ be an increasing sequence s.t. $y_{n_k}\to y_{\infty }$ for some $y_{\infty }\in Y$. We get $\left|f\right(x_{n_k}^{\prime },y_{n_k})-f(x_{\infty },y_{n_k}\left)\right|>ϵ$, which is a contradiction because $f(x_{n_k}^{\prime },y_{n_k})\to f(x_{\infty },y_{\infty })$ and $f(x_{\infty },y_{n_k})\to f(x_{\infty },y_{\infty })$.

#Proposition A.2

Consider $X,Y$ compact Polish spaces and $f:X\times Y\to R$ continuous. Define $\varphi :X\times P\left(Y\right)\to R$ by

$$\varphi (x,\nu ):=E_{y\sim \nu }\left[f\right(x,y\left)\right]$$

Then, $\varphi$ is continuous.

#Proof of Proposition A.2

Consider any $x_{\infty }\in X$, ${\nu }_{\infty }\in P\left(Y\right)$ and sequences $x_n\to x_{\infty }$, ${\nu }_n\to {\nu }_{\infty }$. We have

$$\varphi (x_n,{\nu }_n)-\varphi (x_{\infty },{\nu }_{\infty })=E_{y\sim {\nu }_n}\left[f\right(x_n,y)-f(x_{\infty },y\left)\right]+E_{y\sim {\nu }_n}\left[f\right(x_{\infty },y\left)\right]-E_{y\sim {\nu }_{\infty }}\left[f\right(x_{\infty },y\left)\right]$$

On the right hand side, the first term goes to 0 by Proposition A.1 and the second term goes to 0 by definition of the weak* topology.

#Proposition A.3

Consider any $X,Y$ compact Polish and $f:X\times Y\to R$ continuous. Define $F:P\left(X\right)\times P\left(Y\right)\to R$ by

$$F(\mu ,\nu ):=E_{\mu \times \nu }\left[f\right]$$

Then, $F$ is continuous.

#Proof of Proposition A.3

Follows by applying Fubini's theorem and using Proposition A.2 twice.

#Proposition A.4

Consider any $X,Y$ compact Polish, $A\subseteq Y$ and $f:X\times Y\to R$ continuous. Define $f_A:X\to R$ by $f_A\left(x\right):={inf}_{y\in A}f(x,y)$. Then, $f_A$ is continuous.

#Proof of Proposition A.4

Consider any $x_{\infty }\in X$ and a sequence $x_n\to x_{\infty }$

$$\left|\underset{y\in A}{inf}f\right(x_n,y)-\underset{y\in A}{inf}f(x_{\infty },y\left)\right|\le \underset{y\in A}{sup}\left|f\right(x_n,y)-f(x_{\infty },y\left)\right|$$

By Proposition A.1, the right hand converges to 0, therefore the left hand side also converges to 0.

---

In the following, we will use the notation $U:P\left(S\right)\times P\left(E\right)\to R$, defined by $U(\pi ,\mu ):=E_{\pi \times \mu }\left[u\right]$. By Proposition A.3, $U$ is continuous.

#Proof of Proposition 1

Define $U_{\Phi }:P\left(S\right)\to R$ by $U_{\Phi }\left(\pi \right):={inf}_{\mu \in \Phi }U(\pi ,\mu )$. By Proposition A.4, $U_{\Phi }$ is continuous and therefore, ${\pi }^{\ast }$ exists.

$U$ is continuous and affine in the 2nd argument (i.e. it sends convex linear combinations to convex linear combinations), and therefore ${inf}_{\mu \in \Phi }U(\pi ,\mu )={min}_{\mu \in \overline{\Phi }}U(\pi ,\mu )$, implying the second part of the proposition.

#Proof of Proposition 2

Define $V:P\left(E\right)\to R$ by $V\left(\mu \right):={max}_{\pi \in P\left(S\right)}U(\pi ,\mu )={max}_{s\in S}U({\delta }_s,\mu )$. Denote $\Psi :=p\Phi +(1-p){\Phi }^{\prime }$. By Proposition A.4, $V$ is continuous and therefore, there exists

$${\xi }^{\ast }\in \underset{\mu \in \Psi }{argmin}V\left(\mu \right)$$

Choose ${\mu }^{\ast }\in \Phi$, ${\nu }^{\ast }\in {\Phi }^{\prime }$ s.t. ${\xi }^{\ast }=p{\mu }^{\ast }+(1-p){\nu }^{\ast }$.

$P\left(S\right)$ and $\Psi$ are compact convex sets in the spaces of finite signed Borel measures on $S$ and $E$ respectively. Therefore, we can apply the minimax theorem to get

$$\underset{\pi \in P\left(S\right)}{max}\underset{\xi \in \Psi }{min}U(\pi ,\xi )=\underset{\xi \in \Psi }{min}\underset{s\in S}{max}U({\delta }_s,\xi )$$

Denote the above number $u^{\ast }$. We have

$$\underset{\mu \in \Phi }{min}U({\pi }^{\ast },p\mu +(1-p\left){\nu }^{\ast }\right)\ge \underset{\xi \in \Psi }{min}U({\pi }^{\ast },\xi )=u^{\ast }$$

On the other hand

$$\underset{\pi \in P\left(S\right)}{max}\underset{\mu \in \Phi }{min}U(\pi ,p\mu +(1-p\left){\nu }^{\ast }\right)\le \underset{\pi \in P\left(S\right)}{max}U(\pi ,{\xi }^{\ast })=u^{\ast }$$

Combining the inequalities, we get the desired result.

#Definition A.1

In the setting of Proposition 3, consider any ${\pi }_1\in P\left(S_1\right)$ and ${\pi }_2:T\to P\left(S_2\right)$. We define ${\pi }_1{\otimes }_{\alpha }{\pi }_2\in P(S_1\times S_2)$ as follows. For any Borel measurable $B\subseteq S_1\times S_2$:

$$\left({\pi }_1{\otimes }_{\alpha }{\pi }_2\right)\left(B\right):=\sum _{t\in T}({\pi }_1\times {\pi }_2(t\left)\right)(B\cap ({\alpha }^{-1}\left(t\right)\times S_2\left)\right)$$

It is easy to see the above indeed defines a probability measure.

#Proposition A.5

Consider any ${\pi }_1\in P\left(S_1\right)$ and ${\pi }_2:T\to P\left(S_2\right)$ and $f:S_1\times S_2\to R$ Borel measurable and bounded. Then:

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=E_{s_1\sim {\pi }_1}\left[E_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\right[f(s_1,s_2)\left]\right]$$

#Proof of Proposition A.5

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=\sum _{t\in T}{\int }_{{\alpha }^{-1}\left(t\right)\times S_2}f(s_1,s_2)d({\pi }_1\times {\pi }_2(t\left)\right)\left(s_2\right)$$

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=\sum _{t\in T}{\int }_{{\alpha }^{-1}\left(t\right)}{\int }_{S_2}f(s_1,s_2)d{\pi }_2\left(t\right)\left(s_2\right)d{\pi }_1\left(s_1\right)$$

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=\sum _{t\in T}{\int }_{{\alpha }^{-1}\left(t\right)}{E}_{s_2\sim {\pi }_2\left(t\right)}\left[f\right(s_1,s_2\left)\right]d{\pi }_1\left(s_1\right)$$

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=\sum _{t\in T}{\int }_{{\alpha }^{-1}\left(t\right)}{E}_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\left[f\right(s_1,s_2\left)\right]d{\pi }_1\left(s_1\right)$$

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]={\int }_{S_1}{E}_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\left[f\right(s_1,s_2\left)\right]d{\pi }_1\left(s_1\right)$$

$$E_{{\pi }_1{\otimes }_{\alpha }{\pi }_2}\left[f\right]=E_{s_1\sim {\pi }_1}\left[E_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\right[f(s_1,s_2)\left]\right]$$

#Proposition A.6

Given ${\pi }_1\in P\left(S_1\right)$, ${\pi }_2:T\to P\left(S_2\right)$ and $\mu \in P\left(E\right)$

$$U({\pi }_1{\otimes }_{\alpha }{\pi }_2,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+\mu \left(A\right)E_{t\sim {\alpha }_{\ast }{\pi }_1}\left[E_{{\pi }_2\left(t\right)\times \mu \mid A}\right[u_2\left(t\right)\left]\right]$$

#Proof of Proposition A.6

Applying Proposition A.5:

$$U({\pi }_1{\otimes }_{\alpha }{\pi }_2,\mu )=E_{s_1\sim {\pi }_1}\left[E_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\right[E_{e\sim \mu }\left[u_1\right(s_1,e)+{\chi }_A(e\left)u_2\right(s_2,\alpha \left(s_1\right),e\left)\right]\left]\right]$$

$$U({\pi }_1{\otimes }_{\alpha }{\pi }_2,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+E_{s_1\sim {\pi }_1}\left[E_{s_2\sim {\pi }_2\left(\alpha \right(s_1\left)\right)}\right[\mu \left(A\right)E_{e\sim \mu \mid A}\left[u_2\right(s_2,\alpha \left(s_1\right),e\left)\right]\left]\right]$$

$$U({\pi }_1{\otimes }_{\alpha }{\pi }_2,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+\mu \left(A\right)E_{t\sim {\alpha }_{\ast }{\pi }_1}\left[E_{{\pi }_2\left(t\right)\times \mu \mid A}\right[u_2\left(t\right)\left]\right]$$

#Proposition A.7

Consider any $\pi \in P(S_1\times S_2)$. Define ${\pi }_1\in P\left(S_1\right)$ and ${\pi }_2:T\to P\left(S_2\right)$ by

$${\pi }_1:={\mathrm{pr}}_{1\ast }\pi$$

$${\pi }_2\left(t\right):={\mathrm{pr}}_{2\ast }(\pi \mid {\alpha }^{-1}(t)\times S_2)$$

If for some $t_0\in T$ we have $\pi \left({\alpha }^{-1}\right(t_0)\times S_2)=0$, then ${\pi }_2\left(t_0\right)$ can be arbitrary.

Then,

$$\forall \mu \in P\left(E\right):U(\pi ,\mu )=U({\pi }_1{\otimes }_{\alpha }{\pi }_2,\mu )$$

#Proof of Proposition A.7

$$U(\pi ,\mu )=E_{\begin{array}{c}(s_1,s_2)\sim \pi \\ e\sim \mu \end{array}}\left[u_1\right(s_1,e)+{\chi }_A(e\left)u_2\right(s_2,\alpha \left(s_1\right),e\left)\right]$$

$$U(\pi ,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+\mu \left(A\right)E_{\begin{array}{c}(s_1,s_2)\sim \pi \\ e\sim \mu \mid A\end{array}}\left[u_2\right(s_2,\alpha \left(s_1\right),e\left)\right]$$

$$U(\pi ,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+\mu \left(A\right)\sum _{t\in T}{\mathrm{Pr}}_{(s_1,s_2)\sim \pi }\left[\alpha \right(s_1)=t]E_{\begin{array}{c}(s_1,s_2)\sim \pi \mid {\alpha }^{-1}\left(t\right)\times S_2\\ e\sim \mu \mid A\end{array}}\left[u_2\right(s_2,t,e\left)\right]$$

$$U(\pi ,\mu )=E_{{\pi }_1\times \mu }\left[u_1\right]+\mu \left(A\right)E_{t\sim {\alpha }_{\ast }{\pi }_1}\left[E_{{\pi }_2\left(t\right)\times \mu \mid A}\right[u_2\left(t\right)\left]\right]$$

Applying Proposition A.6, we get the desired result.

#Proof of Proposition 3

Consider any ${\pi }_2:T\to P\left(S_2\right)$. By definition of ${\pi }^{\ast }$

$$\underset{\mu \in \Phi }{min}U({\pi }_1^{\ast }{\otimes }_{\alpha }{\pi }_2,\mu )\le \underset{\mu \in \Phi }{min}U({\pi }^{\ast },\mu )$$

Applying Proposition A.7 to the right hand side

$$\underset{\mu \in \Phi }{min}U({\pi }_1^{\ast }{\otimes }_{\alpha }{\pi }_2,\mu )\le \underset{\mu \in \Phi }{min}U({\pi }_1^{\ast }{\otimes }_{\alpha }{\pi }_2^{\ast },\mu )$$

Applying Proposition A.6 to both sides, we get the desired result.

---

Given any $x\in O^{\ast }$, we denote $x{O}^{\omega }:=\{xy\mid y\in O^{\omega }\}$ and $\overline{x}{O}^{\omega }:=O^{\omega }\setminus x{O}^{\omega }$.

#Proof of Proposition 4

We have

$$E_{\pi \times \mu }\left[u\right]=\mu \left(x{O}^{\omega }\right)E_{\pi \times \mu \mid x{O}^{\omega }}\left[u\right]+(1-\mu (x{O}^{\omega }\left)\right)E_{\pi \times \mu \mid \overline{x}{O}^{\ast }}\left[u\right]$$

$$E_{\left(\pi {\otimes }_x\rho \right)\times \mu }\left[u\right]=\mu \left(x{O}^{\omega }\right)E_{\left(\pi {\otimes }_x\rho \right)\times \mu \mid x{O}^{\omega }}\left[u\right]+(1-\mu (x{O}^{\omega }\left)\right)E_{\pi \times \mu \mid \overline{x}{O}^{\omega }}\left[u\right]$$

$$E_{\left(\pi {\otimes }_x\rho \right)\times \mu }\left[u\right]-E_{\pi \times \mu }\left[u\right]=\mu \left(x{O}^{\omega }\right)\left(E_{\left(\pi {\otimes }_x\rho \right)\times \mu \mid x{O}^{\omega }}\right[u]-E_{\pi \times \mu \mid x{O}^{\omega }}[u\left]\right)$$

Denote $u_1(s,e):={\sum }_{n\le \left|x\right|}\gamma \left(n\right)r\left(e_{<n}^s\right)$, $u_2(s,e):={\sum }_{n>\left|x\right|}\gamma \left(n\right)r\left(e_{<n}^s\right)$. We have

$$E_{\pi \times \mu \mid x{O}^{\omega }}\left[u\right]=E_{\pi \times \mu \mid x{O}^{\omega }}\left[u_1\right]+E_{\pi \times \mu \mid x{O}^{\ast }}\left[u_2\right]$$

$$E_{\left(\pi {\otimes }_x\rho \right)\times \mu \mid x{O}^{\omega }}\left[u\right]=E_{\pi \times \mu \mid x{O}^{\omega }}\left[u_1\right]+E_{\left(\pi {\otimes }_x\rho \right)\times \mu \mid x{O}^{\omega }}\left[u_2\right]$$

$$E_{\left(\pi {\otimes }_x\rho \right)\times \mu }\left[u\right]-E_{\pi \times \mu }\left[u\right]=\mu \left(x{O}^{\omega }\right)\left(E_{\left(\pi {\otimes }_x\rho \right)\times \mu \mid x{O}^{\omega }}\right[u_2]-E_{\pi \times \mu \mid x{O}^{\omega }}[u_2\left]\right)$$

The desired result now follows from $(infr){\sum }_{n>\left|x\right|}\gamma \left(n\right)\le u_2\le (supr){\sum }_{n>\left|x\right|}\gamma \left(n\right)$.

#Definition A.2

A splitting of $(S,E,u)$ is $(S_1,S_2,A,T,\alpha ,u_1,u_2)$ s.t. $S\cong S_1\times S_2$, $A\subseteq E$ is Borel, $T$ is a finite set, $\alpha :S_1\to T$ is Borel measurable, $u_1:S_1\times E\to R$ and $u_2:S_2\times T\times E\to R$ are continuous and

$$u(s_1,s_2,e)=u_1(s_1,e)+{\chi }_A\left(e\right)u_2(s_2,\alpha (s_1),e)$$

#Proposition A.8

Consider $\Phi \in P_C\left(E\right)$, ${\nu }^{\ast }\in P\left(E\right)$ and $p\in [0,1]$, and denote $\Psi :=p\Phi +(1-p){\nu }^{\ast }$. Suppose that $(S_1,S_2,A,T,\alpha ,u_1,u_2)$ is a splitting of $(S,E,u)$. Assume ${\nu }^{\ast }\left(A\right)>0$. Fix $\pi \in P\left(S_1\right)$. Let ${\rho }^{\ast }:T\to P\left(S_2\right)$ satisfy

$${\rho }^{\ast }\in \underset{\rho :T\to P\left(S_2\right)}{argmax}\underset{\xi \in \Psi }{min}U(\pi {\otimes }_{\alpha }\rho ,\xi )$$

Denote $\Gamma :=sup{u}_2-inf{u}_2$. Then, for any ${\mu }_0\in \Phi$ s.t. ${\mu }_0\left(A\right)>0$

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\mu }_0)\ge \underset{\rho :T\to P\left(S_2\right)}{max}\underset{\mu \in \Phi }{min}U(\pi {\otimes }_{\alpha }\rho ,\mu )-2\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)$$

#Proof of Proposition A.8

Let ${\tau }^{\ast }:T\to P\left(S_2\right)$ satisfy

$${\tau }^{\ast }\in \underset{\rho :T\to P\left(S_2\right)}{argmax}\underset{\mu \in \Phi }{min}U(\pi {\otimes }_{\alpha }\rho ,\mu )$$

Denote $u^{\ast }:={min}_{\mu \in \Phi }U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\mu )$. Consider any $\mu \in \Phi$ and denote $\xi :=p\mu +(1-p){\nu }^{\ast }$. We have

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )=pU(\pi {\otimes }_{\alpha }{\tau }^{\ast },{\mu }^{\prime })+(1-p)U(\pi {\otimes }_{\alpha }{\tau }^{\ast },{\nu }^{\ast })$$

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge p{u}^{\ast }+(1-p)U(\pi {\otimes }_{\alpha }{\tau }^{\ast },{\nu }^{\ast })$$

Applying Proposition A.6 to the right hand side

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge p{u}^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)E_{t\sim {\alpha }_{\ast }\pi }\right[E_{{\tau }^{\ast }\left(t\right)\times {\nu }^{\ast }}[u_2\mid A]\left]\right)$$

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge p{u}^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)\right(E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\tau }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]-\Gamma d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

Also, we have

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },{\mu }_0)\ge u^{\ast }$$

Applying Proposition A.6 again

$$E_{\pi \times {\mu }_0}\left[u_1\right]+{\mu }_0\left(A\right)E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\tau }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]\ge u^{\ast }$$

$$E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\tau }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]\ge \frac{u^{\ast }-E_{\pi \times {\mu }_0}\left[u_1\right]}{{\mu }_0\left(A\right)}$$

Combining the inequalities

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge p{u}^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)\right(\frac{u^{\ast }-E_{\pi \times {\mu }_0}\left[u_1\right]}{{\mu }_0\left(A\right)}-\Gamma d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge p{u}^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(u^{\ast }-E_{\pi \times {\mu }_0}\left[u_1\right]-\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

$$U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge (p+(1-p\left)\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}\right)u^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]-\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(E_{\pi \times {\mu }_0}\left[u_1\right]+\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

The above inequality holds for any $\xi$, therefore

$$\underset{\xi \in \Psi }{min}U(\pi {\otimes }_{\alpha }{\tau }^{\ast },\xi )\ge (p+(1-p\left)\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}\right)u^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]-\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(E_{\pi \times {\mu }_0}\left[u_1\right]+\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

By definition of ${\rho }^{\ast }$, it follows that

$$\underset{\xi \in \Psi }{min}U(\pi {\otimes }_{\alpha }{\rho }^{\ast },\xi )\ge (p+(1-p\left)\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}\right)u^{\ast }+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]-\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(E_{\pi \times {\mu }_0}\left[u_1\right]+\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A)\left)\right)$$

Denote ${\xi }_0:=p{\mu }_0+(1-p){\nu }^{\ast }$ and $u:=U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\mu }_0)$. We have

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)=pu+(1-p)U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\nu }^{\ast })$$

Applying Proposition A.6 to the right hand side

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)=pu+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)E_{t\sim {\alpha }_{\ast }\pi }\right[E_{{\rho }^{\ast }\left(t\right)\times {\nu }^{\ast }}[u_2\mid A]\left]\right)$$

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)\le pu+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)\right(E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\rho }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]+\Gamma d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A))$$

On the other hand, Proposition A.6 implies that

$$E_{\pi \times {\mu }_0}\left[u_1\right]+{\mu }_0\left(A\right)E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\rho }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]=u$$

$$E_{t\sim {\alpha }_{\ast }\pi }\left[E_{{\rho }^{\ast }\left(t\right)\times {\mu }_0}\right[u_2\mid A\left]\right]=\frac{u-E_{\pi \times {\mu }_0}\left[u_1\right]}{{\mu }_0\left(A\right)}$$

Substituting in the inequality, we get

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)\le pu+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+{\nu }^{\ast }(A\left)\right(\frac{u-E_{\pi \times {\mu }_0}\left[u_1\right]}{{\mu }_0\left(A\right)}+\Gamma d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A))$$

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)\le pu+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]+\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(u-E_{\pi \times {\mu }_0}\left[u_1\right]+\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A))$$

$$U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)\le (p+(1-p\left)\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}\right)u+(1-p)\left(E_{\pi \times {\nu }^{\ast }}\right[u_1]-\frac{{\nu }^{\ast }\left(A\right)}{{\mu }_0\left(A\right)}(E_{\pi \times {\mu }_0}\left[u_1\right]-\Gamma {\mu }_0\left(A\right)d_{\text{tv}}({\mu }_0\mid A,{\nu }^{\ast }\mid A))$$

Observing that $U(\pi {\otimes }_{\alpha }{\rho }^{\ast },{\xi }_0)\ge {min}_{\xi \in \Psi }U(\pi {\otimes }_{\alpha }{\rho }^{\ast },\xi )$ we can combine the inequalities, we get

$$(<$$