Optimal Policies Tend to Seek Power — part 7/16

Cleaned-text code points [94206, 108627). Bibliography omitted here; source.md includes it.

Let distribution 𝒟 \mathcal{D} have probability measure F F , and let ϕ ⋅ 𝒟 \phi\cdot\mathcal{D} have probability measure F ϕ F_{\phi} . f ⁡ ( B 1 , … , B n ∣ 𝒟 ) \displaystyle f\left(B_{1},\ldots,B_{n}\mid\mathcal{D}\right) (21) ≔ \displaystyle\coloneqq{} 𝔼 𝐫 ∼ 𝒟 [ g ⁡ ( max 𝐛 1 ∈ B 1 ⁡ 𝐛 1 ⊤ ​ 𝐫 , … , max 𝐛 n ∈ B n ⁡ 𝐛 n ⊤ ​ 𝐫 ) ] \displaystyle\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] (22) ≔ \displaystyle\coloneqq{} ∫ ℝ | 𝒮 | g ⁡ ( max 𝐛 1 ∈ B 1 ⁡ 𝐛 1 ⊤ ​ 𝐫 , … , max 𝐛 n ∈ B n ⁡ 𝐛 n ⊤ ​ 𝐫 ) ​ d ⁡ F ⁡ ( 𝐫 ) \displaystyle\int_{\mathbb{R}^{\left|\mathcal{S}\right|}}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)\dif F(\mathbf{r}) (23) = \displaystyle={} ∫ ℝ | 𝒮 | g ⁡ ( max 𝐛 1 ∈ B 1 ⁡ 𝐛 1 ⊤ ​ 𝐫 , … , max 𝐛 n ∈ B n ⁡ 𝐛 n ⊤ ​ 𝐫 ) ​ d ⁡ F ϕ ​ ( 𝐏 ϕ ​ 𝐫 ) \displaystyle\int_{\mathbb{R}^{\left|\mathcal{S}\right|}}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)\dif F_{\phi}(\mathbf{P}_{\phi}\mathbf{r}) (24) = \displaystyle={} ∫ ℝ | 𝒮 | g ⁡ ( max 𝐛 1 ∈ B 1 ⁡ 𝐛 1 ⊤ ​ ( 𝐏 ϕ − 1 ​ 𝐫 ′ ) , … , max 𝐛 n ∈ B n ⁡ 𝐛 n ⊤ ​ ( 𝐏 ϕ − 1 ​ 𝐫 ′ ) ) ​ | det 𝐏 ϕ | ​ d ⁡ F ϕ ​ ( 𝐫 ′ ) \displaystyle\int_{\mathbb{R}^{\left|\mathcal{S}\right|}}g\left(\max_{\mathbf{b}_{1}\in B_{1}}\mathbf{b}_{1}^{\top}\left(\mathbf{P}_{\phi}^{-1}\mathbf{r}^{\prime}\right),\ldots,\max_{\mathbf{b}_{n}\in B_{n}}\mathbf{b}_{n}^{\top}\left(\mathbf{P}_{\phi}^{-1}\mathbf{r}^{\prime}\right)\right)\left|\det\mathbf{P}_{\phi}\right|\dif F_{\phi}(\mathbf{r}^{\prime}) (25) = \displaystyle={} ∫ ℝ | 𝒮 | g ⁡ ( max 𝐛 1 ∈ B 1 ⁡ ( 𝐏 ϕ ​ 𝐛 1 ) ⊤ ​ 𝐫 ′ , … , max 𝐛 n ∈ B n ⁡ ( 𝐏 ϕ ​ 𝐛 n ) ⊤ ​ 𝐫 ′ ) ​ d ⁡ F ϕ ​ ( 𝐫 ′ ) \displaystyle\int_{\mathbb{R}^{\left|\mathcal{S}\right|}}g\left(\max_{\mathbf{b}_{1}\in B_{1}}\left(\mathbf{P}_{\phi}\mathbf{b}_{1}\right)^{\top}\mathbf{r}^{\prime},\ldots,\max_{\mathbf{b}_{n}\in B_{n}}\left(\mathbf{P}_{\phi}\mathbf{b}_{n}\right)^{\top}\mathbf{r}^{\prime}\right)\dif F_{\phi}(\mathbf{r}^{\prime}) (26) = \displaystyle={} ∫ ℝ | 𝒮 | g ⁡ ( max 𝐛 1 ′ ∈ ϕ ⋅ B 1 ⁡ 𝐛 1 ′ ⁣ ⊤ ​ 𝐫 ′ , … , max 𝐛 n ′ ∈ ϕ ⋅ B n ⁡ 𝐛 n ′ ⁣ ⊤ ​ 𝐫 ′ ) ​ d ⁡ F ϕ ​ ( 𝐫 ′ ) \displaystyle\int_{\mathbb{R}^{\left|\mathcal{S}\right|}}g\left(\max_{\mathbf{b}_{1}^{\prime}\in\phi\cdot B_{1}}\mathbf{b}_{1}^{\prime\top}\mathbf{r}^{\prime},\ldots,\max_{\mathbf{b}_{n}^{\prime}\in\phi\cdot B_{n}}\mathbf{b}_{n}^{\prime\top}\mathbf{r}^{\prime}\right)\dif F_{\phi}(\mathbf{r}^{\prime}) (27) ≕ \displaystyle\eqqcolon{} f ⁡ ( ϕ ⋅ B 1 , … , ϕ ⋅ B n ∣ ϕ ⋅ 𝒟 ) . \displaystyle f\left(\phi\cdot B_{1},\ldots,\phi\cdot B_{n}\mid\phi\cdot\mathcal{D}\right). (28)

Equation 24 follows by the definition of F ϕ F_{\phi} ( definition 6.3 ). Equation 25 follows by substituting 𝐫 ′ ≔ 𝐏 ϕ ​ 𝐫 \mathbf{r}^{\prime}\coloneqq\mathbf{P}_{\phi}\mathbf{r} . Equation 26 follows from the fact that all permutation matrices have unitary determinant and are orthogonal (and so ( 𝐏 ϕ − 1 ) ⊤ = 𝐏 ϕ (\mathbf{P}_{\phi}^{-1})^{\top}=\mathbf{P}_{\phi} ). ∎

###### Definition E.18 (Support of 𝒟 any \mathcal{D}_{\text{any}} ) .

Let 𝒟 any \mathcal{D}_{\text{any}} be any reward function distribution. supp ⁡ ( 𝒟 any ) \optSupp(\mathcal{D}_{\text{any}}) is the smallest closed subset of ℝ | 𝒮 | \mathbb{R}^{\left|\mathcal{S}\right|} whose complement has measure zero under 𝒟 any \mathcal{D}_{\text{any}} .

###### Definition E.19 (Linear functional optimality probability) .

For finite A , B ⊊ ℝ | 𝒮 | A,B\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} , the probability under 𝒟 any \mathcal{D}_{\text{any}} that A A is optimal over B B is p 𝒟 any ​ ( A ≥ B ) ≔ ℙ 𝐫 ∼ 𝒟 any ( max 𝐚 ∈ A ⁡ 𝐚 ⊤ ​ 𝐫 ≥ max 𝐛 ∈ B ⁡ 𝐛 ⊤ ​ 𝐫 ) p_{\mathcal{D}_{\text{any}}}\left(A\geq B\right)\coloneqq\Prb\nolimits_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\geq\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right) .

###### Proposition E.20 (Non-dominated linear functionals and their optimality probability) .

Let A ⊊ ℝ | 𝒮 | A\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite. If ∃ b < c : [ b , c ] | 𝒮 | ⊆ supp ⁡ ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}[b,c]^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) , then 𝐚 ∈ ND ​ ( A ) \mathbf{a}\in\text{{ND}}\left(A\right) implies that 𝐚 \mathbf{a} is strictly optimal for a set of reward functions with positive measure under 𝒟 any \mathcal{D}_{\text{any}} .

###### Proof.

Suppose ∃ b < c : [ b , c ] | 𝒮 | ⊆ supp ⁡ ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}[b,c]^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) . If 𝐚 ∈ ND ​ ( A ) \mathbf{a}\in\text{{ND}}\left(A\right) , then let 𝐫 \mathbf{r} be such that 𝐚 ⊤ ​ 𝐫 > max 𝐚 ′ ∈ A ∖ { 𝐚 } ⁡ 𝐚 ′ ⁣ ⊤ ​ 𝐫 \mathbf{a}^{\top}\mathbf{r}>\max_{\mathbf{a}^{\prime}\in A\setminus\left\{\mathbf{a}\right\}}\mathbf{a}^{\prime\top}\mathbf{r} . For a 1 > 0 , a 2 ∈ ℝ a_{1}>0,a_{2}\in\mathbb{R} , positively affinely transform 𝐫 ′ ≔ a 1 ​ 𝐫 + a 2 ​ 𝟏 \mathbf{r}^{\prime}\coloneqq a_{1}\mathbf{r}+a_{2}\mathbf{1} (where 𝟏 ∈ ℝ | 𝒮 | \mathbf{1}\in\mathbb{R}^{\left|\mathcal{S}\right|} is the all-ones vector) so that 𝐫 ′ ∈ ( b , c ) | 𝒮 | \mathbf{r}^{\prime}\in(b,c)^{\left|\mathcal{S}\right|} .

Note that 𝐚 \mathbf{a} is still strictly optimal for 𝐫 ′ \mathbf{r}^{\prime} : 𝐚 ⊤ ​ 𝐫 > max 𝐚 ′ ∈ A ∖ { 𝐚 } ⁡ 𝐚 ′ ⁣ ⊤ ​ 𝐫 ⇔ 𝐚 ⊤ ​ 𝐫 ′ > max 𝐚 ′ ∈ A ∖ { 𝐚 } ⁡ 𝐚 ′ ⁣ ⊤ ​ 𝐫 ′ . \mathbf{a}^{\top}\mathbf{r}>\max_{\mathbf{a}^{\prime}\in A\setminus\left\{\mathbf{a}\right\}}\mathbf{a}^{\prime\top}\mathbf{r}\iff\mathbf{a}^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{a}^{\prime}\in A\setminus\left\{\mathbf{a}\right\}}\mathbf{a}^{\prime\top}\mathbf{r}^{\prime}. (29)

Furthermore, by the continuity of both terms on the right-hand side of eq. 29 , 𝐚 \mathbf{a} is strictly optimal for reward functions in some open neighborhood N N of 𝐫 ′ \mathbf{r}^{\prime} . Let N ′ ≔ N ∩ ( b , c ) | 𝒮 | N^{\prime}\coloneqq N\cap(b,c)^{\left|\mathcal{S}\right|} . N ′ N^{\prime} is still open in ℝ | 𝒮 | \mathbb{R}^{\left|\mathcal{S}\right|} since it is the intersection of two open sets N N and ( b , c ) | 𝒮 | (b,c)^{\left|\mathcal{S}\right|} .

𝒟 any \mathcal{D}_{\text{any}} must assign positive probability measure to all open sets in its support; otherwise, its support would exclude these zero-measure sets by definition E.18 . Therefore, 𝒟 any \mathcal{D}_{\text{any}} assigns positive probability to N ′ ⊆ supp ⁡ ( 𝒟 any ) N^{\prime}\subseteq\optSupp(\mathcal{D}_{\text{any}}) . ∎

###### Lemma E.21 (Expected value of similar linear functional sets) .

Let A , B ⊊ ℝ | 𝒮 | A,B\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite, let A ′ A^{\prime} be such that ND ​ ( A ) ⊆ A ′ ⊆ A \text{{ND}}\left(A\right)\subseteq A^{\prime}\subseteq A , and let g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} be an increasing function. If B B contains a copy B ′ B^{\prime} of A ′ A^{\prime} via ϕ \phi , then 𝔼 𝐫 ∼ 𝒟 bound [ g ⁡ ( max 𝐚 ∈ A ⁡ 𝐚 ⊤ ​ 𝐫 ) ] ≤ 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐛 ∈ B ⁡ 𝐛 ⊤ ​ 𝐫 ) ] . \opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]\leq\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (30)

If ND ​ ( B ) ∖ B ′ \text{{ND}}\left(B\right)\setminus B^{\prime} is empty, then eq. 30 is an equality. If ND ​ ( B ) ∖ B ′ \text{{ND}}\left(B\right)\setminus B^{\prime} is non-empty, g g is strictly increasing, and ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ⁡ ( 𝒟 bound ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{bound}}) , then eq. 30 is strict.

###### Proof.

Because g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} is increasing, it is measurable (as is max \max ). Therefore, the relevant expectations exist for all 𝒟 bound \mathcal{D}_{\text{bound}} . 𝔼 𝐫 ∼ 𝒟 bound [ g ⁡ ( max 𝐚 ∈ A ⁡ 𝐚 ⊤ ​ 𝐫 ) ] \displaystyle\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] = 𝔼 𝐫 ∼ 𝒟 bound [ g ⁡ ( max 𝐚 ∈ A ′ ⁡ 𝐚 ⊤ ​ 𝐫 ) ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A^{\prime}}\mathbf{a}^{\top}\mathbf{r}\right)\right] (31) = 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐚 ∈ ϕ ⋅ A ′ ⁡ 𝐚 ⊤ ​ 𝐫 ) ] \displaystyle=\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in\phi\cdot A^{\prime}}\mathbf{a}^{\top}\mathbf{r}\right)\right] (32) = 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐛 ∈ B ′ ⁡ 𝐛 ⊤ ​ 𝐫 ) ] \displaystyle=\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B^{\prime}}\mathbf{b}^{\top}\mathbf{r}\right)\right] (33) ≤ 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐛 ∈ B ⁡ 𝐛 ⊤ ​ 𝐫 ) ] . \displaystyle\leq\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (34) Equation 31 holds because ∀ 𝐫 ∈ ℝ | 𝒮 | : max 𝐚 ∈ A ⁡ 𝐚 ⊤ ​ 𝐫 = max 𝐚 ∈ A ′ ⁡ 𝐚 ⊤ ​ 𝐫 \forall\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}=\max_{\mathbf{a}\in A^{\prime}}\mathbf{a}^{\top}\mathbf{r} by Lemma E.12 ’s item 2 with X ≔ A X\coloneqq A , X ′ ≔ A ′ X^{\prime}\coloneqq A^{\prime} . Equation 32 holds by Lemma E.17 . Equation 33 holds by the definition of B ′ B^{\prime} . Furthermore, our assumption on ϕ \phi guarantees that B ′ ⊆ B B^{\prime}\subseteq B . Therefore, max 𝐛 ∈ B ′ ⁡ 𝐛 ⊤ ​ 𝐫 ≤ max 𝐛 ∈ B ⁡ 𝐛 ⊤ ​ 𝐫 \max_{\mathbf{b}\in B^{\prime}}\mathbf{b}^{\top}\mathbf{r}\leq\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r} , and so eq. 34 holds by the fact that g g is an increasing function. Then eq. 30 holds.

If ND ​ ( B ) ∖ B ′ \text{{ND}}\left(B\right)\setminus B^{\prime} is empty, then ND ​ ( B ) ⊆ B ′ \text{{ND}}\left(B\right)\subseteq B^{\prime} . By assumption, B ′ ⊆ B B^{\prime}\subseteq B . Then apply Lemma E.12 item 2 with X ≔ B X\coloneqq B , X ′ ≔ B ′ X^{\prime}\coloneqq B^{\prime} in order to conclude that eq. 34 is an equality. Then eq. 30 is also an equality.

Suppose that g g is strictly increasing, ND ​ ( B ) ∖ B ′ \text{{ND}}\left(B\right)\setminus B^{\prime} is non-empty, and ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ⁡ ( 𝒟 bound ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{bound}}) . Let 𝐱 ∈ ND ​ ( B ) ∖ B ′ \mathbf{x}\in\text{{ND}}\left(B\right)\setminus B^{\prime} . 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐛 ∈ B ′ ⁡ 𝐛 ⊤ ​ 𝐫 ) ] \displaystyle\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B^{\prime}}\mathbf{b}^{\top}\mathbf{r}\right)\right] < 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐚 ∈ B ′ ∪ { 𝐱 } ⁡ 𝐛 ⊤ ​ 𝐫 ) ] \displaystyle<\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in B^{\prime}\cup\left\{\mathbf{x}\right\}}\mathbf{b}^{\top}\mathbf{r}\right)\right] (35) ≤ 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ⁡ ( max 𝐛 ∈ B ⁡ 𝐛 ⊤ ​ 𝐫 ) ] . \displaystyle\leq\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (36)

𝐱 \mathbf{x} is strictly optimal for a positive-probability subset of supp ⁡ ( 𝒟 bound ) \optSupp(\mathcal{D}_{\text{bound}}) by Proposition E.20 . Since g g is strictly increasing, eq. 35 is strict. Therefore, we conclude that eq. 30 is strict. ∎

###### Lemma E.22 (For continuous iid distributions 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} , ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ⁡ ( 𝒟 X ​ - iid ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{X\text{-}\textsc{iid}}) ) .

###### Proof.

𝒟 X ​ - iid ≔ X | 𝒮 | \mathcal{D}_{X\text{-}\textsc{iid}}\coloneqq X^{\left|\mathcal{S}\right|} . Since the state reward distribution X X is continuous, X X must have support on some open interval ( b , c ) (b,c) . Since 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} is iid across states, ( b , c ) | 𝒮 | ⊆ supp ⁡ ( 𝒟 X ​ - iid ) (b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{X\text{-}\textsc{iid}}) . ∎

###### Definition E.23 (Bounded, continuous iid reward) .

𝔇 c/b/ iid \mathfrak{D}_{\textsc{c/b/}\textsc{iid}} is the set of 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} which equal X | 𝒮 | X^{\left|\mathcal{S}\right|} for some continuous, bounded-support distribution X X over ℝ \mathbb{R} .

###### Lemma E.24 (Expectation superiority lemma) .

Let A , B ⊊ ℝ | 𝒮 | A,B\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite and let g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} be an increasing function. If B B contains a copy B ′ B^{\prime} of ND ​ ( A ) \text{{ND}}\left(A\right) via ϕ \phi , then 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] ≤ most : 𝔇 bound 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] . \displaystyle\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (37)

Furthermore, if g g is strictly increasing and ND ​ ( B ) ∖ ϕ ⋅ ND ​ ( A ) \text{{ND}}\left(B\right)\setminus\phi\cdot\text{{ND}}\left(A\right) is non-empty, then eq. 37 is strict for all 𝒟 X ​ - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} . In particular, 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] ≱ most : 𝔇 bound 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] .

###### Proof.

Because g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} is increasing, it is measurable (as is max \max ). Therefore, the relevant expectations exist for all 𝒟 bound \mathcal{D}_{\text{bound}} .