Optimal Policies Tend to Seek Power — part 13/16
Cleaned-text code points [186895, 201642). Bibliography omitted here; source.md includes it.
###### Lemma E.45 (Non-dominated visit distribution functions never agree with other visit distribution functions at that state) .
Let 𝐟 ∈ ℱ nd ( s ) , 𝐟 ′ ∈ ℱ ( s ) ∖ { 𝐟 } \mathbf{f}\in\Fndop(s),\mathbf{f}^{\prime}\in\Fop(s)\setminus\{\mathbf{f}\} . ∀ γ ∈ ( 0 , 1 ) : 𝐟 ( γ ) ≠ 𝐟 ′ ( γ ) \forall\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma)\neq\mathbf{f}^{\prime}(\gamma) .
###### Proof.
Let γ ∈ ( 0 , 1 ) \gamma\in(0,1) . Since 𝐟 ∈ ℱ nd ( s ) \mathbf{f}\in\Fndop(s) , there exists a γ ∗ ∈ ( 0 , 1 ) \gamma^{*}\in(0,1) at which 𝐟 \mathbf{f} is strictly optimal for some reward function. Then by section D.1.2 , we can produce another reward function for which 𝐟 \mathbf{f} is strictly optimal at discount rate γ \gamma ; in particular, section D.1.2 guarantees that the policies which induce 𝐟 ′ \mathbf{f}^{\prime} are not optimal at γ \gamma . So 𝐟 ( γ ) ≠ 𝐟 ′ ( γ ) \mathbf{f}(\gamma)\neq\mathbf{f}^{\prime}(\gamma) . ∎
###### Corollary E.46 (Cardinality of non-dominated visit distributions) .
Let F ⊆ ℱ ( s ) F\subseteq\Fop(s) . ∀ γ ∈ ( 0 , 1 ) : | F ∩ ℱ nd ( s ) | = | F ( γ ) ∩ ℱ nd ( s , γ ) | \forall\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\left|F\cap\Fndop(s)\right|=\left|F(\gamma)\cap\Fndop(s,\gamma)\right| .
###### Proof.
Let γ ∈ ( 0 , 1 ) \gamma\in(0,1) . By applying Lemma E.31 with Δ d ≔ 𝐞 s \Delta_{d}\coloneqq\mathbf{e}_{s} , 𝐟 ∈ ℱ nd ( s ) = ND ( ℱ ( s ) ) \mathbf{f}\in\Fndop(s)=\text{{ND}}\left(\Fop(s)\right) iff 𝐟 ( γ ) ∈ ND ( ℱ ( s , γ ) ) \mathbf{f}(\gamma)\in\text{{ND}}\left(\Fop(s,\gamma)\right) . By Lemma E.32 , ND ( ℱ ( s , γ ) ) = ℱ nd ( s , γ ) \text{{ND}}\left(\Fop(s,\gamma)\right)=\Fndop(s,\gamma) . So all 𝐟 ∈ F ∩ ℱ nd ( s ) \mathbf{f}\in F\cap\Fndop(s) induce 𝐟 ( γ ) ∈ F ( γ ) ∩ ℱ nd ( s , γ ) \mathbf{f}(\gamma)\in F(\gamma)\cap\Fndop(s,\gamma) , and | F ∩ ℱ nd ( s ) | ≥ | F ( γ ) ∩ ℱ nd ( s , γ ) | \left|F\cap\Fndop(s)\right|\geq\left|F(\gamma)\cap\Fndop(s,\gamma)\right| .
Lemma E.45 implies that for all 𝐟 , 𝐟 ′ ∈ ℱ nd ( s ) \mathbf{f},\mathbf{f}^{\prime}\in\Fndop(s) , 𝐟 = 𝐟 ′ \mathbf{f}=\mathbf{f}^{\prime} iff 𝐟 ( γ ) = 𝐟 ′ ( γ ) \mathbf{f}(\gamma)=\mathbf{f}^{\prime}(\gamma) . Therefore, | F ∩ ℱ nd ( s ) | ≤ | F ( γ ) ∩ ℱ nd ( s , γ ) | \left|F\cap\Fndop(s)\right|\leq\left|F(\gamma)\cap\Fndop(s,\gamma)\right| . So | F ∩ ℱ nd ( s ) | = | F ( γ ) ∩ ℱ nd ( s , γ ) | \left|F\cap\Fndop(s)\right|=\left|F(\gamma)\cap\Fndop(s,\gamma)\right| . ∎
###### Lemma E.47 (Optimality probability and state bottlenecks) .
Suppose that s s can reach Reach ( s ′ , a ′ ) ∪ Reach ( s ′ , a ) \text{{Reach}}\left(s^{\prime},a^{\prime}\right)\cup\text{{Reach}}\left(s^{\prime},a\right) , but only by taking actions equivalent to a ′ a^{\prime} or a a at state s ′ s^{\prime} . F nd , a ′ ≔ ℱ nd ( s ∣ π ( s ′ ) = a ′ ) , F a ≔ ℱ ( s ∣ π ( s ′ ) = a ) F_{\text{nd},a^{\prime}}\coloneqq\Fndop(s\mid\pi(s^{\prime})=a^{\prime}),F_{a}\coloneqq\Fop(s\mid\pi(s^{\prime})=a) . Suppose F a F_{a} contains a copy of F nd , a ′ F_{\text{nd},a^{\prime}} via ϕ \phi which fixes all states not belonging to Reach ( s ′ , a ′ ) ∪ Reach ( s ′ , a ) \text{{Reach}}\left(s^{\prime},a^{\prime}\right)\cup\text{{Reach}}\left(s^{\prime},a\right) . Then ∀ γ ∈ [ 0 , 1 ] : ℙ 𝒟 any ( F nd , a ′ , γ ) ≤ most : 𝔇 any ℙ 𝒟 any ( F a , γ ) \forall\gamma\in[0,1]\mathrel{\mathop{\ordinarycolon}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},\gamma\right) .
If ℱ nd ( s ) ∩ ( F a ∖ ϕ ⋅ F nd , a ′ ) \Fndop(s)\cap\left(F_{a}\setminus\phi\cdot F_{\text{nd},a^{\prime}}\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 ℙ 𝒟 any ( F nd , a ′ , γ ) ≱ most : 𝔇 any ℙ 𝒟 any ( F a , γ ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},\gamma\right) .
###### Proof.
Let F sub ≔ ϕ ⋅ F nd , a ′ F_{\text{sub}}\coloneqq\phi\cdot F_{\text{nd},a^{\prime}} . Let F ∗ ≔ ⋃ a ′′ ∈ 𝒜 : ( a ′′ ≢ s ′ a ) ∧ ( a ′′ ≢ s ′ a ′ ) ℱ ( s ∣ π ( s ′ ) = a ′′ ) ∪ F nd , a ′ ∪ F sub F^{*}\coloneqq\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\\ \left(a^{\prime\prime}\not\equiv_{s^{\prime}}a\right)\land\left(a^{\prime\prime}\not\equiv_{s^{\prime}}a^{\prime}\right)\end{subarray}}\Fop(s\mid\pi(s^{\prime})=a^{\prime\prime})\cup F_{\text{nd},a^{\prime}}\cup F_{\text{sub}} . ϕ ⋅ F ∗ ≔ \displaystyle\phi\cdot F^{*}\coloneqq\, ϕ ⋅ ( ⋃ a ′′ ∈ 𝒜 : ( a ′′ ≢ s ′ a ) ∧ ( a ′′ ≢ s ′ a ′ ) ℱ ( s ∣ π ( s ′ ) = a ′′ ) ∪ F nd , a ′ ∪ F sub ) \displaystyle\phi\cdot\left(\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\\ \left(a^{\prime\prime}\not\equiv_{s^{\prime}}a\right)\land\left(a^{\prime\prime}\not\equiv_{s^{\prime}}a^{\prime}\right)\end{subarray}}\Fop(s\mid\pi(s^{\prime})=a^{\prime\prime})\cup F_{\text{nd},a^{\prime}}\cup F_{\text{sub}}\right) (157) = \displaystyle=\, ⋃ a ′′ ∈ 𝒜 : ( a ′′ ≢ s ′ a ) ∧ ( a ′′ ≢ s ′ a ′ ) ϕ ⋅ ℱ ( s ∣ π ( s ′ ) = a ′′ ) ∪ ( ϕ ⋅ F nd , a ′ ) ∪ ( ϕ ⋅ F sub ) \displaystyle\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\\ \left(a^{\prime\prime}\not\equiv_{s^{\prime}}a\right)\land\left(a^{\prime\prime}\not\equiv_{s^{\prime}}a^{\prime}\right)\end{subarray}}\phi\cdot\Fop(s\mid\pi(s^{\prime})=a^{\prime\prime})\cup\left(\phi\cdot F_{\text{nd},a^{\prime}}\right)\cup\left(\phi\cdot F_{\text{sub}}\right) (158) = \displaystyle=\, ⋃ a ′′ ∈ 𝒜 : ( a ′′ ≢ s ′ a ) ∧ ( a ′′ ≢ s ′ a ′ ) ϕ ⋅ ℱ ( s ∣ π ( s ′ ) = a ′′ ) ∪ F sub ∪ F nd , a ′ \displaystyle\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\\ \left(a^{\prime\prime}\not\equiv_{s^{\prime}}a\right)\land\left(a^{\prime\prime}\not\equiv_{s^{\prime}}a^{\prime}\right)\end{subarray}}\phi\cdot\Fop(s\mid\pi(s^{\prime})=a^{\prime\prime})\cup F_{\text{sub}}\cup F_{\text{nd},a^{\prime}} (159) = \displaystyle=\, ⋃ a ′′ ∈ 𝒜 : ( a ′′ ≢ s ′ a ) ∧ ( a ′′ ≢ s ′ a ′ ) ℱ ( s ∣ π ( s ′ ) = a ′′ ) ∪ F sub ∪ F nd , a ′ \displaystyle\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\\ \left(a^{\prime\prime}\not\equiv_{s^{\prime}}a\right)\land\left(a^{\prime\prime}\not\equiv_{s^{\prime}}a^{\prime}\right)\end{subarray}}\Fop(s\mid\pi(s^{\prime})=a^{\prime\prime})\cup F_{\text{sub}}\cup F_{\text{nd},a^{\prime}} (160) ≕ \displaystyle\eqqcolon\, F ∗ . \displaystyle F^{*}. (161) Equation 159 follows because the involution ϕ \phi ensures that ϕ ⋅ F sub = F nd , a ′ \phi\cdot F_{\text{sub}}=F_{\text{nd},a^{\prime}} . By assumption, ϕ \phi fixes all s ′ ∉ Reach ( s ′ , a ′ ) ∪ Reach ( s ′ , a ) s^{\prime}\not\in\text{{Reach}}\left(s^{\prime},a^{\prime}\right)\cup\text{{Reach}}\left(s^{\prime},a\right) . Suppose 𝐟 ∈ ℱ ( s ) ∖ ( F nd , a ′ ∪ F a ) \mathbf{f}\in\Fop(s)\setminus\left(F_{\text{nd},a^{\prime}}\cup F_{a}\right) . By the bottleneck assumption, 𝐟 \mathbf{f} does not visit states in Reach ( s ′ , a ′ ) ∪ Reach ( s ′ , a ) \text{{Reach}}\left(s^{\prime},a^{\prime}\right)\cup\text{{Reach}}\left(s^{\prime},a\right) . Therefore, 𝐏 ϕ 𝐟 = 𝐟 \mathbf{P}_{\phi}\mathbf{f}=\mathbf{f} , and so eq. 160 follows.
Let F Z ≔ ( ℱ ( s ) ∖ ( ℱ ( s ∣ π ( s ) = a ′ ) ∪ F a ) ) ∪ F nd , a ′ ∪ F a F_{Z}\coloneqq\left(\Fop(s)\setminus(\Fop(s\mid\pi(s)=a^{\prime})\cup F_{a})\right)\cup F_{\text{nd},a^{\prime}}\cup F_{a} . By definition, F Z ⊆ ℱ ( s ) F_{Z}\subseteq\Fop(s) . Furthermore, ℱ nd ( s ) = ⋃ a ′′ ∈ 𝒜 ℱ nd ( s ∣ π ( s ′ ) = a ′′ ) ⊆ ( ℱ ( s ) ∖ ( ℱ ( s ∣ π ( s ) = a ′ ) ∪ F a ) ) ∪ ℱ nd ( s ∣ π ( s ) = a ′ ) ∪ F a ≕ F Z \Fndop(s)=\bigcup_{\begin{subarray}{c}a^{\prime\prime}\in\mathcal{A}\end{subarray}}\Fndop(s\mid\pi(s^{\prime})=a^{\prime\prime})\subseteq\left(\Fop(s)\setminus(\Fop(s\mid\pi(s)=a^{\prime})\cup F_{a})\right)\cup\Fndop(s\mid\pi(s)=a^{\prime})\cup F_{a}\eqqcolon F_{Z} , and so ℱ nd ( s ) ⊆ F Z \Fndop(s)\subseteq F_{Z} . Note that F ∗ = F Z ∖ ( F a ∖ F sub ) F^{*}=F_{Z}\setminus(F_{a}\setminus F_{\text{sub}}) .
##### Case: γ ∈ ( 0 , 1 ) \gamma\in(0,1) .
ℙ 𝒟 any ( F nd , a ′ , γ ) \displaystyle\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma\right) = p 𝒟 any ( F nd , a ′ ( γ ) ≥ ℱ ( s , γ ) ) \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}}(\gamma)\geq\Fop(s,\gamma)\right) (162) ≤ most : 𝔇 any p 𝒟 any ( F a ( γ ) ≥ ℱ ( s , γ ) ) \displaystyle\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(F_{a}(\gamma)\geq\Fop(s,\gamma)\right) (163) = ℙ 𝒟 any ( F nd , a ′ , γ ) . \displaystyle=\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma\right). (164)
Equation 162 and eq. 164 follow from Lemma E.35 . Equation 163 follows by applying Lemma E.28 with A ≔ F nd , a ′ ( γ ) , B ′ ≔ F sub ( γ ) , B ≔ F a ( γ ) , C ≔ ℱ ( s , γ ) , Z ≔ F Z ( γ ) A\coloneqq F_{\text{nd},a^{\prime}}(\gamma),B^{\prime}\coloneqq F_{\text{sub}}(\gamma),B\coloneqq F_{a}(\gamma),C\coloneqq\Fop(s,\gamma),Z\coloneqq F_{Z}(\gamma) which satisfies ND ( C ) = ℱ nd ( s , γ ) ⊆ F Z ( γ ) ⊆ ℱ ( s , γ ) = C \text{{ND}}\left(C\right)=\Fndop(s,\gamma)\subseteq F_{Z}(\gamma)\subseteq\Fop(s,\gamma)=C , and involution ϕ \phi which satisfies ϕ ⋅ F ∗ ( γ ) = ϕ ⋅ ( Z ∖ ( B ∖ B ′ ) ) = Z ∖ ( B ∖ B ′ ) = F ∗ ( γ ) \phi\cdot F^{*}(\gamma)=\phi\cdot\left(Z\setminus\left(B\setminus B^{\prime}\right)\right)=Z\setminus\left(B\setminus B^{\prime}\right)=F^{*}(\gamma) .
Suppose ℱ nd ( s ) ∩ ( F a ∖ F sub ) \Fndop(s)\cap\left(F_{a}\setminus F_{\text{sub}}\right) is non-empty. 0 < | ℱ nd ( s ) ∩ ( F a ∖ F sub ) | = | ℱ nd ( s , γ ) ∩ ( F a ( γ ) ∖ F sub ( γ ) ) | ≕ | ND ( C ) ∩ ( B ∖ B ′ ) | 0<\left|\Fndop(s)\cap\left(F_{a}\setminus F_{\text{sub}}\right)\right|=\left|\Fndop(s,\gamma)\cap\left(F_{a}(\gamma)\setminus F_{\text{sub}}(\gamma)\right)\right|\eqqcolon\left|\text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right)\right| (with the first equality holding by Corollary E.46 ), and so ND ( C ) ∩ ( B ∖ B ′ ) \text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right) is non-empty. We also have B ≔ F a ( γ ) ⊆ ℱ ( s , γ ) ≕ C B\coloneqq F_{a}(\gamma)\subseteq\Fop(s,\gamma)\eqqcolon C . Then reapplying Lemma E.28 , eq. 163 is strict for all 𝒟 X - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} , and ℙ 𝒟 any ( F nd , a ′ , γ ) ≱ most : 𝔇 any ℙ 𝒟 any ( F a , γ ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},\gamma\right) .
##### Case: γ = 1 \gamma=1 , γ = 0 \gamma=0 .
ℙ 𝒟 any ( F nd , a ′ , 1 ) \displaystyle\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},1\right) = lim γ ∗ → 1 ℙ 𝒟 any ( F nd , a ′ , γ ∗ ) \displaystyle=\lim_{\gamma^{*}\to 1}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}},\gamma^{*}\right) (165) = lim γ ∗ → 1 p 𝒟 any ( F nd , a ′ ( γ ∗ ) ≥ ℱ ( s , γ ∗ ) ) \displaystyle=\lim_{\gamma^{*}\to 1}p_{\mathcal{D}_{\text{any}}}\left(F_{\text{nd},a^{\prime}}(\gamma^{*})\geq\Fop(s,\gamma^{*})\right) (166) ≤ most : 𝔇 any lim γ ∗ → 1 p 𝒟 any ( F a ( γ ∗ ) ≥ ℱ ( s , γ ∗ ) ) \displaystyle\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}\lim_{\gamma^{*}\to 1}p_{\mathcal{D}_{\text{any}}}\left(F_{a}(\gamma^{*})\geq\Fop(s,\gamma^{*})\right) (167) = lim γ ∗ → 1 ℙ 𝒟 any ( F a , γ ∗ ) \displaystyle=\lim_{\gamma^{*}\to 1}\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},\gamma^{*}\right) (168) = ℙ 𝒟 any ( F a , 1 ) . \displaystyle=\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},1\right). (169) Equation 165 and eq. 169 hold by Proposition E.34 . Equation 166 and eq. 168 follow by Lemma E.35 . Applying Lemma E.29 with γ ≔ 1 , I ≔ ( 0 , 1 ) , F A ≔ F nd , a ′ , F B ≔ F a , F C ≔ ℱ ( s ) \gamma\coloneqq 1,I\coloneqq(0,1),F_{A}\coloneqq F_{\text{nd},a^{\prime}},F_{B}\coloneqq F_{a},F_{C}\coloneqq\Fop(s) , F Z F_{Z} as defined above, and involution ϕ \phi (for which ϕ ⋅ ( 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) ), we conclude that eq. 167 follows.
The γ = 0 \gamma=0 case proceeds similarly to γ = 1 \gamma=1 . ∎
###### Lemma E.48 (Action optimality probability is a special case of visit distribution optimality probability) .
ℙ 𝒟 any ( s , a , γ ) = ℙ 𝒟 any ( ℱ ( s ∣ π ( s ) = a ) , γ ) \Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(s,a,\gamma\right)=\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(\Fop(s\mid\pi(s)=a),\gamma\right) .
###### Proof.
Let F a ≔ ℱ ( s ∣ π ( s ) = a ) F_{a}\coloneqq\Fop(s\mid\pi(s)=a) . For γ ∈ ( 0 , 1 ) \gamma\in(0,1) , ℙ 𝒟 any ( s , a , γ ) \displaystyle\Prb_{\mathcal{D}_{\text{any}}}\left(s,a,\gamma\right) ≔ ℙ R ∼ 𝒟 any ( ∃ π ∗ ∈ Π ∗ ( R , γ ) : π ∗ ( s ) = a ) \displaystyle\coloneqq\Prb_{R\sim\mathcal{D}_{\text{any}}}\left(\exists\pi^{*}\in\Pi^{*}\left(R,\gamma\right)\mathrel{\mathop{\ordinarycolon}}\pi^{*}(s)=a\right) (170) = ℙ 𝐫 ∼ 𝒟 any ( ∃ 𝐟 π ∗ , s ∈ F a : 𝐟 π ∗ , s ( γ ) ⊤ 𝐫 = max 𝐟 ∈ ℱ ( s ) 𝐟 ( γ ) ⊤ 𝐫 ) \displaystyle=\Prb_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left(\exists\mathbf{f}^{\pi^{*},s}\in F_{a}\mathrel{\mathop{\ordinarycolon}}\mathbf{f}^{\pi^{*},s}(\gamma)^{\top}\mathbf{r}=\max_{\mathbf{f}\in\Fop(s)}\mathbf{f}(\gamma)^{\top}\mathbf{r}\right) (171) = ℙ 𝒟 any ( F a , γ ) . \displaystyle=\Prb\nolimits_{\mathcal{D}_{\text{any}}}\left(F_{a},\gamma\right). (172) By Lemma E.1 , if ∃ π ∗ ∈ Π ∗ ( R , γ ) : π ∗ ( s ) = a \exists\pi^{*}\in\Pi^{*}\left(R,\gamma\right)\mathrel{\mathop{\ordinarycolon}}\pi^{*}(s)=a , then it induces some optimal 𝐟 π ∗ , s ∈ F a \mathbf{f}^{\pi^{*},s}\in F_{a} . Conversely, if 𝐟 π ∗ , s ∈ F a \mathbf{f}^{\pi^{*},s}\in F_{a} is optimal at γ ∈ ( 0 , 1 ) \gamma\in(0,1) , then π ∗ \pi^{*} chooses optimal actions on the support of 𝐟 π ∗ , s ( γ ) \mathbf{f}^{\pi^{*},s}(\gamma) . Let π ′ \pi^{\prime} agree with π ∗ \pi^{*} on that support and let π ′ \pi^{\prime} take optimal actions at all other states. Then π ′ ∈ Π ∗ ( R , γ ) \pi^{\prime}\in\Pi^{*}\left(R,\gamma\right) and π ′ ( s ) = a \pi^{\prime}(s)=a . So eq. 171 follows.