Uniqueness of the optimal value function for an MDP Suppose we have a Markov decision process with a finite state set and a finite action set. We calculate the expected reward with a discount of $\gamma \in [0,1]$. 
In chapter 3.8 of the book "Reinforcement Learning: An Introduction" (by Andrew Barto and Richard S. Sutton) it is stated that there always exists at least one optimal policy, but it doesn't prove why. 
I suppose the various optimal policies yield the same optimal value function, at least this is what would make sense and also assumed in the book.
Can someone give me a proof for the above statement or a link to a proof?
 A: Assume that there exists two optimal policies $\pi$ and $\pi'$ with respective value functions $V$ and $V'$. Assume that, for some state $x$, $V(x) \neq V'(x)$. Without loss of generality, we can assume that $V(x) < V'(x)$. But if $V(x)$ is lower than $V'(x)$, then it is not optimal since it is better to follow $\pi'$. Therefore, it is proved by contradiction, $V(x)$ and $V'(x)$ must be the same.
A: Maybe I am oversimplifying things, but to me the proof looks straight forward.
The function $f$ mapping a policy $\pi$ to its value function $V^\pi$ is surjective. It is therefore enough to show that the optimal value function $V^*$ exists. The optimal policy then exists, too, because $f^{-1}\{V^*\}\neq\emptyset$.
The value function has the form $V:S\rightarrow\mathbb{R}$ where $S$ is the finite set of states. A finite, discrete set is compact. Further, we can define the isolated points metric on $S$, i.e.
\begin{equation}
d_S(x,y):=\begin{cases}
1 &, y\neq x \\
0 &, y=x
\end{cases}
\end{equation}
If $S$ is a metric space, we can show that $V$ is continuous [1]. The idea here is that if the sequence $s_n$ in $S$ converges to $s\in S$ we can choose $\epsilon \in (0,1)$ and get $s_n=s~~\forall~n>N_\epsilon$ (which does exist).
A continuous function $V$ on a compact metric space $S$ attains its maximum at some point in $S$ [1]. Hence $V^*$ exists. $\Box$
[1] https://www.rose-hulman.edu/~bryan/lottamath/compact.pdf

Arguably this gets more interesting if $S$ is no longer finite. There we have no guarantee that $V$ will be continuous. I assume you can still show the existence of $pi^*$ if the reward is bounded, but I've never written it down or thought it through thoroughly.
