Catastrophe Mitigation Using DRL (Appendices)

[Vanessa Kosoy]

% operators that are separated from the operand by a space

% autosize deliminaters

% operators that require brackets

% operators that require parentheses

% Paper specific

These are Appendices B and C for the essay Catastrophe Mitigation Using DRL. They appear in a separate post because of a length limit in the website.

##Appendix B

Given $p=(a,o)\in A\times O$, we denote $p^A:=a$, $p^O:=o$.

#Proposition B.1

Consider a universe $\upsilon =(\mu ,r)$ which an $O$-realization of an MDP $M$ with state function $S$, a stationary policy ${\pi }^{\ast }:S_M\stackrel{\text{k}}{\to }A$, an arbitrary $I$-policy ${\pi }^0$ and some $\gamma \in (0,1)$. Then,

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(\gamma \right)=\sum _{n=0}^{\infty }{\gamma }^n\underset{x\sim \mu \bowtie {\pi }^0}{E}[V_{M{\pi }^{\ast }}(S\left(x_{:n}\right),\gamma )-Q_{M{\pi }^{\ast }}(S\left(x_{:n}\right),x_n^A,\gamma )]$$

#Proof of Proposition B.1

For the sake of encumbering the notation less, we will omit the parameter $\gamma$ in functions that depend on it. We will use $S$ implicitly, i.e. given $F$ a function on $S_M$ and $h\in \mathrm{hdom}\mu$, $F\left(h\right):=F\left(S\right(h\left)\right)$. Finally, we will omit $M{\pi }^{\ast }$, using the shorthand notations $V:=V_{M{\pi }^{\ast }}$, $Q:=Q_{M{\pi }^{\ast }}$.

For any $x\in {\mathrm{hdom}}^{\omega }\mu$, it is easy to see that

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}=V\left(\lambda \right)=\sum _{n=0}^{\infty }{\gamma }^n(V\left(x_{:n}\right)-\gamma V\left(x_{:n+1}\right))$$

$$U^r\left(x\right)=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^{n}r\left(x_{:n}\right)$$

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}-U^r\left(x\right)=\sum _{n=0}^{\infty }{\gamma }^n(V\left(x_{:n}\right)-(1-\gamma )r\left(x_{:n}\right)-\gamma V\left(x_{:n+1}\right))$$

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}-U^r\left(x\right)=\sum _{n=0}^{\infty }{\gamma }^n(V\left(x_{:n}\right)-Q(x_{:n},x_n^A)+Q(x_{:n},x_n^A)-(1-\gamma )r\left(x_{:n}\right)-\gamma V\left(x_{:n+1}\right))$$

Taking expected value over $x$, we get

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}=\sum _{n=0}^{\infty }{\gamma }^n(\underset{\mu \bowtie {\pi }^0}{E}[V\left(x_{:n}\right)-Q(x_{:n},x_n^A)]+\underset{\mu \bowtie {\pi }^0}{E}[Q(x_{:n},x_n^A)-(1-\gamma )r\left(x_{:n}\right)-\gamma V\left(x_{:n+1}\right)])$$

It is easy to see that the second term vanishes, yielding the desired result.

#Proposition B.2

Consider some $\tau \in (0,\infty )$, $T\in N^{+}$, a universe $\upsilon =(\mu ,r)$ that is an $O$-realization of $M$ with state function $S$, a stationary policy ${\pi }^{\ast }:S_M\stackrel{\text{k}}{\to }A$ and an arbitrary $I$-policy ${\pi }^0:(A\times O{)}^{\ast }\stackrel{\text{k}}{\to }A$. For any $n\in N$, let ${\pi }_n^{\ast }$ be an $I$-policy s.t. for any $h\in \mathrm{hdom}\mu$

$${\pi }_n^{\ast }\left(h\right):=\{\begin{array}{c}{\pi }^0\left(h\right)\text{if}\left|h\right|<nT\\ {\pi }^{\ast }\left(S\right(h\left)\right)\text{otherwise}\end{array}$$

Assume that

i. For any $h\in \mathrm{hdom}\mu$ $$\mathrm{supp}{\pi }^0\left(h\right)\subseteq A_{M{\pi }^{\ast }}^0\left(S\right(h\left)\right)$$

ii. For any $s\in S_M$ and $\gamma \in (0,1)$ $$\left|\frac{d{V}_{M{\pi }^{\ast }}(s,\gamma )}{d\gamma }\right|\le \tau$$

Then, for any $\gamma \in (0,1)$,

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(\gamma \right)\le (1-\gamma )\sum _{n=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{nT+m}(\underset{x\sim \mu \bowtie {\pi }_n^{\ast }}{E}\left[r\left(x_{:nT+m}\right)\right]-\underset{x\sim \mu \bowtie {\pi }^0}{E}\left[r\left(x_{:nT+m}\right)\right])+\frac{2\tau {\gamma }^T(1-\gamma )}{1-{\gamma }^T}$$

#Proof of Proposition B.2

For the sake of encumbering the notation less, we will use $S$ implicitly, i.e. given $F$ a function on $S_M$ and $h\in \mathrm{hdom}\mu$, $F\left(h\right):=F\left(S\right(h\left)\right)$. Also, we will omit $M{\pi }^{\ast }$, using the shorthand notations $V:=V_{M{\pi }^{\ast }}$, $Q:=Q_{M{\pi }^{\ast }}$.

By Proposition B.1, for any $l\in N$

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }_l^{\ast }}\left(\gamma \right)=\sum _{n=0}^{\infty }{\gamma }^n\underset{x\sim \mu \bowtie {\pi }_l^{\ast }}{E}[V(x_{:n},\gamma )-Q(x_{:n},x_n^A,\gamma )]$$

${\pi }_l^{\ast }$ coincides with ${\pi }^{\ast }$ after $lT$, therefore the corresponding expected values vanish.

$${\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }_l^{\ast }}\left(\gamma \right)=\sum _{n=0}^{lT-1}{\gamma }^n\underset{x\sim \mu \bowtie {\pi }^0}{E}[V(x_{:n},\gamma )-Q(x_{:n},x_n^A,\gamma )]$$

Subtracting the equalities for $l+1$ and $l$, we get

$${\mathrm{EU}}_{\upsilon }^{{\pi }_l^{\ast }}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }_{l+1}^{\ast }}\left(\gamma \right)=\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{x\sim \mu \bowtie {\pi }^0}{E}[V(x_{:n},\gamma )-Q(x_{:n},x_n^A,\gamma )]$$

$$(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n(\underset{x\sim \mu \bowtie {\pi }_l^{\ast }}{E}\left[r\left(x_{:n}\right)\right]-\underset{x\sim \mu \bowtie {\pi }_{l+1}^{\ast }}{E}\left[r\left(x_{:n}\right)\right])=\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{x\sim \mu \bowtie {\pi }^0}{E}[V(x_{:n},\gamma )-Q(x_{:n},x_n^A,\gamma )]$$

${\pi }_l^{\ast }$ and ${\pi }_{l+1}^{\ast }$ coincide until $lT$, therefore

$$(1-\gamma )\sum _{n=lT}^{\infty }{\gamma }^n(\underset{x\sim \mu \bowtie {\pi }_l^{\ast }}{E}\left[r\left(x_{:n}\right)\right]-\underset{x\sim \mu \bowtie {\pi }_{l+1}^{\ast }}{E}\left[r\left(x_{:n}\right)\right])=\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{x\sim \mu \bowtie {\pi }^0}{E}[V(x_{:n},\gamma )-Q(x_{:n},x_n^A,\gamma )]$$

Denote ${\rho }_l^{\ast }:=\mu \bowtie {\pi }_l^{\ast }$, ${\rho }^0:=\mu \bowtie {\pi }^0$. We also use the shorthand notations $r_n:=r\left(x_{:n}\right)$, $V_n\left(\gamma \right):=V(x_{:n},\gamma )$, $Q_n\left(\gamma \right):=Q(x_{:n},x_n^A,\gamma )$. Both ${\pi }_l^{\ast }$ and ${\pi }_{l+1}^{\ast }$ coincide with ${\pi }^{\ast }$ after $(l+1)T$, therefore

$$(1-\gamma )\sum _{n=lT}^{(l+1)T-1}{\gamma }^n(\underset{{\rho }_l^{\ast }}{E}\left[r_n\right]-\underset{{\rho }^0}{E}\left[r_n\right])+{\gamma }^{(l+1)T}(\underset{{\rho }_l^{\ast }}{E}\left[V_{(l+1)T}\right(\gamma \left)\right]-\underset{{\rho }^0}{E}\left[V_{(l+1)T}\right(\gamma \left)\right])=\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }^0}{E}\left[V_n\right(\gamma )-Q_n(\gamma \left)\right]$$

Denote $V^{\prime }(s,\gamma ):=\frac{dV(s,\gamma )}{d\gamma }$. By the mean value theorem, for each $s\in S_M$ there is ${\gamma }^{\ast }\in (\gamma ,1)$ s.t.

$$V(s,\gamma )=V^0\left(s\right)-V^{\prime }(s,{\gamma }^{\ast })\cdot (1-\gamma )$$

$$V^0\left(s\right)-\tau (1-\gamma )\le V(s,\gamma )\le V^0\left(s\right)+\tau (1-\gamma )$$

It follows that

$$(1-\gamma )\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[r_n\right]+{\gamma }^{(l+1)T}(\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[V_{(l+1)T}^0\right]+2\tau (1-\gamma \left)\right)\ge \sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }^0}{E}\left[V_n\right(\gamma )-Q_n(\gamma \left)\right]$$

Here, an expected value w.r.t. the difference of two probability measures is understood to mean the corresponding difference of expected values.

It is easy to see that assumption i implies that $V_n^0$ is a submartingale for ${\rho }^0$ (whereas it is a martingale for $\mu \bowtie {\pi }^{\ast }$) and therefore

$$\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[V_{(l+1)T}^0\right]\le 0$$

We get

$$(1-\gamma )\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[r_n\right]+2\tau {\gamma }^{(l+1)T}(1-\gamma )\ge \sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }^0}{E}\left[V_n\right(\gamma )-Q_n(\gamma \left)\right]$$

Summing over $l$, we get

$$(1-\gamma )\sum _{l=0}^{\infty }\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[r_n\right]+\frac{2\tau {\gamma }^T(1-\gamma )}{1-{\gamma }^T}\ge \sum _{n=0}^{\infty }{\gamma }^n\underset{{\rho }^0}{E}\left[V_n\right(\gamma )-Q_n(\gamma \left)\right]$$

Applying Proposition B.1 to the right hand side

$$(1-\gamma )\sum _{l=0}^{\infty }\sum _{n=lT}^{(l+1)T-1}{\gamma }^n\underset{{\rho }_l^{\ast }-{\rho }^0}{E}\left[r_n\right]+\frac{2\tau {\gamma }^T(1-\gamma )}{1-{\gamma }^T}\ge {\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }}\left(\gamma \right)-{\mathrm{EU}}_{\upsilon }^{{\pi }^0}\left(\gamma \right)$$

#Proof of Lemma A.1

Fix $\gamma \in (0,1)$, $\eta \in (0,N^{-1})$ and $T\in N^{+}$. Denote ${\nu }^k:={\overline{\mu }}^k\left[{\sigma }^k{S}^k\right]$. To avoid cumbersome notation, whenever $M^k$ should appear a subscript, we will replace it by $k$. Let $(\Omega ,P\in \Delta \Omega )$ be a probability space\Comment{ and $\{F_n\subseteq 2^{\Omega }{\}}_{n\in N\bigsqcup \{-1\}}$ a filtration of $\Omega$}. Let $K:\Omega \to \left[N\right]$ be \Comment{measurable w.r.t. $F_{-1}$}a random variable and the following be stochastic processes\Comment{ adapted to $F$}

$$Z_n,{\tilde{Z}}_n:\Omega \to \Delta \left[N\right]$$

$$J_n:\Omega \to \left[N\right]$$

$${\Psi }_n:\Omega \to A$$

$$A_n:\Omega \to \overline{A}$$

$${\Theta }_n:\Omega \to \overline{O}$$

We also define $A{\Theta }_{:n}:\Omega \to {\overline{A\times O}}^{\ast }$ by

$$A{\Theta }_{:n}:=A_0{\Theta }_0{A}_1{\Theta }_1\dots A_{n-1}{\Theta }_{n-1}$$

(The following conditions on $A$ and $\Theta$ imply that the range of the above is indeed in ${\overline{A\times O}}^{\ast }$.) Let $D$ and $D^{!k}$ be as in Proposition C.1 (we assume w.l.o.g. that $ϵ<\frac{1}{\left|A\right|}$). We construct $\Omega$\Comment{, $F$}, $K$, $Z$, $\tilde{Z}$, $J$, $\Psi$, $A$ and $\Theta$ s.t $K$ is uniformly distributed and for any $k\in \left[N\right]$, $l\in N$, $m\in \left[T\right]$ and $o\in O$, denoting $n=lT+m$

$${\tilde{Z}}_0\left(k\right)\equiv \frac{1}{N}$$

$$Z_n\left(k\right)=\frac{{\tilde{Z}}_n\left(k\right)\left[\right[{\tilde{Z}}_n\left(k\right)\ge \eta \left]\right]}{{\sum }_{j=0}^{N-1}{\tilde{Z}}_n\left(j\right)\left[\right[{\tilde{Z}}_n\left(j\right)\ge \eta \left]\right]}$$

$$Pr[J_l=k\mid Z_{lT}]=Z_{lT}\left(k\right)$$

$${\Psi }_n={\pi }^{J_l}\left(A{\Theta }_{:n}\right)$$

$$Pr[{\Theta }_n=o\mid A{\Theta }_{:n}]={\nu }^K(o\mid A{\Theta }_{:n})$$

$$A_n=D(A{\Theta }_{:n},{\Psi }_n)$$

$${\tilde{Z}}_{n+1}\left(k\right)\sum _{j=0}^{N-1}{Z}_n\left(j\right)\left[\right[A_n=D^{!j}(A{\Theta }_{:n},{\Psi }_n)\left]\right]{\nu }^j({\Theta }_n\mid A{\Theta }_{:n}{A}_n)=Z_n\left(k\right)\left[\right[A_n=D^{!k}(A{\Theta }_{:n},{\Psi }_n)\left]\right]{\nu }^k({\Theta }_n\mid A{\Theta }_{:n}{A}_n)$$

Note that the last equation has the form of a Bayesian update which is allowed to be arbitrary when update is on “impossible” information.

We now construct the $\overline{I}$-policy ${\pi }^{\ast }$ s.t. for any $n\in N$, $h\in {\overline{A\times O}}^{\ast }$ s.t.$Pr[A{\Theta }_{:n}=h]>0$ and $a\in \overline{A}$

$${\pi }^{\ast }(a\mid h):=Pr[A_n=a\mid A{\Theta }_{:n}=h]$$

That is, we perform Thompson sampling at time intervals of size $T$, moderated by the delegation routine $D$, and discard from our belief state hypotheses whose probability is below $\eta$ and hypotheses sampling which resulted in recommending “unsafe” actions i.e. actions that $D$ refused to perform.

In order to prove ${\pi }^{\ast }$ has the desired property, we will define the stochastic processes $Z^{!}$, ${\tilde{Z}}^{!}$, $J^{!}$, ${\Psi }^{!}$, $A^{!}$ and ${\Theta }^{!}$, each process of the same type as its shriekless counterpart (thus $\Omega$ is constructed to accommodate them). These processes are required to satisfy the following:

$${\tilde{Z}}_0^{!}\left(k\right)\equiv \frac{1}{N}$$

$$Z_n^{!}\left(k\right)=\frac{{\tilde{Z}}_n^{!}\left(k\right)\left[\right[{\tilde{Z}}_n^{!}\left(k\right)\ge \eta \left]\right]}{{\sum }_{j=0}^{N-1}{\tilde{Z}}_n^{!}\left(j\right)\left[\right[{\tilde{Z}}_n^{!}\left(j\right)\ge \eta \left]\right]}\left[\right[{\tilde{Z}}_n^{!}\left(K\right)\ge \eta \left]\right]+\left[\right[K=k\left]\right]\cdot \left[\right[{\tilde{Z}}_n^{!}\left(K\right)<\eta \left]\right]$$

$$Pr[J_l^{!}=k\mid Z_{lT}^{!}]=Z_{lT}^{!}\left(k\right)$$

$${\Psi }_n^{!}={\pi }^{J_l^{!}}\left(A{\Theta }_{:n}^{!}\right)$$

$$Pr[{\Theta }_n^{!}=o\mid A{\Theta }_{:n}^{!}]={\nu }^K(o\mid A{\Theta }_{:n}^{!})$$

$$A_n^{!}=D^{!K}(A{\Theta }_{:n}^{!},{\Psi }_n^{!})$$

$${\tilde{Z}}_{n+1}^{!}\left(k\right)=\frac{Z_n^{!}\left(k\right)\left[\right[A_n^{!}=D^{!k}(A{\Theta }_{:n}^{!},{\Psi }_n^{!})\left]\right]{\nu }^k({\Theta }_n^{!}\mid A{\Theta }_{:n}^{!}{A}_n^{!})}{{\sum }_{j=0}^{N-1}{Z}_n^{!}\left(j\right)\left[\right[A_n^{!}=D^{!j}(A{\Theta }_{:n}^{!},{\Psi }_n^{!})\left]\right]{\nu }^j({\Theta }_n^{!}\mid A{\Theta }_{:n}^{!}{A}_n^{!})}$$

For any $k\in \left[N\right]$, we construct the $\overline{I}$-policy ${\pi }^{?k}$ s.t. for any $n\in N$, $h\in {\overline{A\times O}}^{\ast }$ s.t.$Pr[A{\Theta }_{:n}^{!}=h,K=k]>0$ and $a\in \overline{A}$

$${\pi }^{?k}(a\mid h):=Pr[A_n^{!}=a\mid A{\Theta }_{:n}^{!}=h,K=k]$$

Given any $\overline{I}$-policy $\pi$ and $I$-policy $\sigma$ we define ${\alpha }_{\sigma \pi }:(A\times O{)}^{\ast }\stackrel{\text{k}}{\to }{\overline{A\times O}}^{\ast }$ by

$${\alpha }_{\sigma \pi }(g\mid h):=\left[\right[h=\underset{–}{g}\left]\right]C_h\prod _{n=0}^{\left|h\right|-1}\sum _{a\in A}\left(\right[[g_n\in \perp aO]]\pi (\perp \mid g_{:n})\sigma (a\mid h_{:n})+[[g_n\in a\perp O]\left]\pi (a\mid g_{:n})\right)$$

Here, $C_h\in R$ is a constant defined s.t. the probabilities sum to 1. We define the $I$-policy $\left[\sigma \right]\underset{–}{\pi }$ by

$$\left[\sigma \right]\underset{–}{\pi }(a\mid h):=\underset{g\sim {\alpha }_{\sigma \pi }\left(h\right)}{Pr}[\pi \left(g\right)=a\vee (\pi \left(g\right)=\perp \wedge \sigma (h)=a)]$$

Condition iii of Proposition C.1 and condition i of Definition A.1 imply that for any $h\in \mathrm{hdom}{\mu }^k$

$$\mathrm{supp}\left[{\sigma }^k\right]{\underset{–}{\pi }}^{?k}\left(h\right)\subseteq A_{M^k{\pi }^k}^0\left(S^k\left(h\right)\right)$$

This means we can apply Proposition B.2 and get

$${\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}\left(\gamma \right)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{?k}}\left(\gamma \right)\le (1-\gamma )\sum _{n=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{nT+m}(\underset{x\sim {\mu }^k\bowtie {\pi }_n^{\ast k}}{E}\left[r\left(x_{:nT+m}\right)\right]-\underset{x\sim {\nu }^k\bowtie {\pi }^{?k}}{E}\left[r\left({\underset{–}{x}}_{:nT+m}\right)\right])+\frac{2\overline{\tau }{\gamma }^T(1-\gamma )}{1-{\gamma }^T}$$

Here, the $I$-policy ${\pi }_n^{\ast k}$ is defined as ${\pi }_n^{\ast }$ in Proposition B.2. We also define the $\overline{I}$-policies ${\pi }_n^{!k}$ and ${\pi }_n^{!!k}$ by

$${\pi }_n^{!k}(a\mid h):=\{\begin{array}{c}{\pi }^{?k}(a\mid h)\text{if}\left|h\right|<nT\\ Pr[A_{\left|h\right|}^{!}=a\mid A{\Theta }_{:\left|h\right|}^{!}=h,K=k,J_n^{!}=k]\text{otherwise}\end{array}$$

$${\pi }_n^{!!k}(a\mid h):=\{\begin{array}{c}{\pi }^{?k}(a\mid h)\text{if}\left|h\right|<nT\\ {\pi }_n^{!k}(a\mid h)+{\pi }_n^{!k}(\perp \mid h)\cdot {\pi }_n^{\ast k}(a\mid \underset{–}{h})\text{if}\left|h\right|\ge nT\text{and}a\ne \perp \\ 0\text{if}\left|h\right|\ge nT\text{and}a=\perp \end{array}$$

Denote

$${\rho }_n^{\ast k}:={\mu }^k\bowtie {\pi }_n^{\ast k}$$

$${\rho }_n^{!!k}:={\nu }^k\bowtie {\pi }_n^{!!k}$$

$${\rho }_n^{!k}:={\nu }^k\bowtie {\pi }_n^{!k}$$

$${\rho }^{?k}:={\nu }^k\bowtie {\pi }^{?k}$$

$$R^{?k}:={\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}\left(\gamma \right)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{?k}}\left(\gamma \right)$$

For each $n\in N$, denote

$${\mathrm{EU}}_n^{\ast k}\left(\gamma \right):=\frac{1-\gamma }{1-{\gamma }^T}\sum _{m=0}^{T-1}{\gamma }^m\underset{x\sim {\rho }_n^{\ast k}}{E}\left[r\left(x_{:nT+m}\right)\right]$$

$${\mathrm{EU}}_n^{!!k}\left(\gamma \right):=\frac{1-\gamma }{1-{\gamma }^T}\sum _{m=0}^{T-1}{\gamma }^m\underset{x\sim {\rho }_n^{!!k}}{E}\left[r\left({\underset{–}{x}}_{:nT+m}\right)\right]$$

$${\mathrm{EU}}_n^{!k}\left(\gamma \right):=\frac{1-\gamma }{1-{\gamma }^T}\sum _{m=0}^{T-1}{\gamma }^m\underset{x\sim {\rho }_n^{!k}}{E}\left[r\left({\underset{–}{x}}_{:nT+m}\right)\right]$$

$${\mathrm{EU}}_n^{?k}\left(\gamma \right):=\frac{1-\gamma }{1-{\gamma }^T}\sum _{m=0}^{T-1}{\gamma }^m\underset{x\sim {\rho }^{?k}}{E}\left[r\left({\underset{–}{x}}_{:nT+m}\right)\right]$$

We have

$$R^{?k}\le (1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\left({\mathrm{EU}}_n^{\ast k}\right(\gamma )-{\mathrm{EU}}_n^{?k}(\gamma \left)\right)+\frac{2\overline{\tau }{\gamma }^T(1-\gamma )}{1-{\gamma }^T}$$

$$R^{?k}\le (1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\left({\mathrm{EU}}_n^{\ast k}\right(\gamma )-{\mathrm{EU}}_n^{!!k}(\gamma )+{\mathrm{EU}}_n^{!!k}(\gamma )-{\mathrm{EU}}_n^{!k}(\gamma )+{\mathrm{EU}}_n^{!k}(\gamma )-{\mathrm{EU}}_n^{?k}(\gamma \left)\right)+\frac{2\overline{\tau }{\gamma }^T(1-\gamma )}{1-{\gamma }^T}$$

Condition iv of Proposition C.1 and condition ii of Definition A.1 imply that, given $h\in \mathrm{hdom}{\nu }^k$ s.t. $\left|h\right|\ge nT$

$$\mathrm{supp}{\pi }_n^{!k}\left(h\right)\subseteq \{{\pi }^k\left(S^k\right(h\left)\right),\perp \}$$

$${\pi }_n^{!!k}({\pi }^k\left(S^k\right(h\left)\right)\mid h)=1$$

Therefore, ${\pi }_n^{!!k}={\pi }_n^{\ast k}$, and we remain with

$$R^{?k}\le (1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\left({\mathrm{EU}}_n^{!!k}\right(\gamma )-{\mathrm{EU}}_n^{!k}(\gamma )+{\mathrm{EU}}_n^{!k}(\gamma )-{\mathrm{EU}}_n^{?k}(\gamma \left)\right)+\frac{2\overline{\tau }{\gamma }^T(1-\gamma )}{1-{\gamma }^T}$$

We have

$$\left|{\mathrm{EU}}_n^{!!k}\right(\gamma )-{\mathrm{EU}}_n^{!k}(\gamma \left)\right|\le \underset{x\sim {\rho }_n^{!k}}{Pr}[\exists m\in [T]:x_{nT+m}\in \perp \overline{O}]$$

Since $Z_{nT}^{!}\left(K\right)\ge \eta$, it follows that

$$\left|{\mathrm{EU}}_n^{!!k}\right(\gamma )-{\mathrm{EU}}_n^{!k}(\gamma \left)\right|\le \frac{1}{\eta }\underset{x\sim {\rho }^{?k}}{Pr}[\exists m\in [T]:x_{nT+m}\in \perp \overline{O}]\le \frac{1}{\eta }\underset{x\sim {\rho }^{?k}}{E}\left[\left|\{m\in [T]\mid x_{nT+m}\in \perp \overline{O}\}\right|\right]$$

$$\sum _{n=0}^{\infty }\left|{\mathrm{EU}}_n^{!!k}\right(\gamma )-{\mathrm{EU}}_n^{!k}(\gamma \left)\right|\le \frac{1}{\eta }\underset{x\sim {\rho }^{?k}}{E}\left[\left|\{n\in N\mid x_n\in \perp \overline{O}\}\right|\right]$$

Using condition i of Proposition C.1, we conclude

$$R^{?k}\le (1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\left({\mathrm{EU}}_n^{!k}\right(\gamma )-{\mathrm{EU}}_n^{?k}(\gamma \left)\right)+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

Define the random variables $\{U_n^{!}:\Omega \to [0,1]{\}}_{n\in N}$ by

$$U_n^{!}:=\frac{1-\gamma }{1-{\gamma }^T}\sum _{m=0}^{T-1}{\gamma }^{m}r\left(A{\Theta }_{:nT+m}^{!}\right)$$

Averaging the previous inequality over $k$, we get

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}\le (1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\underset{}{E}[\underset{}{E}[U_n^{!}\mid J_n^{!}=K,Z_{nT}^{!}]-\underset{}{E}[U_n^{!}\mid Z_{nT}^{!}]]+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}=\sqrt{(1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\underset{}{E}\left[{(\underset{}{E}[U_n^{!}\mid J_n^{!}=K,Z_{nT}^{!}]-\underset{}{E}[U_n^{!}\mid Z_{nT}^{!}])}^2\right]}+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

We apply Proposition C.2 to each term in the sum over $n$.

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}=\sqrt{(1-{\gamma }^T)\sum _{n=0}^{\infty }{\gamma }^{nT}\underset{}{E}\left[\frac{1}{2\eta }\underset{}{I}[K;J_n^{!},U_n^{!}\mid Z_{nT}^{!}]\right]}+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}=\sqrt{\frac{1-{\gamma }^T}{2\eta }\sum _{n=0}^{\infty }{\gamma }^{nT}\underset{}{E}[H(Z_{nT}^{!})-H\left(Z_{(n+1)T}^{!}\right)]}+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}=\sqrt{\frac{1-{\gamma }^T}{2\eta }\ln N}+O(\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

$$\frac{1}{N}\sum _{k=0}^{N-1}{R}^{?k}=O(\sqrt{\frac{1-{\gamma }^T}{\eta }}+\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

Condition ii of Proposition C.1 implies that

$$d_{\text{tv}}(\frac{1}{N}\sum _{k=0}^{N-1}{\overline{\nu }}^k\left[{\sigma }^k\right]\bowtie {\pi }^{\ast },\frac{1}{N}\sum _{k=0}^{N-1}{\overline{\nu }}^k\left[{\sigma }^k\right]\bowtie {\pi }^{?k})\le 2(N-1)\eta$$

Here, the factor of 2 comes from the difference between the equations for $Z_n$ and $Z_n^{!}$ (we can construct and intermediate policy between ${\pi }^{\ast }$ and ${\pi }^{?k}$ and use the triangle inequality for $d_{\text{tv}}$). We conclude

$${\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}\left(\gamma \right)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{\ast }}\left(\gamma \right)=O(\eta +\sqrt{\frac{1-{\gamma }^T}{\eta }}+\frac{1-{\gamma }^T}{{\eta }^2}+\frac{\overline{\tau }(1-\gamma )}{1-{\gamma }^T})$$

Now we set

$$\eta :={\overline{\tau }}^{1/4}(1-\gamma {)}^{1/4}$$

$$T:=\lceil {\overline{\tau }}^{3/4}(1-\gamma {)}^{-1/4}\rceil$$

Without loss of generality, we can assume that $\overline{\tau }(1-\gamma )\ll 1$ (because of the form of the bound we are proving), which implies that $T(1-\gamma )\ll 1$ and $1-{\gamma }^T\approx T(1-\gamma )\approx {\overline{\tau }}^{3/4}(1-\gamma {)}^{3/4}$. We get

$${\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}\left(\gamma \right)-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{\ast }}\left(\gamma \right)=O\left({\overline{\tau }}^{1/4}\right(1-\gamma {)}^{1/4})$$

##Appendix C

The following is a simple special case of what appeared as “Proposition A.2” in the previous essay, where we restrict $\pi$ to be single-valued (the more general case isn’t needed).

#Proposition C.1

Fix an interface $I=(A,O)$, $N\in N$, $ϵ\in (0,\frac{1}{\left|A\right|})$, $\eta \in (0,\frac{1}{N})$. Consider some $\{{\sigma }^k:(A\times O{)}^{\ast }\stackrel{\text{k}}{\to }A{\}}_{k\in \left[N\right]}$. Then, there exist $D:{\overline{A\times O}}^{\ast }\times A\to \overline{A}$ and $\{D^{!k}:{\overline{A\times O}}^{\ast }\times A\to \overline{A}{\}}_{k\in \left[N\right]}$ with the following properties. Given $x\in {(A\times \overline{A\times O})}^{\ast }$, we denote $\underset{–}{x}$ its projection to ${\overline{A\times O}}^{\ast }$. Thus, $\underset{–}{\underset{–}{x}}\in (A\times O{)}^{\ast }$. Given $\mu$ an $I$-environment, $\pi :\mathrm{hdom}\mu \stackrel{\text{k}}{\to }A$, $D^{\prime }:{\overline{A\times O}}^{\ast }\times A\to \overline{A}$ and $k\in \left[N\right]$, we can define $\Xi [\mu ,{\sigma }^k,D^{\prime },\pi ]\in \Delta {(A\times \overline{A\times O})}^{\omega }$ as follows

$$\Xi [\mu ,{\sigma }^k,D^{\prime },\pi ](b,a,o\mid x):=\pi (b\mid \underset{–}{\underset{–}{x}})D^{\prime }(a\mid \underset{–}{x},b)\overline{\mu }\left[{\sigma }^k\right](o\mid \underset{–}{x}a)$$

We require that for every $\pi$, $\mu$ and $k$ as above, the following conditions hold

i. $$\frac{1}{N}\sum _{j=0}^{N-1}\underset{x\sim \Xi [\mu ,{\sigma }^j,D^{!j},\pi ]}{E}\left[\left|\right\{n\in N\mid x_n\in A\times \perp \times \overline{O}\left\}\right|\right]\le \frac{\ln N}{\eta \ln (1+ϵ(1-ϵ{)}^{(1-ϵ)/ϵ})}=O\left(\frac{\ln N}{\eta ϵ}\right)$$

ii. $d_{\text{tv}}(\frac{1}{N}{\sum }_{j=0}^{N-1}\Xi [\mu ,{\sigma }^j,D,\pi ],\frac{1}{N}{\sum }_{j=0}^{N-1}\Xi [\mu ,{\sigma }^j,D^{!j},\pi ])\le (N-1)\eta$

iii. For all $x\in \mathrm{hdom}\overline{\mu }\left[{\sigma }^k\right]$, if $D^{!k}(x,\pi \left(\underset{–}{x}\right))\ne \perp$ then ${\sigma }^k(D^{!k}(x,\pi \left(\underset{–}{x}\right))\mid \underset{–}{x})>0$

iv. For all $x\in \mathrm{hdom}\overline{\mu }\left[{\sigma }^k\right]$, if $D^{!k}(x,\pi \left(\underset{–}{x}\right))\notin \{\pi \left(\underset{–}{x}\right),\perp \}$ then ${\sigma }^k(\pi \left(\underset{–}{x}\right)\mid \underset{–}{x})\le ϵ$

---

The following appeared in the previous essay as “Proposition A.1”.

#Proposition C.2

Consider a probability space $(\Omega ,P\in \Delta \Omega )$, $N\in N$, $R\subseteq [0,1]$ a finite set and random variables $U:\Omega \to R$, $K:\Omega \to \left[N\right]$ and $J:\Omega \to \left[N\right]$. Assume that $K_{\ast }P=J_{\ast }P=\zeta \in \Delta \left[N\right]$ and $\underset{}{I}[K;J]=0$. Then

$$\underset{}{I}[K;J,U]\ge 2\left(\underset{i\in \left[N\right]}{min}\zeta \left(i\right)\right){(\underset{}{E}[U\mid J=K]-\underset{}{E}\left[U\right])}^2$$