强化学习读书笔记（7）| n步自举（n-step Bootstrapping）

由于蒙特卡洛算法(MC)和一步差分算法(one-step TD) 都了采取比较极端的形式，所以这两种方法都不可能永远是最优的，最佳的方法往往就是介于TD和MC之间。n步Bootstrapping是MC和TD(0)的综合。随着对参数n的调整，我们可以看到TD是如何过渡到MC的。

n步TD算法的优势在于它解决了固定时间步长的缺点。比如一步TD算法固定了每次选择动作和更新值的时间间隔，然而很多实际应用中需要把发生的变动快速更新到值函数中。n步TD算法可以在多步后进行bootstrap，这就解决了固定一步时间间隔的缺点，还能兼具bootstrap方法的优势。

n-step TD Prediction

n-step Sarsa

n步Sarsa算法很自然的将n步反馈加入到Sarsa算法中，实现了n步Sarsa，其backup diagrams如下，和n步TD类似，只不过起始状态和结束状态都变成了动作。

n-step Off-policy Learning

Off-policy Learning Without

Importance Sampling:The n-step

Tree Backup Algorithm

在上一章中，我们已经看到像Q-Learning或者Off-Policy的Expected Sarsa都没有重要性采样的步骤，这能在n步Off-Policy中实现吗？本节中我们将介绍具有这样性质的树回溯 (Tree Backup) 算法。

树回溯算法的回溯图如下所示（以3步为例）：

n-step TD实例：

Random Walk

本节讨论有19个状态的random walk问题。起点在正中间，如果走到最左边，会得到 -1的奖励值，走到最右边，得到1的奖励值。真实的状态值分别是[-0.1,-0.2,-0.3,……,0.9]，状态初始值为0.

online n-step TD代码编写

运行结果

可以看到，n为1的时候RMS error还是偏高。而n为2就明显降低了，n=3取得实验过程中最低的RMS error，当n超过15，效果就不是很理想了。所以并不是看得越远越好。而当n大于200，状态的价值没有更新，因为在这个实验中，一个episode的步数一般为两位数，很少超过一百，所以没有更新。但是可以预见到，如果更新的话，造成的RMS error还是很大的。

小结

本章介绍了介于MC算法和一步TD算法之间的一系列TD算法。我们重点关注的是n步TD算法，所有的n步TD算法在更新本状态值之前都要继续前进n步。这些算法的一个缺点就是比前面的算法要求更大的计算量。和一步算法相比，n步算法同样也需要更多的内存来存储状态、动作、反馈和一些其它的变量。

n步bootstrapping和资格迹（eligibility traces）有很大的关联，一般使用n步bootstrapping作为资格迹的入门介绍 (第12章将介绍)。尽管n步算法比使用eligibility traces的算法更复杂，但是它有更加清晰的理论解释。我们利用这一点尝试了两个n步off-policy的算法。其中一个是使用Importance Sampling的方法，它很简单但是方差很大。如果两个策略区别很大那么这个方法很不实用。第二是使用tree-backup算法，它不使用Importance Sampling但是对于两个策略区别很大的话，bootstrapping可能只能延伸很短几步。

参考资料：

[1]R.Sutton et al.Reinforcement learning:An introduction,1998

[2]https://blog.csdn.net/qq_25037903/article/details/82425519

[3]https://blog.csdn.net/yucong96/article/details/82461999

[4]https://zhuanlan.zhihu.com/p/27773020

[5]https://blog.csdn.net/cs123951/article/details/77755108