3.2 Temporal-Difference、Q-Learning 与探索：一次更新并不代表已经学会

智能体每执行一步才观察到转移结果。学习算法必须决定：等待整个 episode 结束后使用实际 return，还是立刻用下一状态的估计更新当前值。

例如机器人记录实际转移 $(S_t,A_t,R_{t+1},S_{t+1})$。等整局结束再使用回报，反馈较迟；用下一步估计能立即更新，却会把当前估计误差带进目标。更新得早，不等于学得准。

本课目标

• 区分 Monte Carlo 与 Temporal-Difference target；
• 正确处理 Q-learning 的 terminal、合法动作与随机 tie；
• 理解 on-policy SARSA 与 off-policy Q-learning；
• 说明 tabular 收敛条件和函数近似风险。

1. Monte Carlo 与 TD(0)

Monte Carlo 等 episode 完成，用实际 return 更新：

$$V(S_t)\leftarrow V(S_t)+\alpha [G_t-V(S_t)].$$

它不 bootstrap，但必须等到 return 可知，方差通常较高。

TD(0) 使用一步 target：

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)].$$

TD 可以在线更新，target 的方差较低但带 bootstrap bias。不存在“TD 总优于 MC”的通用结论。

2. Q-Learning backup

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \underset{a}{max}Q(S_{t+1},a)-Q(S_t,A_t)].$$

行为可以 epsilon-greedy，target 却使用 greedy max，因此 Q-learning 是 off-policy control。

下面是 Python 3 + NumPy 片段（partial），省略环境交互循环。调用者传入有效状态索引、合法动作索引列表，以及范围内的 alpha、gamma、epsilon；随机并列选择与终局更新在类内处理。

import numpy as np

class TabularQLearning:
    def __init__(self, n_states, n_actions, alpha, gamma, epsilon, seed=0):
        self.q = np.zeros((n_states, n_actions), dtype=float)
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.rng = np.random.default_rng(seed)

    def act(self, state, legal_actions):
        legal = np.asarray(legal_actions, dtype=int)
        if len(legal) == 0:
            raise ValueError("non-terminal state has no legal actions")
        if self.rng.random() < self.epsilon:
            return int(self.rng.choice(legal))

        values = self.q[state, legal]
        best = legal[np.flatnonzero(values == values.max())]
        return int(self.rng.choice(best))

    def update(self, state, action, reward, next_state, terminal, next_legal):
        if terminal:
            bootstrap = 0.0
        else:
            legal = np.asarray(next_legal, dtype=int)
            if legal.ndim != 1 or len(legal) == 0:
                raise ValueError("non-terminal next state needs legal actions")
            bootstrap = self.q[next_state, legal].max()
        target = reward + self.gamma * bootstrap
        self.q[state, action] += self.alpha * (
            target - self.q[state, action]
        )

真正 terminal 的 target 只有即时奖励，即使 next Q 表中意外有非零值也不能加入。例如 reward 为 2、gamma 为 0.9、next Q 为 100，终局 target 仍是 2；同样的非终局转移才得到 92。terminal 应来自任务终止标志，不能把单纯的采样截断混进来。

3. SARSA 学行为策略的价值

SARSA target 使用实际下一动作：

$$R_{t+1}+\gamma Q(S_{t+1},A_{t+1}).$$

若行为为 epsilon-greedy，它学习的是包含探索风险的策略价值。悬崖行走中，SARSA 可能选择离悬崖更远的路线；Q-learning target 假设以后贪心，可能偏好更短但探索时危险的路线。

“off-policy 更好”不成立。选择取决于要评估/优化的 target policy、数据来源和重要性修正。

4. 探索不是一个固定 epsilon 公式

Epsilon-greedy 简单，却不利用不确定性：所有非贪心动作等概率。可选方法：

• optimistic initialization；
• decaying epsilon；
• UCB/置信上界；
• Boltzmann/softmax exploration；
• intrinsic motivation；
• posterior sampling。

“从 1.0 指数衰减到 0.01”不是通用建议。衰减取决于 horizon、访问频率、非平稳性和安全成本。部署中持续随机探索可能伤人，需要模拟器、约束动作或审批。

5. Tabular Q-Learning 的收敛有条件

经典有限 MDP 中，若：

• 所有状态动作被无限次访问；
• 对每个状态动作对的第 k 次更新，学习率满足 $\sum _k{\alpha }_k=\mathrm{\infty }$ 且 $\sum _k{\alpha }_k^2<\mathrm{\infty }$；
• 奖励有界、环境平稳；
• 折扣/终止使 return 定义良好；

在有限折扣 MDP 的这些标准条件下，tabular Q-learning 几乎必然收敛到 $Q^{\ast }$；无折扣情形还需吸收等额外条件，见 Watkins 与 Dayan 的原始论文。上面的示例使用固定学习率，不能用这个定理声称它已收敛。步长条件和有限折扣情形的完整证明也可查 Regehr 与 Ayoub 的推导，第 5 节。

看见平均回报上升不证明 Q 表收敛，也不证明部署分布表现。

6. Maximization bias 与 Double Q-Learning

max 会偏好带正噪声的估计，造成过估计。Double Q-learning 用一套估计选择动作、另一套评估，减少该偏差。深度版本对应 Double DQN 思路。

这不是保证低估/无偏；函数近似和数据分布仍影响结果。

7. Eligibility traces

TD($\lambda$) 用 eligibility trace 把当前 TD error 传播给近期状态，连接一步 TD 与 Monte Carlo。$\lambda =0$ 接近 TD(0)，$\lambda$ 趋近 1 时更接近长 return（具体等价条件需注意 online/offline 版本）。

n-step returns 同样在 bias、variance 和延迟间折中。

8. 从 Q 表到函数近似

连续/巨大状态不能逐项存表，可用 $Q(s,a;\theta )$。这不是“Q-learning 立刻失效”：可先 tile coding、线性函数或离散化；神经网络只是一个选择。

off-policy + bootstrap + function approximation 被称为 deadly triad，可能不稳定甚至发散。DQN 使用：

• replay buffer 打破相邻样本相关并复用经验；
• target network 延缓 target 漂移；
• gradient clipping、reward scaling 等工程控制。

这些缓解不构成普遍收敛保证。Replay 还会改变数据分布，旧经验在非平稳环境中可能有害。

9. 训练曲线怎样读

分开记录：

• 训练行为（含探索）回报；
• 固定评估策略回报；
• episode 长度、成功率和失败类型；
• 状态动作覆盖；
• TD error 与 Q 值范围；
• 多随机种子分布和置信区间。

只展示最优 seed 或最后 100 局平均，会隐藏不稳定和选择偏差。

常见误区

• 终局 next Q 也照常加入：真正 terminal 不应 bootstrap。
• epsilon 越快变小越快收敛：可能永远没探索关键动作。
• Q-learning 一定比 SARSA 强：两者目标策略不同。
• 用了 replay 和 target network 就稳定：仍需诊断函数近似与覆盖。

练习

1. 手算同一轨迹的 MC、TD(0)、SARSA 与 Q-learning target。
2. 构造 terminal bootstrap bug，观察终局 Q 被高估。
3. 在悬崖环境比较 SARSA 与 Q-learning 的训练/评估路线。
4. 用五个随机种子报告回报分布和状态动作覆盖。

小结

TD 方法用当前估计帮助学习未来估计，因此样本效率和稳定性依赖 target、探索和覆盖。Q-learning 的一行公式只有在终局、合法动作和收敛条件被正确实现时才有意义。

下一课直接参数化策略，并讨论高方差、actor-critic、离线数据和安全评估。