这一章我们介绍Temporal-difference learning(TD-learning)，以及包含其中的Sarsa和Q-learning。我们先考虑下述表达式：这是对上一章的一个更复杂的例子。R和X都是随机变量，v是一个函数，是一个常数。那我们也可以定义出个g(w): 并且根据采样的r和x，得出对应的观测的：于是，我们就可以和RM算法联系起来，得到求解g(w)=0的迭代公式：这个表达式就和我们待会看TD算法的时候看到的表达式非常像了。这个R就对应的reward，就是衰减因子，v就是state value。

TD算法介绍

先看如何用TD算法求解给定策略π后的state value，也就是policy evaluation。TD算法是一大类算法（包括sarsa，q-learning），也指用来估计state value的特定算法，也就是我们现在要介绍的。

TD算法基于数据（experience）来强化学习，这些数据是根据策略π得到的，它们可以写作：或者。那么我们期待已久的TD算法就长这样：我们注意，智能体在一个时刻只能访问到一个状态。这个算法就是，在t时刻，如果访问了状态空间的s状态，就更新这个状态的state value；而对于其他没有访问的状态，就保持不动。

大多数时候，第二个公式是忽略的。第一个公式的详细标注为：其中叫做TD target，我们希望朝着这个方向去修改。TD target和现在的value有个误差，叫做TD error。总而言之，新的estimate是由旧的estimate加上一个修正项得到的。下面对TD target 和TD error详细介绍。

第一，为什么叫做TD target。这是因为TD算法要让朝着去改进。为了看出这点，我们做以下变形，两边同时减去TD target：由于是一个小的正数，那么显然，那么有：这也意味着我们是朝着TD target前进的。

第二就是TD error：。它表明了两个时间步的差，因此叫时序差分。它也反映了和之间的差。为什么这么说，因为当二者相等时，就应该为0。原因如下：我们把公式的改成 ,故而有：我们对其求期望，得到：因此在期望意义下，TD error能说明和之间的不一致。

TD有什么缺点呢？它只能估计给定一个策略下的state value，不能估计action value，也不能寻找最优策略，因为TD只是在policy estimation。但是在此基础上，能让他改的可以干这两件事。

从数学上讲TD算法是在干什么呢？它是在解一个给出策略后的贝尔曼方程，不同于我们最开始的基于模型的，TD是在不基于模型的条件下解贝尔曼方程。我们先给出一种贝尔曼方程的新表达式：我们令是下一个状态，那么显然可以写成：这个式子也叫做Bellman expectation equation，TD算法就是在解这样一个equation。我们利用上节课所学的RM算法，定义：

根据定义我们知道是这个方程的解。如何求解这个式子？我们有一系列对于R和S'的采样，因此就可以observation：对应的RM算法就可以写成：这个和我们的TD算法是非常类似的，但是有两个问题，一个是他需要数据集合{(s,r,s')} for k=1,2,3,与TD基于episode的取样不一样；第二个是不知道。

为了解决第一个问题，我们把{(s,r,s')}换成,为了解决第二个问题，我们把换成，这时的收敛性是可以保持的。具体证明就不阐述了。

TD和MC有什么区别?首先，前者是on-line的，即是一个episode是边采边更新的；后者是off-line的，即一个episode全采完后才能更新。其次，前者因为是on-line的，能够处理continuing tasks，后者只能处理episodic tasks。这些很重要，经常看论文能看到这些词汇。至于其他的，前者需要initial guesses，后者不需要；前者因为采样随机变量少，具有low estimation variance，后者具有high estimation variance。

Sarsa

我们要policy improvement的话，需要知道action value，哪个value大就选哪个；因此我们引进Sarsa，来估计action value。我们将此和policy improvement结合起来，就能找到optimal policy。加入我们现在有如下数据：（看出来了嘛？这就是为什么叫sarsa，s a r s a），那么我们可以利用sarsa算法来更新：类似于TD，sarsa也是在解一个贝尔曼公式，这个公式是：我们的最终目的是找到最优策略，所以我们还要把sarsa和policy improvement结合起来（实际上大多数时候听到的sarsa是包括了后者的）。sarsa伪代码如下：

注意我们policy improvement采用的是epsilon-greedy。

Expected Sarsa

这是对经典sarsa的改进，公式为：唯一的差别在于公式一的后面。改动的项具体为：就是把action value变成了state value。因为期望，它需要更多计算量，但是由于不需要对采样，所以随机变量减少了，随机性也变小了。同样的，expected sarsa也在求解一个贝尔曼公式：

n-step Sarsa

它包含了sarsa和蒙特卡洛两种方法。考虑我们的回报

的不同写法：
当n趋近于正无穷，就变成了MC。那些然，居于Sarsa和MC中间的就是n-step sarsa，它的公式显然就是：

Q-learning

直到今天Q-learning仍然在广泛使用，虽然用的是DQN。Q-learning从数学上讲，与sarsa区别是它主要是直接估计最优action value，就不需要PE和PI交替进行了。Q-learning算法公式为：和Sarsa很像。区别在于TD target，Sarsa的TD target是而Q-learning里是。在数学上，Q-learning解决如下数学问题，他是在求解一个贝尔曼最优方程而非贝尔曼方程：为了更详细介绍Q-learning，先介绍两个重要概念：on-policy和off-policy。我们定义，behavior policy是用来生成经验样本的，target policy是用来不断朝着最优策略更新的。如果二者相同，那么就叫on-policy；不同就是off-policy。额，通俗的讲，就是前者是自己做自己学，后者是可以拿别人的给自己学（并不是说不能自己做自己学）。我们的sarsa是前者，Q-learning是后者。

off-policy的好处就是可以把别人产生的experience拿来自己用。如何判断一个RL算法是on policy还是off policy？第一就是看解决什么问题（贝尔曼还是贝尔曼最优）；第二是看算法需要什么东西。sarsa和MC是off policy的，为什么Q-learning是on-policy?

因为它求解贝尔曼最优方程，它显式地不含任何策略；其次，它需要，并不需要；而是依赖于p而不是π的，所以它的behavior policy是根据策略从生成，而target policy是选q大的action。