% operators that are separated from the operand by a space

% autosize deliminaters

% operators that require brackets

% operators that require parentheses

% Paper specific

Previously we derived a regret bound for DRL which assumed the advisor is "locally sane." Such an advisor can only take actions that don't lose any value in the long term. In particular, if the environment contains a latent catastrophe that manifests with a certain rate (such as the possibility of an UFAI), a locally sane advisor has to take the optimal course of action to mitigate it, since every delay yields a positive probability of the catastrophe manifesting and leading to permanent loss of value. This state of affairs is unsatisfactory, since we would like to have performance guarantees for an AI that can mitigate catastrophes that the human operator cannot mitigate on their own. To address this problem, we introduce a new form of DRL where in every hypothetical environment the set of uncorrupted states is divided into "dangerous" (impending catastrophe) and "safe" (catastrophe was mitigated). The advisor is then only required to be locally sane in safe states, whereas in dangerous states certain "leaking" of long-term value is allowed. We derive a regret bound in this setting as a function of the time discount factor, the expected value of catastrophe mitigation time for the optimal policy, and the "value leak" rate (i.e. essentially the rate of catastrophe occurrence). The form of this regret bound implies that in certain asymptotic regimes, the agent attains near-optimal expected utility (and in particular mitigates the catastrophe with probability close to 1), whereas the advisor on its own fails to mitigate the catastrophe with probability close to 1. %Thus, this formalism can be regarded as a simple model of aligned superintelligence: the agent is aligned since near-optimal utility is achieved despite the presence of corrupted states (which are treated more or less the same as before) and it is superintelligent since its performance is vastly better than the performance of the advisor.

---

Appendix A proves the main theorem. Appendix B contains the proof of an important lemma which is however almost identical to what appeared in the previous essay. Appendix C contains several propositions from the previous essay which we are used in the proof.

##Results

We start by formalising the concepts of a "catastrophe" and "catastrophe mitigation" in the language of MDPs.

#Definition 1

A catastrophe MDP is an MDP $M$ together with a partition of $S_M$ into subsets $S_M:=S_M^F\bigsqcup S_M^D\bigsqcup S_M^C$ (safe, dangerous and corrupt states respectively).

#Definition 2

Fix a catastrophe MDP $M$. Define $A_M^{♯}:S_M\to 2^{A_M}$ by

$$A_M^{♯}\left(s\right):=\{\begin{array}{c}\{a\in A_M\mid \mathrm{supp}T(s,a)\subseteq S_M^F\}\text{if}s\in S_M^F\\ \{a\in A_M\mid \mathrm{supp}T(s,a)\cap S_M^C=\varnothing \}\text{if}s\in S_M^D\\ A_M\text{if}s\in S_M^C\end{array}$$

is called a mitigation policy for $M$ when

i. For any $s\in S_M$, $\mathrm{supp}\pi \left(s\right)\subseteq A_M^{♯}\left(s\right)$.

$\pi$ is called a proper mitigation policy for $M$ when condition i holds and

ii. For any $s\in S_M^D$, ${lim}_{n\to \infty }{T}_{M\pi }^n(S_M^F\mid s)=1$.

#Definition 3

Fix $\overline{\tau }\in (0,\infty )$, a catastrophe MDP $M$ and a proper mitigation policy $\pi$. $\pi$ is said to have expected mitigation time $\overline{\tau }$ when for any $s\in S_M^D$

$$\sum _{n=0}^{\infty }(n+1)(T_{M\pi }^{n+1}(S_M^F\mid s)-T_{M\pi }^n(S_M^F\mid s))=\overline{\tau }$$

---

Next, we introduce the notion of an MDP perturbation. We will use it by considering perturbations of a catastrophe MDP which "eliminate the catastrophe."

#Definition 4

Fix $\delta \in (0,1)$ and consider a catastrophe MDP $M$. An MDP $\tilde{M}$ is said to be a $\delta$-perturbation of $M$ when

i. $S_{\tilde{M}}=S_M$

ii. $A_{\tilde{M}}=A_M$

iii. $R_{\tilde{M}}=R_M$

iv. For any $s\in S_M\setminus S_M^D$ and $a\in A_M$, $T_{\tilde{M}}(s,a)=T_M(s,a)$

v. For any $s\in S_M^D$ and $a\in A_M$, there exists $\zeta \in \Delta S_M$ s.t. $T_M(s,a)=(1-\delta )T_{\tilde{M}}(s,a)+\delta \zeta$.

---

Similarly, we can consider perturbations of a policy.

#Definition 5

Fix $\delta \in (0,1)$ and consider a catastrophe MDP $M$. Given and , $\tilde{\pi }$ is said to be a $\delta$-perturbation of $\pi$ when

i. For any $s\in S_M\setminus S_M^D$, $\tilde{\pi }\left(s\right)=\pi \left(s\right)$.

ii. For any $s\in S_M^D$, there exists $\alpha \in \Delta A$ s.t. $\pi \left(s\right)=(1-\delta )\tilde{\pi }\left(s\right)+\delta \alpha$.

---

We will also need to introduce policy-specific value functions, Q-functions and relatively $k$-optimal actions.

#Definition 6

Fix an MDP $M$ and . We define $V_{M\pi }:S_M\times (0,1)\to [0,1]$ and $Q_{M\pi }:S_M\times A_M\times (0,1)\to [0,1]$ by

$$V_{M\pi }(s,\gamma ):=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\underset{T_{M\pi }^n\left(s\right)}{E}\left[R_M\right]$$

$$Q_{M\pi }(s,a,\gamma ):=(1-\gamma )R_M\left(s\right)+\gamma \underset{t\sim T_M(s,a)}{E}\left[V_{M\pi }\right(t,\gamma \left)\right]$$

For each $k\in N$, we define $V_{M\pi }^k:S_M\to R$, $Q_{M\pi }^k:S_M\times A_M\to R$ and $A_{M\pi }^k:S_M\to 2^{A_M}$ by

$$V_{M\pi }^k\left(s\right):=(-1{)}^k\frac{d^k{V}_{M\pi }(s,\gamma )}{d{\gamma }^k}{|}_{\gamma =1}$$

$$Q_{M\pi }^k(s,a):=(-1{)}^k\frac{d^k{Q}_{M\pi }(s,a,\gamma )}{d{\gamma }^k}{|}_{\gamma =1}$$

$$A_{M\pi }^0\left(s\right):=\{a\in A_M\mid Q_{M\pi }^0(s,a)\ge V_{M\pi }^0(s\left)\right\}$$

$$A_{M\pi }^{k+1}\left(s\right):=\{a\in A_{M\pi }^k(s)\mid Q_{M\pi }^{k+1}(s,a)\ge V_{M\pi }^{k+1}(s)\text{or}\exists j\le k:Q_{M\pi }^j(s,a)>V_{M\pi }^j(s\left)\right\}$$

---

Now we give the new (weaker) condition on the advisor policy. For notational simplicity, we assume the policy is stationary. It is easy to generalize these results to non-stationary advisor policies and to policies that depend on irrelevant additional information (i.e. policies for universes that are realizations of the MDP).

#Definition 7

Given a catastrophe MDP $M$, we denote $M^{♭}$ the MDP defined by

• $S_{M^{♭}}=S_M$

• $A_{M^{♭}}=A_M$

• $T_{M^{♭}}=T_M$

• For any $s\notin S_M^F$, $R_{M^{♭}}\left(s\right)=0$.

• For any $s\in S_M^F$, $R_{M^{♭}}\left(s\right)=\frac{1}{2}+\frac{1}{2}{R}_M\left(s\right)$.

#Definition 8

Fix $ϵ,\delta ,\gamma \in (0,1)$. Consider a catastrophe MDP $M$. A policy is said to be locally $(ϵ,\delta )$-sane for $(M,\gamma )$ when there exists a $\delta$-perturbation $\tilde{M}$ of $M$ with a deterministic proper mitigation policy ${\pi }^{\ast }:S_M\to A_M$ and a $\delta$-perturbation $\tilde{\pi }$ of $\pi$ s.t.

i. For all $s\in S_M$, $V_{M{\pi }^{\ast }}(s,\gamma )=V_M(s,\gamma )$.

ii. $\tilde{\pi }$ is a mitigation policy for $\tilde{M}$.

iii. For any $s\in S_M\setminus S_M^C$: $$\mathrm{supp}\tilde{\pi }\left(s\right)\subseteq A_{{\tilde{M}}^{♭}{\pi }^{\ast }}^0\left(s\right)$$

iv. For any $s\in S_M\setminus S_M^C$: $$\tilde{\pi }\left({\pi }^{\ast }\right(s)\mid s)>ϵ$$

% Alternatively we could allow \pi^* to be stochastic... % and require \tilde{\pi} to be of the form \epsilon \pi^* + (1 - \epsilon) \pi'

Given $\overline{\tau }\in (0,\infty )$, $\pi$ is said to have potential mitigation time $\overline{\tau }$ when ${\pi }^{\ast }$ has it as expected mitigation time.

---

Note that a locally $(ϵ,\delta )$-sane policy still has to be $0$-optimal in $S_M^F$. This requirement seems reasonably realistic, since, roughly speaking, it only means that there is some way to "rearrange the universe" that the agent can achieve, and that would be "endorsed" by the advisor, s.t this rearrangement doesn't destroy substantially much value and s.t. after this rearrangement, there is no "impending catastrophe" that the agent has to prevent and the advisor wouldn't be able to prevent in its place. In particular, this rearrangement may involve creating some subagents inside the environment and destroying the original agent, in which case any policy on $S_M^F$ is "vacuously" optimal (since all actions have no effect).

We can now formulate the main result.

#Theorem 1

Fix an interface $I=(A,O)$, $N\in N$, $ϵ\in (0,1)$ and for each $k\in \left[N\right]$, an MDP $M_k^F$ s.t. $A_{M_k^F}=A$. Now, consider for each $k\in \left[N\right]$, an $I$-universe ${\upsilon }^k=({\mu }^k,r^k)$ which is an $O$-realization of a catastrophe MDP $M^k$ with state function $S^k$ s.t.

i. $S_{M^k}^F=S_{M_k^F}$

ii. For each $s\in S_{M_k^F}$ and $a\in A$, $T_{M^k}(s,a)\mid S_{M_k^F}=T_{M_k^F}(s,a)$.

iii. For each $s\in S_{M_k^F}$, $R_{M^k}\left(s\right)=R_{M_k^F}\left(s\right)$.

iv. Given $k,j\in \left[N\right]$ and $h\in \mathrm{hdom}{\mu }^k\cap \mathrm{hdom}{\mu }^j$, if $S^k\left(h\right)\in S_{M^k}\setminus S_{M^k}^C$ and $S^j\left(h\right)\in S_{M^j}\setminus S_{M^j}^C$, then $r^k\left(h\right)=r^j\left(h\right)$ (this condition means that in uncorrupted states, the reward is observable).

Consider also $\alpha ,\delta \in (0,1)$, $\overline{\tau }\in (0,\infty )$ and ${\sigma }^k$ a locally $(ϵ,\delta )$-sane policy for $(M^k,1-\alpha )$. Assume ${\sigma }^k$ has potential mitigation time $\overline{\tau }$. Then, there exists an $\overline{I}$-policy ${\pi }^{\ast }$ s.t. for any $k\in \left[N\right]$

$${\mathrm{EU}}_{{\upsilon }^k}^{\ast }(1-\alpha )-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{\ast }}(1-\alpha )=O(max(\frac{\delta }{\alpha },1)\cdot (\overline{\tau }\alpha {)}^{1/4}+\overline{\tau }\delta )$$

Here, ${\sigma }^k{S}^k$ is the $I$-policy defined by ${\sigma }^k{S}^k\left(h\right):={\sigma }^k\left(S^k\right(h\left)\right)$. $ϵ$ and the $M_k^F$ are regarded as fixed and we don't explicitly examine their effect on regret, whereas $\alpha$, $\delta$, $\overline{\tau }$ and the $M^k$ are regarded as variable with the asymptotics $\alpha ,\delta \to 0$, $\overline{\tau }\to \infty$.

In most interesting cases, $\delta \gg \alpha$ (i.e. the "mean time between catastrophes" is much shorter than a discount horizon) and $\overline{\tau }\alpha \ll 1$ (i.e. the expected mitigation time is much shorter than the discount horizon), which allows simplifying the above to

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

---

We give a simple example.

#Example 1

Let $A=\{0,1,\ast \}$, $O=\{0,1\}$. For any $n\in N$ and $k\in \left[N\right]$, we fix some $w_n^k\in \{0,1{\}}^n$ and define the catastrophe MDP $M_n^k$ by

• $S_{M_n^k}^D=\{0,1{\}}^{\le n}$, $S_{M_n^k}^F=\{\perp ,\top \}$, $S_{M_n^k}^C=\varnothing$ (adding corrupted states is an easy exercise).

• If $s\in \{0,1{\}}^{<n}$ and $a\in \{0,1\}$ then

$$T_{M_n^k}(sa\mid s,a)=1-\delta$$

$$T_{M_n^k}(\perp \mid s,a)=\delta$$

$$T_{M_n^k}(s\mid sa,\ast )=1-\delta$$

$$T_{M_n^k}(\perp \mid sa,\ast )=\delta$$

• If $a\in 0,1$ then

$$T_{M_n^k}(\top \mid w_n^k,a)=1$$

• If $s\in \{0,1{\}}^n\setminus w_n^k$ and $a\in 0,1$ then

$$T_{M_n^k}(\perp \mid s,a)=1$$

• If $s\in \{\perp ,\top \}$ and $a\in A$ then

$$T_{M_n^k}(s\mid s,a)=1$$

• $R_{M_n^k}\left(\perp \right)=0$, if $s\in S_{M_n^k}\setminus \perp$ then $R_{M_n^k}\left(s\right)=1$.

• $S_n^k\left({\lambda }_{A\times O}\right)={\lambda }_{\{0,1\}}$ and $S_n^k\left(hao\right)=\perp$ iff $o=0$ (this defines a unique $S_n^k$).

• If $s\in \{0,1{\}}^{<n}\cup \{\perp ,\top \}$ then ${\sigma }_n^k(a\mid s)=\frac{1}{3}$ for any $a\in A$.

• ${\sigma }_n^k(0\mid w_n^k)=ϵ$, ${\sigma }_n^k(\ast \mid w_n^k)=1-ϵ$.

• If $s\in \{0,1{\}}^n\setminus w_n^k$ then ${\sigma }_n^k(0\mid s)=\delta$, ${\sigma }_n^k(\ast \mid s)=1-\delta$.

We have $\overline{\tau }=n$. Consider the asymptotic regime $n\to \infty$, ${\alpha }_n=\Theta \left(n^{-6}\right)$, ${\delta }_n=\Theta \left(n^{-5}\right)$. According to Theorem 1, we get

$${\mathrm{EU}}_{{\upsilon }_n^k}^{\ast }(1-{\alpha }_n)-{\mathrm{EU}}_{{\overline{\upsilon }}_n^k\left[{\sigma }_n^k\right]}^{{\pi }_n^{\ast }}(1-{\alpha }_n)=O(n^{-5}\cdot n^{1/4}\cdot {\left(n^{-6}\right)}^{-3/4})=O\left(n^{-1/4}\right)=O\left({\alpha }_n^{1/24}\right)$$

The probability of a catastrophe (i.e. ending up in state $\perp$) for the optimal policy for a given $k$ is $O\left(\overline{\tau }\delta \right)=O\left(n^{-4}\right)$. Therefore, the probability of a catastrophe for policy ${\pi }_n^{\ast }$ is $O(n^{-4}+n^{-1/4})=O\left(n^{-1/4}\right)$. On the other hand, it is easy to see that the policy ${\sigma }_n^k$ has a probability of catastrophe $1-o\left(1\right)$ (and in particular regret $\Omega \left(1\right)$): it spends $\Omega \left(2^n\right)$ time "exploring" $\{0,1{\}}^{\le n}$ with a probability $\delta =\Theta \left(n^{-5}\right)$ of a catastrophe on every step.

Note that this example can be interpreted as a version of Christiano's approval-directed agent, if we regard the state $s\in \{0,1{\}}^i$ as a "plan of action" that the advisor may either approve or not. But in this formalism, it is a special case of consequentialist reasoning.

---

Theorem 1 speaks of a finite set of environments, but as before (see Proposition 1 here and Corollary 3 here), there is a "structural" equivalent, i.e. we can use it to produce corollaries about Bayesian agents with priors over a countable set of environments. The difference is, in this case we consider asymptotic regimes in which the environment is also variable, so the probability weight of the environment in the prior will affect the regret bound. We leave out the details for now.

##Appendix A

We start by deriving a more general and more precise version of the non-catastrophic regret bound, in which the optimal policy is replaced by an arbitrary "reference policy" (later it will be related to the mitigation policy) and the dependence on the MDPs is expressed via a bound on the derivative of $V$ by $\gamma$.

#Definition A.1

Fix $ϵ\in (0,1)$. Consider an MDP $M$ and policies $\pi :S_M\to A_M$, . $\sigma$ is called $ϵ$-sane relatively to $\pi$ when for any $s\in S_M$

i. $\mathrm{supp}\sigma \left(s\right)\subseteq A_{M\pi }^0$

ii. $\sigma \left(\pi \right(s)\mid s)>ϵ$

#Lemma A.1

Fix an interface $I=(A,O)$, $N\in N$ and $ϵ\in (0,1)$. Now, consider for each $k\in \left[N\right]$, an $I$-universe ${\upsilon }^k=({\mu }^k,r)$ which is an $O$-realization of an MDP $M_k$ with state function $S^k$ and policies ${\pi }^k:S_{M^k}\to A$, . Consider also $\alpha \in (0,1)$, $\overline{\tau }\in (0,\infty )$ and assume that

i. ${\sigma }^k$ is $ϵ$-sane relatively to ${\pi }^k$.

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

Then, there exists an $\overline{I}$-policy ${\pi }^{\ast }$ s.t. for any $k\in \left[N\right]$

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

The $O$-notation refers to the asymptotics where $ϵ$ is fixed (so we don't explicitly examine its effect on regret) whereas $\alpha$, $\overline{\tau }$ and the $M_k$ are variable and $\alpha \to 0$, $\overline{\tau }\to \infty$.

---

The proof of Lemma A.1 is almost identical to the proof the main theorem for "non-catastrophic" DRL up to minor modifications needed to pass from absolute to relative regret, and tracking the contribution of the derivative of $V_{M^k{\pi }^k}$. We give it in Appendix B.

We will not apply Lemma A.1 directly the the universes of Theorem 1. Instead, we will define new universes using the following constructions.

#Definition A.2

Consider $M$ a catastrophe MDP. We define the catastrophe MDP $M^D$ as follows.

• $S_{M^D}^F:=S_M^F\bigsqcup \left\{\perp \right\}$, $S_{M^D}^D:=S_M^D$, $S_{M^D}^C:=\varnothing$.

• $A_{M^D}=A_M$

• For any $s,t\in S_M^D$:

$$T_{M^D}(t\mid s)=T_M(t\mid s)$$

$$T_{M^D}(\perp \mid s)=T_M(S_M^C\mid s)$$

$$T_{M^D}(\perp \mid \perp )=1$$

• For any $s\in S_M^D\cup S_M^F$, $t\in S_M^F$:

$$T_{M^D}(t\mid s)=T_M(t\mid s)$$

• For any $s\in S_M^F$:

$$T_{M^D}(\perp \mid s)=T_M(S_M^C\cup S_M^D\mid s)$$

• For any $s\in S_M^D$, $R_{M^D}\left(s\right)=\frac{1}{2}{R}_M\left(s\right)$.

• For any $s\in S_M^F$, $R_{M^D}\left(s\right)=1$.

• $R_{M^D}\left(\perp \right)=0$

Now, consider an interface $I=(A,O)$ and a $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$. Denote $O^{\prime }:=O\times \{R,I\}$, $O^{\star }:=O\times \{R,I,\perp \}$ and $I^{\star }:=(A,O^{\star })$. Denote $\beta :O^{\prime }\to O$ the projection mapping and ${\beta }^{\ast }:{(A\times O^{\prime })}^{\ast }\to {(A\times O)}^{\ast }$ corresponding. We define the $I^{\star }$-universe ${\upsilon }^D=({\mu }^D,r^{\star })$ and the function $S^{\star }:{(A\times O^{\star })}^{\ast }\to S_{M^D}$ as follows

$${\mu }^D(oR\mid ha):=\{\begin{array}{c}\mu (o\mid {\beta }^{\ast }(h\left)a\right)\text{if}h\in {(A\times O^{\prime })}^{\ast }\text{and}S\left({\beta }^{\ast }\right(h\left)\right),S\left({\beta }^{\ast }\right(h\left)ao\right)\in S_M^D\\ 0\text{otherwise}\end{array}$$

$${\mu }^D(oI\mid ha):=\{\begin{array}{c}\mu (o\mid {\beta }^{\ast }(h\left)a\right)\text{if}h\in {(A\times O^{\prime })}^{\ast }\text{and}S\left({\beta }^{\ast }\right(h\left)ao\right)\in S_M^F\\ 0\text{otherwise}\end{array}$$

$${\mu }^D(o\perp \mid ha):=\frac{1}{\left|O\right|}(1-\sum _{o\in O}\left({\mu }^D\right(oR\mid ha)+{\mu }^D(oI\mid ha\left)\right))$$

$$r^{\star }\left(h\right):=\{\begin{array}{c}\frac{1}{2}r\left(\lambda \right)\text{if}h=\lambda \\ \frac{1}{2}r\left({\beta }^{\ast }\right(h\left)\right)\text{if}h\in {(A\times O^{\prime })}^{\ast },\left|h\right|>0\text{and}{h}_{:\left|h\right|-1}\in AOR\\ 1\text{if}h\in {(A\times O^{\prime })}^{\ast },\left|h\right|>0\text{and}{h}_{:\left|h\right|-1}\in AOI\\ 0\text{if}h\notin {(A\times O^{\prime })}^{\ast }\end{array}$$

$$S^{\star }\left(h\right):=\{\begin{array}{c}S\left({\beta }^{\ast }\right(h\left)\right)\text{if}h\in {(A\times O^{\prime })}^{\ast }\\ \perp \text{otherwise}\end{array}$$

It is easy to see that ${\upsilon }^D$ is an $O^{\star }$-realization of $M^D$ with state function $S^{\star }$.

#Definition A.3

Consider $M$ a catastrophe MDP. We define the catastrophe MDP $M^E$ as follows.

• $S_{M^E}^F:=S_M^F\bigsqcup \left\{\perp \right\}$, $S_{M^E}^D:=S_M^D$, $S_{M^E}^C:=\varnothing$.

• $A_{M^E}=A_M$

• $T_{M^E}=T_{M^D}$

• For any $s\in S_M^D\cup S_M^F$, $R_{M^E}\left(s\right)=\frac{1}{2}{R}_M\left(s\right)$.

• $R_{M^E}\left(\perp \right)=0$

Now, consider an interface $I=(A,O)$ and a $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$. We define the $I^{\star }$-universe ${\upsilon }^E=({\mu }^E,r^{\star })$ as follows

$${\mu }^E(oR\mid ha):=\{\begin{array}{c}\mu (o\mid {\beta }^{\ast }(h\left)a\right)\text{if}h\in {(A\times O^{\prime })}^{\ast }\text{and}S\left({\beta }^{\ast }\right(h\left)\right),S\left({\beta }^{\ast }\right(h\left)ao\right)\in S_M^D\\ \mu (o\mid {\beta }^{\ast }(h\left)a\right)\text{if}h\in {(A\times O^{\prime })}^{\ast }\text{and}S\left({\beta }^{\ast }\right(h\left)ao\right)\in S_M^F\\ 0\text{otherwise}\end{array}$$

$${\mu }^E(oI\mid ha):=0$$

$${\mu }^E(\perp \mid ha):=1-\sum _{o\in O}{\mu }^E(oR\mid ha)$$

It is easy to see that ${\upsilon }^E$ is an $O^{\star }$-realization of $M^E$ with state function $S^{\star }$.

Given $h=a_0{o}_0{a}_1{o}_1\dots a_{n-1}{o}_{n-1}\in {(A\times O)}^n$, we will use the notation

$$R^{\ast }h:=a_0{o}_{0}R{a}_1{o}_{1}R\dots a_{n-1}{o}_{n-1}R\in {(A\times O^{\prime })}^n$$

Given an $I^{\star }$-policy $\pi$, the $I$-policy $\pi R^{\ast }$ is defined by $\pi R^{\ast }\left(h\right):=\pi \left(R^{\ast }h\right)$.

---

In order to utilize condition iii of Definition 8, we need to establish the following relation between $M^{♭}$ and $M^D$, $M^E$.

#Proposition A.2

Consider $M$ a catastrophe MDP, some $s\in S_M\setminus S_M^C$ and ${\pi }^{\ast }$ a proper mitigation policy. Then

$$A_{M^{♭}{\pi }^{\ast }}^0\left(s\right)\cap A_M^{♯}\left(s\right)\subseteq A_{M^D{\pi }^{\ast }}^0\left(s\right)$$

$$A_{M^{♭}{\pi }^{\ast }}^0\left(s\right)\cap A_M^{♯}\left(s\right)\subseteq A_{M^E{\pi }^{\ast }}^0\left(s\right)$$

---

For the purpose of the proof, the following notation will be convenient

#Definition A.4

Consider $S$ a finite set and some . We define by

$$T^{\infty }:=\underset{n\to \infty }{lim}\frac{1}{n}\sum _{m=0}^{n-1}{T}^m$$

As well known, the limit above always exists.

#Proof of Proposition A.2

Consider any $s\in S\setminus S_M^C$ and $a\in A_{M^{♭}{\pi }^{\ast }}^0\left(s\right)\cap A_M^{♯}\left(s\right)$. Since $a\in A_{M^{♭}{\pi }^{\ast }}^0\left(s\right)$, we have

$$\underset{(T_{M^{♭}{\pi }^{\ast }}^{\infty }\circ T_{M^{♭}})(s,a)}{E}\left[R_{M^{♭}}\right]=\underset{T_{M^{♭}}(s,a)}{E}\left[V_{M^{♭}{\pi }^{\ast }}^0\right]=Q_{M^{♭}{\pi }^{\ast }}^0(s,a)\ge V_{M^{♭}{\pi }^{\ast }}^0\left(s\right)=\underset{T_{M^{♭}{\pi }^{\ast }}^{\infty }\left(s\right)}{E}\left[R_{M^{♭}}\right]$$

Let $N$ be either of $M^D$ and $M^E$. Since $a\in A_M^{♯}\left(s\right)$, we get

$$\underset{(T_{M^{♭}{\pi }^{\ast }}^{\infty }\circ T_N)(s,a)}{E}\left[R_{M^{♭}}\right]\ge \underset{T_{M^{♭}{\pi }^{\ast }}^{\infty }\left(s\right)}{E}\left[R_{M^{♭}}\right]$$

Since ${\pi }^{\ast }$ is a mitigation policy, we get

$$\underset{(T_{N{\pi }^{\ast }}^{\infty }\circ T_N)(s,a)}{E}\left[R_{M^{♭}}\right]\ge \underset{T_{N{\pi }^{\ast }}^{\infty }\left(s\right)}{E}\left[R_{M^{♭}}\right]$$

Finally, since ${\pi }^{\ast }$ is proper, $\mathrm{supp}{T}_{N{\pi }^{\ast }}^{\infty }\left(s\right)\subseteq S_M^F$ and $\mathrm{supp}(T_{N{\pi }^{\ast }}^{\infty }\circ T_N)(s,a)\subseteq S_M^F$. We conclude

$$Q_{N{\pi }^{\ast }}^0(s,a)=\underset{(T_{N{\pi }^{\ast }}^{\infty }\circ T_N)(s,a)}{E}\left[R_N\right]\ge \underset{T_{N{\pi }^{\ast }}^{\infty }\left(s\right)}{E}\left[R_N\right]=V_{N{\pi }^{\ast }}^0\left(s\right)$$

---

Now we will establish a bound on the derivative of $V$ by $\gamma$ in terms of expected mitigation time, in order to demonstrate condition ii of Lemma A.1.

#Proposition A.3

Fix $\overline{\tau },{\overline{\tau }}_1^F\in (0,\infty )$. Consider a catastrophe MDP $M$ and a proper mitigation policy with expected mitigation time $\overline{\tau }$. Assume than for any $s\in S_M^F$ and $\gamma \in (0,1)$

$$\left|\frac{d{V}_{M\pi }(s,\gamma )}{d\gamma }\right|\le {\overline{\tau }}_1^F$$

Then, for any $s\in S_M\setminus S_M^C$ and $\gamma \in [0,1]$

$$\left|\frac{d{V}_{M\pi }(s,\gamma )}{d\gamma }\right|\le 3{\overline{\tau }}_1+{\overline{\tau }}_1^F$$

---

Note that, since $V_{M\pi }(s,\gamma )$ is a rational function of $\gamma$ with no poles on the interval $[0,1]$, some finite ${\overline{\tau }}^F$ always exists. Note also that Proposition A.3 is really about Markov chains rather than MDPs, but we don't make it explicit to avoid introducing more notation.

#Proof of Proposition A.3

Let ${\mu }_{M\pi s}\in \Delta S_M^{\omega }$ be the Markov chain with transition matrix $T_{M\pi }$ and initial state $s$. For any $\gamma \in (0,1$), we have

$$V_{M\pi }(s,\gamma )=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\right(1-\gamma \left)\sum _{n=0}^{\infty }{\gamma }^n{R}_M\left(x_n\right)\right]$$

Given $x\in S_M^{\omega }$, we define $\tau \left(x\right)\in N\bigsqcup \left\{\infty \right\}$ by

$$\tau \left(x\right)=min\{n\in N\mid x_n\in S_M^F\}$$

It is easy to see that $V_{M\pi }(s,\gamma )$ can be rewritten as

$$V_{M\pi }(s,\gamma )=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\right(1-\gamma \left)(\sum _{n=0}^{\tau \left(x\right)-1}{\gamma }^n{R}_M(x_n)+\frac{{\gamma }^{\tau \left(x\right)}}{1-\gamma }{V}_{M\pi }(x_{\tau \left(x\right)},\gamma ))\right]$$

The expression above is well defined because $\pi$ is a proper mitigation policy and therefore $\tau \left(x\right)$ is finite with probability 1.

$$V_{M\pi }(s,\gamma )=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\right(1-\gamma )\sum _{n=0}^{\tau \left(x\right)-1}{\gamma }^n{R}_M(x_n)+{\gamma }^{\tau \left(x\right)}{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )]$$

Let us decompose $V_{M\pi }(s,\gamma )$ as $V_{M\pi }^D(s,\gamma )+V_{M\pi }^F(s,\gamma )$ defined as follows

$$V_{M\pi }^D(s,\gamma ):=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\right(1-\gamma \left)\sum _{n=0}^{\tau \left(x\right)-1}{\gamma }^n{R}_M(x_n)\right]$$

$$V_{M\pi }^F(s,\gamma ):=\underset{x\sim {\mu }_{M\pi s}}{E}\left[{\gamma }^{\tau \left(x\right)}{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )\right]$$

We have

$$\frac{d{V}_{M\pi }^D(s,\gamma )}{d\gamma }=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\sum _{n=0}^{\tau \left(x\right)-1}(-{\gamma }^n+(1-\gamma )\cdot n{\gamma }^{n-1})R_M(x_n)\right]$$

$$\left|\frac{d{V}_{M\pi }^D(s,\gamma )}{d\gamma }\right|\le \underset{x\sim {\mu }_{M\pi s}}{E}\left[\tau \right(x)+(1-\gamma \left)\sum _{n=0}^{\tau \left(x\right)-1}n{\gamma }^{n-1}{R}_M(x_n)\right]$$

The second term can be regarded as a weighted average (since $1-\gamma ={\sum }_{n=0}^{\infty }{\gamma }^n$), where the maximal term in the average is at most $\tau \left(x\right)-1$, hence

$$\left|\frac{d{V}_{M\pi }^D(s,\gamma )}{d\gamma }\right|\le 2{\overline{\tau }}_1$$

Also, we have

$$\frac{d{V}_{M\pi }^F(s,\gamma )}{d\gamma }=\underset{x\sim {\mu }_{M\pi s}}{E}\left[\tau \right(x){\gamma }^{\tau \left(x\right)-1}{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )+{\gamma }^{\tau \left(x\right)}\frac{d{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )}{d\gamma }]$$

$$\left|\frac{d{V}_{M\pi }^F(s,\gamma )}{d\gamma }\right|\le \underset{x\sim {\mu }_{M\pi s}}{E}\left[\tau \right(x)+\left|\frac{d{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )}{d\gamma }\right|]={\overline{\tau }}_1+\underset{x\sim {\mu }_{M\pi s}}{E}\left[\left|\frac{d{V}_{M\pi }(x_{\tau \left(x\right)},\gamma )}{d\gamma }\right|\right]\le {\overline{\tau }}_1+{\overline{\tau }}_1^F$$

$$\left|\frac{d{V}_{M\pi }(s,\gamma )}{d\gamma }\right|\le \left|\frac{d{V}_{M\pi }^D(s,\gamma )}{d\gamma }\right|+\left|\frac{d{V}_{M\pi }^F(s,\gamma )}{d\gamma }\right|\le 3{\overline{\tau }}_1+{\overline{\tau }}_1^F$$

\Comment{$$\left|\frac{d{V}_{M\pi }^F(s,\gamma )}{d\gamma }{|}_{\gamma =1}\right|\le {\overline{\tau }}_1+\underset{x\sim {\mu }_{M\pi s}}{E}\left[\left|V_{M\pi }^1\left(x_{\tau \left(x\right)}\right)\right|\right]\le {\overline{\tau }}_1+{\overline{\tau }}_1^F$$

We conclude

$$\left|V_{M\pi }^1\right(s\left)\right|\le \left|\frac{d{V}_{M\pi }^D(s,\gamma )}{d\gamma }{|}_{\gamma =1}\right|+\left|\frac{d{V}_{M\pi }^F(s,\gamma )}{d\gamma }{|}_{\gamma =1}\right|\le 3{\overline{\tau }}_1+{\overline{\tau }}_1^F$$}

---

To transform the relative regret bounds for "auxiliary" universes obtained from Lemma A.1 to regret bounds for the original universes, we will need the following.

#Definition A.5

Fix $\delta \in (0,1)$ and a universe $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$. Let $\tilde{M}$ be a $\delta$-perturbation of $M$. An environment $\tilde{\mu }$ is said to be a $\delta$-lift of $\tilde{M}$ to $\mu$ when

i. $(\tilde{\mu },r)$ is an $O$-realization of $\tilde{M}$ with state function $S$.

ii. $\mathrm{hdom}\tilde{\mu }\subseteq \mathrm{hdom}\mu$

iii. For any $h\in \mathrm{hdom}\tilde{\mu }$ and $a\in A$, if $S\left(h\right)\in S_M\setminus S_M^D$ then $\mu \left(ha\right)=\tilde{\mu }\left(ha\right)$.

iv. For any $h\in \mathrm{hdom}\tilde{\mu }$ and $a\in A$, if $S\left(h\right)\in S_M^D$ then there exists $\zeta \in \Delta O$ s.t. $$\mu \left(ha\right)=(1-\delta )\tilde{\mu }\left(ha\right)+\delta \zeta$$

It is easy to see that such a lift always exists, for example we can take:

$$\tilde{\mu }(o\mid ha):=\frac{T_{\tilde{M}}\left(S\right(hao)\mid S(h),a)}{T_M\left(S\right(hao)\mid S(h),a)}\mu (o\mid ha)$$

#Proposition A.4

Consider $\gamma ,\delta \in (0,1)$ s.t $\delta \ge 1-\gamma$ and $\overline{\tau }\in (0,\infty )$. Let $\upsilon =(\mu ,r)$ be a universe which is an $O$-realization of a catastrophe MDP $M$ with state function $S$. Suppose that ${\pi }^{\ast }$ is a mitigation policy for $M$ that has expected mitigation time $\overline{\tau }$. Consider some $I^{\star }$-policy $\pi$. Suppose that $\tilde{M}$ is a $\delta$-perturbation of $M$ and $\tilde{\mu }$ is a $\delta$-lift of $\tilde{M}$ to $\mu$. Denote $\tilde{\upsilon }:=(\tilde{\mu },r)$. Then, there is some $C\in (0,\infty )$ that depends on nothing s.t

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{\pi }\left(\gamma \right)+C\delta (\overline{\tau }+\frac{max\left({\mathrm{EU}}_{{\tilde{\upsilon }}^D}^{{\pi }^{\ast }{S}^{\star }}\right(\gamma )-{\mathrm{EU}}_{{\tilde{\upsilon }}^D}^{\pi }(\gamma ),0)}{1-\gamma })$$

---

In order to prove Proposition A.4, we need a relative regret bound for $M$ derived from a relative regret bound for $M^E$.

#Proposition A.5

Fix an interface $I$ and an $I$-universe $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$ s.t. $S\left(\lambda \right)\notin S_M^C$. Suppose that ${\pi }^{\ast }$ is a mitigation policy for $M$. Let $\pi$ be any $I^{\star }$-policy. Then, for any $\gamma \in (0,1)$

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\upsilon }^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\upsilon }^E}^{\pi }\left(\gamma \right)$$

#Proof of Proposition A.5

${\pi }^{\ast }$ is a mitigation policy, therefore for any $s\in S_M\setminus S_M^C$, $T_{M^E{\pi }^{\ast }}\left(s\right)=T_{M{\pi }^{\ast }}\left(s\right)$. It follows that

$${\mathrm{EU}}_{{\upsilon }^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)=\frac{1}{2}{\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\left(\gamma \right)$$

Also, it is easy to see from the definition of $T_{M^E}$ and $r^{\star }$ that

$${\mathrm{EU}}_{{\upsilon }^E}^{\pi }\left(\gamma \right)\le \frac{1}{2}{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}\left(\gamma \right)$$

Indeed, any discrepancy between the behavior of $M^E$ and $M$ involves transition to the state $\perp$ which yields 0 reward forever. Subtracting these inequalities, we get the desired result.

---

Another observation we need to prove Proposition A.4 is a bound on the effect of $\delta$-perturbations in terms of mitigation time.

#Proposition A.6

Consider $\gamma ,\delta \in (0,1)$, a universe $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$, and some . Assume that for any $h\in S^{-1}\left(S_M^F\right)$ and $a\in \mathrm{supp}\pi \left(h\right)$, $T_M(S_M^F\mid s,a)=1$. Let $\tilde{M}$ be a $\delta$-perturbation of $M$ and $\tilde{\mu }$ a $\delta$-lift of $\tilde{M}$ to $\mu$. Then,

$$d_{\text{tv}}(\mu \bowtie \pi ,\tilde{\mu }\bowtie \pi )\le 2(1-\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_S\left(x\right)}\right])$$

#Proof of Proposition A.6

It is straightforward to construct a probability space $(\Omega ,P)$, $X:\Omega \to (A\times O{)}^{\omega }$ measurable and $\{C_n\subseteq \Omega {\}}_{n\in N}$ measurable s.t.

i. $h_{\ast }\left(P\right)=\mu \bowtie \pi$

ii. For any $n\in N$ and $h\in (A\times O{)}^n$ s.t. $S\left(h\right)\in S_M^D$:

$$\underset{}{\mathrm{Pr}}[C_n\mid X_{:n}=h]=\delta$$

iii. For any $n\in N$ and $h\in (A\times O{)}^n$ s.t. $S\left(h\right)\in S_M\setminus S_M^D$:

$$\underset{}{\mathrm{Pr}}[C_n\mid X_{:n}=h]=0$$

iv. For any $n\in N$, $h\in (A\times O{)}^n$ and $h^{\prime }\in (A\times O{)}^{n+1}$:

$$\underset{}{\mathrm{Pr}}[X_{:n+1}=h^{\prime }\mid X_{:n}=h\text{and not}{C}_n]=\underset{x\sim \tilde{\mu }\bowtie \pi }{\mathrm{Pr}}[x_{:n+1}=h^{\prime }\mid x_{:n}=h]$$

Denote $D:={\cap }_{n=0}^{\infty }\Omega \setminus C_n$. We have

$$P\left(D\right)=\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_S\left(x\right)}\right]$$

$$d_{\text{tv}}(P,P\mid D)\le 1-P\left(D\right)$$

$$d_{\text{tv}}(\mu \bowtie \pi ,h_{\ast }(P\mid D))\le 1-P\left(D\right)$$

Also, it is easy to see that for any $A\subseteq (A\times O{)}^{\omega }$ measurable

$$h_{\ast }(P\mid D)\left(A\right)=\frac{\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_S\left(x\right)}{\chi }_A\right]}{P\left(D\right)}$$

It follows that

$$d_{\text{tv}}(h_{\ast }(P\mid D),\tilde{\mu }\bowtie \pi )=\frac{1}{2}\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[|\frac{{(1-\delta )}^{{\tau }_S\left(x\right)}}{P\left(D\right)}-1|\right]$$

$$d_{\text{tv}}(h_{\ast }(P\mid D),\tilde{\mu }\bowtie \pi )=\frac{1}{2P\left(D\right)}\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[|{(1-\delta )}^{{\tau }_S\left(x\right)}-P(D\left)\right|\right]$$

Using the fact that ${(1-\delta )}^{{\tau }_S\left(x\right)}\in [0,1]$ and the convexity of the function $|t-P(D\left)\right|$

$$d_{\text{tv}}(h_{\ast }(P\mid D),\tilde{\mu }\bowtie \pi )\le \frac{1}{2P\left(D\right)}\underset{x\sim \tilde{\mu }\bowtie \pi }{E}[{(1-2\delta )}^{{\tau }_S\left(x\right)}(1-P(D\left)\right)+(1-{(1-\delta )}^{{\tau }_S\left(x\right)})P(D\left)\right]$$

$$d_{\text{tv}}(h_{\ast }(P\mid D),\tilde{\mu }\bowtie \pi )\le \frac{1}{2P\left(D\right)}\left(P\right(D)(1-P(D\left)\right)+(1-P(D\left)\right)P(D\left)\right)=1-P\left(D\right)$$

Using the triangle inequality, we conclude

$$d_{\text{tv}}(\mu \bowtie \pi ,\tilde{\mu }\bowtie \pi )\le d_{\text{tv}}(\mu \bowtie \pi ,h_{\ast }(P\mid D))+d_{\text{tv}}(h_{\ast }(P\mid D),\tilde{\mu }\bowtie \pi )=2(1-\underset{x\sim \tilde{\mu }\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_S\left(x\right)}\right])$$

---

As a final ingredient towards the proof of Proposition A.4, we will need to use the relative regret bound for $M^D$ to get a certain statistical bound on mitigation time.

#Definition A.6

Let $\mu$ be any environment. We define the closed set ${\mathrm{hdom}}^{\omega }\mu \subseteq (A\times O{)}^{\omega }$ by

$${\mathrm{hdom}}^{\omega }\mu :=\{x\in (A\times O{)}^{\omega }\mid \forall n\in N:x_{:n}\in \mathrm{hdom}\mu \}$$

Consider a universe $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$. We define the measurable function ${\tau }_S:{\mathrm{hdom}}^{\omega }\mu \to N\bigsqcup \left\{\infty \right\}$ as follows

$${\tau }_S\left(x\right):=min\{n\in N\mid S\left(x_{:n}\right)\in S_M^F\}$$

#Proposition A.7

Fix an interface $I$ and an $I$-universe $\upsilon =(\mu ,r)$ which is an $O$-realization of a catastrophe MDP $M$ with state function $S$ s.t. $S\left(\lambda \right)\in S_M^D$. Suppose that ${\pi }^{\ast }$ is a mitigation policy for $M$ that has the expected mitigation time $\overline{\tau }\in (0,\infty )$. Let $\pi$ be any $I^{\star }$-policy. Then, there is $C\in (0,\infty )$ that depends on nothing s.t. for any $\gamma ,\delta \in (0,1)$, if $\delta \ge 1-\gamma$ then

$$\underset{{\mu }^D\bowtie \pi }{E}\left[\right(1-\delta {)}^{{\tau }_{S^{\star }}}]\ge 1-C\delta (\overline{\tau }+\frac{max\left({\mathrm{EU}}_{{\upsilon }^D}^{{\pi }^{\ast }{S}^{\star }}\right(\gamma )-{\mathrm{EU}}_{{\upsilon }^D}^{\pi }(\gamma ),0)}{1-\gamma })$$

#Proof of Proposition A.7

For any $x\in \mathrm{hdom}{\mu }^D$, we have

$$U_{\gamma }^{r^{\star }}\left(x\right)\le (1-\gamma )(\frac{1}{2}\sum _{n=0}^{{\tau }_{S^{\star }}\left(x\right)-1}{\gamma }^n+\sum _{n={\tau }_{S^{\star }}\left(x\right)}^{\infty }{\gamma }^n)=(1-\gamma )(\frac{1}{2}\cdot \frac{1-{\gamma }^{{\tau }_{S^{\star }}\left(x\right)}}{1-\gamma }+\frac{{\gamma }^{{\tau }_{S^{\star }}\left(x\right)}}{1-\gamma })=\frac{1}{2}+\frac{1}{2}{\gamma }^{{\tau }_{S^{\star }}\left(x\right)}$$

It follows that

$${\mathrm{EU}}_{{\upsilon }^D}^{\pi }\left(\gamma \right)\le \frac{1}{2}+\frac{1}{2}\underset{={\mu }^D\bowtie \pi }{E}\left[{\gamma }^{{\tau }_{S^{\star }}}\right]$$

If $x\in {\mathrm{hdom}}^{\omega }{\mu }^D$ is s.t. for all $n\in N$, $S^{\star }\left(x_{:n}\right)\ne \perp$, then

$$U_{\gamma }^{r^{\star }}\left(x\right)\ge (1-\gamma )\sum _{n={\tau }_{S^{\star }}\left(x\right)}^{\infty }{\gamma }^n={\gamma }^{{\tau }_{S^{\star }}\left(x\right)}$$

Since ${\pi }^{\ast }$ is a mitigation policy, it follows that

$${\mathrm{EU}}_{{\upsilon }^D}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)\ge \underset{{\mu }^D\bowtie {\pi }^{\ast }{S}^{\star }}{E}\left[{\gamma }^{{\tau }_{S^{\star }}}\right]\ge {\gamma }^{\overline{\tau }}$$

Subtracting the two inequalities, we get

$${\mathrm{EU}}_{{\upsilon }^D}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\upsilon }^D}^{\pi }\left(\gamma \right)\ge {\gamma }^{\overline{\tau }}-\frac{1}{2}-\frac{1}{2}\underset{{\mu }^D\bowtie \pi }{E}\left[{\gamma }^{{\tau }_{S^{\star }}}\right]$$

$$\underset{{\mu }^D\bowtie \pi }{E}\left[{\gamma }^{{\tau }_{S^{\star }}}\right]\ge 2{\gamma }^{\overline{\tau }}-2\left({\mathrm{EU}}_{{\upsilon }^D}^{{\pi }^{\ast }{S}^{\star }}\right(\gamma )-{\mathrm{EU}}_{{\upsilon }^D}^{\pi }(\gamma \left)\right)-1$$

Denote $\rho :=max\left({\mathrm{EU}}_{{\upsilon }^D}^{{\pi }^{\ast }{S}^{\star }}\right(\gamma )-{\mathrm{EU}}_{{\upsilon }^D}^{\pi }(\gamma ),0)$. By choosing $C$ sufficiently large, we can assume without loss of generality that the right hand side is positive since, unless ${\gamma }^{\overline{\tau }}\approx 1$, we would have $C\delta \overline{\tau }\ge C(1-\gamma )\overline{\tau }>1$, and unless $\rho \ll 1$, we would have $C\delta \frac{\rho }{1-\gamma }\ge C\rho >1$. In either case, the inequality we are trying to prove would hold. Also, note that $\frac{\ln (1-\delta )}{\ln \gamma }\ge 1$. We get

$$\underset{{\mu }^D\bowtie \pi }{E}\left[\right(1-\delta {)}^{{\tau }_{S^{\star }}}]=\underset{{\mu }^D\bowtie \pi }{E}\left[{\gamma }^{{\tau }_{S^{\star }}\frac{\ln (1-\delta )}{\ln \gamma }}\right]\ge \underset{{\mu }^D\bowtie \pi }{E}{\left[{\gamma }^{{\tau }_{S^{\star }}}\right]}^{\frac{\ln (1-\delta )}{\ln \gamma }}\ge {(2{\gamma }^{\overline{\tau }}-2\rho -1)}^{\frac{\ln (1-\delta )}{\ln \gamma }}=(1-\delta {)}^{\frac{\ln (2{\gamma }^{\overline{\tau }}-2\rho -1)}{\ln \gamma }}$$

By the same reasoning as before, we can assume without loss of generality that e.g. ${\gamma }^{\overline{\tau }}\le 1-\frac{1}{2}(1-\gamma )\overline{\tau }$. It follows that

$$2{\gamma }^{\overline{\tau }}-2\rho -1\le 2-(1-\gamma )\overline{\tau }-2\rho -1=1-(1-\gamma )\overline{\tau }-2\rho \le 1-(1-\gamma )=\gamma$$

$$\frac{\ln (2{\gamma }^{\overline{\tau }}-2\rho -1)}{\ln \gamma }\ge 1$$

Combining this with the previous inequality implies

$$\underset{{\mu }^D\bowtie \pi }{E}\left[\right(1-\delta {)}^{{\tau }_{S^{\star }}}]\ge 1-\delta \frac{\ln (2{\gamma }^{\overline{\tau }}-2\rho -1)}{\ln \gamma }$$

It is easy to see that there is $x_0\in (0,1)$ s.t. for any $x\in [x_0,1]$, $2x-1\ge x^3$ and therefore $\frac{2x-1}{x^3}\ge 1$. Therefore, for any such $x$ and $\rho \ll 1$, $e^{-C\rho }\le \frac{2x-1}{x^3}-\frac{2\rho }{x_0^3}\le \frac{2x-2\rho -1}{x^3}$, where it is sufficient to assume that $C>\frac{2}{x_0^3}$. Taking $x={\gamma }^{\overline{\tau }}$, we conclude (assuming $C\ge 3$ and observing that ${\gamma }^{\frac{1}{1-\gamma }}\le e^{-1}$)

$${\gamma }^{\frac{C\rho }{1-\gamma }}\le e^{-C\rho }\le \frac{2{\gamma }^{\overline{\tau }}-2\rho -1}{{\gamma }^{3\overline{\tau }}}\le \frac{2{\gamma }^{\overline{\tau }}-2\rho -1}{{\gamma }^{C\overline{\tau }}}$$

$${\gamma }^{C(\overline{\tau }+\frac{\rho }{1-\gamma })}\le 2{\gamma }^{\overline{\tau }}-2\rho -1$$

Taking logarithm of both sides

$$C(\overline{\tau }+\frac{\rho }{1-\gamma })\ln \gamma \le \ln (2{\gamma }^{\overline{\tau }}-2\rho -1)$$

$$C(\overline{\tau }+\frac{\rho }{1-\gamma })\ge \frac{\ln (2{\gamma }^{\overline{\tau }}-2\rho -1)}{\ln \gamma }$$

Combining with the inequality we had before, we get

$$\underset{{\mu }^D\bowtie \pi }{E}\left[\right(1-\delta {)}^{{\tau }_{S^{\star }}}]\ge 1-C\delta (\overline{\tau }+\frac{\rho }{1-\gamma })$$

#Proof of Proposition A.4

By Proposition A.5, we have

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\upsilon }^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\upsilon }^E}^{\pi }\left(\gamma \right)$$

Note that ${\tilde{M}}^E$ is a $\delta$-perturbation of $M^E$ and ${\tilde{\mu }}^E$ is a $\delta$-lift of ${\tilde{M}}^E$ to ${\mu }^E$. The condition of Proposition A.6 holds tautologically due to Definition A.3. Therefore, we can apply Proposition A.6 and get

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{\pi }\left(\gamma \right)+2(2-\underset{{\tilde{\mu }}^E\bowtie {\pi }^{\ast }{S}^{\star }}{E}\left[{(1-\delta )}^{{\tau }_{S^{\star }}}\right]-\underset{{\tilde{\mu }}^E\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_{S^{\star }}}\right])$$

The only difference between ${\tilde{\mu }}^E$ and ${\tilde{\mu }}^D$ is the appearance of $R$ instead of $I$. Therefore, we can rewrite the above as

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{\pi }\left(\gamma \right)+2(2-\underset{{\tilde{\mu }}^D\bowtie {\pi }^{\ast }{S}^{\star }}{E}\left[{(1-\delta )}^{{\tau }_{S^{\star }}}\right]-\underset{{\tilde{\mu }}^D\bowtie \pi }{E}\left[{(1-\delta )}^{{\tau }_{S^{\star }}}\right])$$

Applying Proposition A.7 to each of the last two terms, we get

$$\frac{1}{2}\left({\mathrm{EU}}_{\upsilon }^{{\pi }^{\ast }S}\right(\gamma )-{\mathrm{EU}}_{\upsilon }^{\pi R^{\ast }}(\gamma \left)\right)\le {\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{{\pi }^{\ast }{S}^{\star }}\left(\gamma \right)-{\mathrm{EU}}_{{\tilde{\upsilon }}^E}^{\pi }\left(\gamma \right)+4C\delta (2\overline{\tau }+\frac{max\left({\mathrm{EU}}_{{\tilde{\upsilon }}^D}^{{\pi }^{\ast }{S}^{\star }}\right(\gamma )-{\mathrm{EU}}_{{\tilde{\upsilon }}^D}^{\pi }(\gamma ),0)}{1-\gamma })$$

---

The following definition will be useful in order to apply Proposition A.4.

#Definition A.7

Consider $M$ a catastrophe MDP s.t. $A_M=A$ and a policy . We then define the catastrophe MDP $M\left[\sigma \right]$ as follows:

• $S_{M\left[\sigma \right]}^F:=S_M^F$, $S_{M\left[\sigma \right]}^D:=S_M^D$, $S_{M\left[\sigma \right]}^C:=S_M^C$.

• $A_{M\left[\sigma \right]}:=\overline{A}$

• For any $s\in S_M$ and $a\in A$: $T_{M\left[\sigma \right]}(s,a):=T_M(s,a)$.

• For any $s\in S_M$: $T_{M\left[\sigma \right]}(s,\perp ):=T_{M\sigma }\left(s\right)$.

• $R_{M\left[\sigma \right]}:=R_M$

Now consider $\upsilon$ an $O$-realization of $M$ with state function $S$. Then, $\overline{\upsilon }\left[\sigma S\right]$ is clearly an $\overline{O}$-realization of $M\left[\sigma \right]$ with the state function $\overline{S}$ defined by $\overline{S}\left(h\right):=S\left(\underset{–}{h}\right)$.

Note also that $M[\sigma {]}^D\cong M^D[\sigma ]$ and $M[\sigma {]}^E\cong M^E[\sigma ]$ (where interpreting $\sigma$ as a policy for $M^D$ or $M^E$ requires choosing an arbitrary value for the state $\perp$). Moreover, ${\overline{I}}^{\star }\cong \overline{I^{\star }}$, $\overline{\upsilon }[\sigma S{]}^D=\overline{{\upsilon }^D}[\sigma S^{\star }]$, $\overline{\upsilon }[\sigma S{]}^E=\overline{{\upsilon }^E}[\sigma S^{\star }]$ and ${\overline{S}}^{\star }=\overline{S^{\star }}$.

---

Finally, we are read to prove the main theorem.

#Proof of Theorem 1

For every $k\in \left[N\right]$, denote ${\tilde{M}}^k$ and ${\tilde{\sigma }}^k$ the $\delta$-perturbations of $M^k$ and ${\sigma }^k$ respectively and ${\pi }^k$ the deterministic proper mitigation policy for ${\tilde{M}}^k$ of Definition 8. Let ${\tilde{\mu }}^k$ be a lift of ${\tilde{M}}^k$ to ${\mu }^k$ and denote ${\tilde{\upsilon }}^k:=({\tilde{\mu }}^k,r^k)$. Define $H:=\{{\tilde{\upsilon }}^{kD},{\tilde{\upsilon }}^{kE}{\}}_{k\in \left[N\right]}$. Observe that ${\tilde{\sigma }}^k$ is $ϵ$-sane relatively to ${\pi }^k$ in the sense of ${\tilde{M}}^{kD}$ and ${\tilde{M}}^{kE}$ both: condition i of Definition A.1 follows by Proposition A.2 from conditions ii and iii of Definition 8, and condition ii of Definition A.1 follows from condition iv of Definition 8. Moreover, by Proposition A.3, we have

$$\left|\frac{d{V}_{{\tilde{M}}^D{\pi }^k}(s,\gamma )}{d\gamma }\right|=O\left(\overline{\tau }\right)$$

$$\left|\frac{d{V}_{{\tilde{M}}^E{\pi }^k}(s,\gamma )}{d\gamma }\right|=O\left(\overline{\tau }\right)$$

Here, we used that $M_k^F$ is fixed (and thus so is ${\overline{\tau }}^F$, by conditions i-iii).

Condition iv implies that all the universes in $H$ have a common reward function (notice that transition to a corrupted state induces the observation $\perp$ whereas transition to a state in $S_M^F$ in the universe ${\tilde{\upsilon }}^{kD}$ induces the observation $I$). Therefore, we can use Lemma A.1 to conclude that there exists an $\overline{I^{\star }}$-policy ${\pi }^{♯}$ s.t.

$${\mathrm{EU}}_{{\tilde{\upsilon }}^{kD}}^{{\pi }^k{S}^{k\star }}(1-\alpha )-{\mathrm{EU}}_{\overline{{\tilde{\upsilon }}^{kD}}\left[{\tilde{\sigma }}^k{S}^{k\star }\right]}^{{\pi }^{♯}}(1-\alpha )\le O\left(\right(\overline{\tau }\alpha {)}^{1/4})$$

$${\mathrm{EU}}_{{\tilde{\upsilon }}^{kE}}^{{\pi }^k{S}^{k\star }}(1-\alpha )-{\mathrm{EU}}_{\overline{{\tilde{\upsilon }}^{kE}}\left[{\tilde{\sigma }}^k{S}^{k\star }\right]}^{{\pi }^{♯}}(1-\alpha )\le O\left(\right(\overline{\tau }\alpha {)}^{1/4})$$

It is easy to see that ${\tilde{M}}^k\left[{\tilde{\sigma }}^k\right]$ is a $2\delta$-perturbation of $M^k\left[{\sigma }^k\right]$. Observe also that $\overline{{\tilde{\upsilon }}^{kD}}\left[{\tilde{\sigma }}^k{S}^{k\star }\right]=\overline{{\tilde{\upsilon }}^k}{\left[{\tilde{\sigma }}^k{S}^k\right]}^D$, $\overline{{\tilde{\upsilon }}^{kE}}\left[{\tilde{\sigma }}^k{S}^{k\star }\right]=\overline{{\tilde{\upsilon }}^k}{\left[{\tilde{\sigma }}^k{S}^k\right]}^E$ and $\overline{{\tilde{\mu }}^k}\left[{\tilde{\sigma }}^k{S}^k\right]$ is a $2\delta$-lift of ${\tilde{M}}^k\left[{\tilde{\sigma }}^k\right]$ to $\overline{{\mu }^k}\left[{\sigma }^k{S}^k\right]$. Applying Proposition A.4, we get

$$\frac{1}{2}\left({\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}\right(1-\alpha )-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{♯}{R}^{\ast }}(1-\alpha \left)\right)\le O\left(\right(\overline{\tau }\alpha {)}^{1/4}+\delta (\overline{\tau }+\frac{(\overline{\tau }\alpha {)}^{1/4}}{\alpha }))$$

\Comment{Given $h=a_0{b}_0{o}_0{a}_1{b}_1{o}_1\dots a_{n-1}{b}_{n-1}{o}_{n-1}\in {\overline{A\times O}}^n$, we use the notation

$${\overline{R}}^{\ast }h:=a_0{b}_0{o}_{0}R{a}_1{b}_1{o}_{1}R\dots a_{n-1}{b}_{n-1}{o}_{n-1}R\in {\overline{A\times O^{\prime }}}^n$$

We define ${\pi }^{\ast }$ as by ${\pi }^{\ast }\left(h\right):={\pi }^{\star }\left({\overline{R}}^{\ast }h\right)$.}

Setting ${\pi }^{\ast }:={\pi }^{♯}{R}^{\ast }$ we get

$${\mathrm{EU}}_{{\upsilon }^k}^{{\pi }^k{S}^k}(1-\alpha )-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{\ast }}(1-\alpha )\le O(max(\frac{\delta }{\alpha },1)\cdot (\overline{\tau }\alpha {)}^{1/4}+\overline{\tau }\delta )$$

By condition i of Definition 8, this implies

$${\mathrm{EU}}_{{\upsilon }^k}^{\ast }(1-\alpha )-{\mathrm{EU}}_{{\overline{\upsilon }}^k\left[{\sigma }^k{S}^k\right]}^{{\pi }^{\ast }}(1-\alpha )\le O(max(\frac{\delta }{\alpha },1)\cdot (\overline{\tau }\alpha {)}^{1/4}+\overline{\tau }\delta )$$

##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 , 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 and an arbitrary $I$-policy . 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(h\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 }}\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 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

$${\mathrm{EU}}_n^{!!k}\left(\gamma \right)-{\mathrm{EU}}_n^{!k}\left(\gamma \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

$${\mathrm{EU}}_n^{!!k}\left(\gamma \right)-{\mathrm{EU}}_n^{!k}\left(\gamma \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} \leq (1-\gamma^T)\sum_{n=0}^\infty \gamma^{nT} \E{}\left[\E{}\left[U^!_n \mid \J^!n = K,\ Z^!{nT}\right]-\E{}\left[U^!n \mid Z^!{nT}\right]\right]