Answers.Body: <p>An optimal policy is just a greedy policy with respect to the optimal state-action value function (which is unique for a given MDP). So, <span class="math-container">$\pi_* = \text{argmax}_a q_*(s,a) $</span> is almost correct - it should have been</p>
  <p><span class="math-container">$$\pi_*(s) = \text{argmax}_a q_*(s,a), \forall s.$$</span></p>
  <p>In this case, <span class="math-container">$\pi_*$</span> is a <a href="https://en.wikipedia.org/wiki/Decision_rule" rel="nofollow noreferrer">decision rule</a> or a function.</p>
  <p>If you define <span class="math-container">$\pi^*$</span> as a <a href="https://ai.stackexchange.com/q/12274/2444">probability distribution</a>, then you can do something like this</p>
  <p><span class="math-container">$$
  \pi_*(s, a)=
  \begin{cases}
  1, \text{if } a = \text{argmax}_a q_*(s,a)\\
  0, \text{otherwise}\end{cases},
  $$</span>
  <span class="math-container">$\forall s \in \mathcal{S}$</span>.</p>
  <p>If <span class="math-container">$\text{argmax}_a q_*(s,a)$</span> is a set, you can choose any of the actions in that set with any rule you want, and, of course, still ignore non-optimal actions.</p>
  <p>This is true for finite MDPs (aka MDPs with finite state, action and reward spaces).</p>
  <p>There's a result (Putterman, 1994) that states that there's a deterministic and Markovian optimal policy for an MDP. So, optimal policies aren't (necessarily) probability distributions. It's a matter of convention and convenience.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T18:28:13.743Z
Answers.Text: I am not sure the action and reward spaces need to be finite. Maybe you just need the rewards to be bounded and I am not sure about the action space. There are assumptions in that book, which I may check later. The specific theorem may be 6.2.7, and applies to infinite-horizon discounted MDPs with finite $\mathcal{S}$ (at least). One also requires stationary reward and transition functions.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T18:15:12.637Z
Answers.LastActivityDate: 2022-07-05T18:15:12.637Z
Answers.UserDisplayName: nbro
Body: <p>I am trying to solve the following exercise from Sutton and Barto:</p>
  <blockquote>
  <p>Sutton and Barto Exercise 3.27 Give an equation for <span class="math-container">$\pi_*$</span> in terms of <span class="math-container">$q_*(s,a)$</span></p>
  </blockquote>
  <p>However, I am struggling to do so. I know that <span class="math-container">$\pi_*$</span> is the policy which will pick the action with highest return, given we know what the optimal action values are. So intuitively, I would express the optimal policy like this: <span class="math-container">$$\pi_*(\text{argmax}_a q_*(s,a)|s) = 1$$</span>. To express it like this: <span class="math-container">$$\pi_* = \text{argmax}_a q_*(s,a) $$</span></p>
  <p>seems wrong since <span class="math-container">$\pi_*$</span> is a probability. What am I not getting correct here?</p>
  
Tags: <reinforcement-learning><sutton-barto><policies><notation><optimality>
Title: What is the equation for $\pi_*$ in terms of $q_*(s,a)$?
UserDisplayName: user
ThreadText: # What is the equation for $\pi_*$ in terms of $q_*(s,a)$?
  
  (Asked by: username_0 on 2022-07-05)
  
  I am trying to solve the following exercise from Sutton and Barto:
  
  > Sutton and Barto Exercise 3.27 Give an equation for $\pi\_\*$ in terms of $q\_\*(s,a)$
  
  However, I am struggling to do so. I know that $\pi\_\*$ is the policy which will pick the action with highest return, given we know what the optimal action values are. So intuitively, I would express the optimal policy like this: $$\pi\_\*(\text{argmax}\_a q\_\*(s,a)|s) = 1$$. To express it like this: $$\pi\_\* = \text{argmax}\_a q\_\*(s,a) $$
  
  seems wrong since $\pi\_\*$ is a probability. What am I not getting correct here?
  
  **Tags:** reinforcement-learning, sutton-barto, policies, notation, optimality
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-07-05. Score: 2 | Accepted answer
  
  An optimal policy is just a greedy policy with respect to the optimal state-action value function (which is unique for a given MDP). So, $\pi\_\* = \text{argmax}\_a q\_\*(s,a) $ is almost correct - it should have been
  
  $$\pi\_\*(s) = \text{argmax}\_a q\_\*(s,a), \forall s.$$
  
  In this case, $\pi\_\*$ is a [decision rule](https://en.wikipedia.org/wiki/Decision_rule) or a function.
  
  If you define $\pi^\*$ as a [probability distribution](https://ai.stackexchange.com/q/12274/2444), then you can do something like this
  
  $$
  \pi\_\*(s, a)=
  \begin{cases}
  1, \text{if } a = \text{argmax}\_a q\_\*(s,a)\\
  0, \text{otherwise}\end{cases},
  $$
  $\forall s \in \mathcal{S}$.
  
  If $\text{argmax}\_a q\_\*(s,a)$ is a set, you can choose any of the actions in that set with any rule you want, and, of course, still ignore non-optimal actions.
  
  This is true for finite MDPs (aka MDPs with finite state, action and reward spaces).
  
  There's a result (Putterman, 1994) that states that there's a deterministic and Markovian optimal policy for an MDP. So, optimal policies aren't (necessarily) probability distributions. It's a matter of convention and convenience.
  
  > **Comments:**
  > **username_1**: I am not sure the action and reward spaces need to be finite. Maybe you just need the rewards to be bounded and I am not sure about the action space. There are assumptions in that book, which I may check later. The specific theorem may be 6.2.7, and applies to infinite-horizon discounted MDPs with finite $\mathcal{S}$ (at least). One also requires stationary reward and transition functions.  
  
  ---
  
  