A Distributional Perspective on Reinforcement Learning — part 4/6

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

A number of probabilistic frameworks for reinforcement learning have been proposed in recent years. The planning as inference approach ( Toussaint & Storkey, 2006 ; Hoffman et al., 2009 ) embeds the return into a graphical model, and applies probabilistic inference to determine the sequence of actions leading to maximal expected reward. Wang et al. (2008) considered the dual formulation of reinforcement learning, where one optimizes the stationary distribution subject to constraints given by the transition function ( Puterman, 1994 ) , in particular its relationship to linear approximation. Related to this dual is the Compress and Control algorithm Veness et al. (2015) , which describes a value function by learning a return distribution using density models. One of the aims of this work was to address the question left open by their work of whether one could be design a practical distributional algorithm based on the Bellman equation, rather than Monte Carlo estimation.

## Appendix B Proofs

###### Lemma 1 (Partition lemma) .

Let A 1 , A 2 , … A_{1},A_{2},\dots be a set of random variables describing a partition of Ω \Omega , i.e. A i ​ ( ω ) ∈ { 0 , 1 } A_{i}(\omega)\in\{0,1\} and for any ω \omega there is exactly one A i A_{i} with A i ​ ( ω ) = 1 A_{i}(\omega)=1 . Let U , V U,V be two random variables. Then d p ​ ( U , V ) ≤ ∑ i d p ​ ( A i ​ U , A i ​ V ) . d_{p}\big(U,V\big)\leq\sum\nolimits_{i}d_{p}(A_{i}U,A_{i}V).

###### Proof.

We will give the proof for p < ∞ p<\infty , noting that the same applies to p = ∞ p=\infty . Let Y i : ⁣ = 𝐷 A i U Y_{i}\overset{D}{:=}A_{i}U and Z i : ⁣ = 𝐷 A i V Z_{i}\overset{D}{:=}A_{i}V , respectively. First note that d p p ​ ( A i ​ U , A i ​ V ) \displaystyle d^{p}_{p}(A_{i}U,A_{i}V) = inf Y i , Z i 𝔼 [ | Y i − Z i | p ] \displaystyle=\inf_{Y_{i},Z_{i}}\expect\big[|Y_{i}-Z_{i}|^{p}\big] = inf Y i , Z i 𝔼 [ 𝔼 [ | Y i − Z i | p | A i ] ] . \displaystyle=\inf_{Y_{i},Z_{i}}\expect\Big[\expect\big[|Y_{i}-Z_{i}|^{p}\,|\,A_{i}\big]\Big]. Now, | A i ​ U − A i ​ V | p = 0 |A_{i}U-A_{i}V|^{p}=0 whenever A i = 0 A_{i}=0 . It follows that we can choose Y i , Z i Y_{i},Z_{i} so that also | Y i − Z i | p = 0 |Y_{i}-Z_{i}|^{p}=0 whenever A i = 0 A_{i}=0 , without increasing the expected norm. Hence d p p ​ ( A i ​ U , A i ​ V ) \displaystyle d^{p}_{p}(A_{i}U,A_{i}V) = \displaystyle= inf Y i , Z i Pr { A i = 1 } 𝔼 [ | Y i − Z i | p | A i = 1 ] . \displaystyle\hskip-35.00005pt\inf_{Y_{i},Z_{i}}\Pr\{A_{i}=1\}\expect\big[|Y_{i}-Z_{i}|^{p}\,|\,A_{i}=1\big]. (8) Next, we claim that inf U , V ∑ i Pr { A i = 1 } 𝔼 [ | A i U − A i V | p | A i = 1 ] \displaystyle\inf_{U,V}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\Big[\big|A_{i}U-A_{i}V\big|^{p}\,|\,A_{i}=1\Big] (9) ≤ inf Y 1 , Y 2 , … Z 1 , Z 2 , … ∑ i Pr { A i = 1 } 𝔼 [ | Y i − Z i | p | A i = 1 ] . \displaystyle\hskip 20.00003pt\leq\inf_{\begin{subarray}{c}Y_{1},Y_{2},\dots\\ Z_{1},Z_{2},\dots\end{subarray}}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\Big[|Y_{i}-Z_{i}\big|^{p}\,|\,A_{i}=1\Big]. Specifically, the left-hand side of the equation is an infimum over all r.v.’s whose cumulative distributions are F U F_{U} and F V F_{V} , respectively, while the right-hand side is an infimum over sequences of r.v’s Y 1 , Y 2 , … Y_{1},Y_{2},\dots and Z 1 , Z 2 , … Z_{1},Z_{2},\dots whose cumulative distributions are F A i ​ U , F A i ​ V F_{A_{i}U},F_{A_{i}V} , respectively. To prove this upper bound, consider the c.d.f. of U U : F U ​ ( y ) \displaystyle F_{U}(y) = Pr { U ≤ y } \displaystyle=\Pr\{U\leq y\} = ∑ i Pr { A i = 1 } Pr { U ≤ y | A i = 1 } \displaystyle=\sum\nolimits_{i}\Pr\{A_{i}=1\}\Pr\{U\leq y\,|\,A_{i}=1\} = ∑ i Pr { A i = 1 } Pr { A i U ≤ y | A i = 1 } . \displaystyle=\sum\nolimits_{i}\Pr\{A_{i}=1\}\Pr\{A_{i}U\leq y\,|\,A_{i}=1\}. Hence the distribution F U F_{U} is equivalent, in an almost sure sense, to one that first picks an element A i A_{i} of the partition, then picks a value for U U conditional on the choice A i A_{i} . On the other hand, the c.d.f. of Y i ​ = 𝐷 ​ A i ​ U Y_{i}\overset{D}{=}A_{i}U is F A i ​ U ​ ( y ) \displaystyle F_{A_{i}U}(y) = Pr { A i = 1 } Pr { A i U ≤ y | A i = 1 } \displaystyle=\Pr\{A_{i}=1\}\Pr\{A_{i}U\leq y\,|\,A_{i}=1\} + Pr { A i = 0 } Pr { A i U ≤ y | A i = 0 } \displaystyle\hskip 10.00002pt+\Pr\{A_{i}=0\}\Pr\{A_{i}U\leq y\,|\,A_{i}=0\} = Pr { A i = 1 } Pr { A i U ≤ y | A i = 1 } \displaystyle=\Pr\{A_{i}=1\}\Pr\{A_{i}U\leq y\,|\,A_{i}=1\} + Pr { A i = 0 } 𝕀 [ y ≥ 0 ] . \displaystyle\hskip 10.00002pt+\Pr\{A_{i}=0\}\mathbb{I}\left[y\geq 0\right]. Thus the right-hand side infimum in ( 9 ) has the additional constraint that it must preserve the conditional c.d.fs, in particular when y ≥ 0 y\geq 0 . Put another way, instead of having the freedom to completely reorder the mapping U : Ω → ℝ U:\Omega\to\mathbb{R} , we can only reorder it within each element of the partition. We now write d p p ​ ( U , V ) \displaystyle d^{p}_{p}(U,V) = inf U , V ‖ U − V ‖ p \displaystyle=\inf_{U,V}\|U-V\|_{p} = inf U , V 𝔼 [ | U − V | p ] \displaystyle\hskip-35.00005pt=\inf_{U,V}\expect\big[|U-V|^{p}\big] = ( a ) inf U , V ∑ i Pr { A i = 1 } 𝔼 [ | U − V | p | A i = 1 ] \displaystyle\hskip-35.00005pt\overset{(a)}{=}\inf_{U,V}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\big[|U-V|^{p}\,|\,A_{i}=1\big] = inf U , V ∑ i Pr { A i = 1 } 𝔼 [ | A i U − A i V | p | A i = 1 ] , \displaystyle\hskip-35.00005pt=\inf_{U,V}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\big[|A_{i}U-A_{i}V|^{p}\,|\,A_{i}=1\big], where (a) follows because A 1 , A 2 , … A_{1},A_{2},\dots is a partition. Using ( 9 ), this implies d p p ​ ( U , V ) \displaystyle d^{p}_{p}(U,V) = inf U , V ∑ i Pr { A i = 1 } 𝔼 [ | A i U − A i V | p | A i = 1 ] \displaystyle\hskip-35.00005pt=\inf_{U,V}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\Big[\big|A_{i}U-A_{i}V\big|^{p}\,|\,A_{i}=1\Big] ≤ inf Y 1 , Y 2 , … Z 1 , Z 2 , … ∑ i Pr { A i = 1 } 𝔼 [ | Y i − Z i | p | A i = 1 ] \displaystyle\hskip-35.00005pt\leq\inf_{\begin{subarray}{c}Y_{1},Y_{2},\dots\\ Z_{1},Z_{2},\dots\end{subarray}}\sum\nolimits_{i}\Pr\{A_{i}=1\}\expect\Big[\big|Y_{i}-Z_{i}\big|^{p}\,|\,A_{i}=1\Big] = ( b ) ∑ i inf Y i , Z i Pr { A i = 1 } 𝔼 [ | Y i − Z i | p | A i = 1 ] \displaystyle\hskip-35.00005pt\overset{(b)}{=}\sum\nolimits_{i}\inf_{Y_{i},Z_{i}}\Pr\{A_{i}=1\}\expect\Big[\big|Y_{i}-Z_{i}\big|^{p}\,|\,A_{i}=1\Big] = ( c ) ​ ∑ i d p ​ ( A i ​ U , A i ​ V ) , \displaystyle\hskip-35.00005pt\overset{(c)}{=}\sum\nolimits_{i}d_{p}(A_{i}U,A_{i}V), because in (b) the individual components of the sum are independently minimized; and (c) from ( 8 ). ∎

###### Lemma 2 .

d ¯ p \bar{d}_{p} is a metric over value distributions.

###### Proof.

The only nontrivial property is the triangle inequality. For any value distribution Y ∈ 𝒵 Y\in\mathcal{Z} , write d ¯ p ​ ( Z 1 , Z 2 ) \displaystyle\bar{d}_{p}(Z_{1},Z_{2}) = sup x , a d p ​ ( Z 1 ​ ( x , a ) , Z 2 ​ ( x , a ) ) \displaystyle=\sup_{x,a}d_{p}(Z_{1}(x,a),Z_{2}(x,a)) ≤ ( a ) ​ sup x , a [ d p ​ ( Z 1 ​ ( x , a ) , Y ⁡ ( x , a ) ) + d p ​ ( Y ⁡ ( x , a ) , Z 2 ​ ( x , a ) ) ] \displaystyle\hskip-42.50006pt\overset{(a)}{\leq}\sup_{x,a}\left[d_{p}(Z_{1}(x,a),Y(x,a))+d_{p}(Y(x,a),Z_{2}(x,a))\right] ≤ sup x , a d p ​ ( Z 1 ​ ( x , a ) , Y ⁡ ( x , a ) ) + sup x , a d p ​ ( Y ⁡ ( x , a ) , Z 2 ​ ( x , a ) ) \displaystyle\hskip-42.50006pt\leq\sup_{x,a}d_{p}(Z_{1}(x,a),Y(x,a))+\sup_{x,a}d_{p}(Y(x,a),Z_{2}(x,a)) = d ¯ p ​ ( Z 1 , Y ) + d ¯ p ​ ( Y , Z 2 ) , \displaystyle\hskip-42.50006pt=\bar{d}_{p}(Z_{1},Y)+\bar{d}_{p}(Y,Z_{2}), where in (a) we used the triangle inequality for d p d_{p} . ∎

###### Lemma 3 .

𝒯 π : 𝒵 → 𝒵 \mathcal{T}^{\pi}:\mathcal{Z}\to\mathcal{Z} is a γ \gamma -contraction in d ¯ p \bar{d}_{p} .

###### Proof.

Consider Z 1 , Z 2 ∈ 𝒵 Z_{1},Z_{2}\in\mathcal{Z} . By definition, d ¯ p ​ ( 𝒯 π ​ Z 1 , 𝒯 π ​ Z 2 ) = sup x , a d p ​ ( 𝒯 π ​ Z 1 ​ ( x , a ) , 𝒯 π ​ Z 2 ​ ( x , a ) ) . \bar{d}_{p}(\mathcal{T}^{\pi}Z_{1},\mathcal{T}^{\pi}Z_{2})=\sup_{x,a}d_{p}(\mathcal{T}^{\pi}Z_{1}(x,a),\mathcal{T}^{\pi}Z_{2}(x,a)). (10) By the properties of d p d_{p} , we have d p ​ ( 𝒯 π ​ Z 1 ​ ( x , a ) , 𝒯 π ​ Z 2 ​ ( x , a ) ) \displaystyle d_{p}(\mathcal{T}^{\pi}Z_{1}(x,a),\mathcal{T}^{\pi}Z_{2}(x,a)) = d p ​ ( R ⁡ ( x , a ) + γ ​ P π ​ Z 1 ​ ( x , a ) , R ⁡ ( x , a ) + γ ​ P π ​ Z 2 ​ ( x , a ) ) \displaystyle\hskip-92.49939pt=d_{p}(R(x,a)+\gamma P^{\pi}Z_{1}(x,a),R(x,a)+\gamma P^{\pi}Z_{2}(x,a)) ≤ γ ​ d p ​ ( P π ​ Z 1 ​ ( x , a ) , P π ​ Z 2 ​ ( x , a ) ) \displaystyle\hskip-92.49939pt\leq\gamma d_{p}(P^{\pi}Z_{1}(x,a),P^{\pi}Z_{2}(x,a)) ≤ γ ​ sup x ′ , a ′ d p ​ ( Z 1 ​ ( x ′ , a ′ ) , Z 2 ​ ( x ′ , a ′ ) ) , \displaystyle\hskip-92.49939pt\leq\gamma\sup_{x^{\prime},a^{\prime}}d_{p}(Z_{1}(x^{\prime},a^{\prime}),Z_{2}(x^{\prime},a^{\prime})), where the last line follows from the definition of P π P^{\pi} (see ( 4 )). Combining with ( 10 ) we obtain d ¯ p ​ ( 𝒯 π ​ Z 1 , 𝒯 π ​ Z 2 ) \displaystyle\hskip-15.00002pt\bar{d}_{p}(\mathcal{T}^{\pi}Z_{1},\mathcal{T}^{\pi}Z_{2}) = sup x , a d p ​ ( 𝒯 π ​ Z 1 ​ ( x , a ) , 𝒯 π ​ Z 2 ​ ( x , a ) ) \displaystyle=\sup_{x,a}d_{p}(\mathcal{T}^{\pi}Z_{1}(x,a),\mathcal{T}^{\pi}Z_{2}(x,a)) ≤ γ ​ sup x ′ , a ′ d p ​ ( Z 1 ​ ( x ′ , a ′ ) , Z 2 ​ ( x ′ , a ′ ) ) \displaystyle\leq\gamma\sup_{x^{\prime},a^{\prime}}d_{p}(Z_{1}(x^{\prime},a^{\prime}),Z_{2}(x^{\prime},a^{\prime}))\hskip-20.00003pt = γ ​ d ¯ p ​ ( Z 1 , Z 2 ) . ∎ \displaystyle=\gamma\bar{d}_{p}(Z_{1},Z_{2}).\qed

###### Proposition 1 (Sobel, 1982) .

Consider two value distributions Z 1 , Z 2 ∈ 𝒵 Z_{1},Z_{2}\in\mathcal{Z} , and write 𝕍 ⁡ ( Z i ) \mathbb{V}(Z_{i}) to be the vector of variances of Z i Z_{i} . Then ‖ 𝔼 𝒯 π Z 1 − 𝔼 𝒯 π Z 2 ‖ ∞ \displaystyle\left\|\expect\mathcal{T}^{\pi}Z_{1}-\expect\mathcal{T}^{\pi}Z_{2}\right\|_{\infty} ≤ γ ​ ‖ 𝔼 Z 1 − 𝔼 Z 2 ‖ ∞ ​ , and \displaystyle\leq\gamma\left\|\expect Z_{1}-\expect Z_{2}\right\|_{\infty}\text{, and} ‖ 𝕍 ⁡ ( 𝒯 π ​ Z 1 ) − 𝕍 ⁡ ( 𝒯 π ​ Z 2 ) ‖ ∞ \displaystyle\left\|\mathbb{V}(\mathcal{T}^{\pi}Z_{1})-\mathbb{V}(\mathcal{T}^{\pi}Z_{2})\right\|_{\infty} ≤ γ 2 ​ ‖ 𝕍 ​ Z 1 − 𝕍 ​ Z 2 ‖ ∞ . \displaystyle\leq\gamma^{2}\left\|\mathbb{V}Z_{1}-\mathbb{V}Z_{2}\right\|_{\infty}.

###### Proof.

The first statement is standard, and its proof follows from 𝔼 𝒯 π Z = 𝒯 π 𝔼 Z \expect\mathcal{T}^{\pi}Z=\mathcal{T}^{\pi}\expect Z , where the second 𝒯 π \mathcal{T}^{\pi} denotes the usual operator over value functions. Now, by independence of R R and P π ​ Z i P^{\pi}Z_{i} : 𝕍 ⁡ ( 𝒯 π ​ Z i ​ ( x , a ) ) \displaystyle\mathbb{V}(\mathcal{T}^{\pi}Z_{i}(x,a)) = 𝕍 ⁡ ( R ⁡ ( x , a ) + γ ​ P π ​ Z i ​ ( x , a ) ) \displaystyle=\mathbb{V}\Big(R(x,a)+\gamma P^{\pi}Z_{i}(x,a)\Big) = 𝕍 ⁡ ( R ⁡ ( x , a ) ) + γ 2 ​ 𝕍 ​ ( P π ​ Z i ​ ( x , a ) ) . \displaystyle=\mathbb{V}(R(x,a))+\gamma^{2}\mathbb{V}(P^{\pi}Z_{i}(x,a)). And now ‖ 𝕍 ⁡ ( 𝒯 π ​ Z 1 ) − 𝕍 ⁡ ( 𝒯 π ​ Z 2 ) ‖ ∞ \displaystyle\left\|\mathbb{V}(\mathcal{T}^{\pi}Z_{1})-\mathbb{V}(\mathcal{T}^{\pi}Z_{2})\right\|_{\infty} = sup x , a | 𝕍 ⁡ ( 𝒯 π ​ Z 1 ​ ( x , a ) ) − 𝕍 ⁡ ( 𝒯 π ​ Z 2 ​ ( x , a ) ) | \displaystyle\hskip-100.00015pt=\sup_{x,a}\big|\mathbb{V}(\mathcal{T}^{\pi}Z_{1}(x,a))-\mathbb{V}(\mathcal{T}^{\pi}Z_{2}(x,a))\big| = sup x , a γ 2 ​ | [ 𝕍 ⁡ ( P π ​ Z 1 ​ ( x , a ) ) − 𝕍 ⁡ ( P π ​ Z 2 ​ ( x , a ) ) ] | \displaystyle\hskip-100.00015pt=\sup_{x,a}\gamma^{2}\big|\left[\mathbb{V}(P^{\pi}Z_{1}(x,a))-\mathbb{V}(P^{\pi}Z_{2}(x,a))\right]\big| = sup x , a γ 2 ​ | 𝔼 [ 𝕍 ⁡ ( Z 1 ​ ( X ′ , A ′ ) ) − 𝕍 ⁡ ( Z 2 ​ ( X ′ , A ′ ) ) ] | \displaystyle\hskip-100.00015pt=\sup_{x,a}\gamma^{2}\big|\expect\left[\mathbb{V}(Z_{1}(X^{\prime},A^{\prime}))-\mathbb{V}(Z_{2}(X^{\prime},A^{\prime}))\right]\big| ≤ sup x ′ , a ′ γ 2 ​ | 𝕍 ⁡ ( Z 1 ​ ( x ′ , a ′ ) ) − 𝕍 ⁡ ( Z 2 ​ ( x ′ , a ′ ) ) | \displaystyle\hskip-100.00015pt\leq\sup_{x^{\prime},a^{\prime}}\gamma^{2}\big|\mathbb{V}(Z_{1}(x^{\prime},a^{\prime}))-\mathbb{V}(Z_{2}(x^{\prime},a^{\prime}))\big| ≤ γ 2 ​ ‖ 𝕍 ​ Z 1 − 𝕍 ​ Z 2 ‖ ∞ . ∎ \displaystyle\hskip-100.00015pt\leq\gamma^{2}\left\|\mathbb{V}Z_{1}-\mathbb{V}Z_{2}\right\|_{\infty}.\qed

###### Lemma 4 .

Let Z 1 , Z 2 ∈ 𝒵 Z_{1},Z_{2}\in\mathcal{Z} . Then ‖ 𝔼 𝒯 Z 1 − 𝔼 𝒯 Z 2 ‖ ∞ ≤ γ ‖ 𝔼 Z 1 − 𝔼 Z 2 ‖ ∞ , \left\|\expect\mathcal{T}Z_{1}-\expect\mathcal{T}Z_{2}\right\|_{\infty}\leq\gamma\left\|\expect Z_{1}-\expect Z_{2}\right\|_{\infty}, and in particular 𝔼 Z k → Q ∗ \expect Z_{k}\to Q^{*} exponentially quickly.

###### Proof.

The proof follows by linearity of expectation. Write 𝒯 D \mathcal{T}_{D} for the distributional operator and 𝒯 E \mathcal{T}_{E} for the usual operator. Then ‖ 𝔼 𝒯 D Z 1 − 𝔼 𝒯 D Z 2 ‖ ∞ \displaystyle\left\|\expect\mathcal{T}_{D}Z_{1}-\expect\mathcal{T}_{D}Z_{2}\right\|_{\infty} = ‖ 𝒯 E 𝔼 Z 1 − 𝒯 E 𝔼 Z 2 ‖ ∞ \displaystyle=\left\|\mathcal{T}_{E}\expect Z_{1}-\mathcal{T}_{E}\expect Z_{2}\right\|_{\infty} ≤ γ ​ ‖ Z 1 − Z 2 ‖ ∞ . ∎ \displaystyle\leq\gamma\left\|Z_{1}-Z_{2}\right\|_{\infty}.\qed

###### Theorem 1 (Convergence in the control setting) .

Let Z k := 𝒯 ​ Z k − 1 Z_{k}:=\mathcal{T}Z_{k-1} with Z 0 ∈ 𝒵 Z_{0}\in\mathcal{Z} . Let 𝒳 \mathcal{X} be measurable and suppose that 𝒜 \mathcal{A} is finite. Then lim k → ∞ inf Z ∗ ⁣ ∗ ∈ 𝒵 ∗ ⁣ ∗ d p ​ ( Z k ​ ( x , a ) , Z ∗ ⁣ ∗ ​ ( x , a ) ) = 0 ∀ x , a . \lim_{k\to\infty}\inf_{Z^{**}\in\mathcal{Z}^{**}}d_{p}(Z_{k}(x,a),Z^{**}(x,a))=0\quad\forall x,a. If 𝒳 \mathcal{X} is finite, then Z k Z_{k} converges to 𝒵 ∗ ⁣ ∗ \mathcal{Z}^{**} uniformly. Furthermore, if there is a total ordering ≺ \prec on Π ∗ \Pi^{*} , such that for any Z ∗ ∈ 𝒵 ∗ Z^{*}\in\mathcal{Z}^{*} , 𝒯 ​ Z ∗ = 𝒯 π ​ Z ∗ ​ with ​ π ∈ 𝒢 Z ∗ , π ≺ π ′ ​ ∀ π ′ ∈ 𝒢 Z ∗ ∖ { π } , \mathcal{T}Z^{*}=\mathcal{T}^{\pi}Z^{*}\;\text{with}\;\pi\in\mathcal{G}_{Z^{*}},\;\pi\prec\pi^{\prime}\;\;\forall\pi^{\prime}\in\mathcal{G}_{Z^{*}}\setminus\{\pi\}, then 𝒯 \mathcal{T} has a unique fixed point Z ∗ ∈ 𝒵 ∗ Z^{*}\in\mathcal{Z}^{*} .

The gist of the proof of Theorem 1 consists in showing that for every state x x , there is a time k k after which the greedy policy w.r.t. Q k Q_{k} is mostly optimal. To clearly expose the steps involved, we will first assume a unique (and therefore deterministic) optimal policy π ∗ \pi^{*} , and later return to the general case; we will denote the optimal action at x x by π ∗ ​ ( x ) \pi^{*}(x) . For notational convenience, we will write Q k := 𝔼 Z k Q_{k}:=\expect Z_{k} and 𝒢 k := 𝒢 Z k \mathcal{G}_{k}:=\mathcal{G}_{Z_{k}} . Let B := 2 ​ sup Z ∈ 𝒵 ‖ Z ‖ ∞ < ∞ B:=2\sup_{Z\in\mathcal{Z}}\left\|Z\right\|_{\infty}<\infty and let ϵ k := γ k ​ B \epsilon_{k}:=\gamma^{k}B . We first define the set of states 𝒳 k ⊆ 𝒳 \mathcal{X}_{k}\subseteq\mathcal{X} whose values must be sufficiently close to Q ∗ Q^{*} at time k k : 𝒳 k := { x : Q ∗ ​ ( x , π ∗ ​ ( x ) ) − max a ≠ π ∗ ​ ( x ) ⁡ Q ∗ ​ ( x , a ) > 2 ​ ϵ k } . \mathcal{X}_{k}:=\Big\{x:Q^{*}(x,\pi^{*}(x))-\max_{a\neq\pi^{*}(x)}Q^{*}(x,a)>2\epsilon_{k}\Big\}. (11) Indeed, by Lemma 4 , we know that after k k iterations | Q k ​ ( x , a ) − Q ∗ ​ ( x , a ) | ≤ γ k ​ | Q 0 ​ ( x , a ) − Q ∗ ​ ( x , a ) | ≤ ϵ k . |Q_{k}(x,a)-Q^{*}(x,a)|\leq\gamma^{k}|Q_{0}(x,a)-Q^{*}(x,a)|\leq\epsilon_{k}. For x ∈ 𝒳 x\in\mathcal{X} , write a ∗ := π ∗ ​ ( x ) a^{*}:=\pi^{*}(x) . For any a ∈ 𝒜 a\in\mathcal{A} , we deduce that Q k ​ ( x , a ∗ ) − Q k ​ ( x , a ) ≥ Q ∗ ​ ( x , a ∗ ) − Q ∗ ​ ( x , a ) − 2 ​ ϵ k . Q_{k}(x,a^{*})-Q_{k}(x,a)\geq Q^{*}(x,a^{*})-Q^{*}(x,a)-2\epsilon_{k}. It follows that if x ∈ 𝒳 k x\in\mathcal{X}_{k} , then also Q k ​ ( x , a ∗ ) > Q k ​ ( x , a ′ ) Q_{k}(x,a^{*})>Q_{k}(x,a^{\prime}) for all a ′ ≠ π ∗ ​ ( x ) a^{\prime}\neq\pi^{*}(x) : for these states, the greedy policy π k ​ ( x ) := arg ​ max a ⁡ Q k ​ ( x , a ) \pi_{k}(x):=\argmax_{a}Q_{k}(x,a) corresponds to the optimal policy π ∗ \pi^{*} .

###### Lemma 5 .

For each x ∈ 𝒳 x\in\mathcal{X} there exists a k k such that, for all k ′ ≥ k k^{\prime}\geq k , x ∈ 𝒳 k ′ x\in\mathcal{X}_{k^{\prime}} , and in particular arg ​ max a ⁡ Q k ​ ( x , a ) = π ∗ ​ ( x ) \argmax_{a}Q_{k}(x,a)=\pi^{*}(x) .

###### Proof.