Answers.Body: <p><strong>Deterministic case</strong>: the greedy action <span class="math-container">$a_g$</span> (discrete) yield by the greedy policy <span class="math-container">$\pi_g$</span> is:
  <span class="math-container">$$\pi_g(s) = a_g = \arg\max_{a\in\mathcal A} q^\pi(s,a)$$</span>
  For continuous actions, the <span class="math-container">$\arg\max_a$</span> is infeasible to compute. One can thus learn a deterministic policy <span class="math-container">$\pi_d$</span>, according to the <a href="http://proceedings.mlr.press/v32/silver14.pdf" rel="nofollow noreferrer">deterministic policy gradient theorem</a>, such that <span class="math-container">$a_d=\pi_d(s)$</span> achieves the maximum action-value, i.e. <span class="math-container">$q^\pi(s,a_d)\ge q^\pi(s,a),\ \forall a\in\mathcal A$</span>.</p>
  <p>Now, for both discrete (<span class="math-container">$a_g$</span>) and continuous (<span class="math-container">$a_d$</span>) actions these are greedy, in the sense that their respective policies should assign a probability of one to those (if viewed as if being stochastic), and zero to all sub-optimal actions:
  <span class="math-container">$$
  \pi_g(a\mid s) = \begin{cases}1 &amp; \text{if $a=a_g$} \\ 0 &amp; \text{otherwise}  \end{cases},
  $$</span>
  similarly for <span class="math-container">$\pi_d$</span> and <span class="math-container">$a_d$</span>. <em>This means that <span class="math-container">$\pi_g$</span> (viewed as stochastic) samples the greedy action all the times, so it always exploits.</em></p>
  <p><strong>Stochastic case</strong>: to simplify let's assume the policy is <a href="https://en.wikipedia.org/wiki/Normal_distribution" rel="nofollow noreferrer">Gaussian</a>, i.e. <span class="math-container">$\pi(a\mid s) = \mathcal{N}(\mu,\sigma^2\mid s)$</span>. I assume <span class="math-container">$\mu$</span> and <span class="math-container">$\sigma$</span> to be meaningful, like being learned to maximize the action-value function, <span class="math-container">$q^\pi$</span>. If so, in my opinion, the <em>most likely action</em> (i.e. the distribution's mode) should have the largest action-value. In the case of Gaussian distributions, the mean <span class="math-container">$\mu$</span> is the most likely action (being also its mode) and so it should be the greedy action, i.e. <span class="math-container">$a_g=\mu$</span> such that <span class="math-container">$q^\pi(s,\mu)\ge q^\pi(s,a),\forall a \in\mathcal A$</span>.</p>
  <p>Therefore <span class="math-container">$\pi$</span> assigns the following probabilities:
  <span class="math-container">$$
  \pi(a\mid s) = \begin{cases}\alpha e^{-\frac12} &amp; \text{if $a=\mu$} \\ 
                              \alpha e^{-\frac12\big(\frac{a-\mu}{\sigma}\big)^2} &amp; \text{otherwise}  \end{cases},
  $$</span>
  where <span class="math-container">$\alpha = (\sigma\sqrt{2\pi})^{-1}$</span>. Now, from this we can see that the considered stochastic policy is greedy <span class="math-container">$\alpha e^{-\frac12}$</span> of the times (since is the probability of sampling the mean <span class="math-container">$\mu$</span> as action.) Since <a href="https://www.davidsilver.uk/wp-content/uploads/2020/03/MDP.pdf" rel="nofollow noreferrer">there always exist a deterministic policy</a> (see slide 41) we can, in principle, turn the stochastic <span class="math-container">$\pi$</span> into a deterministic policy <span class="math-container">$\pi_d$</span> such that:
  <span class="math-container">$$
  \pi_d(a\mid s) = \begin{cases}1 &amp; \text{if $a=\mu$} \\ 0 &amp; \text{otherwise}  \end{cases},
  $$</span>
  in order to be greedy all the times: with probability one, <span class="math-container">$\mu=\pi_d(s)$</span> always outputs the mean <span class="math-container">$\mu$</span> (action that maximizes <span class="math-container">$q^\pi$</span>) in state <span class="math-container">$s$</span> - indeed, the value of <span class="math-container">$\mu$</span> is state-dependent, meaning that a different state could have a different mean.</p>
  <p>(Disclaimer: I don't know if the above is mathematically sound and correct but that's my intuition. So, please correct me eventually.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-11T11:26:55.270Z
Answers.Text: In the Gaussian example, those are probability denisties, not probabilities. I'm not sure this is answering what the OP asked though, see my comments on the question
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-11T09:26:11.697Z
Answers.LastActivityDate: 2023-06-11T09:26:11.697Z
Answers.UserDisplayName: Luca Anzalone
Answers.Body: <p>The stochastic policy trained in the standard policy gradient method are inherently incompatible with any 'greedy' exploitative action during policy improvement which is a deterministic concept. Policy improvement in policy gradient method simply means its parameters update rule follows the gradient ascent of its specified performance metric <span class="math-container">$J(\theta)$</span>.</p>
  <p>Having said that, the closest counterpart of a greedy action perhaps is the <em>actor</em> component in the bootstapping actor-critic methods as detailed in Sutton &amp; Barto's Reinforcement Learning book section 13.5.</p>
  <blockquote>
  <p>As we have seen in the TD learning of value functions throughout this book, the one-step return is often superior to the actual return in terms of its variance and computational congeniality, even though it introduces bias... When the state-value function is used to assess actions in this way it is called a critic, and the overall policy-gradient method is termed an actor–critic method.</p>
  </blockquote>
  <p>Also take a look at its detailed algo without eligibility traces on page 332, and you can treat its actor's parameters <span class="math-container">$\theta$</span> update as some form of 'greedy' action based on the learned critic's feedback <span class="math-container">$\delta$</span> if you will, but it's not the same sense as taking the action with maximum action value in all action based RL methods.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-14T15:45:03.567Z
Answers.Text: See my comment on the question. This answer assumes the OP does not want to calculate the greedy action, and is searching for something else. However, the question is asking for the definition of the greedy action given the action value function, which is straightforward. Also, if you are using $\epsilon$-greedy behaviour policy, then the greedy action choice *is* also used in the policy improvement step. The OP has not returned to the question to clarify, although they are still active on the site.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-14T08:05:45.783Z
Answers.LastActivityDate: 2023-11-14T08:05:45.783Z
Answers.UserDisplayName: cinch
Body: <p>If we have a deterministic policy <span class="math-container">$\pi$</span> with action-value function <span class="math-container">$q(s,a)$</span>, then a greedy action for policy improvement is defined as</p>
  <p><span class="math-container">$\pi^\prime(s)=\arg\max_{a}q^{\pi}(s,a)$</span>.</p>
  <p>How do we define a greedy action for policy improvement for a given stochastic policy <span class="math-container">$\pi(a|s)$</span>
  with action-value function <span class="math-container">$q^{\pi}(s,a)$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-10T15:38:28.890Z
Comments.Text: Probably related: https://ai.stackexchange.com/questions/40149/mean-or-mode-of-action-distribution-when-evaluating-policy-gradient-agents. In my opinion, the action that can be considered "greedy" for a stochastic policy, should be one of the distribution mode(s).
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-10T19:05:41.567Z
Comments.Text: Could you please write your guess mathematically?
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-11T09:26:59.867Z
Comments.Text: Sure, have a look at my answer
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-11T10:45:11.483Z
Comments.Text: I think the question is missing some context. The greedy action is by definition the action that the agent predicts will result in the highest return. That's it, there's no edge cases or special rules beyond that in different circumstances. I'd like to know what you are trying to do with this information. For instance, it would not be appropriate to use the greedy action to train a policy gradient method - you should use the action taken by the policy even if it was "wrong".
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-11T11:23:25.280Z
Comments.Text: Other than that, if you are talking about policy improvement in Q-learning, or SARSA or other action-value based method, then the definition for greedy action/greedy policy does not change. If you are interested there is an extension to the policy improvment theorem that the resulting $\epsilon$-greedy policy (in e.g. SARSA) is a strict improvement over the previous one.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><dynamic-programming>
Title: How do we define greedy action for policy improvement for a given stochastic policy?
UserDisplayName: DSPinfinity
ThreadText: # How do we define greedy action for policy improvement for a given stochastic policy?
  
  (Asked by: username_0 on 2023-06-10)
  
  If we have a deterministic policy $\pi$ with action-value function $q(s,a)$, then a greedy action for policy improvement is defined as
  
  $\pi^\prime(s)=\arg\max\_{a}q^{\pi}(s,a)$.
  
  How do we define a greedy action for policy improvement for a given stochastic policy $\pi(a|s)$
  with action-value function $q^{\pi}(s,a)$.
  
  **Tags:** reinforcement-learning, dynamic-programming
  
  > **Comments:**
  > **username_1**: Probably related: https://ai.stackexchange.com/questions/40149/mean-or-mode-of-action-distribution-when-evaluating-policy-gradient-agents. In my opinion, the action that can be considered "greedy" for a stochastic policy, should be one of the distribution mode(s).  
  > **username_0**: Could you please write your guess mathematically?  
  > **username_1**: Sure, have a look at my answer  
  > **username_2**: I think the question is missing some context. The greedy action is by definition the action that the agent predicts will result in the highest return. That's it, there's no edge cases or special rules beyond that in different circumstances. I'd like to know what you are trying to do with this information. For instance, it would not be appropriate to use the greedy action to train a policy gradient method - you should use the action taken by the policy even if it was "wrong".  
  > **username_2**: Other than that, if you are talking about policy improvement in Q-learning, or SARSA or other action-value based method, then the definition for greedy action/greedy policy does not change. If you are interested there is an extension to the policy improvment theorem that the resulting $\epsilon$-greedy policy (in e.g. SARSA) is a strict improvement over the previous one.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-06-11. Score: 1
  
  **Deterministic case**: the greedy action $a\_g$ (discrete) yield by the greedy policy $\pi\_g$ is:
  $$\pi\_g(s) = a\_g = \arg\max\_{a\in\mathcal A} q^\pi(s,a)$$
  For continuous actions, the $\arg\max\_a$ is infeasible to compute. One can thus learn a deterministic policy $\pi\_d$, according to the [deterministic policy gradient theorem](http://proceedings.mlr.press/v32/silver14.pdf), such that $a\_d=\pi\_d(s)$ achieves the maximum action-value, i.e. $q^\pi(s,a\_d)\ge q^\pi(s,a),\ \forall a\in\mathcal A$.
  
  Now, for both discrete ($a\_g$) and continuous ($a\_d$) actions these are greedy, in the sense that their respective policies should assign a probability of one to those (if viewed as if being stochastic), and zero to all sub-optimal actions:
  $$
  \pi\_g(a\mid s) = \begin{cases}1 & \text{if $a=a\_g$} \\ 0 & \text{otherwise} \end{cases},
  $$
  similarly for $\pi\_d$ and $a\_d$. *This means that $\pi\_g$ (viewed as stochastic) samples the greedy action all the times, so it always exploits.*
  
  **Stochastic case**: to simplify let's assume the policy is [Gaussian](https://en.wikipedia.org/wiki/Normal_distribution), i.e. $\pi(a\mid s) = \mathcal{N}(\mu,\sigma^2\mid s)$. I assume $\mu$ and $\sigma$ to be meaningful, like being learned to maximize the action-value function, $q^\pi$. If so, in my opinion, the *most likely action* (i.e. the distribution's mode) should have the largest action-value. In the case of Gaussian distributions, the mean $\mu$ is the most likely action (being also its mode) and so it should be the greedy action, i.e. $a\_g=\mu$ such that $q^\pi(s,\mu)\ge q^\pi(s,a),\forall a \in\mathcal A$.
  
  Therefore $\pi$ assigns the following probabilities:
  $$
  \pi(a\mid s) = \begin{cases}\alpha e^{-\frac12} & \text{if $a=\mu$} \\
  \alpha e^{-\frac12\big(\frac{a-\mu}{\sigma}\big)^2} & \text{otherwise} \end{cases},
  $$
  where $\alpha = (\sigma\sqrt{2\pi})^{-1}$. Now, from this we can see that the considered stochastic policy is greedy $\alpha e^{-\frac12}$ of the times (since is the probability of sampling the mean $\mu$ as action.) Since [there always exist a deterministic policy](https://www.davidsilver.uk/wp-content/uploads/2020/03/MDP.pdf) (see slide 41) we can, in principle, turn the stochastic $\pi$ into a deterministic policy $\pi\_d$ such that:
  $$
  \pi\_d(a\mid s) = \begin{cases}1 & \text{if $a=\mu$} \\ 0 & \text{otherwise} \end{cases},
  $$
  in order to be greedy all the times: with probability one, $\mu=\pi\_d(s)$ always outputs the mean $\mu$ (action that maximizes $q^\pi$) in state $s$ - indeed, the value of $\mu$ is state-dependent, meaning that a different state could have a different mean.
  
  (Disclaimer: I don't know if the above is mathematically sound and correct but that's my intuition. So, please correct me eventually.)
  
  > **Comments:**
  > **username_2**: In the Gaussian example, those are probability denisties, not probabilities. I'm not sure this is answering what the OP asked though, see my comments on the question  
  
  ---
  
  ### Answer by username_3 on 2023-11-14. Score: 0
  
  The stochastic policy trained in the standard policy gradient method are inherently incompatible with any 'greedy' exploitative action during policy improvement which is a deterministic concept. Policy improvement in policy gradient method simply means its parameters update rule follows the gradient ascent of its specified performance metric $J(\theta)$.
  
  Having said that, the closest counterpart of a greedy action perhaps is the *actor* component in the bootstapping actor-critic methods as detailed in Sutton & Barto's Reinforcement Learning book section 13.5.
  
  > As we have seen in the TD learning of value functions throughout this book, the one-step return is often superior to the actual return in terms of its variance and computational congeniality, even though it introduces bias... When the state-value function is used to assess actions in this way it is called a critic, and the overall policy-gradient method is termed an actor–critic method.
  
  Also take a look at its detailed algo without eligibility traces on page 332, and you can treat its actor's parameters $\theta$ update as some form of 'greedy' action based on the learned critic's feedback $\delta$ if you will, but it's not the same sense as taking the action with maximum action value in all action based RL methods.
  
  > **Comments:**
  > **username_2**: See my comment on the question. This answer assumes the OP does not want to calculate the greedy action, and is searching for something else. However, the question is asking for the definition of the greedy action given the action value function, which is straightforward. Also, if you are using $\epsilon$-greedy behaviour policy, then the greedy action choice *is* also used in the policy improvement step. The OP has not returned to the question to clarify, although they are still active on the site.  
  
  ---
  
  