第6章 时序差分学习¶
6.1 TD预测¶
TD和蒙特卡罗方法都使用经验来解决预测问题。对于基于策略 \(\pi\) 的一些经验，
两种方法都更新了他们对该经验中发生的非终结状态 \(S_t\) 的 \(v_\pi\) 的估计 \(V\)。
粗略地说，蒙特卡罗方法一直等到访问后的回报已知，然后使用该回报作为 \(V(S_t)\) 的目标。
适用于非平稳环境的简单的每次访问蒙特卡罗方法是
(1)¶\[V(S_{t}) \leftarrow V(S_{t})+\alpha\left[ G_{t}-V(S_{t})\right]\]
其中 \(G_t\) 是跟随时间t的实际回报，\(\alpha\) 是一个恒定的步长参数（参见方程2.4）。
我们将此方法称为恒定 \(\alpha\) MC。
蒙特卡罗方法必须等到回合结束才能确定 \(V(S_t)\) 的增量（这时只有 \(G_t\) 已知），
TD方法需要等到下一个时间步。 在时间 \(t+1\)，它们立即形成目标并
使用观察到的奖励 \(R_{t+1}\) 进行有用的更新。
最简单的TD方法立即进行更新
(2)¶\[V(S_{t}) \leftarrow V(S_{t})+\alpha\left[R_{t+1}+\gamma V(S_{t+1})-V(S_{t})\right]\]
过渡到 \(S_{t+1}\) 并接收 \(R_{t+1}\)。
在实际中，蒙特卡洛更新的目标是 \(G_t\)，而TD更新的目标是 \(R_{t+1} + \gamma V(S_{t+1})\)。
这种TD方法称为 TD(0) 或 一步TD，因为它是第12章和第7章中开发的 TD(\(\lambda\))和n步TD方法的特例。
下面的方框完全以程序形式给出了TD(0)。
表格TD(0)估计 \(v_\pi\)
输入：要评估策略 \(\pi\)
算法参数：步长 \(\alpha in (0,1]\)
对所有 \(s \in \mathbb{S}^{+}\)，除了 \(V(终点)=0\)，任意初始化 \(V(s)\)
对每个回合循环：
初始化 \(S\)
对回合的每一步循环：
\(A \leftarrow\) 由 \(\pi\) 给出 \(S\) 的动作
采取动作 \(A\)，观察 \(R\)，\(S^{\prime}\)
\(V(S) \leftarrow V(S)+\alpha\left[R+\gamma V(S^{\prime})-V(S)\right]\)
\(S \leftarrow S^{\prime}\)
直到 \(S\) 是终点
因为TD(0)部分基于现有估计进行更新，所以我们说它是一种 自举（bootstrapping） 方法，就像DP一样。
我们从第3章知道
\[\begin{split}\begin{aligned}
v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] (6.3)\\
&=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] & (由(3.9))\\
&=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] (6.4)
\end{aligned}\end{split}\]
粗略地说，蒙特卡罗方法使用（6.3）的估计作为目标，而DP方法使用（6.4）的估计作为目标。
蒙特卡洛目标是估计，因为（6.3）中的预期值未知；使用样本回报来代替实际预期回报。
DP目标是一个估计，不是因为完全由环境模型提供的预期值，而是因为 \(v_{\pi}(S_{t+1})\) 未知，
且使用当前估计值 \(V(S_{t+1})\) 来代替。
TD目标是估计原因有两个：它在（6.4）中对预期值进行采样，并 使用当前估计值 \(V\) 而不是真实 \(v_\pi\)。
因此，TD方法将蒙特卡罗的采样与DP的自举相结合。
正如我们将要看到的那样，通过谨慎和想象，这将使我们在获得蒙特卡罗和DP方法的优势方面走得很远。
右侧是表格TD(0)的备份图。
备份图顶部的状态节点的值估计基于从它到紧接的状态的一个样本转换而更新。
我们将TD和蒙特卡洛更新称为样本更新，因为它们涉及展望样本后继状态（或状态-动作对），
使用后继值和相应的奖励来计算备份值（?），然后相应地更新原始状态（或状态-动作对）的值。
样本 更新与DP方法的 预期 更新不同，因为它们基于单个样本后继，而不是基于所有可能后继的完整分布。
最后，请注意在TD(0)更新中，括号中的数量是一种误差，
衡量 \(S_t\) 的估计值与更好的估计 \(R_{t+1} + \gamma V(S_{t+1})\) 之间的差异。
这个数量称为 TD误差，在整个强化学习过程中以各种形式出现：
(3)¶\[\delta_{t} \doteq R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\]
请注意，每次TD误差都是 当时估算 的误差。因为TD误差取决于下一个状态和下一个奖励，所以直到一个步骤之后才可用。
也就是说，\(\delta_{t}\) 是 \(V(S_{t+1})\) 中的误差，在时间 \(t+1\) 可用。
还要注意，如果列表 \(V\) 在回合期间没有改变（因为它不是蒙特卡罗方法(?)），那么蒙特卡罗误差可以写成TD误差的和：
\[\begin{split}\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) & (由(3.9)) \\
&=\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} (6.6)
\end{aligned}\end{split}\]
如果在回合期间更新 \(V\) （因为它在TD(0)中），则此恒等式不准确，但如果步长很小，那么它可能仍然保持近似。
这种恒等式的一般化在时序差分学习的理论和算法中起着重要作用。
练习6.1 如果 \(V\) 在回合中发生变化，那么（6.6）只能保持近似；等式两边的区别是什么？
设 \(V_t\) 表示在TD误差（6.5）和TD更新（6.2）中在时间 \(t\) 使用的状态值列表。
重做上面的推导以确定必须添加到TD误差总和的额外量，以便等于蒙特卡罗误差。
例 6.1 开车回家 每天下班回家后，你都会尝试预测回家需要多长时间。
当你离开办公室时，你会记下时间，星期几，天气以及其他可能相关的内容。
这个星期五你正好在6点钟离开，你估计要回家需要30分钟。当你到达你的车是6:05，你注意到开始下雨了。
在雨中交通通常较慢，所以你需要花费35分钟，或者总共40分钟。十五分钟后，你及时完成了旅程的高速公路部分。
当你驶出高速进入第二部分道路时，你将总旅行时间的估计值减少到35分钟。
不幸的是，此时你被困在一辆慢卡车后面，而且道路太窄而无法通过。
你最终不得不跟随卡车，直到6:40你转到住的小街。三分钟后你就回家了。因此，状态，时间和预测的顺序如下：
状态
经过时间（分钟）
预测到的时间
预计总时间
周五6点离开办公室
0
30
30
到达车，下雨
5
35
40
驶出高速公路
20
15
35
第二条路，在卡车后面
30
10
40
进入家的街道
40
3
43
到家
43
0
43
这个例子中的奖励是旅程每一段的经过时间 [1]。我们不打折（\(\gamma=1\)），因此每个状态的回报是从该状态开始的实际时间。
每个状态的价值是 预期的 时间。第二列数字给出了遇到的每个状态的当前估计值。
查看蒙特卡罗方法操作的一种简单方法是绘制序列上预测的总时间（最后一列），如图6.1（左）所示。
红色箭头表示常量 \(\alpha\) MC方法（6.1）推荐的预测变化，其中 \(\alpha=1\)。
这些正是每个状态的估计值（预测的行走时间）与实际返回（实际时间）之间的误差。
例如，当你离开高速公路时，你认为回家仅需15分钟，但实际上需要23分钟。
公式6.1适用于此点，并确定驶出公路后的估计时间的增量。
误差 \(G_t - V(S_t)\) 此时为8分钟。假设步长参数 \(\alpha\) 为 \(1/2\)。
然后，由于这种经验，退出高速公路后的预计时间将向上修改四分钟。
在这种情况下，这可能是一个太大的变化；卡车可能只是一个不幸的中断。
无论如何，只有在你到家之后才能进行变更。只有在这一点上你才知道任何实际的回报。
图6.1 通过蒙特卡罗方法（左）和TD方法（右）在开车回家示例中推荐的变化。
在学习开始之前，是否有必要等到最终结果已知？
假设在另一天你再次估计离开你的办公室时需要30分钟才能开车回家，但是你会陷入大规模的交通堵塞之中。
离开办公室后二十五分钟，你仍然在高速公路上等待。你现在估计还需要25分钟才能回家，共计50分钟。
当你在车流中等待时，你已经知道你最初估计的30分钟过于乐观了。
你必须等到回家才增加对初始状态的估计吗？根据蒙特卡罗的方法，你必须，因为你还不知道真正的回报。
另一方面，根据TD方法，你可以立即学习，将初始估计值从30分钟转移到50分。
事实上，每个估计值都会转移到紧随其后的估计值。
回到驾驶的第一天，图6.1（右）显示了TD规则（6.2）推荐的预测变化
（如果 \(\alpha=1\)，这些是规则所做的更改）。
每个误差与预测随时间的变化成比例，即与预测的 时序差分 成比例。
除了在车流中等待你做点什么之外，还有几个计算原因可以解释为什么根据你当前的预测学习是有利的，
而不是等到你知道实际回报时才终止。我们将在下一节简要讨论其中的一些内容。
练习6.2 这是一个练习，以帮助你发展直觉，了解为什么TD方法通常比蒙特卡罗方法更有效。
考虑开车回家示例以及如何通过TD和蒙特卡罗方法解决它。你能想象一个TD更新平均比蒙特卡罗更新更好的情景吗？
举一个示例场景 - 过去经验和当前状态的描述 - 你期望TD更新更好。这里有一个提示：假设你有很多下班开车回家的经验。
然后你搬到一个新的建筑物和一个新的停车场（但你仍然在同一个地方进入高速公路）。现在你开始学习新建筑的预测。
在这种情况下，你能看出为什么TD更新可能会好得多，至少初始是这样吗？在原始场景中发生同样的事情可能吗？