Optimal Policies Tend to Seek Power — part 6/16
Cleaned-text code points [78769, 94206). Bibliography omitted here; source.md includes it.
Let 𝐱 , 𝐱 ′ ∈ ℝ | 𝒮 | \mathbf{x},\mathbf{x}^{\prime}\in\mathbb{R}^{\left|\mathcal{S}\right|} be distinct. ℙ 𝐫 ∼ 𝒟 cont ( 𝐱 ⊤ 𝐫 = 𝐱 ′ ⊤ 𝐫 ) = 0 \Prb\nolimits_{\mathbf{r}\sim\mathcal{D}_{\text{cont}}}\left(\mathbf{x}^{\top}\mathbf{r}=\mathbf{x}^{\prime\top}\mathbf{r}\right)=0 .
###### Proof.
{ 𝐫 ∈ ℝ | 𝒮 | ∣ ( 𝐱 − 𝐱 ′ ) ⊤ 𝐫 = 0 } \left\{\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mid(\mathbf{x}-\mathbf{x}^{\prime})^{\top}\mathbf{r}=0\right\} is a hyperplane since 𝐱 − 𝐱 ′ ≠ 𝟎 \mathbf{x}-\mathbf{x}^{\prime}\neq\mathbf{0} . Therefore, it has no interior in the standard topology on ℝ | 𝒮 | \mathbb{R}^{\left|\mathcal{S}\right|} . Since this empty-interior set is also convex, it has zero Lebesgue measure. By the Radon-Nikodym theorem, it has zero measure under any continuous distribution 𝒟 cont \mathcal{D}_{\text{cont}} . ∎
###### Corollary E.8 (Unique maximization of almost all vectors) .
Let X ⊊ ℝ | 𝒮 | X\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. ℙ 𝐫 ∼ 𝒟 cont ( | arg max 𝐱 ′′ ∈ X 𝐱 ′ ′ ⊤ 𝐫 | > 1 ) = 0 \Prb\nolimits_{\mathbf{r}\sim\mathcal{D}_{\text{cont}}}\left(\left|\argmax_{\mathbf{x}^{\prime\prime}\in X}\mathbf{x}^{\prime\prime\top}\mathbf{r}\right|>1\right)=0 .
###### Proof.
Let 𝐱 , 𝐱 ′ ∈ X \mathbf{x},\mathbf{x}^{\prime}\in X be distinct. For any 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} , 𝐱 , 𝐱 ′ ∈ arg max 𝐱 ′′ ∈ X 𝐱 ′ ′ ⊤ 𝐫 \mathbf{x},\mathbf{x}^{\prime}\in\argmax_{\mathbf{x}^{\prime\prime}\in X}\mathbf{x}^{\prime\prime\top}\mathbf{r} iff 𝐱 ⊤ 𝐫 = 𝐱 ′ ⊤ 𝐫 ≥ max 𝐱 ′′ ∈ X ∖ { 𝐱 , 𝐱 ′ } 𝐱 ′ ′ ⊤ 𝐫 \mathbf{x}^{\top}\mathbf{r}=\mathbf{x}^{\prime\top}\mathbf{r}\geq\max_{\mathbf{x}^{\prime\prime}\in X\setminus\left\{\mathbf{x},\mathbf{x}^{\prime}\right\}}\mathbf{x}^{\prime\prime\top}\mathbf{r} . By Lemma E.7 , 𝐱 ⊤ 𝐫 = 𝐱 ′ ⊤ 𝐫 \mathbf{x}^{\top}\mathbf{r}=\mathbf{x}^{\prime\top}\mathbf{r} holds with probability 0 under any 𝒟 cont \mathcal{D}_{\text{cont}} . ∎
#### E.1.1 Generalized non-domination results
Our formalism includes both ℱ nd ( s ) \Fndop(s) and RSD nd ( s ) \text{{RSD}}{\text{\textsubscript{nd}}}\left(s\right) ; we therefore prove results that are applicable to both.
###### Definition E.9 (Non-dominated linear functionals) .
Let X ⊊ ℝ | 𝒮 | X\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. ND ( X ) ≔ { 𝐱 ∈ X ∣ ∃ 𝐫 ∈ ℝ | 𝒮 | : 𝐱 ⊤ 𝐫 > max 𝐱 ′ ∈ X ∖ { 𝐱 } 𝐱 ′ ⊤ 𝐫 } \text{{ND}}\left(X\right)\coloneqq\left\{\mathbf{x}\in X\mid\exists\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\top}\mathbf{r}>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}\right\}}\mathbf{x}^{\prime\top}\mathbf{r}\right\} .
###### Lemma E.10 (All vectors are maximized by a non-dominated linear functional) .
Let 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} and let X ⊊ ℝ | 𝒮 | X\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite and non-empty. ∃ 𝐱 ∗ ∈ ND ( X ) : 𝐱 ∗ ⊤ 𝐫 = max 𝐱 ∈ X 𝐱 ⊤ 𝐫 \exists\mathbf{x}^{*}\in\text{{ND}}\left(X\right)\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{*\top}\mathbf{r}=\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r} .
###### Proof.
Let A ( 𝐫 ∣ X ) ≔ arg max 𝐱 ∈ X 𝐱 ⊤ 𝐫 = { 𝐱 1 , … , 𝐱 n } A(\mathbf{r}\mid X)\coloneqq\argmax_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}=\left\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\right\} . Then 𝐱 1 ⊤ 𝐫 = ⋯ = 𝐱 n ⊤ 𝐫 > max 𝐱 ′ ∈ X ∖ A ( 𝐫 ∣ X ) 𝐱 ′ ⊤ 𝐫 . \displaystyle\mathbf{x}_{1}^{\top}\mathbf{r}=\cdots=\mathbf{x}_{n}^{\top}\mathbf{r}>\max_{\mathbf{x}^{\prime}\in X\setminus A(\mathbf{r}\mid X)}\mathbf{x}^{\prime\top}\mathbf{r}. (10)
In eq. 10 , each 𝐱 ⊤ 𝐫 \mathbf{x}^{\top}\mathbf{r} expression is linear on 𝐫 \mathbf{r} . The max \max is piecewise linear on 𝐫 \mathbf{r} since it is the maximum of a finite set of linear functionals. In particular, all expressions in eq. 10 are continuous on 𝐫 \mathbf{r} , and so we can find some δ > 0 \delta>0 neighborhood B ( 𝐫 , δ ) B(\mathbf{r},\delta) such that ∀ 𝐫 ′ ∈ B ( 𝐫 , δ ) : max 𝐱 i ∈ A ( 𝐫 ∣ X ) 𝐱 i ⊤ 𝐫 ′ > max 𝐱 ′ ∈ X ∖ A ( 𝐫 ∣ X ) 𝐱 ′ ⊤ 𝐫 ′ \forall\mathbf{r}^{\prime}\in B(\mathbf{r},\delta)\mathrel{\mathop{\ordinarycolon}}\max_{\mathbf{x}_{i}\in A(\mathbf{r}\mid X)}\mathbf{x}_{i}^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus A(\mathbf{r}\mid X)}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime} .
But almost all 𝐫 ′ ∈ B ( 𝐫 , δ ) \mathbf{r}^{\prime}\in B(\mathbf{r},\delta) are maximized by a unique functional 𝐱 ∗ \mathbf{x}^{*} by Corollary E.8 ; in particular, at least one such 𝐫 ′′ \mathbf{r}^{\prime\prime} exists. Formally, ∃ 𝐫 ′′ ∈ B ( 𝐫 , δ ) : 𝐱 ∗ ⊤ 𝐫 ′′ > max 𝐱 ′ ∈ X ∖ { 𝐱 ∗ } 𝐱 ′ ⊤ 𝐫 ′′ \exists\mathbf{r}^{\prime\prime}\in B(\mathbf{r},\delta)\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{*\top}\mathbf{r}^{\prime\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}^{*}\right\}}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime\prime} . Therefore, 𝐱 ∗ ∈ ND ( X ) \mathbf{x}^{*}\in\text{{ND}}\left(X\right) by definition E.9 .
𝐱 ∗ ⊤ 𝐫 ′ ≥ max 𝐱 i ∈ A ( 𝐫 ∣ X ) 𝐱 i ⊤ 𝐫 ′ > max 𝐱 ′ ∈ X ∖ A ( 𝐫 ∣ X ) 𝐱 ′ ⊤ 𝐫 ′ \mathbf{x}^{*\top}\mathbf{r}^{\prime}\geq\max_{\mathbf{x}_{i}\in A(\mathbf{r}\mid X)}\mathbf{x}_{i}^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus A(\mathbf{r}\mid X)}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime} , with the strict inequality following because 𝐫 ′′ ∈ B ( 𝐫 , δ ) \mathbf{r}^{\prime\prime}\in B(\mathbf{r},\delta) . These inequalities imply that 𝐱 ∗ ∈ A ( 𝐫 ∣ X ) \mathbf{x}^{*}\in A(\mathbf{r}\mid X) . ∎
###### Corollary E.11 (Maximal value is invariant to restriction to non-dominated functionals) .
Let 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} and let X ⊊ ℝ | 𝒮 | X\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. max 𝐱 ∈ X 𝐱 ⊤ 𝐫 = max 𝐱 ∈ ND ( X ) 𝐱 ⊤ 𝐫 \max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}=\max_{\mathbf{x}\in\text{{ND}}\left(X\right)}\mathbf{x}^{\top}\mathbf{r} .
###### Proof.
If X X is empty, holds trivially. Otherwise, apply Lemma E.10 . ∎
###### Lemma E.12 (How non-domination containment affects optimal value) .
Let 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} and let X , X ′ ⊊ ℝ | 𝒮 | X,X^{\prime}\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. 1. If ND ( X ) ⊆ X ′ \text{{ND}}\left(X\right)\subseteq X^{\prime} , then max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≤ max 𝐱 ′ ∈ X ′ 𝐱 ′ ⊤ 𝐫 \max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\leq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r} .
2. If ND ( X ) ⊆ X ′ ⊆ X \text{{ND}}\left(X\right)\subseteq X^{\prime}\subseteq X , then max 𝐱 ∈ X 𝐱 ⊤ 𝐫 = max 𝐱 ′ ∈ X ′ 𝐱 ′ ⊤ 𝐫 \max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}=\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r} .
###### Proof.
Item 1 : max 𝐱 ∈ X 𝐱 ⊤ 𝐫 \displaystyle\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r} = max 𝐱 ∈ ND ( X ) 𝐱 ⊤ 𝐫 \displaystyle=\max_{\mathbf{x}\in\text{{ND}}\left(X\right)}\mathbf{x}^{\top}\mathbf{r} (11) ≤ max 𝐱 ′ ∈ X ′ 𝐱 ′ ⊤ 𝐫 . \displaystyle\leq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r}. (12) Equation 11 follows by Corollary E.11 . Equation 12 follows because ND ( X ) ⊆ X ′ \text{{ND}}\left(X\right)\subseteq X^{\prime} .
Item 2 : by item 1 , max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≤ max 𝐱 ′ ∈ X ′ 𝐱 ′ ⊤ 𝐫 \max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\leq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r} . Since X ′ ⊆ X X^{\prime}\subseteq X , we also have max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐱 ′ ∈ X ′ 𝐱 ′ ⊤ 𝐫 \max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r} , and so equality must hold. ∎
###### Definition E.13 (Non-dominated vector functions) .
Let I ⊆ ℝ I\subseteq\mathbb{R} and let F ⊊ ( ℝ | 𝒮 | ) I F\subsetneq\left(\mathbb{R}^{\left|\mathcal{S}\right|}\right)^{I} be a finite set of vector-valued functions on I I . ND ( F ) ≔ { 𝐟 ∈ F ∣ ∃ γ ∈ I , 𝐫 ∈ ℝ | 𝒮 | : 𝐟 ( γ ) ⊤ 𝐫 > max 𝐟 ′ ∈ F ∖ { 𝐟 } 𝐟 ′ ( γ ) ⊤ 𝐫 } \text{{ND}}\left(F\right)\coloneqq\left\{\mathbf{f}\in F\mid\exists\gamma\in I,\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma)^{\top}\mathbf{r}>\max_{\mathbf{f}^{\prime}\in F\setminus\left\{\mathbf{f}\right\}}\mathbf{f}^{\prime}(\gamma)^{\top}\mathbf{r}\right\} .
###### Remark .
ℱ nd ( s ) = ND ( ℱ ( s ) ) \Fndop(s)=\text{{ND}}\left(\Fop(s)\right) by definition 3.6 .
###### Definition E.14 (Affine transformation of visit distribution sets) .
For notational convenience, we define set-scalar multiplication and set-vector addition on X ⊆ ℝ | 𝒮 | X\subseteq\mathbb{R}^{\left|\mathcal{S}\right|} : for c ∈ ℝ c\in\mathbb{R} , c X ≔ { c 𝐱 ∣ 𝐱 ∈ X } cX\coloneqq\left\{c\mathbf{x}\mid\mathbf{x}\in X\right\} . For 𝐚 ∈ ℝ | 𝒮 | \mathbf{a}\in\mathbb{R}^{\left|\mathcal{S}\right|} , X + 𝐚 ≔ { 𝐱 + 𝐚 ∣ 𝐱 ∈ X } X+\mathbf{a}\coloneqq\left\{\mathbf{x}+\mathbf{a}\mid\mathbf{x}\in X\right\} . Similar operations hold when X X is a set of vector functions ℝ ↦ ℝ | 𝒮 | \mathbb{R}\mapsto\mathbb{R}^{\left|\mathcal{S}\right|} .
###### Lemma E.15 (Invariance of non-domination under positive affine transform) .
1. Let X ⊊ ℝ | 𝒮 | X\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. If 𝐱 ∈ ND ( X ) \mathbf{x}\in\text{{ND}}\left(X\right) , then ∀ c > 0 , 𝐚 ∈ ℝ | 𝒮 | : ( c 𝐱 + 𝐚 ) ∈ ND ( c X + 𝐚 ) \forall c>0,\mathbf{a}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}(c\mathbf{x}+\mathbf{a})\in\text{{ND}}\left(cX+\mathbf{a}\right) .
2. Let I ⊆ ℝ I\subseteq\mathbb{R} and let F ⊊ ( ℝ | 𝒮 | ) I F\subsetneq\left(\mathbb{R}^{\left|\mathcal{S}\right|}\right)^{I} be a finite set of vector-valued functions on I I . If 𝐟 ∈ ND ( F ) \mathbf{f}\in\text{{ND}}\left(F\right) , then ∀ c > 0 , 𝐚 ∈ ℝ | 𝒮 | : ( c 𝐟 + 𝐚 ) ∈ ND ( c F + 𝐚 ) \forall c>0,\mathbf{a}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}(c\mathbf{f}+\mathbf{a})\in\text{{ND}}\left(cF+\mathbf{a}\right) .
###### Proof.
Item 1 : Suppose 𝐱 ∈ ND ( X ) \mathbf{x}\in\text{{ND}}\left(X\right) is strictly optimal for 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} . Then let c > 0 , 𝐚 ∈ ℝ | 𝒮 | c>0,\mathbf{a}\in\mathbb{R}^{\left|\mathcal{S}\right|} be arbitrary, and define b ≔ 𝐚 ⊤ 𝐫 b\coloneqq\mathbf{a}^{\top}\mathbf{r} . 𝐱 ⊤ 𝐫 \displaystyle\mathbf{x}^{\top}\mathbf{r} > max 𝐱 ′ ∈ X ∖ { 𝐱 } 𝐱 ′ ⊤ 𝐫 \displaystyle>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}\right\}}\mathbf{x}^{\prime\top}\mathbf{r} (13) c 𝐱 ⊤ 𝐫 + b \displaystyle c\mathbf{x}^{\top}\mathbf{r}+b > max 𝐱 ′ ∈ X ∖ { 𝐱 } c 𝐱 ′ ⊤ 𝐫 + b \displaystyle>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}\right\}}c\mathbf{x}^{\prime\top}\mathbf{r}+b (14) ( c 𝐱 + 𝐚 ) ⊤ 𝐫 \displaystyle(c\mathbf{x}+\mathbf{a})^{\top}\mathbf{r} > max 𝐱 ′ ∈ X ∖ { 𝐱 } ( c 𝐱 ′ + 𝐚 ) ⊤ 𝐫 \displaystyle>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}\right\}}(c\mathbf{x}^{\prime}+\mathbf{a})^{\top}\mathbf{r} (15) ( c 𝐱 + 𝐚 ) ⊤ 𝐫 \displaystyle(c\mathbf{x}+\mathbf{a})^{\top}\mathbf{r} > max 𝐱 ′′ ∈ ( c X + 𝐚 ) ∖ { c 𝐱 + 𝐚 } 𝐱 ′ ′ ⊤ 𝐫 . \displaystyle>\max_{\mathbf{x}^{\prime\prime}\in\left(cX+\mathbf{a}\right)\setminus\left\{c\mathbf{x}+\mathbf{a}\right\}}\mathbf{x}^{\prime\prime\top}\mathbf{r}. (16) Equation 14 follows because c > 0 c>0 . Equation 15 follows by the definition of b b .
Item 2 : If 𝐟 ∈ ND ( F ) \mathbf{f}\in\text{{ND}}\left(F\right) , then by definition E.13 , there exist γ ∈ I , 𝐫 ∈ ℝ | 𝒮 | \gamma\in I,\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} such that 𝐟 ( γ ) ⊤ 𝐫 > max 𝐟 ′ ∈ F ∖ { 𝐟 } 𝐟 ′ ( γ ) ⊤ 𝐫 . \displaystyle\mathbf{f}(\gamma)^{\top}\mathbf{r}>\max_{\mathbf{f}^{\prime}\in F\setminus\left\{\mathbf{f}\right\}}\mathbf{f}^{\prime}(\gamma)^{\top}\mathbf{r}. (17)
Apply item 1 to conclude ( c 𝐟 ( γ ) + 𝐚 ) ⊤ 𝐫 > max ( c 𝐟 ′ + 𝐚 ) ∈ ( c F + 𝐚 ) ∖ { c 𝐟 + 𝐚 } ( c 𝐟 ′ ( γ ) + 𝐚 ) ⊤ 𝐫 . \displaystyle(c\mathbf{f}(\gamma)+\mathbf{a})^{\top}\mathbf{r}>\max_{(c\mathbf{f}^{\prime}+\mathbf{a})\in(cF+\mathbf{a})\setminus\left\{c\mathbf{f}+\mathbf{a}\right\}}(c\mathbf{f}^{\prime}(\gamma)+\mathbf{a})^{\top}\mathbf{r}. (18)
Therefore, ( c 𝐟 + 𝐚 ) ∈ ND ( c F + 𝐚 ) (c\mathbf{f}+\mathbf{a})\in\text{{ND}}\left(cF+\mathbf{a}\right) . ∎
#### E.1.2 Inequalities which hold under most reward function distributions
See 6.5
###### Lemma E.16 (Helper lemma for demonstrating ≥ most : 𝔇 any \geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}} ) .
Let 𝔇 ⊆ Δ ( ℝ | 𝒮 | ) \mathfrak{D}\subseteq\Delta(\mathbb{R}^{\left|\mathcal{S}\right|}) . If ∃ ϕ ∈ S | 𝒮 | \exists\phi\in S_{\left|\mathcal{S}\right|} such that for all 𝒟 ∈ 𝔇 \mathcal{D}\in\mathfrak{D} , f 1 ( 𝒟 ) < f 2 ( 𝒟 ) f_{1}\left(\mathcal{D}\right)<f_{2}\left(\mathcal{D}\right) implies that f 1 ( ϕ ⋅ 𝒟 ) > f 2 ( ϕ ⋅ 𝒟 ) f_{1}\left(\phi\cdot\mathcal{D}\right)>f_{2}\left(\phi\cdot\mathcal{D}\right) , then f 1 ( 𝒟 ) ≥ most : 𝔇 f 2 ( 𝒟 ) f_{1}(\mathcal{D})\geq_{\text{{most}}\text{: }\mathfrak{D}}f_{2}(\mathcal{D}) .
###### Proof.
Since ϕ \phi does not belong to the stabilizer of S | 𝒮 | S_{\left|\mathcal{S}\right|} , ϕ \phi acts injectively on S | 𝒮 | ⋅ 𝒟 S_{\left|\mathcal{S}\right|}\cdot\mathcal{D} . By assumption on ϕ \phi , the image of { 𝒟 ′ ∈ S | 𝒮 | ⋅ 𝒟 ∣ f 1 ( 𝒟 ′ ) < f 2 ( 𝒟 ′ ) } \{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})<f_{2}(\mathcal{D}^{\prime})\} under ϕ \phi is a subset of { 𝒟 ′ ∈ S | 𝒮 | ⋅ 𝒟 ∣ f 1 ( 𝒟 ′ ) > f 2 ( 𝒟 ′ ) } \{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})>f_{2}(\mathcal{D}^{\prime})\} . Since ϕ \phi is injective, | { 𝒟 ′ ∈ S | 𝒮 | ⋅ 𝒟 ∣ f 1 ( 𝒟 ′ ) < f 2 ( 𝒟 ′ ) } | ≤ | { 𝒟 ′ ∈ S | 𝒮 | ⋅ 𝒟 ∣ f 1 ( 𝒟 ′ ) > f 2 ( 𝒟 ′ ) } | \left|\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})<f_{2}(\mathcal{D}^{\prime})\}\right|\leq\left|\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})>f_{2}(\mathcal{D}^{\prime})\}\right| . f 1 ( 𝒟 ) ≥ most : 𝔇 f 2 ( 𝒟 ) f_{1}(\mathcal{D})\geq_{\text{{most}}\text{: }\mathfrak{D}}f_{2}(\mathcal{D}) by definition 6.5 . ∎
###### Lemma E.17 (A helper result for expectations of functions) .
Let B 1 , … , B n ⊊ ℝ | 𝒮 | B_{1},\ldots,B_{n}\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite and let 𝔇 ⊆ Δ ( ℝ | 𝒮 | ) \mathfrak{D}\subseteq\Delta(\mathbb{R}^{\left|\mathcal{S}\right|}) . Suppose f f is a function of the form f ( B 1 , … , B n ∣ 𝒟 ) = 𝔼 𝐫 ∼ 𝒟 [ g ( max 𝐛 1 ∈ B 1 𝐛 1 ⊤ 𝐫 , … , max 𝐛 n ∈ B n 𝐛 n ⊤ 𝐫 ) ] \displaystyle f\left(B_{1},\ldots,B_{n}\mid\mathcal{D}\right)=\opE_{\mathbf{r}\sim\mathcal{D}}\left[g\left(\max_{\mathbf{b}_{1}\in B_{1}}\mathbf{b}_{1}^{\top}\mathbf{r},\ldots,\max_{\mathbf{b}_{n}\in B_{n}}\mathbf{b}_{n}^{\top}\mathbf{r}\right)\right] (19) for some function g g , and that f f is well-defined for all 𝒟 ∈ 𝔇 \mathcal{D}\in\mathfrak{D} . Let ϕ \phi be a state permutation. Then f ( B 1 , … , B n ∣ 𝒟 ) = f ( ϕ ⋅ B 1 , … , ϕ ⋅ B n ∣ ϕ ⋅ 𝒟 ) . f\left(B_{1},\ldots,B_{n}\mid\mathcal{D}\right)=f\left(\phi\cdot B_{1},\ldots,\phi\cdot B_{n}\mid\phi\cdot\mathcal{D}\right). (20)
###### Proof.