Convergence of Q-learning and Sarsa

Question

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.

Answer 1

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)