Q-Learning是TD算法下Off-policy的表现形式，但Q-Learning算法并不需要通过Importance Sampling去估计动作值函数，可以从理论上证明，在Target Policy为greedy的情况下使用Importance Sampling去估计当前动作状态的Q函数与直接使用下一状态的Q函数的最大值做TD运算从而更新当前状态的Q值，这两种方法是完全等价的。也就是说Q-Learning不需要像Sarsa算法那样依据Policy产生与Next State对应的当前最优的Next Action，这也决定了Q-Learning与Sarsa算法的最大区别就是Off-policy与On-policy的区别（可以先阅读【RL系列】Off-Policy与On-Policy以了解这两种控制方法）。在Reinforcement Learning: An Introduction(2017)这本书中给出了一个例子，Cliff Walking，可以很好的比较这两种算法的区别：

Cliff Walking

这个问题很简单，也是属Grid World系列问题（什么是Grid World？可以参考：Dynamic programming in Python ；Grid World系列问题之Windy Grid World，可以参考：【RL系列】SARSA算法的基本结构）。在一个4x12的Grid World中将某些格子设定为悬崖，在设计Reward时，将Agent掉入悬崖的情况记为奖励-100，同时每走一步奖励-1。Cliff Walking问题需要求解的是可以合理避过悬崖到达目标的行走策略。

这是一个典型的episode task类问题。S为Start，即起始点，G为Goal，即为终点，每个episode的开始皆从起始点行走，遇到Cliff，即悬崖，变回到起始点重新开始，直到到达终点G，episode结束。这里如若使用SARSA算法，程序的基本结构与上一篇关于Windy Grid World文章中介绍的基本一致。对于Q-Learning算法的实现，这里只需要将SARSA中值函数更新部分的Q(S', A')替换为max(Q(S', All Action))即可。需要关注的不是算法的实现，而是两种方法所产生的不同的Policy。

SARSA算法收敛后的Policy

Q-Learning算法收敛后的Policy

Q-Learning可以收敛出Optimal Policy而SARSA却选择的是Safe Path，本质上是因为Q-Learning的Target Policy是绝对的greedy策略，绝对的greedy策略保证了Agent在Q值进入收敛后不会也不可能再记录可能掉入悬崖的状态动作的Q值，也可以说是Off-Policy类的控制方法并不会受到greedy策略无探索性的影响，所以才能够产生Optimal Policy。

然而SARSA算法使用的epsilon-greedy策略来更新Q值，也就是说不论何时，Agent总是有epsilon的概率选择非最优的动作，其中掉入悬崖的动作也始终有一定的概率被选中，并在Q函数更新时被记录下来，所以整个Grid的Q函数变成了越靠近悬崖，值越小的分布，最终导致了SARSA选择的是safe path。

Q-Learning的Target Policy是基于Q值的完全greedy policy，但在学习探索过程中决定Agent行走的Behavior Policy的更新却和SARSA同是epsilon-greedy policy。在进入收敛后，由于Q-Learning的Agent每次选择的都是Optimal Path但又因为Behavior Policy保持了一定的探索性，所以总是有一定的概率选择掉入悬崖的动作，虽然这些动作产生的Q值并不会被更新记录。SARSA的Agent在进入收敛后，基本上选择的是Safe Pass，掉入悬崖的概率比Q-Learning的Agent要小很多。所以，SARSA算法平均每个episode获得的Reward值通常要比Q-Learning更接近实际的步数乘上-1，也就是说SARSA的在线学习的效果比Q-Learning更好。下图表示出了每个episode两种算法的平均收益对比的情况。