Catastrophe Mitigation Using DRL (Appendices)

% 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 $υ = (μ, r)$ which an $O$ -realization of an MDP $M$ with state function $S$ , a stationary policy $π^{*} : S_{M} k \to A$ , an arbitrary $I$ -policy $π^{0}$ and some $γ \in (0, 1)$ . Then,

${EU}_{υ}^{π^{*} S} (γ) - {EU}_{υ}^{π^{0}} (γ) = \infty \sum n = 0 γ^{n} E x \sim μ ⋈ π^{0} [V_{M π^{*}} (S (x_{: n}), γ) - Q_{M π^{*}} (S (x_{: n}), x_{n}^{A}, γ)]$

#Proof of Proposition B.1

For the sake of encumbering the notation less, we will omit the parameter $γ$ in functions that depend on it. We will use $S$ implicitly, i.e. given $F$ a function on $S_{M}$ and $h \in hdom μ$ , $F (h) := F (S (h))$ . Finally, we will omit $M π^{*}$ , using the shorthand notations $V := V_{M π^{*}}$ , $Q := Q_{M π^{*}}$ .

For any $x \in {hdom}^{ω} μ$ , it is easy to see that

${EU}_{υ}^{π^{*} S} = V (λ) = \infty \sum n = 0 γ^{n} (V (x_{: n}) - γ V (x_{: n + 1}))$

$U^{r} (x) = (1 - γ) \infty \sum n = 0 γ^{n} r (x_{: n})$

${EU}_{υ}^{π^{*} S} - U^{r} (x) = \infty \sum n = 0 γ^{n} (V (x_{: n}) - (1 - γ) r (x_{: n}) - γ V (x_{: n + 1}))$

${EU}_{υ}^{π^{*} S} - U^{r} (x) = \infty \sum n = 0 γ^{n} (V (x_{: n}) - Q (x_{: n}, x_{n}^{A}) + Q (x_{: n}, x_{n}^{A}) - (1 - γ) r (x_{: n}) - γ V (x_{: n + 1}))$

Taking expected value over $x$ , we get

${EU}_{υ}^{π^{*} S} - {EU}_{υ}^{π^{0}} = \infty \sum n = 0 γ^{n} (E μ ⋈ π^{0} [V (x_{: n}) - Q (x_{: n}, x_{n}^{A})] + E μ ⋈ π^{0} [Q (x_{: n}, x_{n}^{A}) - (1 - γ) r (x_{: n}) - γ V (x_{: n + 1})])$

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

#Proposition B.2

Consider some $τ \in (0, \infty)$ , $T \in N^{+}$ , a universe $υ = (μ, r)$ that is an $O$ -realization of $M$ with state function $S$ , a stationary policy $π^{*} : S_{M} k \to A$ and an arbitrary $I$ -policy $π^{0} : (A \times O)^{*} k \to A$ . For any $n \in N$ , let $π_{n}^{*}$ be an $I$ -policy s.t. for any $h \in hdom μ$

$π_{n}^{*} (h) := {\begin{matrix} π^{0} (h) if | h | < n T π^{*} (S (h)) otherwise \end{matrix}$

Assume that

i. For any $h \in hdom μ$ $supp π^{0} (h) \subseteq A_{M π^{*}}^{0} (S (h))$

ii. For any $s \in S_{M}$ and $γ \in (0, 1)$ $∣ ∣ ∣ \frac{d V_{M π^{*}} (s, γ)}{d γ} ∣ ∣ ∣ \leq τ$

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

${EU}_{υ}^{π^{*} S} (γ) - {EU}_{υ}^{π^{0}} (γ) \leq (1 - γ) \infty \sum n = 0 T - 1 \sum m = 0 γ^{n T + m} (E x \sim μ ⋈ π_{n}^{*} [r (x_{: n T + m})] - E x \sim μ ⋈ π^{0} [r (x_{: n T + m})]) + \frac{2 τ γ^{T} (1 - γ)}{1 - γ^{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 hdom μ$ , $F (h) := F (S (h))$ . Also, we will omit $M π^{*}$ , using the shorthand notations $V := V_{M π^{*}}$ , $Q := Q_{M π^{*}}$ .

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

${EU}_{υ}^{π^{*}} (γ) - {EU}_{υ}^{π_{l}^{*}} (γ) = \infty \sum n = 0 γ^{n} E x \sim μ ⋈ π_{l}^{*} [V (x_{: n}, γ) - Q (x_{: n}, x_{n}^{A}, γ)]$

$π_{l}^{*}$ coincides with $π^{*}$ after $l T$ , therefore the corresponding expected values vanish.

${EU}_{υ}^{π^{*}} (γ) - {EU}_{υ}^{π_{l}^{*}} (γ) = l T - 1 \sum n = 0 γ^{n} E x \sim μ ⋈ π^{0} [V (x_{: n}, γ) - Q (x_{: n}, x_{n}^{A}, γ)]$

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

${EU}_{υ}^{π_{l}^{*}} (γ) - {EU}_{υ}^{π_{l + 1}^{*}} (γ) = (l + 1) T - 1 \sum n = l T γ^{n} E x \sim μ ⋈ π^{0} [V (x_{: n}, γ) - Q (x_{: n}, x_{n}^{A}, γ)]$

$(1 - γ) \infty \sum n = 0 γ^{n} (E x \sim μ ⋈ π_{l}^{*} [r (x_{: n})] - E x \sim μ ⋈ π_{l + 1}^{*} [r (x_{: n})]) = (l + 1) T - 1 \sum n = l T γ^{n} E x \sim μ ⋈ π^{0} [V (x_{: n}, γ) - Q (x_{: n}, x_{n}^{A}, γ)]$

$π_{l}^{*}$ and $π_{l + 1}^{*}$ coincide until $l T$ , therefore

$(1 - γ) \infty \sum n = l T γ^{n} (E x \sim μ ⋈ π_{l}^{*} [r (x_{: n})] - E x \sim μ ⋈ π_{l + 1}^{*} [r (x_{: n})]) = (l + 1) T - 1 \sum n = l T γ^{n} E x \sim μ ⋈ π^{0} [V (x_{: n}, γ) - Q (x_{: n}, x_{n}^{A}, γ)]$

Denote $ρ_{l}^{*} := μ ⋈ π_{l}^{*}$ , $ρ^{0} := μ ⋈ π^{0}$ . We also use the shorthand notations $r_{n} := r (x_{: n})$ , $V_{n} (γ) := V (x_{: n}, γ)$ , $Q_{n} (γ) := Q (x_{: n}, x_{n}^{A}, γ)$ . Both $π_{l}^{*}$ and $π_{l + 1}^{*}$ coincide with $π^{*}$ after $(l + 1) T$ , therefore

$(1 - γ) (l + 1) T - 1 \sum n = l T γ^{n} (E ρ_{l}^{*} [r_{n}] - E ρ^{0} [r_{n}]) + γ^{(l + 1) T} (E ρ_{l}^{*} [V_{(l + 1) T} (γ)] - E ρ^{0} [V_{(l + 1) T} (γ)]) = (l + 1) T - 1 \sum n = l T γ^{n} E ρ^{0} [V_{n} (γ) - Q_{n} (γ)]$

Denote $V^{'} (s, γ) := \frac{d V (s, γ)}{d γ}$ . By the mean value theorem, for each $s \in S_{M}$ there is $γ^{*} \in (γ, 1)$ s.t.

$V (s, γ) = V^{0} (s) - V^{'} (s, γ^{*}) \cdot (1 - γ)$

$V^{0} (s) - τ (1 - γ) \leq V (s, γ) \leq V^{0} (s) + τ (1 - γ)$

It follows that

$(1 - γ) (l + 1) T - 1 \sum n = l T γ^{n} E ρ_{l}^{*} - ρ^{0} [r_{n}] + γ^{(l + 1) T} (E ρ_{l}^{*} - ρ^{0} [V_{(l + 1) T}^{0}] + 2 τ (1 - γ)) \geq (l + 1) T - 1 \sum n = l T γ^{n} E ρ^{0} [V_{n} (γ) - Q_{n} (γ)]$

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 $ρ^{0}$ (whereas it is a martingale for $μ ⋈ π^{*}$ ) and therefore

$E ρ_{l}^{*} - ρ^{0} [V_{(l + 1) T}^{0}] \leq 0$

We get

$(1 - γ) (l + 1) T - 1 \sum n = l T γ^{n} E ρ_{l}^{*} - ρ^{0} [r_{n}] + 2 τ γ^{(l + 1) T} (1 - γ) \geq (l + 1) T - 1 \sum n = l T γ^{n} E ρ^{0} [V_{n} (γ) - Q_{n} (γ)]$

Summing over $l$ , we get

$(1 - γ) \infty \sum l = 0 (l + 1) T - 1 \sum n = l T γ^{n} E ρ_{l}^{*} - ρ^{0} [r_{n}] + \frac{2 τ γ^{T} (1 - γ)}{1 - γ^{T}} \geq \infty \sum n = 0 γ^{n} E ρ^{0} [V_{n} (γ) - Q_{n} (γ)]$

Applying Proposition B.1 to the right hand side

$(1 - γ) \infty \sum l = 0 (l + 1) T - 1 \sum n = l T γ^{n} E ρ_{l}^{*} - ρ^{0} [r_{n}] + \frac{2 τ γ^{T} (1 - γ)}{1 - γ^{T}} \geq {EU}_{υ}^{π^{*}} (γ) - {EU}_{υ}^{π^{0}} (γ)$

#Proof of Lemma A.1

Fix $γ \in (0, 1)$ , $η \in (0, N^{- 1})$ and $T \in N^{+}$ . Denote $ν^{k} := {¯ μ}^{k} [σ^{k} S^{k}]$ . To avoid cumbersome notation, whenever $M^{k}$ should appear a subscript, we will replace it by $k$ . Let $(Ω, P \in Δ Ω)$ be a probability space\Comment{ and ${F_{n} \subseteq 2^{Ω}}_{n \in N ⊔ {- 1}}$ a filtration of $Ω$ }. Let $K : Ω \to [N]$ be \Comment{measurable w.r.t. $F_{- 1}$ }a random variable and the following be stochastic processes\Comment{ adapted to $F$ }

$Z_{n}, {~ Z}_{n} : Ω \to Δ [N]$

$J_{n} : Ω \to [N]$

$Ψ_{n} : Ω \to A$

$A_{n} : Ω \to ¯ A$

$Θ_{n} : Ω \to ¯ O$

We also define $A Θ_{: n} : Ω \to {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*}$ by

$A Θ_{: n} := A_{0} Θ_{0} A_{1} Θ_{1} \dots A_{n - 1} Θ_{n - 1}$

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

${~ Z}_{0} (k) \equiv \frac{1}{N}$

$Z_{n} (k) = \frac{{~ Z}_{n} (k) [[{~ Z}_{n} (k) \geq η]]}{\sum_{j = 0}^{N - 1} {~ Z}_{n} (j) [[{~ Z}_{n} (j) \geq η]]}$

$Pr [J_{l} = k ∣ Z_{l T}] = Z_{l T} (k)$

$Ψ_{n} = π^{J_{l}} (A Θ_{: n})$

$Pr [Θ_{n} = o ∣ A Θ_{: n}] = ν^{K} (o ∣ A Θ_{: n})$

$A_{n} = D (A Θ_{: n}, Ψ_{n})$

${~ Z}_{n + 1} (k) N - 1 \sum j = 0 Z_{n} (j) [[A_{n} = D^{! j} (A Θ_{: n}, Ψ_{n})]] ν^{j} (Θ_{n} ∣ A Θ_{: n} A_{n}) = Z_{n} (k) [[A_{n} = D^{! k} (A Θ_{: n}, Ψ_{n})]] ν^{k} (Θ_{n} ∣ A Θ_{: 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 $¯ I$ -policy $π^{*}$ s.t. for any $n \in N$ , $h \in {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*}$ s.t. $Pr [A Θ_{: n} = h] > 0$ and $a \in ¯ A$

$π^{*} (a ∣ h) := Pr [A_{n} = a ∣ A Θ_{: 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 $η$ and hypotheses sampling which resulted in recommending "unsafe" actions i.e. actions that $D$ refused to perform.

In order to prove $π^{*}$ has the desired property, we will define the stochastic processes $Z^{!}$ , ${~ Z}^{!}$ , $J^{!}$ , $Ψ^{!}$ , $A^{!}$ and $Θ^{!}$ , each process of the same type as its shriekless counterpart (thus $Ω$ is constructed to accommodate them). These processes are required to satisfy the following:

${~ Z}_{0}^{!} (k) \equiv \frac{1}{N}$

$Z_{n}^{!} (k) = \frac{{~ Z}_{n}^{!} (k) [[{~ Z}_{n}^{!} (k) \geq η]]}{\sum_{j = 0}^{N - 1} {~ Z}_{n}^{!} (j) [[{~ Z}_{n}^{!} (j) \geq η]]} [[{~ Z}_{n}^{!} (K) \geq η]] + [[K = k]] \cdot [[{~ Z}_{n}^{!} (K) < η]]$

$Pr [J_{l}^{!} = k ∣ Z_{l T}^{!}] = Z_{l T}^{!} (k)$

$Ψ_{n}^{!} = π^{J_{l}^{!}} (A Θ_{: n}^{!})$

$Pr [Θ_{n}^{!} = o ∣ A Θ_{: n}^{!}] = ν^{K} (o ∣ A Θ_{: n}^{!})$

$A_{n}^{!} = D^{! K} (A Θ_{: n}^{!}, Ψ_{n}^{!})$

${~ Z}_{n + 1}^{!} (k) = \frac{Z_{n}^{!} (k) [[A_{n}^{!} = D^{! k} (A Θ_{: n}^{!}, Ψ_{n}^{!})]] ν^{k} (Θ_{n}^{!} ∣ A Θ_{: n}^{!} A_{n}^{!})}{\sum_{j = 0}^{N - 1} Z_{n}^{!} (j) [[A_{n}^{!} = D^{! j} (A Θ_{: n}^{!}, Ψ_{n}^{!})]] ν^{j} (Θ_{n}^{!} ∣ A Θ_{: n}^{!} A_{n}^{!})}$

For any $k \in [N]$ , we construct the $¯ I$ -policy $π^{? k}$ s.t. for any $n \in N$ , $h \in {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*}$ s.t. $Pr [A Θ_{: n}^{!} = h, K = k] > 0$ and $a \in ¯ A$

$π^{? k} (a ∣ h) := Pr [A_{n}^{!} = a ∣ A Θ_{: n}^{!} = h, K = k]$

Given any $¯ I$ -policy $π$ and $I$ -policy $σ$ we define $α_{σ π} : (A \times O)^{*} k \to {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*}$ by

$α_{σ π} (g ∣ h) := [[h = g -]] C_{h} | h | - 1 \prod n = 0 \sum a \in A ([[g_{n} \in ⊥ a O]] π (⊥ ∣ g_{: n}) σ (a ∣ h_{: n}) + [[g_{n} \in a ⊥ O]] π (a ∣ g_{: n}))$

Here, $C_{h} \in R$ is a constant defined s.t. the probabilities sum to 1. We define the $I$ -policy $[σ] π - -$ by

$[σ] π - - (a ∣ h) := Pr g \sim α_{σ π} (h) [π (g) = a \lor (π (g) = ⊥ \land σ (h) = a)]$

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

$supp [σ^{k}] {π - -}^{? k} (h) \subseteq A_{M^{k} π^{k}}^{0} (S^{k} (h))$

This means we can apply Proposition B.2 and get

${EU}_{υ^{k}}^{π^{k} S^{k}} (γ) - {EU}_{{¯ υ}^{k} [σ^{k} S^{k}]}^{π^{? k}} (γ) \leq (1 - γ) \infty \sum n = 0 T - 1 \sum m = 0 γ^{n T + m} (E x \sim μ^{k} ⋈ π_{n}^{* k} [r (x_{: n T + m})] - E x \sim ν^{k} ⋈ π^{? k} [r ({x - -}_{: n T + m})]) + \frac{2 ¯ τ γ^{T} (1 - γ)}{1 - γ^{T}}$

Here, the $I$ -policy $π_{n}^{* k}$ is defined as $π_{n}^{*}$ in Proposition B.2. We also define the $¯ I$ -policies $π_{n}^{! k}$ and $π_{n}^{!! k}$ by

$π_{n}^{! k} (a ∣ h) := {\begin{matrix} π^{? k} (a ∣ h) if | h | < n T Pr [A_{| h |}^{!} = a ∣ A Θ_{: | h |}^{!} = h, K = k, J_{n}^{!} = k] otherwise \end{matrix}$

$π_{n}^{!! k} (a ∣ h) := ⎧ ⎪ ⎨ ⎪ ⎩ \begin{matrix} π^{? k} (a ∣ h) if | h | < n T π_{n}^{! k} (a ∣ h) + π_{n}^{! k} (⊥ ∣ h) \cdot π_{n}^{* k} (a ∣ h - -) if | h | \geq n T and a \neq ⊥ 0 if | h | \geq n T and a = ⊥ \end{matrix}$

Denote

$ρ_{n}^{* k} := μ^{k} ⋈ π_{n}^{* k}$

$ρ_{n}^{!! k} := ν^{k} ⋈ π_{n}^{!! k}$

$ρ_{n}^{! k} := ν^{k} ⋈ π_{n}^{! k}$

$ρ^{? k} := ν^{k} ⋈ π^{? k}$

$R^{? k} := {EU}_{υ^{k}}^{π^{k} S^{k}} (γ) - {EU}_{{¯ υ}^{k} [σ^{k} S^{k}]}^{π^{? k}} (γ)$

For each $n \in N$ , denote

${EU}_{n}^{* k} (γ) := \frac{1 - γ}{1 - γ^{T}} T - 1 \sum m = 0 γ^{m} E x \sim ρ_{n}^{* k} [r (x_{: n T + m})]$

${EU}_{n}^{!! k} (γ) := \frac{1 - γ}{1 - γ^{T}} T - 1 \sum m = 0 γ^{m} E x \sim ρ_{n}^{!! k} [r ({x - -}_{: n T + m})]$

${EU}_{n}^{! k} (γ) := \frac{1 - γ}{1 - γ^{T}} T - 1 \sum m = 0 γ^{m} E x \sim ρ_{n}^{! k} [r ({x - -}_{: n T + m})]$

${EU}_{n}^{? k} (γ) := \frac{1 - γ}{1 - γ^{T}} T - 1 \sum m = 0 γ^{m} E x \sim ρ^{? k} [r ({x - -}_{: n T + m})]$

We have

$R^{? k} \leq (1 - γ^{T}) \infty \sum n = 0 γ^{n T} ({EU}_{n}^{* k} (γ) - {EU}_{n}^{? k} (γ)) + \frac{2 ¯ τ γ^{T} (1 - γ)}{1 - γ^{T}}$

$R^{? k} \leq (1 - γ^{T}) \infty \sum n = 0 γ^{n T} ({EU}_{n}^{* k} (γ) - {EU}_{n}^{!! k} (γ) + {EU}_{n}^{!! k} (γ) - {EU}_{n}^{! k} (γ) + {EU}_{n}^{! k} (γ) - {EU}_{n}^{? k} (γ)) + \frac{2 ¯ τ γ^{T} (1 - γ)}{1 - γ^{T}}$

Condition iv of Proposition C.1 and condition ii of Definition A.1 imply that, given $h \in hdom ν^{k}$ s.t. $| h | \geq n T$

$supp π_{n}^{! k} (h) \subseteq {π^{k} (S^{k} (h)), ⊥}$

$π_{n}^{!! k} (π^{k} (S^{k} (h)) ∣ h) = 1$

Therefore, $π_{n}^{!! k} = π_{n}^{* k}$ , and we remain with

$R^{? k} \leq (1 - γ^{T}) \infty \sum n = 0 γ^{n T} ({EU}_{n}^{!! k} (γ) - {EU}_{n}^{! k} (γ) + {EU}_{n}^{! k} (γ) - {EU}_{n}^{? k} (γ)) + \frac{2 ¯ τ γ^{T} (1 - γ)}{1 - γ^{T}}$

We have

$∣ ∣ {EU}_{n}^{!! k} (γ) - {EU}_{n}^{! k} (γ) ∣ ∣ \leq Pr x \sim ρ_{n}^{! k} [\exists m \in [T] : x_{n T + m} \in ⊥ ¯ O]$

Since $Z_{n T}^{!} (K) \geq η$ , it follows that

$∣ ∣ {EU}_{n}^{!! k} (γ) - {EU}_{n}^{! k} (γ) ∣ ∣ \leq \frac{1}{η} Pr x \sim ρ^{? k} [\exists m \in [T] : x_{n T + m} \in ⊥ ¯ O] \leq \frac{1}{η} E x \sim ρ^{? k} [∣ ∣ {m \in [T] ∣ x_{n T + m} \in ⊥ ¯ O} ∣ ∣]$

$\infty \sum n = 0 ∣ ∣ {EU}_{n}^{!! k} (γ) - {EU}_{n}^{! k} (γ) ∣ ∣ \leq \frac{1}{η} E x \sim ρ^{? k} [∣ ∣ {n \in N ∣ x_{n} \in ⊥ ¯ O} ∣ ∣]$

Using condition i of Proposition C.1, we conclude

$R^{? k} \leq (1 - γ^{T}) \infty \sum n = 0 γ^{n T} ({EU}_{n}^{! k} (γ) - {EU}_{n}^{? k} (γ)) + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

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

$U_{n}^{!} := \frac{1 - γ}{1 - γ^{T}} T - 1 \sum m = 0 γ^{m} r (A Θ_{: n T + m}^{!})$

Averaging the previous inequality over $k$ , we get

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} \leq (1 - γ^{T}) \infty \sum n = 0 γ^{n T} E [E [U_{n}^{!} ∣ J_{n}^{!} = K, Z_{n T}^{!}] - E [U_{n}^{!} ∣ Z_{n T}^{!}]] + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} = \sqrt{(1 - γ^{T}) \infty \sum n = 0 γ^{n T} E [{(E [U_{n}^{!} ∣ J_{n}^{!} = K, Z_{n T}^{!}] - E [U_{n}^{!} ∣ Z_{n T}^{!}])}^{2}]} + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

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

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} = \sqrt{(1 - γ^{T}) \infty \sum n = 0 γ^{n T} E [\frac{1}{2 η} I [K; J_{n}^{!}, U_{n}^{!} ∣ Z_{n T}^{!}]]} + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} = \sqrt{\frac{1 - γ^{T}}{2 η} \infty \sum n = 0 γ^{n T} E [H (Z_{n T}^{!}) - H (Z_{(n + 1) T}^{!})]} + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} = \sqrt{\frac{1 - γ^{T}}{2 η} ln N} + O (\frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

$\frac{1}{N} N - 1 \sum k = 0 R^{? k} = O (\sqrt{\frac{1 - γ^{T}}{η}} + \frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

Condition ii of Proposition C.1 implies that

$d_{tv} (\frac{1}{N} N - 1 \sum k = 0 {¯ ν}^{k} [σ^{k}] ⋈ π^{*}, \frac{1}{N} N - 1 \sum k = 0 {¯ ν}^{k} [σ^{k}] ⋈ π^{? k}) \leq 2 (N - 1) η$

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 $π^{*}$ and $π^{? k}$ and use the triangle inequality for $d_{tv}$ ). We conclude

${EU}_{υ^{k}}^{π^{k} S^{k}} (γ) - {EU}_{{¯ υ}^{k} [σ^{k} S^{k}]}^{π^{*}} (γ) = O (η + \sqrt{\frac{1 - γ^{T}}{η}} + \frac{1 - γ^{T}}{η^{2}} + \frac{¯ τ (1 - γ)}{1 - γ^{T}})$

Now we set

$η := {¯ τ}^{1 / 4} (1 - γ)^{1 / 4}$

$T := ⌈ {¯ τ}^{3 / 4} (1 - γ)^{- 1 / 4} ⌉$

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

${EU}_{υ^{k}}^{π^{k} S^{k}} (γ) - {EU}_{{¯ υ}^{k} [σ^{k} S^{k}]}^{π^{*}} (γ) = O ({¯ τ}^{1 / 4} (1 - γ)^{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 $π$ 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}{| A |})$ , $η \in (0, \frac{1}{N})$ . Consider some ${σ^{k} : (A \times O)^{*} k \to A}_{k \in [N]}$ . Then, there exist $D : {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*} \times A \to ¯ A$ and ${D^{! k} : {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*} \times A \to ¯ A}_{k \in [N]}$ with the following properties. Given $x \in {(A \times ¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O)}^{*}$ , we denote $x - -$ its projection to ${¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*}$ . Thus, $x - - - - \in (A \times O)^{*}$ . Given $μ$ an $I$ -environment, $π : hdom μ k \to A$ , $D^{'} : {¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O}^{*} \times A \to ¯ A$ and $k \in [N]$ , we can define $Ξ [μ, σ^{k}, D^{'}, π] \in Δ {(A \times ¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯ A \times O)}^{ω}$ as follows

$Ξ [μ, σ^{k}, D^{'}, π] (b, a, o ∣ x) := π (b ∣ x - - - -) D^{'} (a ∣ x - -, b) ¯ μ [σ^{k}] (o ∣ x - - a)$

We require that for every $π$ , $μ$ and $k$ as above, the following conditions hold

i. $\frac{1}{N} N - 1 \sum j = 0 E x \sim Ξ [μ, σ^{j}, D^{! j}, π] [∣ ∣ {n \in N ∣ x_{n} \in A \times ⊥ \times ¯ O} ∣ ∣] \leq \frac{ln N}{η ln (1 + ϵ (1 - ϵ)^{(1 - ϵ) / ϵ})} = O (\frac{ln N}{η ϵ})$

ii. $d_{tv} (\frac{1}{N} \sum_{j = 0}^{N - 1} Ξ [μ, σ^{j}, D, π], \frac{1}{N} \sum_{j = 0}^{N - 1} Ξ [μ, σ^{j}, D^{! j}, π]) \leq (N - 1) η$

iii. For all $x \in hdom ¯ μ [σ^{k}]$ , if $D^{! k} (x, π (x - -)) \neq ⊥$ then $σ^{k} (D^{! k} (x, π (x - -)) ∣ x - -) > 0$

iv. For all $x \in hdom ¯ μ [σ^{k}]$ , if $D^{! k} (x, π (x - -)) \notin {π (x - -), ⊥}$ then $σ^{k} (π (x - -) ∣ x - -) \leq ϵ$

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

#Proposition C.2

Consider a probability space $(Ω, P \in Δ Ω)$ , $N \in N$ , $R \subseteq [0, 1]$ a finite set and random variables $U : Ω \to R$ , $K : Ω \to [N]$ and $J : Ω \to [N]$ . Assume that $K_{*} P = J_{*} P = ζ \in Δ [N]$ and $I [K; J] = 0$ . Then

$I [K; J, U] \geq 2 (min i \in [N] ζ (i)) {(E [U ∣ J = K] - E [U])}^{2}$

AI ALIGNMENT FORUM
AF

AI ALIGNMENT FORUM
AF

0

Catastrophe Mitigation Using DRL (Appendices)

0