# Convergence of Q-learning and Sarsa

You can show that both SARSA (TD On-Policy) and Q-learning (TD Off-Policy) converge to a certain state-value function q(s,a). However they don't converge to the same q(s,a).

Looking at the following example you can see that SARSA finds a different 'optimal' path than Q-learning.

• Is SARSA useless then?
• Which attribute of an algorithm tells me if it will converge to the optimal/shortest path? (biasedness, consistency, variance for n to infinity)

My idea
An estimator/algorithm can only converge to a constant/static value function when its variance for n to infinity goes to 0. Both SARSA and Q-learning converge thus their variance is 0. They don't converge to the same value because SARSA is biased.

The Q-learning update is as follows:

$Q(s_t,a_t) = (1-\alpha)Q(s_t,a_t) + \alpha( R(s_t,a_t) + \gamma(\;\underset{a}{\max}\;Q(s_{t+1}, a)))$

The SARSA update is:

$Q(s_t,a_t) = (1-\alpha)Q(s_t,a_t) + \alpha( R(s_t,a_t) + \gamma(Q(s_{t+1}, a_{t+1})))$

So the only difference is that Q-learning uses the $\max$ when estimating the future reward. What does this mean? If you always consider the "best" possible future outcomes, you are being very optimistic. So you are likely to go along the edge of the cliff because you don't consider you might slip or there might be a gust of wind etc. (btw, this information is not shown from the figure you posted)

While SARSA is not being very optimistic because it does not always consider the best future value, instead it considers an outcome based on the current policy. That is, $a_{t+1}$ is chosen in the same way that $a_t$ was chosen.

Is SARSA useless then?

It is clearly useful if you want to be less optimistic. Consider training a physical robot to walk, with each fall it would cost real money to replace or repair the robot.

Which attribute of an algorithm tells me if it will converge to the optimal/shortest pat?

The key is the method of selection for the future actions. If you $\max$ over future Q-values you are being optimistic, which in this case leads to a short path.

They don't converge to the same value because SARSA is biased.

Actually, both Q-learning and SARSA are biased. (They are definitely biased with non-linear function approximators, but not 100% sure when a linear-function approximation or no-function approximation is used)

• You mentioned "...you are being very optimistic" but that's excalty what I want - an optimal solution based on my model. I don't want wind or anything else to be taken into consideration as it's not part of my environment. In that context, when do I want a non-optimistic/optimal solution?
– siva
Commented Dec 7, 2017 at 17:18
• Oh, then your question was not clear. Are you claiming that the environment is deterministic?
– A.D
Commented Dec 7, 2017 at 17:20
• Sorry my bad. Yes the environment is deterministic. The agent gets a reward of -1 for each timestep and -100 if it hits the cliff. I wish there was a comprehensive table which desbribes for all RL algos wether they are consistent/biased or not and what variance they have.
– siva
Commented Dec 7, 2017 at 17:22
• Ok, IMO they will then have similar paths... but still not the same path. Because there is still stochasticity in the action-selection. SARSA learns that there is always a chance of the agent making a misstep (think of it as being absent minded or something) and is being cautious against that.
– A.D
Commented Dec 7, 2017 at 17:25
• you might be able to force SARSA to behave more like Q-learning, if you really push for fastest path, by making the cost of each step -10 or something like that
– A.D
Commented Dec 7, 2017 at 17:26