强化学习数学原理 - 第7章：时序差分方法 (Temporal-Difference Methods)

1. TD：结合 MC 与 DP 的艺术

时序差分 (TD) 是强化学习中最核心、最独特、最优雅的思想。它不需要像 DP 那样已知模型，也不需要像 MC 那样等到 Episode 结束。它边走边学 (Bootstrapping from Experience)。

核心公式 (TD(0)):
$$ V(S_t) < V(S_t) + α [ R_{t+1} + γ V(S_{t+1}) - V(S_t) ]
$$

直观解释：

Target: 我走了这一步，拿到了 $R_{t+1}$，加上我对下一步状态价值的预估 $γ V(S_{t+1})$，我觉得这才是更靠谱的价值。
Error: 那个 Target 和我原来的估计 $V(S_t)$ 之间的差，就是惊讶程度 (TD Error)。
Update: 用这个差乘以学习率 $α$ 来修正我的观念。

2. Sarsa: On-policy 的稳健派

2.1 算法流程 (State-Action-Reward-State-Action)

Sarsa 之所以叫 Sarsa，是因为它一次更新需要的数据五元组是 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$。

$$ Q(S_t, A_t) < Q(S_t, A_t) + α [ R_{t+1} + γ Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) ]
$$

关键点：$A_{t+1}$ 是 Agent 实际将在下一步执行的动作（通常由 $ε$-greedy 选出）。这意味着 Sarsa 在优化的是它正在执行的那个策略（On-policy）。如果策略比较“浪”（$ε$ 很大），Sarsa 就会学得比较保守，远离悬崖。

2.2 Python 实现 (Sarsa)

def sarsa(env, num_episodes, alpha=0.1, gamma=0.9, epsilon=0.1):
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    
    for i in range(num_episodes):
        state = env.reset()
        action = epsilon_greedy(Q, state, epsilon) # 选动作 A
        
        while True:
            next_state, reward, done = env.step(action)
            next_action = epsilon_greedy(Q, next_state, epsilon) # 选动作 A'
            
            # Sarsa 更新
            td_target = reward + gamma * Q[next_state][next_action] * (not done)
            Q[state][action] += alpha * (td_target - Q[state][action])
            
            if done: break
            state, action = next_state, next_action
            
    return Q

3. Q-learning: Off-policy 的激进派

3.1 算法流程

Q-learning 的更新公式只有一点点不同，但引起了质变：

$$ Q(S_t, A_t) < Q(S_t, A_t) + α [ R_{t+1} + γ Q(S_{t+1}, a) - Q(S_t, A_t) ]
$$

关键点：不管下一步实际做什么，我在计算 Target 时都假设我下一步会做最好的动作 ($ Q$ )。
这意味着 Q-learning 学习的是最优策略 (Off-policy)，哪怕它实际行为策略是在乱走。

3.2 Sarsa vs Q-learning (悬崖漫步例子)

视频中经典的 Cliff Walking 例子完美展示了区别：

环境: 走到悬崖边掉下去会得 -100 分。
Q-learning: 学出一条紧贴悬崖边的最短路径（它假设自己是最优的，不会手滑）。但在训练时（因为有 $ε$），它经常掉下去。
Sarsa: 学出一条远离悬崖的安全路径。因为它知道自己有 $ε$ 的概率乱走，走悬崖边太危险了。

3.3 Python 实现 (Q-learning)

def q_learning(env, num_episodes, alpha=0.1, gamma=0.9, epsilon=0.1):
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    
    for i in range(num_episodes):
        state = env.reset()
        
        while True:
            action = epsilon_greedy(Q, state, epsilon) # 行为策略
            next_state, reward, done = env.step(action)
            
            # Q-learning 更新：直接取 max，无视 next_action
            best_next_action = np.argmax(Q[next_state])
            td_target = reward + gamma * Q[next_state][best_next_action] * (not done)
            
            Q[state][action] += alpha * (td_target - Q[state][action])
            
            if done: break
            state = next_state
            
    return Q

4. 统一视角

我们可以把 MDP 中的各种算法看作是同一公式的不同变体：
$$ ext{NewEstimate} < ext{OldEstimate} + ext{StepSize} imes [ ext{Target} - ext{OldEstimate}]
$$

算法	Target 是什么？	样本来源
MC	$G_t$ (真实回报)	一整条 Episode
DP (VI)	$[R + γ V(S’)]$	遍历所有 $S’$ (模型计算)
Sarsa	$R + γ Q(S’, A’)$	采样一步 $(S, A, R, S’, A’)$
Q-learning	$R + \gamma \max Q(S’, a)$	采样一步 $(S, A, R, S’)$

5. 深度思考：偏差与方差的权衡 (Bias-Variance Trade-off)

为什么我们要发明 TD？为什么不直接用 MC？这就涉及机器学习核心的偏差 (Bias) 与 方差 (Variance) 权衡。

5.1 MC (Monte Carlo)

Target: $G_t$ (真实回报)。
无偏差 (Unbiased): $G_t$ 是 $v_\pi(s)$ 的无偏估计。
高方差 (High Variance): $G_t$ 依赖于从 $t$ 到结束的所有随机转移和奖励。路途越长，随机因素积累越多，波动越大。
后果: 即使数据很多，训练也很震荡，收敛慢。

5.2 TD (Temporal Difference)

Target: $R + \gamma V(S’)$ (估计值)。
有偏差 (Biased): 我们用了估计值 $V(S’)$ 来更新 $V(S)$。如果 $V(S’)$ 估计错了，Target 也就错了。
低方差 (Low Variance): Target 只依赖一步的随机性 $R_{t+1}$ 和 $S_{t+1}$。后面的随机性被 $V(S’)$ 概括了。
后果: 收敛快，但初始阶段可能跑偏（因为信了错误的估计）。

5.3 n-step TD：最佳平衡点

我们可以折中一下，看 $n$ 步再截断：
$$ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n}) $$

$n=1$: TD(0)，低方差，高偏差。
$n=\infty$: MC，高方差，无偏差。
结论: 调节 $n$ (或者使用 $\lambda$-return) 可以找到方差与偏差的最佳平衡点，通常 $n=3 \sim 5$ 效果最好。

6. 总结

本章我们掌握了 RL 的两把利器：

Sarsa: 稳健，适合在线控制，关心“活在当下”的风险。
Q-learning: 激进，适合模拟训练，直接瞄准“理论最优”。

但目前我们用的表格法 (Tabular Method) 有个致命弱点：状态空间太大存不下怎么办？ (比如像素点组成的图像)。
下一章，我们将引入 函数近似 (Function Approximation)，也就是 Deep RL 的前夜 —— DQN 的基础。

上一章：第6章 - 随机近似 | 下一章：第8章 - 值函数近似 >>