SARSA and Q Learning are both reinforcement learning algorithms that work in a similar way. The most striking difference is that SARSA is on policy while Q Learning is off policy. The update rules are as follows:

Q Learning:

$$Q(s_t,at_)←Q(s_t,a_t)+α[r_{t+1}+γ\max_{a'}Q(s_{t+1},a')−Q(s_t,a_t)]$$

SARSA: $$Q(s_t,a_t)←Q(s_t,a_t)+α[r_{t+1}+γQ(s_{t+1},a_{t+1})−Q(s_t,a_t)]$$

where $s_t, a_t, r_t$ are state, action in reward at time steps $t$ and $\gamma$ is a discount factor.

They mostly look the same except that in SARSA we take actual action and in Q Learning we take the action with highest reward.

Are there any theoretical or practical settings in which one should the prefer one over the other? I can see that taking the maximum in Q Learning can be costly and even more so in continuous action spaces. But is there anything else?

up vote 9 down vote accepted

They mostly look the same except that in SARSA we take actual action and in Q Learning we take the action with highest reward.

Actually in both you "take" the actual single generated action $a_{t+1}$ next. In Q learning, you update the estimate from the maximum estimate of possible next actions, regardless of which action you took. Whilst in SARSA, you update estimates based on and take the same action.

This is probably what you meant by "take" in the question, but in the literature, taking an action means that it becomes the value of e.g. $a_{t}$, and influences $r_{t+1}$, $s_{t+1}$.

Are there any theoretical or practical settings in which one should the prefer one over the other?

Q-learning has the following advantages and disadvantages compared to SARSA:

  • Q-learning directly learns the optimal policy, whilst SARSA learns a near-optimal policy whilst exploring. If you want to learn an optimal policy using SARSA, then you will need to decide on a strategy to decay $\epsilon$ in $\epsilon$-greedy action choice, which may become a fiddly hyperparameter to tune.

  • Q-learning (and off-policy learning in general) has higher per-sample variance than SARSA, and may suffer from problems converging as a result. This turns up as a problem when training neural networks via Q-learning.

  • SARSA will approach convergence allowing for possible penalties from exploratory moves, whilst Q-learning will ignore them. That makes SARSA more conservative - if there is risk of a large negative reward close to the optimal path, Q-learning will tend to trigger that reward whilst exploring, whilst SARSA will tend to avoid a dangerous optimal path and only slowly learn to use it when the exploration parameters are reduced. The classic toy problem that demonstrates this effect is called cliff walking.

In practice the last point can make a big difference if mistakes are costly - e.g. you are training a robot not in simulation, but in the real world. You may prefer a more conservative learning algorithm that avoids high risk, if there was real time and money at stake if the robot was damaged.

If your goal is to train an optimal agent in simulation, or in a low-cost and fast-iterating environment, then Q-learning is a good choice, due to the first point (learning optimal policy directly). If your agent learns online, and you care about rewards gained whilst learning, then SARSA may be a better choice.

  • 1
    Thank you for you answer. Do you know of any papers that deal with this from a theoretical point of view? – hh32 Feb 5 at 7:30
  • @hh32: No sorry I don't have any reference from papers. The subject is covered in Sutton & Barto (using the Cliff Walking example). The only detailed treatments I have seen are mainly experimental, not theoretical. – Neil Slater Feb 5 at 8:06
  • Why is it that we update the Q values using S' and A'? If the goal is to have a less aggressive exploitation policy, why don't we simply use an epsilon greedy action policy with a small/decaying epsilon, e.g. 0.1? That would make the program quite conservative as well. What's the advantage of updating using S'A' as opposed to using the optimal action (which seems to make more sense). – Muppet Aug 8 at 21:53
  • @Muppet: You should ask that as a new question. – Neil Slater Aug 9 at 7:50

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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