Are Q-learning and SARSA the same when action selection is greedy?

Question

I'm currently studying reinforcement learning and I'm having difficulties with question 6.12 in Sutton and Barto's book.

Suppose action selection is greedy. Is Q-learning then exactly the same algorithm as SARSA? Will they make exactly the same action selections and weight updates?

I think it's true, because the main difference between the two is when the agent explores, and following the greedy policy it never explores, but I am not sure.

Answer 1

If we write the pseudo-code for the SARSA algorithm we first initialise our hyper-parameters etc. and then initialise $S_t$, which we use to choose $A_t$ from our policy $\pi(a|s)$. Then for each $t$ in the episode we do the following:

1. Take action $A_t$ and observe $R_{t+1}$, $S_{t+1}$
2. Choose $A_{t+1}$ using $S_{t+1}$ in our policy
3. $Q(S_t, A_t) = Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t, A_t)]$

Now, in Q-learning we replace $Q(S_{t+1},A_{t+1})$ in line 3 with $\max_aQ(S_{t+1},a)$. Recall that in SARSA we chose our $A_{t+1}$ using our policy $\pi$ - if our policy is greedy with respect to the action value function then this simply means the policy is $\pi(a|s) = \text{argmax}_aQ(s,a)$ which is exactly how we choose our weight update in Q-learning.

To answer the question - no, they are not always the same algorithm.

Consider where we transition from $s$ to $s'$ where $s'=s$. I will outline the updates for SARSA and Q-learning indexing the $Q$ functions with $t$ to demonstrate the difference.

For each case, I will assume we are at the start of the episode, as this is the easiest way to illustrate the difference. Note that actions denoted by $A_i$ are for actions taken explicitly in the environment -- in the Q-Learning update the $\max$ action that is chosen for the update is not executed in the environment, the action taken in the environment is chosen by the policy after the update has happened.

SARSA

1. We initialise $S_0 = s$ and choose $A_0 = \text{argmax}_a Q_0(s,a)$
2. Take action $A_0$ and observe $R_{1}$ and $S_{1} = s' = s$.
3. Choose action $A_{1} = \text{argmax}_aQ_{0}(s,a)$
4. $Q_{1}(S_0,A_0) = Q_0(S_0,A_0) + \alpha [R_{1} + \gamma Q_0(s,A_1) - Q_0(S_0,A_0)]$

Q-Learning

1. Initialise $S_0 = s$
2. Choose action $A_0 = \text{argmax}_aQ_0(s,a)$, observe $R_{1}, S_{1} = s' = s$
3. $Q_{1}(S_0,A_0) = Q_0(S_0,A_0) + \alpha [R_{1} + \gamma \max_aQ_0(s,a) - Q_0(S_0,A_0)]$
4. Choose action $A_1 = \text{argmax}_aQ_1(s,a)$

As you can see the next action for the updates in SARSA (line 4) and Q-learning (line 3) are taken with respect to the same $Q$ function, but the key difference is that the actual next action taken in $Q$-learning is taken with respect to the updated $Q$-function.

The key for understanding this edge case is that when we transition into the same state, the Q-Learning update will update the Q-function before choosing $A_1$. I have indexed actions and Q-functions by the episode step - hopefully, it makes sense why I have done this for the Q-functions as, usually, this would not make sense, but, because we have two successive states that are the same, it is okay.

Answer 2

SARSA: $$Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$$ Q-Learning $$Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\max Q(S_{t+1},a)-Q(S_t,A_t)]$$

Consider the following case: For both SARSA and Q-Learning we'll randomly select $a_1$, when $t=1, t=2$, and assume $\alpha R_2 > 0$

SARSA At $t=2$ to determine $Q(S_3,A_3)$ since it's greedy it'll choose $s_1,a_1$ and the recalculate $Q(s_1,a_1)$ $$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline (t,s,a, R) & Q(s_1,a_1) & Q(s_1,a_2) \\ \hline & 0 & 0 \\ \hline (1,s_1,a_1, R_2) & \alpha R_2 & 0\\ \hline (2,s_1,a_1, R_3) & \alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2& 0 \\\hline (3,s_1,a_1, R_4) & & 0\\ \hline \end{array}$$

Q-Learning, at $t=2$ to determine $Q(S_3,A_3)$, it'll first evaluate the policies so inorder to pick $Q(s_1,a_1)$ $$\alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2 > 0$$ $$R_2 + R_3 +\alpha\gamma R_2 -\alpha R_2 > 0$$ $$-R_2(-1-\alpha\gamma + \alpha) + R_3 > 0$$ $$R_3 > R_2(\alpha-\alpha\gamma-1)$$

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline (t,s,a) & Q(s_1,a_1) & Q(s_1,a_2) \\ \hline & 0 & 0 \\ \hline (1,s_1,a_1, R_2) & \alpha R_2 & 0\\ \hline (2,s_1,a_1, R_3) & \alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2& 0 \\\hline (3,s_1,a_1, R_4) & & \\\hline \end{array}$$