RL 学习笔记（8）：n 步自举法

本博客基于西安交通大学强化学习课程 PPT 改编，历经 Gemini 以及本人总结以及整理形成。

引言#

我们已经学习了两种主要的无模型强化学习方法：

一步时序差分 (One-step TD)：如 TD(0), Sarsa(0), Q-learning(0)。它们完全依赖自举 (Bootstrapping)，使用下一步的奖励 $R_{t+1}$ $R_{t + 1}$ 和下一状态的价值估计（ $V(S_{t+1})$ $V (S_{t + 1})$ 或 $Q(S_{t+1}, \cdot)$ $Q (S_{t + 1}, \cdot)$ ）来更新当前状态（或状态-动作对）的价值。
- 优点：方差低，可以在线学习，每步更新。
- 缺点：有偏（依赖于不准确的估计值）。
蒙特卡洛 (Monte Carlo, MC)：完全不使用自举。更新依赖于从当前状态直到 episode 结束的完整实际回报 $G_t$ 。
- 优点：无偏（基于真实回报）。
- 缺点：方差高，必须等待 episode 结束才能更新。

n 步自举法 (n-step Bootstrapping) 提供了一种在这两种极端之间进行平滑过渡的方法。其核心思想是：向前看 n 步 的实际奖励，然后使用第 n 步之后的状态的价值估计来进行自举。

当 $n=1$ 时，n 步法退化为一步 TD 方法。
当 $n=\infty$ （或 $n$ 足够大以覆盖到 episode 结束）时，n 步法等价于 MC 方法。

动机：通过调整步数 $n$ ，我们可以在偏差和方差之间进行权衡。通常，选择一个中间的 $n$ 值可以结合两者的优点，获得比纯粹的一步 TD 或纯 MC 更好的学习性能。

n 步 TD 预测 (估计 $V_\pi$ )#

目标：在遵循策略 $\pi$ 的情况下，估计状态价值函数 $V_\pi$ 。

n 步回报 (n-step Return) $G_{t:t+n}$ ：这是 n 步 TD 的核心。它结合了未来 n 步的实际奖励和第 n 步之后的价值估计。
$G_{t:t+n} \doteq R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n V_{t+n-1}(S_{t+n})$
其中 $V_{t+n-1}$ 表示在时间 $t+n$ 时可用的对 $V(S_{t+n})$ 的估计值（通常是 $t+n-1$ 时刻的估计）。
- 终止情况：如果在 $n$ 步内 episode 终止于时间 $T$ （即 $t+n \ge T$ ），则 n 步回报就是从 $t$ 开始的完整 MC 回报 $G_t$ 。 $G_{t:t+n} \doteq G_t \quad (\text{如果 } t+n \ge T)$
n 步 TD 更新规则：使用 n 步回报作为 TD 目标来更新状态 $S_t$ 的价值。
$V(S_t) \leftarrow V(S_t) + \alpha [G_{t:t+n} - V(S_t)]$
- 注意：这个更新实际上发生在时间 $t+n$ ，因为只有到那时我们才能观测到 $R_{t+n}$ 和 $S_{t+n}$ 并计算出 $G_{t:t+n}$ 。这意味着 n 步法需要缓存过去 n 步的状态和奖励。
算法：n 步 TD 预测：

算法参数: 步长 α ∈ (0, 1], 步数 n ≥ 1
初始化: V(s) 任意, 对所有 s ∈ S

循环 对每个 episode:
  初始化并存储状态序列 S = [S₀]
  初始化并存储奖励序列 R = [0] // R₀ 占位
  T ← ∞
  循环 t = 0, 1, 2, ... :
    如果 t < T:
      // 仍在 episode 内
      A ← 根据策略 π(·|Sₜ) 选择动作
      执行动作 A, 观察得到奖励 R_{t+1} 和下一状态 S_{t+1}
      将 R_{t+1} 存入 R 序列
      将 S_{t+1} 存入 S 序列
      如果 S_{t+1} 是终止状态:
        T ← t + 1
    // τ 是当前可以更新价值的时间步
    τ ← t - n + 1
    如果 τ ≥ 0:
      // 计算 n 步回报 G_{τ:τ+n}
      G ← 0
      对于 i = τ + 1 到 min(τ + n, T):
        G ← G + γ^(i - τ - 1) * Rᵢ
      如果 τ + n < T:
        G ← G + γ^n * V(S_{τ+n}) // 添加自举项

      // 更新状态 S_τ 的价值
      V(S_τ) ← V(S_τ) + α * [G - V(S_τ)]

    如果 τ = T - 1:
      终止内层循环 (episode 结束)

plaintext

误差减少性质：理论上，n 步回报的期望值比一步 TD 目标更接近真实价值 $v_\pi(s)$ ，其偏差随 $\gamma^n$ 衰减。

n 步同轨策略控制 (On-Policy Control)#

目标：学习动作价值函数 $Q_\pi$ ，并同时改进策略 $\pi$ （通常使用 $\epsilon$ -greedy）。

n 步 Sarsa#

n 步 Sarsa 回报 $G_{t:t+n}$ ：类似于 n 步 TD，但最后使用 Q 值进行自举。
$G_{t:t+n} \doteq R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})$
如果 $t+n \ge T$ ，则 $G_{t:t+n} \doteq G_t$ 。
n 步 Sarsa 更新规则：
$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [G_{t:t+n} - Q(S_t, A_t)]$
更新发生在时间 $t+n$ 。
算法：n 步 Sarsa：

算法参数: 步长 α ∈ (0, 1], 步数 n ≥ 1, 探索参数 ε > 0
初始化: Q(s, a) 任意, 对所有 s ∈ S⁺, a ∈ A(s), Q(终止状态, ·) = 0

循环 对每个 episode:
  初始化并存储状态序列 S = [S₀]
  初始化并存储奖励序列 R = [0]
  选择动作 A₀ ← 基于 Q 的 ε-greedy(S₀)
  初始化并存储动作序列 A = [A₀]
  T ← ∞
  循环 t = 0, 1, 2, ... :
    如果 t < T:
      执行动作 Aₜ, 观察奖励 R_{t+1} 和下一状态 S_{t+1}
      将 R_{t+1} 存入 R 序列
      将 S_{t+1} 存入 S 序列
      如果 S_{t+1} 是终止状态:
        T ← t + 1
      否则:
        选择动作 A_{t+1} ← 基于 Q 的 ε-greedy(S_{t+1})
        将 A_{t+1} 存入 A 序列
    // τ 是当前可以更新价值的时间步
    τ ← t - n + 1
    如果 τ ≥ 0:
      // 计算 n 步 Sarsa 回报 G_{τ:τ+n}
      G ← 0
      对于 i = τ + 1 到 min(τ + n, T):
        G ← G + γ^(i - τ - 1) * Rᵢ
      如果 τ + n < T:
        G ← G + γ^n * Q(S_{τ+n}, A_{τ+n}) // 添加自举项

      // 更新状态-动作对 (S_τ, A_τ) 的价值
      Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α * [G - Q(S_τ, A_τ)]

    如果 τ = T - 1:
      终止内层循环 (episode 结束)

plaintext

n 步期望 Sarsa (n-step Expected Sarsa)#

思想：为降低 n 步 Sarsa 回报的方差（因其依赖随机样本 $A_{t+n}$ ），在最后一步使用期望值代替采样值。
n 步期望 Sarsa 回报 $G_{t:t+n}$ ： $G_{t:t+n} \doteq R_{t+1} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n \sum_a \pi(a|S_{t+n}) Q(S_{t+n}, a)$ （如果 $t+n \ge T$ , 则 $G_{t:t+n} \doteq G_t$ ）
更新规则：与 n 步 Sarsa 相同，但使用期望 Sarsa 回报。
优点：通常方差更小，性能可能更稳定。

n 步离轨策略学习 (Off-Policy Learning)#

目标：使用行为策略 $\mu$ 生成的数据来学习目标策略 $\pi$ 的价值。

使用重要性采样 (Importance Sampling, IS)#

核心：通过乘以重要性采样率 (IS Ratio) $\rho$ 来校正由行为策略 $\mu$ 产生的回报。
n 步 IS 比率： $\rho_{t:h} \doteq \prod_{k=t+1}^{\min(h, T-1)} \frac{\pi(A_k|S_k)}{\mu(A_k|S_k)}$
n 步离轨 TD 更新 (估计 $V_\pi$ )： $V(S_t) \leftarrow V(S_t) + \alpha \rho_{t:t+n-1} [G_{t:t+n} - V(S_t)]$
- 注意范围： $\rho$ 只乘到 $t+n-1$ ，因为 $G_{t:t+n}$ 中的 $V(S_{t+n})$ 是对 $\pi$ 下价值的估计，不依赖于 $A_{t+n}$ 。
n 步离轨 Sarsa 更新 (估计 $Q_\pi$ )： $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \rho_{t+1:t+n} [G_{t:t+n} - Q(S_t, A_t)]$
- 注意范围： $\rho$ 乘到 $t+n$ ，因为 $G_{t:t+n}$ 中的 $Q(S_{t+n}, A_{t+n})$ 依赖于实际动作 $A_{t+n}$ 。
问题：高方差（尤其是 $n$ 较大或 $\pi, \mu$ 差异大时），需要满足覆盖性假设。

n 步树回溯算法 (n-step Tree Backup, TB)#

动机：实现离轨学习，同时避免 IS 的高方差。
核心思想：不使用 IS 比率，而是通过在每一步对目标策略 $\pi$ 下未被选择的动作进行期望回溯来构建目标。
n 步树回溯回报 $G_{t:t+n}^{(TB)}$ (用于 Q 值更新)：可以通过递归或迭代方式计算。其思想是在每个时间步 $k$ $k$ ( $t < k < t+n$ $t < k < t + n$ )，回报由实际奖励 $R_{k+1}$ $R_{k + 1}$ 加上一个对 $S_{k+1}$ $S_{k + 1}$ 处价值的估计组成，这个估计是根据目标策略 $\pi$ $π$ 对所有可能动作 $a$ $a$ 的价值 $Q(S_{k+1}, a)$ $Q (S_{k + 1}, a)$ （对于未采取的动作）或后续的树回溯回报（对于实际采取的动作 $A_{k+1}$ $A_{k + 1}$ ）进行加权平均得到的。
- 一步树回溯目标 ( $n=1$ )： $G_{t:t+1}^{(TB)} = R_{t+1} + \gamma \sum_{a'} \pi(a'|S_{t+1}) Q(S_{t+1}, a')$ ，这与期望 Sarsa 目标形式相同（但 $\pi$ 是目标策略）。
n 步树回溯更新规则： $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [G_{t:t+n}^{(TB)} - Q(S_t, A_t)]$
优点：离轨学习，无 IS 方差问题，不依赖于知道行为策略 $\mu$ 的概率。

统一视角：n 步 Q( $\sigma$ )#

思想：引入一个参数 $\sigma_t \in [0, 1]$ 来控制在每一步是进行采样 ( $\sigma_t=1$ ) 还是期望 ( $\sigma_t=0$ ) 回溯。
提供了一个统一的框架，可以平滑地连接 n 步 Sarsa (若 $\sigma=1$ 且使用 IS 校正) 和 n 步树回溯 (若 $\sigma=0$ )，以及它们之间的各种插值算法。
该框架比较复杂，通常用于更深入的理论研究或特定应用。

总结与讨论#

n 步自举法是 TD 和 MC 方法的自然推广，通过步数 $n$ 在偏差和方差之间进行权衡。
选择一个合适的中间值 $n$ 通常能获得比一步 TD 或 MC 更优的性能。
n 步方法包括用于预测的 n 步 TD，用于同轨控制的 n 步 Sarsa（及其期望版本），以及用于离轨控制的基于 IS 的方法和树回溯算法。
实践考量：n 步法需要缓存最近 $n$ 步的数据，并且更新会延迟 $n$ 步。计算复杂度与 $n$ 相关（主要是回报计算）。
这些思想是更高级方法（如资格迹 $TD(\lambda)$ ）的基础。

引言#

n 步 TD 预测 (估计 VπV_\piVπ​)#