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

本内容暂时为 PPT 转述，后续会进行修编

n 步自举法 (n-step Bootstrapping) 概述#

引入：在 TD 和 MC 之间 (Page 2-4)#

回顾 (Page 2)：
- Sarsa (同轨 TD)：学习动作价值函数 $Q_\pi(s, a)$ 。其 TD 目标是基于下一步的实际奖励和动作价值估计： $y_t = R_{t+1} + \gamma Q_\pi(S_{t+1}, A_{t+1})$ （注意：PPT Page 2 的 $r_t$ 应该是指 $S_t, A_t$ 之后获得的奖励，标准记法是 $R_{t+1}$ 。Q 函数下标 $\pi$ 表明是针对策略 $\pi$ 的价值）。
- Q-Learning (离轨 TD)：学习最优动作价值函数 $Q^\*(s, a)$ 。其 TD 目标是基于下一步的实际奖励和最优后续价值估计： $y_t = R_{t+1} + \gamma \max_{a'} Q^*(S_{t+1}, a')$ （同样，PPT Page 2 的 $r_t$ 应为 $R_{t+1}$ ）
自举法的谱系 (Spectrum of Bootstrapping Methods) (Page 3-4)：
- 强化学习方法可以看作是在一个谱系上，一端是蒙特卡洛 (Monte Carlo, MC) 方法，另一端是一步时序差分 (One-step Temporal Difference, TD) 方法（如 Sarsa(0), Q-learning(0), TD(0)）。
- MC：不使用自举 (Bootstrapping)。更新依赖于完整的回报 $G_t$ （从当前状态直到 épisode 结束的所有奖励的折扣和）。只有在 épisode 结束后才能进行更新。方差较高，但无偏（如果样本足够）。
- 一步 TD：完全依赖自举。更新依赖于下一步的奖励 $R_{t+1}$ 和下一步状态的价值估计 $V(S_{t+1})$ 或 $Q(S_{t+1}, A_{t+1})$ 或 $\max_{a'}Q(S_{t+1}, a')$ 。每一步之后都可以立即更新。方差较低，但有偏（因为依赖于可能不准确的价值估计）。
- n 步自举法：介于两者之间。它向前看 n 步 的实际奖励，然后使用第 n 步之后的状态的价值估计来进行自举。
  - 当 $n=1$ 时，n 步法退化为一步 TD 方法。
  - 当 $n=\infty$ 时（或 $n$ 大于等于当前状态到 épisode 结束的步数时），n 步法等价于 MC 方法。
- 动机 (Page 4)：通过调整步数 $n$ ，可以在偏差和方差之间进行权衡。通常，选择一个中间的 $n$ 值（既不是 1 也不是 $\infty$ ）可以获得比纯 TD 或纯 MC 更好的性能。

n 步 TD 预测 (n-step TD Prediction)#

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

回顾目标 (Page 5)：
- MC 目标：完整回报 $G_t \doteq R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$
- 一步 TD 目标 (TD(0))： $G_{t:t+1} \doteq R_{t+1} + \gamma V_t(S_{t+1})$ （ $V_t$ 表示 $t$ 时刻的价值估计）
n 步回报 (n-step Return) $G_{t:t+n}$ (Page 6)：
- 定义：从时间 $t+1$ $t + 1$ 开始，累积 $n$ $n$ 步的折扣奖励，并加上 $n$ $n$ 步之后的状态 $S_{t+n}$ $S_{t + 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})$
  - 解释：这个回报混合了 $n$ 步的实际奖励和第 $n$ 步的估计未来价值。 $V_{t+n-1}$ 指的是在时间 $t+n$ 进行更新时，可用的（即 $t+n-1$ 时刻或之前的）对 $V(S_{t+n})$ 的估计值。
- 终止情况：如果在 $n$ 步内（即在时间 $t+n$ 或之前）épisode 终止（到达终止状态 $S_T$ ），则 n 步回报就是从 $t$ 开始的完整回报 $G_t$ 。 $G_{t:t+n} \doteq G_t \quad (\text{如果 } t+n \ge T)$ 这保证了当 $n$ 足够大时，n 步回报等于 MC 回报。
n 步 TD 更新规则 (Page 7)：
- 使用 n 步回报 $G_{t:t+n}$ 作为 TD 目标来更新状态 $S_t$ 的价值。 $V_{t+n}(S_t) \leftarrow V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)]$
- 关键点：对状态 $S_t$ 的价值更新发生在时间 $t+n$ ，也就是在观察到 $R_{t+n}$ 和 $S_{t+n}$ 之后。这与一步 TD 不同，一步 TD 在 $t+1$ 时刻就更新 $V(S_t)$ 。这意味着 n 步法需要存储过去 $n$ 步的状态和奖励。

算法：n 步 TD 预测 (Page 8)：

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

对 每个 episode 循环:
    初始化并存储 S_0 ≠ 终止状态
    存储 R_0 = 0 // 实际不会用到，占位符
    T ← ∞
    对 t = 0, 1, 2, ... 循环:
        如果 t < T:
            采取动作 A_t (根据策略 π, 对于 S_t)
            观察并存储下一奖励 R_{t+1} 和下一状态 S_{t+1}
            如果 S_{t+1} 是终止状态:
                T ← t + 1
        τ ← t - n + 1 (τ 是正在被更新的时间步)
        如果 τ ≥ 0:
            计算 n 步回报 G:
                G ← Σ_{i=τ+1}^{min(τ+n, T)} γ^{i-τ-1} R_i
            如果 τ + n < T:
                G ← G + γ^n V(S_{τ+n}) // 使用 τ+n 时刻的 V 估计
            // 更新状态 S_τ 的价值
            V(S_τ) ← V(S_τ) + α [G - V(S_τ)]
        如果 τ = T - 1:
            终止循环 (épisode 结束)

plaintext

解释：算法维护一个存储窗口（或队列）来保存最近的状态和奖励。当时间 $t$ 前进时，最早的状态 $S_\tau$ （其中 $\tau = t-n+1$ ）的更新所需的所有信息 ( $R_{\tau+1}, \dots, R_{\min(\tau+n, T)}$ 以及 $S_{\tau+n}$ （如果 $\tau+n\<T$ ））都已经获得，于是可以计算 $G_{\tau:\tau+n}$ 并更新 $V(S_\tau)$ 。

误差减少性质 (Error Reduction Property) (Page 9)：
- n 步回报的期望值与真实价值 $v_\pi(s)$ 之间的差距，其上界与 $n$ 步之后价值估计的最大误差有关，并且以 $\gamma^n$ 的速度衰减。 $\max_s |\mathbb{E}_\pi[G_{t:t+n}|S_t=s] - v_\pi(s)| \le \gamma^n \max_{s'} |V_{t+n-1}(s') - v_\pi(s')|$
- 含义：如果价值函数的估计误差是有界的，那么 n 步回报的期望值会比一步 TD 目标（ $n=1$ ）更接近真实价值 $v_\pi(s)$ （因为 $\gamma^n$ 随着 $n$ 增大而减小）。这为 n 步法通常优于一步 TD 提供了一定的理论依据。

n 步 Sarsa (用于同轨策略控制 On-policy Control)#

目标：学习动作价值函数 $Q_\pi$ ，并根据 $Q_\pi$ 改进策略 $\pi$ (通常是 $\epsilon$ -greedy)。

回顾目标 (Page 10)：
- MC 目标: $G_t$ (用于更新 $Q(S_t, A_t)$ )
- Sarsa(0) 目标: $G_{t:t+1} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$
n 步 Sarsa 回报 ( $G_{t:t+n}$ ) (Page 11)：
- 定义：类似于 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_{t+n-1}(S_{t+n}, A_{t+n})$
- 终止情况：如果 $t+n \ge T$ ，则 $G_{t:t+n} \doteq G_t$ 。
n 步 Sarsa 更新规则 (Page 12)：
- 使用 n 步 Sarsa 回报作为目标来更新状态-动作对 $(S_t, A_t)$ 的价值。 $Q_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n} - Q_{t+n-1}(S_t, A_t)]$
- 更新时机：同样，更新发生在时间 $t+n$ 。

算法：n 步 Sarsa (Page 13)：

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

对 每个 episode 循环:
    初始化并存储 S_0 ≠ 终止状态
    使用从 Q 推导的策略 (例如 ε-greedy) 选择并存储 A_0
    存储 R_0 = 0, A_{-1} = 0 // 占位符
    T ← ∞
    对 t = 0, 1, 2, ... 循环:
        如果 t < T:
            执行动作 A_t
            观察并存储下一奖励 R_{t+1} 和下一状态 S_{t+1}
            如果 S_{t+1} 是终止状态:
                T ← t + 1
            否则:
                使用从 Q 推导的策略 (例如 ε-greedy, 基于 Q_{t+n-1} 或 Q_t) 选择并存储 A_{t+1}
        τ ← t - n + 1 (τ 是正在被更新的时间步)
        如果 τ ≥ 0:
            计算 n 步回报 G:
                G ← Σ_{i=τ+1}^{min(τ+n, T)} γ^{i-τ-1} R_i
            如果 τ + n < T:
                G ← G + γ^n Q(S_{τ+n}, A_{τ+n}) // 使用 Q_{t+n-1} 的估计
            // 更新状态-动作对 (S_τ, A_τ) 的价值
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α [G - Q(S_τ, A_τ)]
        如果 τ = T - 1:
            终止循环 (épisode 结束)

plaintext

解释：与 n 步 TD 类似，但存储的是 $(S_t, A_t, R_{t+1})$ 序列。更新 $Q(S_\tau, A_\tau)$ 需要直到 $A_{\tau+n}$ 被选定（如果是 $\tau+n < T$ 的情况）。

n 步期望 Sarsa (n-step Expected Sarsa) (Page 14)：
- 思想：为了降低 n 步 Sarsa 的方差（因为它依赖于 $A_{t+n}$ 这个随机样本），在最后一步使用期望值代替采样值。
- n 步期望 Sarsa 回报 ( $G_{t:t+n}$ ) (Page 14 公式)： $G_{t:t+n} \doteq R_{t+1} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n \bar{Q}_{t+n-1}(S_{t+n})$ 其中 $\bar{Q}*{t+n-1}(S*{t+n}) \doteq \sum_a \pi(a|S_{t+n}) Q_{t+n-1}(S_{t+n}, a)$ 是在状态 $S_{t+n}$ 处根据当前策略 $\pi$ 的期望动作价值。
- 更新规则： $Q_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n} - Q_{t+n-1}(S_t, A_t)]$
- 优点：通常比 n 步 Sarsa 方差更小，计算量稍大（需要计算期望）。

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

目标：使用由行为策略 $\mu$ 生成的数据 ${S_t, A_t, R_{t+1}, \dots}$ 来学习目标策略 $\pi$ 的价值函数 ( $V_\pi$ 或 $Q_\pi$ )。

方法一：使用重要性采样 (Importance Sampling, IS) (Page 15-20)#

挑战 (Page 15)：直接使用行为策略 $\mu$ 产生的 n 步回报来更新目标策略 $\pi$ 的价值是有偏的，因为奖励和后续状态的分布不同。
解决方案：重要性采样 (Page 16)：通过乘以一个修正因子——重要性采样率 (Importance Sampling Ratio) $\rho$ ——来调整回报的期望值。
n 步重要性采样率 ( $\rho_{t:h}$ ) (Page 16)：从时间 $t+1$ 到时间 $h$ 之间，目标策略 $\pi$ 选择实际发生的动作序列 $A_{t+1}, \dots, A_h$ 的概率与行为策略 $\mu$ 选择同样序列的概率之比。 $\rho_{t:h} \doteq \prod_{k=t+1}^{\min(h, T-1)} \frac{\pi(A_k|S_k)}{\mu(A_k|S_k)}$ （注意指数上界是 $\min(h, T-1)$ ，因为 $A_T$ 没有定义）。
n 步离轨 TD 更新 (Page 17)：用 IS 比率修正 n 步 TD 回报。 $V_{t+n}(S_t) \leftarrow V_{t+n-1}(S_t) + \alpha \rho_{t:t+n-1} [G_{t:t+n} - V_{t+n-1}(S_t)]$
- 注意 $\rho$ 的范围：IS 比率只乘到 $\rho_{t:t+n-1}$ ，即 $A_{t+1}$ 到 $A_{t+n-1}$ 。因为 $G_{t:t+n}$ 仅依赖于这些动作来产生 $R_{t+1}, \dots, R_{t+n}$ 和 $S_{t+n}$ 。而 $V(S_{t+n})$ 是我们对目标策略价值的估计，与 $A_{t+n}$ 如何选择无关。
n 步离轨 Sarsa 更新 (Page 18)：用 IS 比率修正 n 步 Sarsa 回报。 $Q_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha \rho_{t+1:t+n} [G_{t:t+n} - Q_{t+n-1}(S_t, A_t)]$
- 注意 $\rho$ 的范围：这里 IS 比率乘到 $\rho_{t+1:t+n}$ ，包含了 $A_{t+n}$ 。因为 $G_{t:t+n}$ 中的 $Q(S_{t+n}, A_{t+n})$ 项依赖于实际采取的动作 $A_{t+n}$ 。我们需要校正从 $S_{t+1}$ 到 $A_{t+n}$ 这一整段路径的概率。
重要性采样的问题 (Page 19)：
- 高方差：当 $n$ 很大，或者 $\pi$ 和 $\mu$ 相差很大时， $\rho$ 的乘积可能变得非常大或非常接近于 0，导致更新极其不稳定（方差爆炸）。
- 对 $\mu$ 的要求：行为策略 $\mu$ 必须覆盖目标策略 $\pi$ ，即 $\pi(a|s) \> 0 \implies \mu(a|s) \> 0$ 。
算法：带重要性采样的 n 步离轨 TD (Page 20)：给出了预测 $V_\pi$ 的伪代码，展示了如何计算和使用 $\rho_{t:t+n-1}$ 。

方法二：n 步树回溯算法 (n-step Tree Backup, TB) (Page 21-25)#

动机 (Page 21)：实现离轨学习，同时避免重要性采样带来的高方差问题。
核心思想 (Page 21 图示)：不使用 IS 比率，而是通过对目标策略 $\pi$ 下未被选择的动作进行期望回溯来构造目标。它结合了 Q-learning 的 $\max$ (隐式在目标策略 $\pi$ 中，如果 $\pi$ 是贪心的话) 和 Expected Sarsa 的期望思想，并扩展到 n 步。
回顾一步情况：
- Expected Sarsa (on-policy): $R_{t+1} + \gamma \sum_a \pi(a|S_{t+1}) Q(S_{t+1}, a)$
- Tree Backup (1-step, off-policy): 与 Expected Sarsa 形式相同，但 $\pi$ 是目标策略，而数据来自 $\mu$ 。
n 步树回溯回报 ( $G_{t:t+n}^{(TB)}$ ) (Page 22-23)：
- 递归定义 (更容易理解)：
  - 基础 ( $k=t+n-1$ ): $G_{t+n-1:t+n}^{(TB)} = R_{t+n} + \gamma \sum_{a'} \pi(a'|S_{t+n}) Q_{t+n-1}(S_{t+n}, a')$ (这正是期望 Sarsa 的目标)
  - 递归步骤 (对 $k$ 从 $t+n-2$ 向下到 $t$ ): $G_{k:t+n}^{(TB)} = R_{k+1} + \gamma \sum_{a \neq A_{k+1}} \pi(a|S_{k+1}) Q_{t+n-1}(S_{k+1}, a) + \gamma \pi(A_{k+1}|S_{k+1}) G_{k+1:t+n}^{(TB)}$
- 解释 (Page 22, 2-step case)：在 $S_{k+1}$ 处，我们观察到了实际执行的动作 $A_{k+1}$ (由 $\mu$ 产生) 和奖励 $R_{k+2}$ 。目标策略 $\pi$ 会以 $\pi(A_{k+1}|S_{k+1})$ 的概率选择 $A_{k+1}$ ，这种情况下，后续的回报由 $G_{k+1:t+n}^{(TB)}$ 给出。对于所有其他未被选择的动作 $a \neq A_{k+1}$ ，目标策略 $\pi$ 会以 $\pi(a|S_{k+1})$ 的概率选择它们，由于我们没有实际观察到这些路径，我们使用它们当前的 Q 值估计 $Q_{t+n-1}(S_{k+1}, a)$ 作为这些分支的价值。这两部分加权求和构成了从 $S_{k+1}$ 开始的期望回报（根据 $\pi$ ）。最后加上实际获得的 $R_{k+1}$ 。
- 终止情况：如果 $k+1 \ge T$ ，则 $G_{k:t+n}^{(TB)} = R_{k+1}$ 。
n 步树回溯更新规则 (Page 24)： $Q_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n}^{(TB)} - Q_{t+n-1}(S_t, A_t)]$
算法：n 步树回溯 (Page 25)：给出了计算 $G^{(TB)}$ 并更新 Q 值的伪代码。
优点：
- 实现了离轨学习。
- 没有使用重要性采样，避免了高方差问题。
- 只需要目标策略 $\pi$ 的信息，不需要行为策略 $\mu$ 的信息（ $\mu$ 仅用于生成数据）。

统一视角：n 步 Q( $\sigma$ ) (Page 26-29)#

动机 (Page 26)：提供一个统一的框架，可以涵盖 n 步 Sarsa、n 步 Expected Sarsa/Tree Backup 以及它们之间的插值。
参数 $\sigma$ (Page 27)：引入一个状态（或状态-动作）相关的参数 $\sigma_t \in [0, 1]$ $σ_{t} \in [0, 1]$ 来控制在每一步是进行采样 ( $\sigma_t=1$ $σ_{t} = 1$ ) 还是期望 ( $\sigma_t=0$ $σ_{t} = 0$ )。
- $\sigma = 1$ : 对应 Sarsa (采样下一个动作 $A_{t+1}$ )。
- $\sigma = 0$ : 对应 Expected Sarsa 或 Tree Backup (对下一个动作求期望)。
n 步 Q( $\sigma$ ) 回报 ( $G_{t:h}^{(\sigma)}$ ) (Page 28 公式)：这个回报的定义比较复杂，似乎是混合了重要性采样和期望操作。 $G_{t:h}^{(\sigma)} \doteq R_{t+1} + \gamma \left( \sigma_{t+1} \rho_{t+1} + (1-\sigma_{t+1})\pi(A_{t+1}|S_{t+1}) \right) (G_{t+1:h}^{(\sigma)} - Q_{h-1}(S_{t+1}, A_{t+1})) + \gamma \bar{V}_{h-1}(S_{t+1})$ 其中，
- $h = t+n$
- $\bar{V}*{h-1}(s) \doteq \sum_a \pi(a|s)Q*{h-1}(s,a)$ (状态的期望价值)
- $\rho_{t+1} = \frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})}$ (一步 IS 比率)
- 基础: $G_{h:h}^{(\sigma)} \doteq Q_{h-1}(S_h, A_h)$ (注意这里使用的是 $Q(S_h, A_h)$ 而不是期望 $\bar{V}(S_h)$ )
n 步 Q( $\sigma$ ) 更新 (Page 28)： $Q_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n}^{(\sigma)} - Q_{t+n-1}(S_t, A_t)]$
特殊情况 (Page 29)：
- 当所有 $\sigma_k = 1$ (始终采样)：这似乎对应于带 IS 的 n 步 Sarsa。
- 当所有 $\sigma_k = 0$ (始终期望)：这对应于 n 步 Tree Backup 算法。
意义：Q( $\sigma$ ) 提供了一个灵活的框架，允许在采样和期望之间进行平滑过渡，可能找到比纯粹方法更好的中间点。

总结 (Page 30)#

n 步方法是 TD 和 MC 方法的推广，通过步数 $n$ 控制自举的程度。
$n=1$ 对应一步 TD， $n=\infty$ 对应 MC。
中间的 $n$ 值 通常表现最好，能在偏差和方差之间取得更好的平衡。
适用于连续任务和分幕式任务。
计算成本：需要存储最近 $n$ 步的转移信息（状态、动作、奖励），学习更新会延迟 $n$ 步。但每步计算量相对均匀。
易于扩展：这些思想可以进一步推广到更复杂的方法，如资格迹 (Eligibility Traces, 结合不同 $n$ 的回报) 和更通用的 $Q(\sigma)$ 框架。