3.2 Temporal-Difference、Q-Learning 与探索：一次更新并不代表已经学会
探索机器人每走一步才看见结果，工坊必须决定是等整局结束再总结，还是用下一状态的估计立即更新。
机器人不知道风会把它吹向哪里，只能记录实际转移 $(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\max_aQ(S_{t+1},a)-Q(S_t,A_t)]. $$
行为可以 epsilon-greedy，target 却使用 greedy max，因此 Q-learning 是 off-policy control。
一个更完整的 tabular agent：
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):
bootstrap = 0.0 if terminal else self.q[next_state, next_legal].max()
target = reward + self.gamma * bootstrap
self.q[state, action] += self.alpha * (
target - self.q[state, action]
)旧实现无论 next_state 是否 terminal 都 bootstrap，会把终局后的虚构价值加入 target；argmax 还总偏向第一个平局动作。
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 中，若：
- 所有状态动作被无限次访问；
- 学习率满足相应随机逼近条件；
- 奖励有界、环境平稳；
- 折扣/终止使 return 定义良好；
则 tabular Q-learning 可收敛到 $Q^*$（标准条件下）。固定学习率和提前停止通常只得到近似稳定。
看见平均回报上升不证明 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 就稳定：仍需诊断函数近似与覆盖。
练习
- 手算同一轨迹的 MC、TD(0)、SARSA 与 Q-learning target。
- 构造 terminal bootstrap bug，观察终局 Q 被高估。
- 在悬崖环境比较 SARSA 与 Q-learning 的训练/评估路线。
- 用五个随机种子报告回报分布和状态动作覆盖。
小结
TD 方法用当前估计帮助学习未来估计，因此样本效率和稳定性依赖 target、探索和覆盖。Q-learning 的一行公式只有在终局、合法动作和收敛条件被正确实现时才有意义。
下一课直接参数化策略，并讨论高方差、actor-critic、离线数据和安全评估。