Optimal Policies Tend to Seek Power — part 12/16
Cleaned-text code points [171009, 186895). Bibliography omitted here; source.md includes it.
For γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) , let f γ ∗ ( 𝐫 ) ≔ max 𝐟 ∈ ℱ nd ( s ) 1 − γ ∗ γ ∗ ( 𝐟 ( γ ∗ ) − 𝐞 s ) ⊤ 𝐫 f_{\gamma^{*}}(\mathbf{r})\coloneqq\max_{\mathbf{f}\in\Fndop(s)}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}(\gamma^{*})-\mathbf{e}_{s}\right)^{\top}\mathbf{r} . For any sequence γ n → γ \gamma_{n}\to\gamma , ( f γ n ) n = 1 ∞ \left(f_{\gamma_{n}}\right)_{n=1}^{\infty} is a sequence of functions which are piecewise linear on 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} , which means they are continuous and therefore measurable. Since Lemma E.4 shows that each 𝐟 ∈ ℱ nd ( s ) \mathbf{f}\in\Fndop(s) is multivariate rational on γ ∗ \gamma^{*} (and therefore continuous on γ ∗ \gamma^{*} ), { f γ n } n = 1 ∞ \left\{f_{\gamma_{n}}\right\}_{n=1}^{\infty} converges pointwise to limit function f γ f_{\gamma} . Furthermore, | V R ∗ ( s , γ n ) − R ( s ) | ≤ γ 1 − γ n ‖ R ‖ ∞ \left|V^{*}_{R}\left(s,\gamma_{n}\right)-R(s)\right|\leq\frac{\gamma}{1-\gamma_{n}}\left\lVert R\right\rVert_{\infty} , and so | f γ n ( 𝐫 ) | = | 1 − γ n γ n ( V R ∗ ( s , γ n ) − R ( s ) ) | ≤ g ( 𝐫 ) ≤ ‖ 𝐫 ‖ ∞ ≕ g ( 𝐫 ) \left|f_{\gamma_{n}}(\mathbf{r})\right|=\left|\frac{1-\gamma_{n}}{\gamma_{n}}(V^{*}_{R}\left(s,\gamma_{n}\right)-R(s))\right|\leq g(\mathbf{r})\leq\left\lVert\mathbf{r}\right\rVert_{\infty}\eqqcolon g(\mathbf{r}) , which is measurable. Therefore, apply Lebesgue’s dominated convergence theorem to conclude that eq. 132 holds. Equation 133 holds because max \max is a continuous function. ∎
###### Lemma E.44 (Lemma for Power superiority) .
Let Δ 1 , Δ 2 ∈ Δ ( 𝒮 ) \Delta_{1},\Delta_{2}\in\Delta\left(\mathcal{S}\right) be state probability distributions. For i = 1 , 2 i=1,2 , let F Δ i ≔ { γ − 1 𝔼 s i ∼ Δ i [ 𝐟 π , s i − 𝐞 s i ] ∣ π ∈ Π } F_{\Delta_{i}}\coloneqq\left\{\gamma^{-1}\opE_{s_{i}\sim\Delta_{i}}\left[\mathbf{f}^{\pi,s_{i}}-\mathbf{e}_{s_{i}}\right]\mid\pi\in\Pi\right\} . Suppose F Δ 2 F_{\Delta_{2}} contains a copy of ND ( F Δ 1 ) \text{{ND}}\left(F_{\Delta_{1}}\right) via ϕ \phi . Then ∀ γ ∈ [ 0 , 1 ] : 𝔼 s 1 ∼ Δ 1 [ Power 𝒟 bound ( s 1 , γ ) ] ≤ most : 𝔇 bound 𝔼 s 2 ∼ Δ 2 [ Power 𝒟 bound ( s 2 , γ ) ] \forall\gamma\in[0,1]\mathrel{\mathop{\ordinarycolon}}\opE_{s_{1}\sim\Delta_{1}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{1},\gamma\right)\right]\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{s_{2}\sim\Delta_{2}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{2},\gamma\right)\right] .
If ND ( F Δ 2 ) ∖ ϕ ⋅ ND ( F Δ 1 ) \text{{ND}}\left(F_{\Delta_{2}}\right)\setminus\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right) is non-empty, then for all γ ∈ ( 0 , 1 ) \gamma\in(0,1) , the inequality is strict for all 𝒟 X - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} and 𝔼 s 1 ∼ Δ 1 [ Power 𝒟 bound ( s 1 , γ ) ] ≱ most : 𝔇 bound 𝔼 s 2 ∼ Δ 2 [ Power 𝒟 bound ( s 2 , γ ) ] \opE_{s_{1}\sim\Delta_{1}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{1},\gamma\right)\right]\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{s_{2}\sim\Delta_{2}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{2},\gamma\right)\right] .
These results also hold when replacing F Δ i F_{\Delta_{i}} with F Δ i ∗ ≔ { 𝔼 s i ∼ Δ i [ 𝐟 π , s i ] ∣ π ∈ Π } F_{\Delta_{i}}^{*}\coloneqq\left\{\opE_{s_{i}\sim\Delta_{i}}\left[\mathbf{f}^{\pi,s_{i}}\right]\mid\pi\in\Pi\right\} for i = 1 , 2 i=1,2 .
###### Proof.
ϕ ⋅ ND ( Norm ( F Δ 1 , γ ) ) \displaystyle\phi\cdot\text{{ND}}\left(\text{{Norm}}\left(F_{\Delta_{1}},\gamma\right)\right) ⊆ ϕ ⋅ Norm ( ND ( F Δ 1 ) , γ ) \displaystyle\subseteq\phi\cdot\text{{Norm}}\left(\text{{ND}}\left(F_{\Delta_{1}}\right),\gamma\right) (134) ≔ { 𝐏 ϕ lim γ ∗ → γ ( 1 − γ ∗ ) 𝐟 ( γ ∗ ) ∣ 𝐟 ∈ ND ( F Δ 1 ) } \displaystyle\coloneqq\left\{\mathbf{P}_{\phi}\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}(\gamma^{*})\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\} (135) = { lim γ ∗ → γ ( 1 − γ ∗ ) 𝐏 ϕ 𝐟 ( γ ∗ ) ∣ 𝐟 ∈ ND ( F Δ 1 ) } \displaystyle=\left\{\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{P}_{\phi}\mathbf{f}(\gamma^{*})\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\} (136) = { lim γ ∗ → γ ( 1 − γ ∗ ) 𝐟 ( γ ∗ ) ∣ 𝐟 ∈ F sub ′ } \displaystyle=\left\{\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}(\gamma^{*})\mid\mathbf{f}\in F_{\text{sub}}^{\prime}\right\} (137) ⊆ { lim γ ∗ → γ ( 1 − γ ∗ ) 𝐟 ( γ ∗ ) ∣ 𝐟 ∈ F Δ 2 } \displaystyle\subseteq\left\{\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}(\gamma^{*})\mid\mathbf{f}\in F_{\Delta_{2}}\right\} (138) ≕ Norm ( F Δ 2 , γ ) . \displaystyle\eqqcolon\text{{Norm}}\left(F_{\Delta_{2}},\gamma\right). (139) Equation 134 follows by Lemma E.42 . Equation 136 follows because 𝐏 ϕ \mathbf{P}_{\phi} is a continuous linear operator. Equation 138 follows by assumption. 𝔼 s 1 ∼ Δ 1 [ Power 𝒟 bound ( s 1 , γ ) ] \displaystyle\opE_{s_{1}\sim\Delta_{1}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{1},\gamma\right)\right] ≔ 𝔼 s 1 ∼ Δ 1 , 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ π ∈ Π 1 − γ ∗ γ ∗ ( 𝐟 π , s 1 ( γ ∗ ) − 𝐞 s 1 ) ⊤ 𝐫 ] \displaystyle\coloneqq\opE_{\begin{subarray}{c}s_{1}\sim\Delta_{1},\\ \mathbf{r}\sim\mathcal{D}_{\text{bound}}\end{subarray}}\left[\max_{\pi\in\Pi}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}^{\pi,s_{1}}(\gamma^{*})-\mathbf{e}_{s_{1}}\right)^{\top}\mathbf{r}\right] (140) = 𝔼 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ π ∈ Π 1 − γ ∗ γ ∗ 𝔼 s 1 ∼ Δ 1 [ 𝐟 π , s 1 ( γ ∗ ) − 𝐞 s 1 ] ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\pi\in\Pi}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\opE_{s_{1}\sim\Delta_{1}}\left[\mathbf{f}^{\pi,s_{1}}(\gamma^{*})-\mathbf{e}_{s_{1}}\right]^{\top}\mathbf{r}\right] (141) = 𝔼 𝐫 ∼ 𝒟 bound [ max 𝐝 ∈ Norm ( F Δ 1 , γ ) 𝐝 ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{d}\in\text{{Norm}}\left(F_{\Delta_{1}},\gamma\right)}\mathbf{d}^{\top}\mathbf{r}\right] (142) = 𝔼 𝐫 ∼ 𝒟 bound [ max 𝐝 ∈ ND ( Norm ( F Δ 1 , γ ) ) 𝐝 ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{d}\in\text{{ND}}\left(\text{{Norm}}\left(F_{\Delta_{1}},\gamma\right)\right)}\mathbf{d}^{\top}\mathbf{r}\right] (143) ≤ most : 𝔇 bound 𝔼 𝐫 ∼ 𝒟 bound [ max 𝐝 ∈ Norm ( F Δ 2 , γ ) 𝐝 ⊤ 𝐫 ] \displaystyle\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{d}\in\text{{Norm}}\left(F_{\Delta_{2}},\gamma\right)}\mathbf{d}^{\top}\mathbf{r}\right] (144) = 𝔼 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ π ∈ Π 1 − γ ∗ γ ∗ 𝔼 s 2 ∼ Δ 2 [ 𝐟 π , s 2 ( γ ∗ ) − 𝐞 s 2 ] ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\pi\in\Pi}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\opE_{s_{2}\sim\Delta_{2}}\left[\mathbf{f}^{\pi,s_{2}}(\gamma^{*})-\mathbf{e}_{s_{2}}\right]^{\top}\mathbf{r}\right] (145) = 𝔼 s 2 ∼ Δ 2 , 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ π ∈ Π 1 − γ ∗ γ ∗ ( 𝐟 π , s 2 ( γ ∗ ) − 𝐞 s 2 ) ⊤ 𝐫 ] \displaystyle=\opE_{\begin{subarray}{c}s_{2}\sim\Delta_{2},\\ \mathbf{r}\sim\mathcal{D}_{\text{bound}}\end{subarray}}\left[\max_{\pi\in\Pi}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}^{\pi,s_{2}}(\gamma^{*})-\mathbf{e}_{s_{2}}\right)^{\top}\mathbf{r}\right] (146) ≕ 𝔼 s 2 ∼ Δ 2 [ Power 𝒟 bound ( s 2 , γ ) ] . \displaystyle\eqqcolon\opE_{s_{2}\sim\Delta_{2}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{2},\gamma\right)\right]. (147)
Equation 140 and eq. 147 follow by Lemma E.43 . Equation 141 and eq. 146 follow because each R R has a stationary deterministic optimal policy π ∈ Π ∗ ( R , γ ) ⊆ Π \pi\in\Pi^{*}\left(R,\gamma\right)\subseteq\Pi which simultaneously achieves optimal value at all states. Equation 143 follows by Corollary E.11 .
Apply Lemma E.24 with A ≔ Norm ( F Δ 1 , γ ) , B ≔ Norm ( F Δ 2 , γ ) A\coloneqq\text{{Norm}}\left(F_{\Delta_{1}},\gamma\right),B\coloneqq\text{{Norm}}\left(F_{\Delta_{2}},\gamma\right) , g g the identity function, and involution ϕ \phi (satisfying ϕ ⋅ ND ( A ) ⊆ B \phi\cdot\text{{ND}}\left(A\right)\subseteq B by eq. 139 ) in order to conclude that eq. 144 holds.
Suppose that ND ( F Δ 2 ) ∖ ϕ ⋅ ND ( F Δ 1 ) \text{{ND}}\left(F_{\Delta_{2}}\right)\setminus\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right) is non-empty; let F sub ′ ≔ ϕ ⋅ ND ( F Δ 1 ) F_{\text{sub}}^{\prime}\coloneqq\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right) . Lemma E.31 shows that for all γ ∈ ( 0 , 1 ) \gamma\in(0,1) , ND ( F Δ 2 ( γ ) ) ∖ F sub ′ ( γ ) \text{{ND}}\left(F_{\Delta_{2}}(\gamma)\right)\setminus F_{\text{sub}}^{\prime}(\gamma) is non-empty. Lemma E.15 item 1 then implies that ND ( B ) ∖ ϕ ⋅ A = 1 − γ γ ( ND ( F Δ 2 ( γ ) ) − 𝐞 s ) ∖ ( 1 − γ γ F sub ′ ( γ ) ) \text{{ND}}\left(B\right)\setminus\phi\cdot A=\frac{1-\gamma}{\gamma}\left(\text{{ND}}\left(F_{\Delta_{2}}(\gamma)\right)-\mathbf{e}_{s}\right)\setminus\left(\frac{1-\gamma}{\gamma}F^{\prime}_{\text{sub}}(\gamma)\right) is non-empty. Then Lemma E.24 implies that for all γ ∈ ( 0 , 1 ) \gamma\in(0,1) , eq. 144 is strict for all 𝒟 X - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} and 𝔼 s 1 ∼ Δ 1 [ Power 𝒟 bound ( s 1 , γ ) ] ≱ most : 𝔇 bound 𝔼 s 2 ∼ Δ 2 [ Power 𝒟 bound ( s 2 , γ ) ] \opE_{s_{1}\sim\Delta_{1}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{1},\gamma\right)\right]\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{s_{2}\sim\Delta_{2}}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{2},\gamma\right)\right] .
We show that this result’s preconditions holding for F Δ i ∗ F_{\Delta_{i}}^{*} implies the F Δ i F_{\Delta_{i}} preconditions. Suppose F Δ i ∗ ≔ { 𝔼 s i ∼ Δ i [ 𝐟 π , s i ] ∣ π ∈ Π } F_{\Delta_{i}}^{*}\coloneqq\left\{\opE_{s_{i}\sim\Delta_{i}}\left[\mathbf{f}^{\pi,s_{i}}\right]\mid\pi\in\Pi\right\} for i = 1 , 2 i=1,2 are such that F sub ∗ ≔ ϕ ⋅ ND ( F Δ 1 ∗ ) ⊆ F Δ 2 ∗ F_{\text{sub}}^{*}\coloneqq\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)\subseteq F_{\Delta_{2}}^{*} . In the following, the Δ i \Delta_{i} are represented as vectors in ℝ | 𝒮 | \mathbb{R}^{\left|\mathcal{S}\right|} , and γ \gamma is a variable. ϕ ⋅ { γ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 1 ) } \displaystyle\phi\cdot\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\} = ϕ ⋅ ( ND ( F Δ 1 ∗ − Δ 1 ) ) \displaystyle=\phi\cdot\left(\text{{ND}}\left(F_{\Delta_{1}}^{*}-\Delta_{1}\right)\right) (148) = ϕ ⋅ ( ND ( F Δ 1 ∗ ) − Δ 1 ) \displaystyle=\phi\cdot\left(\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)-\Delta_{1}\right) (149) = { 𝐏 ϕ 𝐟 − 𝐏 ϕ Δ 1 ∣ 𝐟 ∈ ND ( F Δ 1 ∗ ) } \displaystyle=\left\{\mathbf{P}_{\phi}\mathbf{f}-\mathbf{P}_{\phi}\Delta_{1}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)\right\} (150) ⊆ { 𝐟 − Δ 2 ∣ 𝐟 ∈ F Δ 2 ∗ } \displaystyle\subseteq\left\{\mathbf{f}-\Delta_{2}\mid\mathbf{f}\in F_{\Delta_{2}}^{*}\right\} (151) = { γ 𝐟 ∣ 𝐟 ∈ F Δ 2 } . \displaystyle=\left\{\gamma\mathbf{f}\mid\mathbf{f}\in F_{\Delta_{2}}\right\}. (152)
Equation 149 follows from Lemma E.15 item 2 . Since we assumed that ϕ ⋅ ND ( F Δ 1 ∗ ) ⊆ F Δ 2 ∗ \phi\cdot\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)\subseteq F_{\Delta_{2}}^{*} , ϕ ⋅ { Δ 1 } = ϕ ⋅ ( ND ( F Δ 1 ∗ ) ( 0 ) ) ⊆ F Δ 2 ∗ ( 0 ) = { Δ 2 } \phi\cdot\left\{\Delta_{1}\right\}=\phi\cdot\left(\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)(0)\right)\subseteq F_{\Delta_{2}}^{*}(0)=\left\{\Delta_{2}\right\} . This implies that 𝐏 ϕ Δ 1 = Δ 2 \mathbf{P}_{\phi}\Delta_{1}=\Delta_{2} and so eq. 151 follows.
Equation 152 shows that ϕ ⋅ { γ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 1 ) } ⊆ { γ 𝐟 ∣ 𝐟 ∈ F Δ 2 } \phi\cdot\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\}\subseteq\left\{\gamma\mathbf{f}\mid\mathbf{f}\in F_{\Delta_{2}}\right\} . But we then have ϕ ⋅ { γ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 1 ) } ≔ { γ 𝐏 ϕ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 1 ) } = { γ 𝐟 ∣ 𝐟 ∈ ϕ ⋅ ND ( F Δ 1 ) } ⊆ { γ 𝐟 ∣ 𝐟 ∈ F Δ 2 } \phi\cdot\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\}\coloneqq\left\{\gamma\mathbf{P}_{\phi}\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\}=\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right)\right\}\subseteq\left\{\gamma\mathbf{f}\mid\mathbf{f}\in F_{\Delta_{2}}\right\} . Thus, ϕ ⋅ ND ( F Δ 1 ) ⊆ F Δ 2 \phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right)\subseteq F_{\Delta_{2}} .
Suppose ND ( F Δ 2 ∗ ) ∖ ϕ ⋅ ND ( F Δ 1 ∗ ) \text{{ND}}\left(F_{\Delta_{2}}^{*}\right)\setminus\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}^{*}\right) is non-empty, which implies that ϕ ⋅ { γ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 1 ) } \displaystyle\phi\cdot\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}\right)\right\} = { 𝐏 ϕ 𝐟 − 𝐏 ϕ Δ 1 ∣ 𝐟 ∈ ND ( F Δ 1 ∗ ) } \displaystyle=\left\{\mathbf{P}_{\phi}\mathbf{f}-\mathbf{P}_{\phi}\Delta_{1}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)\right\} (153) = { 𝐟 − 𝐏 ϕ Δ 1 ∣ 𝐟 ∈ ϕ ⋅ ND ( F Δ 1 ∗ ) } \displaystyle=\left\{\mathbf{f}-\mathbf{P}_{\phi}\Delta_{1}\mid\mathbf{f}\in\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}^{*}\right)\right\} (154) ⊊ { 𝐟 − Δ 2 ∣ 𝐟 ∈ ND ( F Δ 2 ∗ ) } \displaystyle\subsetneq\left\{\mathbf{f}-\Delta_{2}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{2}}^{*}\right)\right\} (155) = { γ 𝐟 ∣ 𝐟 ∈ ND ( F Δ 2 ) } . \displaystyle=\left\{\gamma\mathbf{f}\mid\mathbf{f}\in\text{{ND}}\left(F_{\Delta_{2}}\right)\right\}. (156)
Then ND ( F Δ 2 ) ∖ ϕ ⋅ ND ( F Δ 1 ) \text{{ND}}\left(F_{\Delta_{2}}\right)\setminus\phi\cdot\text{{ND}}\left(F_{\Delta_{1}}\right) must be non-empty. Therefore, if the preconditions of this result are met for F Δ i ∗ F_{\Delta_{i}}^{*} , they are met for F Δ i F_{\Delta_{i}} . ∎
See 6.6
###### Proof.
Let F sub ≔ ϕ ⋅ ℱ nd ( s ′ ) ⊆ ℱ ( s ) F_{\text{sub}}\coloneqq\phi\cdot\Fndop(s^{\prime})\subseteq\Fop(s) . Let Δ 1 ≔ 𝐞 s ′ , Δ 2 ≔ 𝐞 s \Delta_{1}\coloneqq\mathbf{e}_{s^{\prime}},\Delta_{2}\coloneqq\mathbf{e}_{s} , and define F Δ i ∗ ≔ { 𝔼 s i ∼ Δ i [ 𝐟 π , s i ] ∣ π ∈ Π } F_{\Delta_{i}}^{*}\coloneqq\left\{\opE_{s_{i}\sim\Delta_{i}}\left[\mathbf{f}^{\pi,s_{i}}\right]\mid\pi\in\Pi\right\} for i = 1 , 2 i=1,2 . Then ℱ nd ( s ′ ) = ND ( F Δ 1 ∗ ) \Fndop(s^{\prime})=\text{{ND}}\left(F_{\Delta_{1}}^{*}\right) is similar to F sub = F sub ∗ ⊆ F Δ 2 ∗ = ℱ ( s ) F_{\text{sub}}=F^{*}_{\text{sub}}\subseteq F_{\Delta_{2}}^{*}=\Fop(s) via involution ϕ \phi . Apply Lemma E.44 to conclude that ∀ γ ∈ [ 0 , 1 ] : Power 𝒟 bound ( s ′ , γ ) ≤ most : 𝔇 bound Power 𝒟 bound ( s , γ ) \forall\gamma\in[0,1]\mathrel{\mathop{\ordinarycolon}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) .
Furthermore, ℱ nd ( s ) = ND ( F Δ 2 ∗ ) \Fndop(s)=\text{{ND}}\left(F_{\Delta_{2}}^{*}\right) , and F sub = F sub ∗ F_{\text{sub}}=F_{\text{sub}}^{*} , and so if ℱ nd ( s ) ∖ ϕ ⋅ ℱ nd ( s ′ ) ≔ ℱ nd ( s ) ∖ F sub = ND ( F Δ 2 ∗ ) ∖ F sub ∗ \Fndop(s)\setminus\phi\cdot\Fndop(s^{\prime})\coloneqq\Fndop(s)\setminus F_{\text{sub}}=\text{{ND}}\left(F_{\Delta_{2}}^{*}\right)\setminus F_{\text{sub}}^{*} is non-empty, then Lemma E.44 shows that for all γ ∈ ( 0 , 1 ) \gamma\in(0,1) , the inequality is strict for all 𝒟 X - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} and Power 𝒟 bound ( s ′ , γ ) ≱ most : 𝔇 bound Power 𝒟 bound ( s , γ ) \text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) . ∎