第7章：n步自举方法（n-step Bootstrapping）
一、导读
1.1 本章学习目标
第7章介绍了 n 步方法，它统一了蒙特卡洛方法和单步 TD 方法。n 步方法使用 n 步回报作为更新目标，当 $n=1$ 时退化为 TD(0)，当 $n \to \infty$ 时退化为 MC。通过调整 $n$，可以在偏差和方差之间取得最佳平衡。
本章核心学习目标：
- 理解 n 步回报：使用 n 步真实奖励 + 第 n 步的估计价值
- 掌握 n 步 Sarsa 和 n 步 Q-learning
- 理解 $\lambda$-return 和 TD($\lambda$)：所有 n 步方法的加权平均
- 理解前向视图和后向视图：资格迹（eligibility trace）的直觉
1.2 为什么本章如此重要
n 步方法是理解 TD($\lambda$) 和现代强化学习算法的桥梁。它揭示了一个深刻的洞察：从 1 步 TD 到完整 MC 之间存在一个连续的谱系，不同的 n 值对应不同的偏差-方差权衡。在实际应用中，n=3 到 n=10 往往比 n=1 或 n=$\infty$ 表现更好。
1.3 核心问题引导
n 步回报与 1 步 TD 回报和完整 MC 回报有什么区别？
为什么 n 步方法通常比纯 1 步 TD 或纯 MC 表现更好？
TD($\lambda$) 如何统一所有 n 步方法？
资格迹（eligibility trace）的直觉是什么？它如何高效地实现 TD($\lambda$)？
二、核心概念详解
7.1 n 步回报
n 步回报 $G_{t:t+n}$ 使用接下来 n 步的真实奖励，加上第 n 步的价值估计：
$$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$$
当 $t+n \geq T$（回合终止）时，$G_{t:t+n}$ 就是完整的回报 $G_t$。
import numpy as np
from collections import defaultdict
class RandomWalk:
def __init__(self, n_states=19):
self.n_states = n_states
self.center = n_states // 2
self.true_values = np.arange(n_states + 2, dtype=float) / (n_states + 1)
def reset(self):
self.state = self.center + 1
return self.state
def step(self):
action = np.random.choice([-1, 1])
self.state += action
if self.state <= 0:
return 0, 0, True
if self.state >= self.n_states + 1:
return self.n_states + 1, 1, True
return self.state, 0, False
def n_step_td(env_factory, n=3, alpha=0.1, gamma=1.0, n_episodes=100):
env = env_factory()
V = np.zeros(env.n_states + 2)
for ep in range(n_episodes):
state = env.reset()
trajectory = []
done = False
T = float('inf')
t = 0
while True:
if t < T:
next_state, reward, done = env.step()
trajectory.append((state, reward))
if done:
T = t + 1
state = next_state
tau = t - n + 1
if tau >= 0:
G = sum(gamma**i * trajectory[tau+i][1]
for i in range(min(n, T) - tau))
if tau + n < T:
G += gamma**n * V[trajectory[tau+n][0]]
state_to_update = trajectory[tau][0]
if 1 <= state_to_update <= env.n_states:
V[state_to_update] += alpha * (G - V[state_to_update])
t += 1
if tau == T - 1:
break
return V
for n in [1, 3, 10, float('inf')]:
n_int = int(n) if n != float('inf') else 1000
V = n_step_td(RandomWalk, n=n_int, alpha=0.1, n_episodes=200)
env = RandomWalk()
true_v = env.true_values[1:-1]
estimated = V[1:-1]
rms = np.sqrt(np.mean((estimated - true_v)**2))
print(f"n={int(n) if n != float('inf') else 'inf'}: RMSE = {rms:.4f}")7.2 n 步 Sarsa
n 步 Sarsa 将 n 步回报的思想应用到动作价值函数：
$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [G_{t:t+n} - Q(S_t, A_t)]$$
其中 $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})$
def n_step_sarsa(env_factory, n=3, alpha=0.5, gamma=0.99, epsilon=0.1, n_episodes=500):
env = env_factory()
n_actions = 4
Q = defaultdict(lambda: np.zeros(n_actions))
for ep in range(n_episodes):
state = env.reset()
trajectory = []
done = False
T = float('inf')
action = np.argmax(Q[state]) if np.random.random() > epsilon else np.random.randint(n_actions)
trajectory.append((state, action, 0))
t = 0
while True:
if t < T:
next_state, reward, done = env.step(action)
if not done:
next_action = np.argmax(Q[next_state]) if np.random.random() > epsilon else np.random.randint(n_actions)
else:
next_action = None
trajectory.append((next_state, next_action, reward))
if done:
T = t + 1
state = next_state
action = next_action
tau = t - n + 1
if tau >= 0:
G = sum(gamma**i * trajectory[tau+i+1][2]
for i in range(min(n, T) - tau))
if tau + n < T:
s_n, a_n, _ = trajectory[tau+n]
G += gamma**n * Q[s_n][a_n]
s_tau, a_tau, _ = trajectory[tau]
Q[s_tau][a_tau] += alpha * (G - Q[s_tau][a_tau])
t += 1
if tau == T - 1:
break
return Q7.3 $\lambda$-return 和 TD($\lambda$)
TD($\lambda$) 是所有 n 步回报的加权平均。使用指数衰减权重 $(1-\lambda)\lambda^{n-1}$：
$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}$$
当 $\lambda = 0$ 时，$G_t^\lambda = G_{t:t+1}$（1 步 TD）；当 $\lambda = 1$ 时，$G_t^\lambda = G_t$（MC）。
7.4 资格迹（Eligibility Trace）
资格迹 $e_t(s)$ 记录了状态 $s$ 在最近被访问的"资格"。TD($\lambda$) 的后向视图使用资格迹来高效地分配信用：
$$e_t(s) = \gamma \lambda e_{t-1}(s) + \mathbf{1}(S_t = s)$$
$$V(s) \leftarrow V(s) + \alpha \delta_t e_t(s) \quad \forall s$$
def td_lambda(env_factory, lam=0.5, alpha=0.1, gamma=1.0, n_episodes=100):
env = env_factory()
V = np.zeros(env.n_states + 2)
for ep in range(n_episodes):
state = env.reset()
E = np.zeros(env.n_states + 2)
done = False
while not done:
next_state, reward, done = env.step()
delta = reward + gamma * V[next_state] - V[state]
E[state] += 1
for s in range(1, env.n_states + 1):
V[s] += alpha * delta * E[s]
E[s] *= gamma * lam
state = next_state
return V
for lam in [0, 0.3, 0.5, 0.8, 1.0]:
V = td_lambda(RandomWalk, lam=lam, alpha=0.1, n_episodes=200)
env = RandomWalk()
true_v = env.true_values[1:-1]
rms = np.sqrt(np.mean((V[1:-1] - true_v)**2))
print(f"lambda={lam}: RMSE = {rms:.4f}")三、实战案例
3.1 案例：不同 n 值的性能对比
def compare_n_steps(n_runs=20, n_episodes=200):
n_values = [1, 2, 4, 8, 16, float('inf')]
alphas = {1: 0.1, 2: 0.1, 4: 0.08, 8: 0.05, 16: 0.03, float('inf'): 0.01}
results = {}
for n in n_values:
rms_errors = []
for run in range(n_runs):
n_int = int(n) if n != float('inf') else 1000
V = n_step_td(RandomWalk, n=n_int, alpha=alphas[n], n_episodes=n_episodes)
env = RandomWalk()
true_v = env.true_values[1:-1]
rms = np.sqrt(np.mean((V[1:-1] - true_v)**2))
rms_errors.append(rms)
results[n] = np.mean(rms_errors)
print("n-step TD comparison:")
for n, rms in results.items():
n_str = str(int(n)) if n != float('inf') else 'inf'
print(f" n={n_str}: avg RMSE = {rms:.4f}")
compare_n_steps(n_runs=5, n_episodes=100)四、本章小结
n 步方法统一了 MC 和 1 步 TD，通过调整 n 在偏差和方差之间取得平衡
n 步 Sarsa/Q-learning：将 n 步回报应用到控制问题
TD($\lambda$)：所有 n 步方法的指数加权平均
资格迹：高效实现 TD($\lambda$) 的后向视图
五、思考与练习
思考题
为什么 n=3 到 n=10 在实践中往往比 n=1 或 n=$\infty$ 表现更好？
资格迹的衰减因子 $\lambda$ 如何影响信用分配的范围？
TD($\lambda$) 的前向视图和后向视图为什么是等价的？
编程练习
在随机游走问题上画出不同 n 值的 RMS 误差曲线
实现 n 步 Q-learning 并在 Cliff Walking 上测试
比较 TD($\lambda$) 和 n-step TD 的收敛速度