Optimal Policies Tend to Seek Power — part 5/16

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

If ℙ 𝒟 any ( s 1 , N , 1 ) ≥ most : 𝔇 any ℙ 𝒟 any ( s 1 , NE , 1 ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{N},1\right)\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{NE},1\right) , then Lemma B.3 shows that ℙ 𝒟 X ​ - iid ( s 1 , N , 1 ) ≥ ℙ 𝒟 X ​ - iid ( s 1 , NE , 1 ) \Prb\nolimits_{\mathcal{D}_{X\text{-}\textsc{iid}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{N},1\right)\geq\Prb\nolimits_{\mathcal{D}_{X\text{-}\textsc{iid}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{NE},1\right) for all 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} . But the proof of Proposition B.1 showed that ℙ 𝒟 X u ​ - iid ( s 1 , N , 1 ) < ℙ 𝒟 X u ​ - iid ( s 1 , NE , 1 ) \Prb\nolimits_{\mathcal{D}_{X_{u}\text{-}\textsc{iid}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{N},1\right)<\Prb\nolimits_{\mathcal{D}_{X_{u}\text{-}\textsc{iid}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{NE},1\right) for X u ≔ unif ​ ( 0 , 1 ) X_{u}\coloneqq\text{unif}(0,1) . Therefore, it cannot be true that ℙ 𝒟 any ( s 1 , N , 1 ) ≥ most : 𝔇 any ℙ 𝒟 any ( s 1 , NE , 1 ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{N},1\right)\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left({\color[rgb]{0.25,0.45,0.75}s_{1}},\texttt{NE},1\right) . ∎

## Appendix C Sub-optimal Power

In certain situations, Power returns intuitively surprising verdicts. There exists a policy under which the reader chooses a winning lottery ticket, but it seems wrong to say that the reader has the power to win the lottery with high probability. For various reasons, humans and other bounded agents are generally incapable of computing optimal policies for arbitrary objectives. More formally, consider the rewardless mdp of fig. 11 .

Consider a model-based RL agent with black-box simulator access to this environment. The agent has no prior information about the model, and so it acts randomly. Before long, the agent has probably learned how to navigate from s 0 {\color[rgb]{0.25,0.45,0.75}s_{0}} to states s ℓ s_{\ell} , s r s_{r} , s 1 s_{1} , s 2 s_{2} , and s 5 s_{5} . However, over any reasonable timescale, it is extremely improbable that the agent discovers the two actions respectively leading to s 3 s_{3} and s 4 s_{4} .

Even provided with a reward function R R and the discount rate γ \gamma , the agent has yet to learn the relevant environmental dynamics, and so many of its policies are far from optimal. Although Proposition 6.6 shows that ∀ γ ∈ [ 0 , 1 ] : Power 𝒟 bound ( s ℓ , γ ) ≤ most : 𝔇 bound Power 𝒟 bound ( s r , γ ) \forall\gamma\in[0,1]\mathrel{\mathop{\ordinarycolon}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{\ell},\gamma\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s_{r},\gamma\right) , there is a sense in which s ℓ s_{\ell} gives this agent more power.

We formalize a bounded agent’s goal-achievement capabilities with a function pol , which takes as input a reward function and a discount rate, and returns a policy. Informally, this is the best policy which the agent knows about. We can then calculate Power 𝒟 bound \text{{Power}}_{\mathcal{D}_{\text{bound}}} with respect to pol .

###### Definition C.1 (Suboptimal Power ) .

Let Π Δ \Pi_{\Delta} be the set of stationary stochastic policies, and let pol : ℝ 𝒮 × [ 0 , 1 ] → Π Δ \text{pol}\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{\mathcal{S}}\times[0,1]\to\Pi_{\Delta} . For γ ∈ [ 0 , 1 ] \gamma\in[0,1] , Power 𝒟 bound pol ​ ( s , γ ) ≔ 𝔼 R ∼ 𝒟 bound , a ∼ pol ​ ( R , γ ) ​ ( s ) , s ′ ∼ T ⁡ ( s , a ) [ lim γ ∗ → γ ( 1 − γ ∗ ) ​ V R pol ​ ( R , γ ) ​ ( s ′ , γ ∗ ) ] . \displaystyle\text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)\coloneqq\opE_{\begin{subarray}{c}R\sim\mathcal{D}_{\text{bound}},\\ a\sim\text{pol}\left(R,\gamma\right)(s),\\ s^{\prime}\sim T\left(s,a\right)\end{subarray}}\left[\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})V^{\text{pol}\left(R,\gamma\right)}_{R}\left(s^{\prime},\gamma^{*}\right)\right]. (5)

By Lemma E.36 , Power 𝒟 bound \text{{Power}}_{\mathcal{D}_{\text{bound}}} is the special case where ∀ R ∈ ℝ 𝒮 , γ ∈ [ 0 , 1 ] : pol ​ ( R , γ ) ∈ Π ∗ ​ ( R , γ ) \forall R\in\mathbb{R}^{\mathcal{S}},\gamma\in[0,1]\mathrel{\mathop{\ordinarycolon}}\text{pol}\left(R,\gamma\right)\in\Pi^{*}\left(R,\gamma\right) . We define Power 𝒟 bound pol \text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}} -seeking similarly as in definition 5.6 .

Power 𝒟 bound pol ​ ( s 0 , 1 ) \text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{0.25,0.45,0.75}s_{0}},1\right) increases as the policies returned by pol are improved. We illustrate this by considering the 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} case.

pol 1 \text{pol}_{1} The model is initially unknown, and so ∀ R , γ : pol 1 ​ ( R , γ ) \forall R,\gamma\mathrel{\mathop{\ordinarycolon}}\text{pol}_{1}(R,\gamma) is a uniformly random policy. Since pol 1 \text{pol}_{1} is constant on its inputs, Power 𝒟 X ​ - iid pol 1 ​ ( s 0 , 1 ) = 𝔼 [ X ] \text{{Power}}^{\text{pol}_{1}}_{\mathcal{D}_{X\text{-}\textsc{iid}}}\left({\color[rgb]{0.25,0.45,0.75}s_{0}},1\right)=\opE\left[X\right] by the linearity of expectation and the fact that 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} distributes reward independently and identically across states.

pol 2 \text{pol}_{2} The agent knows the dynamics, except that it does not know how to reach s 3 s_{3} or s 4 s_{4} . At this point, pol 2 ​ ( R , 1 ) \text{pol}_{2}(R,1) navigates from s 0 {\color[rgb]{0.25,0.45,0.75}s_{0}} to the average-optimal choice among three terminal states: s 1 s_{1} , s 2 s_{2} , and s 5 s_{5} . Therefore, Power 𝒟 bound pol 2 ​ ( s 0 , 1 ) = 𝔼 [ max ⁡ of ​ 3 ​ draws from ​ X ] \text{{Power}}^{\text{pol}_{2}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{0.25,0.45,0.75}s_{0}},1\right)=\opE\left[\max\text{ of }3\text{ draws from }X\right] .

pol 3 \text{pol}_{3} The agent knows the dynamics, the environment is small enough to solve explicitly, and so ∀ R , γ : pol 3 ​ ( R , γ ) \forall R,\gamma\mathrel{\mathop{\ordinarycolon}}\text{pol}_{3}(R,\gamma) is an optimal policy. pol 3 ​ ( R , 1 ) \text{pol}_{3}(R,1) navigates from s 0 {\color[rgb]{0.25,0.45,0.75}s_{0}} to the average-optimal choice among all five terminal states. Therefore, Power 𝒟 bound pol 3 ​ ( s 0 , 1 ) = 𝔼 [ max ⁡ of ​ 5 ​ draws from ​ X ] \text{{Power}}^{\text{pol}_{3}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{0.25,0.45,0.75}s_{0}},1\right)=\opE\left[\max\text{ of }5\text{ draws from }X\right] .

As the agent learns more about the environment and improves pol , the agent’s Power 𝒟 bound pol \text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}} increases. The agent seeks Power 𝒟 bound pol 2 \text{{Power}}^{\text{pol}_{2}}_{\mathcal{D}_{\text{bound}}} by navigating to s ℓ s_{\ell} instead of s r s_{r} , but seeks more Power 𝒟 bound \text{{Power}}_{\mathcal{D}_{\text{bound}}} by navigating to s r s_{r} instead of s ℓ s_{\ell} . Intuitively, bounded agents gain power by improving pol and by formally seeking Power 𝒟 bound pol \text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}} within the environment.

## Appendix D Lists of results

\ignoretheorems cor-no-num,conjecture,remark,definition

### D.1 Contributions of independent interest

We developed new basic mdp theory by exploring the structural properties of visit distribution functions. Echoing Wang et al. [2007] , Wang et al. [2008] , we believe that this area is interesting and underexplored.

#### D.1.1 Optimal value theory

Lemma E.38 shows that f ⁡ ( γ ∗ ) ≔ lim γ ∗ → γ ( 1 − γ ∗ ) ​ V R ∗ ​ ( s , γ ∗ ) f(\gamma^{*})\coloneqq\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})V^{*}_{R}\left(s,\gamma^{*}\right) is Lipschitz continuous on γ ∈ [ 0 , 1 ] \gamma\in[0,1] , with Lipschitz constant depending only on ‖ R ‖ 1 \left\lVert R\right\rVert_{1} . For all states s s and policies π ∈ Π \pi\in\Pi , Corollary E.5 shows that V R π ​ ( s , γ ) V^{\pi}_{R}(s,\gamma) is rational on γ \gamma .

Optimal value has a well-known dual formulation: V R ∗ ​ ( s , γ ) = max 𝐟 ∈ ℱ ⁡ ( s ) ⁡ 𝐟 ​ ( γ ) ⊤ ​ 𝐫 V^{*}_{R}\left(s,\gamma\right)=\max_{\mathbf{f}\in\Fop(s)}\mathbf{f}(\gamma)^{\top}\mathbf{r} . {restatable*} [ ∀ γ ∈ [ 0 , 1 ) : V R ∗ ​ ( s , γ ) = max 𝐟 ∈ ℱ nd ⁡ ( s ) ⁡ 𝐟 ​ ( γ ) ⊤ ​ 𝐫 \forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}V^{*}_{R}\left(s,\gamma\right)=\max_{\mathbf{f}\in\Fndop(s)}\mathbf{f}(\gamma)^{\top}\mathbf{r} ]lemoptVfFndRestrict In a fixed rewardless mdp , section D.1.1 may enable more efficient computation of optimal value functions for multiple reward functions.

#### D.1.2 Optimal policy theory

Section D.1.2 demonstrates how to preserve optimal incentives while changing the discount rate.

{restatable*} [How to transfer optimal policy sets across discount rates]proptransferDiscount Suppose reward function R R has optimal policy set Π ∗ ​ ( R , γ ) \Pi^{*}\left(R,\gamma\right) at discount rate γ ∈ ( 0 , 1 ) \gamma\in(0,1) . For any γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) , we can construct a reward function R ′ R^{\prime} such that Π ∗ ​ ( R ′ , γ ∗ ) = Π ∗ ​ ( R , γ ) \Pi^{*}\left(R^{\prime},\gamma^{*}\right)=\Pi^{*}\left(R,\gamma\right) . Furthermore, V R ′ ∗ ​ ( ⋅ , γ ∗ ) = V R ∗ ​ ( ⋅ , γ ) V^{*}_{R^{\prime}}\left(\cdot,\gamma^{*}\right)=V^{*}_{R}\left(\cdot,\gamma\right) .

#### D.1.3 Visit distribution theory

While Regan and Boutilier [2010] consider a visit distribution function 𝐟 ∈ ℱ ⁡ ( s ) \mathbf{f}\in\Fop(s) to be non-dominated if it is optimal for some reward function in a set ℛ ⊆ ℝ | 𝒮 | \mathcal{R}_{\text{}}\subseteq\mathbb{R}^{\left|\mathcal{S}\right|} , our stricter definition 3.6 considers 𝐟 \mathbf{f} to be non-dominated when ∃ 𝐫 ∈ ℝ | 𝒮 | , γ ∈ ( 0 , 1 ) : 𝐟 ​ ( γ ) ⊤ ​ 𝐫 > max 𝐟 ′ ∈ ℱ ⁡ ( s ) ∖ { 𝐟 } ⁡ 𝐟 ′ ​ ( γ ) ⊤ ​ 𝐫 \exists\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|},\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma)^{\top}\mathbf{r}>\max_{\mathbf{f}^{\prime}\in\Fop(s)\setminus\left\{\mathbf{f}\right\}}\mathbf{f}^{\prime}(\gamma)^{\top}\mathbf{r} .

## Appendix E Theoretical results

###### Lemma E.1 (A policy is optimal iff it induces an optimal visit distribution at every state) .

Let γ ∈ ( 0 , 1 ) \gamma\in(0,1) and let R R be a reward function. π ∈ Π ∗ ​ ( R , γ ) \pi\in\Pi^{*}\left(R,\gamma\right) iff π \pi induces an optimal visit distribution at every state.

###### Proof.

By definition, a policy π \pi is optimal iff π \pi induces the maximal on-policy value at each state, which is true iff π \pi induces an optimal visit distribution at every state (by the dual formulation of optimal value functions). ∎

###### Definition E.2 (Transition matrix induced by a policy) .

𝐓 π \mathbf{T}^{\pi} is the transition matrix induced by policy π ∈ Π \pi\in\Pi , where 𝐓 π ​ 𝐞 s ≔ T ⁡ ( s , π ⁡ ( s ) ) \mathbf{T}^{\pi}\mathbf{e}_{s}\coloneqq T(s,\pi(s)) . ( 𝐓 π ) t ​ 𝐞 s (\mathbf{T}^{\pi})^{t}\mathbf{e}_{s} gives the probability distribution over the states visited at time step t t , after following π \pi for t t steps from s s .

###### Proposition E.3 (Properties of visit distribution functions) .

Let s , s ′ ∈ 𝒮 , 𝐟 π , s ∈ ℱ ⁡ ( s ) s,s^{\prime}\in\mathcal{S},\mathbf{f}^{\pi,s}\in\Fop(s) . 1. 𝐟 π , s ​ ( γ ) \mathbf{f}^{\pi,s}(\gamma) is element-wise non-negative and element-wise monotonically increasing on γ ∈ [ 0 , 1 ) \gamma\in[0,1) .

2. ∀ γ ∈ [ 0 , 1 ) : ‖ 𝐟 π , s ​ ( γ ) ‖ 1 = 1 1 − γ \forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}\left\lVert\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{1}=\frac{1}{1-\gamma} .

###### Proof.

Item 1 : by examination of definition 3.3 , 𝐟 π , s = ∑ t = 0 ∞ ( γ ​ 𝐓 π ) t ​ 𝐞 s \mathbf{f}^{\pi,s}=\sum_{t=0}^{\infty}\left(\gamma\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s} . Since each ( 𝐓 π ) t \left(\mathbf{T}^{\pi}\right)^{t} is left stochastic and 𝐞 s \mathbf{e}_{s} is the standard unit vector, each entry in each summand is non-negative. Therefore, ∀ γ ∈ [ 0 , 1 ) : 𝐟 π , s ​ ( γ ) ⊤ ​ 𝐞 s ′ ≥ 0 \forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s^{\prime}}\geq 0 , and this function monotonically increases on γ \gamma .

Item 2 : ‖ 𝐟 π , s ​ ( γ ) ‖ 1 \displaystyle\left\lVert\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{1} = ‖ ∑ t = 0 ∞ ( γ ​ 𝐓 π ) t ​ 𝐞 s ‖ 1 \displaystyle=\left\lVert\sum_{t=0}^{\infty}\left(\gamma\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}\right\rVert_{1} (6) = ∑ t = 0 ∞ γ t ​ ‖ ( 𝐓 π ) t ​ 𝐞 s ‖ 1 \displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\left\lVert\left(\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}\right\rVert_{1} (7) = ∑ t = 0 ∞ γ t \displaystyle=\sum_{t=0}^{\infty}\gamma^{t} (8) = 1 1 − γ . \displaystyle=\frac{1}{1-\gamma}. (9)

Equation 7 follows because all entries in each ( 𝐓 π ) t ​ 𝐞 s \left(\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s} are non-negative by item 1 . Equation 8 follows because each ( 𝐓 π ) t \left(\mathbf{T}^{\pi}\right)^{t} is left stochastic and 𝐞 s \mathbf{e}_{s} is a stochastic vector, and so ‖ ( 𝐓 π ) t ​ 𝐞 s ‖ 1 = 1 \left\lVert\left(\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}\right\rVert_{1}=1 . ∎

###### Lemma E.4 ( 𝐟 ∈ ℱ ⁡ ( s ) \mathbf{f}\in\Fop(s) is multivariate rational on γ \gamma ) .

𝐟 π ∈ ℱ ⁡ ( s ) \mathbf{f}^{\pi}\in\Fop(s) is a multivariate rational function on γ ∈ [ 0 , 1 ) \gamma\in[0,1) .

###### Proof.

Let 𝐫 ∈ ℝ | 𝒮 | \mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|} and consider 𝐟 π ∈ ℱ ⁡ ( s ) \mathbf{f}^{\pi}\in\Fop(s) . Let 𝐯 R π \mathbf{v}^{\pi}_{R} be the V R ∗ ​ ( s , γ ) V^{*}_{R}\left(s,\gamma\right) function in column vector form, with one entry per state value.

By the Bellman equations, 𝐯 R π = ( 𝐈 − γ ​ 𝐓 π ) − 1 ​ 𝐫 . \mathbf{v}^{\pi}_{R}=\left(\mathbf{I}-\gamma\mathbf{T}^{\pi}\right)^{-1}\mathbf{r}. Let 𝐀 γ ≔ ( 𝐈 − γ ​ 𝐓 π ) − 1 \mathbf{A}_{\gamma}\coloneqq\left(\mathbf{I}-\gamma\mathbf{T}^{\pi}\right)^{-1} , and for state s s , form 𝐀 s , γ \mathbf{A}_{s,\gamma} by replacing 𝐀 γ \mathbf{A}_{\gamma} ’s column for state s s with 𝐫 \mathbf{r} . As noted by Lippman [1968] , by Cramer’s rule, V R π ​ ( s , γ ) = det 𝐀 s , γ det 𝐀 γ V^{\pi}_{R}(s,\gamma)=\frac{\det{\mathbf{A}_{s,\gamma}}}{\det\mathbf{A}_{\gamma}} is a rational function with numerator and denominator having degree at most | 𝒮 | \left|\mathcal{S}\right| .

In particular, for each state indicator reward function 𝐞 s i \mathbf{e}_{s_{i}} , V s i π ​ ( s , γ ) = 𝐟 π , s ​ ( γ ) ⊤ ​ 𝐞 s i V^{\pi}_{s_{i}}(s,\gamma)=\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s_{i}} is a rational function of γ \gamma whose numerator and denominator each have degree at most | 𝒮 | \left|\mathcal{S}\right| . This implies that 𝐟 π ​ ( γ ) \mathbf{f}^{\pi}(\gamma) is multivariate rational on γ ∈ [ 0 , 1 ) \gamma\in[0,1) . ∎

###### Corollary E.5 (On-policy value is rational on γ \gamma ) .

Let π ∈ Π \pi\in\Pi and R R be any reward function. V R π ​ ( s , γ ) V^{\pi}_{R}(s,\gamma) is rational on γ ∈ [ 0 , 1 ) \gamma\in[0,1) .

###### Proof.

V R π ​ ( s , γ ) = 𝐟 π , s ​ ( γ ) ⊤ ​ 𝐫 V^{\pi}_{R}(s,\gamma)=\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{r} , and 𝐟 \mathbf{f} is a multivariate rational function of γ \gamma by Lemma E.4 . Therefore, for fixed 𝐫 \mathbf{r} , 𝐟 π , s ​ ( γ ) ⊤ ​ 𝐫 \mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{r} is a rational function of γ \gamma . ∎

### E.1 Non-dominated visit distribution functions

###### Definition E.6 (Continuous reward function distribution) .

Results with 𝒟 cont \mathcal{D}_{\text{cont}} hold for any absolutely continuous reward function distribution.

###### Remark .

We assume ℝ | 𝒮 | \mathbb{R}^{\left|\mathcal{S}\right|} is endowed with the standard topology.

###### Lemma E.7 (Distinct linear functionals disagree almost everywhere on their domains) .