1
$\begingroup$

Could someone explain to me which is the key difference between the $\epsilon$-greedy policy and the softmax policy? In particular, in the contest of SARSA and Q-Learning algorithms. I understood the main difference between these two algorithms, but I didn't understand all the combinations between algorithm and policy

  • SARSA + $\epsilon$-greedy
  • SARSA + Softmax
  • Q-Learning + $\epsilon$-greedy
  • Q-Learning + Softmax
$\endgroup$
4
$\begingroup$

The $\epsilon$-greedy policy is a policy that chooses the best action (i.e. the action associated with the highest value) with probability $1-\epsilon \in [0, 1]$ and a random action with probability $\epsilon $. The problem with $\epsilon$-greedy is that, when it chooses the random actions (i.e. with probability $\epsilon$), it chooses them uniformly (i.e. it considers all actions equally good), even though certain actions (even excluding the currently best one) are better than others. Of course, this approach is not ideal in the case certain actions are extremely worse than others. Therefore, a natural solution to this problem is to select the random actions with probabilities proportional to their current values. These policies are called softmax policies.

Q-learning is an off-policy algorithm, which means that, while learning a so-called target policy, it uses a so-called behaviour policy to select actions. The behaviour policy can either be an $\epsilon$-greedy, a softmax policy or any other policy that can sufficiently explore the environment while learning.

The figure below shows the pseudocode of the Q-learning algorithm. In this case, the $\epsilon$-greedy policy is actually derived from the current estimate of the $Q$ function. The target policy, in this context, is represented by the $\operatorname{max}$ operator, which is used to select the highest $Q$ value of the future state $s'$, which is the state the RL agent ends up in after having taken the action $a$ selected by the $\epsilon$-greedy behaviour policy, with respect to another action $a'$ from state $s'$. This may sound complicated, but if you read the pseudocode several times, you will understand that there are two different actions (and states). The target policy (i.e. the policy that the RL agent wants to learn) is represented by the $\operatorname{max}$ operator in the sense that the so-called target of the Q-learning update step, i.e. $r + \gamma \operatorname{max}_{a'} Q(s', a')$, assumes that the greedy action is taken from the next state $s'$. For this reason, Q-learning is said to learn the greedy policy (as a target policy), while using an exploratory policy, usually, the $\epsilon$-greedy, but it can also be the softmax. Note that, in both cases, the policies are derived from the current estimate of the Q function.

enter image description here

On the other hand, SARSA is often considered an on-policy algorithm, given that there aren't necessarily two distinct policies, i.e. the target policy is not necessarily different than the behaviour policy, like in Q-learning (where the target policy is the greedy policy and the behaviour policy is e.g. the softmax policy derived from the current estimate of the Q function). This can more easily be seen from the pseudocode.

enter image description here.

In this case, no $\operatorname{max}$ operator is used and the $\epsilon$-greedy policy is mentioned twice: in the first case, it is used to choose the action $a$ and indirectly $s'$, and, in the second case, to select the action $a'$ from $s'$. In Q-learning, $a'$ is the action that corresponds to the highest Q value from $s'$ (i.e. the greedy action). Clearly, you are free to choose a different policy than the $\epsilon$-greedy (in both cases), but this will possibly have a different effect.

To conclude, to understand the difference between Q-learning and SARSA and the places where the $\epsilon$-greedy or softmax policies can be used, it is better to look at the pseudocode.

$\endgroup$
4
  • $\begingroup$ If I train my agent with softmax policy, is the learning process more unstable w.r.t the epsilon greedy? $\endgroup$
    – FraMan
    Jan 26 '20 at 12:38
  • $\begingroup$ @FraMan http://incompleteideas.net/book/first/ebook/node17.html says that it is unclear whether softmax is better or not than $\epsilon$-greedy and it may depend on the problem. $\endgroup$
    – nbro
    Jan 26 '20 at 12:45
  • $\begingroup$ does Q-Learning + epsilon greedy makes sense? Q-Learning use a greedy policy as default. $\endgroup$
    – FraMan
    Jan 26 '20 at 15:30
  • $\begingroup$ @FraMan I think this is a good new question you could ask on the website ;) $\endgroup$
    – nbro
    Jan 26 '20 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.