FIRST TERMS · CONTROL
这课的名字不是算法名，而是一个决策问题。
| 术语 | 全称 / 白话含义 | 它要解决什么 |
|---|---|---|
| Control（控制） | 不再固定策略 π，而是不断改它，直到得到高 return 的策略。 | 从“这条策略好不好”变成“怎样找到更好策略”。 |
| Exploration（探索） | 主动尝试不确定的动作，收集新的证据。 | 避免过早相信一个偶然看起来好的动作。 |
| Exploitation（利用） | 选择当前估计价值最高的动作。 | 把已有知识变成当前 reward。 |
| ε-greedy | 以 1−ε 概率利用，以 ε 概率随机探索；ε（epsilon）是探索率。 | 用一个可调旋钮平衡探索与利用。 |
评估是在固定策略下估价值；控制是用估到的价值反过来改策略。探索不是“乱走”，而是为了降低对动作价值的不确定性而付出的信息成本。
LEARNING TARGET
学完后，你能解释 Q-learning 为什么能学会选动作，也能指出它何时会冒险过头。
| 完成目标 | 直接应用 | 为后续铺路 |
|---|---|---|
| 区分 policy evaluation 与 control；从 Q(s,a) 推出 greedy 改策略。 | 阅读离散动作的 RL 训练循环，知道行为选择与价值更新各在做什么。 | DQN、Actor-Critic 与 policy gradient 都是在更大空间做“评估 + 改进”。 |
| 按 target 区分 SARSA 与 Q-learning，理解 on-policy / off-policy。 | 根据“训练时会不会探索”和“部署时要不要保守”选择合理算法与评估协议。 | 理解 replay buffer、offline RL 与 importance sampling 的前提。 |
| 用 ε-greedy 设计最小探索实验，并看懂最大化偏差。 | 诊断卡在局部路径、早停探索、线上 reward 高估等现象。 | Double DQN、UCB、entropy bonus、PPO 的探索设计。 |
FROM EVALUATION TO CONTROL
有了 Q，为什么就能“改策略”？
Lesson 02 的动作价值 Qπ(s,a) 回答的是：“现在在状态 s 先做 a，之后继续遵循当前策略 π，平均能拿多少长期回报？”如果同一状态里 Q(s,right)=7、Q(s,down)=2，最朴素的改进就是让策略更偏向 right：
这叫 Generalized Policy Iteration（GPI，广义策略迭代）：评估和改进不必各自完全收敛才切换；它们可以一边收集经验、一边互相推动。SARSA、Q-learning、actor-critic 都是这个循环的不同实现。
WHY EXPLORE
只选当前最大的 Q，为什么会失败？
假设一个新状态有两个动作。你第一次随机试 A 得到 +1，试 B 时恰好遇到噪声得到 −1。若从此永远 greedy，就会认定 A 更好，永远不会发现 B 的真实平均收益可能是 +10。这不是实现 bug，而是数据由策略自己生成的后果。
| 选择规则 | 当前 Q(A)=4，Q(B)=7 | 优点 | 风险 |
|---|---|---|---|
| pure greedy | 总选 B | 当前即时表现最好。 | 不再获得 A 的新证据，早期错误无法纠正。 |
| ε-greedy，ε=0.1 | 90% 选 B；10% 随机选 A 或 B | 规则极简单，所有动作持续有被尝试的机会。 | 即使已经确定 B 更好，也会偶尔做明显较差动作。 |
| softmax / UCB（后续） | 按价值或不确定性分配概率 | 探索更有针对性。 | 需要额外假设、温度或不确定性估计。 |
不要只看训练 reward。至少同时画：① ε 随时间的曲线；② 训练时带探索的 return；③ 评估时 ε=0 的 greedy return；④ 每个动作的被选次数。否则“训练 reward 低”可能只是探索很多，而不是策略变差。
TWO TD CONTROL ALGORITHMS
SARSA 与 Q-learning 只差一个 target，却在学习不同策略。
两者都使用 Lesson 03 的 TD 思路，维护一张 Q 表并每看见一步 transition 就更新。最关键问题不是名字，而是 target 中“下一步的动作”由谁决定。
| 算法 | 全称 / target | 它评估谁 | 名称怎么来的 |
|---|---|---|---|
| SARSA | State–Action–Reward–State–Action Q(s,a) ← Q(s,a)+α[r+γQ(s′,a′)−Q(s,a)] | 实际会执行的 ε-greedy 策略。 | 一条经验正好按 s,a,r,s′,a′ 五个量排列。 |
| Q-learning | Q 值学习 Q(s,a) ← Q(s,a)+α[r+γ maxa′Q(s′,a′)−Q(s,a)] | 假设后续总选最优动作的 greedy 策略。 | 核心是直接学习最优动作价值 Q*。 |
ALGORITHM ANATOMY
不要背更新式：把一次更新拆成五个机械步骤。
表格型 TD 控制没有“神秘训练”。它维护的是一个可写入的数表 Q；每到一条 transition，就构造一个对长期回报的局部承诺（target），再只把对应表格单元向该承诺移动一小步。
| 步骤 | 程序里发生什么 | 数学上发生什么 | 为什么需要 |
|---|---|---|---|
| 1 · 取动作 | 用 ε-greedy 从 Q[s,*] 选 a。 | 行为策略 μ(a|s) 决定数据分布。 | 既拿当前收益，也确保每个动作仍有机会被看到。 |
| 2 · 交互 | 环境返回 (s′, r, done)。 | 采到一次 p(s′,r|s,a) 的样本。 | 模型未知时，不能直接枚举所有后继，只能采样。 |
| 3 · 选 target 的后半段 | SARSA 选实际 a′；Q-learning 取 max Q[s′,*]。 | 分别写成 Q(s′,a′) 或 maxa′Q(s′,a′)。 | 这一行决定了它学实际策略还是 greedy 目标策略。 |
| 4 · 形成 TD error | delta = target - Q[s,a]。 | δ = r + γ·next_value − Q(s,a)。 | 把“当前预测错多少”变成带方向的学习信号。 |
| 5 · 局部写回 | Q[s,a] += alpha * delta。 | Q ← (1−α)Q + α·target。 | α∈(0,1] 是旧信息与新证据的权重，不是随便加的系数。 |
ONE EPISODE, BY HAND
同一条轨迹，SARSA 与 Q-learning 从哪一步开始分叉？
设 γ=0.9、α=0.5。环境有 A → B → terminal：从 A 执行 go 到 B，reward=0；在 B 执行 safe 后终止并得到 +4。初始 Q 全为 0，但假设过去的噪声经验使 Q(B,risky)=5，而 Q(B,safe)=0。当前 ε-greedy 在 B 实际选中了 safe。
| 看到的 transition | SARSA target 与更新 | Q-learning target 与更新 | 这一步揭示什么 |
|---|---|---|---|
| A, go → r=0, B 实际下一动作是 safe | target=0+0.9·Q(B,safe)=0 Q(A,go)=0+0.5(0−0)=0 | target=0+0.9·max(0,5)=4.5 Q(A,go)=0+0.5(4.5−0)=2.25 | SARSA 把“我真的会选 safe”带进 target；Q-learning 不管实际动作，追随当前最大估计 risky。 |
| B, safe → r=+4, terminal | target=4（终止后 next_value=0） Q(B,safe)=0+0.5(4−0)=2 | 同样 target=4 Q(B,safe)=2 | 终止 transition 没有未来价值，两者一致。 |
| 下一次再访问 A → B，且仍选 safe | target=0+0.9·2=1.8 Q(A,go) 从 0 向 1.8 移动 | 若 risky 的虚高值仍最大，仍向 4.5 移动 | bootstrap 会把 B 的新信息逐次向 A 传播；Q-learning 的 max 也会放大幸运噪声。 |
它不是说 SARSA 总更安全、Q-learning 总更差。它只隔离了一个机制：同一份数据，target 的后半段不同，学习对象就不同。若 Q(B,risky)=5 真实可靠且部署时不探索，Q-learning 的乐观 target 反而可能更接近目标策略。
WHAT THE ALGORITHM ASSUMES
“会收敛”不是无条件承诺。
| 经典表格收敛讨论需要 | 为什么 | 现实里破坏它会怎样 |
|---|---|---|
| 有限的 MDP 与有界 reward | Q 表必须可被反复覆盖，return 也应有稳定尺度。 | 连续／极大状态空间装不进表，要进入函数近似与 DQN。 |
| 所有 (s,a) 被充分访问 | 没尝试过的动作没有证据，无法知道其真实价值。 | ε 太早归零、稀疏奖励，会造成错误价值永远没有机会修正。 |
| 步长满足“逐渐但不停学习”的条件 | 理论上通常要求累计步长足够大、平方累计有限，以平均掉随机噪声。 | 固定 α 适合非平稳任务的持续适应，却不等同于经典的精确收敛保证。 |
| 表格 + 合理采样的组合 | Q-learning 的证明依赖特定的 tabular 设置。 | 函数近似、bootstrap、off-policy 混在一起会形成 deadly triad，可能发散。 |
因此真实实验的正确问法不是“Q-learning 收不收敛”，而是：在这个状态表示、探索日程、步长、数据分布与函数近似下，它的评估 return、Q 值尺度和覆盖度是否共同支持收敛的证据？
ON-POLICY VS OFF-POLICY
“用什么行为采数据”与“要学谁”可以相同，也可以分开。
| 概念 | 行为策略（behavior policy） | 目标策略（target policy） | 本课例子 |
|---|---|---|---|
| On-policy（同策略） | 产生数据的策略 | 要被评估/改进的同一策略 | SARSA 用 ε-greedy 行动，也把这个会探索的 ε-greedy 当作学习对象。 |
| Off-policy（异策略） | 可以更嘈杂、更旧或来自别人的策略 | 另一个目标策略 | Q-learning 用 ε-greedy 收集数据，却用 max 学 greedy 目标策略。 |
若到终点的最短边路旁就是悬崖，Q-learning 的 target 假设“以后总能完美 greedy”，因而可能偏好贴边最短路；SARSA 把将来偶尔 ε-greedy 失手也算进去，常会学到离悬崖更远的安全路。这不是谁绝对正确，而是目标策略不同。
ALGORITHM DEEP DIVES
两条 TD control 路线必须各自推到尽头，不能只做一张对比表。
READ THE CODE
先读 Q-learning 的数据流，不必先背每个变量。
initialize Q(s, a) = 0
for each episode:
s = env.reset()
while not done:
a = epsilon_greedy(Q, s, epsilon) # behavior: 收集数据
s_next, r, done = env.step(a)
next_value = 0 if done else max_a(Q[s_next, a]) # target: greedy
td_target = r + gamma * next_value
Q[s, a] += alpha * (td_target - Q[s, a])
s = s_next
把第 6 行的 max_a(Q[s_next, a]) 换成“实际按 ε-greedy 选出的下一动作 a_next 的 Q[s_next,a_next]”，并让循环带着 a_next 前进，就得到 SARSA。唯一实质差异仍是 target。
| 变量 | 不是它什么 | 本课中它的作用 |
|---|---|---|
| α（alpha，步长） | 不是探索率。 | 一次 TD error 写回 Q 表的幅度。 |
| γ（gamma，折扣） | 不是学习率。 | 定义远期 reward 在 target 中有多重。 |
| ε（epsilon，探索率） | 不是随机环境概率。 | 定义行动时有多频繁故意不选当前最佳动作。 |
WHAT CAN GO WRONG
最大化偏差：max 会偏爱噪声中的幸运值。
若两个动作真实价值都为 0，但估计里一个因噪声是 +1、另一个是 −1，max 总挑 +1。反复如此，Q-learning 的 target 容易系统性偏高。它并不是“max 写错了”，而是同一组带噪估计既负责挑最大，又负责评估被挑中的那个。
估计 Q 不断升高，实际评估 return 却没同步变好；或在随机 reward 环境里看起来异常乐观。
Double Q-learning / Double DQN 会把“选择动作”和“评价动作”分给相对独立的估计器，降低这个偏差。
另一个常见错误是只把 ε 线性降到 0：在非平稳环境、稀疏奖励或新状态不断出现的任务中，完全停止探索可能使性能退化。调 ε 是实验假设，应记录和比较，而不是默认一个“标准答案”。
CHECK YOUR UNDERSTANDING
先判断 target，再判断它在学谁。
01 · 当前 s′ 上 Q(s′,left)=4、Q(s′,right)=9，行为策略因 ε-greedy 实际选了 left。Q-learning 与 SARSA 的下一步价值各用多少？
Q-learning 用 max=9；SARSA 用实际动作 left 的 4。前者学习 greedy target policy，后者学习实际会探索的 behavior policy。
02 · ε=0.2、三个动作，当前 greedy 动作被选中的概率是多少？
0.8 + 0.2/3 ≈ 0.867。80% 是直接利用，20% 的随机探索中也有三分之一会恰好选到它。
03 · 为什么“训练 return 下降”不一定表示策略退化？
若 ε 增大或尚未衰减，训练时刻意随机探索会拉低实际回报。必须分开报告探索行为的训练 return 与 ε=0 的评估 return。
NEXT