Proof of the existence of an optimal MDP with a stochastic reward signal? I'm following Sutton's 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?
 A: 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.
A: Yes, this is true. Let $Q^*$ be the optimal Q-function. (Note that $Q^*(s,a)$ can be defined without explicit reference to an optimal policy as the supremum of the expected utility-to-go starting from state $s$, the supremum being taken over all policies starting with action $a$.) Then a stochastic policy $\pi$ is optimal iff $\pi(s)$ maximizes $Q^*(s,\cdot)$ almost surely for each state $s$. So clearly a deterministic policy always exists.
A: I think that both answers are kinda flawed and I even think that the remark in the question itself

This is trivially the case for deterministic policies, since there is a finite number of policies

is not trivially true (maybe I'm too dumb to see it but I think that there is an important piece missing, see below).
Given a Markov Decision Process consisting of random variables $(S_t, R_t, A_t)_{t \in \mathbb{N}_0}$, put 
$$ G_t := \sum_{k \in \mathbb{N}_0} \gamma^k R_{t+k}$$
for any state $s$ let $v^\pi(s) = E^\pi[G_t|S_t=s]$ for any $t$ arbitrary. It is already not clear that this variable $G_t$ converges in any sense but if we assume that there are only finitely many $L^1$ rewards involved or all rewards are bounded then this converges and $E^\pi[G_t|S_t=s]$ is independent of the point in time $t$ (given that all policies we consider are stationary).
What "you people" always claim is the following: consider a fixed policy $\pi$ and a fixed state $s$. Assuming that I change that policy to $\pi'$ but only on all other states $s' \neq s$ is it true that $v^\pi(s) = v^{\pi'}(s)$? I do not think so (at least I cannot easily find a proof for that). Changing the behaviour only on one single state $s$ can change all values of $v^\pi$! The property you are looking for is not true for 'the function $\pi \mapsto v^\pi$' but rather for the following construction:
We know that under suitable conditions, the so-called Bellman equation holds: 
$$v^\pi(s) = E^\pi[R_t|S_t=s] + \gamma \int_{s'} p(s'|s) v^\pi(s') ds'$$
see https://stats.stackexchange.com/questions/243384/deriving-bellmans-equation-in-reinforcement-learning for a proof.
Consider the space $V$ of all bounded functions from $S$ to $\mathbb{R}$. On this space we can define the operator
  $$v \mapsto ((L_\pi v)(s))_{s \in S}$$
where
  $$(L_\pi v)(s) = E[R_t|S_t=s] + \gamma \int_{s'} p(s'|s) v(s') ds'$$
(actually, the first term $E[R_t|S_t=s]$ does not depend on $\pi$ but the latter one $p(s'|s)$ does!) The Bellman equation is the motivation for that operator: $v^\pi$ is its unique fixed point.
Now given any $v \in V$ fixed and a policy $\pi$ and I change $\pi$ to $\pi'$ on all states $s' \neq s$ then
  $$(L_\pi v)(s) = (L_{\pi'} v)(s) ~~~~ (*)$$
i.e. the property you were looking for only holds for '$\pi \mapsto (L_\pi v)$' for a fixed $v$ but not for '$\pi \mapsto v^\pi$'!
The only proof I was really able to understand can be found in Puterman, Markov Decision Processes. He essentially proves in Chapter 6 that optimizing $L_\pi$ on $v^*$ is sufficient for obtaining on optimal policy.
Side note: one can understand it up to the facts that $E[G_t|S_t=\cdot]$ is actually not a function but a $P_{S_t}$-almost everywhere class of functions and up to the fact that $E[G_t|S_t=s]$ cannot be defined if $P[S_t=s]=0$, i.e. the vectors $v^\pi$ are 'incomplete'. The first thing can be fixed by restricting to the case where $S$ is discrete (then it actually becomes a function) and the second one can be fixed by not considering the single MDP as it but the MArkov Decision Automata that gives rise (in the sense of Markov processes: Construction of the state variables) to the MDP, i.e. we do not say 'given an MDP, $\pi(a|s) = p(a_t|s_t)$ is its policy' but we start by saying 'given a function $\pi : A \times S \to [0,1]$ such that for each $s$, $\int_a \pi(a|s) = 1$ we define canonical expressions for $v^\pi(s)$ even if, for example, $P[S_0=s]=0$' and we can do this because we actually know the value for $\pi(a|s_0)$ even if $P[S_0=s_0]=0$! Just wanted to note that because it was something that confused me for quite some time...
