3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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! $\endgroup$
    – Tamar
    Commented Mar 26, 2021 at 12:25
  • $\begingroup$ @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?". $\endgroup$
    – nbro
    Commented Mar 26, 2021 at 13:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – David
    Commented Mar 26, 2021 at 13:26
  • 1
    $\begingroup$ @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 $\endgroup$
    – mikkola
    Commented Mar 27, 2021 at 10:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .