Answers.Body: <p>The value function is defined as <span class="math-container">$v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$</span> where <span class="math-container">$G_t$</span> are the (discounted) returns from time step <span class="math-container">$t$</span>. The expectation is taken with respect to the policy <span class="math-container">$\pi$</span> and the transition dynamics of the MDP.</p>
  <p>Now, as you pointed out the optimal value function is defined as <span class="math-container">$v_*(s) = \max_\pi v_\pi(s)\; ; \;\forall s \in \mathcal{S}$</span>. All we are doing here is choosing a policy <span class="math-container">$\pi$</span> 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T12:25:06.903Z
Answers.Text: 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!
Answers.UserDisplayName: Tamar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T13:10:38.890Z
Answers.Text: @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?".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T13:26:01.460Z
Answers.Text: @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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-27T10:04:03.190Z
Answers.Text: @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: https://mathoverflow.net/a/44685/80487
Answers.UserDisplayName: mikkola
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T11:34:55.553Z
Answers.LastActivityDate: 2021-03-26T11:34:55.553Z
Answers.UserDisplayName: David
Body: <p>I am reading Sutton &amp; Bartos's Book &quot;Introduction to reinforcement learning&quot;. In this book, the defined the optimal value function as:</p>
  <p><span class="math-container">$$v_*(s) = \max_{\pi} v_\pi(s),$$</span> for all <span class="math-container">$s \in \mathcal{S}$</span>.</p>
  <p>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?)</p>
  <p>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).</p>
  <p>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?</p>
  
Tags: <markov-decision-process><value-functions><stochastic-policy><optimal-policy><optimality>
Title: How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?
UserDisplayName: Tamar
ThreadText: # How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?
  
  (Asked by: username_0 on 2021-03-26)
  
  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?
  
  **Tags:** markov-decision-process, value-functions, stochastic-policy, optimal-policy, optimality
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-26. Score: 2 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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!  
  > **username_2**: @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?".  
  > **username_1**: @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.  
  > **username_3**: @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: https://mathoverflow.net/a/44685/80487  
  
  ---
  
  