I'm following [Sutton's](http://ufal.mff.cuni.cz/~straka/courses/npfl114/2016/sutton-bookdraft2016sep.pdf) book on Reinforcement Learning, and he casually states that "There is always at least one policy that is better than
or equal to all other policies" for a given finite MDP. This is trivially the case for deterministic policies, since there is a finite number of policies. Is there any proof when one allows for stochastic policies? Or any proof that a stochastic policy can always be improved by a deterministic one?


The value function is bounded and real-valued and therefore there is a least upper bound, but how can we know it is achieved by a valid policy?



Proof of the existence of an optimal MDP with a stochastic reward signal?
Old question, but I will try to answer anyway: It depends. 


If the search space only allows policies that have at least one state for which a non-deterministic action selection takes place, then no; trivially there is no (fully) deterministic policy that is better then the optimal stochastic policy.


If you allow all stochastic policies in the sense that $\pi(a|s)\neq 0$ for any number ($\geq 1$) of $a$ available in $s$ and further $\forall a,s~:\pi(a|s)\in [0,1] $ (there is no restriction on the probability value for a state-action pair) then yes, deterministic policies are at least equally good.


**Proof:**


Let $\pi^\*$ be an optimal, non-deterministic policy. This means that $\exists \hat{s}~ \exists a : \pi^\*(a|\hat{s}) \in (0,1)$, where $\pi^\*(\cdot|s)$ is the probability distribution function for the optimal policy $\pi^\*$ in state $s$.


We can find a value function $V^\*$ as well as a Q-function $Q^\*$ that correspond to $\pi^\*$ and a relationship between them
\begin{equation}
V^\*(s) = \sum\_{i=0}^N\pi^\*(a\_i|s)Q^\*(s,a\_i)
\end{equation}


W.l.o.g. $Q^\*(s,a\_1)\geq Q^\*(s,a\_2)\geq\dots\geq Q^\*(s,a\_N)$. Choosing $\alpha\_i \in [0,1]$, we can now construct a family of policies $\pi^{\alpha\_2,\dots,\alpha\_N}$ such that:
\begin{equation}
\pi^{\alpha\_2,\dots,\alpha\_N}(a|s) = 
\begin{cases}
\pi^\*(a|s) +\sum\_{i=2}^N \alpha\_i&,~\textrm{if}~a=a\_1~\textrm{and}~ s = \hat{s}\\
\pi^\*(a|s) - \alpha\_i&,~\textrm{if}~a=a\_i~\textrm{and}~ s = \hat{s}~\textrm{for}~i\geq 2\\
\pi^\*(a|s)&,~\textrm{otherwise}
\end{cases}.
\end{equation}


Choose $\alpha\_N = \pi^\*(a\_N|\hat{s})~,~\alpha\_i = 0$ otherwise; we can compare


\begin{align}
V^\*(s) &= \sum\_{i=0}^{N-1}\pi^\*(a\_i|s)Q^\*(s,a\_i) + \pi^\*(a\_N|s)Q^\*(s,a\_N)\\
&\leq \sum\_{i=0}^{N-1}\pi^\*(a\_i|s)Q^\*(s,a\_i) + \pi^\*(a\_N|s)Q^\*(s,a\_1) \\
&= \sum\_{i=0}^{N-1}\pi^\*(a\_i|s)Q^\*(s,a\_i) + \alpha\_N Q^\*(s,a\_1) \\
&= V^{0,\dots,0,\pi^\*(a\_N|s)}(s)
\end{align}
(Note: for [my] convenience I've written s instead of $\hat{s}$ here.)


Analogous for $\alpha\_i=\pi^\*(a\_i|s)$ and we arrive at
\begin{equation}
V^\*(s) \leq V^{\pi^\*(a\_2|\hat{s}),\dots,\pi^\*(a\_n|\hat{s})}~\forall s
\end{equation}
meaning that the policy $\pi^{\pi^\*(a\_2|\hat{s}),\dots,\pi^\*(a\_n|\hat{s})}$ which is deterministic in $\hat{s}$ is at least as good as $\pi^\*$.


Doing this for each stochastic state in $\pi^\*$ constructs a new policy which is at least as good as the previous optimal policy, but deterministic.




---


A shorter, but I think less insightful, proof following the same line of thought (sketch):


W.l.o.g. $Q^\*(s,a\_1)\geq Q^\*(s,a\_2)\geq\dots\geq Q^\*(s,a\_N)$.


\begin{equation}
V^\*(s) = \sum\_{i=0}^N\pi^\*(a\_i|s)Q^\*(s,a\_i) \leq \underbrace{\sum\_{i=0}^N\pi^\*(a\_i|s)}\_{=1}Q^\*(s,a\_1) = Q^\*(s,a\_1)
\end{equation}


Choosing
\begin{equation}
\pi(a|s) = 
\begin{cases}
1&,~\textrm{if}~a = a\_1\\
0&,~\textrm{otherwise}
\end{cases}
\end{equation}
follows that $V^\*(s)\leq V^\pi(s)~\forall s$. $\pi$ is deterministic by construction.


