Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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
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.
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.
.
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.
