Optimal Policies Tend to Seek Power — part 11/16
Cleaned-text code points [156253, 171009). Bibliography omitted here; source.md includes it.
Equation 103 follows from Lemma E.36 . Equation 104 follows because V R ∗ ( s ′ , γ ) ≤ max s ′′ ∈ 𝒮 R ( s ′′ ) 1 − γ V^{*}_{R}\left(s^{\prime},\gamma\right)\leq\frac{\max_{s^{\prime\prime}\in\mathcal{S}}R(s^{\prime\prime})}{1-\gamma} , as no policy can do better than achieving maximal reward at each time step. Taking limits, the inequality holds for all γ ∈ [ 0 , 1 ] \gamma\in[0,1] .
Suppose that s s can deterministically reach all states in one step and all states are 1-cycles. Then eq. 104 is an equality for all γ ∈ ( 0 , 1 ) \gamma\in(0,1) , since for each R R , the agent can select an action which deterministically transitions to a state with maximal reward. Thus the equality holds for all γ ∈ [ 0 , 1 ] \gamma\in[0,1] . ∎
###### Lemma E.39 (Lower bound on current Power based on future Power ) .
Power 𝒟 bound ( s , γ ) ≥ ( 1 − γ ) min a 𝔼 s ′ ∼ T ( s , a ) , R ∼ 𝒟 bound [ R ( s ′ ) ] + γ max a 𝔼 s ′ ∼ T ( s , a ) [ Power 𝒟 bound ( s ′ , γ ) ] . \displaystyle\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\geq(1-\gamma)\min_{a}\opE_{\begin{subarray}{c}s^{\prime}\sim T(s,a),\\ R\sim\mathcal{D}_{\text{bound}}\end{subarray}}\left[R(s^{\prime})\right]+\gamma\max_{a}\opE_{s^{\prime}\sim T(s,a)}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right]. (106)
###### Proof.
Let γ ∈ ( 0 , 1 ) \gamma\in(0,1) and let a ∗ ∈ arg max a 𝔼 s ′ ∼ T ( s , a ) [ Power 𝒟 bound ( s ′ , γ ) ] a^{*}\in\argmax_{a}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right] . Power 𝒟 bound ( s , γ ) \displaystyle\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) (107) = \displaystyle=\, ( 1 − γ ) 𝔼 R ∼ 𝒟 bound [ max a 𝔼 s ′ ∼ T ( s , a ) [ V R ∗ ( s ′ , γ ) ] ] \displaystyle(1-\gamma)\opE_{R\sim\mathcal{D}_{\text{bound}}}\left[\max_{a}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right]\right] (108) ≥ \displaystyle\geq\, ( 1 − γ ) max a 𝔼 s ′ ∼ T ( s , a ) [ 𝔼 R ∼ 𝒟 bound [ V R ∗ ( s ′ , γ ) ] ] \displaystyle(1-\gamma)\max_{a}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[\opE_{R\sim\mathcal{D}_{\text{bound}}}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right]\right] (109) = \displaystyle=\, ( 1 − γ ) max a 𝔼 s ′ ∼ T ( s , a ) [ V 𝒟 bound ∗ ( s ′ , γ ) ] \displaystyle(1-\gamma)\max_{a}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[V^{*}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right] (110) = \displaystyle=\, ( 1 − γ ) max a 𝔼 s ′ ∼ T ( s , a ) [ 𝔼 R ∼ 𝒟 bound [ R ( s ′ ) ] + γ 1 − γ Power 𝒟 bound ( s ′ , γ ) ] \displaystyle(1-\gamma)\max_{a}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[\opE_{R\sim\mathcal{D}_{\text{bound}}}\left[R(s^{\prime})\right]+\frac{\gamma}{1-\gamma}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right] (111) ≥ \displaystyle\geq\, ( 1 − γ ) 𝔼 s ′ ∼ T ( s , a ∗ ) [ 𝔼 R ∼ 𝒟 bound [ R ( s ′ ) ] + γ 1 − γ Power 𝒟 bound ( s ′ , γ ) ] \displaystyle(1-\gamma)\opE_{s^{\prime}\sim T\left(s,a^{*}\right)}\left[\opE_{R\sim\mathcal{D}_{\text{bound}}}\left[R(s^{\prime})\right]+\frac{\gamma}{1-\gamma}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right] (112) ≥ \displaystyle\geq\, ( 1 − γ ) min a 𝔼 s ′ ∼ T ( s , a ) , R ∼ 𝒟 bound [ R ( s ′ ) ] + γ 𝔼 s ′ ∼ T ( s , a ∗ ) [ Power 𝒟 bound ( s ′ , γ ) ] . \displaystyle(1-\gamma)\min_{a}\opE_{\begin{subarray}{c}s^{\prime}\sim T(s,a),\\ R\sim\mathcal{D}_{\text{bound}}\end{subarray}}\left[R(s^{\prime})\right]+\gamma\opE_{s^{\prime}\sim T\left(s,a^{*}\right)}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right]. (113)
Equation 108 holds by Lemma E.36 . Equation 109 follows because 𝔼 x ∼ X [ max a f ( a , x ) ] ≥ max a 𝔼 x ∼ X [ f ( a , x ) ] \opE_{x\sim X}\left[\max_{a}f(a,x)\right]\geq\max_{a}\opE_{x\sim X}\left[f(a,x)\right] by Jensen’s inequality, and eq. 111 follows by Lemma E.36 .
The inequality also holds when we take the limits γ → 0 \gamma\to 0 or γ → 1 \gamma\to 1 . ∎
See 5.5
###### Proof.
Suppose γ ∈ [ 0 , 1 ] \gamma\in[0,1] . First consider the case where Power 𝒟 bound ( s , γ ) ≥ Power 𝒟 bound ( s ′ , γ ) \text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\geq\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right) . Power 𝒟 bound ( s ′ , γ ) \displaystyle\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right) ≥ ( 1 − γ ) min a 𝔼 s x ∼ T ( s ′ , a ) , R ∼ 𝒟 bound [ R ( s x ) ] + γ max a 𝔼 s x ∼ T ( s ′ , a ) [ Power 𝒟 bound ( s x , γ ) ] \displaystyle\geq(1-\gamma)\min_{a}\opE_{\begin{subarray}{c}s_{x}\sim T(s^{\prime},a),\\ R\sim\mathcal{D}_{\text{bound}}\end{subarray}}\left[R(s_{x})\right]+\gamma\max_{a}\opE_{s_{x}\sim T(s^{\prime},a)}\left[\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{x},\gamma\right)\right] (114) ≥ ( 1 − γ ) b + γ Power 𝒟 bound ( s , γ ) . \displaystyle\geq(1-\gamma)b+\gamma\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right). (115)
Equation 114 follows by Lemma E.39 . Equation 115 follows because reward is lower-bounded by b b and because s ′ s^{\prime} can reach s s in one step with probability 1. | Power 𝒟 bound ( s , γ ) − Power 𝒟 bound ( s ′ , γ ) | \displaystyle\left|\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)-\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right)\right| = Power 𝒟 bound ( s , γ ) − Power 𝒟 bound ( s ′ , γ ) \displaystyle=\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)-\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right) (116) ≤ Power 𝒟 bound ( s , γ ) − ( ( 1 − γ ) b + γ Power 𝒟 bound ( s , γ ) ) \displaystyle\leq\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)-\left((1-\gamma)b+\gamma\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\right) (117) = ( 1 − γ ) ( Power 𝒟 bound ( s , γ ) − b ) \displaystyle=(1-\gamma)\left(\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)-b\right) (118) ≤ ( 1 − γ ) ( 𝔼 R ∼ 𝒟 bound [ max s ′′ ∈ 𝒮 R ( s ′′ ) ] − b ) \displaystyle\leq(1-\gamma)\left(\opE_{R\sim\mathcal{D}_{\text{bound}}}\left[\max_{s^{\prime\prime}\in\mathcal{S}}R(s^{\prime\prime})\right]-b\right) (119) ≤ ( 1 − γ ) ( c − b ) . \displaystyle\leq(1-\gamma)(c-b). (120)
Equation 116 follows because Power 𝒟 bound ( s , γ ) ≥ Power 𝒟 bound ( s ′ , γ ) \text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\geq\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right) . Equation 117 follows by eq. 115 . Equation 119 follows by Proposition 5.4 . Equation 120 follows because reward under 𝒟 bound \mathcal{D}_{\text{bound}} is upper-bounded by c c .
The case where Power 𝒟 bound ( s , γ ) ≤ Power 𝒟 bound ( s ′ , γ ) \text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\leq\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s^{\prime},\gamma\right) is similar, leveraging the fact that s s can also reach s ′ s^{\prime} in one step with probability 1. ∎
### E.4 Seeking Power is often more probable under optimality
#### E.4.1 Keeping options open tends to be Power -seeking and tends to be optimal
###### Definition E.40 (Normalized visit distribution function) .
Let 𝐟 : [ 0 , 1 ) → ℝ | 𝒮 | \mathbf{f}\mathrel{\mathop{\ordinarycolon}}[0,1)\to\mathbb{R}^{\left|\mathcal{S}\right|} be a vector function. For γ ∈ [ 0 , 1 ] \gamma\in[0,1] , Norm ( 𝐟 , γ ) ≔ lim γ ∗ → γ ( 1 − γ ∗ ) 𝐟 ( γ ∗ ) \text{{Norm}}\left(\mathbf{f},\gamma\right)\coloneqq\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}(\gamma^{*}) (this limit need not exist for arbitrary 𝐟 \mathbf{f} ). If F F is a set of such 𝐟 \mathbf{f} , then Norm ( F , γ ) ≔ { Norm ( 𝐟 , γ ) ∣ 𝐟 ∈ F } \text{{Norm}}\left(F,\gamma\right)\coloneqq\left\{\text{{Norm}}\left(\mathbf{f},\gamma\right)\mid\mathbf{f}\in F\right\} .
###### Remark .
RSD ( s ) = Norm ( ℱ ( s ) , 1 ) \text{{RSD}}\left(s\right)=\text{{Norm}}\left(\Fop(s),1\right) .
###### Lemma E.41 (Normalized visit distribution functions are continuous) .
Let Δ s ∈ Δ ( 𝒮 ) \Delta_{s}\in\Delta(\mathcal{S}) be a state probability distribution, let π ∈ Π \pi\in\Pi , and let 𝐟 ∗ ≔ 𝔼 s ∼ Δ s [ 𝐟 π , s ] \mathbf{f}^{*}\coloneqq\opE_{s\sim\Delta_{s}}\left[\mathbf{f}^{\pi,s}\right] . Norm ( 𝐟 ∗ , γ ) \text{{Norm}}\left(\mathbf{f}^{*},\gamma\right) is continuous on γ ∈ [ 0 , 1 ] \gamma\in[0,1] .
###### Proof.
Norm ( 𝐟 ∗ , γ ) \displaystyle\text{{Norm}}\left(\mathbf{f}^{*},\gamma\right) ≔ lim γ ∗ → γ ( 1 − γ ∗ ) 𝔼 s ∼ Δ s [ 𝐟 π , s ( γ ∗ ) ] \displaystyle\coloneqq\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\opE_{s\sim\Delta_{s}}\left[\mathbf{f}^{\pi,s}(\gamma^{*})\right] (121) = 𝔼 s ∼ Δ s [ lim γ ∗ → γ ( 1 − γ ∗ ) 𝐟 π , s ( γ ∗ ) ] \displaystyle=\opE_{s\sim\Delta_{s}}\left[\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}^{\pi,s}(\gamma^{*})\right] (122) ≕ 𝔼 s ∼ Δ s [ Norm ( 𝐟 π , s , γ ) ] . \displaystyle\eqqcolon\opE_{s\sim\Delta_{s}}\left[\text{{Norm}}\left(\mathbf{f}^{\pi,s},\gamma\right)\right]. (123) Equation 122 follows because the expectation is over a finite set. Each 𝐟 π , s ∈ ℱ ( s ) \mathbf{f}^{\pi,s}\in\Fop(s) is continuous on γ ∈ [ 0 , 1 ) \gamma\in[0,1) by Lemma E.4 , and lim γ ∗ → 1 ( 1 − γ ∗ ) 𝐟 π , s ( γ ∗ ) \lim_{\gamma^{*}\to 1}(1-\gamma^{*})\mathbf{f}^{\pi,s}(\gamma^{*}) exists because rsd s are well-defined [ Puterman, 2014 ] . Therefore, each Norm ( 𝐟 π , s , γ ) \text{{Norm}}\left(\mathbf{f}^{\pi,s},\gamma\right) is continuous on γ ∈ [ 0 , 1 ] \gamma\in[0,1] . Lastly, eq. 123 ’s expectation over finitely many continuous functions is itself continuous. ∎
###### Lemma E.42 (Non-domination of normalized visit distribution functions) .
Let Δ s ∈ Δ ( 𝒮 ) \Delta_{s}\in\Delta(\mathcal{S}) be a state probability distribution and let F ≔ { 𝔼 s ∼ Δ s [ 𝐟 π , s ] ∣ π ∈ Π } F\coloneqq\left\{\opE_{s\sim\Delta_{s}}\left[\mathbf{f}^{\pi,s}\right]\mid\pi\in\Pi\right\} . For all γ ∈ [ 0 , 1 ] \gamma\in[0,1] , ND ( Norm ( F , γ ) ) ⊆ Norm ( ND ( F ) , γ ) \text{{ND}}\left(\text{{Norm}}\left(F,\gamma\right)\right)\subseteq\text{{Norm}}\left(\text{{ND}}\left(F\right),\gamma\right) , with equality when γ ∈ ( 0 , 1 ) \gamma\in(0,1) .
###### Proof.
Suppose γ ∈ ( 0 , 1 ) \gamma\in(0,1) . ND ( Norm ( F , γ ) ) \displaystyle\text{{ND}}\left(\text{{Norm}}\left(F,\gamma\right)\right) = ND ( ( 1 − γ ) F ( γ ) ) \displaystyle=\text{{ND}}\left((1-\gamma)F(\gamma)\right) (124) = ( 1 − γ ) ND ( F ( γ ) ) \displaystyle=(1-\gamma)\text{{ND}}\left(F(\gamma)\right) (125) = ( 1 − γ ) ( ND ( F ) ( γ ) ) \displaystyle=(1-\gamma)\left(\text{{ND}}\left(F\right)(\gamma)\right) (126) = Norm ( ND ( F ) , γ ) . \displaystyle=\text{{Norm}}\left(\text{{ND}}\left(F\right),\gamma\right). (127)
Equation 124 and eq. 127 follow by the continuity of Norm ( 𝐟 , γ ) \text{{Norm}}\left(\mathbf{f},\gamma\right) ( Lemma E.41 ). Equation 125 follows by Lemma E.15 item 1 . Equation 126 follows by Lemma E.31 .
Let γ = 1 \gamma=1 . Let 𝐝 ∈ ND ( Norm ( F , 1 ) ) \mathbf{d}\in\text{{ND}}\left(\text{{Norm}}\left(F,1\right)\right) be strictly optimal for 𝐫 ∗ ∈ ℝ | 𝒮 | \mathbf{r}^{*}\in\mathbb{R}^{\left|\mathcal{S}\right|} . Then let F 𝐝 ⊆ F F_{\mathbf{d}}\subseteq F be the subset of 𝐟 ∈ F \mathbf{f}\in F such that Norm ( 𝐟 , 1 ) = 𝐝 \text{{Norm}}\left(\mathbf{f},1\right)=\mathbf{d} . max 𝐟 ∈ F 𝐝 Norm ( 𝐟 , 1 ) ⊤ 𝐫 ∗ \displaystyle\max_{\mathbf{f}\in F_{\mathbf{d}}}\text{{Norm}}\left(\mathbf{f},1\right)^{\top}\mathbf{r}^{*} > max 𝐟 ′ ∈ F ∖ F 𝐝 Norm ( 𝐟 ′ , 1 ) ⊤ 𝐫 ∗ . \displaystyle>\max_{\mathbf{f}^{\prime}\in F\setminus F_{\mathbf{d}}}\text{{Norm}}\left(\mathbf{f}^{\prime},1\right)^{\top}\mathbf{r}^{*}. (128)
Since Norm ( 𝐟 , 1 ) \text{{Norm}}\left(\mathbf{f},1\right) is continuous at γ = 1 \gamma=1 ( Lemma E.41 ), 𝐱 ⊤ 𝐫 ∗ \mathbf{x}^{\top}\mathbf{r}^{*} is continuous on 𝐱 ∈ ℝ | 𝒮 | \mathbf{x}\in\mathbb{R}^{\left|\mathcal{S}\right|} , and F F is finite, eq. 128 holds for some γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) sufficiently close to γ = 1 \gamma=1 . By Lemma E.10 , at least one 𝐟 ∈ F 𝐝 \mathbf{f}\in F_{\mathbf{d}} is an element of ND ( F ( γ ∗ ) ) \text{{ND}}\left(F(\gamma^{*})\right) . Then by Lemma E.31 , 𝐟 ∈ ND ( F ) \mathbf{f}\in\text{{ND}}\left(F\right) . We conclude that ND ( Norm ( F , 1 ) ) ⊆ Norm ( ND ( F ) , 1 ) \text{{ND}}\left(\text{{Norm}}\left(F,1\right)\right)\subseteq\text{{Norm}}\left(\text{{ND}}\left(F\right),1\right) .
The case for γ = 0 \gamma=0 proceeds similarly. ∎
###### Lemma E.43 ( Power limit identity) .
Let γ ∈ [ 0 , 1 ] \gamma\in[0,1] . Power 𝒟 bound ( s , γ ) \displaystyle\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) = 𝔼 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ 𝐟 ∈ ℱ nd ( s ) 1 − γ ∗ γ ∗ ( 𝐟 ( γ ∗ ) − 𝐞 s ) ⊤ 𝐫 ] . \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{f}\in\Fndop(s)}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}(\gamma^{*})-\mathbf{e}_{s}\right)^{\top}\mathbf{r}\right]. (129)
###### Proof.
Let γ ∈ [ 0 , 1 ] \gamma\in[0,1] . Power 𝒟 bound ( s , γ ) \displaystyle\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) = lim γ ∗ → γ Power 𝒟 bound ( s , γ ∗ ) \displaystyle=\lim_{\gamma^{*}\to\gamma}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma^{*}\right) (130) = lim γ ∗ → γ 𝔼 𝐫 ∼ 𝒟 bound [ max 𝐟 ∈ ℱ nd ( s ) 1 − γ ∗ γ ∗ ( 𝐟 ( γ ∗ ) − 𝐞 s ) ⊤ 𝐫 ] \displaystyle=\lim_{\gamma^{*}\to\gamma}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{f}\in\Fndop(s)}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}(\gamma^{*})-\mathbf{e}_{s}\right)^{\top}\mathbf{r}\right] (131) = 𝔼 𝐫 ∼ 𝒟 bound [ lim γ ∗ → γ max 𝐟 ∈ ℱ nd ( s ) 1 − γ ∗ γ ∗ ( 𝐟 ( γ ∗ ) − 𝐞 s ) ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\lim_{\gamma^{*}\to\gamma}\max_{\mathbf{f}\in\Fndop(s)}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}(\gamma^{*})-\mathbf{e}_{s}\right)^{\top}\mathbf{r}\right] (132) = 𝔼 𝐫 ∼ 𝒟 bound [ max lim γ ∗ → γ 𝐟 ∈ ℱ nd ( s ) 1 − γ ∗ γ ∗ ( 𝐟 ( γ ∗ ) − 𝐞 s ) ⊤ 𝐫 ] . \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[\max_{\mathbf{f}\in\Fndop(s)}\lim_{\gamma^{*}\to\gamma}\frac{1-\gamma^{*}}{\gamma^{*}}\left(\mathbf{f}(\gamma^{*})-\mathbf{e}_{s}\right)^{\top}\mathbf{r}\right]. (133) Equation 130 follows because Power 𝒟 bound ( s , γ ) \text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right) is continuous on γ ∈ [ 0 , 1 ] \gamma\in[0,1] by Lemma 5.3 . Equation 131 follows by Lemma E.36 .