CS234 L16 · 蒙特卡洛树搜索、基于模型的 RL 与全课收尾 · 放映厅

知识点 1

开场

1 / 65

讲解

最后一讲做两件事：把基于模型的 RL 扶回一线工具的位置，然后在它上面搭出 蒙特卡洛树搜索——AlphaGo 背后那个在决策时做规划的方法。前半讲的论点只有一句：一旦你拟合出一个转移和奖励模型，你就拥有了一个模拟器；而有了模拟器，你什么都能干——动态规划、在合成轨迹上跑 Q 学习、策略搜索，还有一个额外的好处：奖励换了而动力学没换时，可以零样本迁移。代价是两层近似误差叠在一起：模型本身的误差，和在模型上规划的误差。而它们复合的方式，和 L07 行为克隆在分布漂移下的误差复合是同一个形状。后半讲是一条从笨到巧的阶梯：完整前向搜索（正确，但叶子数是 (|S||A|)^H，而且它还固执地拒绝合并相同的状态）→ 基于模拟的搜索 → 简单蒙特卡洛搜索（它恰好是一步策略改进）→ MCTS。 而这一讲最好的部分是它的结尾：Brunskill 对 UCT 提出了一个诚实的批评。UCT 把每个树节点当成一个独立的老虎机、用 UCB 的乐观加成去选动作。但老虎机里乐观之所以对，是因为你真的会为坏决策付出代价；而在规划里，在脑子里模拟一个坏动作，你什么也不疼。所以正确的目标应该是「关于根节点 argmax 的信息增益」，而不是累积遗憾。我把这个批评验了一遍，它站得住：同样的模拟预算，花在不确定的那个动作上，把两条置信区间分开的概率是 0.5274；花在乐观会选的那个上，只有 0.0604——差 8.7 倍。

知识点 2

1 · 拟合一个模型 = 拥有一个模拟器，而模拟器什么都能干

2 / 65

拟合一个模型，你就拥有了一个模拟器。而模拟器什么都能干。

讲解

最后一讲从一件被前面十五讲冷落的事开始：拟合一个环境模型。论点只有一句：一旦你有了转移和奖励的估计，你就拥有了一个模拟器。而模拟器的用处不是一种，是全部：在它上面做动态规划——值迭代、策略迭代，L02 那一整套直接回来了。用它生成合成轨迹，然后在合成数据上跑任何无模型算法——Q 学习、策略梯度，随便。在它上面做策略搜索，而且可以搜到不敢在真实环境里试的地方。还有一个额外的好处，下一镜说。

3 / 65

无模型才是现代做法估模型又贵又容易错

L12 第九集已经出现过一次反例：探索的 PAC 结果几乎全在基于模型这边。

讲解

这个印象有很强的时代背景：深度 RL 的成名作几乎都在无模型这边——DQN、TRPO、PPO。而拟合一个环境模型看起来又贵又容易出错，尤其在高维观测上。但这门课里已经出现过一次反例：L12 第九集——探索的 PAC 结果几乎全部出在基于模型这一侧，因为模型把「我对这里了解多少」显式地记了下来。这一讲给的是第二个理由，而且是一个更普遍的理由：模型是一个可以反复使用的资产，而策略不是。下一镜把这句话说具体。

4 / 65

零样本迁移：奖励换了而世界没换时，模型一点不用重学。

讲解

最能说明「模型是资产」的，是奖励变了而动力学没变的情形。这在真实场景里极其常见：同一个机器人，今天要它搬箱子，明天要它避开人。物理没变。同一个辅导系统，这学期优化完成率，下学期优化留存。学生怎么学没变。这时候：策略是对着旧奖励优化出来的，得从头学。模型只描述世界怎么运转，一点不用动——换个奖励函数重新规划一遍就行，不需要任何新数据。这就是零样本迁移。这也说明了模型和策略在信息上的不对称：模型编码的是「世界是什么样」，策略编码的是「世界是什么样 + 我想要什么」。前者可以复用，后者不能。

5 / 65

三样东西里，只有模型不含「我想要什么」 —— 所以只有它能复用。

讲解

把三样东西并排看，不对称就很清楚了：模型 P(s′|s,a)：只描述世界。不含目标。策略 π(a|s)：「在这个状态我该做什么」——取决于我想要什么。 值函数 V(s)：「这个状态有多好」——也取决于我想要什么。所以奖励一变，策略和值函数同时作废，而模型完好无损。这个区分还解释了一件前面几讲留下的事：为什么 L15 那些离线评估方法可以对任意候选策略给出估计，而一个学好的 Q 函数只对它自己那个策略有效。信息含量不同。但要把话说完整——模型这个优势是有代价的，而且代价不小。下一集专门算这笔账。

6 / 65

指名反驳：不是无模型更现代，是两者编码的信息不一样。

讲解

指名回去：不是「无模型更现代」，是两条路线编码的信息不一样，因此适用的场合不一样。把账摆平： 模型的代价是真的——要多学一个东西，而且它的误差会传给规划（下一集）。在高维观测上拟合一个准确的动力学模型，至今仍是难题。 模型的好处也是真的——可以跨奖励复用、可以显式表达不确定性（L12 第九集）、可以在脑子里试危险的动作。判断标准很实际：你会不会复用它？ 只解一个固定任务、能大量交互——无模型更直接。奖励会变、交互昂贵、需要解释「为什么」——基于模型更划算。而这一讲后半段的全部内容，都建立在「你已经有一个模拟器」这个前提上。有了模拟器，才谈得上在决策时「想一想」。 下一集先把代价算清楚。

7 / 65

知识点 1 · 总结

拟合一个模型 = 拥有一个模拟器，而模拟器什么都能干

核心结论

有了模拟器可以：做动态规划、生成合成轨迹喂给任何无模型算法、做策略搜索，还能在脑子里试危险动作。

底层机制

零样本迁移：奖励变而动力学没变时，模型一点不用重学。因为三样东西里只有模型不含「我想要什么」 —— 策略和值函数都含，奖励一变就同时作废。

常见误解

误解：「无模型才是现代做法」。L12 第九集已有反例：探索的 PAC 结果几乎全在基于模型这边。

与你的考试

判断标准很实际：你会不会复用它？只解一个固定任务、能大量交互 ⟹ 无模型更直接；奖励会变、交互昂贵、需要解释 ⟹ 基于模型更划算。而这一讲后半段全部建立在「你已经有一个模拟器」之上。

8 / 65

知识点 1 · 检验

为什么说模型比策略和值函数更「可复用」？

知识点 3

2 · 代价：模型误差和规划误差叠在一起，而且会复合

9 / 65

基于模型要付的账：两层近似误差叠在一起。

讲解

上一集把好处说完了，这一集算账。无模型的方法只有一层近似：直接估值或估策略，估得准不准就是全部。基于模型的方法有两层： 第一层，模型误差：你拟合的 P̂ 和 R̂ 不等于真的 P 和 R。 第二层，规划误差：就算模型是对的，你在上面规划也未必解得精确——值迭代截断、函数逼近、MCTS 只展开了一部分树。两层叠在一起。而问题不在于「叠」，在于它们叠的方式。

10 / 65

模型误差小就没事1% 的误差能有多大影响

误差会沿着规划的路径复合 —— 和 L07 行为克隆是同一个形状。

讲解

这个直觉在监督学习里通常是对的：模型准 99%，预测就大体可信。 在这里不对，而且不对的理由这门课已经讲过一次了。 L07 第四集：行为克隆的误差为什么会复合？因为一个小错误把你带到一个训练数据没覆盖的状态，在那里你的策略更不可靠，于是错得更远。误差沿着时间轴放大，那一集给的量级是 εT(T+1)/2。 基于模型的规划是完全一样的机制：规划器会沿着模型的预测往前推很多步。每一步的模型误差不是独立叠加的——它会把你推到模型更不准的区域，在那里下一步的误差更大。更糟的是规划器会主动找模型的漏洞：如果模型在某个地方错误地预测了高回报，规划器恰恰会挑中那里。 它在优化模型的误差，而不是优化真实回报。

11 / 65

最坏的一环：规划器会主动去找模型高估的地方。

讲解

把最坏的那一环单独拎出来说，因为它常被低估。规划器做的事是在模型里找回报最高的路径。而模型在某些地方会高估、某些地方会低估。 规划器的 argmax 会系统性地偏向被高估的那些地方。 这不是巧合，是 argmax 的性质——而这门课里已经见过它两次了： L04 第八集：最大化偏差。对一组有噪声的估计取 max，得到的期望大于真值的 max。 L12 第一集：依赖差距的界里，难的是区分两个都不错的选项。 同一个 argmax，在这里第三次咬人。规划得越深、搜索得越广，找到模型漏洞的机会就越多——更强的规划器，在一个有误差的模型上，可能表现更差。这是基于模型 RL 里一个真实且反直觉的现象。

12 / 65

缓解的办法都朝同一个方向：不要相信模型太远、太深。

讲解

实践里缓解这个问题的办法，形状都一样：不要相信模型太远。 短程规划：只往前推几步，然后接一个学出来的值函数。误差没有时间放大。 显式建模不确定性：模型不只给一个预测，还给一个置信范围；规划时对不确定的地方保守而不是乐观。集成：训练多个模型，只在它们一致的地方相信预测；不一致的地方按最悲观的那个算。注意第二条和第三条的方向：对模型的不确定性要悲观，不是乐观。这和 L11 到 L13 那一整块正好相反——那里对环境的不确定性要乐观（因为去试探是有价值的）。这里对模型的不确定性要悲观（因为你不是去试探，你是在拿模型当真）。 同一个「不确定性」，在探索里是机会，在规划里是风险。下一集看一个更基本的例子：连「用模型」和「不用模型」收敛到的东西都不一样。

13 / 65

指名反驳：不是「1% 误差没事」。误差会复合，而且规划器会放大它。

讲解

指名回去：模型误差不是一个可以按百分比折算的量。三个理由叠在一起： 误差沿规划路径复合——同 L07 行为克隆的机制，小错把你推到模型更不准的地方。 argmax 系统性偏向被高估处——同 L04 的最大化偏差，第三次出现。 规划越强，找到漏洞的机会越多——所以更强的规划器可能表现更差。这一条尤其值得记住，因为它违反了一个很深的直觉：在监督学习里，优化器更强通常更好。在一个近似模型上不是这样——你优化的是模型，不是世界。代价说完了。下一集是一个把「用不用模型」这件事逼到极限的例子：同一份数据，批 TD 和批 MC 收敛到两个不同的值，而它们的差别恰恰就是「有没有假设马尔可夫」。

14 / 65

知识点 2 · 总结

两层误差叠在一起，而且规划器会放大模型的错误

核心结论

模型误差（世界估错）+ 规划误差（在错模型上又没解准）。关键不是叠加，是复合 —— 与 L07 行为克隆在分布漂移下的机制相同。

底层机制

最坏的一环：规划器的 argmax 系统性偏向被模型高估的地方（同 L04 的最大化偏差，第三次出现）。后果反直觉：更强的规划器在有误差的模型上可能表现更差。

常见误解

误解：「模型准 99% 就没事」。在监督学习里通常对；这里不对 —— 你优化的是模型，不是世界。

与你的考试

缓解办法方向一致：不要相信模型太远太深 —— 短程规划接值函数、显式建模型不确定性、多模型集成取悲观。注意：对模型的不确定性要悲观，与 L11–L13 对环境的不确定性要乐观正好相反。同一个不确定性，探索里是机会，规划里是风险。

15 / 65

知识点 2 · 检验

为什么「更强的规划器」在一个有误差的模型上可能表现更差？

知识点 4

3 · AB 例子：批 TD 与批 MC 收敛到两个不同的东西

16 / 65

一个只有两个状态的例子，把「用不用模型」这件事逼到极限。

讲解

这一集用一个极小的例子，把「有没有假设马尔可夫」这件事逼出来。这是 Sutton & Barto 的经典 AB 例子，这门课很早就引过一次。数据是八个回合：一次：从 A 出发，得到奖励 0，转到 B，再得到奖励 0，结束。七次：直接从 B 出发，其中六次得到奖励 1，一次得到奖励 0。（讲座在数数时口误了一次，说成「六次得 1，然后从 B 开始得 0」，后面才对上——正确的是 B 一共被访问 8 次，其中 6 次得 1。另外这里没有折扣，γ=1，这一点讲座只顺口提了一句，但 V(A) 的答案依赖它。）问题很简单：V(A) 是多少？

17 / 65

两种算法都会收敛到同一个值数据一样，真值只有一个

批 TD 给 0.75，批 MC 给 0.00。两个都「收敛」了。

讲解

很自然的期待：同一份数据，两种算法反复跑到收敛，应该得到同一个答案。数据是同一份，真值只有一个。 不是这样。 批量 TD 收敛到 V(A) = 0.75。 批量蒙特卡洛 收敛到 V(A) = 0.00。两个都确实收敛了——反复在这八个回合上迭代到不动为止，各自停在这两个数上。 它们收敛到了两个不同的东西。而差别的来源只有一个，下面两镜说清楚。先说 V(B)：这个两边一致，都是 6/8 = 0.75。分歧只在 A 上。

18 / 65

批 MC：经过 A 的回合只有一个，它的回报是 0。所以 V(A)=0。

讲解

批量蒙特卡洛做的事：对每个状态，把所有经过它的回合的实际回报平均。经过 A 的回合只有一个，那次的总回报是 0 + 0 = 0。所以 V(A) = 0。更准确地说，批 MC 收敛到的是对观测回报的最小均方误差拟合。我扫了一遍验证：在 [0,1] 上找使 Σ(V(A) − 观测回报)² 最小的值，得到的正是 0.0000。关键在于：MC 完全没有用到「A 之后是 B」这个结构。它只知道「有一个从 A 出发的回合，总共拿了 0」。 它不假设马尔可夫，所以它也享受不到马尔可夫带来的信息。

19 / 65

批 TD 解的是最大似然 MDP：A 必去 B，所以 V(A)=V(B)=0.75。

讲解

看什么：左边那根高度为零 —— 批 MC 给 V(A)=0.00。右边 0.75。同一份数据、同一个状态，两个算法给出两个不同的数，而且都已经收敛。差别不在数值精度上，在它们假设了什么。　—— 批量 TD 做的事完全不同：它先用数据拟合一个 MDP，再解那个 MDP。拟合出来的最大似然 MDP 是：从 A 出发，100% 转移到 B，奖励 0（因为数据里从 A 出发的那一次就是这样）。于是解它：V(A) = 0 + γ·V(B) = 0 + 1×0.75 = 0.75。这就是确定性等价（certainty equivalence）：把估计出来的模型当成真的，然后精确求解。 而 TD 之所以能这么做，是因为它假设了马尔可夫。「A 转到 B」这个结构，让它把 B 的七次观测借给了 A——虽然从来没有第二个回合经过 A。 这就是分歧的全部来源：TD 假设马尔可夫，于是能跨状态共享信息；MC 不假设，于是只能用直接观测。

20 / 65

指名反驳：不是谁算错了。是它们假设了不同的东西。

讲解

指名回去：两个算法都没算错，它们在回答不同的问题。 批 TD 回答：「如果这是一个马尔可夫过程，最可能的 V(A) 是多少？」 批 MC 回答：「只看我实际观测到的回报，最拟合的 V(A) 是多少？」哪个对？取决于世界是不是马尔可夫的。 如果是：TD 更好——它用上了结构，同样的数据榨出更多信息。这就是 L03 到 L04 一路上 TD 比 MC 样本效率高的原因。如果不是：MC 更稳——它不会因为一个错误的假设而被带偏。这也正是 L15 第二集里重要性采样「不需要马尔可夫」值钱的原因。 同一个假设，是 TD 的力量来源，也是它的风险来源。 最后标两处记号：这个例子被反复叫作「MDP」，但它只有一个动作，其实是一个马尔可夫奖励过程——做的是策略评估，不是控制。讲座自己也纠正了这一点。模型这一半讲完了。下面六集全部在回答一个问题：手上有个模拟器，怎么用它想事情？

21 / 65

知识点 3 · 总结

AB 例子：批 TD 与批 MC 收敛到两个不同的值

核心结论

八回合数据（A→B 得 0 一次；B 单独 7 次，6 次得 1）。V(B) 两法一致 = 6/8 = 0.75。而 V(A)：批 MC = 0.00，批 TD = 0.75。两个都收敛了。

底层机制

批 MC = 对观测回报的最小 MSE 拟合（扫格自证 = 0.0000），不假设马尔可夫。批 TD = 解最大似然 MDP（确定性等价）：A 必去 B ⟹ V(A)=γV(B)=0.75，假设马尔可夫。

常见误解

误解：「同一份数据必然收敛到同一个值」。差别不在数值精度，在假设。

与你的考试

哪个对取决于世界：是马尔可夫 ⟹ TD 更好（跨状态借信息，所以样本效率高）；不是 ⟹ MC 更稳（不会被错误假设带偏，同 L15 第二集 IS 不需要马尔可夫的价值）。记号：这个例子只有一个动作，其实是马尔可夫奖励过程，讲座自己纠正过；且 γ=1，V(A) 的答案依赖它。

22 / 65

知识点 3 · 检验

AB 例子里批 TD 给 V(A)=0.75 而批 MC 给 V(A)=0.00，差别来自哪里？

知识点 5

4 · 前向搜索正确，但叶子数是 (|S||A|)^H

23 / 65

从这里开始换问题：不求整个策略，只求当前这一步。

讲解

模型这一半讲完了。后面六集全部在回答一个问题：手上有个模拟器，怎么用它想事情？ 而这里有一个重要的换题：前十五讲求的都是一个策略——一个能回答所有状态的函数。 这一讲后半段不求策略，只求「我现在这一步该走哪里」。 这叫决策时规划（decision-time planning）。它的好处很实在：你不需要把整个状态空间搞明白，只需要把当前这个局面想清楚。围棋有 10¹⁷⁰ 个局面，但你每一步只面对一个。最直接的做法是把所有可能性展开来看。

24 / 65

把所有分支都展开想清楚不就是把可能性穷尽吗

完全正确。而叶子数是 (|S||A|)^H。

讲解

前向搜索：从当前状态出发，展开一棵树——我有哪些动作，每个动作可能到哪些状态，从那些状态又有哪些动作……一直展开到时域 H。然后从叶子往回算：状态节点取期望（环境的随机性），动作节点取 max（我会选最好的）。这种树叫 expectimax 树。（字幕把它写成「expecting max」，每次出现都是这个词。） 这个做法完全正确——它算出来的就是最优动作，没有任何近似。问题只有一个：树有多大。 （标一处：她在动作节点取 max 时说「the reward here is equal to whichever of those was bigger」——取的是值（Q），不是奖励。另外她写 V(s,a₁) > V(s,a₂) 时，那个对象是 Q(s,a) 不是 V(s)。这一讲 V 和 Q 混用得很厉害。）

25 / 65

围棋只往前想三步，叶子就已经 2.2×10¹⁵。而一盘棋两百多手。

讲解

叶子数是 (|S||A|)^H——每一层既要枚举动作又要枚举可能到达的状态。代几个数： |S||A|=4、H=3 → 64（小问题没事）同样 H=10 → 1.05×10⁶ |S|=10、|A|=4、H=5 → 1.02×10⁸ 围棋首手 361 个落点，H=3 → 2.21×10¹⁵ 围棋只往前想三步，就已经两千万亿个叶子。而一盘棋有两百多手。 标一处口述的歧义：讲座说的是「S times A to the H」，听起来可能是 |S|·|A|^H。要的是 (|S||A|)^H——在 |S|=10、|A|=4、H=5 时，这两个读法差 10⁴ 倍。而围棋那个论证需要的是前者。

26 / 65

前向搜索的毛病不是「错」，是它对所有分支一视同仁。

讲解

把前向搜索的毛病说准，因为这决定了后面几集要修什么。 它不是算错了，它是不肯取舍。 前向搜索对每一个分支一视同仁：一个明显是自杀的走法，和一个明显很强的走法，它会花同样多的力气展开到底。而人类下棋显然不是这样。一个棋手看一个局面，大部分分支连想都不会想，剩下的几个里又有一两个会想得特别深。他的搜索树是极度不对称的。 所以要修的不是「让树小一点」，是「让树长在该长的地方」。后面几集就是一步步实现这件事：先用采样代替穷举（基于模拟的搜索），再只做一步改进（简单蒙特卡洛搜索），最后让树自己决定往哪长（MCTS）。

27 / 65

指名反驳：不展开全部。从模型里抽轨迹 —— 代价与深度脱钩。

讲解

指名回去：不该把所有分支都展开。第一步改动叫基于模拟的搜索：不枚举，改成采样。从当前状态出发，用模型抽一条完整的轨迹出来，然后……然后就把它当成真实经验，跑任何一个无模型算法。 这一步的意义在于代价的结构变了。 穷举：代价是 (|S||A|)^H —— 深度每加一，代价乘一个因子。采样：代价是「抽几条 × 每条多长」—— 深度只线性地进来。换句话说：你可以想得很深，只要你不要求想得很全。而这正是人类下棋的样子。注意这里有一个概念上的小转折：模拟出来的轨迹是假的（来自模型），但对无模型算法来说，它和真实经验长得一模一样。所以前十五讲所有的无模型工具，在这里可以原样搬进来用。 下一集看这条路上最简单的那个算法——而它的身份有点意外。

28 / 65

知识点 4 · 总结

前向搜索正确，但叶子数是 (|S||A|)^H

核心结论

从当前状态展开 expectimax 树，状态节点取期望、动作节点取 max。完全正确、毫无近似；问题只在树有多大。

底层机制

|S||A|=4,H=3 → 64；H=10 → 1.05×10⁶；|S|=10,|A|=4,H=5 → 1.02×10⁸；围棋 H=3 → 2.21×10¹⁵，而一盘棋两百多手。

常见误解

误解：「把所有分支都展开」。毛病不是算错，是它对所有分支一视同仁 —— 自杀的走法和很强的走法花同样的力气。人类的搜索树极度不对称。

与你的考试

第一步改动：从枚举换成采样。代价结构随之改变 —— 穷举时深度每加一乘一个因子，采样时深度只线性进来。可以想得很深，只要不要求想得很全。而模拟出的轨迹对无模型算法而言和真经验长得一样。

29 / 65

知识点 4 · 检验

完整前向搜索的主要问题是什么？

知识点 6

5 · 简单蒙特卡洛搜索：恰好一步策略改进

30 / 65

最简单的那个算法：每个首动作试一遍，之后按固定策略走到底。

讲解

这条路上最简单的算法叫简单蒙特卡洛搜索（simple Monte Carlo search）。Sutton & Barto 管它叫 rollout 算法。四步：一、对当前状态的每一个可能的首动作。二、模拟：先做这个动作，之后按一个固定的策略 π 走到底。三、这样抽若干条轨迹，算平均回报。四、选平均回报最大的那个首动作，真的走它。就这么多。没有树，没有递归，没有回传。而这个算法的身份，比它看起来有意思得多。

31 / 65

太糙了，没什么保证就是随便试试取最好的

它恰好是一步策略改进 —— 而策略改进定理直接适用。

讲解

第一印象通常是：这也太糙了，就是把几个动作各试几次取最好的，凭什么有用？ 凭 L02 那条策略改进定理。 把这个算法翻译一遍：它在估的是 Q^π(s, a)——在状态 s 做动作 a，之后按 π 走的期望回报。这正是第二步在做的事。然后它取 argmax_a Q^π(s,a)。 这就是策略改进的定义式。L02 第五集：给定一个策略 π，对它的 Q 取贪心，得到的新策略保证不比 π 差。 所以简单蒙特卡洛搜索恰好是一步策略改进 —— 在当前这个状态上执行的一步。

32 / 65

a^{*} = \arg max_{a} {\hat{Q}}^{π} (s, a) ⟹ 不比 π 差 (L02)

所以它继承了那条定理：结果不比用来 rollout 的那个策略差。

讲解

认出这个身份之后，两件事立刻跟着来。 第一，它有保证：只要 Q̂ 估得够准，这个算法选出的动作不比直接按 π 走差。而且基准很明确——是那个 rollout 策略 π，不是最优策略。 第二，它的上限也清楚了：一步策略改进只有一步。它不会比「π 迭代改进到收敛」更好。这解释了一个很实际的现象：rollout 策略越好，这个算法越好。用一个随机策略去 rollout，你得到的是「比随机好一点」；用一个已经训练过的策略去 rollout，你得到的是「比它还好一点」。 AlphaGo 的做法正是后者——用一个训练好的策略网络当 rollout 策略，于是搜索是在一个已经很强的基准上再改进一步。 「决策时再想一想」的价值，是在你已有的策略上白加一层。

33 / 65

同一条策略改进定理：训练时用它迭代，决策时用它加一层。

讲解

把这个对照摆出来，因为它把这门课的开头和结尾接上了。 L02 的用法：反复做「评估 → 改进 → 评估 → 改进」，一直到收敛。这是训练时的策略迭代。 这一集的用法：拿一个现成的策略，只在当前这个状态上做一次改进。这是决策时的规划。 同一条定理，两个完全不同的用法。 而决策时那个用法有一个训练时没有的好处：计算可以随时停。抽的轨迹越多，Q̂ 越准，改进越可靠；但抽得少也照样出一个答案。讲座说得很直接——「你可以整晚跑八小时来算这一个决策」，也可以「需要多快就少抽几条」，总能给出答案。 这类算法叫「随时算法」（anytime），而它是决策时规划最实用的性质。 但简单蒙特卡洛搜索仍然一视同仁：它给每个首动作同样多的模拟。下一集修这一点。

34 / 65

指名反驳：不糙。它恰好是一步策略改进，定理原样适用。

讲解

指名回去：它不糙，它恰好是一步策略改进，L02 那条定理原样适用。把这个算法的边界画清楚： 保住的：不比 rollout 策略差（前提是 Q̂ 估得够准）；随时可停；实现极其简单。 放掉的：只有一步改进，不会趋向最优；而且它仍然对每个首动作一视同仁——明显很差的那个和最有希望的那个，分到同样多的模拟预算。最后这一条正是第四集批评前向搜索时说的同一个毛病，只是从「展开」换到了「采样」。 而模拟预算是有限的。花在一个明显很差的首动作上的每一条轨迹，都是从最需要分辨的那几个动作那里抢来的。下一集让这棵树自己决定往哪长。

35 / 65

知识点 5 · 总结

简单蒙特卡洛搜索恰好是一步策略改进

核心结论

四步：每个首动作 → 之后按固定策略 π 走到底 → 抽若干条算平均 → 取 argmax。它估的是 Q^π(s,a)，取的是 argmax_a Q^π(s,a) —— 这就是 L02 策略改进的定义式。

底层机制

于是它继承那条定理：不比用来 rollout 的那个策略差。推论：rollout 策略越好，它越好 —— AlphaGo 正是用训练好的策略网络当 rollout 策略。

常见误解

误解：「太糙了，没什么保证」。它有保证，而且基准明确；只是上限也明确 —— 一步改进就是一步。

与你的考试

同一条定理的两个用法：L02 是训练时反复迭代到收敛，这里是决策时只在当前状态加一层。决策时用法多一个好处：随时算法（讲座：可以跑八小时算一个决策，也可以少抽几条马上给答案）。但它仍然一视同仁 —— 每个首动作分到同样多的预算。

36 / 65

知识点 5 · 检验

简单蒙特卡洛搜索（rollout 算法）的保证来自哪里？

知识点 7

6 · MCTS：故意长成偏的一棵树

37 / 65

MCTS 的全部结构：树里一个策略，树外另一个。

讲解

蒙特卡洛树搜索把前两集的东西合起来，结构只有两块： 树策略（tree policy）：在已经长出来的那部分树里，按统计量选动作——哪个看起来更有希望、哪个试得还不够。 rollout 策略：一旦走出树的边界，就换成一个便宜的策略一路走到底——通常就是随机。讲座反复强调：「the key part is that tree policy」——真正做事的是树策略，rollout 只是用来给叶子一个粗糙的估值。然后把这条轨迹的回报沿路回传，更新沿途每个节点的统计量。 然后再来一遍。每来一遍，树就在最有希望的方向上长出一点。

38 / 65

树要均匀展开才公平不然某些分支被冷落了

不对称是目的，不是缺陷 —— 冷落明显差的分支正是要的。

讲解

这个直觉来自搜索算法的传统印象：广度优先、迭代加深，都是「一层一层公平地铺开」。 而 MCTS 故意不这样。 它长出来的树是极度不对称的：在几个看起来最有希望的分支上深入得很远，在明显很差的分支上几乎不展开。讲座的说法是：「只把树填在那些看起来最终会被 max 选中、会把值回传到根的部分」。 这不是偷懒，这就是目的。第四集已经说过：完整前向搜索的毛病恰恰是它一视同仁。修的就是这一点。而「公平」在这里是一个错误的目标——你的模拟预算是有限的，花在一个明显自杀的走法上的每一条轨迹，都是从真正需要分辨的地方抢来的。

39 / 65

一次迭代：选 → 扩 → 模拟 → 回传。然后重复几千几万次。

讲解

一次迭代四步：选：从根开始，用树策略一路往下走，直到走到树的边界。扩：在边界上加一个新节点。模拟：从这个新节点用 rollout 策略（通常随机）一路走到终局。回传：把这条轨迹的回报，沿着刚才走过的路径回传，更新每个节点的访问次数和平均回报。重复几千几万次，然后在根节点选那个统计上最好的动作。关于「回传」要标一处，因为它常被误解：回传的是平均，不是自举。课上有学生专门问了这个：这算不算 TD？不算。讲座的回答是——每个节点的「奖励」就是从这个节点出发的整条 rollout 的回报，因为「那正是我们在平均的东西」。 所以原始的 MCTS 是纯蒙特卡洛回传，没有任何自举。（后来的 AlphaZero 一类才把值网络接进来，那是另一回事。）

40 / 65

两个策略的分工：把「仔细想」的预算，只花在树里那一段。

讲解

两个策略的分工，是这个算法真正的设计。树里：用统计量仔细选。这一段的每个节点都记着访问次数和平均回报，选择是有依据的。代价是要维护这些统计量。树外：随机走到底。这一段什么都不记，纯粹是为了给叶子一个粗糙的估值。代价几乎为零。 而边界会随着迭代往外推：每次迭代加一个节点，于是「仔细想」的范围一点点扩大，而且是往最有希望的方向扩大。这个设计回答了第四集那个问题——「怎么让树长在该长的地方」： 让树自己的统计量决定往哪长。 注意这意味着一个很强的性质：在极限下，MCTS 会填满整棵 expectimax 树，所以它是渐近正确的。讲座提了这一点，紧接着说这在实践中从来不会发生——这是一个关于渐近完备性的陈述，不是一个关于效率的承诺。 而这个算法的价值恰恰在「远未填满」的时候。

41 / 65

指名反驳：不对称是目的。而具体怎么不对称，全看树策略。

讲解

指名回去：均匀展开不是公平，是浪费。不对称是这个算法的设计目标，不是它的妥协。把 MCTS 相对前两集修好了什么列清楚： 相对完整前向搜索：不再穷举，改成采样；不再一视同仁，改成按统计量倾斜。 相对简单蒙特卡洛搜索：不再只看第一步，而是在树里递归地做同样的事；而且不再给每个动作同样的预算。 但整个算法的行为，完全取决于树策略怎么选动作。讲座说的 「the key thing is really this tree policy」 就是这个意思——换掉树策略，就是换一个算法。下一集看最常用的那个树策略。而它是一个老朋友——L11 那个。

42 / 65

知识点 6 · 总结

MCTS：故意长成偏的一棵树

核心结论

两块结构：树策略（树里，按统计量选，贵但准）+ rollout 策略（树外，通常随机，糙但便宜）。一次迭代四步：选 → 扩 → 模拟 → 回传。

底层机制

不对称是目的不是缺陷：预算有限，花在明显自杀的走法上的每条轨迹都是从真正需要分辨的地方抢来的。讲座：只把树填在「会被 max 选中、会把值回传到根」的那部分。

常见误解

误解：「树要均匀展开才公平」。完整前向搜索的毛病恰恰是一视同仁 —— 修的就是这一点。

与你的考试

回传的是平均，不是自举：课上有学生问这算不算 TD，答案是不算 —— 每个节点的「奖励」是从它出发的整条 rollout 的回报。原始 MCTS 是纯蒙特卡洛回传。另：「极限下会填满整棵 expectimax 树」是渐近完备性的陈述，讲座紧接着说实践中从不会发生。

43 / 65

知识点 6 · 检验

MCTS 回传时更新的是什么？

知识点 8

7 · UCT：每节点当独立老虎机，回报是整条 rollout

44 / 65

树策略用什么？UCT 的答案：把每个节点当成一个独立的老虎机。

讲解

上一集说整个算法取决于树策略。最常用的那个答案叫 UCT（UCB applied to Trees）。它的想法一句话：把树里的每一个状态节点，当成一个独立的多臂老虎机——这个节点上的每个动作是一条臂，选哪条臂就用 L11 那套 UCB。讲座原话：「we're treating each of the nodes, so each state node as a separate bandit」。 L11 整整一讲的机器，在这里被原样搬了进来。 这一集看它具体怎么搬，以及搬的过程中有一处转录稿把关键的东西说反了。

45 / 65

那个加成是个折扣因子看起来像访问次数什么的

不是折扣因子。是 UCB 的乐观加成，方向和作用完全不同。

讲解

这一集要修的是一处转录稿把概念说错的地方。那个探索加成在讲座里从头到尾没有被写下来，转录稿把它含糊成了「一个折扣因子，看起来像是你在那个节点待过多少次」。 它不是折扣因子。 折扣因子是一个小于 1 的常数，作用是压低远期的回报。而这里说的东西是 UCB1 的探索加成，作用是抬高试得不够的动作的分数。两者： 作用对象不同——折扣作用在时间上，加成作用在不确定性上。 方向不同——折扣让远的变小，加成让陌生的变大。 是不是常数——折扣是超参数，加成随访问次数变。下一镜把正确的式子写出来。

46 / 65

\arg max_{a} [\bar{Q} (s, a) + c \sqrt{\frac{\ln N (s)}{N (s, a)}}]

正确的形式：父节点访问越多它越大，这个动作试得越多它越小。

讲解

正确的树策略是： argmax_a [ Q̄(s,a) + c·√( ln N(s) / N(s,a) ) ] Q̄(s,a)：这个节点这个动作下，所有 rollout 回报的平均（上一集说的那个）。 N(s)：父节点被访问的总次数——在分子的 log 里。 N(s,a)：这个动作自己被选中的次数——在分母里。和 L11 第九集那个对照，形状完全一样： 分母上的那个计数让加成缩——这个动作试得越多，越不需要再试。 分子里的那个计数让加成涨——这个节点被反复访问而某个动作一直没被选，它的加成越来越大，最终一定会被试到。 两个方向相反的计数器，L11 第九集专门讲过这一点，这里原样重现。

47 / 65

上一集那个「不对称」，具体就是这个式子造出来的。

讲解

现在可以回答上一集留下的问题：树为什么会长成偏的？ 讲座说得很直接：「下一次到达同一个节点时，我们可能会做不一样的事，因为计数变了」。机制就在那个式子里：某个动作的 Q̄ 很高 ⟹ 它会被反复选中 ⟹ 它下面的子树被反复深入 ⟹ 那一支长得很深。某个动作的 Q̄ 很低 ⟹ 加成虽然在涨，但涨的是 √ln，涨得很慢 ⟹ 它偶尔被试一次 ⟹ 那一支几乎不长。 √ln 这个增长率是关键：它慢到不会浪费预算（不会强迫你均匀展开），又快到最终一定会试（不会永久放弃任何一支）。 树的形状不是设计出来的，是这个式子长出来的。 这就是 MCTS 最漂亮的地方：它没有任何一处显式地说「往哪长」，形状完全是统计量的副产品。

48 / 65

c \sqrt{\frac{\ln n (s)}{n (s, a)}}

指名反驳：是 UCB 的乐观加成，两个方向相反的计数器。

讲解

指名回去：那不是折扣因子，是 UCB1 的探索加成 c·√(ln N(s)/N(s,a))。父节点的计数让它涨，这个动作自己的计数让它缩——L11 第九集那对方向相反的计数器，在这里第二次出现。 但 UCT 有两个假设值得存疑，而讲座两个都点了名。 第一个：「每个节点是一个独立的老虎机」——那么同一个状态在树的两个不同位置出现时，它们的统计量不合并。下一集。 第二个：「用 UCB，也就是用乐观」——而乐观在规划里到底对不对？课上就有学生把这个问题提了出来，讲座当时的回应是 「这是不是个好主意（笑）……我们等下回来说」。 第九集就是回来说这件事，而那是这一讲最好的部分。

49 / 65

知识点 7 · 总结

UCT：每个树节点当成一个独立的老虎机

核心结论

树策略 = argmax_a [ Q̄(s,a) + c·√(ln N(s)/N(s,a)) ]。N(s)（父节点总访问）在分子 log 里让加成涨；N(s,a)（这个动作自己）在分母让它缩 —— L11 第九集那对方向相反的计数器，第二次出现。

底层机制

上一集那个「不对称」就是这个式子造出来的：Q̄ 高的分支被反复深入，Q̄ 低的分支加成按 √ln 涨得很慢、几乎不长。树的形状不是设计的，是统计量的副产品。

常见误解

误解：「那个加成是个折扣因子」（转录稿的说法）。折扣作用在时间上、是常数、让远的变小；加成作用在不确定性上、随计数变、让陌生的变大。

与你的考试

讲座自己点名了 UCT 的两个可疑假设：① 每个节点独立（同一状态在两处不合并，下一集）；② 用乐观（第九集 —— 学生当场问，讲座回「这是不是个好主意（笑）……等下回来说」）。

50 / 65

知识点 7 · 检验

UCT 的树策略里，父节点访问数 N(s) 和该动作自身计数 N(s,a) 各起什么作用？

知识点 9

8 · 树不是图 —— 它拒绝合并相同的状态

51 / 65

同一个状态动作对，在树的两个不同位置出现。合并吗？

讲解

MCTS 长出来的是一棵树。而树有一个性质：每个节点只有一个父亲。现实不是这样。围棋里同一个局面可以由不同的着法顺序到达；网格世界里同一个格子可以从上面来也可以从左边来。讲座举的例子就是这个：「你可能在树的这部分有 s₁, a₁，在那边也有 s₁, a₁」。那么问题是：这两处的统计量要不要合并？ 直觉上显然要——同一个状态就是同一个状态，合并了信息量翻倍。 而 UCT 不合并。

52 / 65

当然要合并马尔可夫嘛，同一个状态就是同一个状态

讲座原话：「我们不合并它们的计数，把每个节点当成完全不同的」。

讲解

这个直觉在原理上是对的——而这正是这一集有意思的地方。讲座的原话是： 「we're not combining their counts. We're treating every node as if it's totally distinct.」 然后她自己补了最关键的一句： 「Even though often the model we'll be using to simulate will be Markov.」 ——尽管我们用来模拟的那个模型通常是马尔可夫的。 也就是说：算法明知道这两个节点是同一个状态，却故意装作不知道。 这显然浪费信息。那为什么还这么做？

53 / 65

理由是实现复杂度：在图上做那四步，比在树上难得多。

讲解

讲座给的理由很实在：「you can do it, it's mostly that it becomes a lot more complicated for implementation if you wanted to basically treat it as a graph instead of a tree」。 可以做，只是实现复杂得多。 具体难在哪？上一集那四步全都要改：回传：树上只有一条路径回到根，沿着它更新就完了。图上一个节点有多个父亲，一次模拟的结果要回传给哪些祖先、各算几次？处理不好会重复计数，让某些路径的统计量被系统性放大。选：UCB 里的 N(s) 是「父节点的访问数」——在图上「父节点」不唯一，这个量本身要重新定义。循环：图可以有环，而「从这个节点出发的回报」在有环的图上不再是一个良定义的有限展开。 所以这是一个工程取舍，不是一个原理判断。

54 / 65

账要算全：浪费了信息，换来了正确性上的简单和实现上的可控。

讲解

把这笔账算全，因为两边都是真的。亏的：同一个状态在树的 k 个位置出现，它的统计量被分成 k 份。每一份都更嘈杂，收敛更慢。状态空间里「殊途同归」越多，浪费越大——围棋里这个现象（叫「转置」）非常普遍。赚的： 回传只有一条路径，不会重复计数，不需要考虑该给哪些祖先记账。 N(s) 有明确含义，UCB 的式子可以直接用。 没有环，「从这个节点出发的回报」永远良定义。 这个取舍的形状值得记住：放弃一部分统计效率，换取一个结构上更简单、更不容易出错的算法。它和 L13 第四集那个「故意扔掉数据」是同一类，但理由不同：那里是证明逼出来的，这里是实现逼出来的。两个都不是优点，两个都要知道自己在放弃什么。

55 / 65

指名反驳：直觉没错。是算法为了实现简单主动放弃了它。

讲解

指名回去——但这一次不是反驳，是确认： 「同一个状态该合并」这个直觉是对的。是 UCT 为了实现上的简单，主动放弃了这份信息。讲座自己说得很清楚：可以做，只是复杂得多。 而这类取舍会随着工程能力变化。后来的实现里处理转置（把树变成有向无环图）是常见做法；AlphaZero 一类用神经网络给节点估值，本身就带来了跨位置的泛化——网络不知道也不在乎这是树的哪一处，相同的局面自然得到相同的估值。 所以这一条是「2019 年的 UCT 是这样」，不是「MCTS 必须这样」。 读算法时能分清这两种陈述，是这一整套片子一直在练的事： 哪些是原理（策略改进定理、UCB 的两个计数器方向相反）。 哪些是当时的工程取舍（不合并转置、随机 rollout、扔掉第 m 个之后的数据）。 前者过十年还对，后者不一定。 下一集是最后一集，也是这一讲最好的一集：讲座回头质疑了它自己刚教完的东西。

56 / 65

知识点 8 · 总结

树不是图 —— UCT 拒绝合并相同的状态

核心结论

同一个 (s,a) 出现在树的多处，统计量不合并。讲座原话：「we're not combining their counts... every node as if it's totally distinct」，并补了「even though the model is often Markov」。

底层机制

理由是实现复杂度（讲座：「it becomes a lot more complicated for implementation」）：图上一个节点多个父亲，回传该记给谁、会不会重复计数、N(s) 怎么定义、有环怎么办 —— 四步全要改。

常见误解

~~这一条不是反驳~~：「该合并」这个直觉是对的，是算法主动放弃了它。

与你的考试

账要算全：亏了统计效率（同一状态分 k 份，围棋的「转置」非常普遍）；赚了回传唯一、无重复计数、无环。同 L13 第四集的形状，但那里是证明逼的、这里是实现逼的。

57 / 65

知识点 8 · 检验

UCT 为什么不合并树中不同位置出现的同一个状态？

知识点 10

9 · 而乐观在规划里是错的 —— 在脑子里做坏决策不疼

58 / 65

最后一集：讲者回头质疑了她自己刚教完的东西。

讲解

最后一集。讲完 UCT 之后，Brunskill 主动回到一个学生提过的问题，而她的开场白是： 「It's a little weird that we do bandits in each of the nodes.」 ——在每个节点上做老虎机，这件事有点怪。 这是整门课里少见的一段：讲者把自己刚教完的、而且是业界标准做法的东西，拿出来做结构性的质疑。而她的论证只有两句话，下面两镜。

59 / 65

乐观在这里同样正确L11 证过的，搬过来就行

L11 的乐观有一个前提：你真的会为坏决策付出代价。

讲解

这个错误模型特别值得拆，因为它看起来完全合规：L11 用四集证明了 UCB 的遗憾界，UCT 把它搬到树里，一切照章办事。 但搬一个原理的时候，要重新问一遍「它当初为什么对」。 L11 第五集给的理由是：乐观的拉动两难都赢——要么它真的好（不亏），要么它不好（但你学到了）。 而这个论证里有一个前提：结局一里的「不亏」和结局二里的「亏了这一步」，都是真的在发生。 Brunskill 的话是： 「We do it because we're actually incurring the pain of making bad decisions.」 ——我们之所以要乐观，是因为我们真的在承受坏决策的痛。 那么在规划里呢？

60 / 65

在脑子里模拟一个坏动作，你什么也不疼 —— 那个前提不成立。

讲解

在规划里，那个前提不成立。 Brunskill 的原话：「The weird thing about doing that for planning is that we're not suffering if we make bad decisions in our head.」 ——在脑子里做坏决策，我们什么也不疼。 模拟一个自杀的走法，没有任何人受损失。你花的只有计算。于是整个目标函数错了： UCB 最小化的是累积遗憾——「我在这些拉动里一共亏了多少」。而在规划里，这个量根本不该被在乎。 该在乎的是：我花这些模拟，能多快确定根节点该走哪一步。 她的说法是：「it doesn't actually matter if I simulate out bad actions, if it allows me to get a better decision at the root」——模拟坏动作根本不要紧，只要它能让我在根上做出更好的决定。 正确的目标是关于根节点 argmax 的信息增益，不是遗憾。

61 / 65

同样的预算：采不确定的那个，分开区间的概率高 8.7 倍。

讲解

看什么：右边那根高出近九倍。左边是把模拟预算花在乐观会选的那个动作上，右边是花在更不确定的那个上。要确定根节点该走哪一步，该采的是不确定的那个 —— 而 UCB 会一直采左边。　—— 讲座给了一个口头的例子，我把它做成了可以量的。设定（正是她画在板上的那个形状）： A1：均值高（0.60），而且已经测得很准（400 个样本）。 A2：均值低（0.40），但很不确定（只有 9 个样本）。现在再给 400 个模拟的预算，花在哪个上更能确定根节点的 argmax？我用「之后两条 95% 区间分离的比例」来量（分离了就说明能确定谁更好）：花在 A1 上 → 0.0604 花在 A2 上 → 0.5274 差 8.7 倍。 道理不难懂：A1 已经很准了，再给它 400 个样本，区间几乎不变；而 A2 的区间又宽又不确定，给它样本立刻收窄，于是两条区间分开了。 而 UCB 会一直选 A1——因为它的上置信界更高。用讲座的话说：「它就像在说，我不想在脑子里承受选错动作的代价，所以我还是选 A1」。 它在优化一个它根本不需要优化的东西。

62 / 65

指名反驳：不能直接搬。搬一个原理时，要重新问它当初为什么对。

讲解

指名回去：乐观不能直接从老虎机搬到规划，因为它当初成立的理由——「坏决策真的疼」——在规划里不成立。 而 Brunskill 的结论值得一字不改地记住，因为它把「批评」和「实用」两半同时说完了： 「it's not clear that the bandits at each node is the optimal thing to do, but it's pretty efficient.」 ——在每个节点上做老虎机是不是最优的，不清楚；但它相当高效。 一个能同时说出这两半的判断，是这门课最值得学的东西。不是「UCT 有缺陷所以不该用」，也不是「AlphaGo 用了它所以它是对的」——而是知道它为什么好用，同时知道它的理由在哪里断了。这也是这十六讲反复在做的事。整门课最后落在这句话上，很合适。 三个值得带走的形状，作为全课的结尾： 搬一个原理时，重新问它当初为什么对（这一集）。 分清哪部分是定理、哪部分是工程（L10 的 TRPO、L13 的 MBIE-EB、上一集的转置）。 正确不等于有用（L15 那个 −5 百万的界；L10 的 C=39600ε；L12 的 10^T）。十六讲到此结束。

63 / 65

知识点 9 · 总结

乐观在规划里是错的 —— 在脑子里做坏决策不疼

核心结论

L11 的乐观有一个前提：「we're actually incurring the pain of making bad decisions」。而规划里 「we're not suffering if we make bad decisions in our head」 —— 前提没了，结论也就没了。

底层机制

实测（A1 均值 0.60 已测准 n=400，A2 均值 0.40 很不确定 n=9，再给 400 个模拟）：把预算花在 A1 上，两条区间分离的比例 0.0604；花在 A2 上 0.5274 —— 差 8.7 倍。而 UCB 会一直选 A1。

常见误解

误解：「L11 证过了，搬过来就行」。搬一个原理时要重新问它当初为什么对。正确目标是关于根节点 argmax 的信息增益，不是累积遗憾。

与你的考试

讲座的结论一字不改：「it's not clear that the bandits at each node is the optimal thing to do, but it's pretty efficient.」 —— 能同时说出这两半的判断，是这门课最值得学的东西。

64 / 65

知识点 9 · 检验

为什么把 UCB 的乐观原则搬到规划里是可疑的？

知识点 11

完

65 / 65

讲解

这是最后一讲的最后一集，也是这一整套片子的结尾。说三件事。 第一，这一讲自己的收尾。Brunskill 回到「这门课想让你带走什么」，她给的第一条是：RL 和别的东西的根本区别，在于智能体要自己去搜集数据。于是数据是被自己的决策筛过的（她说的是 censored data，字幕写成了 sensored），这和监督学习的独立同分布假设完全不同；也和规划不同，因为你得先从世界里问出这些信息。她给的第二条更实际：拿到一个问题，先判断它该不该写成 RL，以及怎么写——「这往往是最难的部分之一，而且它对问题好不好解有巨大影响」。 第二，这门课反复出现过的几个形状。把它们放在一起看，比任何一讲单独看都清楚： 「精确但不可算 → 可算但有偏 → 把偏差量化成一个界」——L09 的相对性能恒等式到代理目标，L10 的 max KL 到平均 KL，L15 的 IS 到截尾，都是这个形状。 「定理正确，常数大到没法用」——L10 的 C=39600ε、L12 的 10^T 初始化、L15 的 10^L 取值范围。三次。而三次的出路都是：放弃理论上的最坏值，换一个只朝安全方向偏的近似。 「定理失效时先看前提」——L05 的压缩性、L08 的确定性最优策略、L10 的混合策略形状、L15 的覆盖条件。 「把误差挡在一个能检查的地方」——TRPO 的线搜索、MAGIC 用 IS 的区间去量模型的偏差、安全策略改进的下界闸门。 第三，这一讲结尾那个批评值得单独记住，因为它是整门课里少见的、讲者对自己刚教完的东西提出的结构性质疑：一个在 A 场景里被证明正确的原则，搬到 B 场景时要重新问一遍「它当初为什么对」。乐观在老虎机里对，是因为坏决策真的疼；规划里不疼，所以那个理由不再成立，哪怕算法照样跑得很好。 她的原话是：「it's not clear that the bandits at each node is the optimal thing to do, but it's pretty efficient.」——一个能同时说出这两半的判断，是这门课最值得学的东西。十五部片子到此结束。

CS234 L16 · 蒙特卡洛树搜索、基于模型的 RL 与全课收尾 · 全片速览

开场

1 · 拟合一个模型 = 拥有一个模拟器，而模拟器什么都能干

拟合一个模型 = 拥有一个模拟器，而模拟器什么都能干

2 · 代价：模型误差和规划误差叠在一起，而且会复合

两层误差叠在一起，而且规划器会放大模型的错误

3 · AB 例子：批 TD 与批 MC 收敛到两个不同的东西

AB 例子：批 TD 与批 MC 收敛到两个不同的值

4 · 前向搜索正确，但叶子数是 (|S||A|)^H

前向搜索正确，但叶子数是 (|S||A|)^H

5 · 简单蒙特卡洛搜索：恰好一步策略改进

简单蒙特卡洛搜索恰好是一步策略改进

6 · MCTS：故意长成偏的一棵树

MCTS：故意长成偏的一棵树

7 · UCT：每节点当独立老虎机，回报是整条 rollout

UCT：每个树节点当成一个独立的老虎机

8 · 树不是图 —— 它拒绝合并相同的状态

树不是图 —— UCT 拒绝合并相同的状态

9 · 而乐观在规划里是错的 —— 在脑子里做坏决策不疼

乐观在规划里是错的 —— 在脑子里做坏决策不疼

完