n步自举法：时序差分方法与蒙特卡洛方法的结合

前言： 之前讨论了（1步）时序差分方法（链接）与蒙特卡洛方法（链接）。刚刚学习完 Sutton 的《强化学习（第二版）》的第七章：n步自举法。它是时序差分方法与蒙特卡洛方法的折中，一般地，效果要好于二者。

本次笔记不记录公式、算法框架，介绍思想。具体内容请见中文电子书：

第7章 n 步引导（Bootstrapping）方法：

http://rl.qiwihui.com/zh_CN/latest/partI/chapter7/n_step_bootstrapping.html

n步自举法与时序差分方法、蒙特卡洛方法

如上图：

• 时序差分方法中，下一状态的价值是“估计”出来的；
• 蒙特卡洛方法中，下一状态的价值是在整个幕都终止后，更加后续状态的折扣算出来的，是“已知”的；
• n步自举法有“部分估计”、“部分已知”的特性。但是，所有n步方法都要在更新之前延迟至n个时刻步长。

同轨策略下的控制：为什么n步比1步收敛得更快

如上图，取自 Sutton 的书，只有G点有收益，状态到达G点后：

• 在1步控制中（即之前所谓的“时序差分学习”），到达G的前1步的“状态-动作”价值得到了增强；
• 在10步控制中，到达G的前的第10步就可以“感受”到价值的增强。

离轨策略下的n步学习：共4种

在蒙特卡洛方法中我讨论过“重要度采样率”，用于离轨策略下的学习（包括估值与控制）；在时序差分控制的“期望Sarsa”中，采用后续状态的动作期望，对节点进行估值。这两个思想在离轨策略下的n步学习中得以混合、应用。

上图取自 Sutton 的书，从左到右的解释见下表：

[*] n步期望Sarsa 与 n步Sarsa略有不同：

• 在期望Sarsa中，采样率取而非Sarsa的；
• 因为在期望Sarsa方法中，最有一个状态考虑所有可能的动作，实际采取哪个动作不重要，无需修正。

代码：n步时序差分预测

使用例子 6.2 ，如下图。

n步时序差分预测算法框图如下。

来自：Zhang's GitHub

https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/tree/master/chapter07

运行结果：

我对代码进行了1处标注。

其他：数学性

本章公式较多，值得一提的是，n步时序差分方法有坚实的数学基础，引用书上的话：在最坏的情况下，采用它的期望值作为对的估计可以保证比更好；即n步回报的期望的最坏误差能够保证不大于的最坏误差的倍（）。

但 n 并非越大越好，从代码产生的例子中我们可以看出。

此外，更新公式间的递推转换，不予过分关注。

另外提一点：Sutton 在第一版中认为“n步算法在实际中不可行”，而见过Cichosz（1995），van Seijen（2016）的研究后，认为其为很实用的算法。