《强化学习》中的第12章:资格迹

前言: 本次笔记对《强化学习(第二版)》第十二章进行概括性描述。

以下概括都是基于我个人的理解,可能有误,欢迎交流:piperliu@qq.com。

第12章我依旧有很多地方不懂、不透,这里,我只尽力将自己所理解的知识体系串讲下来,并且我在文末给出自己的疑问与猜测的答案/解决方案。因为还有很多东西要学要做,因此第一遍学习不求很透彻,重视工程能力而非理论能力。

第12章提出的方法实在太多,个人认为其核心思想在于利用“资格迹”这个辅助向量,“优雅地”把前向视图转为后向视图(使计算在线、高效)。

正文

12.1 lambda-回报

个人认为从蒙特卡洛方法说起会更加好理解一点:蒙特卡洛lambda-回报的特例

什么意思?当lambda=1时,才是蒙特卡洛方法,若lambda不等于1其计算量比蒙特卡洛方法大了n倍

当幕结束时:

  • 蒙特卡洛方法只从最后一步回溯(G_t的t即最后一步),对每个状态进行价值更新;
  • lambda-回报不单单从最后一步回溯,还要从 T-1, T-2, T-3, ... 步回溯,其前面乘上参数lambda相关项

换个说法:

蒙特卡洛lambda-回报都对每一个时刻有对应的回报 G t G_t Gt​,但是lambda-回报的 G t G_t Gt​信息量更丰富一些,其中包含了lambda-回报的相关项运算,因此写作 G t λ G_t^\lambda Gtλ​。

代码可见https://nbviewer.jupyter.org/github/PiperLiu/Reinforcement-Learning-practice-zh/blob/master/practice/Random-Walk-Mountain-Car.ipynb

12.2 TD(lambda)

上节所提到的lambda-回报有这样几个问题:

  • 不能在线,有延后(前向视图,需要用到)(必须幕结束后才能更新);
  • 幕结束后,计算任务集中统一处理(计算压力大)。

TD(lambda)是一种古老的方法,却解决了上述问题。

其能解决上述问题的技巧在于,其引入了辅助的向量“资格迹”,这个向量与权重向量同样大小,用于保存权重的“痕迹”。

资格迹随着迭代的更新而更新。

因此我们有了后项视图(依靠产生过的、身后的数据来更新权重)的算法。

应注意,代码https://nbviewer.jupyter.org/github/PiperLiu/Reinforcement-Learning-practice-zh/blob/master/practice/Random-Walk-Mountain-Car.ipynb的random-walk案例中,虽然是对权重进行更新,其实本质上还是表格型的 v ( s ) v(s) v(s)关系。因为在这个案例中,编程者是对其进行 v ( s ) = w T x = w 1 x 1 + w 2 x 2 . . . v(s) = w^T x = w_1 x_1 + w_2 x_2 ... v(s)=wTx=w1​x1​+w2​x2​...且 x 1 = [ s 1 , 0 , 0 , . . ] T , x 2 = [ 0 , s 2 , 0 , . . ] T x_1=[s_1, 0, 0, ..]^T, x_2=[0, s_2, 0, ..]^T x1​=[s1​,0,0,..]T,x2​=[0,s2​,0,..]T建模的。

12.3 n-步截断 lambda-回报方法

现在回过头来考虑离线算法,我们给t时刻规定一个视界h,即回报 G t G_t Gt​只能获得从t到h的共(h-t)步的回报,即 G t : h λ G_{t:h}^\lambda Gt:hλ​

我们称这种回报为截断回报

如果你仔细阅读random-walk案例的代码会发现,其实截断的思想早有体现:当lambda有很高次方时,该项对于更新的影响其实微乎甚微,可以省略。

有关截断的相关算法被称为截断TD(lambda)TTD(lambda)

并且,由此推广, G t : t + k λ G_{t:t+k}^\lambda Gt:t+kλ​有了一个高效的计算公式,见公式12.10。【疑问1】

12.4 重做更新:在线lambda-回报算法

12.4节其实是12.5的铺垫,12.4提出了一种计算量很庞大的算法,12.5提供了其简化形式(计算量小,效果相同)。

重做更新:在线lambda-回报算法中,随着时间的推移(随着步进,或者说随着t的最大值的增大),我们收获的数据也在变多,视界h也就可以随之增大,因此,每走一步(t最大可取的值增大/h增大),我们就可以进行一次更新全局的、从t=0到t=h的更新。

关于公式,这里我有个疑问,昨天着实困扰我许久。我做出了自己的猜测。

h = 1    :    w 0 1 = w 0 1 + α [ G 0 : 1 λ − v ^ ( S 0 , w 0 1 ) ] ∇ v ^ ( S 0 , w 0 1 ) h = 2    :    w 1 2 = w 0 2 + α [ G 0 : 2 λ − v ^ ( S 0 , w 0 2 ) ] ∇ v ^ ( S 0 , w 0 1 )    w 2 2 = w 0 1 + α [ G 0 : 2 λ − v ^ ( S 1 , w 1 2 ) ] ∇ v ^ ( S 0 , w 1 2 ) h = 3    :    w 1 3 = w 0 3 + α [ G 0 : 3 λ − v ^ ( S 0 , w 0 3 ) ] ∇ v ^ ( S 0 , w 0 3 )    w 2 3 = w 1 3 + α [ G 1 : 3 λ − v ^ ( S 1 , w 1 3 ) ] ∇ v ^ ( S 0 , w 1 3 )    w 3 3 = w 2 3 + α [ G 2 : 3 λ − v ^ ( S 2 , w 2 3 ) ] ∇ v ^ ( S 0 , w 2 3 ) \begin{aligned} h = 1 & \; : & \; w_0^1 = w_0^1 + \alpha [G_{0:1}^\lambda - \hat{v}(S_0,w_0^1)]\nabla \hat{v}(S_0,w_0^1) \\ h = 2 & \; : & \; w_1^2 = w_0^2 + \alpha [G_{0:2}^\lambda - \hat{v}(S_0,w_0^2)]\nabla \hat{v}(S_0,w_0^1) \\ & & \; w_2^2 = w_0^1 + \alpha [G_{0:2}^\lambda - \hat{v}(S_1,w_1^2)]\nabla \hat{v}(S_0,w_1^2) \\ h = 3 & \; : & \; w_1^3 = w_0^3 + \alpha [G_{0:3}^\lambda - \hat{v}(S_0,w_0^3)]\nabla \hat{v}(S_0,w_0^3) \\ & & \; w_2^3 = w_1^3 + \alpha [G_{1:3}^\lambda - \hat{v}(S_1,w_1^3)]\nabla \hat{v}(S_0,w_1^3) \\ & & \; w_3^3 = w_2^3 + \alpha [G_{2:3}^\lambda - \hat{v}(S_2,w_2^3)]\nabla \hat{v}(S_0,w_2^3) \\ \end{aligned} h=1h=2h=3​:::​w01​=w01​+α[G0:1λ​−v^(S0​,w01​)]∇v^(S0​,w01​)w12​=w02​+α[G0:2λ​−v^(S0​,w02​)]∇v^(S0​,w01​)w22​=w01​+α[G0:2λ​−v^(S1​,w12​)]∇v^(S0​,w12​)w13​=w03​+α[G0:3λ​−v^(S0​,w03​)]∇v^(S0​,w03​)w23​=w13​+α[G1:3λ​−v^(S1​,w13​)]∇v^(S0​,w13​)w33​=w23​+α[G2:3λ​−v^(S2​,w23​)]∇v^(S0​,w23​)​

书上说, w 0 h w_0^h w0h​由上一幕继承而来,最终所需要的权重(或者说权重的最终值)即 w T T w_T^T wTT​。那么,我的问题是:干嘛要在h=1、h=2..时计算呢?在h=T时计算不好吗?毕竟,我注意到,h=T计算的公式中,没有用到h=T-1产生的变量w^{T-1}。

后来我自己给出了答案:重做更新:在线lambda-回报算法其实还是基于12.3中公式12.10的离线lambda-回报的。比如在 w 1 2 w_1^2 w12​的计算中,我们还是用到了 G 0 : 2 G_{0:2} G0:2​,在 G 0 : 2 G_{0:2} G0:2​的计算中,我们还是需要 w 1 w_1 w1​的值,而此时 w 1 1 w_1^1 w11​的值未产生,我们需要用到 w 1 0 w_1^0 w10​(上个视界产生的值)。

12.5 真实的在线TD(lambda)

真实的在线TD(lambda)是效果(数学上等价)的真正意义上的在线、计算量小重做更新

其资格迹被称为荷兰迹

12.6 蒙特卡洛学习中的荷兰迹

本节证明了前向视图和后向视图的等价性。【疑问3】

12.7 Sarsa(lambda)

看到 Sarsa ,我们知道,要开始探讨控制问题。

即把对 v ( s , w ) v(s, w) v(s,w) 估值的方法迁移到对 q ( s , a , w ) q(s, a, w) q(s,a,w) 估值上来。

12.8 变量lambda和gamma

本节没有给出控制变量lambda和gamma的明确结论,我也没有深究。

12.9 带有控制变量的离轨策略资格迹

讨论了同轨策略问题,照例,应该来讨论离轨策略问题。

本节由7.4节中的带有控制变量的每次决策型重要度采样的自举法,进行推广,得出了带有重要度采样的lambda-回报形式。数学证明我没有深究。

但是半梯度方法的离轨策略稳定性终究是不理想的。

12.10 从Watkins的Q(lambda)到树回溯TB(lambda)

首先讨论了Watkins的Q(lambda),其既可以使用离轨策略数据,又有不使用重要度采样的优势。

此外,还有树回溯(lambda)或称为TB(lambda)方法。没有实例,我也没有深究。【疑问4】

12.11 采用资格迹保障离轨策略方法的稳定性

这节结合了11.7、11.8中的梯度TD或强调TD的思想。在算法GTD(lambda)中,提出了一个额外的向量, v \textbf{v} v用于分布存储样本【疑问5】。

算法HTD(lambda)可以视为TD(lambda)的扩展,同时结合了算法GTD(lambda)

算法强调TD(lambda)是单步强调TD算法的扩展。这还涉及到了收敛性的问题。【疑问6】

12.12 实现中的问题

现实计算中,我们经常涉及到计算量与准确性的博弈

对于并行计算机来说,这很好解决。

对于常规串行计算机来说,通常,有很多lambda、gamma的项是接近0的,可以舍去。

疑问

疑问1:

此处的证明以及练习12.5应该是巧妙且复杂的,我没有深究。相信答案在原论文中。

疑问2:

解答如原文12.4 重做更新:在线lambda-回报算法

疑问3:

关于12.6 蒙特卡洛学习中的荷兰迹的数学证明我没有深究。

疑问4:

12.10 从Watkins的Q(lambda)到树回溯TB(lambda,未来深究该知识点时,可以考虑写出其伪代码。

疑问5:

由于没有理解透彻,不知“分布存储样本”这个说法来形容 v \textbf{v} v是否正确。

疑问6:

书上没说,我也不知道这几个算法的效果、适用场景有何差别。原论文中应该会有对比。

Piper Liu
2020-3-20 00:08:12

上一篇:Unsupervised Monocular Depth Estimation with Left-Right Consistency 论文解析


下一篇:从GNN到GCN再到GAT