Minimax forecasting

%&latex

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

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

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

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

##Notation

Given $X$ a topological space, $P (X)$ will denote the space of Borel probability measures on $X$ . We regard it as a topological space using the weak $^{*}$ topology. Given $x \in X$ , $δ_{x} \in P (X)$ is defined by $δ_{x} (A) := [[x \in A]]$ . Given $μ, ν \in P (X)$ , $d_{tv} (μ, ν)$ stands for the total variation distance between $μ$ and $ν$ . We denote $P_{C} (X)$ the set of non-empty convex compact subsets of $P (X)$ .

Given $X$ a finite set, $X^{*}$ denotes the set of finite strings in alphabet $X$ , i.e. $X^{*} := ⨆_{n \in N} X^{n}$ . $X^{ω}$ denotes the set of infinite strings in alphabet $X$ . Given $x \in X^{*} ⊔ X^{ω}$ , $| x | \in N ⊔ {\infty}$ is the length of string. Given $0 \leq n < | x |$ , $x_{n} \in X$ is the $n$ -th symbol in $x$ . Given $0 \leq n \leq | x |$ , $x_{< n}$ is the prefix of $x$ of length $n$ . Given $x, y \in X^{*} ⊔ X^{ω}$ , the notations $x ⊏ y$ , $x ⊑ y$ , $x ⊏/ y$ and $x ⋢ y$ mean " $x$ is a proper prefix of $y$ ", " $x$ is a prefix of $y$ " and their negations. $λ_{X} \in X^{*}$ is the empty string and $X^{+} := X^{*} ∖ λ_{X}$ .

##Elementary properties of minimax

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

#Proposition 1

Consider $Φ \subseteq P (E)$ . There exists

$π^{*} \in a r g m a x π \in P (S) inf μ \in Φ E_{π \times μ} [u]$

Moreover, let $¯ Φ$ be the closure of the convex hull of $Φ$ . Then, the same $π^{*}$ satisfies

$π^{*} \in a r g m a x π \in P (S) min μ \in ¯ Φ E_{π \times μ} [u]$

We will say that such a $π^{*}$ is a minimax policy for $Φ$ .

#Proposition 2

Consider $Φ, Φ^{'} \in P_{C} (E)$ and $p \in [0, 1]$ . Then, there is $ν^{*} \in Φ^{'}$ s.t. any minimax policy for $p Φ + (1 - p) Φ^{'}$ is a minimax policy for $p Φ + (1 - p) ν^{*}$ .

In particular, Proposition 2 implies that a minimax policy for $Φ$ is the optimal policy for some $μ^{*} \in Φ$ .

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

$u (s_{1}, s_{2}, e) = u_{1} (s_{1}, e) + χ_{A} (e) u_{2} (s_{2}, α (s_{1}), e)$

Consider $Φ \in P_{C} (E)$ and $π^{*} \in P (S)$ minimax for $Φ$ . Denote ${pr}_{1, 2} : S \to S_{1, 2}$ the projection mappings. Define $π_{1}^{*} \in P (S_{1})$ by

$π_{1}^{*} := {pr}_{1 *} π^{*}$

Define $π_{2}^{*} : T \to P (S_{2})$ by

$π_{2}^{*} (t) := {pr}_{2 *} (π^{*} ∣ α^{- 1} (t) \times S_{2})$

If for some $t_{0} \in T$ we have $π^{*} (α^{- 1} (t_{0}) \times S_{2}) = 0$ , then $π_{2}^{*} (t_{0})$ can be arbitrary.

#Proposition 3

$π_{2}^{*} \in a r g m a x π_{2} : T \to P (S_{2}) min μ \in Φ (E_{π_{1}^{*} \times μ} [u_{1}] + μ (A) E_{t \sim α_{*} π_{1}^{*}} [E_{π_{2} (t) \times μ ∣ A} [u_{2} (t)]])$

It should also be possible to make do without $T$ and the associated decomposition of $u$ by instead decomposing $π^{*}$ into $π_{1}^{*}$ and a Markov kernel from $S_{1}$ to $S_{2}$ .

##Asymptotic optimality

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

$e_{n}^{s} := (s (e_{< n}), e_{n})$

The utility function is then given by

$u (s, e) = \sum n \in N γ (n) r (e_{< n}^{s})$

We will need a notation for a combination of two policies where the agent switches from one to another when observing some $x \in O^{*}$ . Given $s_{1} : O^{*} \to A$ and $s_{2} : O^{*} \to A$ , we define $s_{1} \times_{x} s_{2} : O^{*} \to A$ by

$(s_{1} \times_{x} s_{2}) (y) := {\begin{matrix} s_{1} (y) if y ⋣ x s_{2} (z) if y = x z \end{matrix}$

Consider any $π \in P (O^{*} \to A)$ and $ρ : A^{| x |} \to P (O^{*} \to A)$ . We define $π \otimes_{x} ρ \in P (O^{*} \to A)$ as follows. For any Borel measurable $B \subseteq O^{*} \to A$ :

$(π \otimes_{x} ρ) (B) := \sum t \in A^{| x |} {Pr}_{\begin{matrix} s_{1} \sim π s_{2} \sim ρ (t) \end{matrix}} [s_{1} \times_{x} s_{2} \in B \land \forall n < | x | : t_{n} = s_{1} (x_{< n})]$

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

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

#Proposition 4

$| E_{(π \otimes_{x} ρ) \times μ} [u] - E_{π \times μ} [u] | \leq (sup r - inf r) {Pr}_{e \sim μ} [x ⊏ e] \sum n > | x | γ (n)$

We are now ready to formulate the optimality theorem. Consider $Φ, Φ^{'} \in P_{C} (O^{ω})$ and $p \in (0, 1]$ . Denote $Ψ = p Φ + (1 - p) Φ^{'}$ . We think of $Ψ$ as the prior, $Φ$ as one of the models in the prior (assigned probability $p$ ) and $Φ^{'}$ as the convex combination of all other models. Let $π^{*} \in P (O^{*} \to A)$ be a minimax policy for $Ψ$ . Define $v : O^{*} \to R$ by

$v (x) := max ρ \in A^{| x |} \to P (O^{*} \to A) min μ \in Φ E_{(π^{*} \otimes_{x} ρ) \times μ} [u]$

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

#Theorem 1

$\forall μ \in Φ : {Pr}_{e \sim μ} [lim n \to \infty max (\frac{v (e_{< n}) - E_{π^{*} \times μ} [u]}{{Pr}_{e^{'} \sim μ} [e_{< n} ⊏ e^{'}] \sum_{m > n} γ (m)}, 0) = 0] = 1$

##Appendix A

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

#Proposition A.1

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

#Proof of Proposition A.1

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

$max y \in Y | f (x_{n}^{'}, y) - f (x_{\infty}, y) | > ϵ$

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

#Proposition A.2

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

$ϕ (x, ν) := E_{y \sim ν} [f (x, y)]$

Then, $ϕ$ is continuous.

#Proof of Proposition A.2

Consider any $x_{\infty} \in X$ , $ν_{\infty} \in P (Y)$ and sequences $x_{n} \to x_{\infty}$ , $ν_{n} \to ν_{\infty}$ . We have

$ϕ (x_{n}, ν_{n}) - ϕ (x_{\infty}, ν_{\infty}) = E_{y \sim ν_{n}} [f (x_{n}, y) - f (x_{\infty}, y)] + E_{y \sim ν_{n}} [f (x_{\infty}, y)] - E_{y \sim ν_{\infty}} [f (x_{\infty}, y)]$

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

#Proposition A.3

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

$F (μ, ν) := E_{μ \times ν} [f]$

Then, $F$ is continuous.

#Proof of Proposition A.3

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

#Proposition A.4

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

#Proof of Proposition A.4

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

$| inf y \in A f (x_{n}, y) - inf y \in A f (x_{\infty}, y) | \leq sup y \in A | f (x_{n}, y) - f (x_{\infty}, y) |$

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

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

#Proof of Proposition 1

Define $U_{Φ} : P (S) \to R$ by $U_{Φ} (π) := {inf}_{μ \in Φ} U (π, μ)$ . By Proposition A.4, $U_{Φ}$ is continuous and therefore, $π^{*}$ exists.

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

#Proof of Proposition 2

Define $V : P (E) \to R$ by $V (μ) := {max}_{π \in P (S)} U (π, μ) = {max}_{s \in S} U (δ_{s}, μ)$ . Denote $Ψ := p Φ + (1 - p) Φ^{'}$ . By Proposition A.4, $V$ is continuous and therefore, there exists

$ξ^{*} \in a r g m i n μ \in Ψ V (μ)$

Choose $μ^{*} \in Φ$ , $ν^{*} \in Φ^{'}$ s.t. $ξ^{*} = p μ^{*} + (1 - p) ν^{*}$ .

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

$max π \in P (S) min ξ \in Ψ U (π, ξ) = min ξ \in Ψ max s \in S U (δ_{s}, ξ)$

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

$min μ \in Φ U (π^{*}, p μ + (1 - p) ν^{*}) \geq min ξ \in Ψ U (π^{*}, ξ) = u^{*}$

On the other hand

$max π \in P (S) min μ \in Φ U (π, p μ + (1 - p) ν^{*}) \leq max π \in P (S) U (π, ξ^{*}) = u^{*}$

Combining the inequalities, we get the desired result.

#Definition A.1

In the setting of Proposition 3, consider any $π_{1} \in P (S_{1})$ and $π_{2} : T \to P (S_{2})$ . We define $π_{1} \otimes_{α} π_{2} \in P (S_{1} \times S_{2})$ as follows. For any Borel measurable $B \subseteq S_{1} \times S_{2}$ :

$(π_{1} \otimes_{α} π_{2}) (B) := \sum t \in T (π_{1} \times π_{2} (t)) (B \cap (α^{- 1} (t) \times S_{2}))$

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

#Proposition A.5

Consider any $π_{1} \in P (S_{1})$ and $π_{2} : T \to P (S_{2})$ and $f : S_{1} \times S_{2} \to R$ Borel measurable and bounded. Then:

$E_{π_{1} \otimes_{α} π_{2}} [f] = E_{s_{1} \sim π_{1}} [E_{s_{2} \sim π_{2} (α (s_{1}))} [f (s_{1}, s_{2})]]$

#Proof of Proposition A.5

$E_{π_{1} \otimes_{α} π_{2}} [f] = \sum t \in T \int_{α^{- 1} (t) \times S_{2}} f (s_{1}, s_{2}) d (π_{1} \times π_{2} (t)) (s_{2})$

$E_{π_{1} \otimes_{α} π_{2}} [f] = \sum t \in T \int_{α^{- 1} (t)} \int_{S_{2}} f (s_{1}, s_{2}) d π_{2} (t) (s_{2}) d π_{1} (s_{1})$

$E_{π_{1} \otimes_{α} π_{2}} [f] = \sum t \in T \int_{α^{- 1} (t)} E_{s_{2} \sim π_{2} (t)} [f (s_{1}, s_{2})] d π_{1} (s_{1})$

$E_{π_{1} \otimes_{α} π_{2}} [f] = \sum t \in T \int_{α^{- 1} (t)} E_{s_{2} \sim π_{2} (α (s_{1}))} [f (s_{1}, s_{2})] d π_{1} (s_{1})$

$E_{π_{1} \otimes_{α} π_{2}} [f] = \int_{S_{1}} E_{s_{2} \sim π_{2} (α (s_{1}))} [f (s_{1}, s_{2})] d π_{1} (s_{1})$

$E_{π_{1} \otimes_{α} π_{2}} [f] = E_{s_{1} \sim π_{1}} [E_{s_{2} \sim π_{2} (α (s_{1}))} [f (s_{1}, s_{2})]]$

#Proposition A.6

Given $π_{1} \in P (S_{1})$ , $π_{2} : T \to P (S_{2})$ and $μ \in P (E)$

$U (π_{1} \otimes_{α} π_{2}, μ) = E_{π_{1} \times μ} [u_{1}] + μ (A) E_{t \sim α_{*} π_{1}} [E_{π_{2} (t) \times μ ∣ A} [u_{2} (t)]]$

#Proof of Proposition A.6

Applying Proposition A.5:

$U (π_{1} \otimes_{α} π_{2}, μ) = E_{s_{1} \sim π_{1}} [E_{s_{2} \sim π_{2} (α (s_{1}))} [E_{e \sim μ} [u_{1} (s_{1}, e) + χ_{A} (e) u_{2} (s_{2}, α (s_{1}), e)]]]$

$U (π_{1} \otimes_{α} π_{2}, μ) = E_{π_{1} \times μ} [u_{1}] + E_{s_{1} \sim π_{1}} [E_{s_{2} \sim π_{2} (α (s_{1}))} [μ (A) E_{e \sim μ ∣ A} [u_{2} (s_{2}, α (s_{1}), e)]]]$

$U (π_{1} \otimes_{α} π_{2}, μ) = E_{π_{1} \times μ} [u_{1}] + μ (A) E_{t \sim α_{*} π_{1}} [E_{π_{2} (t) \times μ ∣ A} [u_{2} (t)]]$

#Proposition A.7

Consider any $π \in P (S_{1} \times S_{2})$ . Define $π_{1} \in P (S_{1})$ and $π_{2} : T \to P (S_{2})$ by

$π_{1} := {pr}_{1 *} π$

$π_{2} (t) := {pr}_{2 *} (π ∣ α^{- 1} (t) \times S_{2})$

If for some $t_{0} \in T$ we have $π (α^{- 1} (t_{0}) \times S_{2}) = 0$ , then $π_{2} (t_{0})$ can be arbitrary.

Then,

$\forall μ \in P (E) : U (π, μ) = U (π_{1} \otimes_{α} π_{2}, μ)$

#Proof of Proposition A.7

$U (π, μ) = E_{\begin{matrix} (s_{1}, s_{2}) \sim π e \sim μ \end{matrix}} [u_{1} (s_{1}, e) + χ_{A} (e) u_{2} (s_{2}, α (s_{1}), e)]$

$U (π, μ) = E_{π_{1} \times μ} [u_{1}] + μ (A) E_{\begin{matrix} (s_{1}, s_{2}) \sim π e \sim μ ∣ A \end{matrix}} [u_{2} (s_{2}, α (s_{1}), e)]$

$U (π, μ) = E_{π_{1} \times μ} [u_{1}] + μ (A) \sum t \in T {Pr}_{(s_{1}, s_{2}) \sim π} [α (s_{1}) = t] E_{\begin{matrix} (s_{1}, s_{2}) \sim π ∣ α^{- 1} (t) \times S_{2} e \sim μ ∣ A \end{matrix}} [u_{2} (s_{2}, t, e)]$

$U (π, μ) = E_{π_{1} \times μ} [u_{1}] + μ (A) E_{t \sim α_{*} π_{1}} [E_{π_{2} (t) \times μ ∣ A} [u_{2} (t)]]$

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

#Proof of Proposition 3

Consider any $π_{2} : T \to P (S_{2})$ . By definition of $π^{*}$

$min μ \in Φ U (π_{1}^{*} \otimes_{α} π_{2}, μ) \leq min μ \in Φ U (π^{*}, μ)$

Applying Proposition A.7 to the right hand side

$min μ \in Φ U (π_{1}^{*} \otimes_{α} π_{2}, μ) \leq min μ \in Φ U (π_{1}^{*} \otimes_{α} π_{2}^{*}, μ)$

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

Given any $x \in O^{*}$ , we denote $x O^{ω} := {x y ∣ y \in O^{ω}}$ and $¯ x O^{ω} := O^{ω} ∖ x O^{ω}$ .

#Proof of Proposition 4

We have

$E_{π \times μ} [u] = μ (x O^{ω}) E_{π \times μ ∣ x O^{ω}} [u] + (1 - μ (x O^{ω})) E_{π \times μ ∣ ¯ x O^{*}} [u]$

$E_{(π \otimes_{x} ρ) \times μ} [u] = μ (x O^{ω}) E_{(π \otimes_{x} ρ) \times μ ∣ x O^{ω}} [u] + (1 - μ (x O^{ω})) E_{π \times μ ∣ ¯ x O^{ω}} [u]$

$E_{(π \otimes_{x} ρ) \times μ} [u] - E_{π \times μ} [u] = μ (x O^{ω}) (E_{(π \otimes_{x} ρ) \times μ ∣ x O^{ω}} [u] - E_{π \times μ ∣ x O^{ω}} [u])$

Denote $u_{1} (s, e) := \sum_{n \leq | x |} γ (n) r (e_{< n}^{s})$ , $u_{2} (s, e) := \sum_{n > | x |} γ (n) r (e_{< n}^{s})$ . We have

$E_{π \times μ ∣ x O^{ω}} [u] = E_{π \times μ ∣ x O^{ω}} [u_{1}] + E_{π \times μ ∣ x O^{*}} [u_{2}]$

$E_{(π \otimes_{x} ρ) \times μ ∣ x O^{ω}} [u] = E_{π \times μ ∣ x O^{ω}} [u_{1}] + E_{(π \otimes_{x} ρ) \times μ ∣ x O^{ω}} [u_{2}]$

$E_{(π \otimes_{x} ρ) \times μ} [u] - E_{π \times μ} [u] = μ (x O^{ω}) (E_{(π \otimes_{x} ρ) \times μ ∣ x O^{ω}} [u_{2}] - E_{π \times μ ∣ x O^{ω}} [u_{2}])$

The desired result now follows from $(inf r) \sum_{n > | x |} γ (n) \leq u_{2} \leq (sup r) \sum_{n > | x |} γ (n)$ .

#Definition A.2

A splitting of $(S, E, u)$ is $(S_{1}, S_{2}, A, T, α, u_{1}, u_{2})$ s.t. $S ≅ S_{1} \times S_{2}$ , $A \subseteq E$ is Borel, $T$ is a finite set, $α : S_{1} \to T$ is Borel measurable, $u_{1} : S_{1} \times E \to R$ and $u_{2} : S_{2} \times T \times E \to R$ are continuous and

$u (s_{1}, s_{2}, e) = u_{1} (s_{1}, e) + χ_{A} (e) u_{2} (s_{2}, α (s_{1}), e)$

#Proposition A.8

Consider $Φ \in P_{C} (E)$ , $ν^{*} \in P (E)$ and $p \in [0, 1]$ , and denote $Ψ := p Φ + (1 - p) ν^{*}$ . Suppose that $(S_{1}, S_{2}, A, T, α, u_{1}, u_{2})$ is a splitting of $(S, E, u)$ . Assume $ν^{*} (A) > 0$ . Fix $π \in P (S_{1})$ . Let $ρ^{*} : T \to P (S_{2})$ satisfy

$ρ^{*} \in a r g m a x ρ : T \to P (S_{2}) min ξ \in Ψ U (π \otimes_{α} ρ, ξ)$

Denote $Γ := sup u_{2} - inf u_{2}$ . Then, for any $μ_{0} \in Φ$ s.t. $μ_{0} (A) > 0$

$U (π \otimes_{α} ρ^{*}, μ_{0}) \geq max ρ : T \to P (S_{2}) min μ \in Φ U (π \otimes_{α} ρ, μ) - 2 Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)$

#Proof of Proposition A.8

Let $τ^{*} : T \to P (S_{2})$ satisfy

$τ^{*} \in a r g m a x ρ : T \to P (S_{2}) min μ \in Φ U (π \otimes_{α} ρ, μ)$

Denote $u^{*} := {min}_{μ \in Φ} U (π \otimes_{α} τ^{*}, μ)$ . Consider any $μ \in Φ$ and denote $ξ := p μ + (1 - p) ν^{*}$ . We have

$U (π \otimes_{α} τ^{*}, ξ) = p U (π \otimes_{α} τ^{*}, μ^{'}) + (1 - p) U (π \otimes_{α} τ^{*}, ν^{*})$

$U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) U (π \otimes_{α} τ^{*}, ν^{*})$

Applying Proposition A.6 to the right hand side

$U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{τ^{*} (t) \times ν^{*}} [u_{2} ∣ A]])$

$U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) (E_{t \sim α_{*} π} [E_{τ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] - Γ d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

Also, we have

$U (π \otimes_{α} τ^{*}, μ_{0}) \geq u^{*}$

Applying Proposition A.6 again

$E_{π \times μ_{0}} [u_{1}] + μ_{0} (A) E_{t \sim α_{*} π} [E_{τ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] \geq u^{*}$

$E_{t \sim α_{*} π} [E_{τ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] \geq \frac{u^{*} - E_{π \times μ_{0}} [u_{1}]}{μ_{0} (A)}$

Combining the inequalities

$U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) (\frac{u^{*} - E_{π \times μ_{0}} [u_{1}]}{μ_{0} (A)} - Γ d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

$U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + \frac{ν^{*} (A)}{μ_{0} (A)} (u^{*} - E_{π \times μ_{0}} [u_{1}] - Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

$U (π \otimes_{α} τ^{*}, ξ) \geq (p + (1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}) u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] - \frac{ν^{*} (A)}{μ_{0} (A)} (E_{π \times μ_{0}} [u_{1}] + Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

The above inequality holds for any $ξ$ , therefore

$min ξ \in Ψ U (π \otimes_{α} τ^{*}, ξ) \geq (p + (1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}) u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] - \frac{ν^{*} (A)}{μ_{0} (A)} (E_{π \times μ_{0}} [u_{1}] + Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

By definition of $ρ^{*}$ , it follows that

$min ξ \in Ψ U (π \otimes_{α} ρ^{*}, ξ) \geq (p + (1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}) u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] - \frac{ν^{*} (A)}{μ_{0} (A)} (E_{π \times μ_{0}} [u_{1}] + Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)))$

Denote $ξ_{0} := p μ_{0} + (1 - p) ν^{*}$ and $u := U (π \otimes_{α} ρ^{*}, μ_{0})$ . We have

$U (π \otimes_{α} ρ^{*}, ξ_{0}) = p u + (1 - p) U (π \otimes_{α} ρ^{*}, ν^{*})$

Applying Proposition A.6 to the right hand side

$U (π \otimes_{α} ρ^{*}, ξ_{0}) = p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times ν^{*}} [u_{2} ∣ A]])$

$U (π \otimes_{α} ρ^{*}, ξ_{0}) \leq p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) (E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] + Γ d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A))$

On the other hand, Proposition A.6 implies that

$E_{π \times μ_{0}} [u_{1}] + μ_{0} (A) E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] = u$

$E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times μ_{0}} [u_{2} ∣ A]] = \frac{u - E_{π \times μ_{0}} [u_{1}]}{μ_{0} (A)}$

Substituting in the inequality, we get

$U (π \otimes_{α} ρ^{*}, ξ_{0}) \leq p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) (\frac{u - E_{π \times μ_{0}} [u_{1}]}{μ_{0} (A)} + Γ d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A))$

$U (π \otimes_{α} ρ^{*}, ξ_{0}) \leq p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + \frac{ν^{*} (A)}{μ_{0} (A)} (u - E_{π \times μ_{0}} [u_{1}] + Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A))$

$U (π \otimes_{α} ρ^{*}, ξ_{0}) \leq (p + (1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}) u + (1 - p) (E_{π \times ν^{*}} [u_{1}] - \frac{ν^{*} (A)}{μ_{0} (A)} (E_{π \times μ_{0}} [u_{1}] - Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A))$

Observing that $U (π \otimes_{α} ρ^{*}, ξ_{0}) \geq {min}_{ξ \in Ψ} U (π \otimes_{α} ρ^{*}, ξ)$ we can combine the inequalities, we get

$(p + (1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}) (u - u^{*}) \geq 2 (1 - p) (- \frac{ν^{*} (A)}{μ_{0} (A)} Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A))$

If $p = 1$ , we get $u \geq u^{*}$ , as desired. If $p < 1$ , we divide both sides by $(1 - p) \frac{ν^{*} (A)}{μ_{0} (A)}$ and get

$(\frac{p}{1 - p} \frac{μ_{0} (A)}{ν^{*} (A)} + 1) (u - u^{*}) \geq - 2 Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)$

$u \geq u^{*} - \frac{2 Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)}{\frac{p}{1 - p} \frac{μ_{0} (A)}{ν^{*} (A)} + 1}$

$u \geq u^{*} - 2 Γ μ_{0} (A) d_{tv} (μ_{0} ∣ A, ν^{*} ∣ A)$

#Proposition A.9

In the setting of Proposition A.8, assuming $p > 0$ but sans the assumption $ν^{*} (A) > 0$ :

$U (π \otimes_{α} ρ^{*}, μ_{0}) \geq max ρ : T \to P (S_{2}) min μ \in Φ U (π \otimes_{α} ρ, μ) - \frac{1 - p}{p} Γ ν^{*} (A)$

#Proof of Proposition A.9

We use the same notation as in the proof of Proposition A.8. As before, we have

$min ξ \in Ψ U (π \otimes_{α} τ^{*}, ξ) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{τ^{*} (t) \times ν^{*}} [u_{2} ∣ A]])$

$U (π \otimes_{α} ρ^{*}, ξ_{0}) = p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times ν^{*}} [u_{2} ∣ A]])$

Combining, we get

$p u + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{ρ^{*} (t) \times ν^{*}} [u_{2} ∣ A]]) \geq p u^{*} + (1 - p) (E_{π \times ν^{*}} [u_{1}] + ν^{*} (A) E_{t \sim α_{*} π} [E_{τ^{*} (t) \times ν^{*}} [u_{2} ∣ A]])$

$u \geq u^{*} + \frac{1 - p}{p} ν^{*} (A) E_{t \sim α_{*} π} [E_{τ^{*} (t) \times ν^{*}} [u_{2} ∣ A] - E_{ρ^{*} (t) \times ν^{*}} [u_{2} ∣ A]]$

$u \geq u^{*} + \frac{1 - p}{p} Γ ν^{*} (A)$

#Definition A.3

Denote $x O^{*} := {x y ∣ y \in O^{*}}$ , $¯ x O^{*} := O^{*} ∖ x O^{*}$ . Given any $x \in O^{*}$ , the splitting of $(O^{*} \to A, O^{ω}, u)$ at $x$ is defined as follows.

$S_{1} := ¯ x O^{*} \to A$

$S_{2} := x O^{*} \to A$

$A := x O^{ω}$

$T := A^{| x |}$

$α (s)_{n} := s (x_{< n})$

Given $s : ¯ x O^{*} \to A$ and $e \in x O^{ω}$ , define $e^{s} \in (A \times O)^{| x |}$ by $e_{n}^{s} := (s (e_{< n}), e_{n})$ . Given $e \in ¯ x O^{ω}$ , define $e^{s} \in (A \times O)^{ω}$ by $e_{n}^{s} := (s (e_{< n}), e_{n})$ . Define $u_{1}$ by

$u_{1} (s, e) := | e^{s} | \sum n = 0 γ (n) r (e_{< n}^{s})$

Given $t \in A^{| x |}$ , $s : x O^{*} \to A$ and $e \in x O^{ω}$ , define $e^{t s} \in (A \times O)^{ω}$ by

$e_{n}^{t s} := {\begin{matrix} (t_{n}, e_{n}) if n < | x | (s (e_{< n}, e_{n}) if n \geq | x | \end{matrix}$

Define $u_{2}$ by

$u_{2} (s, t, e) := {\begin{matrix} \sum_{n = | x | + 1}^{\infty} γ (n) r (e_{< n}^{t s}) if x ⊏ e 0 otherwise \end{matrix}$

It is easy to see that this is indeed a splitting.

#Proof of Theorem 1

Fix $μ_{0} \in Φ$ . Let $ν^{*} \in Φ^{'}$ be as in Proposition 2. Define $M, N \subseteq O^{ω}$ by

$M := {e \in O^{ω} ∣ lim n \to \infty d_{tv} (μ_{0} ∣ e_{< n} O^{ω}, ν^{*} ∣ e_{< n} O^{ω}) = 0}$

$N := {e \in O^{ω} ∣ lim n \to \infty \frac{ν^{*} (e_{< n} O^{ω})}{μ_{0} (e_{< n} O^{ω})} = 0}$

By Corollary B, $μ_{0} (M \cup N) = 1$ .

Consider any $e \in M$ . By definition of $M$ , for any $n \in N$ we have $μ_{0} (e_{< n} O^{ω}) > 0$ and $ν^{*} (e_{< n} O^{ω}) > 0$ . Therefore, we can apply Proposition A.8 to the splitting of $(O^{*} \to A, O^{ω}, u)$ at $e_{< n}$ , with $π = π^{*}$ . This gives us

$U (π^{*}, μ_{0}) \geq v (e_{< n}) - 2 Γ_{n} μ_{0} (e_{< n} O^{ω}) d_{tv} (μ_{0} ∣ e_{< n} O^{ω}, ν^{*} ∣ e_{< n} O^{ω})$

Here, $Γ_{n} \leq (sup r - inf r) \sum_{m > n} γ (n)$ .

$\frac{v (e_{< n}) - U (π^{*}, μ_{0})}{Γ_{n} μ_{0} (e_{< n} O^{ω})} \leq 2 d_{tv} (μ_{0} ∣ e_{< n} O^{ω}, ν^{*} ∣ e_{< n} O^{ω})$

By definition of $M$ , this implies

$lim n \to \infty max (\frac{v (e_{< n}) - U (π^{*}, μ_{0})}{Γ_{n} μ_{0} (e_{< n} O^{ω})}, 0) = 0$

Now, consider any $e \in N$ . By definition of $N$ , for any $n \in N$ we have $μ_{0} (e_{< n} O^{ω}) > 0$ . Therefore, we can apply Proposition A.9 to the splitting of $(O^{*} \to A, O^{ω}, u)$ at $e_{< n}$ , with $π = π^{*}$ . This gives us

$U (π^{*}, μ_{0}) \geq v (e_{< n}) - \frac{1 - p}{p} Γ_{n} ν^{*} (e_{< n} O^{ω})$

$\frac{v (e_{< n}) - U (π^{*}, μ_{0})}{Γ_{n} μ_{0} (e_{< n} O^{ω})} \leq \frac{1 - p}{p} \frac{ν^{*} (e_{< n} O^{ω})}{μ_{0} (e_{< n} O^{ω})}$

By definition of $N$ , this also implies

$lim n \to \infty max (\frac{v (e_{< n}) - U (π^{*}, μ_{0})}{Γ_{n} μ_{0} (e_{< n} O^{ω})}, 0) = 0$

##Appendix B

The following theorem is adapted from Blackwell and Dubbins (1962).

#Theorem B.1

Consider any $μ, ν \in P (O^{ω})$ . Assume that $μ$ is absolutely continuous with respect to $ν$ . Then:

${Pr}_{e \sim μ} [lim n \to \infty d_{tv} (μ ∣ e_{< n} O^{ω}, ν ∣ e_{< n} O^{ω}) = 0] = 1$

#Theorem B.2

Consider any $μ, ν \in P (O^{ω})$ . Define ${D_{n} : O^{ω} \to R ⊔ {+ \infty}}_{n \in N}$ by

$D_{n} (x) := {\begin{matrix} \frac{μ (x_{< n} O^{ω})}{ν (x_{< n} O^{ω})} if ν (x_{< n} O^{ω}) > 0 + \infty otherwise \end{matrix}$

Define $D := {limsup}_{n \to \infty} D_{n}$ . Then, for any Borel $A \subseteq O^{ω}$ :

$μ (A) = \int_{A} D (x) d ν (x) + μ (A \cap D^{- 1} (+ \infty))$

#Proof of Theorem B.2

This is almost a special case of Theorem 5.3.3 in Durret (2010), except that we don't assume $μ$ is locally absolutely continuous w.r.t. $ν$ (i.e. we don't assume that $μ (x O^{ω}) = 0$ whenever $ν (x O^{ω}) = 0$ ). Careful reading of the proof shows that in our case it doesn't matter: $D_{n}$ ( $X_{n}$ is Durret's notation) is no longer a $ν$ -martingale but is still a $ν$ -supermartingale, and the identity $X_{n} = \frac{Y_{n}}{Z_{n}}$ still holds if the fraction is understood to stand for $+ \infty$ whenever $Z_{n} = 0$ .

#Corollary B

Consider any $μ, ν \in P (O^{ω})$ . Define

$A := {e \in O^{ω} ∣ lim n \to \infty d_{tv} (μ ∣ e_{< n} O^{ω}, ν ∣ e_{< n} O^{ω}) = 0}$

$B := {e \in O^{ω} ∣ lim n \to \infty \frac{ν (e_{< n} O^{ω})}{μ (e_{< n} O^{ω})} = 0}$

Then, $μ (A \cup B) = 1$ .

#Proof of Corollary B

Assume that $E_{ν} [D] > 0$ . Then, we can define $μ_{r} \in P (O^{ω})$ by

$μ_{r} (C) := \frac{\int_{C} D (x) d ν (x)}{\int_{O^{ω}} D (x) d ν (x)}$

Obviously, $μ_{r}$ is absolutely continuous w.r.t. $ν$ , therefore we can use Theorem B.1 to conclude

${Pr}_{e \sim μ_{r}} [lim n \to \infty d_{tv} (μ_{r} ∣ e_{< n} O^{ω}, ν ∣ e_{< n} O^{ω}) = 0] = 1$

By Theorem B.2, $μ_{r}$ is dominated by $μ$ and in particular is absolutely continuous w.r.t. $μ$ . Therefore, again by Theorem B.1:

${Pr}_{e \sim μ_{r}} [lim n \to \infty d_{tv} (μ_{r} ∣ e_{< n} O^{ω}, μ ∣ e_{< n} O^{ω}) = 0] = 1$

Using the triangle inequality for $d_{tv}$ , we get

${Pr}_{e \sim μ_{r}} [lim n \to \infty d_{tv} (μ ∣ e_{< n} O^{ω}, ν ∣ e_{< n} O^{ω}) = 0] = 1$

By definition of $μ_{r}$ and $A$ , this means that

$\frac{\int_{A} D (x) d ν (x)}{\int_{O^{ω}} D (x) d ν (x)} = 1$

$\int_{A} D (x) d ν (x) = \int_{O^{ω}} D (x) d ν (x)$

This holds even without the assumption $E_{ν} [D] > 0$ , since if $E_{ν} [D] = 0$ then both sides vanish.

$\frac{ν (e_{< n} O^{ω})}{μ (e_{< n} O^{ω})}$ is $μ$ -supermatingale, therefore (by Doob's convergence theorem) its limit exists $μ$ -almost surely. If the limit exists for some $e \in O^{ω}$ , then it vanishes iff $D (e) = + \infty$ . It follows that

$μ (B \cap D^{- 1} (+ \infty)) = μ (D^{- 1} (+ \infty))$

By Theorem B.2

$μ (A \cup B) = \int_{A \cup B} D (x) d ν (x) + μ ((A \cup B) \cap D^{- 1} (+ \infty))$

$μ (A \cup B) \geq \int_{A} D (x) d ν (x) + μ (B \cap D^{- 1} (+ \infty))$

$μ (A \cup B) \geq \int_{O^{ω}} D (x) d ν (x) + μ (D^{- 1} (+ \infty))$

Applying Theorem B.2 to the right hand side:

$μ (A \cup B) \geq μ (O^{ω}) = 1$

AI ALIGNMENT FORUM
AF

AI ALIGNMENT FORUM
AF

0

0