5
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I don't think that the proof is very straightforward (based on a quick google scholar search). To get a flavor for the proof I would recommend skimming through the paper by Leizarowitz, Arie, and Alexander J. Zaslavski. "Uniqueness and stability of optimal policies of finite state Markov decision processes." Mathematics of Operations Research 32.1 (2007): 156-167. $\endgroup$
    – combo
    Jan 30, 2017 at 20:51

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.