第6章：时序差分学习（Temporal-Difference Learning）
一、导读
1.1 本章学习目标
第6章介绍强化学习中最重要的无模型方法——时序差分（TD）学习。TD 方法结合了蒙特卡洛方法和动态规划的优点：它像 MC 一样不需要环境模型、直接从经验学习，又像 DP 一样使用自举（bootstrapping）——用估计值来更新估计值。
本章的核心学习目标包括：
- 理解 TD(0) 的核心思想：用下一步的估计值来更新当前估计
- 掌握 TD 与 MC 的区别：TD 不需要等到回合结束，可以逐步更新
- 理解 TD 方法的偏差-方差权衡：有偏但低方差
- 掌握 Sarsa（on-policy）和 Q-learning（off-policy）
- 理解 TD 控制方法的收敛性
1.2 为什么本章如此重要
TD 学习是强化学习中最核心的算法家族。从经典的 Tabular Q-learning 到现代的 DQN、PPO，几乎所有实用的强化学习算法都建立在 TD 学习的基础上。
TD 方法的独特之处在于它可以从不完整的序列中学习——不需要等到回合结束。这使得 TD 方法可以应用于持续性任务（没有终止的任务），并且通常比 MC 方法收敛更快（虽然是有偏的）。
1.3 核心问题引导
TD 方法如何在不知道环境模型的情况下实现自举？
TD(0) 的更新规则是什么？它与 MC 的更新规则有什么本质区别？
为什么 TD 方法是有偏的？这个偏差会导致什么问题？
Sarsa 和 Q-learning 的区别是什么？为什么 Q-learning 是 off-policy 的？
在实际应用中，应该选择 TD 还是 MC？取决于哪些因素？
二、核心概念详解
6.1 TD(0)：最基本的时序差分方法
TD(0) 的更新规则极其简单：
$$V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$$
其中 $R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 称为 TD 误差（TD error），记为 $\delta_t$。
python
import numpy as np
from collections import defaultdict
class RandomWalk:
def __init__(self, n_states=7):
self.n_states = n_states
self.center = n_states // 2
self.terminal_left = 0
self.terminal_right = n_states - 1
self.true_values = np.zeros(n_states)
for i in range(1, n_states - 1):
self.true_values[i] = (i - self.terminal_left) / (self.terminal_right - self.terminal_left)
def reset(self):
self.state = self.center
return self.state
def step(self):
action = np.random.choice([-1, 1])
self.state += action
if self.state <= self.terminal_left:
return self.state, 0, True
if self.state >= self.terminal_right:
return self.state, 1, True
return self.state, 0, False
def td_zero(env_factory, n_episodes=100, alpha=0.1, gamma=1.0):
env = env_factory()
V = np.zeros(env.n_states)
for ep in range(n_episodes):
state = env.reset()
done = False
while not done:
next_state, reward, done = env.step()
V[state] += alpha * (reward + gamma * V[next_state] - V[state])
state = next_state
return V
def mc_zero(env_factory, n_episodes=100, alpha=0.01, gamma=1.0):
env = env_factory()
V = np.zeros(env.n_states)
returns = defaultdict(list)
for ep in range(n_episodes):
state = env.reset()
episode = []
done = False
while not done:
next_state, reward, done = env.step()
episode.append((state, reward))
state = next_state
G = 0
for t in range(len(episode) - 1, -1, -1):
s, r = episode[t]
G += r
returns[s].append(G)
V[s] = np.mean(returns[s])
return V
env = RandomWalk(7)
print("True values:", np.round(env.true_values, 3))
V_td = td_zero(RandomWalk, n_episodes=1000, alpha=0.1)
print("TD(0) values:", np.round(V_td, 3))
V_mc = mc_zero(RandomWalk, n_episodes=1000, alpha=0.01)
print("MC values:", np.round(V_mc, 3))
print("\nRMS Error:")
true_v = env.true_values[1:-1]
print(f" TD(0): {np.sqrt(np.mean((V_td[1:-1] - true_v)**2)):.4f}")
print(f" MC: {np.sqrt(np.mean((V_mc[1:-1] - true_v)**2)):.4f}")6.2 TD 误差与自举
TD 方法的核心特征是自举（bootstrapping）：用 $V(S_{t+1})$ 的当前估计来更新 $V(S_t)$ 的估计。这与 DP 类似，但 TD 不需要知道转移概率——它直接从采样中获得 $R_{t+1}$ 和 $S_{t+1}$。
TD 误差 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 衡量了"实际观测到的价值"与"预期价值"之间的差距。当 $\delta_t = 0$ 时，说明当前的价值估计与观测一致。
6.3 Sarsa：On-policy TD 控制
Sarsa 是 TD 方法在控制问题中的直接推广。它使用 TD 误差来更新动作价值函数 $Q$：
$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$$
名字 Sarsa 来源于它使用的五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$。
python
class CliffWalking:
def __init__(self, width=12, height=4):
self.width = width
self.height = height
self.start = (height - 1, 0)
self.goal = (height - 1, width - 1)
self.cliff = [(height - 1, c) for c in range(1, width - 1)]
self.actions = [(-1,0),(1,0),(0,-1),(0,1)]
def reset(self):
self.state = self.start
return self.state
def step(self, action):
dr, dc = self.actions[action]
r, c = self.state
nr, nc = max(0, min(self.height-1, r+dr)), max(0, min(self.width-1, c+dc))
if (nr, nc) in self.cliff:
self.state = self.start
return self.state, -100, False
self.state = (nr, nc)
reward = -1
done = self.state == self.goal
return self.state, reward, done
def sarsa(env_factory, n_episodes=1000, alpha=0.5, gamma=0.99, epsilon=0.1):
env = env_factory()
Q = defaultdict(lambda: np.zeros(4))
for ep in range(n_episodes):
state = env.reset()
if np.random.random() < epsilon:
action = np.random.randint(4)
else:
action = np.argmax(Q[state])
done = False
while not done:
next_state, reward, done = env.step(action)
if np.random.random() < epsilon:
next_action = np.random.randint(4)
else:
next_action = np.argmax(Q[next_state])
td_target = reward if done else reward + gamma * Q[next_state][next_action]
Q[state][action] += alpha * (td_target - Q[state][action])
state = next_state
action = next_action
return Q
Q_sarsa = sarsa(CliffWalking, n_episodes=2000)
print("Sarsa learned policy (sample states):")
action_names = ['up', 'down', 'left', 'right']
for state in [(3,0), (2,0), (2,1)]:
best_a = np.argmax(Q_sarsa[state])
print(f" {state}: {action_names[best_a]}")6.4 Q-learning：Off-policy TD 控制
Q-learning 是最重要的强化学习算法之一。它的更新规则与 Sarsa 几乎相同，唯一的区别是：Q-learning 在更新时使用贪心动作的价值，而不是实际执行的动作的价值：
$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)]$$
这意味着 Q-learning 的目标策略是贪心的，而行为策略是 $\epsilon$-greedy 的。这就是为什么 Q-learning 是 off-policy 的。
python
def q_learning(env_factory, n_episodes=1000, alpha=0.5, gamma=0.99, epsilon=0.1):
env = env_factory()
Q = defaultdict(lambda: np.zeros(4))
for ep in range(n_episodes):
state = env.reset()
done = False
while not done:
if np.random.random() < epsilon:
action = np.random.randint(4)
else:
action = np.argmax(Q[state])
next_state, reward, done = env.step(action)
best_next = np.max(Q[next_state])
td_target = reward if done else reward + gamma * best_next
Q[state][action] += alpha * (td_target - Q[state][action])
state = next_state
return Q
Q_ql = q_learning(CliffWalking, n_episodes=2000)
print("Q-learning learned policy (sample states):")
for state in [(3,0), (2,0), (2,1)]:
best_a = np.argmax(Q_ql[state])
print(f" {state}: {action_names[best_a]}")6.5 Sarsa vs Q-learning 的对比
python
def compare_sarsa_qlearning(n_runs=50, n_episodes=1000):
sarsa_rewards = np.zeros(n_episodes)
ql_rewards = np.zeros(n_episodes)
for run in range(n_runs):
env = CliffWalking()
Q_s = defaultdict(lambda: np.zeros(4))
Q_q = defaultdict(lambda: np.zeros(4))
for ep in range(n_episodes):
state = env.reset()
action_s = np.argmax(Q_s[state]) if np.random.random() > 0.1 else np.random.randint(4)
done = False
ep_reward_s = 0
ep_reward_q = 0
while not done:
next_state, reward, done = env.step(action_s)
ep_reward_s += reward
next_action_s = np.argmax(Q_s[next_state]) if np.random.random() > 0.1 else np.random.randint(4)
target_s = reward if done else reward + 0.99 * Q_s[next_state][next_action_s]
Q_s[state][action_s] += 0.5 * (target_s - Q_s[state][action_s])
target_q = reward if done else reward + 0.99 * np.max(Q_q[next_state])
Q_q[state][action_s] += 0.5 * (target_q - Q_q[state][action_s])
ep_reward_q += reward
state = next_state
action_s = next_action_s
sarsa_rewards[ep] += ep_reward_s
ql_rewards[ep] += ep_reward_q
sarsa_rewards /= n_runs
ql_rewards /= n_runs
print("Sarsa vs Q-learning on Cliff Walking:")
print(f" Sarsa avg reward (last 100 ep): {np.mean(sarsa_rewards[-100:]):.1f}")
print(f" Q-learning avg reward (last 100 ep): {np.mean(ql_rewards[-100:]):.1f}")
compare_sarsa_qlearning(n_runs=10, n_episodes=500)6.6 TD 方法的偏差-方差权衡
| 特性 | MC | TD(0) |
|---|---|---|
| 偏差 | 无偏 | 有偏（自举引入） |
| 方差 | 高（依赖完整回合） | 低（只依赖一步） |
| 收敛性 | 收敛到 $v_\pi$ | 在 tabular 情况下收敛 |
| 样本效率 | 低 | 较高 |
| 适用场景 | 回合制任务 | 回合制和持续性任务 |
三、实战案例
3.1 案例一：TD 与 MC 在随机游走上的对比
python
def td_mc_comparison(n_episodes_list=[10, 50, 100, 500], alpha_td=0.1, alpha_mc=0.01):
env = RandomWalk(7)
true_v = env.true_values
for n_ep in n_episodes_list:
V_td = td_zero(RandomWalk, n_episodes=n_ep, alpha=alpha_td)
V_mc = mc_zero(RandomWalk, n_episodes=n_ep, alpha=alpha_mc)
rms_td = np.sqrt(np.mean((V_td - true_v)**2))
rms_mc = np.sqrt(np.mean((V_mc - true_v)**2))
print(f"Episodes={n_ep}: TD RMSE={rms_td:.4f}, MC RMSE={rms_mc:.4f}")
td_mc_comparison()3.2 案例二：Wind Grid World
python
class WindGridWorld:
def __init__(self):
self.width = 10
self.height = 7
self.start = (3, 0)
self.goal = (3, 7)
self.wind = [0, 0, 0, 1, 1, 1, 2, 2, 1, 0]
self.actions = [(-1,0),(1,0),(0,-1),(0,1),
(-1,-1),(-1,1),(1,-1),(1,1),(0,0)]
def reset(self):
self.state = self.start
return self.state
def step(self, action):
dr, dc = self.actions[action]
r, c = self.state
w = self.wind[c]
nr = max(0, min(self.height - 1, r + dr - w))
nc = max(0, min(self.width - 1, c + dc))
self.state = (nr, nc)
reward = -1
done = self.state == self.goal
return self.state, reward, done
def sarsa_wind_grid(n_episodes=5000, alpha=0.5, gamma=1.0, epsilon=0.1):
env = WindGridWorld()
n_actions = len(env.actions)
Q = defaultdict(lambda: np.zeros(n_actions))
episode_lengths = []
for ep in range(n_episodes):
state = env.reset()
action = np.argmax(Q[state]) if np.random.random() > epsilon else np.random.randint(n_actions)
done = False
steps = 0
while not done:
next_state, reward, done = env.step(action)
next_action = np.argmax(Q[next_state]) if np.random.random() > epsilon else np.random.randint(n_actions)
target = reward if done else reward + gamma * Q[next_state][next_action]
Q[state][action] += alpha * (target - Q[state][action])
state = next_state
action = next_action
steps += 1
episode_lengths.append(steps)
return Q, episode_lengths
Q, lengths = sarsa_wind_grid()
print(f"Wind Grid World: final episode length = {lengths[-1]}")
print(f"Average length (last 100): {np.mean(lengths[-100:]):.1f}")四、本章小结
第6章介绍了时序差分学习，核心要点：
TD(0)：用一步的 TD 误差来更新价值估计，结合了 MC 的无模型特性和 DP 的自举特性
TD 误差：$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$，衡量预期与实际的差距
Sarsa：on-policy TD 控制，使用实际执行的下一步动作
Q-learning：off-policy TD 控制，使用贪心动作的价值，是最经典的 RL 算法
偏差-方差权衡：TD 有偏但低方差，MC 无偏但高方差
五、思考与练习
思考题
为什么 Q-learning 在 tabular 情况下保证收敛到最优策略？
如果步长 $\alpha$ 不满足 Robbins-Monro 条件（$\sum \alpha = \infty, \sum \alpha^2 < \infty$），Q-learning 会怎样？
在什么场景下 Sarsa 比 Q-learning 更安全（更保守）？为什么？
编程练习
在 Cliff Walking 上比较 Sarsa 和 Q-learning 的学习曲线
实现 Double Q-learning 来解决 Q-learning 的最大化偏差问题
在 Wind Grid World 上测试不同的 $\alpha$ 和 $\epsilon$ 值