此为《强化学习》第七章 n-step Bootstrapping 。

$n$ 步Bootstrapping是MC和TD(0)的综合。随着对参数 $n$ 的调整，我们可以看到TD是如何过渡到MC的。而最佳的方法往往就是介于TD和MC之间。

$n$ 步TD估计

在上一章的TD(0)方法中，我们有

v (S_{t}) \leftarrow v (S_{t}) + α (G_{t} - v (S_{t}))

并且，我们使用了一步后的状态值函数来估计 $G_{t}$ ，从而得到

v (S_{t}) \leftarrow v (S_{t}) + α [R_{t + 1} + γ v (S_{t + 1}) - v (S_{t})]

那么如果我们考虑 $n$ 步，那么显然 $G_{t}$ 也可以使用以下等式进行估计：

\begin{aligned} G_{t} & = R_{t + 1} + γ v (S_{t + 1}) \\ = R_{t + 1} + γ R_{t + 2} + γ^{2} v (S_{t + 2}) \\ = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} v (S_{t + n}) \end{aligned}

在书本中，上面每个 $v$ 都会有一个下标，表示此处的值函数是哪一步迭代的值函数。但实际上，我们只有一个表格用来存值函数，所以实践上应该很容易知道到底是哪一步迭代的，因此这里省略不写（可见下文伪代码即可知）。令上述表达式为 $G_{t : t + n}$ ，则算法TD(n)为

v (S_{t}) \leftarrow v (S_{t}) + α [G_{t : t + n} - v (S_{t})]

如果 $t + n = T$ ，那么TD(n)将成为MC。在回溯图中，我们可以看到TD(n)包含了从TD(0)到MC的所有算法。

《强化学习Sutton》读书笔记（六）——n步Bootstrapping（n-step Bootstrapping）

TD(n)的伪代码如下：

稍微解释一下。第一个循环当然是针对episode，第二个循环是在一个episode中产生样本。第一个if表示如果该episode没有结束，那么就继续采样；if后的 $τ$ 表示已经执行的步数和 $n - 1$ 的差。如果 $τ < 0$ ，就说明 $n$ 步还没有走完，当然没有任何可以迭代的；如果 $τ \geq 0$ ，则进入第二个if，使用 $n$ 步后的状态值函数 $v (S_{τ + n})$ 来更新 $v (S_{τ})$ 。

$n$ 步Sarsa

考虑完状态值函数，下一步当然是行为值函数。过程几乎完全一样，先定义 $G_{t : t + n}$ ：

G_{t} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} Q (S_{t + n}, A_{t + n})

因此 $n$ 步Sarsa更新表达式为：

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [G_{t : t + n} - Q (S_{t}, A_{t})]

它的回溯图如下：

伪代码如下：

和之前TD(n)相比，除了值函数的变化，唯一的不同是增加了策略改良的步骤（倒数第二行），但这只是一个非常熟悉的 $ϵ$ -贪心而已，毕竟Sarsa只是一个On-Policy的算法。

我们也可以尝试扩展Expected Sarsa到 $n$ 步。从下面的回溯图中可以看到，Expected Sarsa仅仅在最后一步使用了值函数的期望，并没有每一步都使用。我猜想可能是因为如果每一步都做成期望，那么随着树的展开，计算量将指数级增长。不过我不清楚是否存在两步使用期望的Expected Sarsa算法。

表达式如下：

G_{t} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} \sum_{a} π (a | S_{t + n}) Q (S_{t + n}, a) Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [G_{t : t + n} - Q (S_{t}, A_{t})]

$n$ 步Off-Policy学习

在MC一章中第一次提出Off-Policy方法的时候，我们需要求解一个重要性采样系数。当时由于是MC方法，因此需要求 $ρ_{t : T - 1}$ ，而在 $n$ 步的方法中，只需要求解 $ρ_{t : t + n - 1}$ ，但过程是极其类似的。

ρ_{t : t + n - 1} = \prod_{k = t}^{min {t + n - 1, T - 1}} \frac{π (A_{k} | S_{k})}{b (A_{k} | S_{k})}

在每次更新值函数的时候，我们需要乘上 $ρ_{t + 1 : t + n}$ ，即

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α ρ_{t + 1 : t + n} [G_{t : t + n} - Q (S_{t}, A_{t})]

在MC一章中，我们提到过普通重要性采样和加权重要性采样。我个人认为，这里这样的更新式应该是基于普通重要性采样的。照抄一下第四篇里基于加权重要性的公式：

v_{n + 1} (s) = v_{n} (s) + \frac{W_{n + 1}}{C_{n + 1}} (G_{n + 1} - v_{n} (s))

这里的 $W$ 几乎就是这章中的 $ρ$ ，但显然没有对应的 $C_{n} = \sum_{k = 1}^{n} W_{n}$ 。如果考虑基于普通重要性采样，那么把上式中的分母去掉就好了，另外 $α$ 实际上对应这经过状态 $s$ 的次数，这样两边就说得通了。

$n$ 步Off-Policy方法的伪代码如下：

注意决策（目标策略）使用的是纯贪心，而数据生成（行为策略）使用的是探索性的策略。

* 单次决策法与决策变量

略。

不带重要性采样的 $n$ 步Off-Policy学习

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

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

可以看到，树回溯的最后一步和一步Expected Sarsa是一致的，即一层的树回溯法得到的回报为

G_{t : t + 1} = R_{t + 1} + γ \sum_{a} π (a | S_{t + 1}) Q (S_{t + 1}, a)

两层的树回溯法就有点不同了，在倒数第二层的分支中，每个实际中不会被选择的行为值函数将被计入回报，而实际中选择的行为将作为下一层的回报间接计入，即

\begin{aligned} G_{t : t + 2} & = R_{t + 1} + γ \sum_{a \neq A_{t + 1}} π (a | S_{t + 1}) Q (S_{t + 1}, a) + γ π (A_{t + 1} | S_{t + 1}) [R_{t + 2} + γ \sum_{a} π (a | S_{t + 2}) Q (S_{t + 2}, a)] \\ = R_{t + 1} + γ \sum_{a \neq A_{t + 1}} π (a | S_{t + 1}) Q (S_{t + 1}, a) + γ π (A_{t + 1} | S_{t + 1}) G_{t + 1 : t + 2} \end{aligned}

这里的表达式启示我们可以用递归的方法来定义和求解 $G_{t : t + n}$ ，即

G_{t : t + n} = R_{t + 1} + γ \sum_{a \neq A_{t + 1}} π (a | S_{t + 1}) Q (S_{t + 1}, a) + γ π (A_{t + 1} | S_{t + 1}) G_{t + 1 : t + n}

于是更新行为值函数的表达式为

Q (S_{t}, A_{t}) = Q (S_{t}, A_{t}) + α [G_{t : t + n} - Q (S_{t}, A_{t})]

在阅读这一节时，我有好几个疑问。首先，注意到 $π$ 是纯贪心得到的，因此上述式子中许多 $π (a | s)$ 将等于0，一方面树看起来将变成棍子，另一方面由于行为策略 $b$ 不一定选择了 $π$ 认定最优的路线，因此树高也可能发生变化。我一度认为这看起来是不合理的，把它们都改成了 $b$ 。然而，改成 $b$ 之后，这将不再是一个Off-Policy的方法了。因此，我认为这里确实应该是 $π$ ，也确实会出现许多的0，使用 $π (a | s)$ 只是另一种形式的最大化。

第二个问题是，为什么树回溯法是Off-Policy的？在每一步选择中，数据（具体的行为）都是由行为策略 $b$ 来生成的，但更新的算法隐含了最大化，因此和Q-Learning一样，它是按照目标策略 $π$ 来更新值函数的。假如 $n$ 步的中间某一步不是最优的，那么它下面的树的权重将全是0，不会对值函数产生影响。需要注意的是，在2017年草稿及以前的版本中，伪代码里使用了 $ϵ$ -贪心的算法来生成 $π$ ，我认为这是不对的（这样就是On-Policy方法了），且已在2018年草稿中得到更正。

第三个问题是，为什么这样就不需要重要性采样了？我个人的理解是，和Q-Learning类似，采用重要性采样的根本原因是避免行为策略 $b$ 做出一些非常差的行为，从而拉低了上一行为的值函数，而实际上目标策略 $π$ 却根本不会考虑这样差的行为（可见上一章）。这里，我们使用了目标策略 $π$ 作为更新的算法，通过隐含的最大化去掉了可能的差行为对上一行为的影响，所以就不需要重要性采样了。

n步树回溯法伪代码如下：

* 一种统一的算法：n步Q( $σ$ )

略。

参考文献

《Reinforcement Learning: An Introduction (second edition)》Richard S. Sutton and Andrew G. Barto

上一篇：《强化学习Sutton》读书笔记（五）——时序差分学习（Temporal-Difference Learning）
下一篇：暂无

《强化学习Sutton》读书笔记（六）——n步Bootstrapping（n-step Bootstrapping）

nn步TD估计

nn步Sarsa

nn步Off-Policy学习