跳到主要内容

规划与学习 — 同一台引擎,两种经验

这一章讲三件事: 「模型」和「规划」的准确定义,以及为什么规划与学习本质是同一个更新; Dyna 架构怎么把真实经验、模型学习、模拟经验接成一个循环,模型错了怎么办; 决策时规划(启发式(凭经验规则抄近路)搜索、rollout、MCTS)与后台规划的分界。 读完你会拿到第一部分的总地图:方法的差异是「维度」上的取值,不是门派的差异。

1. 定位:统一 model-based 与 model-free​

书到这里,前面两条线该合龙了。model-based 方法(DP、启发式(凭经验规则抄近路)搜索)靠规划,model-free 方法(MC、TD)靠学习;但两者的心脏是同一颗——都在算值函数,都在沿真实或可能的轨迹做 backup 更新1。本章的目的就是考察它们能混到什么程度。

先把两个词钉死:

  • 模型=任何能用来预测「环境将如何回应我的动作」的东西。分布模型给出全部可能及概率(DP 要的那种),样本模型只按概率抽一个结果(模拟器)。十二颗骰子求和:写个模拟器容易,列全所有和数的概率分布难——样本模型往往容易得到得多,二十一点那章已经预演过2。
  • 规划=任何「拿模型当输入、产出或改进策略」的计算过程。本书只谈状态空间规划(搜状态空间);搜索「计划的空间」的那一类(偏序规划、演化法)与随机序贯决策不合拍,不谈3。

于是统一视角一句话:所有状态空间规划=(1) 把算值函数当改进策略的中间步骤 +(2) 用模拟经验做 backup 更新。规划与学习的差别只剩经验来源4。

2. Dyna:一台引擎,三种经验​

Dyna-Q 是全书给的集成样板,一个循环里同时跑四件事5:

              ┌────────────── 直接强化学习(真实经验 → Q) ◀─────┐
   真实经验 ──┤                                                  │
              └── 模型学习(真实经验 → Model)                     │
                       │                                        │
                       ▼                                        │
                  模拟经验(从 Model 抽)── 计划更新(→ Q) ──────┘
                                                      ▲
   动作选择照 Q 走,走完把 (S,A,R,S′) 喂给上面全部通路 ┘

  图说:学习与规划用的是同一个 Q 更新;差别只有经验的来源。
       书里的说法:RL 方法是学习与规划的「共同最后通路」。

主走查拿书里的迷宫实验走一遍(数字全部来自书)6:47 个格子的迷宫,每步真实动作后额外做 n 次「随机挑一个见过的 (S,A),问模型,套同一个 Q 更新」:

  n=0(纯 TD,不规划):约 25 幕才达到(ε-)最优
  n=5:              约 5 幕
  n=50:             仅 3 幕
  第一幕大家都一样:约 1700 步(纯乱撞,种子都相同)

  差别在第 2 幕中途就肉眼可见:n=0 的策略只学会最后一步;
  n=50 的策略已经铺到接近起点——规划在 agent 还在乱逛时,
  就用模型把这次经验「摊」到了整条回程上。

一句书里的妙语收束:agent 同时是 reactive 和 deliberative 的——对最新感官即时反应,同时永远在后台规划7。

3. 模型错了怎么办​

模型会错:样本太少、函数逼近的泛化失真、或者环境变了。后果分两档8:

  • 乐观的错(模型许诺了不存在的捷径):策略扑过去,扑空,顺手纠正——自愈。书里的 blocking maze:1000 步后近路被堵,Dyna 找新路,只是中间断粮一阵。
  • 悲观的错(环境变好了,模型不知道):可能永远发现不了。书里的 shortcut maze:3000 步后开了条更近的路,普通 Dyna-Q 永远没发现——它的模型说没有捷径,于是规划越多越不会往那边走;连 ε-greedy 的随机都救不了。解法 Dyna-Q+:给每个 (S,A) 记「多久没试过」,越久,模拟奖励加成 κ√τ 越大——作者称之为计算性好奇(computational curiosity),而且判定这买卖值得9。

这里藏着探索-利用两难的规划版:探索=试能改进模型的事,利用=照当前模型最优地走9。

4. 更新该往哪儿放:优先级与方向​

uniformly 随机挑 (S,A) 做模拟更新显然浪费——prioritized sweeping 只挑「值刚变化、且会向上游传播误差」的对,按紧急度排队更新10。另一个方向相反的省法:轨迹采样(on-policy trajectory sampling)——不均匀扫全空间,只沿「按当前策略真的会走到的轨迹」采样更新,顺带把「更新的分布」对准了将来的处境(8.6-8.7 节,RTDP 是其代表)。

5. 决策时规划:启发式搜索、rollout 与 MCTS​

前面所有规划都发生在后台——改进的是长期值函数。另一族规划发生在决策现场:每遇到一个状态,临时算一大笔,只为选当前这个动作,算完就丢。经典启发式(凭经验规则抄近路)搜索(A*)、rollout 算法、MCTS 都属此族。

MCTS(蒙特卡洛树搜索)是这一族的当代代表,书的介绍值得整段转述11:

  每次轮到出招:
    反复迭代直到时间用完:
      1 Selection: 从根(当前局面)沿树策略(如 UCB)走到叶
      2 Expansion: 给叶挂上新孩子
      3 Simulation: 从那里用快而糙的 rollout policy 走完整局
      4 Backup:    这局的回报回填给树路径上的边
    最后照树的统计(值或访问数)选出真实动作。

  树内:有值估计,用 tree policy 精挑;
  树外:没有估计,用 rollout policy 快走。

书里给它的历史分量:2005 年到 2015 年,计算机围棋从业余水平到围棋大师(6 段以上),MCTS 是主要功臣;2016 年 AlphaGo 击败世界冠军用的是它的加强版(见第 15 章)11。作者给它的机理定位:边更新边长出一张局部的动作值查找表,把记忆(存下来的估计值)精确花在高回报轨迹的起始段上——避开了「全局逼近值函数」的难题,又保留了用经验引导探索的好处12。

6. 第一部分收官:方法的「维度」​

本章末节是第一部分的总账,也是全书方法论上最值钱的一页13。所有已见方法共享三件事:估价值函数、沿轨迹 backup、GPI。在此之上,方法之间的差异是一组坐标轴:

维度取值的两端
更新的宽度样本更新 ↔ 期望更新(要分布模型)
更新的深度one-step TD ↔ 穷举搜索;四角=TD / MC / DP / 穷举
on-policy ↔ off-policy学自己走的 ↔ 学别的策略的
回报的定义情节/持续、折扣/不折扣
估什么值状态值 / 动作值 / afterstate 值
探索怎么加ε-greedy / 乐观初值 / softmax(把一组数变成一组概率) / UCB
同步 ↔ 异步;真实 ↔ 模拟;更新哪里、何时、记忆多久……

作者点出尚未出场的那根最重要的轴:函数逼近——从表格到聚合到线性到非线性的整条谱,留给第二部分13。

7. 作者的判断与证据​

实验支撑的: Dyna 迷宫的 25/5/3 幕对比、blocking 与 shortcut 迷宫、图 8.3 的策略铺开图,都是书中实验68;MCTS 推动围棋水平跃迁是作者认定的历史事实11。

作者的立场: 「直接法与间接法谁优」的长期争论被作者判为伪对立——两者的相似处多于差异处,洞察来自合并而非站队5。心理学里「认知 vs 试错」「深思 vs 反应」的老争论,作者同样按合并处理(第 14 章再回收)。

坦白: shortcut maze 暴露的「模型悲观错误无法自愈」没有一般解;Dyna-Q+ 的好奇心加成只是「往往有效」的启发式,书里明说这个冲突「大概不存在既完美又实用的解」9。

8. 边界与局限​

  • Dyna-Q 的模型是确定性表格(每对 (S,A) 只记最后一次结果);随机环境、大状态空间都要另想办法(书里在习题里点了方向)。
  • 决策时规划要求一个能快速多步模拟的模型;没有模拟器,rollout/MCTS 一概免谈。
  • prioritized sweeping、RTDP 等只处理了「更新顺序」的一个侧面;更新位置的自动选择仍是开放问题。
  • 本章全部结论都在表格情形内;函数逼近进场后,「模型+规划」的组合还要再经历一次发散危机(第 10-11 章)。

9. 可带走的​

  1. 规划=对模拟经验做学习更新;两者唯一差别是经验来源,算法可以完全同一。
  2. 样本模型比分布模型好拿得多:能模拟就别硬写分布(DP 除外)。
  3. Dyna 的本质:每步真实经验,顺手用模型重放 n 次——25 幕 vs 3 幕的差距全在这里。
  4. 模型错了分两档:乐观的错会自愈;悲观的错要靠「计算性好奇」定期巡检。
  5. MCTS 口诀:树内精挑、树外快走、按局回填、用完重来;它是「用算力换评估函数」的当代典范。
  6. 更新的位置和顺序是被低估的自由度:优先扫、按轨迹扫,常比改公式更见效。
  7. 选方法=在维度表上选坐标,不是选门派;第一部分的所有算法都能放进同一张图。
  8. 后台规划改长期值,决策时规划只管眼前这一步——两者用的可以是同一套模拟与更新。

10. 原文地图​

主题原书章原文位置
统一视角、心脏相同Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:4(搜「unified view」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:83(搜「heart of both」)
模型定义、分布/样本模型Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:20(搜「to predict how the」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:25(搜「distribution models」)
规划定义、状态空间规划Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:44(搜「takes a model as input」)
共同结构两条Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:63(搜「two basic ideas」)
Dyna、共同最后通路Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:116(搜「Dyna」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:183(搜「final common path」)
Dyna Maze 25/5/3Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:252(搜「25 episodes」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:254(搜「three episodes」)
reactive 且 deliberativePlanning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:298(搜「reactive and always deliberative」)
模型出错、blocking/shortcutPlanning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:309(搜「When the Model Is Wrong」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:367(搜「never realized」)
Dyna-Q+ 好奇心Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:391(搜「bonus reward」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:397(搜「computational curiosity」)
prioritized sweepingPlanning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:416(搜「Prioritized Sweeping」)
MCTS、围棋跃迁Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:1191(搜「Monte Carlo Tree Search」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:1063(搜「grandmaster」)
MCTS 四步、树策略/rolloutPlanning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:1249(搜「Selection」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:1224(搜「rollout policy」)
查找表机理Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:1296(搜「lookup table」)
第一部分维度总结Planning and Learningtext/11-fm-planning-and-learning-with-tabular-methods.txt:1347(搜「Dimensions」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:1355(搜「three key ideas」) · text/11-fm-planning-and-learning-with-tabular-methods.txt:1451(搜「orthogonal spectrum」)

Footnotes​

  1. 出处:「Planning and Learning with Tabular Methods」第 83 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:83,搜「heart of both」)。 ↩

  2. 出处:「Planning and Learning with Tabular Methods」第 20 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:20,搜「to predict how the」)与第 24 段(搜「distribution models」);骰子例在第 27-36 段(搜「dozen dice」)。 ↩

  3. 出处:「Planning and Learning with Tabular Methods」第 44 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:44,搜「takes a model as input」);不谈 plan-space 在第 52-59 段(搜「Plan-space」)。 ↩

  4. 出处:「Planning and Learning with Tabular Methods」第 63 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:63,搜「two basic ideas」)与第 85 段(搜「simulated experience」)。 ↩

  5. 出处:「Planning and Learning with Tabular Methods」第 116 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:116,搜「Dyna」);直接/间接之争的合并裁决在第 145-158 段(搜「exaggerated」);「共同最后通路」在第 182-185 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:183,搜「final common path」)。 ↩ ↩2

  6. 出处:「Planning and Learning with Tabular Methods」第 252 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:252,搜「25 episodes」)与第 253 段(搜「three episodes」);第一幕约 1700 步在第 246 段(搜「1700」);图 8.3 的策略铺开在第 276-284 段(搜「halfway」)。 ↩ ↩2

  7. 出处:「Planning and Learning with Tabular Methods」第 298 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:298,搜「reactive and always deliberative」)。 ↩

  8. 出处:「Planning and Learning with Tabular Methods」第 309 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:309,搜「When the Model Is Wrong」);乐观错误自愈在第 318-322 段(搜「optimistic」);shortcut maze「永远没发现」在第 367 段(搜「never realized that it existed」)。 ↩ ↩2

  9. 出处:「Planning and Learning with Tabular Methods」第 386 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:386,搜「Dyna-Q+」);κ√τ 加成在第 393 段(搜「bonus reward」);「计算性好奇」在第 397 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:397,搜「computational curiosity」);「没有完美又实用的解」在第 384 段(搜「perfect and practical」)。 ↩ ↩2 ↩3

  10. 出处:「Planning and Learning with Tabular Methods」第 416 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:416,搜「Prioritized Sweeping」)。 ↩

  11. 出处:「Planning and Learning with Tabular Methods」第 1191 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:1191,搜「Monte Carlo Tree Search」)与第 1195 段(搜「grandmaster」);四步在第 1246-1267 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:1249,搜「Selection」);树策略/rollout 之分在第 1224-1227 段(搜「rollout policy」)。 ↩ ↩2 ↩3

  12. 出处:「Planning and Learning with Tabular Methods」第 1296 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:1296,搜「lookup table」)。 ↩

  13. 出处:「Planning and Learning with Tabular Methods」第 1347 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:1347,搜「Dimensions」);三个共同点在第 1355 段(搜「three key ideas」);函数逼近是未覆盖的最重要维度在第 1451 段(text/11-fm-planning-and-learning-with-tabular-methods.txt:1451,搜「orthogonal spectrum」)。 ↩ ↩2