上一章提到了强化学习的一种重要方法:TD方法。TD方法结合了DP方法和MC方法的优点，不需要环境信息，并且通过DP的迭代思想大幅提高运算速度。这一章在上一章的基础上深入思考，如果增加更新时候使用的采样点数，即将TD方法推向MC方法，会有哪些新的算法，会获得更好的效果吗？
n-step TD Prediction
在引入一种新的控制算法前首先考虑就是prediction方法的实现。首先思考一下MC方法和TD(0)方法的区别：MC方法使用了episode中产生的所有action对应的reward，而TD(0)方法只使用了episode中需要更新的Q(s,a)的后续一个step的Q(s’,a’)。如果我想在两者中间取一个折中？答案很明显吧，就是使用更多的后续state-action和对应的reward。
这里我们便引出了n-step TD的想法，为了统一期间，我们把上一章提到的TD(0)也叫作one-step TD方法，下面给出了不同n的n-step方法的backup diagrams(关于这个图形这本书里见太多了，我的理解就是为了update Q(s,a)需要备份的episode产生的数据，比如state、action、reward等，但是像step size、epsilon、gamma等就不包含其中了，它们应该归于updating algorithm中):
接着给出n-step TD方法的核心更新公式的target：
关于这个更新规则真的不能在说什么了，注意下V的下标，t+n表示是使用的time=t+n的时候的估计值更新的V(S_t)。给出使用n-step TD方法的预测伪代码：
关于这个伪代码其实一眼看上去挺复杂的，但是几个关键的点理解之后就容易很多了:
1、每个episode的循环内部维护一个递增变量time，如果初始的state-action对是(S0,A0)，那么time在第一个循环值=1。对，time表征的就是当前的next state的index。
2、在time < n+1 之前，只进行state-action对的推进，并存储对应的reward和state。当time>=n+1后，按照更新规则进行更新。
3、当time>T后，因为剩下的后续state已经不足n个了，所以更新规则退化为MC方法的更新规则：target=G_{time-n+1}。(G is reutrn …)
例子可以参考 Example7.1 random walk 19-state
n-step Sarsa
如果弄明白了predict算法，那么控制方法自然是简单啦^_^。这里就讲了一个最简单的on-policy n-step Sarsa方法。
最简单的n-step Sarsa直接把上一部分需要评估的policy改为epsilon-greey就行了。当然这里没有用到的Q(s,a)都是不更新的，本章后面会讲到一种需要使用未出现的Q(s,a)的off-policy算法。
backup diagrams和n-step TD很相似了就不给出了，看一下n-step Sarsa的伪代码:
如果是Expected Sarsa那？给出核心更新规则的target：
n-step Off-policy Learning by Importance Sampling
引入重要采样因子解决off-policy，调和target policy使用behavior policy产生的数据更新Q(s,a)的问题，更新使用的target如下：
其中重要采样因子(importance sampling ratio)表达式为：
给出使用重要采样因子的off-policy控制算法伪代码:
Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm
off-policy控制算法可以不使用重要采样因子吗？答案是肯定的，不过我们需要借助于那些episode中没有被采用的state-action对的Q(s,a)来完成更新，下面给出backup diagrams：
可以看出tree backup algorithm保留了更多的state-action对。下面具体看一下这种算法是如何将未选用的state-action对引入更新规则的：
首先回顾一下Expected Sarsa的更新规则的target：
然后给出一个2-step的tree backup algorithm算法，是不是很容易理解：
顺水推舟，给出n-step更新规则target的递归定义：
注意虽然更新的时候使用了未被选中的state-action对，但是实际上它们用来更新的是选中的state-action的Q，所以自己的Q并没有被改变…
下面给出tree backup Algorithm的伪代码:
woc这次post粘了好多图…最近太懒了。如果岛学家什么时候打折了我可能就会精神一点✧(≖ ◡ ≖✿)