What are the differences between SARSA and Q-learning?

Question

From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series), are the following definitions:

To aid my learning of RL and gain an intuition, I'm focusing on the differences between some algorithms. I've selected Sarsa (on-policy TD control) for estimating Q ≈ q * and Q-learning (off-policy TD control) for estimating π ≈ π *.

For conciseness I'll refer to Sarsa (on-policy TD control) for estimating Q ≈ q * and Q-learning (off-policy TD control) for estimating π ≈ π * as Sarsa and Q-learning respectively.

Are my following assertions correct?

The primary differences are how the Q values are updated.

Sarsa Q value update: $ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma Q ( S ′ , A ′ ) − Q ( S, A ) ] $

Q-learning Q value update: $ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma \max_a Q ( S ′ , a ) − Q ( S, A ) ] $

Sarsa, in performing the td update subtracts the discounted Q value of the next state and action, S', A' from the Q value of the current state and action S, A. Q-learning, on the other hand, takes the discounted difference between the max action value for the Q value of the next state and current action S', a. Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?

Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step

Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.

Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy? Q learning does not utilise the next state-action pair in performing the td update, it just utilises the next state and current action, this is given in the algorithm definition as $ Q ( S ′ , a ) $ what is $a$ in this case ?

Answer 1

The main difference between the two is that Q-learning is an off policy algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at the update rule.

Q-Learning

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$

SARSA

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$

In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.

In Q-learning, we learn about the greedy policy whilst following some other policy, such as $\epsilon$-greedy. This is because when we transition into state $s'$ our TD-target becomes the maximum Q-value for whichever state we end up in, $s'$, where the max is taken over the actions.

Once we have actually updated our Q-function and we need to choose an action to take in $s'$, we do so from the policy we are using to generate our actions from -- thus we are learning about the greedy policy whilst following some other policy, hence off policy. In SARSA when we move into $s'$ our TD-target is chosen by the Q-value for the state we transition into and then the action we would choose based on our policy.

Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?

It will be, because the policy we use to choose our actions is ensured to explore sufficiently around all of the state-action pairs and so it is guaranteed to be encountered at some point.

Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.

It is not an $\arg \max$, it is a $\max$. This is defined as $$\max_x f(x) = \{f(x) | \forall y\; : f(y) \leq f(x) \}$$

Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step

Kind of - the action that you chose for your TD-target in SARSA becomes the next action that you consider in the next step of the episode. This is natural because essentially you are in state $s$, you take action $a$ and observe a new state $s'$, at which point you can use your policy to see which action you will take, call this $a'$, and then perform the SARSA update, and then execute that action in the environment.

Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?

Yes, any policy can be used although you want to choose a policy that allows sufficient exploration of the state-space.

Q learning does not utilise the next state-action pair in performing the td update, it just utilises the next state and current action, this is given in the algorithm definition as $Q(S',a)$ what is $a$ in this case ?

in the algorithm it actually has $\max_a Q(S',a)$, which if you refer back to my earlier definition of what the $\max$ operator does, should answer this question.