Optimal Policies Tend to Seek Power — part 9/16

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

Equation 60 holds because ϕ \phi is an involution. Equation 61 and eq. 63 hold by applying Lemma E.27 with permutation ϕ \phi . Equation 62 holds by assumption. Therefore, p 𝒟 any ( A ≥ C ) ≤ most : 𝔇 any p 𝒟 any ( B ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) by Lemma E.16 .

Suppose B ′ ⊆ C B^{\prime}\subseteq C and ND ​ ( C ) ∩ ( B ∖ B ′ ) \text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right) is non-empty, and let 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} be any continuous distribution which distributes reward independently and identically across states. Let ϕ ′ ∈ S | 𝒮 | \phi^{\prime}\in S_{\left|\mathcal{S}\right|} . p ϕ ′ ⋅ 𝒟 X ​ - iid ​ ( A ≥ C ) \displaystyle p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(A\geq C\right) = p 𝒟 X ​ - iid ​ ( A ≥ C ) \displaystyle=p_{\mathcal{D}_{X\text{-}\textsc{iid}}}\left(A\geq C\right) (64) < p ϕ ⋅ 𝒟 X ​ - iid ​ ( B ≥ C ) \displaystyle<p_{\phi\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(B\geq C\right) (65) = p ϕ ′ ⋅ 𝒟 X ​ - iid ​ ( A ≥ C ) . \displaystyle=p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(A\geq C\right). (66)

Equation 64 and eq. 66 hold because 𝒟 X ​ - iid \mathcal{D}_{X\text{-}\textsc{iid}} distributes reward identically across states, ∀ ϕ x ∈ S | 𝒮 | : ϕ x ⋅ 𝒟 X ​ - iid = 𝒟 X ​ - iid \forall\phi_{x}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\phi_{x}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}=\mathcal{D}_{X\text{-}\textsc{iid}} . By Lemma E.22 , ∃ 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}}) . Therefore, apply Lemma E.27 to conclude that eq. 65 holds.

Therefore, ∀ ϕ ′ ∈ S | 𝒮 | : p ϕ ′ ⋅ 𝒟 X ​ - iid ​ ( A ≥ C ) < p ϕ ′ ⋅ 𝒟 X ​ - iid ​ ( B ≥ C ) \forall\phi^{\prime}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(A\geq C\right)<p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(B\geq C\right) . In particular, p 𝒟 any ( A ≥ C ) ≱ most : 𝔇 any p 𝒟 any ( B ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) by definition 6.5 . ∎

###### Lemma E.29 (Limit probability inequalities which hold for most distributions) .

Let I ⊆ ℝ I\subseteq\mathbb{R} , let 𝔇 ⊆ Δ ⁡ ( ℝ | 𝒮 | ) \mathfrak{D}\subseteq\Delta(\mathbb{R}^{\left|\mathcal{S}\right|}) be closed under permutation, and let F A , F B , F C F_{A},F_{B},F_{C} be finite sets of vector functions I ↦ ℝ | 𝒮 | I\mapsto\mathbb{R}^{\left|\mathcal{S}\right|} . Let γ \gamma be a limit point of I I such that f 1 ​ ( 𝒟 ) ≔ lim γ ∗ → γ p 𝒟 ​ ( F B ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) , f 2 ​ ( 𝒟 ) ≔ lim γ ∗ → γ p 𝒟 ​ ( F A ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) f_{1}(\mathcal{D})\coloneqq\lim_{\gamma^{*}\to\gamma}p_{\mathcal{D}}\left(F_{B}(\gamma^{*})\geq F_{C}(\gamma^{*})\right),f_{2}(\mathcal{D})\coloneqq\lim_{\gamma^{*}\to\gamma}p_{\mathcal{D}}\left(F_{A}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) are well-defined for all 𝒟 ∈ 𝔇 \mathcal{D}\in\mathfrak{D} .

Let F Z F_{Z} satisfy ND ​ ( F C ) ⊆ F Z ⊆ F C \text{{ND}}\left(F_{C}\right)\subseteq F_{Z}\subseteq F_{C} . Suppose F B F_{B} contains a copy of F A F_{A} via ϕ \phi such that ϕ ⋅ ( F Z ∖ ( F B ∖ ϕ ⋅ F A ) ) = F Z ∖ ( F B ∖ ϕ ⋅ F A ) \phi\cdot\left(F_{Z}\setminus\left(F_{B}\setminus\phi\cdot F_{A}\right)\right)=F_{Z}\setminus\left(F_{B}\setminus\phi\cdot F_{A}\right) . Then f 2 ( 𝔇 ) ≤ most : 𝔇 f 1 ( 𝔇 ) f_{2}(\mathfrak{D})\leq_{\text{{most}}\text{: }\mathfrak{D}}f_{1}(\mathfrak{D}) .

###### Proof.

Suppose 𝒟 ∈ 𝔇 \mathcal{D}\in\mathfrak{D} is such that f 2 ​ ( 𝒟 ) > f 1 ​ ( 𝒟 ) f_{2}(\mathcal{D})>f_{1}(\mathcal{D}) . f 2 ​ ( ϕ ⋅ 𝒟 ) \displaystyle f_{2}\left(\phi\cdot\mathcal{D}\right) = f 2 ​ ( ϕ − 1 ⋅ 𝒟 ) \displaystyle=f_{2}\left(\phi^{-1}\cdot\mathcal{D}\right) (67) ≔ lim γ ∗ → γ p ϕ − 1 ⋅ 𝒟 ​ ( F A ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) \displaystyle\coloneqq\lim_{\gamma^{*}\to\gamma}p_{\phi^{-1}\cdot\mathcal{D}}\left(F_{A}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) (68) ≤ lim γ ∗ → γ p 𝒟 ​ ( F B ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) \displaystyle\leq\lim_{\gamma^{*}\to\gamma}p_{\mathcal{D}}\left(F_{B}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) (69) < lim γ ∗ → γ p 𝒟 ​ ( F A ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) \displaystyle<\lim_{\gamma^{*}\to\gamma}p_{\mathcal{D}}\left(F_{A}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) (70) ≤ lim γ ∗ → γ p ϕ ⋅ 𝒟 ​ ( F B ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) \displaystyle\leq\lim_{\gamma^{*}\to\gamma}p_{\phi\cdot\mathcal{D}}\left(F_{B}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) (71) ≕ f 1 ​ ( ϕ ⋅ 𝒟 ) . \displaystyle\eqqcolon f_{1}\left(\phi\cdot\mathcal{D}\right). (72) By the assumption that 𝔇 \mathfrak{D} is closed under permutation and f 2 f_{2} is well-defined for all 𝒟 ∈ 𝔇 \mathcal{D}\in\mathfrak{D} , f 2 ​ ( ϕ ⋅ 𝒟 ) f_{2}(\phi\cdot\mathcal{D}) is well-defined. Equation 67 follows since ϕ = ϕ − 1 \phi=\phi^{-1} because ϕ \phi is an involution. For all γ ∗ ∈ I \gamma^{*}\in I , let A ≔ F A ​ ( γ ∗ ) , B ≔ F B ​ ( γ ∗ ) , C ≔ F C ​ ( γ ∗ ) , Z ≔ F Z ​ ( γ ∗ ) A\coloneqq F_{A}(\gamma^{*}),B\coloneqq F_{B}(\gamma^{*}),C\coloneqq F_{C}(\gamma^{*}),Z\coloneqq F_{Z}(\gamma^{*}) (by definition E.13 , ND ​ ( C ) ⊆ Z ⊆ C \text{{ND}}\left(C\right)\subseteq Z\subseteq C ). Since ϕ ⋅ A ⊆ B \phi\cdot A\subseteq B by assumption, and since ND ​ ( A ) ⊆ A \text{{ND}}\left(A\right)\subseteq A , B B also contains a copy of ND ​ ( A ) \text{{ND}}\left(A\right) via ϕ \phi . Furthermore, ϕ ⋅ ( Z ∖ ( B ∖ ϕ ⋅ A ) ) = Z ∖ ( B ∖ ϕ ⋅ A ) \phi\cdot\left(Z\setminus\left(B\setminus\phi\cdot A\right)\right)=Z\setminus\left(B\setminus\phi\cdot A\right) (by assumption), and so apply Lemma E.27 to conclude that p ϕ − 1 ⋅ 𝒟 ​ ( F A ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) ≤ p 𝒟 ​ ( F B ​ ( γ ∗ ) ≥ F C ​ ( γ ∗ ) ) p_{\phi^{-1}\cdot\mathcal{D}}\left(F_{A}(\gamma^{*})\geq F_{C}(\gamma^{*})\right)\leq p_{\mathcal{D}}\left(F_{B}(\gamma^{*})\geq F_{C}(\gamma^{*})\right) . Therefore, the limit inequality eq. 69 holds. Equation 70 follows because we assumed that f 1 ​ ( 𝒟 ) < f 2 ​ ( 𝒟 ) f_{1}(\mathcal{D})<f_{2}(\mathcal{D}) . Equation 71 holds by reasoning similar to that given for eq. 69 .

Therefore, f 2 ​ ( 𝒟 ) > f 1 ​ ( 𝒟 ) f_{2}(\mathcal{D})>f_{1}(\mathcal{D}) implies that f 2 ​ ( ϕ ⋅ 𝒟 ) < f 1 ​ ( ϕ ⋅ 𝒟 ) f_{2}\left(\phi\cdot\mathcal{D}\right)<f_{1}\left(\phi\cdot\mathcal{D}\right) , and so apply Lemma E.16 to conclude that f 2 ( 𝒟 ) ≤ most : 𝔇 f 1 ( 𝒟 ) f_{2}(\mathcal{D})\leq_{\text{{most}}\text{: }\mathfrak{D}}f_{1}(\mathcal{D}) . ∎

#### E.1.3 ℱ nd \Fndop results

\transferDiscount

###### Proof.

Let R R be any reward function. Suppose γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) and construct R ′ ​ ( s ) ≔ V R ∗ ​ ( s , γ ) − γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] R^{\prime}(s)\coloneqq V^{*}_{R}\left(s,\gamma\right)-\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] .

Let π ∈ Π \pi\in\Pi be any policy. By the definition of optimal policies, π ∈ Π ∗ ​ ( R ′ , γ ∗ ) \pi\in\Pi^{*}\left(R^{\prime},\gamma^{*}\right) iff for all s s : R ′ ​ ( s ) + γ ∗ ​ 𝔼 s ′ ∼ T ⁡ ( s , π ⁡ ( s ) ) [ V R ′ ∗ ​ ( s ′ , γ ∗ ) ] \displaystyle R^{\prime}(s)+\gamma^{*}\opE_{s^{\prime}\sim T\left(s,\pi(s)\right)}\left[V^{*}_{R^{\prime}}\left(s^{\prime},\gamma^{*}\right)\right] = R ′ ​ ( s ) + γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ′ ∗ ​ ( s ′ , γ ∗ ) ] \displaystyle=R^{\prime}(s)+\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[V^{*}_{R^{\prime}}\left(s^{\prime},\gamma^{*}\right)\right] (73) R ′ ​ ( s ) + γ ∗ ​ 𝔼 s ′ ∼ T ⁡ ( s , π ⁡ ( s ) ) [ V R ∗ ​ ( s ′ , γ ) ] \displaystyle R^{\prime}(s)+\gamma^{*}\opE_{s^{\prime}\sim T\left(s,\pi(s)\right)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] = R ′ ​ ( s ) + γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] \displaystyle=R^{\prime}(s)+\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T\left(s,a\right)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] (74) γ ∗ ​ 𝔼 s ′ ∼ T ⁡ ( s , π ⁡ ( s ) ) [ V R ∗ ​ ( s ′ , γ ) ] \displaystyle\gamma^{*}\opE_{s^{\prime}\sim T\left(s,\pi(s)\right)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] = γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] \displaystyle=\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] (75) 𝔼 s ′ ∼ T ⁡ ( s , π ⁡ ( s ) ) [ V R ∗ ​ ( s ′ , γ ) ] \displaystyle\opE_{s^{\prime}\sim T\left(s,\pi(s)\right)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] = max a ∈ 𝒜 ⁡ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] . \displaystyle=\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right]. (76)

By the Bellman equations, R ′ ​ ( s ) = V R ′ ∗ ​ ( s , γ ∗ ) − γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ′ ∗ ​ ( s ′ , γ ∗ ) ] R^{\prime}(s)=V^{*}_{R^{\prime}}\left(s,\gamma^{*}\right)-\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R^{\prime}}\left(s^{\prime},\gamma^{*}\right)\right] . By the definition of R ′ R^{\prime} , V R ′ ∗ ​ ( ⋅ , γ ∗ ) = V R ∗ ​ ( ⋅ , γ ) V^{*}_{R^{\prime}}\left(\cdot,\gamma^{*}\right)=V^{*}_{R}\left(\cdot,\gamma\right) must be the unique solution to the Bellman equations for R ′ R^{\prime} at γ ∗ \gamma^{*} . Therefore, eq. 74 holds. Equation 75 follows by plugging in R ′ ≔ V R ∗ ​ ( s , γ ) − γ ∗ ​ max a ∈ 𝒜 ​ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] R^{\prime}\coloneqq V^{*}_{R}\left(s,\gamma\right)-\gamma^{*}\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] to eq. 74 and doing algebraic manipulation. Equation 76 follows because γ ∗ > 0 \gamma^{*}>0 .

Equation 76 shows that π ∈ Π ∗ ​ ( R ′ , γ ∗ ) \pi\in\Pi^{*}\left(R^{\prime},\gamma^{*}\right) iff ∀ s : 𝔼 s ′ ∼ T ⁡ ( s , π ⁡ ( s ) ) [ V R ∗ ​ ( s ′ , γ ) ] = max a ∈ 𝒜 ⁡ 𝔼 s ′ ∼ T ⁡ ( s , a ) [ V R ∗ ​ ( s ′ , γ ) ] \forall s\mathrel{\mathop{\ordinarycolon}}\opE_{s^{\prime}\sim T(s,\pi(s))}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right]=\max_{a\in\mathcal{A}}\opE_{s^{\prime}\sim T(s,a)}\left[V^{*}_{R}\left(s^{\prime},\gamma\right)\right] . That is, π ∈ Π ∗ ​ ( R ′ , γ ∗ ) \pi\in\Pi^{*}\left(R^{\prime},\gamma^{*}\right) iff π ∈ Π ∗ ​ ( R , γ ) \pi\in\Pi^{*}\left(R,\gamma\right) . ∎

###### Definition E.30 (Evaluating sets of visit distribution functions at γ \gamma ) .

For γ ∈ ( 0 , 1 ) \gamma\in(0,1) , define ℱ ⁡ ( s , γ ) ≔ { 𝐟 ⁡ ( γ ) ∣ 𝐟 ∈ ℱ ⁡ ( s ) } \Fop(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\Fop(s)\right\} and ℱ nd ⁡ ( s , γ ) ≔ { 𝐟 ⁡ ( γ ) ∣ 𝐟 ∈ ℱ nd ⁡ ( s ) } \Fndop(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\Fndop(s)\right\} . If F ⊆ ℱ ⁡ ( s ) F\subseteq\Fop(s) , then F ⁡ ( γ ) ≔ { 𝐟 ⁡ ( γ ) ∣ 𝐟 ∈ F } F(\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in F\right\} .

###### Lemma E.31 (Non-domination across γ \gamma values for expectations of visit distributions) .

Let Δ d ∈ Δ ⁡ ( ℝ | 𝒮 | ) \Delta_{d}\in\Delta\left(\mathbb{R}^{\left|\mathcal{S}\right|}\right) be any state distribution and let F ≔ { 𝔼 s d ∼ Δ d [ 𝐟 π , s d ] ∣ π ∈ Π } F\coloneqq\left\{\opE_{s_{d}\sim\Delta_{d}}\left[\mathbf{f}^{\pi,s_{d}}\right]\mid\pi\in\Pi\right\} . 𝐟 ∈ ND ​ ( F ) \mathbf{f}\in\text{{ND}}\left(F\right) iff ∀ γ ∗ ∈ ( 0 , 1 ) : 𝐟 ⁡ ( γ ∗ ) ∈ ND ​ ( F ⁡ ( γ ∗ ) ) \forall\gamma^{*}\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma^{*})\in\text{{ND}}\left(F(\gamma^{*})\right) .

###### Proof.

Let 𝐟 π ∈ ND ​ ( F ) \mathbf{f}^{\pi}\in\text{{ND}}\left(F\right) be strictly optimal for reward function R R at discount rate γ ∈ ( 0 , 1 ) \gamma\in(0,1) : 𝐟 π ​ ( γ ) ⊤ ​ 𝐫 > max 𝐟 π ′ ∈ F ∖ { 𝐟 π } ⁡ 𝐟 π ′ ​ ( γ ) ⊤ ​ 𝐫 . \displaystyle\mathbf{f}^{\pi}(\gamma)^{\top}\mathbf{r}>\max_{\mathbf{f}^{\pi^{\prime}}\in F\setminus\left\{\mathbf{f}^{\pi}\right\}}\mathbf{f}^{\pi^{\prime}}(\gamma)^{\top}\mathbf{r}. (77)

Let γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) . By section D.1.2 , we can produce R ′ R^{\prime} such that Π ∗ ​ ( R ′ , γ ∗ ) = Π ∗ ​ ( R , γ ) \Pi^{*}\left(R^{\prime},\gamma^{*}\right)=\Pi^{*}\left(R,\gamma\right) . Since the optimal policy sets are equal, Lemma E.1 implies that 𝐟 π ​ ( γ ∗ ) ⊤ ​ 𝐫 ′ > max 𝐟 π ′ ∈ F ∖ { 𝐟 π } ⁡ 𝐟 π ′ ​ ( γ ∗ ) ⊤ ​ 𝐫 ′ . \displaystyle\mathbf{f}^{\pi}(\gamma^{*})^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{f}^{\pi^{\prime}}\in F\setminus\left\{\mathbf{f}^{\pi}\right\}}\mathbf{f}^{\pi^{\prime}}(\gamma^{*})^{\top}\mathbf{r}^{\prime}. (78)

Therefore, 𝐟 π ​ ( γ ∗ ) ∈ ND ​ ( F ⁡ ( γ ∗ ) ) \mathbf{f}^{\pi}(\gamma^{*})\in\text{{ND}}\left(F(\gamma^{*})\right) .

The reverse direction follows by the definition of ND ​ ( F ) \text{{ND}}\left(F\right) . ∎

###### Lemma E.32 ( ∀ γ ∈ ( 0 , 1 ) : 𝐝 ∈ ℱ nd ⁡ ( s , γ ) \forall\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{d}\in\Fndop(s,\gamma) iff 𝐝 ∈ ND ​ ( ℱ ⁡ ( s , γ ) ) \mathbf{d}\in\text{{ND}}\left(\Fop(s,\gamma)\right) ) .

###### Proof.

By definition E.30 , ℱ nd ⁡ ( s , γ ) ≔ { 𝐟 ⁡ ( γ ) ∣ 𝐟 ∈ ND ​ ( ℱ ⁡ ( s ) ) } \Fndop(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\text{{ND}}\left(\Fop(s)\right)\right\} . By applying Lemma E.31 with Δ d ≔ 𝐞 s \Delta_{d}\coloneqq\mathbf{e}_{s} , 𝐟 ∈ ND ​ ( ℱ ⁡ ( s ) ) \mathbf{f}\in\text{{ND}}\left(\Fop(s)\right) iff ∀ γ ∈ ( 0 , 1 ) : 𝐟 ⁡ ( γ ) ∈ ND ​ ( ℱ ⁡ ( s , γ ) ) \forall\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma)\in\text{{ND}}\left(\Fop(s,\gamma)\right) . ∎

\optVfFndRestrict

###### Proof.

ND ​ ( ℱ ⁡ ( s , γ ) ) = ℱ nd ⁡ ( s , γ ) \text{{ND}}\left(\Fop(s,\gamma)\right)=\Fndop(s,\gamma) by Lemma E.32 , so apply Corollary E.11 with X ≔ ℱ ⁡ ( s , γ ) X\coloneqq\Fop(s,\gamma) . ∎

### E.2 Some actions have greater probability of being optimal

###### Lemma E.33 (Optimal policy shift bound) .

For fixed R R , Π ∗ ​ ( R , γ ) \Pi^{*}\left(R,\gamma\right) can take on at most ( 2 ​ | 𝒮 | + 1 ) ​ ∑ s ( | ℱ ⁡ ( s ) | 2 ) (2\left|\mathcal{S}\right|+1)\sum_{s}\binom{\left|\Fop(s)\right|}{2} distinct values over γ ∈ ( 0 , 1 ) \gamma\in(0,1) .

###### Proof.

By Lemma E.1 , Π ∗ ​ ( R , γ ) \Pi^{*}\left(R,\gamma\right) changes value iff there is a change in optimality status for some visit distribution function at some state. Lippman [1968] showed that two visit distribution functions can trade off optimality status at most 2 ​ | 𝒮 | + 1 2\left|\mathcal{S}\right|+1 times. At each state s s , there are ( | ℱ ⁡ ( s ) | 2 ) \binom{\left|\Fop(s)\right|}{2} such pairs. ∎

###### Proposition E.34 (Optimality probability’s limits exist) .

Let F ⊆ ℱ ⁡ ( s ) F\subseteq\Fop(s) . ℙ 𝒟 any ( F , 0 ) = lim γ → 0 ℙ 𝒟 any ( F , γ ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F,0\right)=\lim_{\gamma\to 0}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F,\gamma\right) and ℙ 𝒟 any ( F , 1 ) = lim γ → 1 ℙ 𝒟 any ( F , γ ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F,1\right)=\lim_{\gamma\to 1}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F,\gamma\right) .

###### Proof.

First consider the limit as γ → 1 \gamma\to 1 . Let 𝒟 any \mathcal{D}_{\text{any}} have probability measure F any F_{\text{any}} , and define δ ⁡ ( γ ) ≔ F any ​ ( { R ∈ ℝ 𝒮 ∣ ∃ γ ∗ ∈ [ γ , 1 ) : Π ∗ ​ ( R , γ ∗ ) ≠ Π ∗ ​ ( R , 1 ) } ) \delta(\gamma)\coloneqq F_{\text{any}}\left(\left\{R\in\mathbb{R}^{\mathcal{S}}\mid\exists\gamma^{*}\in[\gamma,1)\mathrel{\mathop{\ordinarycolon}}\Pi^{*}\left(R,\gamma^{*}\right)\neq\Pi^{*}\left(R,1\right)\right\}\right) . Since F any F_{\text{any}} is a probability measure, δ ⁡ ( γ ) \delta(\gamma) is bounded [ 0 , 1 ] [0,1] , and δ ⁡ ( γ ) \delta(\gamma) is monotone decreasing. Therefore, lim γ → 1 δ ⁡ ( γ ) \lim_{\gamma\to 1}\delta(\gamma) exists.