从表格开始 — 时序差分与 Q-learning
这一章讲三件事: 「走一步就修一点」的时序差分(TD)更新为什么是 RL 的发动机; Q-learning 那一行更新公式逐项拆开,拿两状态世界把 Q 表从 0 修到 5; 「off-policy / on-policy」这一对词到底在分什么。 读完你会拿到全书的第一个可运行算法——它不需要神经网络,一张表就够; 表什么时候不够,是第 07 章的事。
1. 这一章讲什么
原书第 4 章开宗明义:RL 的历史始于状态与动作有限、离散的年代 —— 那时的标准做法是把它们装进一张表;围棋、国际象棋这类棋盘游戏都属于此类, 不需要神经网络,所以是 RL,不是深度 RL1。
这一章讲的就是这个「表格时代」的两件遗产:一件是更新机制(时序差分,TD), 一件是更新对象(Q 表)。第 04 章的贝尔曼方程给出了价值的更新规律, 但那是「已知环境、整表扫描」的解法;TD 要回答的问题是:环境规则未知、 一次只能走一步时,怎么把贝尔曼方程用起来?
2. 顶层全景:走一步,修一点
走一步:( sₜ , aₜ ) ──► 奖励 rₜ 、新状态 sₜ₊₁
│
算误差:δ = rₜ + γ·V(sₜ₊₁) − V(sₜ)
└──「一步真实 + 下一步的现成估计」减「当前估计」
│
修一点:V(sₜ) ← V(sₜ) + α·δ
│
重复。不需要环境模型,不需要等任务结束。
图说:TD 更新是全书最核心的一行代码;后面每个算法都是它的变奏。
图说里那行「修一点」就是时序差分学习:书里把它称为无模型学习的支柱—— 转移函数的位置被「一串环境样本的迭代」取代;δ 里「新估计减旧估计」 正是一步之差的「差分」2。
主走查: 一个两状态世界,s₀ 前进即到终点 s₁,奖励 +5;γ=0.9、学习率(每次修的比例)α=0.5。 第 3 节把 Q 值从 0 一步步修上去,每个数都可验算。
3. 核心原理
3.1 TD 更新逐项拆开
书里的公式:V(s) ← V(s) + α·[ r + γ·V(s′) − V(s) ]2,五件套各司其职:
| 件 | 意思 | 走查里的取值 |
|---|---|---|
| r | 这一步的真实奖励 | +5 |
| γ·V(s′) | 下一步价值的现成估计(打完折) | 终点,0 |
| −V(s) | 减掉当前估计,得到差 δ | 见下 |
| α 学习率 | 每次修的比例 | 0.5 |
| (无 T) | 公式里没有转移模型,所以是无模型更新 | — |
书里特别提醒:α 设太高有害——最后一条样本在自举过程里权重过大; α 的最优值靠实验找2。直觉:α=0.5 意味着「一半信旧账,一半信新见闻」; α=1 就是无脑全信最新一条,前面攒的经验一步作废。
3.2 主走查:把 Q 表从 0 修到 5
Q-learning(Watkins 1989)把 TD 更新用在 Q 函数上,更新式书里写为 「当前值与新信息的加权平均」3:
Q(sₜ,aₜ) ← Q(sₜ,aₜ) + α·[ r + γ·max Q(sₜ₊₁,·) − Q(sₜ,aₜ) ]
└── 注意:取的是「下一步所有动作里最大的 Q」
世界:s₀ ──前进──► s₁(终点,+5),γ=0.9,α=0.5
初始 Q 随机;为演示取 Q(s₀)=0(终点状态的 Q 恒为 0 —— 书里的设定 [^4])
第 1 回合:在 s₀ 前进,拿到 r=5,落在终点
Q(s₀) ← 0 + 0.5×[ 5 + 0.9×0 − 0 ] = 2.5
第 2 回合:同一步再来
Q(s₀) ← 2.5 + 0.5×[ 5 + 0 − 2.5 ] = 3.75
第 3 回合: 4.375 第 4 回合: 4.69 第 5 回合: 4.84 …
每一回合,估计朝真值 5 前进剩余距离的一半(α=0.5 的几何含义),越走 越近。 这就是「学习」在这本书里的最小样貌:一行更新,重复到不动。
对比一下「等结局」的老办法(蒙特卡罗):它要等整条任务跑完、拿到真实总回报才更新。 TD 的便宜处:终点还没到就开始学——第 1 回合刚拿到 +5,Q 表就已经动起来。 书里在算法分类里把这层区别写成了 MC 与 TD 两个流派的分野, 第 08 章的 SARSA(λ) 会给出两者的加权折中4。
3.3 off-policy:更新时不看「实际走的路」
Q(3.2) 式里藏着本章第二个关键词。更新用的是 max Q(sₜ₊₁,·)—— 「下一步最好的可能」,而不是「下一步实际会做的动作」。 估计的策略(奔着最好去)和行为的策略(实际在探索)是两个策略——这就是 off-policy(离策略)。
书里给这对词的标准解释5:
| off-policy | on-policy | |
|---|---|---|
| 训练数据 | 经验回放池:存下过往的状态转移,随机抽一批来训,不按当前表现更新 | 每回合按当前探索到的数据更新 |
| 特点 | 旧数据反复利用;探索只用一次也不浪费 | 收敛慢、噪声大——因为每条探索只用一次 |
| 代表 | Q-learning、DQN | SARSA(第 08 章) |
「经验回放」值得单独说清:智能体把走过的每一步 (状态, 动作, 奖励, 新状态) 存进一个大池子;训练时随机抽一小撮出来更新。随机抽有两个好处: 数据不再按时间连成串(打破相关性),同一条宝贵经验能被反复学习(样本效率)。 它在表格时代就发明了,但真正大放异彩要等第 07 章——用神经网络时, 顺序相关的数据会把训练搅得不稳定。
3.4 全书算法的总家谱
书里给所有 RL 算法画了一棵分类树,本节的 Q-learning 只是其中一枝6: 按「要不要模型」分——有模型的一枝:MCTS、世界模型(先在脑内把环境学出来、再拿它做规划);无模型的一枝: model-free 里再按「学价值还是学策略」分:学价值的按 on/off 分 SARSA 与 Q-learning/DQN,学策略的走策略梯度一枝(TRPO/PPO),另有免梯度的一枝 (交叉熵法、进化策略)。 第 4 章引言还给了环境侧的三问:确定还是随机?有限还是无限视界?环境静不静态? ——每个算法的适用面由这三问框定7。
书里也给了所有算法共享的通用循环:采轨迹(状态、动作、奖励、新状 态、 终止记号)→(可选)存进回放池→随机抽一小批(一小撮样本,行话叫批)→算策略梯度/评论员梯度→更新参数8。 后面七章的所有算法,差异全部藏在这四个步骤的某一步里。
4. 作者的判断与证据
- 书里给证据的: TD 公式与「无 T、无模型」的强调、α 过高的害处、 off/on-policy 的定义、通用循环,均为书里明写内容258。
- 书里的章法痕迹(照实指出): Q-learning 一节里混进了一句 SARSA 的描述 (「A SARSA agent uses an on-policy learning…」)9——按前后文看,这属于编辑串行; 我们把它归位到第 08 章,不按原书位置讲。
- 作者的实用主义: α 怎么取?书里直说「靠实验」2,不假装有理论—— 这与第 01 章样板书『默认值多半是试出来的,别当有理论』是同一种诚实。
5. 边界与局限
- 表格的天花板就在眼前。 书里在 Q-learning 一节末尾亲自埋了伏笔: 有限状态-动作的 Q 表要大内存,推广到连续情形几乎不可能, 解法是拿深度网络近似 Q——这就是 DQN10。数字感受一下:走查里 2 个状态; 真实任务百万状态 × 连续动作,表的行数与「没被访问过的空格」一起爆炸(第 01 章 §3.3)。
- max 带来高估。 更新取「下一步的最大 Q」,而 Q 本身是带噪声的估计—— 最大值系统性偏向高估。表格时代收敛条件能兜住,换成网络就成真病灶 (书里在算法表里给 Double DQN 的评语:「分离选择与评估」治高估11; 第 09 章 TD3 再治一次)。
- Q-learning 收敛到最优的前提是所有状态-动作对被无限次访问—— 书里没有展开这条,但「探索要充分」的影子在第 07 章 ε-greedy 里可见。
- 书里 Q-learning 的应用清单(网页自配置、新闻推荐、网络流量控制)12 都是离散决策场景——恰好印证「表格时代算法的主场」。
6. 可带走的
- TD 更新一行记牢:V ← V + α·[一步真实 + γ·下一步估计 − 当前估计]; 便宜在「走一步修一步」,不用等结局;
- α 是记忆的旋钮:0.5=新旧各半;太高则最后一条样本淹没全部历史,书里明说过犹不及;
- Q-learning 的更新目标是「下一步的最大 Q」,不是下一步实际发生的动作—— 这一个 max 就是 off-policy 的全部含义;
- 经验回放池:存转移、随机抽批、旧经验复用;表格时代是优化,网络时代是刚需;
- on/off 之分预告了第 08 章的主线:SARSA 选 on-policy,连「下一步实际做什么」 都按当前策略算;
- 蒙特卡罗等结局、TD 走一步修一点;两者的折中(一步的估计稳但常偏,整局的估计准但抖)在第 08 章的 λ 里连续可调;
- 所有算法共用一个循环(采轨迹→回放→采样→更新),读新算法先定位它改了哪一步;
- Q 表的极限是下一章的起点:状态一多、动作一连,表格「几乎不可能」, 「Deep」两个字要登场了10。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 表格时代、围棋棋类不算 deep | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:16(搜「tabular form」) |
| 环境三问 | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:26(搜「Deterministic versus stochastic」) · text/08-ch04-01-4-1-q-learning.txt:40(搜「static」) |
| off/on-policy 定义 | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:69(搜「replay buffer」) · text/08-ch04-01-4-1-q-learning.txt:74(搜「ON Policy」) |
| TD 公式、α 过高、无模型 | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:83(搜「temporal difference」) · text/08-ch04-01-4-1-q-learning.txt:89(搜「bootstraps」) · text/08-ch04-01-4-1-q-learning.txt:95(搜「model-free」) |
| 通用循环 | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:107(搜「Collect trajectories」) |
| 算法分类树 | 4.1 Q-Learning(章引言) | text/08-ch04-01-4-1-q-learning.txt:69(搜「Model based」) · text/08-ch04-01-4-1-q-learning.txt:207(搜「Value-based」) |
| Q-learning、Watkins 1989 | 4.1 Q-Learning | text/09-ch04-01-4-1-q-learning.txt:39(搜「Chris Watkins」) |
| 表格内存大、连续几乎不可能 | 4.1 Q-Learning | text/09-ch04-01-4-1-q-learning.txt:47(搜「big memory」) |
| 更新式与加权平均口径 | 4.1 Q-Learning | text/09-ch04-01-4-1-q-learning.txt:86(搜「Qnew」) · text/09-ch04-01-4-1-q-learning.txt:65(搜「weighted average」) |
| 终点 Q 为 0 | 4.1 Q-Learning | text/09-ch04-01-4-1-q-learning.txt:139(搜「terminal」) |
| 应用清单 | 4.1 Q-Learning | text/09-ch04-01-4-1-q-learning.txt:154(搜「Autoconfiguration」) |