0
$\begingroup$

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)$.

$\endgroup$
5
  • $\begingroup$ Probably related: ai.stackexchange.com/questions/40149/…. In my opinion, the action that can be considered "greedy" for a stochastic policy, should be one of the distribution mode(s). $\endgroup$ Commented Jun 10, 2023 at 15:38
  • $\begingroup$ Could you please write your guess mathematically? $\endgroup$ Commented Jun 10, 2023 at 19:05
  • $\begingroup$ Sure, have a look at my answer $\endgroup$ Commented Jun 11, 2023 at 9:26
  • 2
    $\begingroup$ 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". $\endgroup$ Commented Jun 11, 2023 at 10:45
  • $\begingroup$ 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. $\endgroup$ Commented Jun 11, 2023 at 11:23

2 Answers 2

1
$\begingroup$

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, 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, 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 (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.)

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Commented Jun 11, 2023 at 11:26
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Nov 14, 2023 at 15:45

You must log in to answer this question.

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