时间差分学习外文翻译资料

 2021-11-26 10:11

英语原文共 24 页

选自Richard S. Sutton and Andrew G. Barto的著作《Reinforcement Learning:

An Introduction》第六章:Temporal-Difference Learning

时间差分学习

如果必须将一个观点作为强化学习的核心和新概念,那么它无疑就是时间差分(TD)学习。TD学习是蒙特卡罗思想和规划的结合。与蒙特卡罗方法一样,TD方法可以直接从原始经验中学习,而无需建立环境动力学模型。与DP方法一样,TD方法部分地更新了估计值。 根据其他了解到的估计,无需等待最终结果(他们自举)。在强化学习理论中,TD、DP和蒙特卡罗方法之间的关系是一个反复出现的主题。 这一章是我们对它的探索的开始。在我们完成之前,我们将看到这些想法和方法相互融合,可以在许多方面结合在一起。尤其是在第一章 第七章介绍了n步算法,它提供了从TD到蒙特卡罗方法之间的桥梁,在第12章中,我们介绍了TD(lambda;)算法,它将它们无缝地结合在一起。

像往常一样,我们首先关注策略评估或预测问题,即为给定的策略标准估算价值函数Vacs。对于控制问题(找到最佳策略),DP, TD和MonteCarlo方法都使用了广义策略迭代(GPI)的一些变化。这些方法的差异主要是它们在预测问题的方法上的不同。

6.1 TD预测

TD和MonteCarlo方法都是利用经验来解决预测问题。根据策略pi;的一些经验,这两种方法都会更新它们对非终端状态Stoc的Vpi;估计值。 在那次经历中急转直下。粗略地说,蒙特卡洛方法等到访问后返回时才知道,然后使用该返回作为V(ST)的目标。一种简单的每次访问蒙特卡洛方法适合于非平稳环境的OD值是

V (St) larr; V (St) alpha;[Gt -V (St)] (6.1)

其中GT是时间t之后的实际返回值,而alpha;是一个常数步长参数(c.f.,等式2.4)。让我们把这个方法称为常量-alpha;MC。鉴于蒙特卡罗方法必须等到回合结束时才能确定到V(ST)的增量(只有这样才知道),TD方法只需要等到下一个时间步骤。在t1时,它们立即形成一个 使用观察到的奖励RT 1和估计值V(ST 1)对目标和进行有用的更新。最简单的TD方法,称为TD(0),是

V (St) larr; V (St) alpha;[Rt 1 gamma;V (St 1)- V (St)] (6.2)

实际上,MonteCarlo更新的目标是GT,而TD更新的目标是Rt 1 gamma;V (St 1)。页面底部的框完全以过程形式指定TD(0)。TD (0)是TD(lambda;)的一个特例,在第12章中讨论过。

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

粗略地说,MonteCarlo方法以(6.3)为目标,而DP方法以估计(6.4)为目标。蒙特卡罗目标是一个估计,因为期望值不知道;用样本返回代替实际预期回报。DP目标是一个估计数,而不是因为期望值被假定完全由蒙特卡罗方法提供。 由于不知道Vpi;(ST 1),因此使用当前估计值V(ST 1)。由于这两个原因,TD目标是一个估计:它在(6.4)中对期望值进行了采样。它使用的是当前估计值V,而不是真正的Vpi;。因此,TD方法将蒙特卡罗采样和自举结合在一起。

估计Vpi;的表格TD(0)

输入:要评估的策略pi;

初始化V(S)(例如,V(S)=0,forall;sisin;S)重复(针对每一回合):

初始化S重复(针对每一回合):

pi;为S 提供动作A,观察R,S

V(S)larr;V(S)alpha;Rgamma;V(S _) - V(S),

Slarr;S _

直到S结束。

正如我们将要看到的那样,如果谨慎想象的话,这将使我们在获得蒙特卡罗方法和DP方法的优势方面走了很长的路。TD(0)右边的图是备份图顶部的状态节点的,值估计是根据从它到随后状态的一个示例转换来更新的。我们指的是TD(a)。 MonteCarlo更新为示例备份,因为它们涉及到向前看样例的后续状态(或状态-动作对),使用后续状态的值和计算过程中的奖励。然后相应地更改原始状态(或状态-操作对)的值。示例备份与DP方法的完整备份不同,因为它们是基于单个样本的继承,而不是完全分配所有可能的继承。

最后注意,TD(0)更新中括号中的数量是一种错误,测量了 ST的估计值及较好的RT 1 gamma;V(ST 1)估计值。这种数量,称为TD错误,在强化学习过程中以各种形式出现:

注意,每个时间的TD错误都是当时估计值中的错误。因为TD错误取决于下一个状态和下一个奖励,所以它在一个时间步骤之前实际上是不可用的。 后来。也就是说,delta;t是V(ST)中的错误,在时间t1可用。还请注意,MonteCarlo错误可以写成TD错误之和:

这一事实及其推广在TD学习理论中起着重要的作用。

6.2 TD预测方法的优势

TD方法部分地在其他估计的基础上学习其估计数。他们从猜测中学到猜测-他们自举。这是件好事吗?TD方法与Montecar相比有什么优势? LO和DP方法?开发和回答这样的问题将占用这本书的其余部分和更多。在本节中,我们简要地预测了一些答案。

显然,与DP方法相比,TD方法有一个优势,因为它们不需要环境、回报和下一状态概率分布的模型。

与蒙特卡罗方法相比,TD方法的另一个最明显的优点是,它们自然是以在线、完全增量的方式实现的。用蒙特卡罗方法,必须等到 E的结尾,因为只有这样才是返回已知的,而对于TD方法,只需要等待一个时间步骤。令人惊讶的是,这往往是一个关键的考虑因素。一些应用 S有很长的回合,所以把所有的学习推迟到一回合结束是太慢了。其他应用程序是持续的任务,根本没有节点。

最后,在前一章中我们注意到,一些蒙特卡罗方法必须忽略或忽略一些实验动作,这会大大降低学习速度。TD方法是较少的套叠。 这些问题是可以理解的,因为无论采取什么后续行动,它们都可以从每个过渡中学习。

但是TD方法是否合理?当然,在不等待实际结果的情况下,从下一个猜测中学习是很方便的,但我们还能保证收敛到正确的答案吗?令人高兴的是 答案是肯定的。对于任何固定的策略pi;,已经证明了上面描述的TD算法收敛到Vpi;,对于一个常数步长参数(如果它足够小的话),并且是带概率的。 如果步长参数按照通常的随机近似条件(2.7)减小,则为1。大多数收敛性证明仅适用于基于表的ABO算法的情形。但也有一些适用于一般线性函数逼近的情形。这些结果将在后面两章的一个更一般的背景中讨论。

如果TD和MonteCarlo方法都渐近地收敛到正确的预测,那么一个自然的下一个问题是“哪个首先到达那里?”换句话说,哪种方法学习得更快?如何更有效地利用有限的数据?目前,这是一个悬而未决的问题,因为没有人能够从数学上证明一种方法比另一种方法收敛得更快。我 事实上,还不清楚什么是最适合表达这个问题的正式方式!然而,在实践中,TD方法通常比恒定alpha;MC方法收敛得更快。

6.3 TD(0)的最优性

假设只有有限的经验,例如10或100个步骤。在这种情况下,使用增量学习方法的常见方法是呈现经验重复。 直到方法收敛到一个答案为止。给定一个近似值函数V,则计算由(6.1)或(6.2)指定的增量,用于非终端状态为v的每个时间步骤t。但值函数只更改一次,即所有增量之和。然后,使用新的值函数再次处理所有可用的经验,从而产生新的整体增量。 等等,直到值函数收敛为止。我们将此批更新称为批更新,因为只有在处理完每一批完整的培训数据后才会进行更新。

在批更新下,只要选择了足够小的alpha;,TD(0)就确定地收敛到一个独立于步长参数alpha;的单一答案。常数alpha;MC方法 在相同的条件下,肯定地,但答案不同。理解这两个答案将有助于我们理解这两种方法的不同之处。在正常更新下 e方法不会一直移动到它们各自的批处理答案,但在某种意义上,它们在这些方向上采取步骤。在试着去理解这两个答案之前,对于所有可能的问题,我们首先看几个例子。

示例6.3:批更新版本TD(0)和常数-alpha;MC下的随机游走被应用于随机游走预测示例(示例6.2)。在每一集之后, 我们到目前为止看到的剧集都被当作一批处理。它们被反复提交给算法,无论是TD(0)还是常数alpha;MC,alpha;足够小以至于值函数收敛。结果 然后将ing值函数与vpi;进行比较,绘制出五种状态下的平均均方误差(以及整个实验的100次独立重复),得到 学习曲线如图6.3所示。请注意,批处理TD方法始终优于批处理MonteCarlo方法。

图6.3:批量训练下TD(0)和常数-alpha;MC在随机游走任务上的性能

在批量训练下,常数-alpha;MC收敛到值V(S),即访问每个州后实际收益的样本平均值。在t的意义上,这些是最优估计。 将训练集中实际返回的均方误差降到最低。从这个意义上讲,批处理TD方法能够根据均方根更好地执行,这是令人惊讶的。度量值如图6.3所示。如何使批处理TD能够比这种最优方法表现得更好?答案是蒙特卡罗方法仅在有限的范围内是最优的,而TD(i)则是最优的。 s以一种与预测收益更相关的方式进行优化。

6.4 Sarsa:同策略的TD控制

现在我们来谈谈TD预测方法在控制问题上的应用。与往常一样,我们遵循广义策略迭代(Gpi)的模式,但这次只使用TD方法进行计算(P)。与蒙特卡洛方法一样,我们面临着对勘探和开发进行权衡的需要,方法又分为两大类:on-policy和off-policy。在本节中,我们将提出了一种在线TD控制方法。

第一步是学习操作值函数,而不是状态值函数。特别是对于同策略方法,我们必须估计当前行为策略pi;和所有行为策略的qpi;(s,a)。 国家和行动a.这可以使用上面描述的学习Vpi;的本质上相同的TD方法来完成。回想一下,一个回合由一组交替的状态和状态动作组成。

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

此更新是在从非终端状态ST进行的每一次转换之后完成的。如果ST 1是终端,则q(ST 1,at 1)定义为零。此规则使用事件的每个元素(ST,at ,RT 1,ST 1,at 1),构成了从一个状态-动作对到下一个状态-动作对的过渡。算法的名字称为Sarsa。

设计一种基于Sarsa预测方法的策略控制算法是非常简单的.与所有同策略方法一样,我们不断地估计行为策略pi;的qpi;,并且在相同的 时间改变了pi;对Qpi;的贪婪。在下面的方框中给出了Sarsa控制算法的一般形式。

Sarsa:一种同策略TD控制算法

初始化q(s,a),forall;sisin;S,aisin;A(S),任意和q(终端状态)=0

重复(每回合):使用从q(例如-贪婪策略)重复(对每个s)派生的策略

初始化S选择A

采取行动A,观察R,S0从S0中选择A0,使用Q(例如-贪婪策略)

Q(S,A)larr;Q(S,A)alpha;Rgamma;Q(S 0,A0) - Q(S,A),

Slarr;S0,

Alarr;A0的策略;

直到S是终点

Sarsa算法的收敛性取决于策略依赖Q的性质,例如,可以使用ε-贪婪策略或ε-软策略。据Satinder Singh称(个人交流),只要对所有状态-动作对进行无限次访问,且策略收敛于t,则SARSA以1的概率收敛到最优策略和动作值函数。 他仅限于贪婪策略(例如,可以通过设置ε-贪婪策略设置ε=1/t来安排),但这一结果尚未在文献中发表。

6.5 Q-learning:异策略TD控制

强化学习的早期突破之一是开发了一种称为q学习的异策略TD控制算法(Watkins,1989)。

在这种情况下,学习的动作值函数Q直接逼近Qlowast;,这是与所遵循的策略无关的最优动作值函数。这极大地简化了对 该算法实现了早期收敛性证明。策略仍然有效果,因为它决定访问和更新哪些状态-动作对。然而,所有这些都是正确的合作所需要的。 继续更新所有对,正如我们在第5章中所观察到的,这是在一般情况下保证找到最佳行为的任何方法都必须满足的最低要求。 要求它。在此假设下,在阶跃参数序列上通常的随机逼近条件的一个变体下,证明了q在概率1到qlowast;的情况下是收敛的。Q- 学习算法以过程形式显示在下面的框中。

  1. learning:一种异策略TD控制算法

初始化q(s,a),forall;sisin;S,aisin;A(S),任意,和q(终端状态)=0

重复(对于每回合):

初始化S重复(对于回合的每一步):使用从Q派生的策略从S中选择A (例如-贪婪)采取行动A,观察R,S_0

q(S,A)larr;q(S,A)alpha;[R gamma;Maxa q(S_0,a) - q(S,A)],

Slarr;S_0

直到S终止。

Q学习的规划图是什么?规则(6.8)更新一个状态-动作对,所以顶部节点,备份的根,必须是一个小的填充操作节点。后续也来自于行动。 在下一个状态下,最大化所有可能的操作。因此,备份图的底部节点应该是所有这些操作节点。最后,请记住,我们指示取最大值。 这些“下一个操作”节点的弧线穿过它们(图3.7-右)。你现在能猜出这张图是什么吗?如果是,请先猜一猜,然后再看图6.6中的答案。

例6.6:CliffWalking这个网格世界示例比较了Sarsa和QLearning,突出了同策略(Sarsa)和异策略(QLearning)方法之间的区别。考虑一下所显示的网格世界 在图6.5的上部。

原文和译文剩余内容已隐藏,您需要先支付 20元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。