# How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?

I am reading Sutton & Bartos's Book "Introduction to reinforcement learning". In this book, the defined the optimal value function as:

$$v_*(s) = \max_{\pi} v_\pi(s),$$ for all $$s \in \mathcal{S}$$.

Do we take the max over all deterministic policies, or do we also look at stochastic policies (is there an example where a stochastic policy always performs better than a deterministic one?)

My intuition is that the value function of a stochastic policy is more or less a linear combination of the deterministic policies it tries to model, however, there are some self-references, so it is not mathematically true).

If we do look over all stochastic policies, shouldn't we take the supremum? Or do we know, that the supremum is achieved, and therefore it is truly a maximum?

The value function is defined as $$v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$$ where $$G_t$$ are the (discounted) returns from time step $$t$$. The expectation is taken with respect to the policy $$\pi$$ and the transition dynamics of the MDP.

Now, as you pointed out the optimal value function is defined as $$v_*(s) = \max_\pi v_\pi(s)\; ; \;\forall s \in \mathcal{S}$$. All we are doing here is choosing a policy $$\pi$$ that maximises the value function; this can be a deterministic or a stochastic policy, though intuitively it is likely to be deterministic unless for some states that are two (or more) actions with the same expected value, in which case you can take any of said actions with equal probability, thus making the policy stochastic.

For a finite MDP (which is what I assumed above too), we know that an optimal value function exists (this is mentioned in the book) so taking the maximum is fine here.

• But do we know that there always exists a deterministic optimal policy? I think I read somewhere that sometimes only stochastic policies are optimal (for example in a game with an opponent, like Scissors-Stone-Paper, where a deterministic policy would always lead to a loss, when the other opponent can also learn). But thanks for your answer! Mar 26 '21 at 12:25
• @MaximusMJ In Scissors-Stone-Paper, the optimal policy is definitely not deterministic. You can easily beat any deterministic policy in this case (in the long run), i.e. once you know the opponent chooses e.g. stone, you can choose paper, and so on. So, yes, there are cases where the optimal policy is not deterministic. This should answer your question in parentheses "is there an example where a stochastic policy always performs better than a deterministic one?".
– nbro
Mar 26 '21 at 13:10
• @MaximusMJ We know that there always exists an optimal policy (for a finite MDP), whether it is deterministic or not does not matter in the context of taking the $\max$ (I don't think), as we know the $\max$ exists then it is fine. Mar 26 '21 at 13:26
• @nbro I don't think it is helpful to bring game theory into a discussion on single-agent finite MDPs, although in games the value of a stochastic policies can exceed the value of any deterministic policy. This is not the case in MDP however; if there is an optimal policy in MDP, there is a deterministic optimal policy, additional discussion: mathoverflow.net/a/44685/80487 Mar 27 '21 at 10:04