
\chapter{第六章 Temporal-Difference学习}

\begin{summary}
	如果要强化学习，就必须把一个想法确定为中心和新颖的，那无疑就是时间性差异(TD)学习。TD学习是蒙特卡罗思想和动态规划思想的结合。像蒙特卡罗方法一样，TD方法可以直接从原始经验中学习，而不需要环境动力学模型。像DP一样，TD方法更新估计部分基于其他学习的估计，而不需要等待最终结果(它们是自启动的)。在强化学习理论中，TD、DP和蒙特卡罗方法之间的关系是一个反复出现的主题;这一章是我们对它的探索的开始。在我们完成之前，我们将看到这些想法和方法相互融合，可以以多种方式组合在一起。特别是,在第七章我们介绍n-step算法,提供一个桥梁从TD蒙特卡罗方法,在第十二章我们介绍了TD(λ)算法,它无缝地结合。
	像往常一样,我们首先关注政策评估或预测问题,估计价值函数的问题vππ为给定的政策。对于控制问题(寻找最优策略)，DP、TD和蒙特卡罗方法都使用广义策略迭代(GPI)的一些变化。方法上的差异主要是预测问题方法上的差异。
\end{summary}

\section{TD预测}
TD和蒙特卡罗方法都利用经验来解决预测问题。给出一些经验后政策π,两种方法更新他们的估计V vπ的非终结符州圣发生在体验。粗略地说，蒙特卡罗方法要等到访问结束后返回，然后使用该返回作为V (St)的目标。一种适用于非平稳环境的简单的every-visit蒙特卡罗方法。
V(St)←(St)+α
Gt−V(St)
, 					(6.1)
Gt是实际返回时间t后,和α是一个恒定的步长参数(出口的。,方程2.4)。让我们调用这个方法constant-αMC。而蒙特卡罗方法必须等到结束的事件来确定增量V(St)(只有Gt),TD方法需要等待直到下一个时间步。在t+1时刻，他们立即形成一个目标，利用观察到的奖励Rt+1和估计值V (St+1)进行有用的更新。最简单的TD方法进行更新

V(St)←(St)+α

Rt + 1 +γV(圣+ 1)−V(St)

(6.2)

立即过渡到St+1并接收Rt+1。实际上,蒙特卡洛更新Gt的目标,而目标TD更新Rt + 1 +γV(圣+ 1)。这个TD方法叫做TD(0),或一步TD,因为它是一个特例的TD(λ)和n-step TD方法开发的第十二章和第七章。下面的框以过程的形式指定TD(0)。
 

因为TD(0)的更新部分基于现有的估计，所以我们说它是一种引导方法，就像DP一样。从第三章我们知道

vπ(年代)。= Eπ[Gt |圣= s] 					(6.3)
= Eπ[Rt + 1 +γGt + 1 |圣= s] 					(从(3.9))
= Eπ[Rt + 1 +γvπ(圣+ 1)|圣= s]。 					(6.4)
粗略地说，蒙特卡罗方法以(6.3)估计值为目标，而DP方法以(6.4)估计值为目标。蒙特卡罗目标是一个估计，因为(6.3)中的期望值未知;示例返回用于替代实际期望返回。DP的目标是估计不是因为预期值,这是假定为完全的模型所提供的环境,而是因为vπ(圣+ 1)是未知的和当前估计,V(圣+ 1),而不是使用。TD的目标是估计有两个原因:它样品预期值(6.4),它使用当前估计代替真正的vπV。因此，TD方法结合了采样。

蒙特卡洛与DP的bootstrapping。正如我们将看到的，只要小心和想象，这将使我们在获得蒙特卡罗和DP方法的优点方面取得很大的进展。
TD(0)
右边显示的是表格式TD(0)的备份图。在备份图顶部的状态节点的值估计是基于从它到下一个状态的一个示例转换而更新的。我们称TD和蒙特卡罗更新为样本更新,因为它们涉及展望一个样本的继任者状态(或政府行动对),使用的继任者的价值和奖励来计算一个备份值,然后更新初始状态的值(或状态-动作对)。示例更新与预期的更新不同
在DP方法中，它们基于一个样本继承，而不是所有可能继承的完整分布。
最后,请注意,TD的数量在括号中(0)更新是一种错误,测量圣的估计价值的区别和更好地估计Rt + 1 +γV(圣+ 1)。这个量，被称为TD误差，在强化学习中以各种形式出现:
δt。= Rt + 1 +γV(圣+ 1)−V(St)。 					(6.5)
请注意，每次的TD错误都是当时估计的错误。因为TD错误依赖于下一个状态和下一个奖励，实际上直到一个时间步骤之后它才可用。即δt V(St)的错误,可以在时间t + 1。还要注意，如果数组V在这一集中没有变化(在蒙特卡罗方法中没有变化)，那么蒙特卡罗误差可以写成TD误差之和:
Gt−V(St)= Rt + 1 +γGt + 1−V(St)+γV(圣+ 1)−γV(圣+ 1)(从(3.9))
=δt +γ
Gt  1−V(圣+ 1)?
=δt +γδt + 1 +γ2
Gt + 2−V(圣+ 2)?
=δt +γδt + 1 +γ2δt + 2 +···+γT t−−1δt−1 +γT−t

GT−V(ST)?
=δt +γδt + 1 +γ2δt + 2 +···+γT t−−1δt−1 +γT−t

−0

γk−tδk。 					(6.6)

如果V在事件期间更新(如TD(0)))，则该标识并不准确，但是如果步骤大小很小，那么它仍然可以保持大约。这种同一性的归纳在时变学习的理论和算法中起着重要的作用。
练习6.1如果V在发作过程中发生变化，那么(6.6)只能保持大约;两者之间的区别是什么?让Vt表示在TD错误(6.5)和TD更新(6.2)中所使用的状态值的数组。重新进行上面的推导，以确定必须添加到TD错误总和中的额外金额
为了等于蒙特卡罗误差。 					?

例6.1:每天下班开车回家，你试着预测回家需要多长时间。当你离开办公室时，你会注意到时间、星期、天气以及其他可能相关的事情。假设这个星期五你正好6点离开，你估计要花30分钟才能到家。当你到达你的车时，已经是6:05了，你注意到开始下雨了。在下雨的时候，交通通常会比较慢，所以你要重新估计，从那时开始需要35分钟，或者总共需要40分钟。15分钟后，你已经按时完成了高速公路的部分。当你走到第二条路的时候，你会把估计的总旅行时间缩短到35分钟。不幸的是，此时你被卡在一辆缓慢的卡车后面，道路太窄，无法通过。你最终不得不跟着卡车走，直到你在6点40分拐到你住的那条小街。三分钟后你就到家了。状态、时间和预测的顺序如下:


国离局，周五6点到车，下出公路2ndary road，后面卡车进入家乡街道到达家	时间(分钟)0 5 20 30 40 43	预计时间30 35 15 10 30	预计总时间30 40 35 40 43
这个例子的回报是旅途中每一段经过的时间。1我们不是打折(γ= 1),从而换取每个状态是实际时间从状态。每个状态的值是期望的时间。数字的第二列给出遇到的每个状态的当前估计值。
观察蒙特卡罗方法的操作的一种简单方法是在序列上绘制预测的总时间(最后一列)，如图6.1(左)所示。红色箭头显示推荐的变化预测constant-αMC方法(6.1),α= 1。这些正是每个状态的估计值(预计时间)与实际回报(实际时间)之间的误差。例如，当你从高速公路上下来的时候，你以为回家只需要15分钟，但实际上却需要23分钟。公式6.1适用于这一点，并确定出高速公路后的时间估计增量。错误,Gt−V(St),在这个时间是8分钟。假设步长参数α,是1/2。然后，在这一经验的结果下，预计的离开高速公路的时间将被向上修正4分钟。这个变化可能太大了;那辆卡车很可能只是一次不幸的事故。无论如何，更改只能在离线状态下进行，也就是说，在您到达家之后。只有在这个时候你才知道实际的回报。
在开始学习之前，是否有必要等到最后的结果出来?假设有一天你再次估计离开办公室后开车回家需要30分钟，然后你陷入了严重的交通堵塞。离开办公室25分钟后，你仍在高速公路上颠簸前行。你现在

如果这是一个控制问题，目的是减少旅行时间，那么我们当然会这样做
让奖励成为过去时间的负值。但因为我们只关心这里
预测(政策评估)，我们可以用正数来保持简单。

情况 					情况


图6.1:蒙特卡罗方法在驾驶回家示例中建议的更改(左)
和TD方法(右)。



估计回家还需要25分钟，总共需要50分钟。当你在堵车时，你已经知道你最初估计的30分钟太过乐观了。你一定要等到回家后才增加初始状态的估计值吗?根据蒙特卡罗的方法，你必须这么做，因为你还不知道真正的回报。
另一方面，根据TD方法，你会立即学到东西，把最初的估计时间从30分钟改为50分钟。事实上，每一个估计都会被转移到紧随其后的估计。回到我们的第一天开车,图6.1(右)显示的变化预测推荐的TD规则(6.2)(这些是由规则的变化如果α= 1)。每个误差成正比的随时间变化的预测,预测的时间差异。
除了让您在等待流量时有一些事情要做之外，还有几个计算上的原因可以解释为什么基于当前的预测而不是等到知道实际的回报时才终止学习是有益的。我们将在下一节中简要讨论其中的一些问题。

练习6.2这是一个练习，可以帮助你对为什么TD方法比蒙特卡罗方法更有效的直觉。考虑驾车回家的例子，以及TD和蒙特卡罗方法如何解决这个问题。你能想象一种情况:TD更新比蒙特卡罗更新平均要好吗?给出一个示例场景——对过去经验的描述和当前状态的描述，您将期望TD更新更好。这里有一个提示:假设你有很多下班开车回家的经验。然后你搬到一个新的建筑和一个新的停车场(但你仍然在同一地点进入高速公路)。现在你开始学习对新建筑的预测了。你能明白为什么TD更新在这种情况下会更好吗?在原著中也可能发生同样的事情
场景吗? 					?

124年 					第六章:Temporal-Difference学习


\section{TD预测方法的优点}

TD方法更新他们的估计部分基于其他估计。他们从猜测中学习猜测——他们自己引导。这是一件好事吗?与蒙特卡罗和DP方法相比，TD方法有什么优势?开发和回答这些问题将占用本书的其余部分以及更多的时间。在本节中，我们简要地预测了一些答案。
显然，TD方法比DP方法有一个优势，因为它们不需要环境模型、奖励模型和下一个状态概率分布模型。
与蒙特卡罗方法相比，TD方法的下一个最明显的优点是它们自然地以一种在线的、完全增量的方式实现。使用蒙特卡罗方法时，必须等到一集结束时，因为只有那时才知道返回值，而使用TD方法时，只需要等待一个时间步骤。令人惊讶的是，这往往是一个关键的考虑。有些应用程序有很长的一段时间，所以延迟所有的学习直到这一集的结尾太慢。其他应用程序是持续的任务，根本没有发作。最后，正如我们在前一章中所提到的，一些蒙特卡罗方法必须忽略或忽略实验行为所发生的事件，这会极大地降低学习速度。TD方法不太容易受到这些问题的影响，因为它们从每次转换中学习，而不管后续采取什么操作。
但是TD方法是否可靠呢?当然，在不等待实际结果的情况下，从下一种猜测中学习一种猜测是很方便的，但我们能不能保证收敛到正确的答案呢?幸运的是，答案是肯定的。对于任何固定政策π,TD(0)已被证明收敛vπ,意味着一个常数的步长参数如果足够小,以概率1如果根据通常的步长参数减少随机近似条件(2.7)。大多数收敛证明只适用于上述算法的基于表的情况(6.2)，也有一些适用于一般线性函数逼近的情况。这些结果将在第9章的更一般的设置中讨论。
如果TD和蒙特卡罗方法都渐近地收敛于正确的预测，那么自然的下一个问题就是“谁先到达那里?”换句话说，哪种方法学得更快?怎样才能更有效地利用有限的数据?目前，这是一个悬而未决的问题，因为没有人能够从数学上证明一种方法比另一种方法收敛得更快。事实上，我们甚至不知道什么是表达这个问题最合适的正式方式!然而在实践中,TD方法通常被发现收敛速度比constant-αMC方法随机任务,见例6.2。

练习6.3从随机游动例子的左图中可以看出，第一集的结果只有V (a)的变化，这说明了第一集发生了什么?为什么只有这个状态的估计值?
改变了吗?它到底改变了多少? 					?
练习6.4具体成果图的随机漫步的例子所示的值依赖于步长参数,α。你觉得会影响算法的结论是更好的,如果是使用广泛的α值吗?有不同,固定值α,要么算法的表现吗
明显好于显示?为什么或为什么不呢? 					?
∗6.5运动图的随机漫步的例子中,TD的均方根误差方法似乎在下降,然后起来,特别是在高α。是什么导致了这种情况?你认为这种情况经常发生吗
近似值函数初始化? 					?
练习6.6在例子6.2中我们说过随机漫步例子的真实值是，
2

对于A到e的状态，描述至少两种不同的方式
这些是可以计算出来的。你猜我们实际上用的是什么?为什么??


\section{最优的TD(0)}
假设只有有限数量的经验，比如10集或100个时间步骤。在这种情况下，使用增量学习方法的常见方法是重复地呈现经验，直到方法收敛到一个答案。在给定一个近似值函数V的情况下，对于每次访问一个非终端状态的第t步，都要计算(6.1)或(6.2)指定的增量，但值函数只更改一次，以所有增量之和。然后使用新的值函数再次处理所有可用的经验，从而产生新的总体增量，以此类推，直到值函数收敛。我们称此批更新为批更新，因为只有在处理完每批培训数据之后才进行更新。
在批处理更新,TD(0)确定性收敛于一个回答独立于步长参数,α,只要选择α足够小。constant-αMC方法也收敛确定性在相同条件下,而是一个不同的答案。理解这两个答案将有助于我们理解这两种方法的区别。在正常的更新方法中，这些方法不会一直移动到它们各自的批次答案中，但在某种意义上，它们会在这些方向上采取步骤。在尝试理解这两个答案之前，我们先看几个例子。
例6.3:随机漫步在批处理更新分批更新版本的TD(0)和constant-αMC如下随机漫步预测例子(例如6.2)。在每一集之后，到目前为止看到的所有剧集都被当作一集来处理。他们一再提出的算法,TD(0)或constant-αMC,α值足够小,聚合函数。结果值函数然后与vπ相比,平均根均方误差在5个州(在100年独立重复整个实验)是获得绘制

如图6.2所示的学习曲线。注意，批处理TD方法始终优于批处理蒙特卡罗方法。

。0 0。
。实施率达1
。2为

0 25 50 75 100。
道明
MC
批处理培训

走/集
RMS误差，对状态求平均值

图6.2:TD(0)的性能和随机漫步constant-αMC下批培训任务。
下批培训,constant-αMC收敛于价值观,V(s),样本平均数的实际回报有经验在访问每个状态。这些都是最优估计,他们均方误差最小化训练集的实际回报。在这个意义上令人惊奇的是,一批TD方法能够根据根均方误差表现更好,右边的图所示。为什么批量TD能够比这种最优方法表现得更好?答案是蒙特卡罗方法只在有限的范围内是最优的。
以一种与预测回报更相关的方式，TD是最优的。
示例6.4:您现在是一个预测者，您将自己置于一个未知的马尔可夫回报过程的预测者的角色。假设你观察以下8集:

一个0 B,0 					B,1
B,1 					B,1
B,1 					B,1
B,1 					B,0

这意味着第一集从状态A开始，以0的奖励转移到B，然后以0的奖励从B结束。其他七集甚至更短，从B开始，立即结束。考虑到这批数据，你会说什么是最优预测，估计V (A)和V (B)的最佳值?每个人可能都同意，V (B)的最优值是3 4，因为在状态B中8次中有6次的进程立即终止，返回1，而在B中的其他2次，进程立即终止，返回0。
但是给定这些数据，估计值V (A)的最优值是多少?这里有两个合理的答案。一个是100%的观察。



一个B
r = 1


100%
75%

25%
r = 0

r = 0
乘以进程处于状态A，它立即遍历到B(奖励为0);因为我们已经确定B的值是3 4，所以A必须有值
3
4。
看这个答案的一种方法是，它是基于第一次对马尔可夫过程的建模，在这个例子中是向右的，然后计算出给定模型的正确估计，在这个例子中，它给出了V (A) = 3 4。这是

也就是批次TD(0)给出的答案。
另一个合理的答案是，我们观察到，我们已经看到了一次，之后的回报是0;因此我们估计V (A)为0。这就是批量蒙特卡罗方法给出的答案。注意，这也是对训练数据给出最小平方误差的答案。事实上，它对数据的误差为零。但我们仍然期待第一个答案会更好。如果这个过程是马尔可夫过程，我们预计第一个答案将在未来的数据上产生更低的误差，即使蒙特卡罗的答案在现有数据上更好。
示例6.4说明了批量TD(0)方法和批量蒙特卡罗方法的估计之间的一般差异。批量蒙特卡罗方法总是找到最小化训练集上的均方误差的估计，而批量TD(0)方法总是找到对马尔可夫过程的最大似然模型完全正确的估计。一般来说，参数的最大似然估计是生成数据的概率最大的参数值。在这种情况下,最大似然估计的模型是马尔可夫过程中形成明显的方式从观察到的事件:转移概率估计从我到j是观察到的分数转换从我这去j,和相关的预期回报的平均回报观察这些转换。在这个模型中，我们可以计算值函数的估计值，如果模型是完全正确的，那么它将是完全正确的。这被称为确定-等价估计，因为它等价于假定底层过程的估计是确定的而不是被估计的。总的来说，批量TD(0)收敛于确定性等价估计。
这有助于解释为什么TD方法比蒙特卡罗方法收敛得更快。在批处理形式中，TD(0)比蒙特卡罗方法更快，因为它计算的是真实的确定性-等价估计。这解释了TD(0)在随机漫步任务的批处理结果中所显示的优点(图6.2)。与某些等价估计的关系也可以在一定程度上解释非批量TD(0)的速度优势(例如，例6.2，第125页，右图)。虽然非批处理方法既没有达到确定的等价性，也没有达到最小的平方误差估计，但是它们可以被理解为大致在这些方向上移动。非批量TD(0)可能比constant-αMC更快,因为它正朝着一个更好的估计,即使它是得不到的。目前，对于在线TD和蒙特卡罗方法的相对效率，没有什么比这更明确的了。
最后，值得注意的是，虽然确定性等价估计在某种意义上是一个最优解，但直接计算它几乎是不可能的。如果n = |S|是状态数，则只需按n2个内存的顺序形成流程所需的最大似然估计值，按n3的计算步骤按顺序计算相应的值函数。在这些术语中，TD方法可以使用不超过n阶的内存和训练集上的重复计算来近似相同的解决方案，这确实令人惊讶。在状态空间较大的任务中，TD方法可能是近似确定等价解的唯一可行方法。

∗锻炼6.7设计一个off-policy TD(0)版本的更新,可以使用

任意目标策略π和覆盖的行为策略b,在每个步骤使用的重要性
抽样比例ρt:t(5.3)。 					?

\section{Sarsa: On-policy TD Control}

现在我们来谈谈TD预测方法在控制问题中的应用。像往常一样，我们遵循广义策略迭代(GPI)的模式，只是这次使用TD方法进行评估或预测部分。与蒙特卡罗方法一样，我们面临的需要是放弃勘探和开发，而方法又分为两大类:政策上的和政策上的。在本节中，我们介绍一种基于策略的TD控制方法。
第一步是学习动作-值函数，而不是状态-值函数。特别是,在政策的方法我们必须估计qπ(s)为当前行为政策π和所有国家年代和行动,这可以通过使用基本相同的学习vπTD方法上面所描述的。回想一下，一集由状态的交替序列和状态-动作对组成:


在
Rt + 1 + 1 St
Rt圣+ 1 + 2 + 2
Rt + 3圣圣+ 3 + 3 + 2
。 					。




在上一节中，我们考虑了从状态到状态的转换，并学习了状态的值。现在我们考虑从状态-动作对到状态-动作对的转换，并学习状态-动作对的值。在形式上，这些情况是相同的:它们都是带有奖赏过程的马尔可夫链。保证在TD(0)下状态值收敛的定理也适用于相应的作用值算法:

问(St)←Q(圣,)+α

Rt + 1 +γQ(圣+ 1,+ 1)−Q(圣,)

。(6.7)




撒尔沙
这个更新是在从非终端状态St.的每次转换之后完成的，如果St+1是终端，那么Q(St+1，在+1)被定义为零。这个规则使用事件的五倍中的每个元素(St, At, Rt+1, St+1, At+1)，它们构成了从一个状态-动作对到下一个状态-动作对的转换。这个五倍产生了算法的名称Sarsa。Sarsa的备份图如图右侧所示。
基于Sarsa预测方法设计一种基于策略的控制算法是非常简单的。在所有政策方法,我们不断地估计qππ行为的政策,同时改变对贪吃对qππ。Sarsa控制算法的一般形式在下一页的框中给出。
撒尔沙算法的收敛性质取决于政策的依赖的本质问题:例如,你可以使用ε-greedy或ε-soft政策。撒尔沙以概率1收敛于最优的政策和行为价值函数只要所有政府行动对访问了无限次数和政策收敛极限贪婪的政策(例如,可以安排ε-greedy政策通过设置ε= 1 / t)。
练习6.8显示的行为价值版本(6.6)适用于TD的错误的行为价值形式δt = Rt + 1 +γQ(圣+ 1,+ 1)−Q(圣,),再假设值
不要一步一步地改变。 					?

示例6.5:下面显示的多风网格世界是一个标准的网格世界，有开始状态和目标状态，但有一个不同之处:有一股横风向上穿过网格的中部。动作是标准的向上、向下、右、左四种状态，但在中间区域，由于“风”的作用，产生的下一个状态会向上移动，而“风”的强度会随列而变化。风的强度

0 1000 2000 3000 4000 5000 6000 7000 8000 0
50 100 150 170

时间步长
S G

0 0 0 					0 1 1 1 1 2
行动
在每一列下面给出，表示向上移动的单元格数。例如，如果你是目标右侧的一个单元格，那么左边的操作将你带到目标上方的单元格。这是一个尚未完全情景任务,不断回报−1直到到达目标状态。
右边的图显示的结果应用ε-greedy撒尔沙这个任务,ε= 0.1,α= 0.5,和初始值Q(,)= 0年代,a。增加的斜率图表明,目标是达到更快。通过
8000个时间步长，贪心策略自最优以来时间较长(其中显示一条轨迹);继续ε-greedy探索保持平均集长度约17步骤,两个超过最低15。注意，蒙特卡罗方法在这里不容易使用，因为不是所有策略都保证终止。如果发现了一项使代理保持相同状态的策略，那么下一次事件将永远不会结束。像Sarsa这样的在线学习方法没有这个问题，因为他们在这一事件中很快就学会了这样的政策是很差的，转而去做别的事情。
练习6.9:有风的网格世界与国王的移动(编程)重新解决了有风网格世界，假设有八个可能的动作，包括对角线的移动，而不是

通常四个。额外的行动你能做得更好吗?你能做得更好吗?包括第九次行动，除了引起的行动以外没有任何行动
风吗? 					?

练习6.10:随机风(编程)用King的动作重新解决了有风的gridworld任务，假设风的作用(如果有的话)是随机的，有时是由每一列的平均值变化1。也就是说，有三分之一的时间你完全按照这些值移动，就像之前的练习一样，但也有三分之一的时间你移动一个单元格在上面，另外三分之一的时间你移动一个单元格在下面。举个例子，如果你在目标的右边是一个细胞，你向左移动，那么三分之一的时间你移动一个细胞在目标之上，三分之一的时间你移动两个细胞在目标之上，三分之一的时间你移动到目标。?


\section{Q-learning: Off-policy TD Control}

强化学习的早期突破之一是开发一种称为Q-learning (Watkins, 1989)的离线TD控制算法

问(St)←Q(圣,)+α

Rt + 1 +γmax
一个
Q(圣+ 1 a)−Q(圣,)

在这种情况下,学习行为价值函数,Q,直接接近问∗,最优行为价值函数,独立的政策被跟踪。这极大地简化了算法的分析，并使早期的收敛证明成为可能。该策略仍然具有影响，因为它决定访问和更新哪些状态操作对。然而，正确收敛所需要的是所有对继续更新。正如我们在第5章中看到的，这是一个最小的需求，因为任何保证在一般情况下找到最优行为的方法都必须需要它。这种假设下的一种变体通常随机步长参数序列的近似条件,问了问∗收敛概率1所示。Q-learning算法如下程序形式所示。

Q-learning的备份图是什么?规则(6.8)更新状态-动作对，因此顶部节点(更新的根)必须是一个小的、填充的动作节点。更新也来自操作节点，在下一个状态中最大化所有这些操作。因此，备份图的底部节点应该是所有这些操作节点。最后，请记住，我们指出了使用这些“下一个动作”节点的最大值(图3.4-右)。你现在能猜到这个图是什么吗?如果有，请在翻到第134页图6.4的答案之前做一个猜测。
示例6.6:Cliff Walking这个gridworld示例比较Sarsa和Q-learning，突出显示了on-policy (Sarsa)和off-policy (Q-learning)方法之间的区别。

年代 					G

theclff
R
R = 1

更安全的路径

最优路径

R = -100
考虑向右显示的网格世界。这是一项标准的不间断的间歇性任务，有开始和目标状态，以及导致向上、向下、右和左移动的通常动作。奖励是−1在所有转换进入该地区除标有“悬崖。“走进这个地区增加了一个奖励100−并发送代理立即回到开始。

撒尔沙

q学习的
情节期间的奖励总和

-100年
0 100 200 300 400 500
右边的图显示了撒尔沙和q学习方法的性能与ε-greedy行动选择,ε= 0.1。在初始的瞬变后，Q-learning学习为最优策略学习值，即沿着悬崖边缘移动的策略。不幸的是,这将导致其偶尔因为ε-greedy跌落悬崖的行动选择。另一方面，Sarsa考虑了动作选择，通过网格的上部学习更长的更安全的路径。虽然Q-learning实际上学习了最优策略的值，但是它的在线性能比Sarsa差
学会迂回的政策。当然,如果ε是逐渐减少,那么这两种方法将渐近收敛于最优政策。
练习6.11为什么Q-learning被认为是一种策略外的控制方法?吗?假设行动选择是贪婪的。Q-learning算法和Sarsa算法完全一样吗?他们会做出完全相同的动作选择和重量吗
更新? 					?
\section{预期撒尔沙}

考虑一下学习算法，它就像Q-learning一样，只不过它不是使用下一个状态-动作对的最大值，而是考虑到在当前策略下每个动作的可能性。也就是说，考虑使用更新规则的算法。

问(St)←Q(圣,)+α

Rt + 1 +γEπ[Q(圣+ 1,+ 1)|圣+ 1]−Q(圣,)

←Q(St)+α

Rt + 1 +γ

一个
π(|圣+ 1)Q(圣+ 1 a)−Q(圣,)

(6.9)


但那是遵循Q-learning模式的。给定下一个状态St+1，该算法与Sarsa在期望中的移动方向一致，因此被称为expect Sarsa。它的备份图显示在图6.4的右边。
预期的Sarsa在计算上比Sarsa更复杂，但反过来，它消除了随机选择At+1带来的方差。在同样的经验量下，我们可能会认为它的表现比萨尔萨略好，事实上它通常是这样的。图6.3显示了与Sarsa和Q-learning相比，带有预期Sarsa的cliff-walking任务的总结结果。在这个问题上，与Q-learning相比，Sarsa保留了显著的优势。此外，预期的Sarsa显示出显著的改善
 
α
图6.3:TD的临时和渐近性能控制方法cliff-walking任务作为α的函数。所有算法与ε= 0.1ε-greedy政策使用。渐近表演平均超过100,000集，而临时表演平均超过前100集。这些数据分别为中期和渐进情况下的5万次和10次。实心圆表示每种方法的最佳过渡性能。改编自van Seijen et al.(2009)。

q学习的预期撒尔沙

图6.4:Q-learning和预期Sarsa的备份图。



撒尔沙/广泛的步长参数α的值。在cliff walking中，状态转换都是确定性的，并且所有的随机性都来自策略。在这种情况下,预期的撒尔沙可以安全地设置α= 1没有遭受任何退化的渐近性能,而撒尔沙只能长期表现良好在α一个较小的值,在短期业绩很差。在这个和其他例子中，预期Sarsa对Sarsa有一个一致的经验优势。
这些悬崖行走结果预期撒尔沙在政策,但总的来说它可能使用一个政策目标不同政策π生成行为,在这种情况下,它成为off-policy算法。例如,假设π是贪婪的政策而行为更多的探索性;然后预期Sarsa就是Q-learning。在这个意义上，期望Sarsa包含并推广Q-learning，同时可靠地改进Sarsa。除了额外的计算开销很小之外，预期的Sarsa可能会完全控制其他两种更知名的TD控制算法。


\section{最大偏差和双学习}

到目前为止，我们讨论的所有控制算法都涉及到目标策略的构建的最大化。例如,在q学习的目标政策是贪婪的政策在当前行动的价值观,这是马克斯,定义和撒尔沙的政策通常是ε-greedy,也涉及到一个最大化操作。在这些算法中，最大值超过估计值被隐式地用作最大值的估计值，这可能导致显著的正偏差。要知道为什么，考虑一个单独的状态s，其中有许多行为a的真实值q(s, a)都为0，但其估计值q(s, a)是不确定的，因此分布在一些高于和一些低于0的状态。真实值的最大值是零，但是估计值的最大值是正的，一个正的偏差。我们称之为最大化偏差。
例子6.7:最大化偏倚示例图6.5所示的小MDP提供了一个简单的例子，说明了最大化偏差如何影响TD控制算法的性能。MDP有两个非终端状态A和b。事件总是从A开始，在两个动作之间进行选择，左和右。正确的操作立即转换到终端状态，并返回0。左行动过渡到B,也奖励的零,有许多可能的行动导致立即终止所有的奖励来自正态分布方差平均−0.1和1.0。因此,预期回报任何轨迹从左−0.1开始,因此采取了国家总是一个

图6.5:简单情景MDP的Q-learning和双Q-learning的比较(如图所示)
插图)。Q-learning最初学习左动作的频率要比正确动作高得多，并且总是比5%的最小概率更频繁地学习左动作
ε-greedy行为选择与ε= 0.1。相反，双q学习基本上不受最大偏差的影响。这些数据平均运行超过10,000次。最初的行为价值估计
是零。随机ε-greedy行动选择的任何关系被打破。



错误。然而，我们的控制方法可能偏向左，因为极大化偏倚使B看起来具有正值。图6.5显示了q学习ε-greedy行动选择最初学会强烈支持左边行动在这个例子。即使在渐近线,q学习需要左边行动约5%通常是最佳的在我们的参数设置(ε= 0.1,α= 0.1,γ= 1)。
有没有避免最大偏差的算法?首先，考虑一个匪徒案例，在这个案例中，我们对许多行为的每个行为的价值都有嘈杂的估计，这些行为都以每个行为在所有游戏中所获得的奖励的样本平均值来获得。正如我们上面所讨论的，如果我们用估计值的最大值作为真实值的最大值的估计值，就会有一个正的最大化偏差。看待这个问题的一种方法是，它是由于使用相同的样本(play)来确定最大化行为和估计它的价值。假设我们把在两集和他们学习使用两个独立的估计,称之为Q1(a)和(a),每个估计的真正价值q(a),对所有∈答:我们可以使用一个估计,说Q1,确定最大化行动∗= argmaxa Q1(a),另,Q2,提供的估计价值,Q2(∗)= Q2(argmaxa Q1(a))。这将无偏估计,E[Q2(∗)]= q(∗)。我们还可以重复这一过程，将两个估计值颠倒后，得到第二个无偏差的估计值Q1(argmaxa Q2(a))。这是双重学习的概念。注意，虽然我们学习了两个估计值，但是每个游戏只更新一个估计值;重复学习可以使内存需求增加一倍，但不会增加每一步的计算量。
双学习的想法自然地扩展到实现完整MDPs的算法。例如，类似于Q-learning的双学习算法，称为双q学习，将时间步分为两步，可能是在每一步上抛硬币。如果硬币朝上，


如果硬币是反面，那么同样的更新是在交换了Q1和Q2之后完成的，所以Q2被更新了。这两个近似函数是完全对称的。行为策略可以同时使用动作价值评估。例如,一个ε-greedy政策双q学习可以根据平均(或总和)两个行为价值的估计。在下面的框中给出了一个完整的双q学习算法。这是用于生成图6.5中的结果的算法。在这个例子中，重复学习似乎消除了最大化偏差带来的危害。当然也有双重版本的莎莎和预期的莎莎。
 
∗锻炼6.13的更新方程是什么预期撒尔沙的两倍
ε-greedy目标政策? 					?



\section{游戏、后州和其他特殊情况}

在这本书中，我们试图提出一种统一的方法来处理广泛的任务，但是当然，总是有一些特殊的任务，以专门的方式得到更好的处理。例如，我们的一般方法包括学习一个动作-值函数，但是在第一章中，我们提出了一个学习玩井字游戏的TD方法，它学习了一些更像状态-值函数的东西。如果我们仔细看一下这个例子，就会发现这个函数在通常意义上既没有动作值函数也没有状态值函数。常规的状态值函数评估代理可以选择操作的状态，但是使用的是状态值函数

在代理人采取行动后，井字游戏会评估董事会的位置。让我们调用这些后态和值函数，这些后态值函数。当我们了解了环境动力学的初始部分，但不一定是完整的动力学时，后状态是有用的。例如，在游戏中，我们通常知道动作的直接影响。我们知道每一个可能的棋局的棋局将会是什么位置，但不知道我们的对手会如何回答。后态价值函数是利用这种知识的一种自然方法，从而产生一种更有效的学习方法。
传统的动作值函数会从位置映射到值的估计值。但是许多位置移动对产生相同的结果位置，如下面的例子所示:
 
 

在这种情况下，位置移动对是不同的，但是产生相同的“后位置”，因此必须具有相同的值。传统的动作价值函数必须分别评估这两对，而后态价值函数将立即同时评估这两对。任何关于左边位置移动对的了解都会立即转移到右边。
后状态出现在许多任务中，而不仅仅是游戏。例如，在排队任务中有一些操作，如将客户分配到服务器、拒绝客户或丢弃信息。在这种情况下，行动实际上是根据它们的直接影响来定义的，这是众所周知的。
描述所有可能的专门化问题和相应的专门化学习算法是不可能的。然而，本书所阐述的原则应该得到广泛的应用。例如，在通用策略迭代方面，afterstate方法仍然被恰当地描述，策略和(afterstate)值函数以基本相同的方式交互。在许多情况下，人们仍然需要在政策上和政策之外的方法之间进行选择，以管理持续探索的需要。

练习6.14描述了如何根据后态重新定义Jack的租车任务(例子4.2)。为什么，就这个具体的任务而言，会有这样一个
重组有可能加快收敛速度? 					?


\section{总结}
在本章中，我们介绍了一种新的学习方法——时变学习(TD)，并说明了它如何应用于强化学习问题。像往常一样，我们把整个问题分为预测问题和控制问题。TD方法是蒙特卡罗方法解决预测问题的替代方法。在这两种情况下，对控制问题的扩展都是通过我们从动态规划中抽象出来的广义策略迭代(GPI)概念。这是近似策略和值函数的交互方式，它们都朝着最优值移动。
组成GPI的两个过程之一驱动值函数准确预测当前策略的收益;这就是预测问题。其他流程驱动政策改善本地(例如,ε-greedy)对当前值函数。当第一个过程建立在经验的基础上时，关于保持充分探索的复杂性就产生了。我们可以根据TD的控制方法是采用政策上的还是政策外的方法来处理这一复杂问题，对其进行分类。Sarsa是一种策略方法，Q-learning是一种策略外的方法。正如我们在这里所展示的，预期的Sarsa也是一种非政策方法。有第三种方法可以将TD方法扩展到控制中，我们在这一章中没有包括这种方法，叫做actor - critics方法。这些方法在第13章中有详细介绍。
本章介绍的方法是目前应用最广泛的强化学习方法。这可能是因为它们非常简单:它们可以在线应用，只需要很少的计算量，就可以通过与环境的交互产生体验;它们几乎完全可以用单个方程来表示，这些方程可以用小型计算机程序实现。在接下来的几章中，我们对这些算法进行了扩展，使它们变得稍微复杂一些，并且非常强大。所有的新算法都将保留本文介绍的本质:它们将能够在线处理经验，而计算量相对较少，并且它们将受到TD错误的驱动。本章所介绍的TD方法的特殊情况应该被正确地称为一步法、表格法、无模型的TD方法。在接下来的两章中，我们将它们扩展到n步的表单(与蒙特卡罗方法的链接)和包含环境模型的表单(与规划和动态编程的链接)。然后，在书的第二部分，我们将它们扩展到各种形式的函数逼近，而不是表(连接到深度学习和人工神经网络)。
最后，在本章中，我们已经讨论了完全在强化学习问题的背景下的TD方法，但是TD方法实际上比这更一般。它们是学习对动力系统进行长期预测的一般方法。例如，TD方法可能与预测财务数据、寿命、选举结果、天气模式、动物行为、发电站需求或客户购买相关。只有将TD方法作为纯粹的预测方法进行分析，不依赖于它们在强化学习中的应用，它们的理论性质才首次得到充分的理解。即便如此，TD学习方法的其他潜在应用还没有得到广泛的探索。
