时间差分学习（TD）是强化学习独特的核心思想，TD结合了DP方法和MC方法的思想。
TD可以从原始经验中学习，不需要知道环境模型，这一点和MC方法很类似，MC方法也是不需要清楚知道环境模型；TD不需要仿真出完整的轨迹，直接利用其它状态的估计来更新当前状态值，这一点和DP方法很类似，即需要自举。DP、MC、TD方法之间的关系是强化学习理论中反复讨论的主题。
关于具体方法，其实都是广义策略迭代的思想，在预测阶段，即值函数评估，三种方法各不相同，DP使用贝尔曼方程，MC使用采样回报均值，TD即将进行介绍；在控制阶段，即策略提升，都是用贪婪测试完成策略提升环节。
1. 时间差分预测
TD方法和MC方法都是用经验来估计值函数。
在MC方法中，状态$S_t$的值函数表达式为：
\[V(S_t) \leftarrow V(S_t) + \alpha[ G_t - V(S_t)]\tag{1-1}\]公式1-1中，$G_t$表示从$S_t$后直到episode结束后得到的回报总和。因此，更新状态值函数，必须等到一个episode结束才行。而TD方法只需要等到下一步，在$t+1$不，就能利用$R_{t+1}$计算一个有效的更新目标。
公式为：
\[V(S_t)\leftarrow V(S_t)+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]\tag{1-2}\]公式1-2所示，TD方法和MC方法的不同就是，MC的更新目标为$G_t$，TD方法的更新目标为$R_{t+1}+\gamma V(S_{t+1})$，TD的这种方法叫做TD(0)，或者叫一步TD（one-step TD）。
更新公式1-2的策略预测伪代码为：
公式1-2所显示的方法称为自举，我们看一下其推导：
\[\begin{align} v_{\pi}(s)&=\Bbb E_{\pi}[G_t \mid S_t=s]\\ &=\Bbb E_{\pi}[R_{t+1}+\gamma G_{t+1} \mid S_t=s]\\ &=\Bbb E_{\pi}[R_{t+1}+\gamma v_{t+1} \mid S_t=s] \end{align}\tag{1-3}\]状态值函数的估计是一个期望，因此MC采取采样回报均值的方法估计其期望值；DP方法因为已知环境模型，因此求解期望不是问题；至于TD方法，即采样，又估计。
我们再来看一下TD（0）的备份图：
通过备份图可以发现，其只有一个分支，因为使用的是采样的方式，称之为采样更新；DP使用期望更新，其使用所有可能的后续状态的分布；MC方法使用采样更新，但是它是完整一条分支，而不是TD这样，使用自举，仅观测一个状态。
在TD（0）更新中，当前估计$V(S_t)$与估计目标$R_{t+1}+\gamma V(S_{t+1})$的差别，称作TD误差（TD-error）。
TD误差表示为：
\[\delta_t \doteq R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \tag{1-4}\]RL中，TD误差有很多不同的形式，不同的形式演化出不同的算法。
MC误差也可以转换成TD误差的格式：
\(\begin{aligned} G_{t}-V\left(S_{t}\right) &=R_{t+1}+\gamma G_{t+1}-V\left(S_{t}\right)+\gamma V\left(S_{t+1}\right)-\gamma V\left(S_{t+1}\right) \\ &=\delta_{t}+\gamma\left(G_{t+1}-V\left(S_{t+1}\right)\right) \\ &=\delta_{t}+\gamma \delta_{t+1}+\gamma^{2}\left(G_{t+2}-V\left(S_{t+2}\right)\right) \\ &=\delta_{t}+\gamma \delta_{t+1}+\gamma^{2} \delta_{t+2}+\cdots+\gamma^{T-t-1} \delta_{T-1}+\gamma^{T-t}\left(G_{T}-V\left(S_{T}\right)\right) \\ &=\delta_{t}+\gamma \delta_{t+1}+\gamma^{2} \delta_{t+2}+\cdots+\gamma^{T-t-1} \delta_{T-1}+\gamma^{T-t}(0-0) \\ &=\sum_{k=t}^{T-1} \gamma^{k-t} \delta_{k} \end{aligned}\tag{1-5}\) 当然，公式1-5的前提是，$V$在一个episode中不改变。而实际中，V在episode中肯定是变化的，所有只能说公式1-5近似成立。
2. TD预测方法的优势
TD方法估计状态值函数是依赖于其他状态值函数的估计的，相当于从一个猜测估计另一个猜测。
我们来看一下TD方法的优势：
- 不需要环境模型
- 相比于MC方法，TD方法本质上能够以增量的、在线的方式实现。MC方法只能在一个episode结束后才能执行更新，对于很长的episode，甚至没有episode的连续任务，MC方法的劣势是很大的。
- 一些MC方法必须忽视或者折扣一些episode（包含待试验动作），会降低学习速率。TD方法则不受这种影响。
TD方法在步长参数足够小，且遵循公式1-2的更新规则，TD(0)方法能够被证明收敛到$v_{\pi}$
在实际中，TD方法在随机任务上比同样学习步长（$\alpha$）的MC方法更快。
在经验较少时，即episode的数量较少时，我们可以使用类似于深度学习中epoch的思想，多批次的使用经验进行更新。在TD中，这种方法叫做批更新，具体方法为，使用公式1-2，不在每一步进行更新，而是等所有经验遍历完后，再一次性的更新，如果在所有经验中，一个状态出现多次，更新就是各个增量的和。
在批更新中，在超参数$\alpha$足够小的，TD方法和MC方法都能收敛到最优解，但是TD方法比MC方法要好，因为MC的方法只有在特定情况下才是最优的，TD的最优则依赖于预测回报。
另一个方向理解，就是MC方法过拟合了，TD方法训练误差和测试误差，因此过拟合可能性比较小。
总结上述内容，就是MC方法试图找到训练集上误差最小的估计，TD则是试图找到一个估计值，这个估计值相对于马尔科夫过程的最大似然模型时最优的。如果最大似然模型是精确的，那么TD方法得到的估计也是准确的，这是确定性等价估计。
3. Sarsa:on-policy TD
第1、2小节介绍如何使用TD方法评估值函数，即预测问题；本小节介绍使用TD法进行策略提升，即控制问题。
TD方法同样分为两类：on-policy、off-policy
在第1、2小节，我们策略评估的是状态值函数，但是在不知道环境模型的情况下，我们没法使用状态值函数转换成对应的策略。因此，需要使用动作值函数。
使用TD(0)方法估计动作值函数的公式如下：
\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]\tag{3-1}\]通过公式3-1，发现动作值函数的更新方式和状态值函数的更新方式相同，它完全使用了五元组信息$(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$，这也是算法名称Sarsa的由来。这样一个五元组也叫作一个转移（transition）。
下面我们来看一下Sarsa算法的伪代码：
在上述伪代码中，实际上并没有显式的策略提升的代码，原因是代码提升相当于当前策略的贪婪策略，$\epsilon$-greedy就是相对于$\epsilon$-soft 的贪婪算法，直接在选择动作时使用贪婪策略。
4. Q-learning:off-policy TD
上一小节讲了一种on-policy的基于TD的算法，叫做Sarsa，本小节讲一种off-policy的基于TD的算法，叫做Q-learning。它是强化学习的一大突破，形式简单，但影响深远。
Q-learning的更新公式如下：
\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma \max _aQ(S_{t+1},a)-Q(S_t,A_t)]\tag{4-1}\]公式4-1的更新过程和Sarsa算法很类似，但是却有本质不同：
- 从公式看，Sarsa的更新目标是下一个状态动作对的Q值，在Q-learning中是最大化Q值操作。
- Q-learning取的是最大化Q值，实际上，这个动作并没有执行，即行为策略并没有执行，因此行为策略和我们的目标策略没有必然的联系，所以它是off-policy的。
- 通过公式4-1，最终的策略逼近于最优值函数$q_{\ast}$，而不是当前的值函数$q_{\pi}$。类似于Sarsa。
当然，在之前提过，我们的行为策略要能探索到所有的状态动作对，并且学习率$\alpha$足够小且满足随机近似条件，那么可以证明Q-learning算法能够以概率1收敛到$q_{\ast}$
Q-learning算法的伪代码如下：
在伪代码中，实际上并没有显式的使用两个策略（行为策略、目标策略），但是在关键步骤的更新中，优化的策略和行为策略并不一定相同，因此，也是off-policy的。其他大体逻辑与Sarsa类似。
5. 期望Sarsa算法
我们把Q-learning算法中，状态动作值函数的最大值，变为求期望，看一下公式：
\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma \Bbb E[Q(S_{t+1},A_{t+1})\mid S_{t+1}]-Q(S_t,A_t)]\\ \leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma \sum_a \pi(a \mid S_{t+1} )Q(S_{t+1},a)-Q(S_t,A_t)]\\ \tag{5-1}\]在公式5-1中，我们将更新目标变成期望的形式，因为它的形式和Sarsa一样，更新目标是Q的期望值，因此叫做期望Sarsa算法。
实际中，期望Sarsa的效果比Sarsa的效果好一点，但是相比较而言，计算量更大（期望值）。
6. 最大化偏差 + Double Learning
在DP、MC、TD方法中，都遵循广义策略迭代的思想，在GPI中，策略提升往往是使当前的策略贪婪，在Q-learning中取最大动作值，以及Sarsa中使用贪婪的算法选择动作。这种贪婪，也就是最大化的操作会导致严重的正向偏差，称之为最大化偏差。
对于最大化偏差的理解：
假设对于一个状态s，有很多动作a可以选择，每个(s,a)的真实值都为0。但是由于估计偏差或者不准确性导致估计的值Q(s,a)大于或者小于0，再对其做最大化操作，就得到了一个正值，这时对于真实的值0，是一个正向偏差。
我们观察一下Q-learning算法，当前的更新目标为$R_{t+1} +\gamma \max_a Q(S_{t+1}, a)$，在更新目标中，我们需要知道两个条件：
- 真实的$Q(S_{t+1},\cdot)$
- 哪个动作使得$Q(S_{t+1},\cdot)$最大
在Q-learning中，我们使用相同的数据来估计这两个条件。相当于在最大化偏差（$Q(S_{t+1},\cdot)$）的基础上又做了最大化操作，相当于错上加错。于是，我们将这个过程分开，使用两个估计值分别计算需要的两个条件：
同时估计两个值$Q_1(a)$和$Q_2(a)$，其中一个用来选择最大化值的动作，即$A^\ast = \arg \max_aQ_1(a)$；另外一个计算具体的动作状态值，即$Q_2(A^\ast) = Q_2(\arg \max_a Q_1(a))$，这样就无偏了。
以上的思想就是Double Q-learning，虽然我们有两个估计，但是计算量并没有增加，只是需要增加一倍的内存进行存储，对于使用网络近似值函数的情况，就是多了一个网络。
Double Q-learning的更新公式如下：
\[Q_1(S_t, A_t) \leftarrow Q_1(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q_2(S_{t+1}, \arg \max_a Q_1(S_{t+1}, a) ) -Q_1(S_t, A_t) \right] \tag{6-1}\]我们使用0.5的概率使用公式6-1更新$Q_1$，另外的0.5概率更新$Q_2$，伪代码如下：
7. 总结
TD方法是RL中使用最广泛的，因为他们比较简洁、可以在线更新、计算量小。上述的内容都是单步的、表格式的无模型TD算法。
当TD方法引入值函数近似，就和深度学习神经网络发生联系，例如Q-learning与DQN，Double Q-learning与Double DQN等等。
上述内容主要参考《Reinforcement Learning An Introduction》一书。
