时序差分（temporal difference，TD）学习是强化学习最核心和流行的方法。TD学习结合了MC和DP的思想，既类似蒙特卡洛（Monte Carlo，MC）方法直接从交互经验中学习而不需要获得环境动态信息，又类似动态规划（Dynamic Programming, DP）方法利用其他状态的估计更新状态价值而不需要完成一轮交互后才更新。
1.TD预测
回顾一下MC方法，一个每次访问MC方法应用于非静态问题。给定策略\(\pi\)，当完成一轮交互后，根据采样得到的回报回溯计算每个状态的回报\(G_t\)，并更新其状态价值\(V(S_t)\)：
\[V(S_t)\leftarrow V(S_t)+\alpha[G_t-V(S_t)],
\]
上述更新方式也被称为定步长MC（constant-\(\alpha\) MC）方法，MC方法必须等到一轮交互结束后才能进行更新。TD方法采样自举（bootstrap）方式每一步都可以更新价值函数。最简单的TD更新方法为
\[V(S_t)\leftarrow V(S_t) + \alpha\left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right]
\]
这个方法也被称为TD(0)或单步TD法。其中，\(R_{t+1}+\gamma V(S_{t+1})\)为用于更新的目标（target）值。下面给出单步TD法的伪代码。
TD方法的状态价值更新是基于估计值，因此它是一种自举的方法：
\[\begin{eqnarray*}
v_\pi(s)&:=&E_\pi[G_t|S_t=s]\\
&=&E_\pi[R_t+\gamma G_{t+1}|S_t=s]\\
&=&E_\pi[R_t+\gamma v_\pi(S_{t+1})|S_t=s]
\end{eqnarray*}
\]
根据上式可以看出，TD方法将蒙特卡洛采样方法和动态规划的自举方法相结合。定义TD误差为
\[\delta_t:=R_{t+1}+\gamma V(S_{t+1})-V(S_t)
\]
假设状态价值函数在一轮交互中不发生变化，蒙特卡洛误差\(G_t-V(S_t)\)可以写成TD误差累加和的形式：
\[\begin{eqnarray*}
G_t-V(S_t)&=&R_{t+1}+\gamma G_{t+1}-V(S_t)+\gamma V(S_{t+1})-\gamma V(S_{t+1})\\
&=&\delta_t+\gamma (G_{t+1}-V(S_{t+1}))\\
&=&\delta_t+\delta_{t+1}+\gamma^2 (G_{t+2}-V(S_{t+2}))\\
&=&\delta_t+\delta_{t+1}+\cdots+\gamma^{T-t-1}\delta_{T-1}+\gamma^{T-t}(G_T-V(S_T))\\
&=&\sum_{k=t}^{T-1}\gamma^{k-t}\delta_k
\end{eqnarray*}
\]
上述假设往往不成立，但是当学习率\(\alpha\)比较小时，近似成立。
综上，TD方法不需要获得环境的动态信息，另外它采用的是逐步更新的方式。相比于MC方法，TD方法只需要考虑一次状态转移，每一次的状态转移可以看作为一个样本，而不需要将完整的一轮交互都纳入考量。因此，TD方法往往具有更好的灵活性，且收敛速度较快。
下面仔细考虑一下MC方法和TD方法的不同计算方法对状态价值估计的影响。考虑存在三个状态A、B和C，假设学习率\(\alpha=1\)，折扣系数\(\gamma=1\)，所有状态价值初始化为0，过程奖励为0，只有到达终止点奖励为1。经过一轮交互，产生交互轨迹\(A\rightarrow B\rightarrow C\rightarrow 终点(r=1)\) 。若采用TD(0)方法，只有状态C的状态价值发生改变\(V(s=C)=1\)，而采用MC方法三个状态的状态价值都会变为1。
2. TD(0)的最优性
假设根据收集一批数据之后更新值函数，这种方法就被称为批量更新（batch updating）。TD(0)和MC都会在批量更新的情况下收敛，但是两者会收敛到不同的值。
考虑一个例子，假设进行了8轮交互，得到8条交互轨迹为
\[\begin{eqnarray*}
\begin{array}{l}
A,0,B,0 && B,1 && B,1 && B,1\\
B,1 && B,1 && B,1 && B,0
\end{array}
\end{eqnarray*}
\]
表示第一次交互从状态A开始过渡到B得到奖励0，然后从B到结束状态得到奖励0。其他七次交互轨迹则更短，从B开始，立即结束。给定这批数据，你认为状态价值估计值\(V(A)\)和\(V(B)\)的最佳值是什么？
当采用MC方法，每个状态的采样回报都是独立的。状态A的样本只有一个回报为0，状态B的样本有8个，其中2个回报为0，其余样本回报为1。因此得到\(V(A)=0\)和\(V(B)=3/4\)。而采用TD(0)方法，状态A的样本是基于状态B的估计值，因此得到\(V(A)=V(B)=3/4\)。
这个例子再次展示了MC方法与TD方法的不同之处。MC方法的批量更新总是去求解最小化训练集均方误差的解，但是TD方法的批量更新则是去寻找训练集的马尔可夫过程的最大似然模型。TD的这种估计方式也被称为确定性等价估计（certainty-equivalence estimate），也就是说TD收敛于确定性等价估计。这也可以帮助解释TD收敛的速度比MC快的原因。但值得注意的是，尽管确定性等价估计在某种意义上是一个最优解，但直接计算它几乎是不可行的。假设状态空间大小为\(n=|\mathcal{S}|\)，直接计算环境模型则需要存储\(n^2\)的转移信息，计算量还要更大。而采用TD算法来获取近似解，其存储空间仅需O(n)。因此，目前TD方法是处理大型状态空间问题中唯一的确定性等价估计方法。
3. Sarsa：在线TD控制
控制问题采用广义策略迭代（GPI）的思路。考虑在给定策略\(\pi\)下估计状态-动作价值函数\(q_\pi(s,a)\)，首先在一轮交互内的状态-动作对：
将其应用于TD算法中，可得
\[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)]
\]
在每次交互的状态转移之后进行更新，其中\(S_t\)应该是非终止状态。当\(S_{t+1}\)为终止状态，则\(Q(S_{t+1},A_{t+1})=0\)。将一次交互中的五个元素作为一个样本\((S_t,A_t,R_{t+1},S_{t+1},A_{t+1})\)，这就是Sarsa算法。作为在线策略方法，每次交互后都会重新估计\(q_\pi\)，并且根据\(q_\pi\)采用\(\epsilon\)-greedy方法更新最优策略\(\pi\)。下面给出Sarsa算法的伪代码。
这里需要注意，为了保证持续性探索，在动作选择的过程中需要采用随机策略，在探索和挖掘之间寻找平衡。随着交互次数的不断增加，逐渐减少\(\epsilon\)值，使\(\pi\)逐渐靠近最优策略。
4. Q-learning：离线TD控制
Q-learning的更新形式与Sarsa非常类似：
\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\max_a Q(S_{t+1},a)-Q(S_t,A_t)]
\]
在这种情况下，学习的状态-动作价值函数\(Q\)直接近似于\(q_*\)最优状态-动作价值函数，独立于交互策略。这也就使得它被称为了离线策略方法。但是，要保证Q-learning正确收敛需要所有的状态-动作对都得到持续的更新。下面给出Q-learning算法的伪代码。
这里需要注意，为了保证持续性探索，在动作选择的过程中需要采用随机策略例如\(\epsilon\)-greedy方法。
5*. 期望Sarsa
Q-learning算法采用最大值作为目标，容易造成过估计。期望Sarsa将最大值替换为状态-动作价值的期望更新价值函数：
\[\begin{eqnarray*}
Q(S_t,A_t)&\leftarrow& Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\mathbb{E}[Q(S_{t+1},A_{t+1})|S_{t+1}]-Q(S_t,A_t)]\\
&\leftarrow& Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\sum_a\pi(a|S_{t+1})Q(S_{t+1},a)-Q(S_t,A_t)]
\end{eqnarray*}
\]
期望Sarsa需要更多的计算量，但是带来的好处是有效减小的方差，相比于Sarsa不再需要随机选取动作\(A_{t+1}\)。一般来说，期望Sarsa的算法优于Sarsa和Q-learning，而且对于学习率\(\alpha\)的变化具有更好的鲁棒性。
6. 最大化偏差与双重学习（double learning）
在Q-learning中，通常会倾向于高估状态-动作价值函数，因为更新公式用到了取最大值。这往往会带来显著的正向偏差，也称为最大化偏差（maximization bias）。其原因在于，Q-learning算法利用同一个样本在估计状态-动作价值的最大值的同时，还在选取价值最大的动作作为最优策略。类似于正反馈，这样过高的估计错误的动作，使得算法的估计值波动较大。
为了解决这个问题，在不增加样本的情况下，可以引入两个状态-动作价值函数\(Q_1\)和\(Q_2\)分别独立估计状态-动作价值。例如当\(Q_1\)来估计价值最大的动作\(A^*=\arg\max_aQ_1(s,a)\)时，那么\(Q_2\)则用于提供状态-动作价值的最大值估计\(Q_2(s,A^*)=Q_2(s,\arg\max_aQ_1(s,a))\)，反之亦然。这种更新方式是无偏的，也被称为双重学习。需要注意的是尽管我们利用两个\(Q_i\)函数进行学习，但每次只更新一个\(Q_i\)函数。因此，计算量并没有增加，存储量翻倍了。在实际实现过程中可以采用随机的方式来交替更新，例如\(Q_1(S_t,A_t)\)的更新，
\[Q_1(S_t,A_t)\leftarrow Q_1(S_t,A_t)+\alpha[R_{t+1}+\gamma Q_2\left(S_{t+1},\arg\max_aQ_1(S_{t+1},a)\right)-Q_1(S_t,A_t)]
\]
Double Q-learning算法的伪代码如下。
值得注意的是，在进行交互的过程中，采用随机策略\(\epsilon\)-greedy算法基于状态-动作价值函数\(Q_1+Q_2\)。显然，在随机估计的过程中，\(Q_1+Q_2\)优于任何单一的\(Q_i\)。
7. 博弈/游戏、后状态与其他特例
前面介绍的是一类通用的学习状态-动作价值的方法，但是总是存在一些特殊的情况可以采用针对性方式得到更好的处理。例如井字棋的游戏，与其采用状态-动作价值函数的学习，不如状态价值函数的学习。因为不同的动作次序会得到相同的状态，如下图所示。传统的学习算法根据\(Q(S_t,A_t)\)确定下一步动作，但井字棋则不同，它是评估智能体下棋之后的状态\(V(S_{t+1})\)来确定最优动作，称为后状态（afterstates），其状态价值函数被称为后状态值函数。
后状态价值函数的好处就在于我们只需要知道环境初始状态的动态信息，而不需要知道整个环境的动态信息。例如在博弈游戏中，我们只需要知道所采取动作所产生的影响，而不需要考虑对手的反应。传统的动作价值函数通过动作和状态来确定价值，但是很多状态-动作对会产生相同的状态，因此不同的状态-动作对应该有相同的价值。但传统方法会将这些状态-动作对独立对待，而后状态价函数则会等价看待它们，当得到一个状态-动作对的估计，则更新所有与其具有相同的后状态的状态-动作对的价值。
8. 小结
本节学习了最基本的TD算法，还是依靠GPI的思路来解决问题。最基本的算法有Sarsa，Q-learning和更复杂一些的期望Sarsa。其中Sarsa是在线更新的，而Q-learning是离线更新的。在接下来几章中我们会介绍更复杂的TD算法，它们在应用中也更加强大。
9.实验
实验1：Random Walk 预测问题
考虑一个马尔可夫奖励过程（Markov reward process, MRP），每轮交互都从中心状态\(C\)开始，每个状态可以随机选择向左或者向右两种动作，两个动作的选择概率为50%。每轮交互的结束状态位于最左端和最右端，当且仅当智能体到达最右端才能获得奖励\(R=+1\)，其他状态转移的奖励均为\(R=0\)。例如，产生的一轮交互轨迹为\(C,0,B,0,C,0,D,0,E,1\)。在等概率的随机策略\(\pi\)下，状态\(A\)到\(E\)的状态价值分别为\(v_\pi(s)=\frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6}\)。
现分别利用\(TD(0)\)算法和定步长蒙特卡洛算法估计\(v_\pi(s)\)。实验主要展示了100轮交互的状态价值估计的收敛情况，折扣系数\(\gamma=1\)，初始状态\(v_\pi(s)=0.5\)。为了保证实验的一般性，对每个步长\(\alpha\)重复进行100次实验，取其均值。对于TD(0)算法而言，其核心式子在于
\[V_\pi(S_{t}) = V_\pi(S_{t}) + \alpha\left(R_{t+1}+\gamma V_\pi(S_{t+1})-V_\pi(S_t)\right)
\]
对于MC算法而言，其核心式子在于
\[V_\pi(S_t)=V_\pi(S_t)+\alpha(G_t-V_\pi(S_t))
\]
具体代码参照随书代码random_walk.py。仿真结果如下图所示。
左图展示了TD(0)算法在\(\alpha=0.1\)的情况下，经过一次实验，状态价值估计随交互轮数的增加，估计值逐渐趋近于真实值。右图展示了不同学习率下，TD(0)算法和MC算法的收敛情况。可以看出TD(0)方法的收敛速度优于MC方法。
下面再测试一下，两个算法对于步长选择范围的敏感性。
从上图可以看出，相比于MC算法，TD算法对于步长的选择具有更大的宽度。学习率\(\alpha\)过小会影响收敛速率，但更不宜偏大使得算法无法收敛到真实值。值得注意的是TD算法出现反弹的情况，即估计值由好逐渐变差，学习率越大这个现象越明显。原因在于TD算法采用的是自举的更新方式，即
\[\begin{eqnarray*}
V_\pi(S_{t}) &\leftarrow& V_\pi(S_{t}) + \alpha\left(R_{t+1}+\gamma V_\pi(S_{t+1})-V_\pi(S_t)\right)\\
&\leftarrow& (1-\alpha)V_\pi(S_t)+\alpha(R_{t+1}+\gamma V_\pi(S_{t+1}))
\end{eqnarray*}
\]
当\(\alpha\)越大，估计值越容易受到当前采样数据的影响，而\(V_\pi(S_{t+1})\)的估计不准确会导致\(V_\pi(S_t)\)的更新也不准确。而一开始的估计误差不断减小，其原因在于，终止状态附近的状态估计值得到了改善。而MC算法没有这样的问题，因为MC算法的回报\(G_t\)采样是独立的，当学习率\(\alpha\)较大，受到\(G_t\)的方差影响较大。
（扩展）实验1：Random Walk -- batch update
前面的实验1采用的是逐样本更新的方式，可以理解为实时更新。本实验将采用批量更新的方式，每进行一轮交互采集一批数据，交互过程中并不更新状态估计，然后将所有交互数据利用TD算法和MC算法进行多次迭代更新，直到估计值收敛，然后在进行下一轮交互。与前面的实验1相比，其最大的区别在于，采样得到的数据被多次用于更新状态估计。批量更新所采用的学习率需要比较小以保证其收敛于真值，实验中取\(\alpha=0.001\)。其实验结果如下图所示。
对比于实时更新方式，批量更新方法的计算量会大大增加。但从曲线梯度变化可以明显看出其收敛速度也大大增加。最后收敛到误差的界限是一致的。当交互次数有限时，批量更新方法更具有优势。在实验过程中，批量更新方法对学习率比较敏感，当学习率非常小时，其效果不如MC方法。
实验2：Windy Gridworld 控制问题
下面的插图是一个标准的网格世界，有起点状态\(S\)和终点状态\(G\)，但有一个区别：有一股侧风从网格中间向上吹。智能体有四个标准动作：向上、向下、向右和向左。在中间区域，产生的下一个状态通过“风”向上移动，“风”的强度标注在每一列的最下方，给出向上移动的单元格数。例如，如果你的目标是右侧的单元格，那么向左的动作会将你带到目标上方的单元格。智能体在达到目标状态之前，每次动作的奖励为−1。
本次实验利用Sarsa算法寻找最优策略，以最快的速度到达目标点。交互策略采用\(\epsilon\)-greedy方法，其中初始化参数的选择为\(\epsilon=0.1\)，\(\alpha=0.5\)，初始状态-动作价值为\(Q(s,a)=0\)。
小技巧：在程序实现过程中，当某个状态存在多个动作都是贪婪动作时，随机进行选择。若代码中采用np.argmax(values)这样并不正确，每次只能采用贪婪动作中编号最小的。而np.random.choice([action_ for action_, value_ in enumerate(values_) if value_==np.max(values_)])才是真正随机选择贪婪动作。
具体代码参照随书代码windy_grid_world.py。仿真结果如下图所示。
从图中可以看出随着交互次数的增加，每轮交互次数越来越少，逐渐达到最优策略（通过观察曲线梯度变化）。这里采用了固定的探索概率。如果采用前期加大探索的力度，然后逐渐加大挖掘的力度，可以更快找到最优策略。针对此想法，设定最初的\(\epsilon=1\)，经过4000步交互均匀衰减至\(\epsilon=0.1\)。仿真结果如下。
可以看出采用exploration-exploitation均衡策略可以帮助智能体更快找到最优策略。同时，获得的最优策略与前面的有很大的不同，原因在于本实验采用的是固定起始点和目标点，因此较早找到最优策略后，与之无关的状态被访问的概率就大大降低了，无法得到正确的策略。
实验3：cliff Walking 控制问题
考虑一个网格世界如下图所示。本实验比较了Sarsa和Q学习，探究在线策略（Sarsa）和离线策略（Q-learning）方法之间的区别。该网格世界有起始状态\(S\)和目标状态\(G\)，智能体可选的动作为上、下、右和左移动。除了进入标有“悬崖”的区域外，所有状态转移的奖励都是\(−1\)。进入该区域会获得\(R=−100\)的奖励，并立即将智能体送回起点。
实验过程中采用\(\epsilon\)-greedy策略进行探索，超参数选择为\(\epsilon=0.1\)，\(\gamma=1\)，\(\alpha=0.5\)。具体代码参照随书代码cliff_walking.py。实验结果如下图所示。
虽然Sarsa算法的平均累计奖励优于Q-learning算法，但是Q-learning算法找到了一条最优路径。其原因在于，Sarsa算法是根据随机策略进行学习，因此学习得到的最安全的路径（虽然远但是掉落悬崖的概率最低）；但是Q-learning算法是基于贪婪动作进行学习，因此学习得到最优路径。当\(\epsilon\)逐渐趋向于0，则两种算法都收敛于最优策略。
（扩展）实验3：cliff Walking
同样根据实验3的条件，现考量Sarsa算法、Expected Sarsa算法和Q-learning算法对于学习率\(\alpha\)的敏感性。这里需要注意的是Expected Sarsa算法的目标状态为\(\sum_a\pi(a|S_{t+1})Q(S_{t+1},a)\)，当存在多个贪婪动作时，每个贪婪动作的概率为
\[\frac{1-\epsilon}{可选贪婪动作数量}+\frac{\epsilon}{|A|}
\]
其中\(|A|\)表示所有可选动作的数量。为了保证实验的一般性，三种算法针对每个学习率进行1000轮交互，重复运行10次，取均值（收敛性能）。并展示了不同学习率下三个算法在前100轮的交互下的表现（瞬时表现）。仿真结果如下图所示。
从图中可以看出来，Expected Sarsa算法和Q-learning算法对学习率具有很好的适用范围。Expected Sarsa算法的表现明显优于其他两种算法。
实验四：最大化偏差
考虑模型如下图所示。该模型总共包含两个非结束状态\(A\)和\(B\)。每轮交互总是从状态\(A\)开始，在状态\(A\)智能体可以选择向左和向右，在状态\(B\)可以有多个动作到达最左端终止状态。最右侧的结束状态获得的奖励为0，而最左侧的结束状态获得的奖励满足均值为-0.1，方差为1的正太分布。
这里分别采用Q-learning算法和double Q-learning算法学习最优策略。超参数设置分别为\(\epsilon=0.1\)，\(\gamma=1\)，\(\alpha=0.1\)。在代码实现过程中运用了一些小技巧来简化实现，因为模型较为简单，因此可以直接定义状态转移列表、动作选择列表以及与之对应的状态-动作价值列表：
STATE_A = 0 # state A
STATE_B = 1 # state B
STATE_TERMINAL = 2 # use one terminal state
# possible actions in A
ACTION_A_RIGHT = 0
ACTION_A_LEFT = 1
# possible actions in B, maybe 10 actions
ACTIONS_B = range(0, 10)
# all possible actions
STATE_ACTIONS = [[ACTION_A_RIGHT, ACTION_A_LEFT], ACTIONS_B]
# state action pair values, if a state is a terminal state, then the value is always 0
INITIAL_Q = [np.zeros(2), np.zeros(len(ACTIONS_B)), np.zeros(1)]
# set up destination for each state and each action
TRANSITION = [[STATE_TERMINAL, STATE_B], [STATE_TERMINAL] * len(ACTIONS_B)]
上述定义的好处，例如TRANSITION[STATE_A][ACTION_A_RIGHT]实现状态\(A\)通过动作向右得到下一时刻状态STATE_TERMINAL。具体代码参照随书代码maximization_bias.py。实验结果如下图所示。
从图中可以看出Q-learning算法存在最大化偏差的问题，一旦估计值受到最大值影响需要较长时间才能恢复过来。相比之下，Double Q-learning算法几乎不受影响。