2.2 时间差分方法
蒙特卡罗方法一个最大的问题是，必须每一次都完成一个回合（局）才能够估计值函数。但是在很多实际的情况中，例如训练一个机器人走路，可能没有结束的状态；或者即使有结束的状态，但是整个回合特别长，例如一盘《王者荣耀》比赛，可能需要半个多小时，完成上万个动作。在这些情况下，蒙特卡罗方法可能就没有办法应用了。1988年Richard Sutton提出时间差分（Temporal Difference，TD）之后，才找到了解决这种问题的有效方法。可以说这是强化学习发展的重要成果之一。
2.2.1 基本思想
时间差分方法是一类利用过去从系统中获得的经验来增量地学习预测未来的方法［18，10，5］。对于大部分的强化学习问题，和蒙特卡罗方法相比，时间差分方法可以以更少的计算资源更快地产生更准确的预测。具体而言，从之前的章节中我们可以得到
蒙特卡罗方法就是想要估计G t，而时间差分方法则是想要估计R（st+1）+γV（st+1）。可以看到，蒙特卡罗方法是用每个样本真实获得的奖赏累积G t来估计vπ（st）的；而时间差分方法则是用样本下一步的奖赏R（st+1）和在策略π下，下一状态st+1的当前估计值来估计vπ（st）的。为了估计这个期望，时间差分方法结合了蒙特卡罗的采样和动态规范的自举（bootstraping）。在具体的算法中，我们可以用当前估计的时间差分误差来更新当前的值函数。
更新的公式如下：
这个公式被称为TD（0），即一步差分公式。其本质思想是只利用t+1步的状态值函数来更新t步的状态值函数。它可以扩展到N步的时间差分公式。它的主要部分便是时间差分误差σ=R（st+1）+γV（st+1）-V（st）。和蒙特卡罗方法相比，时间差分方法对值函数的估计是有偏差的，因此对初值比较敏感，但是其收敛比较快，泛化性也比较好。
在实际的时间差分算法中，大家其实更多地还是估计Q值而不是V值，其中最经典的两个算法是Q-Learning和Sarsa，这两个方法也分别是异策略和同策略的，比较其中的思路，可以更好地理解它们之间的区别。
2.2.2 Sarsa算法
Sarsa算法是一种同策略的时间差分类的算法［68］，Sarsa这个名字很直白地表示了其所使用的五个重要因子：
·S：当前状态（State）；
·A：当前动作（Action）；
·R：当前奖赏（Reward）；
·S：下一状态（State）；
·A：下一动作（Action）。
即Sarsa算法的全称是State-Action-Reward-State-Action算法，假设一定要翻译成中文，则可能是状态-动作-奖赏-状态-动作算法。
前面我们提到了两种值函数，分别是状态值函数V（s）和状态动作值函数Q（s，a），而Sarsa算法就是利用时间差分的方法来对当前策略π下的所有s，a的状态动作值函数Q（s，a）进行估计的方法。具体地，为了对Q（s，a）进行更加准确的估计，Sarsa采取的方式是基于当前策略π在状态St下使用动作At转换到状态St+1后，收获奖赏R（St，At），以此差异来更新原始的对于（St，At）的状态动作值函数的估计，并以At+1为动作来继续执行直到终止状态。其中，更新Q值可使用下式：
其中，α表示学习率，决定了从新样本中获取的信息取代旧信息的程度，比如α为0时对新样本不产生任何影响，α为1时则完全覆盖旧样本。Q（St，At）是当前对于（St，At）的Q值估计，Q′（St，At）是更新后对（St，At）的Q值的估计，这个过程如图2.1所示。看到这里，应该会对Sarsa算法中涉及的五个部分和这个算法的名字有更深刻的了解。基于此过程，可得到Sarsa的具体算法如Algorithm 2所示。
图2.1
Algorithm 2 Sarsa算法
1：随机初始化所有的状态和动作对应的价值函数Q，对于终止状态的Q值初始化为0
2：REPEAT
3：从状态St开始，基于Q值来制定策略（比如ϵ贪婪的方法），选择At
4：计算（St，At）对应的奖赏r，和下一步的状态St+1
5：从St+1开始，基于Q值来制定策略（比如ϵ贪婪的方法），选择At+1
6：Q（St，At）=Q（St，At）+α（R（St，At）+γQ（St+1，At+1）-Q（St，At））
7：直至所有的Q（S，A）收敛，在这里步长α一般需要随着迭代的进行逐渐变小，这样才能保证动作价值函数收敛
可以看到，Sarsa算法更新Q函数是根据当前选择的策略得到的，因此这是一个同策略的算法。在算法中，我们通常使用ϵ贪婪策略来选择动作，但实际上，其他的策略其实也是可以使用的。可以看到，在这样的更新方式下，Sarsa算法下Q值估计的方差要比蒙特卡罗算法下的要小一些，这是因为，Sarsa算法每次更新都是基于上一次估计的Q值，因此Q值迭代之间的变化比较小，收敛比较快。而蒙特卡罗算法每次采样的结果很可能差别很大，因此方差会比较大。另一方面，蒙特卡罗方法的偏差会比较小，因为其每次的估计都是基于一次真实的轨迹；而Sarsa算法估计的Q值偏差有可能特别大。
一个应用Sarsa算法的经典例子是Sutton提到的Windy Gridworld问题，如图2.2所示。图中是一个10×7的网格，每一个格子表示一个可能到达的状态，其中S是起点（Start），G是目标点（Goal），中间一部分网络中存在风的影响，网络下方的数字表示对应的列中风的强度，当该数字是1时，个体进入该列的某个格子时，会按图中箭头所示的方向自动移动一格，当数字为2时，表示顺风移动2格，以此类推模拟风的作用。我们所能做的就是分别往上（U）下（D）左（L）右（R）四个方向移动一步，且每一步的奖赏都是-1，到达目标点的奖赏为0。用Sarsa算法来求解这个问题，以得到最优策略使累积奖赏最大，可能的一个训练结果如图2.3所示。
图2.2
图2.3
通过在网格世界中的探索和学习，智能体学习到这样的行为序列［R，R，R，R，R，R，R，R，R，D，D，D，D，L，L］，得到了比较大的奖赏-14。可以看出，在训练的早期，由于智能体对环境的情况一无所知，需要进行很多的探索和试错，也因此在开始的两千多步中，智能体只能完成非常少的完整一局。但是一旦智能体找到了一条从起点到终点的路径后，其策略优化的速度就变得非常快了。值得一提的是，在这个问题上，蒙特卡罗方法的效率会变得很低，因为必须走完完整一局才可能更新策略，而Sarsa算法则更新较快，能够更快收敛。
2.2.3 Q-Learning算法
在经典强化学习中，最令人熟知的算法莫过于Q-Learning算法。在Sarsa算法中，学习最优策略的同时还在做探索，而Q-Learning直接学习的是最优策略［76］，1步的Q-Learning的Q值更新公式如下：
其更新过程如图2.4所示。
图2.4
在Q-Learning中，并不是根据下一步选择的动作At+1来更新Q值，而是根据在下一状态下的最大Q值max A′Q（St+1，A′）来更新当前的Q（St，At）。这样Q值的更新和具体的策略就分开了，因此是异策略的算法。相比Sarsa算法，因为每次估计的时候都用当前的最大值，所以整体的偏差会变小。但是由于更新是基于最大值的，因此Q-Learning算法的方差会更大一些，同时会倾向于高估当前的状态。基于式（2.19），Q-Learning算法如Algorithm 3所示。
Algorithm 3 Q-Learning算法
1：随机初始化所有的状态和动作对应的价值函数Q，对于终止状态的Q值初始化为0
2：REPEAT
3：从状态St开始，以ϵ贪婪的方法来选择动作At
4：计算（St，At）对应的奖赏r，和下一步的状态St+1
5：根据式（2.19）来更新对应的Q值
6：从St+1开始，以ϵ贪婪的方法来选择动作At+1
7：直至所有的Q（S，A）收敛，在这里步长α一般需要随着迭代的进行逐渐变小，这样才能保证动作价值函数收敛
我们同样用一个简单的例子来演示一下Q-Learning算法的学习过程。Cliff Walking是一个非常经典的问题，如图2.5所示，其也是属于将常见的网格世界进行改造得到的。具体地，Cliff Walking是由4×12的网格组成，每一个格子表示一个可能到达的状态，其中S是起点，G是目标点。下方的一些网格被设定为悬崖，一旦进入就结束游戏。我们所能做的同样是分别往上（U）下（D）左（L）右（R）四个方向移动一步，且每一步的奖赏都是-1，到达悬崖的奖赏是-100。显然，Cliff Walking问题需要求解的是可以合理避开悬崖到达目标的行走策略。显然，Sarsa算法同样可以用来求解这个问题，并且其可能会学习到如图2.6所示的行为序列，如果用Q-Learning算法则可能得到如图2.7所示的行为序列。可以看出，使用Q-Learning算法收敛到的是事实上的最优策略，而用Sarsa算法学习到的却是一个安全路径。为什么会出现这样的差别呢？
图2.5
图2.6
图2.7
Q-Learning算法与Sarsa算法最本质的差别是两者分别属于异策略和同策略。尽管在学习过程中为了保证对环境的探索，Q-Learning算法使用的行为策略的更新往往也采用了ϵ贪婪的方法，但是其目标策略是完全基于Q值的贪婪策略，这就使得当收敛后，其不会再更新可能掉入悬崖的状态动作的Q值，这种机制使其可能得到最优策略。而Sarsa算法是同策略的算法，其目标策略与行为策略相同，比如一般使用ϵ贪婪方法，也导致智能体一直有一定概率会选中掉入悬崖的动作，并且会更新Q值，从而越靠近悬崖的Q值变得越小，最终Sarsa算法学习到的策略就变成走一条安全路径。
然而，如果比较两种算法学到的策略的在线表现，可能会发现，Q-Learning算法所能获得的奖赏要比Sarsa算法更低，这是因为QLearning算法可能会执行掉入悬崖的动作从而出现非常大的负奖赏。因此，在有些环境中，可以采用逐渐减小随机探索比例的方法来使得两种算法都逐渐收敛到最优策略。