Parametrically Retargetable Decision-Makers Tend To Seek Power — part 12/13
Cleaned-text code points [170300, 183867). Bibliography omitted here; source.md includes it.
Let A , B ⊊ ℝ d A,B\subsetneq\mathbb{R}^{d} be finite and let g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} be a (total) increasing function. Suppose B B contains n n copies of ND ( A ) \text{{ND}}\left(A\right) . Then 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] ≥ most : 𝔇 bound n 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] . \displaystyle\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}^{n}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]. (142)
###### Proof.
Because g : ℝ → ℝ g\mathrel{\mathop{\ordinarycolon}}\mathbb{R}\to\mathbb{R} is increasing, it is measurable (as is max \max ).
Let L ≔ inf 𝐫 ∈ supp ( 𝒟 bound ) max 𝐱 ∈ X 𝐱 ⊤ 𝐫 , U ≔ sup 𝐫 ∈ supp ( 𝒟 bound ) max 𝐱 ∈ X 𝐱 ⊤ 𝐫 L\coloneqq\inf_{\mathbf{r}\in\optSupp(\mathcal{D}_{\text{bound}})}\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r},U\coloneqq\sup_{\mathbf{r}\in\optSupp(\mathcal{D}_{\text{bound}})}\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r} . Both exist because 𝒟 bound \mathcal{D}_{\text{bound}} has bounded support. Furthermore, since g g is monotone increasing, it is bounded [ g ( L ) , g ( U ) ] [g(L),g(U)] on [ L , U ] [L,U] . Therefore, g g is measurable and bounded on each supp ( 𝒟 bound ) \optSupp(\mathcal{D}_{\text{bound}}) , and so the relevant expectations exist for all 𝒟 bound \mathcal{D}_{\text{bound}} .
For finite X ⊊ ℝ d X\subsetneq\mathbb{R}^{d} , let f ( X ∣ 𝐮 ) ≔ g ( max 𝐱 ∈ X 𝐱 ⊤ 𝐮 ) f(X\mid\mathbf{u})\coloneqq g(\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{u}) . By Lemma B.11 , f f is invariant under joint permutation by S d S_{d} . Furthermore, f f is measurable because g g and max \max are. Therefore, apply Lemma B.5 to conclude that f ( X ∣ 𝒟 bound ) ≔ 𝔼 𝐮 ∼ 𝒟 bound [ g ( max 𝐱 ∈ X 𝐱 ⊤ 𝐮 ) ] f(X\mid\mathcal{D}_{\text{bound}})\coloneqq\opE_{\mathbf{u}\sim\mathcal{D}_{\text{bound}}}\left[g(\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{u})\right] is also invariant under joint permutation by S d S_{d} (with f f being bounded when restricted to supp ( 𝒟 bound ) \optSupp(\mathcal{D}_{\text{bound}}) ). Lastly, if X ′ ⊆ X X^{\prime}\subseteq X , f ( X ′ ∣ 𝒟 bound ) ≤ f ( X ∣ 𝒟 bound ) f(X^{\prime}\mid\mathcal{D}_{\text{bound}})\leq f(X\mid\mathcal{D}_{\text{bound}}) because g g is increasing. 𝔼 𝐮 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐮 ) ] \displaystyle\opE_{\mathbf{u}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{u}\right)\right] = 𝔼 𝐮 ∼ 𝒟 bound [ g ( max 𝐚 ∈ ND ( A ) 𝐚 ⊤ 𝐮 ) ] \displaystyle=\opE_{\mathbf{u}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in\text{{ND}}\left(A\right)}\mathbf{a}^{\top}\mathbf{u}\right)\right] (143) ≤ most : 𝔇 any n 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] . \displaystyle\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (144)
Equation 143 follows by corollary E.11 of [ Turner et al., 2021 ] . Equation 144 follows by applying Lemma B.9 with f f as defined above with the ϕ 1 , … , ϕ n \phi_{1},\ldots,\phi_{n} guaranteed by the copy assumption. ∎
###### Definition D.4 (Linear functional optimality probability [ Turner et al., 2021 ] ) .
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).
###### Lemma D.5 (Quantitative optimality probability superiority lemma) .
Let A , B , C ⊊ ℝ d A,B,C\subsetneq\mathbb{R}^{d} be finite and let Z Z satisfy ND ( C ) ⊆ Z ⊆ C \text{{ND}}\left(C\right)\subseteq Z\subseteq C . Suppose that B B contains n n copies of ND ( A ) \text{{ND}}\left(A\right) via involutions ϕ i \phi_{i} . Furthermore, let B extra ≔ B ∖ ( ∪ i = 1 n ϕ i ⋅ ND ( A ) ) B_{\text{extra}}\coloneqq B\setminus\left(\cup_{i=1}^{n}\phi_{i}\cdot\text{{ND}}\left(A\right)\right) ; suppose that for all i i , ϕ i ⋅ ( Z ∖ B extra ) = Z ∖ B extra \phi_{i}\cdot\left(Z\setminus B_{\text{extra}}\right)=Z\setminus B_{\text{extra}} .
Then p 𝒟 any ( B ≥ C ) ≥ most : 𝔇 any n p 𝒟 any ( A ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right) .
###### Proof.
For finite X , Y ⊊ ℝ d X,Y\subsetneq\mathbb{R}^{d} , let g ( X , Y ∣ 𝒟 any ) ≔ p 𝒟 any ( X ≥ Y ) = 𝔼 𝐮 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐮 ≥ max 𝐲 ∈ Y 𝐲 ⊤ 𝐮 ] . g(X,Y\mid\mathcal{D}_{\text{any}})\coloneqq p_{\mathcal{D}_{\text{any}}}\left(X\geq Y\right)=\opE_{\mathbf{u}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{u}\geq\max_{\mathbf{y}\in Y}\mathbf{y}^{\top}\mathbf{u}}\right]. By the proof of item 1 of Proposition A.11 , g g is the expectation of a 𝐮 \mathbf{u} -measurable function. g g is an EU function, and so Lemma B.11 shows that it is invariant to joint permutation by ϕ i \phi_{i} . Letting f Y ( X ∣ 𝒟 any ) ≔ g ( X , Y ∣ 𝒟 any ) f_{Y}(X\mid\mathcal{D}_{\text{any}})\coloneqq g(X,Y\mid\mathcal{D}_{\text{any}}) , Lemma B.10 shows that f Y ( X ∣ 𝒟 any ) = f Y ( ϕ i ⋅ X ∣ ϕ i ⋅ 𝒟 any ) f_{Y}(X\mid\mathcal{D}_{\text{any}})=f_{Y}(\phi_{i}\cdot X\mid\phi_{i}\cdot\mathcal{D}_{\text{any}}) whenever the ϕ i \phi_{i} satisfy ϕ i ⋅ Y = Y \phi_{i}\cdot Y=Y .
Furthermore, if X ′ ⊆ X X^{\prime}\subseteq X , then f Y ( X ′ ∣ 𝒟 any ) ≤ f Y ( X ∣ 𝒟 any ) f_{Y}(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f_{Y}(X\mid\mathcal{D}_{\text{any}}) . p 𝒟 any ( A ≥ C ) \displaystyle p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right) = p 𝒟 any ( ND ( A ) ≥ C ) \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(\text{{ND}}\left(A\right)\geq C\right) (145) ≤ p 𝒟 any ( ND ( A ) ≥ Z ∖ B extra ) \displaystyle\leq p_{\mathcal{D}_{\text{any}}}\left(\text{{ND}}\left(A\right)\geq Z\setminus B_{\text{extra}}\right) (146) ≤ most : 𝔇 any n p 𝒟 any ( B ≥ Z ∖ B extra ) \displaystyle\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}p_{\mathcal{D}_{\text{any}}}\left(B\geq Z\setminus B_{\text{extra}}\right) (147) ≤ p 𝒟 any ( B ∪ B extra ≥ Z ) \displaystyle\leq p_{\mathcal{D}_{\text{any}}}\left(B\cup B_{\text{extra}}\geq Z\right) (148) = p 𝒟 any ( B ≥ Z ) \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(B\geq Z\right) (149) = p 𝒟 any ( B ≥ C ) . \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right). (150) Equation 145 follows by Turner et al. [2021] ’s lemma E.12’s item 2 with X ≔ A X\coloneqq A , X ′ ≔ ND ( A ) X^{\prime}\coloneqq\text{{ND}}\left(A\right) (similar reasoning holds for C C and Z Z in eq. 150 ). Equation 146 follows by the first inequality of lemma E.26 of [ Turner et al., 2021 ] with X ≔ A , Y ≔ C , Y ′ ≔ Z ∖ B extra X\coloneqq A,Y\coloneqq C,Y^{\prime}\coloneqq Z\setminus B_{\text{extra}} . Equation 147 follows by applying Lemma B.9 with the f Z ∖ B extra f_{Z\setminus B_{\text{extra}}} defined above. Equation 148 follows by the second inequality of lemma E.26 of [ Turner et al., 2021 ] with X ≔ A , Y ≔ Z , Y ′ ≔ Z ∖ B extra X\coloneqq A,Y\coloneqq Z,Y^{\prime}\coloneqq Z\setminus B_{\text{extra}} . Equation 149 follows because B extra ⊆ B B_{\text{extra}}\subseteq B .
Letting f 0 ( 𝒟 any ) ≔ p 𝒟 any ( A ≥ C ) , f 1 ( 𝒟 any ) ≔ p 𝒟 any ( ND ( A ) ≥ Z ∖ B extra ) , f 2 ( 𝒟 any ) ≔ p 𝒟 any ( B ≥ Z ∖ B extra ) , f 3 ( 𝒟 any ) ≔ p 𝒟 any ( B ≥ C ) f_{0}(\mathcal{D}_{\text{any}})\coloneqq p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right),f_{1}(\mathcal{D}_{\text{any}})\coloneqq p_{\mathcal{D}_{\text{any}}}\left(\text{{ND}}\left(A\right)\geq Z\setminus B_{\text{extra}}\right),f_{2}(\mathcal{D}_{\text{any}})\coloneqq p_{\mathcal{D}_{\text{any}}}\left(B\geq Z\setminus B_{\text{extra}}\right),f_{3}(\mathcal{D}_{\text{any}})\coloneqq p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) , apply Lemma B.1 to conclude that p 𝒟 any ( A ≥ C ) ≤ most : 𝔇 any n p 𝒟 any ( B ≥ C ) . p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right). ∎
###### Definition D.6 (Rewardless mdp [ Turner et al., 2021 ] ) .
⟨ 𝒮 , 𝒜 , T ⟩ \langle\mathcal{S},\mathcal{A},T\rangle is a rewardless mdp with finite state and action spaces 𝒮 \mathcal{S} and 𝒜 \mathcal{A} , and stochastic transition function T : 𝒮 × 𝒜 → Δ ( 𝒮 ) T\mathrel{\mathop{\ordinarycolon}}\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S}) . We treat the discount rate γ \gamma as a variable with domain [ 0 , 1 ] [0,1] .
###### Definition D.7 (1-cycle states [ Turner et al., 2021 ] ) .
Let 𝐞 s ∈ ℝ | 𝒮 | \mathbf{e}_{s}\in\mathbb{R}^{\left|\mathcal{S}\right|} be the standard basis vector for state s s , such that there is a 1 1 in the entry for state s s and 0 0 elsewhere. State s s is a 1-cycle if ∃ a ∈ 𝒜 : T ( s , a ) = 𝐞 s \exists a\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}T(s,a)=\mathbf{e}_{s} . State s s is a terminal state if ∀ a ∈ 𝒜 : T ( s , a ) = 𝐞 s \forall a\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}T(s,a)=\mathbf{e}_{s} .
###### Definition D.8 (State visit distribution [ Sutton and Barto, 1998 ] ) .
Π ≔ 𝒜 𝒮 \Pi\coloneqq\mathcal{A}^{\mathcal{S}} , the set of stationary deterministic policies. The visit distribution induced by following policy π \pi from state s s at discount rate γ ∈ [ 0 , 1 ) \gamma\in[0,1) is 𝐟 π , s ( γ ) ≔ ∑ t = 0 ∞ γ t 𝔼 s t ∼ π | s [ 𝐞 s t ] \mathbf{f}^{\pi,s}(\gamma)\coloneqq\sum_{t=0}^{\infty}\gamma^{t}\opE_{s_{t}\sim\pi\mid s}\left[\mathbf{e}_{s_{t}}\right] . 𝐟 π , s \mathbf{f}^{\pi,s} is a visit distribution function ; ℱ ( s ) ≔ { 𝐟 π , s ∣ π ∈ Π } \Fop(s)\coloneqq\{\mathbf{f}^{\pi,s}\mid\pi\in\Pi\} .
###### Definition D.9 (Recurrent state distributions [ Puterman, 2014 ] ) .
The recurrent state distributions which can be induced from state s s are RSD ( s ) ≔ { lim γ → 1 ( 1 − γ ) 𝐟 π , s ( γ ) ∣ π ∈ Π } \text{{RSD}}\left(s\right)\coloneqq\left\{\lim_{\gamma\to 1}(1-\gamma)\mathbf{f}^{\pi,s}(\gamma)\mid\pi\in\Pi\right\} . RSD nd ( s ) \text{{RSD}}{\text{\textsubscript{nd}}}\left(s\right) is the set of rsd s which strictly maximize average reward for some reward function.
###### Definition D.10 (Average-optimal policies [ Turner et al., 2021 ] ) .
The average-optimal policy set for reward function R R is Π avg ( R ) ≔ { π ∈ Π ∣ ∀ s ∈ 𝒮 : 𝐝 π , s ∈ arg max 𝐝 ∈ RSD ( s ) 𝐝 ⊤ 𝐫 } \Pi^{\text{avg}}\left(R\right)\coloneqq\left\{\pi\in\Pi\mid\forall s\in\mathcal{S}\mathrel{\mathop{\ordinarycolon}}\mathbf{d}^{\pi,s}\in\argmax_{\mathbf{d}\in\text{{RSD}}\left(s\right)}\mathbf{d}^{\top}\mathbf{r}\right\} (the policies which induce optimal rsd s at all states). For D ⊆ RSD ( s ) D\subseteq\text{{RSD}}\left(s\right) , the average optimality probability is ℙ 𝒟 any ( D , average ) ≔ ℙ R ∼ 𝒟 any ( ∃ 𝐝 π , s ∈ D : π ∈ Π avg ( R ) ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(D,\text{average}\right)\coloneqq\Prb\nolimits_{R\sim\mathcal{D}_{\text{any}}}\left(\exists\mathbf{d}^{\pi,s}\in D\mathrel{\mathop{\ordinarycolon}}\pi\in\Pi^{\text{avg}}\left(R\right)\right) .
###### Remark .
Theorem D.11 generalizes the first claim of Turner et al. [2021] ’s theorem 6.13, and Corollary D.12 generalizes the first claim of Turner et al. [2021] ’s corollary 6.14.
###### Theorem D.11 (Quantitatively, average-optimal policies tend to end up in “larger” sets of rsd s) .
Let D ′ , D ⊆ RSD ( s ) D^{\prime},D\subseteq\text{{RSD}}\left(s\right) . Suppose that D D contains n n copies of D ′ D^{\prime} and that the sets D ′ ∪ D D^{\prime}\cup D and RSD nd ( s ) ∖ ( D ′ ∪ D ) \text{{RSD}}{\text{\textsubscript{nd}}}\left(s\right)\setminus\left(D^{\prime}\cup D\right) have pairwise orthogonal vector elements (i.e., pairwise disjoint vector support). Then ℙ 𝒟 any ( D ′ , average ) ≤ most : 𝔇 any n ℙ 𝒟 any ( D , average ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(D^{\prime},\text{average}\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(D,\text{average}\right) .
###### Proof.
Let D i ≔ ϕ i ⋅ D ′ D_{i}\coloneqq\phi_{i}\cdot D^{\prime} , where D i ⊆ D D_{i}\subseteq D by assumption. Let S ≔ { s ′ ∈ 𝒮 ∣ max 𝐝 ∈ D ′ ∪ D 𝐝 ⊤ 𝐞 s ′ > 0 } S\coloneqq\left\{s^{\prime}\in\mathcal{S}\mid\max_{\mathbf{d}\in D^{\prime}\cup D}\mathbf{d}^{\top}\mathbf{e}_{s^{\prime}}>0\right\} . Define ϕ i ′ ( s ′ ) ≔ { ϕ i ( s ′ ) if s ′ ∈ S s ′ else . \phi_{i}^{\prime}(s^{\prime})\coloneqq\begin{cases}\phi_{i}(s^{\prime})&\text{ if }s^{\prime}\in S\\ s^{\prime}&\text{ else}.\end{cases} (151)
Since ϕ i \phi_{i} is an involution, ϕ i ′ \phi_{i}^{\prime} is also an involution. Furthermore, ϕ i ′ ⋅ D ′ = D i \phi_{i}^{\prime}\cdot D^{\prime}=D_{i} , ϕ i ′ ⋅ D i = D ′ \phi_{i}^{\prime}\cdot D_{i}=D^{\prime} , and ϕ i ′ ⋅ D j = D j \phi_{i}^{\prime}\cdot D_{j}=D_{j} for j ≠ i j\neq i because we assumed that these equalities hold for ϕ i \phi_{i} , and D ′ , D i , D j ⊆ D ′ ∪ D D^{\prime},D_{i},D_{j}\subseteq D^{\prime}\cup D and so the vectors of these sets have support contained in S S .