TARGET
读完后，你应能从零写出 Q-learning，并能解释每一个符号为何存在。
| 你要能做的事 | 不是只会背什么 | 现实中用来判断什么 |
|---|---|---|
| 从最优动作价值 Q* 的定义推导 Q-learning target。 | 不是只记 r + γ max Q。 | target 是否写对、terminal 是否 mask、γ 是否改变任务含义。 |
| 分开 behavior policy 与 target policy。 | 不是只知道它叫 off-policy。 | 为什么 ε-greedy 收集的数据能用于学习 greedy 策略；何时这种迁移会变危险。 |
| 手算连续三次更新并解释信息怎样逆向传播。 | 不是只会调用一个训练循环。 | 调试 Q 值不动、异常高估、训练回报与评估回报背离。 |
0 · WHAT PROBLEM DOES IT SOLVE?
Q-learning 求的不是“当前策略的分数”，而是最优决策的动作价值。
在有限 MDP 中，给定当前 state s 并强制先做动作 a，之后每一步都可以自由选最优动作。该条件下的最佳期望回报叫最优动作价值：
若有 Q*，控制就变得平凡：在每个状态选择 argmaxaQ*(s,a)。困难是我们通常不知道环境转移 P 和平均 reward，无法直接把 Q* 算出来。
Q-learning 是无模型（model-free）、离策略（off-policy）、表格型 TD 控制算法。“无模型”表示不需提前知道 P；“离策略”表示用一个行为策略收集数据，却学习另一个 greedy 目标策略；“TD”表示只看一步真实反馈，再用估计值补未来。
1 · THE EQUATION BEFORE THE ALGORITHM
先有最优 Bellman 方程，才有更新式。
如果环境模型 P(s′,r|s,a) 已知，我们可以枚举动作后的所有可能后继。最优性原理说：当前先拿到 r，抵达 s′ 后就再次选择最优动作。因此：
| 符号 | 在方程里的精确职责 | 常见误读 |
|---|---|---|
| s,a | 正在评估的当前状态和已选动作。 | max 不会重新选择当前 a；当前 a 已被条件固定。 |
| s′,r | 环境对 (s,a) 的随机后继与单步反馈。 | r 不是整局 return，只是一小步证据。 |
| γ | 把未来回报映射到今天的权重。 | 不是“为了收敛随便调小”；它改变优化的长期偏好。 |
| maxa′Q*(s′,a′) | 下一状态若从此以后完美决策，最好的继续价值。 | 不是行为策略实际将选的动作价值。 |
这一方程定义了最优 Bellman 算子 T*。求解就是找固定点：Q*=T*Q*。已知模型时可用 value iteration；Q-learning 的工作是：没有 P 时，怎样用真实采样替代这层期望。
2 · FROM EXPECTATION TO ONE SAMPLE
一条 transition 为什么能参与学习？它是期望里的一个带噪样本。
在状态 s 做 a 后，环境实际只给你一份观测 (r,s′)，而不是完整的 P 分布。把最优 Bellman 右侧中的随机变量记为：
E[Y | s,a] = (T*Q)(s,a)一次交互得到的 y=r+γmax Q(s′,·) 不等于完整期望；它是该期望的单个样本。重复访问同一 (s,a) 才能逐步抵消抽样噪声。
于是我们不把 Q(s,a) 直接改成 y，而采取随机逼近的增量平均形式：
yt = rt+1 + γ maxa′Qt(st+1,a′)方括号是 TD error：若样本 target 高于当前估计，Q 上调；反之下调。α 控制本次样本的可信权重。其余表格格子在这一刻不变。
3 · WHY OFF-POLICY IS POSSIBLE
行为在探索，target 却假设贪心：这不是矛盾，而是刻意分工。
Q-learning 用 ε-greedy 行为策略 μ 收集 transition，以保证不是只反复走当前最爱的一条路；但 target 使用 maxa′Q(s′,a′)，它学习的是确定性 greedy 目标策略 π*。于是：
| 对象 | 写法 | 它决定什么 | Q-learning 中的选择 |
|---|---|---|---|
| 行为策略 μ | a ~ μ(·|s) | 今天实际访问哪些 transition。 | 通常 ε-greedy(Q)，以维持覆盖。 |
| 目标策略 π | π(s)=argmaxaQ(s,a) | 我们最终想优化／部署谁。 | greedy(Q)，不把探索失手写进 target。 |
| 学习目标 | r+γmax Q(s′,·) | 对 π 的一步最优性承诺。 | 与实际 a′ 无关。 |
“离策略”不代表可以用任意历史数据、毫无条件地学任何目标。表格 Q-learning 仍需要覆盖：若 μ 永远不访问某个关键 (s,a)，它的 Q 没有样本来修正。深度网络里，数据分布漂移、分布外动作、bootstrapping 会让这个问题更尖锐，这正是 offline RL 与 conservative value learning 的动机。
4 · THREE UPDATES BY HAND
只看公式仍抽象；用一个两步世界追踪 Q 的每一次变化。
环境：A 只有 go，到 B 得 r=0；B 有 safe（终止，r=+4）和 risky（终止，r=−6）。令 γ=0.9、α=0.5，所有 Q 初始为 0。行为策略在 B 先探索到 safe。
| 时间 | 实际 transition | target 的计算 | TD error / 写回 | 信息在哪里 |
|---|---|---|---|---|
| t=0 | (A,go) → r=0,B | max[Q(B,safe),Q(B,risky)]=max(0,0)=0 y=0+0.9×0=0 | δ=0−Q(A,go)=0 Q(A,go) 仍是 0 | 终点 reward 尚未传回；这不是失败，是 bootstrap 的局部传播。 |
| t=1 | (B,safe) → r=+4, terminal | terminal 没有未来：y=4 | δ=4−0=4 Q(B,safe)=0+0.5×4=2 | safe 的直接价值先被学到。 |
| t=2（下一局） | (A,go) → r=0,B | max(2,0)=2 y=0+0.9×2=1.8 | δ=1.8−0=1.8 Q(A,go)=0.9 | B 的价值沿 transition 逆向传给 A。 |
| t=3（再一局） | (A,go) → r=0,B | y 仍为 1.8 | δ=1.8−0.9=0.9 Q(A,go)=1.35 | 固定 α=0.5 时，Q(A,go) 逐步靠近 1.8。 |
第一，终止状态必须令未来项为 0；若错误地继续 max Q(terminal,·)，会把不存在的未来收益泄漏进 target。第二，Q(A,go) 的真值应为 γ×4=3.6，而上表暂时只到 1.35，因为 Q(B,safe) 自己也还未收敛到 4；多次访问会继续推动两者。
5 · PSEUDOCODE, LINE BY LINE
每一行都对应前面的一个理论对象。
Q = zeros(num_states, num_actions) # 当前近似 Q_t
for episode in range(num_episodes):
s, info = env.reset()
done = False
while not done:
a = epsilon_greedy(Q[s], epsilon) # behavior policy μ
s_next, r, terminated, truncated, info = env.step(a)
done = terminated or truncated
bootstrap = 0.0 if terminated else max(Q[s_next])
target = r + gamma * bootstrap # one sample of T*Q
td_error = target - Q[s, a]
Q[s, a] = Q[s, a] + alpha * td_error # stochastic approximation
s = s_next
| 容易被略过的行 | 原理解释 | 常见 bug |
|---|---|---|
a = epsilon_greedy(...) | 这是数据采集策略，不是 target policy。 | 训练与评估都用 ε>0，导致看不出实际 greedy 能力。 |
terminated vs truncated | 自然终止表示没有未来；时间上限截断是否应 bootstrap 取决于任务定义与 API 语义。 | 把所有 done 都 mask 掉，低估被时间上限截断的状态价值。 |
max(Q[s_next]) | 实现最优 Bellman target 的 maxa′。 | 错误写成 max(Q[s])，把当前 state 当成下一 state。 |
Q[s,a] | 表格法只更新刚访问的一个 state-action 单元。 | 不小心整行广播更新，改变了未观察动作的价值。 |
6 · WHY IT CONVERGES — AND THE FINE PRINT
经典保证的骨架：压缩映射 + 足够访问 + 合适步长。
最优 Bellman 算子 T* 在最大范数下是 γ-压缩：||T*Q−T*Q′||∞≤γ||Q−Q′||∞，因此它有唯一固定点 Q*。Q-learning 的更新可以看成朝 T*Q 的带噪样本走。Watkins 与 Dayan 对有限、离散表格设置给出了几乎必然收敛的经典结果；其核心前提不是一句“多跑几轮”，而是：
| 前提 | 它排除什么问题 | 实践中的对应检查 |
|---|---|---|
| 有限、离散的 state-action 表 | 每个值能被单独反复估计。 | 连续状态需离散化或转向函数近似；不能把这条证明直接搬到 DQN。 |
| 每个相关 (s,a) 被无限次访问 | 避免某些价值永远停留在初始化误差。 | 看状态／动作覆盖计数，审查 ε 衰减是否过快。 |
| 有界 reward 与合适折扣／终止条件 | 使长期回报和固定点定义良好。 | 检查 reward scale、γ、自然终止与 time limit 的建模。 |
| Robbins–Monro 步长 | 长期不停止学习，但逐渐平均掉抽样噪声。 | 典型理论条件为 Σαt=∞ 且 Σαt2<∞；固定 α 更适合持续适应而非精确极限收敛。 |
原始论文是 Watkins 与 Dayan 1992 年的 《Q-learning》↗；它讨论的正是离散 action-value、重复采样与收敛条件。不要把“表格 Q-learning 在这些假设下收敛”简化成“任何叫 Q-learning 的深度实现都稳定”。
7 · FAILURE MODES
当 Q 值看起来不对时，先定位是哪一层假设被破坏。
| 现象 | 机制层原因 | 先做的检查 | 不是优先解法 |
|---|---|---|---|
| Q 值几乎不变 | reward 太稀疏、状态未覆盖、α 太小或 transition 没真的写回。 | 打印访问计数、TD error、非零 reward 的比例、Q 前后差值。 | 盲目加大网络／增加 epoch。 |
| 训练 reward 忽高忽低 | ε-greedy 行为刻意探索；随机环境也有方差。 | 另画 ε=0 的 greedy evaluation 与多个 seed 的均值区间。 | 只看单条训练曲线下结论。 |
| Q 明显高估 | max 会选择估计噪声中的幸运值（maximization bias）。 | 比较 Q 尺度与真实／评估 return；测试随机 reward MDP。 | 仅靠降低 α 掩盖系统偏差。 |
| 换成神经网络后发散 | 函数近似 + bootstrap + off-policy 形成 deadly triad，更新会互相放大。 | 检查 replay、target network、reward scale、学习率、分布覆盖。 | 认为“表格收敛证明”仍自动成立。 |
| 连续动作无法 max | maxa′Q(s′,a′) 需在无穷动作空间做优化。 | 明确动作空间结构。 | 在连续向量上枚举动作；应转向 actor-critic、SAC 等。 |
8 · TEST YOUR MODEL
能回答这些，才算真正理解了 Q-learning。
01 · Q-learning 实际在 B 选择了 left，但 target 使用 right 的 Q 值；这是 bug 吗？
不是。若 right 是 Q(B,·) 最大值，Q-learning 正是在用行为策略的 left 样本学习“未来改为 greedy 后”的目标策略。SARSA 才使用实际 next action 的 Q(B,left)。
02 · 为什么 terminal transition 的 target 不含 γmax Q？
自然终止后定义上没有未来 return，G 的后缀为 0；因此 target=r。若是仅因 time limit 截断，是否置零取决于它是不是任务真正终点，不能不加区分。
03 · 若 α=1，会发生什么？
每次访问直接覆盖为最新 target，适合某些确定性、一次即可准确的情形；随机环境中会高度跟随单次噪声，不再像样本平均一样稳定。
04 · 为什么 Q-learning 没有显式估计 P(s′|s,a)，仍像动态规划？
它把 DP 的“对所有后继取期望”改为每次从环境拿一个后继样本，用随机逼近累积这些样本。它保留 Bellman backup 的结构，但不显式存模型。
WHERE THIS GOES NEXT