前言： 本次笔记对《强化学习（第二版）》第十二章进行概括性描述。
以下概括都是基于我个人的理解，可能有误，欢迎交流：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λ。
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=w1x1+w2x2...且 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