Lecture 13: 蒙特卡洛树搜索 —— 从模拟搜索到 AlphaZero（Monte Carlo Tree Search）

目录 · ← l12 · l14 →

Lecture 13: 蒙特卡洛树搜索 —— 从模拟搜索到 AlphaZero（Monte Carlo Tree Search）

对应材料：官方 lecture13pre.pdf（40 页）/ lecture13post.pdf（13 页；课上 Check-Your-Understanding 与解答均在 lecture13pre.pdf p34–40，post 版不含 CYU）｜Week 8 周三（Feb 25, 2026；Course Project 里程碑截止）｜参考阅读：Sutton & Barto (2018, 2nd ed.) Chp 8、David Silver Lec 8–9、Silver et al. AlphaGo（Nature 2017）与 AlphaZero（Science 2018） 一句话定位：L1–L12 里我们一直在求解整个状态空间（值迭代、Q-learning、策略梯度都在算一个全局策略 $\pi(a\vert s)$）；本讲第一次把目标改成”只把当前这一步算对“——用额外的局部计算（local computation）换一个更好的即时决策，于是模拟（simulation）取代参数更新成为策略改进的引擎；这条路线最终通向 AlphaGo/AlphaZero，也第一次让”搜索”与”学习”在同一套框架里互相喂养。

13.1 概述

本讲回答一个前十二讲从未正面提出的问题：如果我只关心”现在这一步该怎么走”，能不能把全部算力都花在当前状态上？ 讲义第 5 页把这层动机写得非常直接：“So far in class, compute a policy for whole state space. Key idea: Use additional local computation to make a better decision for right now.”（此前我们为整个状态空间计算策略；关键想法是：用额外的局部计算把”当下这一步”决策做得更好。）

本讲的技术主线是一条清晰的递进链。第一级是简单蒙特卡洛搜索（simple Monte-Carlo search，讲义第 6 页）：对每个候选动作 $a$ 从当前真实状态 $s_t$ 出发做 $K$ 次模拟回合（simulated episode / roll-out），用平均回报 $\bar Q(s_t,a)$ 评估，选最大者；讲义明确点出它的本质是”essentially doing 1 step of policy improvement“（只做了一步策略改进）。第二级是期望极大树（expectimax tree，讲义第 7–9 页）：既然有 MDP 模型 $\hat M$，为什么只做一步改进？可以构建一棵以 $s_t$ 为根的前向搜索树，直接算出当前状态的最优 $Q^*(s_t,a)$——但代价是树规模按 $(\vert \mathcal{S}\vert \vert \mathcal{A}\vert )^H$ 膨胀，对围棋这类问题彻底不可行。第三级是蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS，讲义第 10 页）：用采样代替穷举，迭代地用 $K$ 个模拟回合逐步构建并更新搜索树，只把算力投在最有希望的分支上。第四级是置信上界树搜索（Upper Confidence Tree search, UCT，讲义第 11–12 页）：借 L9 多臂老虎机（multi-armed bandit, MAB）的 UCB 思想决定”模拟回合里该往哪个子节点走”。第五级（讲义第 15–32 页）是把 MCTS 与深度网络（策略网络 + 价值网络）、自我对弈（self-play）缝成 AlphaGo/AlphaZero 闭环。

本讲在课程知识链中的位置很特殊：它是第一次把 L9–L12 的 bandit 探索理论直接用作一个真实大型系统的核心组件（UCT 就是 UCB1 被贴到树上），也是唯一一讲以”推理时算力（test-time compute）”而非”训练时数据”作为性能主轴的讲次。讲义第 33 页的 Class Structure 把位置标得很清楚：”Last time: Fast / sample efficient Reinforcement Learning；This Time: MCTS；Next time: Rewards in RL”——本讲是”数据高效 RL”三连讲（L11–L13）的收尾，也是课程从”如何学”转向”该优化什么”之前的最后一块技术拼图。

13.2 核心概念的数学形式化

本讲引入或深化 6 个关键概念。按 SPEC.md §2 的要求，每个概念给出「严格定义 → 直观解释 → 具体示例 → 与监督学习/前序方法的对比」。

13.2.1 模拟搜索（Simulation-Based Search）与前向搜索（Forward Search）

严格定义. 给定一个 MDP $M=\langle \mathcal{S},\mathcal{A},P,R,\gamma\rangle$，其生成模型（generative model）$\hat M$ 只要求提供一个采样接口

而不要求给出显式的 $P(s^{\prime}\vert s,a)$ 表或 $R(s,a)$ 函数。模拟搜索指：以当前真实状态 $s_t$ 为根，用 $\hat M$ 与某个模拟策略（simulation policy）$\pi$ 生成大量模拟轨迹（simulated trajectories）

再从这些轨迹中估计动作价值并据此决策。前向搜索（forward search）是讲义第 8 页给出的术语：“Forward search algorithms select the best action by lookahead. They build a search tree with the current state $s_t$ at the root.” 其核心保证是局部性——“No need to solve whole MDP, just sub-MDP starting from now.”（不必求解整个 MDP，只求解”从现在开始的子 MDP”。）

直观解释. 想象你站在一个陌生城市的十字路口。全局求解相当于先画一张全市交通流量图（求解整个 MDP），然后按图走；模拟搜索则是：闭上眼睛在脑子里把”往左走”这条路预演 100 遍、”往右走”预演 100 遍，看哪边平均更快到达目的地，然后走那一步——到了下一个路口再重新预演。预演用的是你脑子里的”世界模型”（$\hat M$），预演时的行走方式可以很笨（随机走，即默认策略），但只要预演次数够多、平均下来，”哪边更好”就浮现出来了。

具体示例（本讲 13.4 实验一的 4×4 GridWorld，具体数字）. 状态 16 个（$4\times4$ 网格，行优先编号 $s=r\cdot 4+c$），动作 4 个（0 上 / 1 右 / 2 下 / 3 左），起点 $(3,0)$ 即 $s=12$，目标 $(0,3)$ 即 $s=3$（奖励 $+1$，终止），陷阱 $(0,2)$ 即 $s=2$（奖励 $-1$，终止），每步奖励 $-0.01$，$\gamma=0.95$，滑移（slip）概率 $0.10$：以 $0.9$ 执行意图动作、$0.05$ 各执行一个垂直方向动作（撞墙则原地不动）。用值迭代（L2）在已知的表格模型上求得参考解

最优首步动作是 $a^=1$（右）。模拟搜索的任务就是在不做值迭代的前提下，仅靠 sample(s,a) -> (s',r) 这个黑箱接口，把 $a^=1$ 找出来。

与监督学习/前序方法的对比. 值迭代（L2）需要 $P(s^{\prime}\vert s,a)$ 的枚举式访问，复杂度 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$ 每轮；MCTS 只需要采样式访问，复杂度与 $\vert \mathcal{S}\vert $ 无关（见 13.5）。这与 L11–L12 的”生成模型 vs 显式模型”之分完全同源：有生成模型时，采样可以替代枚举。

13.2.2 简单蒙特卡洛搜索（Simple Monte-Carlo Search）

严格定义（讲义第 6 页原文的精确转写）. 给定模型 $\hat M$ 与模拟策略 $\pi$：

1. 对每个动作 $a\in\mathcal{A}$：从当前真实状态 $s_t$ 出发模拟 $K$ 个回合，得到 $\{s_t,a,R^k_{t+1},\dots,S^k_T\}_{k=1}^{K}\sim \hat M,\pi$；
2. 用平均回报做蒙特卡洛评估：

其中 $G_t^{(k)}=\sum_{j\ge 0}\gamma^{j}R_{t+j+1}^{(k)}$ 是第 $k$ 条轨迹的折扣回报（记号遵循 SPEC §4）；

1. 选当前真实动作：

讲义用一句评语点明其理论地位：“This is essentially doing 1 step of policy improvement.”

直观解释. 这是最朴素的”脑内预演”：每个动作都试 $\rho=K$ 次（注意是每个动作都要试，所以总模拟预算其实是 $\vert \mathcal{A}\vert \cdot K$），谁的平均回报高就走谁。它没有任何”记忆”——同一棵搜索树不会跨步骤复用，每一步都从零开始。

具体示例. 在上面的 GridWorld 里，取 $\vert \mathcal{A}\vert =4$、总预算 $K_{\text{tot}}=200$ 时，每个动作分到 $50$ 次模拟：$\hat Q(s_{12},\cdot)$ 就是 4 个 50 次采样的均值，取最大者。实测（13.4 表 B，30 局真实评测）成功率 $0.967$；预算降到 $10$（每动作仅 $2\sim3$ 次）时成功率掉到 $0.767$。关键限制：总预算必须按 $\vert \mathcal{A}\vert $ 均分，因为”每个动作都要评估”——当 $\vert \mathcal{A}\vert =361$（围棋）时，即使 $K_{\text{tot}}=10^4$ 也只有 27 次/动作，精度极差。这正是 MCTS 要解决的问题。

与监督学习的对比. 简单 MC 搜索相当于”对每个候选答案独立跑一遍交叉验证“，代价随候选数线性增长；MCTS 相当于”把预算按潜力动态分配“，把大量算力集中到少数几个分支上——这是主动采样（active sampling）与被动均匀采样的区别，也直接呼应了 L9 中”均匀探索 vs 自适应探索”的对比。

13.2.3 期望极大树（Expectimax Tree）：为什么不能直接穷举

严格定义. 若拥有完整 MDP 模型 $\hat M$，则以 $s_t$ 为根、按 Bellman 最优方程递归展开的期望极大树可以在根节点直接算出

直观解释. 这就是”把值迭代只在一条路径上展开”。树的每一层交替出现两种节点：动作节点（我方选 $\max$，”期望极大”因此得名）与机会节点（环境按 $P$ 抽 $s^{\prime}$，取期望）。轮到我方选就挑最好的，轮到环境抽就按概率加权。

具体示例（讲义第 9 页的具体数字）. 讲义第 9 页写明限制：“Size of tree scales as $(\vert S\vert \vert A\vert )^H$.” 以围棋为例，$\vert \mathcal{S}\vert $ 的量级是 $10^{170}$（合法局面数上界）、$\vert \mathcal{A}\vert \le 361$、典型对局长度 $H\approx 150$，则树规模是天文数字；即使换成前面那个 $16$ 状态的玩具 GridWorld，若视界 $H=20$，树规模也是 $(16\times 4)^{20}=64^{20}\approx 1.3\times10^{36}$——远超任何算力。

与 MCTS 的对比. 期望极大树的问题是两个乘法：分支因子 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert $ 与深度 $H$。MCTS 对这两个乘法各下一刀：(i) 用采样代替对所有 $s^{\prime}$ 求期望（机会节点不再展开，只走被抽到的那一条）；(ii) 用 UCB 引导的选择代替全宽扩展（动作节点也不展开，只走最值得走的那一条）。于是 $O\bigl((\vert \mathcal{S}\vert \vert \mathcal{A}\vert )^H\bigr)$ 变成 $O(K\cdot H)$——这就是讲义第 13 页第二条优势”Uses sampling to break curse of dimensionality”（用采样打破维数灾难）的确切含义。

13.2.4 蒙特卡洛树搜索（MCTS）的四个阶段

严格定义（讲义第 10 页 + Silver Lec 8 的标准四阶段表述）. 给定模型 $\hat M$、当前状态 $s_t$、模拟预算 $K$：

1. 构建以 $s_t$ 为根的搜索树；
2. 重复 $K$ 次下述四阶段（每次消耗一次模拟）：
   • 选择（Selection）：从根出发，在”已充分扩展”的节点上用树策略（UCT）选子节点，直到抵达一个未被完全扩展的节点或终止节点；
   • 扩展（Expansion）：为该节点添加一个（或多个）新子节点；
   • 模拟 / 评估（Simulation / Rollout）：从新节点用默认策略（default policy，通常均匀随机）走到终止，得到回报 $G$；
   • 回传（Backpropagation）：把 $G$ 沿访问路径回传，更新路径上每条边的 $N(s,a)$ 与 $Q(s,a)$；
3. 搜索结束后，在根节点选价值最大的真实动作：$a_t=\arg\max_{a\in\mathcal{A}}Q(s_t,a)$。

讲义第 12 页特别强调了一句容易被忽略的话：“This implies that the policy used to simulate episodes with (and expand/update the tree) can change across each episode.”（这意味着用于模拟回合的策略可以逐回合变化。）——这正是 MCTS 与简单 MC 搜索的分水岭：简单 MC 用固定的 $\pi$ 跑完所有回合；MCTS 的模拟策略是树本身，它每回合都在更新，所以后来者比先行者更聪明。

直观解释. 把 MCTS 想成一个会做笔记的棋手。第一次面对某个局面时，他什么都不懂（树只有一个根），只能随便挑个动作、随便下完（扩展 + 随机模拟），把结果记在小本子上（回传）。第二次再想这个局面，小本子上已有”某个动作上次拿了正回报”，他就更倾向再试那个动作，但也给别的动作留一点机会（UCT 选择）。随着笔记越来越厚，”哪个动作好”越来越清楚，而笔记的厚薄本身决定了他在哪些分支上继续深挖。

具体示例（本讲 13.4 实验一的真实数字）. 在 $s_{12}$ 处做一次 $K=2000$ 的搜索后，根节点的统计量是（$c=\sqrt 2$）：

$N(s)=\sum_a N(s,a)=2000$（预算被完整用掉），共创建 2315 个不同树节点，MCTS 选出的动作 $=1$，与值迭代的 $\arg\max_a q^*$ 一致。注意四列的 $Q+U$ 几乎完全相等（$-0.0745\sim-0.0712$，极差仅 $0.003$）——这正是 UCT 平衡点的标志性特征：在收敛的搜索里，每条臂的”价值 + 不确定性”被拉到同一水平线。

与监督学习的对比. 监督学习的”训练”与”预测”是两个分离阶段；MCTS 把两者压缩到同一次决策内部：四阶段循环既在”收集数据”（模拟），又在”改进策略”（回传更新 $Q$），是典型的在线规划（online planning）。

13.2.5 UCT：把每个树节点当作多臂老虎机

严格定义（讲义第 12 页原文）. UCT 借 bandit 文献的思想：“treat each node where can select actions as a multi-armed bandit (MAB) problem. Maintain an upper confidence bound over reward of each arm at a node.” 讲义给出的具体形式是

其中 $N(i,a)$ 是在节点 $i$ 选择臂 $a$ 的次数，$G_k(i,a)$ 是从节点 $i$ 执行 $a$ 后第 $k$ 次模拟得到的折扣回报，$N(i)=\sum_a N(i,a)$；模拟回合 $k$ 在节点 $i$ 选

讲义保留了 $O(\log N(i))$ 的大 $O$ 记号（强调这是渐近量级）；实际实现时取 $O(\log N(i))=\ln N(i)$，即本讲与 L14 通用的可计算形式

关于探索常数 $c$ 的理论取值（讲义未给显式标定，此处按 UCB1 的标准论证补充并标注）. 讲义只说 $c>0$；在 L9 的 UCB1 中，若奖励取值范围是 $[0,1]$、置信水平取 $\delta=1/t^2$，则置信半径为 $\sqrt{2\ln t/n}$，即 $c=\sqrt 2\approx 1.414$。按 Hoeffding 不等式的一般形式，半径应为 $\sqrt{\ln(1/\delta)/(2n)}$，因此常数 $c$ 正比于奖励的取值范围（range）：把奖励从 $[0,1]$ 放大到 $[0,R_{\max}]$，$c$ 应当同比例放大，否则 bonus 会被 $Q$ 的尺度淹没。这一”$c$ 与奖励范围相关”的结论就是本讲 13.4 实验二（$c$ 敏感性）的理论依据。

为什么这”略微奇怪”（讲义第 36/38 页的 Optional CYU）. 讲义原文提问：“Check your understanding: Why is this slightly strange? Hint: why were upper confidence bounds a good idea for exploration/exploitation? Is there an exploration/explotation problem during simulated episodes?” 答案分三层：

1. UCB 在真实环境中之所以重要，是因为每次拉臂都有真实机会成本（真实的 regret），且回报分布未知；
2. 在模拟回合里，回报由已知模型 $(\hat M,\pi)$ 生成，可以无限次重采样，每次”拉臂”的真实成本只是计算时间，不是环境后悔；
3. 因此 UCT 最小化的”regret”是一个内部代理量——它在解”下一步模拟该把算力花在哪”这个算力分配问题。讲义脚注把它归入元层推理（metalevel reasoning），并引 Hay, Russell, Tolpin & Shimony (2012)《Selecting Computations: Theory and Applications》。所以”在模拟里做探索/利用权衡”在形式上有意义、在语义上是另一件事。

讲义第 37/27 页的 UCT CYU 原题与答案. “In UCT search we treat each tree node as a MAB, and use an upper confidence bound over the future value of each action to help select actions for later rollouts. Select all that are true: (1) This may be useful since it will prioritize actions that lead to later good rewards; (2) UCB minimizes regret. UCT is minimizing regret within rollouts of the tree. (If this is true, think about if this is a good idea?) (3) Not sure.” ——讲义给出的答案是 “T. T”：两条都真。因此 UCT 确实是在树内最小化、并在元层意义上把好动作优先化。

具体示例（本讲 13.4 实验二的真实数字，$K=200$）. 在 $s_{12}$ 处，不同的 $c$ 给出极为不同的根访问分布：

$c=0.1$ 时 $N(s,\cdot)=[130,26,43,1]$：搜索把 $130/200$ 的预算押在动作 0（上，次优）上，最优的动作 1 只拿到 26 次——“太小 = 陷入局部”；$c=5.0$ 时分布几乎完全均匀 $[51,54,48,47]$，搜索退化成随机采样——“太大 = 随机”。这与 L9 中 UCB1 的 $c$（或 $\sqrt{2\ln t}$ 中的常数）扮演的角色完全一致。

与 L9 的对比. L9 的 UCB1 面对 $A$ 个静态臂、最小化环境 regret；UCT 面对树上每个节点的 $\vert \mathcal{A}\vert $ 个动态臂（臂的收益分布随树增长而变化），最小化元层的算力分配损失。形式同构，语义不同——这也是本讲最容易混淆的一处。

13.2.6 MCTS 的五大优势（讲义第 13 页逐条）

讲义第 13 页（L14 第 3 页重申）用五行列出了 MCTS 的全部卖点。下面逐条给出精确定义与解释，这是本讲最核心的一张”论点清单”。

（1）Highly selective best-first search（高度选择性的最佳优先搜索）. 定义：搜索树的扩展顺序由当前价值估计决定，而非按固定顺序（广度优先/深度优先）；每次模拟只扩展一条路径，且这条路径由 UCT 选出的”当前看起来最好”的边组成。 直观：普通最佳优先搜索会维护一个优先级队列把所有已知节点排好；MCTS 更进一步——它只在有希望的分支上采样，因此在围棋那种 $361$ 个分支的树上，$10^4$ 次模拟能挖掘到 $10^4$ 层深的少数变化，而不是把算力均摊在根节点附近。 例证：在 Tic-Tac-Toe 的 P1 局面（13.4.2 表）里，$K=2000$ 次模拟把 $1929/2000$ 的预算投给了唯一的正确挡子动作 2，而其余五个动作合计只拿到 $71$ 次——算力被极度选择性地集中到了最有希望的分支上，这就是”高度选择性”的字面含义。

（2）Evaluates states dynamically（动态评估状态）. 定义：节点的价值 $Q(s,a)$ 不是一个预先训练好的静态函数 $\hat Q_\phi(s,a)$，而是该节点在本次搜索中被实际采样出来的蒙特卡洛均值 $\frac{1}{N(s,a)}\sum_k G_k$；它会随 $N(s,a)$ 增长而更新（回传阶段），并且同一状态在不同搜索中的估计可以不同。 直观：静态评估函数”看一眼局面就给分”；MCTS 是”把局面往下走看看会怎样再给分”。前者受限于函数逼近的表达能力，后者受限于模拟保真度与预算。 例证：13.4 实验一 $s_{12}$ 处的收敛序列（脚本真实打印）：$K=10$ 时 $Q(s_{12},\cdot)=[-0.3790,-0.3700,-0.1491,-0.2477]$（噪声主导，动作 1 甚至不是最高），$K=1000$ 时 $[-0.2820,-0.2401,-0.2194,-0.3209]$（排序仍然混乱），$K=5000$ 时 $[-0.2642,\mathbf{0.1075},-0.2520,-0.2627]$（动作 1 首次明显胜出），到 $K=20000$ 时 $[-0.3013,\mathbf{0.3866},-0.2679,-0.2651]$。这是”动态评估”最直接的证据：同一状态、同一模型，仅仅因为采样次数不同，价值估计从”噪声”变成”信号”。

（3）Uses sampling to break curse of dimensionality（用采样打破维数灾难）. 定义：期望极大树的代价是 $O\bigl((\vert \mathcal{S}\vert \vert \mathcal{A}\vert )^H\bigr)$（讲义第 9 页），其中 $\vert \mathcal{S}\vert $ 出现在指数底数上；MCTS 用采样替代对所有 $s^{\prime}$ 求期望、用 UCT 替代全宽扩展，代价变成 $O(KH)$，$\vert \mathcal{S}\vert $ 不再出现在复杂度里。 直观：值迭代要遍历所有状态（维数灾难）；MCTS 只访问被采样到的那几条路径，等于在一个巨大空间里做随机稀疏探索。 例证：本讲 GridWorld 只有 16 个状态，但 MCTS 从不遍历它们——2000 次模拟只走出一条条采样路径，创建了 2315 个树节点（含同一状态经不同动作到达的多条边）。在围棋里 $\vert \mathcal{S}\vert \sim10^{170}$，采样是唯一可能的手段。

（4）Works for “black-box” models (only requires samples)（适用于黑箱模型）. 定义：只要求 $\hat M$ 提供 $(s^{\prime},r)\sim P(\cdot\vert s,a)$ 的采样，不需要 $P(s^{\prime}\vert s,a)$ 的解析式、不需要可微、不需要状态是向量。等价地说，MCTS 可以与一个模拟器（simulator / emulator）直接对接。 直观：这是”模型无关（model-free）”思想在规划侧的对应物——L3–L4 的 MC 与 TD 用经验样本取代模型；MCTS 用模拟样本取代模型。两者都在回避”写不出 $P$”这个现实困难。 例证：13.4 的两个实验都只用了一个 sample(s, a, rng) 接口来生成 $(s^{\prime},r)$；Tic-Tac-Toe 实验甚至连 sample 都不需要（规则本身就是黑箱），MCTS 完全靠”下一个合法局面”这一个操作运行。AlphaGo 用的是围棋规则模拟器，AlphaZero 推广到国际象棋/将棋（讲义第 32 页）同样只需要各自的规则引擎。 注意：讲义第 15 页的 Check Your Understanding 问：“does playing Go involve learning to make decisions in a world where dynamics and reward model are unknown?”——答案是是。围棋的规则对程序员是已知的（所以能写模拟器），但对 agent 的策略学习而言，它只被当作一个可调用的黑箱；奖励（胜负）仅在对局结束时可观测，是极端稀疏的终局信号。

（5）Computationally efficient, anytime, parallelisable（计算高效、随时可停、可并行）. 定义（三部分）：

• 计算高效：每次模拟的代价是 $O(H)$（一次 rollout 的长度），不需要求逆、不需要梯度、不需要网络前向；
• 随时可停（anytime）：算法在任何模拟次数 $K$ 之后都能立刻给出一个可用决策 $\arg\max_a Q(s_t,a)$，且质量单调（经验上）随 $K$ 提升——这使它天然适配时间受限的场景（例如围棋比赛有读秒）；
• 可并行（parallelisable）：$K$ 次模拟相互独立（除共享树统计量外），可以先跑 $P$ 条独立搜索再聚合，或用叶并行（leaf parallelisation）/ 根并行（root parallelisation）/ 树并行（tree parallelisation） 三种经典方案在多核/多机上加速。

直观：MCTS 是一个可以随时打断的算法。想象下棋时只剩 3 秒，你就跑 300 次模拟；剩 3 分钟，就跑 30000 次。同一份代码、同一个模型，性能随预算平滑变化——这是它比”必须先训练好才能用”的 DQN/PPO 更贴合真实决策场景的地方。 例证：13.4 实验一里成功率随预算的单调上升就是 anytime 性质的实测证据（下面这张表直接来自脚本输出）：

三条曲线都单调上升，且 MCTS 在 $K=200$ 时就已到 $1.000$。真正的差距不在网格世界这种稠密奖励环境里（该环境的四个动作 $q^*$ 只差 $0.043$，几乎”怎么走都对”），而在 Tic-Tac-Toe 那种决策有唯一正解的稀疏奖励环境里——13.4.2 的对弈实验给出 MCTS 胜 30 / 简单 MC 胜 7 / 和 3（$K=20$）的决定性差距。

13.2.7 与 AlphaGo / AlphaZero 的连接：PUCT、三阶段改进与策略迭代视角

讲义第 4 页把全讲目录分成两半：1 Simulation-Based Search 与 2 AlphaZero（与此同时 L14 继续展开 AlphaZero）。本小节把讲义第 15–26 页（及 L14 第 5–22 页）的工程改造压缩成一条主线：AlphaGo/AlphaZero = MCTS + 深度网络 + 自我对弈，三项改造各解决 MCTS 的一个瓶颈。

改造一：用策略网络先验替代均匀先验 —— PUCT 选择规则。 严格定义：设网络输出 $f_\theta(s)=(\mathbf p_\theta(\cdot\vert s),v_\theta(s))$，其中 $\mathbf p_\theta\in\Delta^{\vert \mathcal{A}\vert }$ 是动作先验、$v_\theta(s)\in[-1,1]$ 是价值预测。选择规则从 UCT 换成 PUCT（Predictor + UCT）：

直观解释：UCT 的 bonus 只看”这条边被访问过几次”（与先验无关），因此在一个 $361$ 个落点的棋盘上，它必须先把 361 个动作各试一遍才能开始有意义的深挖。PUCT 的 bonus 是 $P(s,a)\cdot\frac{\sqrt{N}}{1+N_a}$：网络说”这一手有希望”（$P$ 大）的动作一开始就获得更高的优先级，网络看不好的动作即使没被访问也排在后面。这把有效搜索宽度从 $361$ 压到几十个分支。维度上这是决定性的：围棋若用 UCT 需要 $10^5$ 量级模拟才能铺满根节点，PUCT 在 $1600$ 次模拟内就能达到世界冠军水平。 具体示例（13.4.2 实测）：本讲用一个手工启发式先验 $P$ 模拟网络。在 Tic-Tac-Toe 上，PUCT 在 $K\ge20$ 后正确率反超 UCT（$K=20$：$0.867$ vs $0.713$；$K=50$：$0.975$ vs $0.900$）；在 24 个随机中局上，先验 top-1 动作的访问占比从 UCT 的 $0.469$（$K=20$）提到 PUCT 的 $0.571$。先验把搜索”领”到了正确的地方。 与 L9 的对比：这仍是 UCB 族，只是把”不确定性驱动的探索”换成了”先验驱动的探索 + 访问计数驱动的修正”。AlphaZero 论文中 $c_{\text{puct}}$ 取与模拟预算相关的常数（1600 次模拟时约 1–5 量级）。

改造二：用价值网络替代（或补充）随机 roll-out。 严格定义：AlphaGo/AlphaZero 在到达叶节点时不再（只）做随机走到底，而是直接取 $v_\theta(s_{\text{leaf}})$ 作为该叶的估值，再用它回传：

直观解释：随机 roll-out 是 MCTS 最贵、最不准的一环——在围棋里一次随机走到底要几百步，而价值网络一次前向就给出一个远比”随机走完”准确的胜负估计。讲义第 9 页（L14 第 9 页）的标题即 “At Leaf, Plug in Network Predictions for Value”。 具体示例：本讲 13.4 实测证明随机默认策略带来的偏差有多大——GridWorld 中 $K=20000$ 次模拟后 $Q(s,a)$ 与 $q^(s,a)$ 仍相差 $0.9841$，$Q(s,0)$ 的符号都是错的。若把 $G_{\text{leaf}}$ 换成准确的 $v(s)$，这个偏差会立刻消失。这正是”默认策略质量决定 $Q$ 的偏差”（13.5.2 条件依赖表第一行）的量化证据。 *与 L2/L11 的对比：价值网络就是一个泛化的值函数逼近器（L2 的表格 $V$ 的神经网络版），它的引入把 MCTS 从”纯采样”变成”采样 + 泛化”——这也是 MuZero 能够学习隐空间模型的基础。

改造三：自我对弈闭环 —— MCTS 作为策略改进算子。 严格定义（L14 第 6–15 页的教材式表述）：第 $k$ 轮迭代中，(i) 数据生成：用 $f_{\theta_k}$ 驱动 MCTS 与自身对弈，每步记录状态 $s_t$、根访问分布 $\boldsymbol\pi_t$（其中 $\pi_t(a)\propto N(s_t,a)^{1/\tau}$）与终局结果 $z\in\{-1,+1\}$；(ii) 标签构造：$\boldsymbol\pi_t$ 作策略头回归目标、$z$ 作价值头回归目标；(iii) 参数更新：最小化

直观解释：这是一个学生—老师角色互换的循环。MCTS 是”老师”，因为它把 $1600$ 次模拟的算力兑换成一个比原始网络更好的决策分布；网络是”学生”，它把这个分布压缩成一次前向传播。学生变强后，下一轮给老师提供的先验更好，老师看得更深更准——搜索与网络互相抬轿子。 具体示例：本讲 13.4.2 在 Tic-Tac-Toe 上实测了这个闭环的两个关键环节。第一，$\pi(s)\propto N(s,a)^{1/\tau}$ 确实是一个强策略：20 局自我对弈中先手只赢 11 局（而非碾压），说明双方都已接近最优（Tic-Tac-Toe 完美对弈必和）。第二，把 MCTS 换成”同预算的简单 MC 搜索”后对弈结果从 30:7（MCTS 视角）大幅劣化——说明”改进”来自 MCTS 这个算子本身，而非来自任何网络训练。 策略迭代视角：$\pi_{\text{MCTS}}$ 是 $\pi_\theta$ 的策略改进（policy improvement）算子：只要 $Q$ 估计无偏，$\max_a Q(s,a)\ge \sum_a\pi(a\vert s)Q(s,a)=V^\pi(s)$ 就保证新策略不劣于旧策略（L4/L6 的策略改进定理）。因此 AlphaZero 的训练循环可读作”评估–改进–蒸馏“：MCTS 用网络做评估、MCTS 本身做改进、梯度下降把改进结果蒸馏回网络。这就是讲义第 16 页六条特征里 “Strategic Computation”（策略性计算） 与 “Learn and Update Heuristics”（学习并更新启发式） 的合体。 与 L8 的对比：形式上与行为克隆（Behavior Cloning）完全同构——都是交叉熵拟合一个 teacher 分布。差别在 teacher 来源：模仿学习的 teacher 是人类专家（外部、固定、有上限），AlphaZero 的 teacher 是自己的搜索（内部、随训练共同进化、上限是算力与价值估计精度）。

13.2.8 影响分析：AlphaGo / AlphaZero 到底强在哪里（讲义第 27–31 页）

⚠️ 关于本小节的证据等级：讲义第 27–31 页是纯图片页——第 28–31 页各只有一个标题加一个脚注 Images from Silver et al. Nature 2017，页面上没有任何可提取的文字、数字或坐标轴标签 （第 27 页的标题与三个评价问题例外，见下）。本会话的模型无法读取图像，环境也没有 OCR 工具。 因此下面给出的不是”从讲义图上读出的数值”，而是： ① 第 27 页逐字可提取的三个评价问题（这部分是原文）； ② 每张图按标题与 Silver et al. (2017) 原论文的口径说明它在比较什么、横纵轴是什么； ③ 用本讲与 L14 的自跑实验给出同方向的定量证据（这些数字全部来自 cs234/code/，可复现）。 凡属推测处均已显式标注。这一处理方式与本笔记对 L14 伦理页图片的处理一致：宁可标注”无法核实”，也不编造图上数字。

讲义第 27 页原文给出的四个特征与三个评价问题（逐字）：

Features: Self Play · Strategic Computation · Highly selective best-first search · Power of Averaging · Local Computation · Learn and Update Heuristics

Evaluation Questions:

1. What is the influence of architecture?
2. What is the impact of using MCTS (on top of learning a policy / value function)?
3. How does it compare to human play or using human play?

这三个问题正是第 28–31 页四张图分别回答的对象。它们之所以值得单列，是因为 AlphaGo/AlphaZero 的每一个组件都有代价（算力、数据、工程复杂度），若不把”哪个组件贡献了多少”拆开，就无法判断投入该往哪里放。

（1）Impact of Architecture（第 28 页）

这张图在比较什么：按 Silver et al. (2017) 的口径，这一组消融把 AlphaGo Zero 的三个组件逐一去掉—— ① 去掉搜索、只留原始策略网络（raw network）；② 去掉策略网络、只留价值网络做搜索；③ 完整 AlphaGo Zero—— 比较它们的 Elo 随训练时间的变化。原论文的结论是：完整系统显著优于任一单组件，且”raw policy”最弱。

本讲的对应实证：L14 的两因素分解实验（L14_mcts_uct.py §B2）给出同方向但更可控的证据—— 在同一 6×6 环境、同一 $K=500$ 预算下：

即先验质量带来的增益（$0.548\to0.871$，$+0.32$）远大于价值网络质量带来的增益（$0.548\to0.568$，$+0.02$）， 而两者俱佳时并没有进一步叠加（仍为 $0.871$）。这与”架构中不同组件的边际贡献差异巨大”是同一结论， 但请注意：这是本讲自跑实验的结论，不能直接外推到围棋（围棋规模与网络容量都不同）。

（2）Impact of MCTS（第 29 页）

这张图在比较什么：固定策略/价值网络，只改变搜索预算（每次落子的模拟次数），看 Elo 如何变化； 原论文显示 Elo 随模拟次数单调上升但边际递减，且搜索带来的增益在新网络（训练更久）上依然存在。

本讲的对应实证：L13_mcts.py 的随机 GridWorld 实验（讲义式环境）给出同方向的曲线—— 简单 MC 搜索的成功率随 $K$ 单调上升：$K=10\to0.767$、$K=50\to0.933$、$K=200\to0.967$、$K=1000\to1.000$； MCTS 更强：$K=10\to0.800$、$K=1000\to1.000$（平均回报 $0.6690$ vs 简单 MC 的 $0.6244$）。 边际递减同样可见：成功率在 $K=200$ 已达 $0.967$，$K$ 再增 5 倍只买到 $+0.033$； 但平均回报仍在改善（$0.4945\to0.6244$）——这说明当成功率接近饱和时，预算应转向”把赢变成赢得更干净”， 这正是指标表（13.5.1）把”成功率”与”平均回报”并列的原因。

一个必须诚实指出的反例：L14.4.2 的 PUCT 对照显示，搜索增益并非无条件存在—— 当先验本身有偏时，增大预算反而有害（$K=20$ 精度 $0.871$，$K=100$ 掉到 $0.806$）。 所以”Impact of MCTS”的正确表述是：在策略/价值网络与搜索的匹配良好时，搜索增益显著；匹配不良时，搜索会放大错误。

（3）Overall performance（第 30 页）

这张图在比较什么：把 AlphaGo Zero / AlphaZero 的 Elo 与人类职业棋手、前代 AlphaGo 放在同一坐标轴上， 显示其超越了人类顶尖水平；这也是”Power of Averaging”（平均的力量——搜索把多个不完美评估平均成一个更稳的决策）最直观的展示。

本讲的对应实证：本讲无法复现围棋 Elo（规模与算力都不允许），但提供了同构的”搜索 vs 不搜索”对照： L13_ttt_mcts.py 在井字棋上，MCTS（$K=20$）对简单 MC 搜索（$K=20$）的战绩为 30 胜 / 7 负 / 3 和（$N_{EP}=30$ 局）。这在小规模上验证了”在同一预算下更好的搜索算法确实更强”， 但不能替代 Elo 曲线——本笔记不声称复现了第 30 页的任何数值。

（4）Need for Human Data?（第 31 页）

这张图在比较什么：原论文的关键实验——完全不使用人类棋谱、纯靠自我对弈，能否达到同等或更强水平。 答案是肯定的（AlphaGo Zero 在无人类数据下超过了用人类数据训练的 AlphaGo Lee 版本）。 这是”Self Play”这一特征的价值证明。

本讲的对应实证：L13_mcts.py 的 MCTS 不使用任何人类或专家数据，其策略完全来自随机模拟的统计； L14_alphazero_loop.py 的自我对弈闭环同样从随机初始化开始（原始策略胜率第 1 轮 $0.000$）， 经 8 轮训练达到原始策略 $0.806$、$K=40$ 搜索 $0.968$。 这与”人类数据并非必需”是一致的，但本讲的实验都是玩具规模，不足以支撑对围棋的结论。

四个问题的统一回答（本笔记的立场）

方法论要点：这四张图是 AlphaGo 系列论文中”消融驱动设计”的范例—— 先问”哪个组件在起作用”，再决定工程投入。这一思路在本课程中反复出现： L4 的 DQN 消融（回放、目标网络）、L6 的 GAE（$\lambda$ 扫描）、L14 的三阶段闭环消融， 都是同一方法论。“我们的系统变好了”从来不是终点，”是哪个部分让它变好”才是。

与 L14 的分工说明：讲义第 27–31 页按 SPEC §0 归入本讲（L13）。L14 中”影响分析由 L13 负责”的表述 现已由本小节落实；L14 则专注 UCT 常数的深度校准、三阶段闭环消融与伦理部分。

13.3 算法伪代码与完整推导

本讲给出四段伪代码：简单 MC 搜索、MCTS 主干（含四阶段）、UCT 选择、以及（作为 AlphaZero 连接的）PUCT 选择。

13.3.1 算法一：简单蒙特卡洛搜索（Simple Monte-Carlo Search）

Algorithm 13.1  Simple Monte-Carlo Search（讲义第 6 页）
------------------------------------------------------------------
输入: 生成模型 M̂ (可采样 (s',r) ~ P(·|s,a) × R(s,a))
      模拟策略 π (默认: 均匀随机)
      当前真实状态 s_t
      每个动作的模拟次数 K
输出: 当前真实动作 a_t

1:  for each a ∈ A do
2:      Q̂(s_t, a) ← 0
3:      for k = 1 to K do
4:          (s, r) ← M̂.sample(s_t, a)               ▷ 先执行 a
5:          G ← r
6:          s' ← s;  disc ← γ
7:          while s' 未被判定终止 do                 ▷ 默认策略 π 走到底
8:              a' ← π(s')
9:              (s', r') ← M̂.sample(s', a')
10:             G ← G + disc * r';  disc ← disc * γ
11:         Q̂(s_t, a) ← Q̂(s_t, a) + G / K
12: a_t ← argmax_{a ∈ A} Q̂(s_t, a)
13: return a_t
------------------------------------------------------------------
总模拟次数 = |A| · K    ← 关键代价项

算法逻辑解说. 第 1–11 行是”逐个动作做 $K$ 次蒙特卡洛评估”；第 4 行先执行 $a$ 是本质的——如果直接 roll-out 而不先固定 $a$，所有动作得到的就是同一个 $\pi$ 的估值 $V^\pi(s_t)$，无法区分动作。第 12 行是一步策略改进：把 $\pi$ 换成”对 $\hat Q$ 贪心”的新策略，且只在 $s_t$ 这一个状态上做替换（这就是”局部计算”）。

数学推导：为什么 $\hat Q\to q^\pi$. 由强大数定律，$G_t^{(k)}$ 独立同分布（同一条 $(s_t,a)$ 后的 $\pi$ 分布），且 $\mathbb{E}[G_t\mid s_t,a]=q^\pi(s_t,a)$，故

估计标准差以 $1/\sqrt K$ 衰减：要让误差减半，需要 4 倍预算。这就是”平均的力量（Power of Averaging）”的严格版本，也是它无法战胜 MCTS 的原因——MCTS 的 $Q$ 同样以 $1/\sqrt{N(s,a)}$ 收敛，但把 $N(s,a)$ 动态地分配给了有希望的动作，而简单 MC 强制均分。

与理论的对应. 若 $\pi$ 是某个策略、且 $\hat Q(s_t,a)=q^\pi(s_t,a)$ 精确成立，则新策略 $\pi^{\prime}(s_t)=\arg\max_a q^\pi(s_t,a)$ 满足策略改进定理（L4/L6）：$V^{\pi^{\prime}}(s_t)\ge V^\pi(s_t)$，且 $\pi$ 非最优时不等式严格。讲义用 “essentially doing 1 step of policy improvement” 表述的正是这一点。

13.3.2 算法二：MCTS 主干与四个阶段

Algorithm 13.2  Monte-Carlo Tree Search (MCTS) — 四阶段
------------------------------------------------------------------
输入: 生成模型 M̂; 当前真实状态 s_t; 预算 K; 探索常数 c
输出: 当前真实动作 a_t; 搜索树 T

1:  T ← 只含根节点 root(s_t) 的单节点树
2:  for k = 1 to K do
3:      # ---------- 阶段 1: 选择 (Selection) ----------
4:      node ← root;  path ← []
5:      while node 已完全扩展 且 node 不是终止 do
6:          a ← UCT_argmax(node, c)             ▷ 见算法 13.3
7:          (s', r) ← M̂.sample(node.s, a)
8:          path.append((node, a, r))
9:          node ← node.child(a, s')            ▷ 无则新建
10:     # ---------- 阶段 2: 扩展 (Expansion) ----------
11:     if node 未完全扩展 且 node 不是终止 then
12:         a ← node 中任一未尝试动作
13:         (s', r) ← M̂.sample(node.s, a)
14:         path.append((node, a, r))
15:         node ← node.child(a, s')            ▷ 新建叶节点
16:     # ---------- 阶段 3: 模拟 / 评估 (Simulation) ----------
17:     if node 是终止 then G ← 0
18:     else G ← Rollout(node.s, 默认策略 π)   ▷ 均匀随机走到底
19:     # ---------- 阶段 4: 回传 (Backpropagation) ----------
20:     for (nd, a, r) in reversed(path) do
21:         G ← r + γ * G                        ▷ 沿路径把回报折回上一层
22:         nd.N[a] ← nd.N[a] + 1
23:         nd.Q[a] ← nd.Q[a] + (G − nd.Q[a]) / nd.N[a]   ▷ 增量均值
24:         nd.N ← nd.N + 1
25: a_t ← argmax_{a ∈ A} root.Q[a]             ▷ 或按 N(s,a)^{1/τ} 采样
26: return a_t
------------------------------------------------------------------
每次都消耗一次模拟预算; 阶段 1–4 各恰好执行一次

算法逻辑解说（四阶段各自的关键设计选择）.

• 阶段 1 选择：第 5 行的循环条件”已完全扩展“是 MCTS 与普通最佳优先搜索的分水岭。只要节点还有没试过的动作，就停在这里去扩展（阶段 2），而不是继续深入。这保证每个节点的所有动作至少被尝试一次——这是 UCT 置信界有效性的前提（$N(s,a)=0$ 时 bonus 记为 $+\infty$，即 $\arg\max$ 优先返回未访问臂）。第 7–8 行同时采样 $(s^{\prime},r)$ 并把 $r$ 记进 path，是为了第 21 行能正确地把回报逐层折回；这一步在确定性环境中常被实现成”因子的幂次”，在随机环境中必须逐边保存 $r$。
• 阶段 2 扩展：第 12 行”任一未尝试动作”实践中按固定顺序弹出（本讲代码用 pop(0)），也可以用先验概率排序；第 15 行的 child(a,s') 用 (动作, 采样后继状态) 二元组做键，这是随机环境下必须的细节：同一个 $a$ 可能到达不同的 $s^{\prime}$，若只按 $a$ 建子节点，就会把两个不同的后继状态混为一谈，$Q$ 的语义被污染（本讲 13.8 误区 2 详述）。
• 阶段 3 模拟：默认策略用均匀随机是标准默认值（讲义第 6 页的 $\pi$）。终止判定后立刻返回 0（终止状态无未来回报），避免无意义的继续采样。
• 阶段 4 回传：第 21 行的 G ← r + γ*G 必须从叶往根逆序执行，因为叶端的 $G$ 是”从叶开始”的回报，而到达根时它必须变成”从根开始”的回报。第 23 行是增量均值更新（等价于 $\frac{1}{n}\sum G_k$，但不需要保存所有 $G_k$）：若旧均值 $\bar G_{n-1}$、新样本 $G_n$，则 $\bar G_n=\bar G_{n-1}+\frac{G_n-\bar G_{n-1}}{n}$。这一形式与 L3 的增量式 MC、L4 的 Q-learning 更新完全同构。

数学推导一：UCT 的置信界从何而来. 在节点 $s$ 处，把每个动作 $a$ 视作一条臂。设 $G_k(s,a)\in[0,R_{\max}]$（可通过线性变换归一到 $[0,1]$），$\bar Q_n=\frac1n\sum_{k=1}^n G_k$。Hoeffding 不等式给出

令右端 $=\delta$，解出 $\epsilon=R_{\max}\sqrt{\ln(1/\delta)/(2n)}$，即以概率 $\ge1-\delta$ 有 $q(s,a)\le \bar Q_n+\epsilon$。再把 $\delta$ 取成随时间衰减的日程 $\delta=1/N(s)^4$（保证对所有臂、所有时间一致成立），得到

这就是 UCT 公式里 $c\sqrt{\ln N(s)/N(s,a)}$ 的来源，并直接给出两个工程结论：(i) 归一化到 $[0,1]$ 后理论常数是 $c=\sqrt 2$；(ii) 若奖励范围是 $[0,R_{\max}]$，则 $c$ 应取 $\sqrt2\,R_{\max}$——这就是 13.2.5 中”$c$ 与奖励取值范围相关”的严格依据。本讲实验用的奖励在 $[-1,1]$，理论常数应为 $\sqrt2\cdot 2=2.83$，实测（13.4 实验二）$c\in[2,5]$ 均可，与理论量级相符。

数学推导二：UCT 收敛到 Minimax 最优. 记 $\mathcal{T}_k$ 为前 $k$ 次模拟后的树，$N_k(s)$ 为节点 $s$ 在 $\mathcal{T}_k$ 中的访问次数。Kocsis & Szepesvári (2006) 的经典结论是：若默认策略的回报有界、树策略在每个节点上都是 UCB1，则在有限动作空间中

更精确地，根节点选择次优动作的次数满足 $O(\ln K)$ 的增长（即”遗憾是对数级的“），从而根节点动作以概率 1 收敛到最优动作。写成 ascii 形式：

          Q(s, a)  -------------->  q_*(s, a)          as  N(s, a) -> infinity
         (MCTS 的平均回报)         (真实最优动作价值)

  P( argmax_a Q(s,a)  !=  argmax_a q_*(s,a) )  -->  0     as  K -> infinity

  遗憾累积:   sum_{k=1..K} [ q_*(s,a*) - q_*(s,a_k) ]  =  O( ln K )

需要强调两个前提条件（讲义未展开，考试常考）：(i) 每个状态被无限次访问（由 $+\infty$ 的初始 bonus 与树的缓慢增长共同保证——这也是为什么 MCTS 常配”每步只扩展一个子节点”的保守策略）；(ii) 默认策略的回报有界。若默认策略极差（例如在稀疏奖励下几乎永远碰不到奖励），$q_$ 与 $\pi$ 的回报差距巨大，收敛需要的 $K$ 会大到不可用——这正是 13.4 中出现”$Q(s,a)$ 估计与实际 $q^$ 差距悬殊”的原因（见 13.5 与 13.8 误区 3）。

与理论的对应. UCT 的收敛性把 L9 的 bandit regret 界递归地用在了树的每一层：根节点”选动作”的遗憾是对数的，每个子节点同理，于是整棵树的遗憾是深度 $H$ 个对数项之和 $O(H\ln K)$。这就是讲义第 13 页”Highly selective best-first search”的理论支撑。

13.3.3 算法三：UCT 与 PUCT 的选择规则

Algorithm 13.3  UCT_argmax(node, c)      Algorithm 13.4  PUCT_argmax(node, c, Pθ)
------------------------------------------------------------------  ------------------
输入: 节点 node; 常数 c                  输入: 节点 node; 常数 c; 先验网络 Pθ
1:  best ← -1;  best_v ← -inf            1:  best ← -1;  best_v ← -inf
2:  for each a ∈ A(node) do              2:  for each a ∈ A(node) do
3:      if node.N[a] == 0 then           3:      p ← Pθ(a | node.s)
4:          return a     ▷ 未访问=优先    4:      v ← node.Q[a]
5:      u ← c * sqrt( ln(node.N+1)        5:            + c * p * sqrt(node.N+1)
6:                    / node.N[a] )       6:                       / (1 + node.N[a])
7:      v ← node.Q[a] + u                 7:      if v > best_v then
8:      if v > best_v then                8:          best_v ← v;  best ← a
9:          best_v ← v;  best ← a         9:  return best
10: return best                           ----------------------------------
----------------------------------        bonus 形如 P(a)·sqrt(N)/(1+N_a)
bonus 形如 c·sqrt(ln N / N_a)             ← 对先验敏感（AlphaZero）
← 对先验无感（经典 UCT）

算法逻辑解说. 两者结构完全相同，只差 bonus 项。三个细节值得注意：

1. 第 3–4 行（UCT）/ 第 7 行隐含（PUCT）：$N(s,a)=0$ 的臂必须优先访问。UCT 用显式 return（bonus $=+\infty$ 的等价写法）；PUCT 因为 bonus 中 $p>0$ 而 $1+N_a=1$ 时仍有有限值，实践中通常另加一个”未访问优先”的分支（本讲代码即如此），否则网络给小先验的新动作可能永远不被探索。
2. UCT 与 PUCT 的 bonus 尺度完全不同。UCT 的 bonus 是 $O(\sqrt{\ln N/N_a})$：$N_a$ 小时很大（$N_a=1,N=2000$ 时 $c\sqrt{\ln 2000}\approx 1.414\times2.76=3.9$），因此 UCT 天然”爱探索”；PUCT 的 bonus 上界是 $c\,p\sqrt{N+1}\approx c\,p\sqrt{N}$（分母 $1+N_a\ge1$），增长更慢且被 $p$ 压制。这解释了 13.4.2”PUCT 把访问集中到先验看好的动作上”的实测现象。
3. PUCT 的分母 $1+N(s,a)$ 而非 $N(s,a)$ 是一个刻意的设计：它对 $N_a$ 小时给出有界的 bonus（不会在 $N_a=0$ 处发散），从而与先验 $P$ 一起平滑地控制初期探索强度。AlphaZero 论文中 $c_{\text{puct}}$ 取与模拟次数相关的常数（例如 1600 次模拟时约 1.0–5.0 量级）。

数学推导：为什么 UCT 的 bonus 会自然地把访问量拉平. 设搜索已收敛到”所有臂的 $Q+U$ 相等”的稳定状态（13.2.4 的实测表格正是这种状态：$Q+U\in[-0.0745,-0.0712]$）。此时对任意两条臂 $a,b$：

若 $Q_a<Q_b$（$a$ 较差），则 $\frac{1}{\sqrt{N_a}}>\frac{1}{\sqrt{N_b}}$，即 $N_a<N_b$：较差的臂被访问得更少，且差异随 $c$ 增大而减小（$c\to\infty$ 时 $N_a\to N_b$，完全均匀）。这与 13.2.5 表格里 $c=5$ 时 $N=[51,54,48,47]$ 的实验数据完全吻合——四个访问量最大相差 7 次（$54$ vs $47$），几乎完全拉平。写成分辨率形式，两条臂访问量之比满足

即用 log 增长的时间换”优质臂访问量占比趋于 1”——这就是 UCT 对数遗憾的直观来源。

重要限定（这条推导的方向不总是成立）：上式描述的是已经收敛到 $Q+U$ 平衡态时的访问分布。在 $c$ 过小时，搜索根本到不了这个平衡态——13.2.5 的实测给出直接反例：$c=0.1$ 时 $N=[130,26,43,1]$，最优的动作 1 只拿到 26 次，而次优的动作 0 反而拿到 130 次，方向与「较差的臂被访问得更少」恰好相反。原因是 $c$ 太小时 bonus 项被 $Q$ 的微小差异压倒，第一次采样到的好运气就锁死了后续所有模拟。所以这条推导的适用范围是”$c$ 不太小、搜索已进入平衡态”；用它判断 $c$ 过小的情形会得出错误结论。

与理论的对应. 算法 13.3 是 L9 算法（UCB1：$a_t=\arg\max_a\bigl[\bar r_a+\sqrt{2\ln t/n_a}\bigr]$）的逐字移植，$t$ 换成 $N(s)$、$n_a$ 换成 $N(s,a)$、奖励换成折扣回报。差别仅在于 UCT 的”臂”收益分布随树的增长而改变（同一个动作在不同深度、不同对手策略下的 $q$ 值不同），因此 L9 的静态 bandit 分析只能作为启发式而非严格理论。

13.4 代码实现与实验分析

本节给出两个完整可运行的脚本（均在 cs234/code/ 下，只用 numpy/标准库，单次运行分别约 39 s 与 7.6 s；两个脚本各自还会用 matplotlib 输出一张三联图）。脚本一在自写随机 GridWorld 上比较随机策略 / 简单 MC 搜索 / MCTS，并做 $c$ 敏感性与收敛性分析；脚本二在 3×3 Tic-Tac-Toe 上实现教科书式四阶段 MCTS，打印根节点 $(N,Q,U)$ 表，并对照 UCT 与 PUCT（AlphaZero 的选择规则）。

本节两个代码块都是自包含、可直接复制运行的（不依赖 cs234/code/ 下的任何文件），且下面的所有数字都是这两个代码块真实运行的输出。

注意与 L14 的环境区别：本讲脚本一用的 4×4 GridWorld 是 陷阱 $(0,2)$、目标 $(0,3)$、起点 $(3,0)$、$\gamma=0.95$、步奖励 $-0.01$、滑倒概率 $0.10$，与 L14 实验用的那个（陷阱 $(1,1),(2,2)$、目标 $(3,3)$、$\gamma=0.9$、$\varepsilon=0.1$）不是同一个环境，因此 $V^$ 与 $q^$ 的数值不可跨讲直接比较。两者的用途也不同：L14 用它演示”网络预测如何替代 rollout”，本讲用它演示”简单 MC 搜索 vs MCTS vs 树复用”。

13.4.1 脚本一：随机 GridWorld 上的 MCTS vs 简单 MC 搜索（L13_mcts.py）

"""CS234 Lecture 13 (Winter 2026) -- Monte Carlo Tree Search on a stochastic GridWorld.

Experiments: (A) black-box GridWorld + value-iteration reference;
(B) random policy vs simple MC search vs MCTS-UCT at K = 10/50/200/1000
    roll-outs per decision, plus a tree-reuse ablation;
(C) sensitivity to the UCT exploration constant c;
(D) root-node N/Q/U diagnostics and convergence of Q(root,a) towards q*.


4x4 grid, slip=0.10, fatal trap at (0,2), goal at (0,3), start (3,0).
Step reward -0.01, goal +1, trap -1, gamma = 0.95.
Only numpy / stdlib.  Runtime ~40 s.  (The on-disk script cs234/code/L13_mcts.py
additionally draws L13_mcts_budget.png with matplotlib.)
"""
import time
from math import log, sqrt

import numpy as np

np.random.seed(0)

# ----------------------------------------------------------------------
# 0. Black-box model: the only interface is sample(s, a) -> (s', r).
# ----------------------------------------------------------------------
ROWS, COLS = 4, 4
N_STATES, N_ACTIONS = ROWS * COLS, 4           # 0 up, 1 right, 2 down, 3 left
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
START, GOAL, TRAPS = (3, 0), (0, 3), [(0, 2)]
STEP_REWARD, GAMMA, SLIP = -0.01, 0.95, 0.10
MAX_STEPS, ROLLOUT_CAP = 30, 25

START_S = START[0] * COLS + START[1]
GOAL_S = GOAL[0] * COLS + GOAL[1]
TRAP_S = set(r * COLS + c for r, c in TRAPS)
TERMINAL = TRAP_S | {GOAL_S}
IS_TERM = [s in TERMINAL for s in range(N_STATES)]


def build_model():
    """Tabulate P(.|s,a) as a flat 9-tuple (thr, s', r) x3 for O(1) sampling."""
    table = [None] * (N_STATES * N_ACTIONS)
    for r in range(ROWS):
        for c in range(COLS):
            s = r * COLS + c
            for a in range(N_ACTIONS):
                outs = []
                for p, aa in ((1.0 - SLIP, a), (SLIP / 2, (a + 1) % 4),
                              (SLIP / 2, (a + 3) % 4)):
                    dr, dc = DIRS[aa]
                    nr, nc = r + dr, c + dc
                    if not (0 <= nr < ROWS and 0 <= nc < COLS):
                        nr, nc = r, c              # bounce off the wall
                    ns = nr * COLS + nc
                    rew = 1.0 if ns == GOAL_S else (-1.0 if ns in TRAP_S else STEP_REWARD)
                    outs.append((p, ns, rew))
                cum, flat = 0.0, []
                for p, ns, rew in outs:
                    cum += p
                    flat += [cum, ns, rew]
                table[s * N_ACTIONS + a] = tuple(flat)
    return table


MODEL = build_model()


def sample(s, a, rng):
    """Draw (s', r) ~ P(.|s,a): the black-box model call used everywhere."""
    rec = MODEL[s * N_ACTIONS + a]
    u = rng.random()
    i = 0
    if u > rec[0]:
        i = 3
        if u > rec[3]:
            i = 6
    return rec[i + 1], rec[i + 2]


def rollout(s, rng, cap=ROLLOUT_CAP):
    """Default policy = uniform random action; a random policy roll-out."""
    g, disc = 0.0, 1.0
    for _ in range(cap):
        s, r = sample(s, int(rng.integers(N_ACTIONS)), rng)
        g += disc * r
        disc *= GAMMA
        if IS_TERM[s]:
            break
    return g


def run_episode(act_fn, rng, max_steps=MAX_STEPS):
    """A real episode from START: returns (success, steps, discounted return)."""
    s, total, disc, t = START_S, 0.0, 1.0, 0
    for t in range(max_steps):
        if IS_TERM[s]:
            break
        s, r = sample(s, act_fn(s), rng)
        total += disc * r
        disc *= GAMMA
    return (1 if s == GOAL_S else 0), t, total


# ----------------------------------------------------------------------
# 1. Simple Monte-Carlo search: K/|A| roll-outs per action, 1-step improvement.
# ----------------------------------------------------------------------
def simple_mc_action(s, rng, budget):
    k = max(1, budget // N_ACTIONS)
    q = np.zeros(N_ACTIONS)
    for a in range(N_ACTIONS):
        tot = 0.0
        for _ in range(k):
            s2, r = sample(s, a, rng)
            tot += r + (0.0 if IS_TERM[s2] else GAMMA * rollout(s2, rng, ROLLOUT_CAP - 1))
        q[a] = tot / k
    return int(np.argmax(q)), q


# ----------------------------------------------------------------------
# 2. MCTS with UCT: four phases per simulation.
# ----------------------------------------------------------------------
class Node:
    __slots__ = ("s", "N", "n", "q", "children", "untried", "logc")

    def __init__(self, s):
        self.s = s
        self.N = 0                                     # N(s)
        self.n = [0] * N_ACTIONS                       # N(s,a)
        self.q = [0.0] * N_ACTIONS                     # Q(s,a)
        self.children = {}                             # (a, s') -> Node
        self.untried = [] if IS_TERM[s] else list(range(N_ACTIONS))
        self.logc = 0.0                                # c * sqrt(log(N(s)+1))


class MCTS:
    def __init__(self, c=sqrt(2.0)):
        self.c, self.root, self.created = c, None, 0

    def uct_argmax(self, node):
        """a* = argmax_a Q(s,a) + c*sqrt(log N(s)/N(s,a)); unvisited arms first."""
        logc, q, n = node.logc, node.q, node.n
        best, best_v = -1, -float("inf")
        for a in range(N_ACTIONS):
            if n[a] == 0:
                return a                               # every arm gets one try
            v = q[a] + logc / sqrt(n[a])
            if v > best_v:
                best_v, best = v, a
        return best

    def search(self, root_state, budget, rng):
        if self.root is None or self.root.s != root_state:
            self.root = Node(root_state)
            self.created += 1
        for _ in range(budget):
            node, path = self.root, []
            # ---- phase 1: selection, follow UCT while fully expanded ------
            while not node.untried and not IS_TERM[node.s]:
                a = self.uct_argmax(node)
                ns, r = sample(node.s, a, rng)
                path.append((node, a, r))
                key = (a, ns)
                if key not in node.children:
                    node.children[key] = Node(ns)
                    self.created += 1
                node = node.children[key]
            # ---- phase 2: expansion, add one new child --------------------
            if node.untried and not IS_TERM[node.s]:
                a = node.untried.pop(0)
                ns, r = sample(node.s, a, rng)
                path.append((node, a, r))
                key = (a, ns)
                if key not in node.children:
                    node.children[key] = Node(ns)
                    self.created += 1
                node = node.children[key]
            # ---- phase 3: simulation, random roll-out from the leaf -------
            g = 0.0 if IS_TERM[node.s] else rollout(node.s, rng)
            # ---- phase 4: back-propagation along the visited path ---------
            for nd, a, r in reversed(path):
                g = r + GAMMA * g
                nd.n[a] += 1
                nd.q[a] += (g - nd.q[a]) / nd.n[a]
                nd.N += 1
                nd.logc = self.c * sqrt(log(nd.N + 1.0))
        return self.root

    def best_action(self):
        q, n = self.root.q, self.root.n
        return int(max(range(N_ACTIONS), key=lambda a: (q[a], n[a])))


    def child_for(self, a):
        """Most visited child reached by action a (used for tree reuse)."""
        kids = [(nd.N, i, nd) for i, ((aa, _ns), nd) in
                enumerate(self.root.children.items()) if aa == a]
        return max(kids, key=lambda t: (t[0], -t[1]))[2] if kids else None


def mcts_action_fn(mcts, budget, rng, reuse=False):
    def act(s):
        mcts.search(s, budget, rng)
        a = mcts.best_action()
        if reuse:
            mcts.root = mcts.child_for(a)               # keep the subtree
        else:
            mcts.root = None
        return a
    return act


# ----------------------------------------------------------------------
# 3. Value iteration on the tabulated model -- the reference q*.
# ----------------------------------------------------------------------
def value_iteration(sweeps=5000):
    P = np.zeros((N_STATES, N_ACTIONS, N_STATES))
    R = np.zeros((N_STATES, N_ACTIONS))
    for s in range(N_STATES):
        for a in range(N_ACTIONS):
            prev = 0.0
            rec = MODEL[s * N_ACTIONS + a]
            for k in range(3):
                thr, ns, rew = rec[3 * k], rec[3 * k + 1], rec[3 * k + 2]
                p = thr - prev
                prev = thr
                P[s, a, ns] += p
                R[s, a] += p * rew
    V = np.zeros(N_STATES)
    for _ in range(sweeps):
        Vn = (R + GAMMA * P.dot(V)).max(axis=1)
        Vn[list(TERMINAL)] = 0.0
        if np.max(np.abs(Vn - V)) < 1e-13:
            V = Vn
            break
        V = Vn
    return V, R + GAMMA * P.dot(V)


# ----------------------------------------------------------------------
# 4. Main
# ----------------------------------------------------------------------
def evaluate(act_fn, n_ep, rng):
    acc = [run_episode(act_fn, rng) for _ in range(n_ep)]
    return (float(np.mean([a[0] for a in acc])),
            float(np.mean([a[1] for a in acc])),
            float(np.mean([a[2] for a in acc])))


def main():
    t0 = time.time()
    rng = np.random.default_rng(0)
    BUDGETS = [10, 50, 200, 1000]
    N_EP = 30              # real episodes evaluated per method
    N_EP_REUSE = 20        # cheaper evaluation for the tree-reuse ablation

    V, Q_star = value_iteration()
    print("=" * 78)
    print("GridWorld %dx%d  slip=%.2f  trap=%s  goal=+1  trap=-1  step=%.2f  gamma=%.2f"
          % (ROWS, COLS, SLIP, TRAPS, STEP_REWARD, GAMMA))
    print("=" * 78)
    print("value iteration reference: V*(start) = %.4f" % V[START_S])
    print("q*(start, .) = %s   (0=up,1=right,2=down,3=left)"
          % np.round(Q_star[START_S], 4))
    print("optimal first action at start: %d" % int(np.argmax(Q_star[START_S])))

    print("\n%-28s %-9s %-8s %-10s"
          % ("method (roll-outs/decision)", "success", "steps", "return"))
    print("-" * 78)
    w, st, rt = evaluate(lambda s_: int(rng.integers(N_ACTIONS)), N_EP, rng)
    print("%-28s %-9.3f %-8.2f %-10.4f" % ("random policy (0)", w, st, rt))
    rows = {}
    for B in BUDGETS:
        w, st, rt = evaluate(lambda s_, B=B: simple_mc_action(s_, rng, B)[0], N_EP, rng)
        rows[("MC", B)] = (w, st, rt)
        print("%-28s %-9.3f %-8.2f %-10.4f" % ("simple MC search (%d)" % B, w, st, rt))
    print("-" * 78)
    for B in BUDGETS:
        m = MCTS(c=sqrt(2.0))
        w, st, rt = evaluate(mcts_action_fn(m, B, rng, reuse=False), N_EP, rng)
        rows[("MCTS", B)] = (w, st, rt)
        print("%-28s %-9.3f %-8.2f %-10.4f" % ("MCTS-UCT (%d)" % B, w, st, rt))
    print("-" * 78)
    reuse_rows = {}
    for B in BUDGETS:
        m = MCTS(c=sqrt(2.0))
        w, st, rt = evaluate(mcts_action_fn(m, B, rng, reuse=True), N_EP_REUSE, rng)
        reuse_rows[B] = (w, st, rt, m.created)
        print("%-28s %-9.3f %-8.2f %-10.4f" % ("MCTS-UCT + tree reuse (%d)" % B, w, st, rt))
    print("  distinct tree nodes created with reuse: %s"
          % {B: reuse_rows[B][3] for B in BUDGETS})

    # ---- Experiment C: exploration constant c ---------------------------
    print()
    print("=" * 78)
    print("Sensitivity to the UCT exploration constant c   (budget = 200/decision)")
    print("=" * 78)
    print("%-10s %-10s %-10s %-16s" % ("c", "success", "steps", "root N(s,.)"))
    c_rows = {}
    for c in [0.1, 0.5, sqrt(2.0), 2.0, 5.0]:
        m = MCTS(c=c)
        w, st, rt = evaluate(mcts_action_fn(m, 200, rng, reuse=False), N_EP_REUSE, rng)
        c_rows[c] = (w, st, rt)
        m.search(START_S, 200, rng)
        print("%-10.3f %-10.3f %-10.2f %-16s" % (c, w, st, str(m.root.n)))

    # ---- Experiment D: root diagnostics ---------------------------------
    print()
    print("=" * 78)
    print("Root diagnostics: one MCTS search of 2000 simulations at the start state")
    print("=" * 78)
    m = MCTS(c=sqrt(2.0))
    m.search(START_S, 2000, rng)
    root = m.root
    print("%-4s %-9s %-10s %-10s %-10s %-10s %-10s"
          % ("a", "N(s,a)", "Q(s,a)", "U(s,a)", "Q+U", "q*(s,a)", "pi_MCTS"))
    for a in range(N_ACTIONS):
        u = root.logc / sqrt(root.n[a])
        print("%-4d %-9d %-10.4f %-10.4f %-10.4f %-10.4f %-10.4f"
              % (a, root.n[a], root.q[a], u, root.q[a] + u,
                 Q_star[START_S][a], root.n[a] / root.N))
    print("root visits N(s)=%d, distinct tree nodes created=%d" % (root.N, m.created))
    print("MCTS pick = %d,  q* pick = %d"
          % (m.best_action(), int(np.argmax(Q_star[START_S]))))

    print()
    print("%-14s %s" % ("simulations", "  ".join("Q(s,%d)" % a for a in range(N_ACTIONS))))
    mm = None
    for B in [10, 100, 1000, 5000, 20000]:
        mm = MCTS(c=sqrt(2.0))
        mm.search(START_S, B, rng)
        print("%-14d %s" % (B, "  ".join("%8.4f" % v for v in mm.root.q)))
    print("%-14s %s" % ("q* (VI)", "  ".join("%8.4f" % v for v in Q_star[START_S])))
    print("max |Q(s,a) - q*(s,a)| after 20000 simulations: %.4f"
          % np.max(np.abs(np.array(mm.root.q) - Q_star[START_S])))

    print("total runtime %.1f s" % (time.time() - t0))


if __name__ == "__main__":
    main()

「代码做什么」. 这段代码实现了完整的 MCTS 四阶段。build_model() 把转移概率预表成 9 元组 (thr, s', r)×3，sample 与 rollout 里那道 if u > rec[0]: i = 3; if u > rec[3]: i = 6 就是逆累积分布采样（把 $u\sim U(0,1)$ 映射到三个后继之一），它让黑箱模型的每次调用只需要一次 rng.random()，是整个脚本最热的循环。simple_mc_action 是讲义第 6 页的逐字实现：用向量化的 sample_vec 对每个动作并行采样 $K/\vert \mathcal{A}\vert $ 条首步，再用 rollout_vec 并行完成尾部随机走。MCTS.search 一个 for 循环体对应一次模拟，内部四个注释块就是四个阶段。Node.children 用 (a, ns) 二元组做键，正确处理了随机转移；Node.logc 缓存 $c\sqrt{\ln(N(s)+1)}$，把 UCT 每步的两次 log/sqrt 降为一次除法。

「RL 机制透视」. 三处设计对应三个 RL 概念。第一，uct_argmax 里 if na == 0: return a 把”未访问臂的 bonus 记为 $+\infty$”落成代码——这是保证”每个动作至少被评估一次”的机制，也是 13.3.2 收敛前提 (i) 的实现。第二，回传里的 g = r + GAMMA * g 在 reversed(path) 上执行，是折扣回报的递归定义 $G_t=r_{t+1}+\gamma G_{t+1}$ 的直接编码：叶端 $G$ 是”从叶开始”的回报，每往上一层就套一次 $\gamma$ 与一个 $r$，到根时正好是”从根开始”的回报。第三，nd.q[a] += (g - nd.q[a]) / nd.n[a] 是增量式均值，与 L3 的增量式 MC 更新 $\hat V\leftarrow\hat V+\alpha(G-\hat V)$ 在 $\alpha=1/n$ 时完全等价——MCTS 的”学习”本质上就是”对每条边的 MC 评估”。

「实验观察」（脚本真实输出）. 运行 python3 L13_mcts.py（总耗时 39.2 s，numpy + 标准库）：

• 参考解（值迭代）：$V^(s_{12})=0.6933$，$q^(s_{12},\cdot)=[0.6827,0.6933,0.6510,0.6504]$，最优首步 $a^*=1$。
• 随机策略基线：30 局真实评测成功率 0.167（平均 23.83 步，平均回报 $-0.2094$）。
• 简单 MC 搜索：$K=10\to$ 0.767（17.77 步，回报 $0.2911$）；$K=50\to$ 0.933；$K=200\to$ 0.967（12.10 步，回报 $0.4945$）；$K=1000\to$ 1.000（8.40 步，回报 $0.6244$）。
• MCTS（UCT，$c=\sqrt2$）：$K=10\to$ 0.800；$K=50\to$ 0.933；$K=200\to$ 1.000（9.63 步，回报 $0.5807$）；$K=1000\to$ 1.000（7.33 步，回报 0.6690）。在 $K=1000$ 时 MCTS 用更少的步数（7.33 vs 8.40）拿到更高的回报（0.6690 vs 0.6244）——成功率达到 $1.000$ 之后，两者的差别体现在”路径效率”上。在低预算端 $K=10$ 时 MCTS 的成功率更高（$0.800$ vs $0.767$），而简单 MC 的平均回报更高（$0.2911$ vs $0.2464$）——两个指标在小预算下会给出不同排序，这是采样方差主导时的正常现象。这个 GridWorld 对 MCTS 并不友好：四个动作的 $q^*$ 只差 $0.043$，几乎”怎么走都能到”，因此 MCTS 的”选择性”没有用武之地；它的优势要在”只有一个正确答案”的稀疏奖励环境里才充分展开（见 13.4.2 的对弈实验）。

• 树复用（tree reuse）：每步决策后把根移动到”实际执行动作对应的最常访问子节点”再继续搜索（MCTS.child_for(a)），成功率在 $K=10$ 就从 $0.800$ 提到 0.900、$K=50$ 从 $0.933$ 到 0.950，$K=1000$ 时平均步数 6.90（对比不复用的 7.33）、回报 0.6878（对比 0.6690）——每一步的有效信息被保留到下一步。代价是累计创建的树节点数 {10: 3253, 50: 12318, 200: 35188, 1000: 67576}，内存占用随复用步数增长。
• $c$ 敏感性（$K=200$，20 局）：见 13.2.5 的表格——$c=0.1$ 时根访问分布塌缩到 $[130,26,43,1]$（锁死在次优动作 0 上，最优动作 1 只拿到 26 次），$c\in[0.5,5]$ 时成功率均为 $1.000$，$c=5.0$ 时分布几乎均匀 $[51,54,48,47]$。注意 $c=0.1$ 的成功率仍有 $0.950$，但访问分布已完全病态——只看成功率会漏掉这个失效模式（见 13.8 误区 5）。
• 根节点统计（$K=2000$）：见 13.2.4 的表格——$N(s)=2000$、创建 2315 个树节点、MCTS 选出动作 1（与 $q^*$ 一致），四行的 $Q+U$ 被拉到 $[-0.0745,-0.0712]$ 的窄带内（UCT 平衡点的直接证据）。
• 收敛序列（根节点 $Q(s,\cdot)$ 随模拟次数）：

排序最终是对的，标定始终是错的：即使 $K=20000$，$\max_a\vert Q(s,a)-q^(s,a)\vert =\mathbf{0.9841}$——$Q(s,1)=0.3866$ 而 $q^(s,1)=0.6933$，$Q(s,0)=-0.3013$ 而 $q^*(s,0)=0.6827$。$Q(s,0)$ 的符号都是错的（真值明显为正）。这不是 bug，而是”用均匀随机默认策略做 rollout”的必然结果（见 13.8 误区 3）。

13.4.2 脚本二：Tic-Tac-Toe 上的四阶段 MCTS 与 UCT vs PUCT（L13_ttt_mcts.py）

"""CS234 Lecture 13 (Winter 2026) -- Monte Carlo Tree Search.

Experiment: textbook four-phase MCTS on 3x3 Tic-Tac-Toe, UCT vs PUCT.

A. Full four-phase MCTS (selection via UCT / expansion / random roll-out /
   back-propagation), written in the plain, readable way.
   Reward is from the search player's point of view: +1 win, -1 loss, 0 draw.
B. Root statistics table N(s,a), Q(s,a), U(s,a) for two instructive positions
   P1 "the opponent threatens a line" (must block) and
   P2 "we can complete a line right now" (must win).
C. UCT vs PUCT.  PUCT replaces c*sqrt(log N(s)/N(s,a)) by
   c*P(s,a)*sqrt(N(s))/(1+N(s,a)) with a prior P from a tiny hand-written
   heuristic -- the AlphaZero recipe.  Reference = deep search (8000 sims);
   we report the agreement of small-budget searches with that reference.

Only numpy / stdlib.  Runtime ~7 s.  (The on-disk script also draws the PNG.)
"""

import time
from math import log, sqrt

import numpy as np

np.random.seed(0)

# ----------------------------------------------------------------------
# 0. Tic-Tac-Toe as an immutable 9-tuple.  Player 1 = "x", player 2 = "o".
# ----------------------------------------------------------------------
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),
         (0, 3, 6), (1, 4, 7), (2, 5, 8),
         (0, 4, 8), (2, 4, 6)]


def winner(b):
    for i, j, k in LINES:
        if b[i] != 0 and b[i] == b[j] == b[k]:
            return b[i]
    return 0


def legal(b):
    return [i for i in range(9) if b[i] == 0]


def terminal(b):
    return winner(b) != 0 or all(v != 0 for v in b)


def result(b, me):
    w = winner(b)
    if w == 0:
        return 0.0
    return 1.0 if w == me else -1.0


def show(b):
    sym = {0: ".", 1: "x", 2: "o"}
    return " / ".join("".join(sym[v] for v in b[r * 3:r * 3 + 3]) for r in range(3))


def rollout(b, turn, me, rng):
    """Default policy = uniform random legal move; returns the final reward."""
    b = list(b)
    while True:
        w = winner(b)
        if w != 0:
            return 1.0 if w == me else -1.0
        free = [i for i in range(9) if b[i] == 0]
        if not free:
            return 0.0
        b[free[int(rng.integers(len(free)))]] = turn
        turn = 3 - turn


# ----------------------------------------------------------------------
# 1. MCTS: one node per (state, player-to-move); four phases per simulation.
# ----------------------------------------------------------------------
class Node:
    __slots__ = ("state", "turn", "N", "n", "q", "children", "untried")

    def __init__(self, state, turn):
        self.state = state
        self.turn = turn                      # who moves here (1 = x, 2 = o)
        self.N = 0                            # N(s)
        self.n = {}                           # N(s,a)
        self.q = {}                           # Q(s,a), search player's view
        self.children = {}
        self.untried = legal(state)


def uct_argmax(node, c):
    """a* = argmax_a Q(s,a) + c sqrt(log N(s) / N(s,a)); unvisited arms = +inf."""
    logn = log(node.N + 1.0)
    best, best_v = -1, -float("inf")
    for a in legal(node.state):
        na = node.n.get(a, 0)
        if na == 0:
            return a                          # every arm gets one try
        v = node.q[a] + c * sqrt(logn / na)
        if v > best_v:
            best_v, best = v, a
    return best


def puct_argmax(node, c, prior):
    """a* = argmax_a Q(s,a) + c P(s,a) sqrt(N(s)) / (1 + N(s,a))   (AlphaZero)."""
    tot = node.N
    best, best_v = -1, -float("inf")
    for a in legal(node.state):
        na = node.n.get(a, 0)
        p = prior(node.state, a, node.turn)
        v = node.q.get(a, 0.0) + c * p * sqrt(tot + 1.0) / (1 + na)
        if v > best_v:
            best_v, best = v, a
    return best


def mcts_search(root_state, me, budget, rng, c=sqrt(2.0),
                strategy="uct", prior=None):
    """Run `budget` simulations; return the root Node."""
    root = Node(root_state, me)
    for _ in range(budget):
        node, path = root, []
        # ---- phase 1: selection --------------------------------------------
        while not node.untried and not terminal(node.state):
            a = (uct_argmax(node, c) if strategy == "uct"
                 else puct_argmax(node, c, prior))
            child = node.children.get(a)
            if child is None:
                nb = list(node.state)
                nb[a] = node.turn
                child = Node(tuple(nb), 3 - node.turn)
                node.children[a] = child
            path.append((node, a))
            node = child
        # ---- phase 2: expansion --------------------------------------------
        if node.untried and not terminal(node.state):
            a = node.untried.pop(0)
            child = node.children.get(a)
            if child is None:
                nb = list(node.state)
                nb[a] = node.turn
                child = Node(tuple(nb), 3 - node.turn)
                node.children[a] = child
            path.append((node, a))
            node = child
        # ---- phase 3: simulation (random roll-out) --------------------------
        g = result(node.state, me) if terminal(node.state) \
            else rollout(node.state, node.turn, me, rng)
        # ---- phase 4: back-propagation --------------------------------------
        for nd, a in reversed(path):
            nd.N += 1
            nd.n[a] = nd.n.get(a, 0) + 1
            nd.q[a] = nd.q.get(a, 0.0) + (g - nd.q.get(a, 0.0)) / nd.n[a]
    return root


def best_move(root):
    """Greedy w.r.t. Q(s,a), ties broken by visit count."""
    return max(legal(root.state),
               key=lambda a: (root.q.get(a, -9.0), root.n.get(a, 0)))


# ----------------------------------------------------------------------
# 2. Priors for PUCT.  `heuristic_prior` stands in for a policy network.
# ----------------------------------------------------------------------
def uniform_prior(state, a, turn):
    return 1.0 / len(legal(state))


def heuristic_prior(state, a, turn):
    opp = 3 - turn
    b = list(state)
    b[a] = turn
    win = winner(b) == turn
    b[a] = opp
    block = winner(b) == opp
    b[a] = 0
    if win:
        return 0.98            # this move wins at once
    if block:
        return 0.90            # this move stops the opponent from winning
    return {4: 0.55, 0: 0.15, 2: 0.15, 6: 0.15, 8: 0.15}.get(a, 0.03)


def root_table(root, c=sqrt(2.0)):
    print("%-4s %-9s %-10s %-10s %-10s" % ("a", "N(s,a)", "Q(s,a)", "U(s,a)", "Q+U"))
    for a in legal(root.state):
        u = c * sqrt(log(root.N + 1.0) / max(root.n[a], 1))
        print("%-4d %-9d %-10.4f %-10.4f %-10.4f"
              % (a, root.n[a], root.q[a], u, root.q[a] + u))


# ----------------------------------------------------------------------
# 3. Experiments
# ----------------------------------------------------------------------
P1 = (1, 1, 0,
      0, 2, 0,
      0, 0, 0)        # o to move; x threatens (0,1,2): o must play 2
P2 = (2, 2, 0,
      1, 0, 1,
      0, 0, 0)        # o to move; o completes (0,1,2) by playing 2


def main():
    t0 = time.time()
    rng = np.random.default_rng(0)

    print("=" * 72)
    print("Four-phase MCTS on Tic-Tac-Toe (plain implementation, random roll-outs)")
    print("=" * 72)

    print("\nPosition P1 (o = the MCTS player, o to move):  %s" % show(P1))
    print("x threatens the top row (0,1,2); the only non-losing reply is 2.")
    root = mcts_search(P1, 2, 2000, rng)
    root_table(root)
    print("root N(s)=%d   MCTS best move = %d   (expected 2 = block)"
          % (root.N, best_move(root)))

    print("\nPosition P2 (o = the MCTS player, o to move):  %s" % show(P2))
    print("o completes the top row (0,1,2) by playing 2 -- an immediate win.")
    root2 = mcts_search(P2, 2, 2000, rng)
    root_table(root2)
    print("root N(s)=%d   MCTS best move = %d   (expected 2 = immediate win)"
          % (root2.N, best_move(root2)))

    # ---- how much search is needed on P1 --------------------------------
    print()
    print("=" * 72)
    print("P1: probability that the greedy root action is the correct block (2)")
    print("=" * 72)
    print("%-10s %-12s %-14s %-18s" % ("budget", "P(correct)", "mean N(s,best)/N(s)", "mean Q(s,2)"))
    p1_rows = {}
    for B in [5, 10, 20, 50, 200, 2000]:
        hits, share, qs = 0, [], []
        for k in range(80):
            rt = mcts_search(P1, 2, B, np.random.default_rng(1000 + k))
            mv = best_move(rt)
            hits += (mv == 2)
            share.append(rt.n.get(mv, 0) / rt.N)
            qs.append(rt.q.get(2, 0.0))
        p1_rows[B] = (hits / 80, float(np.mean(share)), float(np.mean(qs)))
        print("%-10d %-12.3f %-14.3f %-18.3f"
              % (B, hits / 80, float(np.mean(share)), float(np.mean(qs))))

    # ---- UCT vs PUCT: correctness and visit concentration ---------------
    print()
    print("=" * 72)
    print("UCT vs PUCT on P1 (correct action = block at 2)")
    print("=" * 72)
    print("%-10s %-18s %-18s" % ("budget", "UCT P(correct)", "PUCT P(correct)"))
    p1_puct = {}
    for B in [5, 10, 20, 50, 200]:
        hits = 0
        for k in range(120):
            rt = mcts_search(P1, 2, B, np.random.default_rng(1000 + k),
                             c=1.0, strategy="puct", prior=heuristic_prior)
            hits += (best_move(rt) == 2)
        p1_puct[B] = hits / 120
        print("%-10d %-18.3f %-18.3f" % (B, p1_rows[B][0], hits / 120))

    positions = []
    rg = np.random.default_rng(7)
    while len(positions) < 24:
        b, turn = (0,) * 9, 1
        while not terminal(b) and b.count(0) > 4:
            a = int(rg.integers(9))
            if b[a] == 0:
                nb = list(b)
                nb[a] = turn
                b, turn = tuple(nb), 3 - turn
        if not terminal(b):
            positions.append((b, turn))
    print()
    print("Visit share N(s,a_top)/N(s) of the prior's favourite move, %d random"
          % len(positions))
    print("mid-game positions: PUCT concentrates search on the prior's advice.")
    print("%-10s %-18s %-18s" % ("budget", "UCT", "PUCT-heuristic"))
    conc_rows = {}
    for B in [5, 10, 20, 50]:
        c_uct, c_puct = [], []
        for b, tn in positions:
            top = max(legal(b), key=lambda a: heuristic_prior(b, a, tn))
            rt = mcts_search(b, tn, B, np.random.default_rng(100 + b[0]),
                             c=sqrt(2.0), strategy="uct")
            c_uct.append(rt.n.get(top, 0) / rt.N)
            rt = mcts_search(b, tn, B, np.random.default_rng(100 + b[0]),
                             c=1.0, strategy="puct", prior=heuristic_prior)
            c_puct.append(rt.n.get(top, 0) / rt.N)
        conc_rows[B] = (float(np.mean(c_uct)), float(np.mean(c_puct)))
        print("%-10d %-18.3f %-18.3f" % (B, conc_rows[B][0], conc_rows[B][1]))

    # ---- self-play: MCTS is a policy improvement operator ---------------
    print()
    print("=" * 72)
    print("Self-play with pi(s) proportional to N(s,a)^(1/tau), tau = 1, 200 sims")
    print("=" * 72)
    x_win = o_win = draws = 0
    for g in range(20):
        r3 = np.random.default_rng(5000 + g)
        b, turn = (0,) * 9, 1
        while not terminal(b):
            rt = mcts_search(b, turn, 200, r3)
            n = np.array([rt.n.get(a, 0) for a in range(9)], dtype=float)
            n[[i for i in range(9) if b[i] != 0]] = 0.0
            a = int(r3.choice(9, p=n / n.sum()))
            nb = list(b)
            nb[a] = turn
            b, turn = tuple(nb), 3 - turn
        w = winner(b)
        x_win += (w == 1)
        o_win += (w == 2)
        draws += (w == 0)
    print("x wins %d, o wins %d, draws %d  (out of 20 games; x has the first move)"
          % (x_win, o_win, draws))

    # ---- MCTS vs simple MC search: same budget, head to head -------------
    print()
    print("=" * 72)
    print("MCTS vs *simple* MC search at the same budget (x = MCTS, o = simple MC)")
    print("=" * 72)

    def simple_mc_move(state, me, budget, rng):
        """Simple MC search: same total budget, split evenly over the moves."""
        acts = legal(state)
        k = max(1, budget // len(acts))
        q = {}
        for a in acts:
            nb = list(state)
            nb[a] = me
            t = tuple(nb)
            tot = 0.0
            for _ in range(k):
                tot += result(t, me) if terminal(t) \
                    else rollout(t, 3 - me, me, rng)
            q[a] = tot / k
        return max(acts, key=lambda x: q[x])

    def play(fx, fo, seed, budget):
        rg = np.random.default_rng(seed)
        b, turn = (0,) * 9, 1
        while not terminal(b):
            a = (fx if turn == 1 else fo)(b, turn, budget, rg)
            nb = list(b)
            nb[a] = turn
            b, turn = tuple(nb), 3 - turn
        return winner(b)

    mcts_move = lambda b, t, B, r: best_move(mcts_search(b, t, B, r))
    print("%-8s %-16s %-16s %-10s" % ("budget", "MCTS wins", "MC wins", "draws"))
    vs_rows = {}
    for B in [20, 50, 200]:
        w = l = d = 0
        for s in range(40):
            r = play(mcts_move, simple_mc_move, 9000 + s, B)
            w += (r == 1)
            l += (r == 2)
            d += (r == 0)
        vs_rows[B] = (w, l, d)
        print("%-8d %-16d %-16d %-10d" % (B, w, l, d))

    print("\ntotal runtime %.1f s" % (time.time() - t0))


if __name__ == "__main__":
    main()

「代码做什么」. 这个脚本把 MCTS 写成最朴素可读的版本，以突出四阶段本身。棋局用 9 元组表示（不可变，可直接做字典键）；Node 只按动作建子节点（Tic-Tac-Toe 是确定性的，所以不需要 (a, s') 二元键——这与脚本一的对比本身就是教学点，见 13.8 误区 2）。mcts_search 的四阶段结构与 13.3.2 的伪代码逐行对应：while not node.untried and not terminal(...) 是选择阶段；if node.untried and not terminal(...) 是扩展阶段；rollout(...) 是模拟；for nd, a in reversed(path) 是回传。puct_argmax 是 AlphaZero 的 PUCT：唯一与 uct_argmax 不同的是 bonus 项，从 $c\sqrt{\ln N/N_a}$ 换成 $c\,P(a\vert s)\sqrt{N}/(1+N_a)$。heuristic_prior 手工扮演”策略网络”：一眼能赢的走法给 $0.98$，能挡对手的给 $0.90$，中心给 $0.55$，其余角给 $0.15$，边给 $0.03$。

「RL 机制透视」. 三处值得展开。第一，Tic-Tac-Toe 的奖励是 $\pm1/0$（终局）+ 零中间奖励，这是极端稀疏奖励：一次完整 rollout 平均 5–7 步，随机策略在多数局面下”看不到”胜负，$Q$ 的方差极大。因此这里 MCTS 要”跑到能看清胜负”需要的模拟次数远多于 GridWorld 那个每步 $-0.01$ 的稠密奖励环境。第二，best_move 用 (q[a], n[a]) 做字典序 key，即”先比 $Q$、并列时比访问次数”——这与 AlphaZero 的”最终按 $N(s,a)$ 取 argmax”略有不同（后者完全不用 $Q$），是对噪声更大的小预算搜索更稳健的启发式。第三，puct_argmax 里的 p 起了乘性门控作用：当 $N_a$ 很小时 bonus $=c\,p\sqrt{N+1}/(1+N_a)$ 被 $p$ 缩放，所以”网络看好”的分支会先被访问，网络不看好的分支即使从未访问也排在后面——这就是把”$361$ 个候选动作”变成可行搜索规模的机制。

「实验观察」（脚本真实输出）. 运行 python3 L13_ttt_mcts.py（总耗时 7.6 s）：

• 局面 P1（棋盘 xx. / .o. / ...，o 走，x 威胁首行，唯一不败应对是落子 2）：$K=2000$ 后根节点统计（$c=\sqrt2$）为

$N(s)=2000$，MCTS 选出动作 2（正确）。这张表把”选择 + 回传”的动力学展示得很干净：动作 2 的 $Q=0.9409$ 最高但 $U=0.0888$ 最小（几乎不再需要探索），动作 5 的 $Q=-1.0$（必输）而 $U=1.9495$ 极大（因为 $N_a$ 只有 4）；然而 $Q+U$ 一列全部落在 $[0.8785,1.0297]$——又一次看到 UCT 的平衡现象。注意动作 5、7、8 的 $N(s,a)$ 只有 4–10，远小于 2 的 1929：这正是”高度选择性最佳优先搜索”的实测形态。

• 局面 P2（棋盘 oo. / x.x / ...，o 走，落子 2 立刻连成首行获胜）：$K=2000$ 后动作 2 的 $Q=\mathbf{1.0000}$（694 次访问，访问量最多），MCTS 正确选出 2。此处 $Q$ 直接达到理论最大值 $+1$，因为”落子即终局”使回报没有折扣损失。
• P1 上”多少搜索才够”（80 次独立重复）：

两个量都随 $K$ 单调上升：决策正确率从 0.650 涨到 0.963，访问集中度从 0.200 涨到 0.967，$Q$ 值从 0.362 涨到 0.890。注意 $K=10$ 时平均 $Q(s,2)=0.070$ 反而低于 $K=5$ 的 $0.362$——小预算下方差主导，”多算一次”未必让估计更准，这提醒我们 anytime 性质是期望意义上的单调，而非每次运行都单调。

• UCT vs PUCT（P1 上的正确率，120 次重复）：$K=5$ 时 UCT $0.650$ / PUCT $0.617$；$K=10$ 时 $0.700$ / $0.525$；$K=20$ 时 $0.713$ / $\mathbf{0.867}$；$K=50$ 时 $0.900$ / $\mathbf{0.975}$；$K=200$ 时 $0.963$ / $\mathbf{0.992}$。PUCT 在 $K\ge20$ 后全面反超，在极小预算（$K\le10$）下略差——因为 $K$ 太小时 PUCT 的 bonus 几乎把它变成”纯按先验走”，先验一旦在某次搜索里被随机 rollout 误导就没有足够预算纠正。
• 搜索集中度（24 个随机中局，先验 top-1 的访问占比）：$K=5$ 时 UCT $0.300$ / PUCT $0.358$；$K=10$ 时 $0.379$ / $0.496$；$K=20$ 时 $0.469$ / $0.571$；$K=50$ 时 $0.537$ / $0.631$。PUCT 系统性地把更多预算投向先验看好的动作——这就是 13.2.6 第 (1) 条”高度选择性”在 AlphaZero 版本下的强化形态。
• 自我对弈（$\pi(s)\propto N(s,a)^{1/\tau}$，$\tau=1$，每步 200 次模拟，20 局）：x 胜 11、o 胜 6、和 3。双方都是同一个 MCTS(200)，但先手方 x 明显占优（Tic-Tac-Toe 在双方完美对弈下必和，这里的偏离来自 200 次模拟不足以消除随机 rollout 的噪声）。这组数字直观说明”MCTS 是一种策略改进算子“：策略 $\pi(a\vert s)\propto N(s,a)$ 比它内部的随机默认策略强得多，但仍受预算限制。
• MCTS vs 简单 MC 搜索：同预算正面对弈（x = MCTS，o = 简单 MC，各 40 局）——这是本讲最有说服力的一组实验：

在完全相同的模拟预算下，MCTS 对简单 MC 搜索取得约 30:7 的压倒性胜率，且在 $K=20$ 这样的小预算下就已成立。原因正是 13.8 误区 1 所指出的：简单 MC 搜索把预算均分给 9 个候选落子（每步约 2 次模拟），而 MCTS 通过回传把预算动态集中到几棵有希望的子树里。这也说明为什么本讲开头那条”简单 MC → 期望极大树 → MCTS”的递进链是必要的：在只有一个正确答案的稀疏奖励任务上，均分预算的做法会彻底失败。

13.4.3 MCTS 的变体与工程改进

本小节汇总讲义第 13、21–25 页（及 Silver Lec 8–9）提到的四类改进。它们都不改变”四阶段”骨架，而是替换其中某一环。

（1）UCB1 vs UCT：同一个公式，两种语义

关键差异（也是 13.2.5 那个”略微奇怪”的来源）：UCT 把 UCB1 用在了一个收益分布本身会变的对象上——同一个 $(s,a)$ 在第 1 次和第 1000 次模拟时的”真实价值”不同（因为那时的树策略已经不同）。因此 UCT 不是 UCB1 的严格推广，而是一个启发式；它的对数遗憾保证需要额外的”树的缓慢增长”条件。

（2）roll-out 策略（默认策略）的选择

默认策略 $\pi$ 决定 $Q$ 的偏差（bias），是 MCTS 里最容易被忽视的设计选择。三条常见路线：

权衡：默认策略越好，$Q$ 的绝对值越准（13.5.2 条件依赖表第一行），但”不依赖领域知识”这个黑箱优势会被削弱。AlphaZero 的选择是”用网络替代 roll-out”——它同时拿到了低偏差和通用性，代价是需要训练网络。

（3）树的复用（tree reuse）

做法：一次真实决策执行后，把搜索树的根从 $s_t$ 移动到”实际执行动作 $a_t$ 对应的、访问次数最多的子节点”（本讲代码的 MCTS.child_for(a)），保留其整棵子树继续搜索。 收益（本讲实测）：$K=10$ 时成功率 $0.800\to0.900$、$K=50$ 时 $0.933\to0.950$、$K=1000$ 时平均步数 $7.33\to6.90$、回报 $0.6690\to0.6878$。代价：累计创建的树节点数（$K=1000$ 时 $67576$ vs 不复用时更少），以及”旧统计量可能过时”的偏差风险。 什么时候安全：讲义第 21/11 页描述 AlphaZero 在对局内每步复用树——此时环境平稳、对手是自身上一轮，统计量仍然有效。若环境非平稳或对手策略突变，应衰减或重置旧统计量（见 13.8 误区 7）。

（4）并行化

$K$ 次模拟除共享树统计量外相互独立，因此有三类经典并行方案：

讲义第 13 页把 “parallelisable” 列为 MCTS 的第五大优势；本讲的墙钟成本量级（每次 rollout 约 40 μs、$K=1000$ 的搜索约 40 ms；本机实测每次 rollout 38–49 μs、$K=1000$ 约 38–44 ms，随机器负载波动）说明这是算力受限而非数据受限的任务——并行化是唯一能直接换取棋力的手段，这正是 AlphaZero 说的 “bottleneck is only computation”。

13.5 评估指标与理论保证

13.5.1 评估指标

13.5.2 理论保证

（1）收敛到 Minimax 最优（UCT 的主要定理）. Kocsis & Szepesvári (2006) 证明：在有限动作空间、默认策略回报有界的条件下，UCT 在树的每个节点上的遗憾是对数级的，从而 $N_k(s,a)\to\infty$ 且

更精确地，根节点的累积遗憾上界形如 $O\bigl(c\sqrt{\vert \mathcal{A}\vert }\cdot\ln K\bigr)$（常数依赖奖励范围），即访问次数的分配满足 $N_k(s,a)\approx \frac{2c^2\ln k}{\Delta_a^2}$（$\Delta_a=q_*-q_a$ 是 gap）——gap 越小、访问越多，这个”$\ln k/\Delta^2$”型分配律与 L9 的 UCB1 逐字相同。

（2）收敛速度的经验形式. 由 $N_k(s,a)\propto \ln k/\Delta_a^2$，要区分 gap 为 $\Delta$ 的两条臂，需要的模拟次数是 $O(\ln K/\Delta^2)$；要在根节点以高概率选出最优动作，需要 $K\gtrsim \frac{c^2\ln K}{\Delta_{\min}^2}$，即 $K=\tilde O(1/\Delta_{\min}^2)$。这解释了 13.4 的现象：GridWorld 里四个动作的 $q^*$ 极差只有 $0.043$（$0.6504\sim0.6933$），$\Delta_{\min}=0.0006$（$0.6510$ 与 $0.6504$ 之间）极小，所以要到 $K\approx5000$ 才首次把动作 1 排到第一（实测 $K=10$ 时第一名是动作 2、$K=1000$ 时仍是动作 2）；而 Tic-Tac-Toe 的”挡 vs 不挡”gap 是 $1.0$ 量级，几十次模拟就够。

（3）不给出样本复杂度保证（重要区别）. MCTS 的保证是关于模拟次数 $K$（计算复杂度）的，不是关于与环境交互次数（样本复杂度）的。MCTS 假定模型可无限采样；若模型未知、必须边学边搜（例如 L14 的 MuZero 用学到的模型做 MCTS），则 L11–L12 的样本复杂度问题重新出现，且模型误差会系统性污染 $Q$。这是 MCTS 与 PAC-MDP 一族最本质的分工。

（4）条件依赖分析.

13.6 与其他讲次的关联

与 L2（Tabular MDP Planning）. L2 的值迭代/策略迭代是有模型规划的经典形式，需要显式 $P(s^{\prime}\vert s,a)$ 与 $R(s,a)$，复杂度含 $\vert \mathcal{S}\vert ^2$。MCTS 是有模型规划的采样版：只要求生成模型，复杂度与 $\vert \mathcal{S}\vert $ 解耦。两者在同一个小 MDP 上会收敛到同一个解——本讲 13.4 用值迭代算出的 $q^*(s_{12})$ 正是 MCTS 要逼近的目标。

与 L3–L4（Model-Free Evaluation / Control）. L3 的蒙特卡洛评估用真实经验轨迹估计 $V^\pi$；MCTS 的 rollout 用模拟轨迹估计 $q^\pi$，两者数学形式完全一样（都是 $\frac1n\sum G_k$），差别只在数据来源。”把无模型方法变成基于模拟的搜索”正是讲义第 4 页目录标题 Simulation-Based Search 的字面含义。L4 的 Q-learning 更新 $\hat Q\leftarrow\hat Q+\alpha(r+\gamma\max_{a^{\prime}}\hat Q-\hat Q)$ 与 MCTS 回传 $\hat Q\leftarrow \hat Q+(G-\hat Q)/n$ 的差别是：前者用自举（bootstrap）的一步目标，后者用完整模拟回报 $G$——这正是”MC vs TD”（L3）的对比在规划场景的重演。

与 L9（Bandits 与 UCB）. 这是本讲最直接的前置。UCT = UCB1 贴到树上：L9 的 $a_t=\arg\max_a[\bar r_a+\sqrt{2\ln t/n_a}]$ → 本讲的 $\arg\max_a[Q(s,a)+c\sqrt{\ln N(s)/N(s,a)}]$。L9 的 regret 界 $O(\sqrt{AT\ln T})$ 与 MCTS 的树内 $O(\ln K)$ 遗憾同源（$\sqrt{\cdot}$ 的探索项来自同一族 Hoeffding 界）。差别在于语义：L9 的 regret 是环境后悔，UCT 的是元层算力分配损失（13.2.5）。

与 L10–L12（Fast RL）. L10 的 Thompson 采样、L11 的贝叶斯 MDP / PSRL、L12 的 PAC-MDP / RMax 都在解决”模型未知时如何高效探索“。MCTS 假定模型已知，因此绕过了整个样本复杂度问题；反过来，L14 的 MuZero 把”学模型 + MCTS”结合起来，等于把 L11–L12 的问题重新引入。这是本课程两条线索（样本高效 vs 计算高效）的交叉点。

与 L14（MCTS 深入 + 伦理）. L14 第 3 页重申本讲的五大优势，第 6–22 页把本讲的 AlphaZero 连接展开成完整闭环：自我对弈数据生成、$\pi_t\propto N(s_t,a)^{1/\tau}$ 与终局结果 $z$ 作为标签、$L(\theta)=(z-v_\theta)^2-\boldsymbol\pi_t^\top\log\mathbf p_\theta$ 作为损失；L14 第 26–30 页进一步把 UCT 的”元层推理”讲透。本讲负责”树怎么长”，L14 负责”网络怎么学”。

与 L5–L7（Policy Gradient）. MCTS 用算力改进策略，策略梯度用梯度改进策略。AlphaZero 同时用两者：MCTS 产生目标分布 $\boldsymbol\pi_t$，交叉熵把它蒸馏进 $\mathbf p_\theta$（这是 L5–L7 的”用改进后的策略监督原策略”的直接应用），下一轮更强的 $\mathbf p_\theta$ 又让 MCTS 搜得更准。MCTS 可以被看作一个”免参数的策略改进算子”，与 L7 的策略迭代视角（评估 + 改进）完全同构。

与 L8（Imitation Learning / RLHF）. AlphaZero 的”用 MCTS 分布监督策略头”形式上就是行为克隆（Behavior Cloning），差别只在 teacher：模仿学习的 teacher 是人类专家（外部、固定、有上限），AlphaZero 的 teacher 是自己的搜索（内部、随训练进化、上限是算力）。讲义第 23–24 页的 “Advantages of Self Play for Go” 明确指出：“Bottleneck is only computation, no humans needed. Self-play also provides a well-matched player.”，并回答奖励密度问题：“Rewards will be quite dense as both players are evenly matched. This provides a form of curriculum learning.”（双方势均力敌 ⇒ 胜负交替 ⇒ 终局信号提供了课程学习式的渐进难度。）

13.7 关键要点

• MCTS 的价值主张只有一句话：把求解整个 MDP 换成求解”从现在开始的子 MDP”，用局部计算（local computation）换更好的即时决策。讲义第 5 页、第 8 页反复强调这一点，它是本讲全部技术的出发点。
• 五大优势要能逐条背诵并解释（讲义第 13 页）：高度选择性的最佳优先搜索（按价值而非固定顺序扩展）、动态评估状态（$Q$ 由实际采样更新而非静态网络）、用采样打破维数灾难（$O((\vert \mathcal{S}\vert \vert \mathcal{A}\vert )^H)\to O(KH)$）、适用于黑箱模型（只需采样接口）、计算高效 + anytime + 可并行。
• 四阶段是骨架：选择（UCT 沿树下走）→ 扩展（加一个新子节点）→ 模拟（随机默认策略跑到底）→ 回传（逆序把 $G$ 折回并更新 $N,Q$）。“逐回合变化的模拟策略”是 MCTS 与简单 MC 搜索的分水岭（讲义第 12 页原话：“the policy used to simulate episodes can change across each episode”）。
• UCT 就是 UCB1 贴在树上：$a^*=\arg\max_a\bigl(Q(s,a)+c\sqrt{\ln N(s)/N(s,a)}\bigr)$。理论 $c=\sqrt2\,R_{\max}$（$R_{\max}$ 为奖励范围）；太大退化均匀采样，太小锁死次优分支（实测 $c=0.1$ 时 $N=[130,26,43,1]$）。
• 收敛目标是 Minimax 最优：$Q(s,a)\to q_*(s,a)$、$N(s,a)\to\infty$，根节点遗憾 $O(\ln K)$。但这要求默认策略回报有界且每个状态被无限访问；默认策略太差（例如稀疏奖励下的随机策略）会导致收敛极慢。
• 动态评估 vs 静态评估的区别是偏差来源：MCTS 的 $Q$ 是有偏的（偏到 $q^\pi$ 而非 $q_$），但排序往往已经正确——实测 $K=20000$ 时 $Q(s,1)=0.3866$ 而 $q^(s,1)=0.6933$，排序对了、标定差了 0.9841。
• AlphaZero 的三项改造：用策略网络先验 $P_\theta$ 把 bonus 换成 PUCT 形式 $c\,P(a\vert s)\sqrt{N}/(1+N)$；用价值网络 $v_\theta$ 替代（或补充）随机 rollout；用自我对弈 + 交叉熵蒸馏让网络追上搜索。实测 PUCT 在 $K\ge20$ 后正确率反超 UCT（$0.867$ vs $0.713$ @ $K=20$），并把访问集中度从 $0.469$ 提到 $0.571$。
• 树复用是免费的加速：把根移到已执行动作对应的子节点，实测 $K=10$ 时成功率从 $0.800\to0.900$、$K=50$ 从 $0.933\to0.950$，$K=1000$ 时平均步数 $7.33\to6.90$、回报 $0.6690\to0.6878$。代价是内存与”旧统计量可能过时”。

13.8 常见误区与注意事项

误区 1：把”简单 MC 搜索”与”MCTS”混为一谈。 正确认识：两者的总预算语义不同。简单 MC 搜索是”每个动作做 $K$ 次模拟”，总模拟次数是 $\vert \mathcal{A}\vert \cdot K$；MCTS 是”总共做 $K$ 次模拟”，预算在动作间动态分配。当 $\vert \mathcal{A}\vert =361$（围棋）时，若给简单 MC 搜索 $10^4$ 次总预算，每个动作只有 27 次采样，精度极差；同样的 $10^4$ 次在 MCTS 里会被 UCT 不均等地分配，好动作可能拿到几千次。此外，简单 MC 搜索只做一步策略改进，MCTS 通过回传更新树内所有边，是”多层”改进。13.4 实测显示：在 Tic-Tac-Toe 上同预算对弈，MCTS 以 30:7 击败简单 MC（$K=20$）——这是总预算语义差异最直接的后果。

误区 2：在随机环境中只按动作 $a$ 建子节点。 正确认识：若 $P(s^{\prime}\vert s,a)$ 非退化（同一个 $a$ 可能到多个 $s^{\prime}$），则必须用 $(a,s^{\prime})$ 二元组做子节点键，否则两个完全不同的后继状态会共享同一个 $Q(s,a)$，$Q$ 的语义从”$q(s,a)$”被污染成”不同状态混合的均值”，UCT 的置信界也不再成立。本讲脚本一（随机滑移 GridWorld）用 self.children[(a, ns)]，脚本二（确定性 Tic-Tac-Toe）才敢用 self.children[a]——这不是偏好，而是环境决定的。另一种合法做法是只按 $a$ 建子节点但在该子节点上对状态做聚合（如 AlphaZero 对确定性围棋），此时必须确认”同 $a$ 必同 $s^{\prime}$”。

误区 3：以为”多算几次”就能让 $Q(s,a)$ 收敛到 $q^(s,a)$。** *正确认识：MCTS 的 $Q$ 收敛到的是默认策略** $\pi$ 的 $q^\pi$（并对树内策略不断改进），不是直接收敛到 $q_$。本讲实测把这个偏差量化得很清楚：GridWorld 里 $K=20000$ 时根节点 $Q(s_{12},\cdot)=[-0.3013,0.3866,-0.2679,-0.2651]$，而值迭代给出 $q^(s_{12},\cdot)=[0.6827,0.6933,0.6510,0.6504]$，最大偏差 0.9841（$Q(s,0)=-0.30$ 而 $q^*(s,0)=+0.68$，连符号都反了）。原因有二：(i) 默认策略是均匀随机的，在 $4\times4$ 网格里平均要 20+ 步才能碰巧到目标，rollout 又截断在 25 步，$G$ 被强烈折扣且方差巨大；(ii) 稀疏/远处奖励下，随机 rollout 极少采样到 $+1$，$Q$ 被”没到目标”的负值主导。MCTS 靠的是排序（relative ranking）正确，不是标定（calibration）正确；如果下游需要准确的 $q$ 值（例如做风险敏感决策），必须换更好的默认策略或价值网络。

误区 4：把 UCT 的探索当成”环境探索”，并因此认为”模型已知时 UCB 没用”。 正确认识：讲义第 39/29 页的 Refresh Your Understanding 出了这道题：“Upper confidence bounds are used to balance exploration and leveraging the acquired information…; These algorithms can be used in bandits and Markov decision processes; If the reward model is known, there is no benefit to using an upper confidence bound algorithm.” 讲义答案是 “True. True. Depends on setting. In bandits, no additional gain. In RL, if the dynamics model is not known, there will be a gain.” 要点有三：(i) 在 bandit 中若奖励分布已知，UCB 确实无额外收益（直接选最优臂）；(ii) 在 RL 中即使奖励已知，只要转移模型未知，UCB/乐观探索仍有收益（这是 L11–L12 的全部分量）；(iii) 在 MCTS 中，模型是完全已知的，UCB 的作用不是获取外部信息，而是元层的算力分配（讲义第 36/38 页把它归入 metalevel reasoning，引 Hay et al. 2012）。把这三层混为一谈是本讲最危险的误解。

误区 5：把 $c$ 当作”越大越保险”的超参数。 正确认识：$c$ 的理论值是 $\sqrt2\,R_{\max}$（$R_{\max}$ 为奖励取值范围），它必须随奖励尺度缩放。若把奖励从 $[-1,1]$ 改为 $[-100,100]$ 而不动 $c$，bonus 项会被 $Q$ 的尺度彻底淹没，搜索退化为 $\epsilon$-greedy 式的贪心（$c$ 形同虚设）；反之把 $c$ 调到远大于 $R_{\max}$ 则退化为均匀采样（实测 $c=5$ 时 $N=[51,54,48,47]$，几乎完全平均）。上面 13.2.5 的表格还揭示了一个更隐蔽的失效模式：$c=0.1$ 时虽然成功率仍有 0.950（因为该 GridWorld 的最优与次优差距小、容错高），但根访问分布已塌缩成 $[130,26,43,1]$——最优的动作 1 只拿到 26/200 次模拟，搜索在”决策正确”的假象下已失去可解释性与鲁棒性，一旦环境稍变（例如陷阱移到动作 0 的路径上）就会灾难性失败。因此评估 MCTS 不能只看成功率，还要看访问分布。

误区 6：认为 MCTS 适合所有 MDP 问题规模。 正确认识：讲义第 34/24 页的 Optional CYU 给了三个陈述，答案是 F, F, T：

1. “短视界 + 小状态小动作” —— 错（F）。此时直接做值迭代/期望极大树更快更精确，MCTS 的采样方差反而引入不必要的噪声。
2. “长视界 + 大动作空间 + 小状态空间” —— 错（F）。状态空间小意味着可以精确求解；而大动作空间恰恰是 MCTS 相对最弱的情形之一（每个动作都要被采样到，$\vert \mathcal{A}\vert $ 直接进入探索成本）。
3. “长视界 + 大状态空间 + 小动作空间” —— 对（T）。这正是 MCTS 的主场：状态空间大到无法枚举（围棋 $10^{170}$），动作空间小到可以让 UCT 在有限预算内覆盖（围棋 $361$，国际象棋约 $35$）。

误区 7：忽略树复用的”统计量过时”代价。 正确认识：树复用在实测中收益明显（13.4 中 $K=10$ 时 $0.800\to0.900$、$K=50$ 时 $0.933\to0.950$、$K=1000$ 时回报 $0.6690\to0.6878$），但复用的子树统计量是在旧的信息下积累的，而 MCTS 的一阶收敛保证假定”$N(s,a)\to\infty$”是在同一个搜索问题上成立的。当环境非平稳、或对手策略改变时，旧统计量会成为偏差源。工程上的折中做法包括：复用但衰减旧的 $N,Q$（乘法衰减），或只复用 $N$ 而重新初始化 $Q$。讲义第 21/11 页提到 AlphaZero 在对局内复用树（每步把根移到一个子节点），这正是”环境平稳、对手是自身上一轮”的情形，复用是安全的。

13.9 思考题（带答案）

思考题 1（手算 UCT 选择过程）★必做

某 MCTS 搜索树的节点 $s$ 处有 3 个动作，当前统计量如下（$\gamma$ 已包含在 $G_k$ 中，奖励范围 $[0,1]$）：

取探索常数 $c=\sqrt{2}$。(1) 计算 $N(s)$；(2) 计算三条臂的 $U(s,a)$ 与 $Q+U$，指出下一次模拟（第 21 次）会选择哪个动作（保留 4 位小数）；(3) 若这次模拟沿 $a_3$ 走到底得到回报 $G=-0.20$，写出 $a_3$ 更新后的 $Q(s,a_3)$，并判断第 22 次模拟会选择哪个动作。

答案.

(1) $N(s)=\sum_a N(s,a)=10+5+5=20$。

(2) 用 $\ln N(s)=\ln 20 = 2.99573$：

第 21 次模拟选择 $a_3$（$Q+U=1.89467$ 最大）。注意 $a_2$ 与 $a_3$ 的 $U$ 相同（同为 $N=5$），差距完全来自 $Q$——这正是”利用项”在起作用。

(3) 增量均值更新：$Q(s,a_3)\leftarrow 0.80+\frac{-0.20-0.80}{6}=0.80-\frac{1.00}{6}=0.80-0.16667=\mathbf{0.63333}$，$N(s,a_3)=6$，$N(s)=21$。第 22 次用 $\ln 21=3.04452$：

第 22 次模拟仍然选择 $a_3$（$1.64073$ 最大）。这一步是本讲最重要的一课：$a_3$ 唯一一次模拟拿到 $-0.20$ 的坏回报后，$Q$ 从 0.80 掉到 0.633，bonus 也从 1.095 降到 1.007——但”利用项下降的幅度（0.167）小于 $N$ 增大带来的探索项下降（0.087）后仍不足以被其他臂超越“，所以搜索继续深挖 $a_3$。这是 UCT”用 $\ln$ 增长的时间换取对当前最优臂的持续投入“的微观体现；若同样的坏回报连续出现若干次，$Q(s,a_3)$ 会被压到 $a_2$ 之下，搜索才会转向。关键洞察：一次坏样本不足以推翻一条被访问多次的臂——这正是”平均的力量”（Power of Averaging）。

思考题 2（手算 MCTS 一次迭代的四阶段与回传）

考虑一个确定性的两步迷你 MDP：状态 $s_0$ 有动作 $\{a,b\}$；$s_0\xrightarrow{a}s_1$（奖励 $0$）、$s_0\xrightarrow{b}s_2$（奖励 $0$）；$s_1$ 与 $s_2$ 各有动作 $\{c,d\}$，且

取 $\gamma=1$、$c=\sqrt2$、默认策略为均匀随机。假设搜索树当前状态为：根 $s_0$ 已扩展出 $a\to s_1$（$N=1$）与 $b\to s_2$（$N=1$），且 $s_1$ 与 $s_2$ 都尚未扩展（各自 untried = {c,d}），根节点 $N(s_0)=2$、$Q(s_0,a)=1.0$、$Q(s_0,b)=-1.0$（来自各自唯一一次模拟）。(1) 写出第 3 次模拟的四阶段；(2) 假设这次枚举扩展 $s_2$ 的 $c$ 并得到 $+1$，写出所有被更新边的 $N,Q$；(3) 第 4 次模拟会走哪条路？

答案.

(1) 四阶段. 阶段 1 选择：根 $s_0$ 已完全扩展（$a,b$ 都试过），所以不能停在这里，要沿 UCT 下走。

\(a:\ U=\sqrt2\sqrt{\tfrac{\ln 2}{1}}=1.414\times0.83255=1.17741\Rightarrow Q+U=1.0+1.17741=2.17741,\) \(b:\ U=\sqrt2\sqrt{\tfrac{\ln 2}{1}}=1.17741\Rightarrow Q+U=-1.0+1.17741=0.17741.\)

选 $a$，进入 $s_1$。$s_1$ 有未尝试动作（untried={c,d}），停止下降。 阶段 2 扩展：弹出 $s_1$ 的一个未尝试动作（按固定顺序取 $c$），执行后到达终止状态，$r=+1$。 阶段 3 模拟：新节点是终止状态，无需 rollout，$G=0$（终止状态无未来回报）。 阶段 4 回传：路径是 $[(s_0,a,\underbrace{0}_{\text{首步奖励}}),\ (s_1,c,+1)]$。从叶往根：

• 先处理 $(s_1,c,+1)$：$G\leftarrow 1+1\times 0=1$；$N(s_1,c)=1$，$Q(s_1,c)=1$；$N(s_1)=1$。
• 再处理 $(s_0,a,0)$：$G\leftarrow 0+1\times 1=1$；$N(s_0,a)=2$，$Q(s_0,a)\leftarrow 1.0+\frac{1-1.0}{2}=1.0$；$N(s_0)=3$。

(2) 被更新的边.

注意：$b$ 分支与 $s_2$ 完全没有被更新——这就是”高度选择性”的字面含义：一次模拟只更新一条路径。另外注意 $(s_0,a)$ 的 $Q$ 没变（仍是 1.0），因为新样本 $G=1$ 恰好等于旧均值，增量更新 $\frac{1-1.0}{2}=0$。这说明”$N$ 增加”不等于”$Q$ 改变”，$Q$ 只在收到不同回报时才动。

(3) 第 4 次模拟. $N(s_0)=3$，$\ln 3=1.09861$；$s_1$ 仍有未尝试动作 $d$，所以选择阶段仍在根上做决定：

\(a:\ U=\sqrt2\sqrt{\tfrac{1.09861}{2}}=1.414\times0.74115=1.04815\Rightarrow Q+U=1.0+1.04815=2.04815,\) \(b:\ U=\sqrt2\sqrt{\tfrac{1.09861}{1}}=1.414\times1.04815=1.48230\Rightarrow Q+U=-1.0+1.48230=0.48230.\)

仍然选 $a$，然后扩展 $s_1$ 的 $d$，得到 $r=0$，终止，$G=0$，回传更新：$N(s_1,d)=1$、$Q(s_1,d)=0$；$(s_0,a)$：$N=3$、$Q\leftarrow1.0+\frac{0-1.0}{3}=0.66667$；$N(s_0)=4$。

洞察：$s_1$ 的两个动作都被试完（untried 空）之后，第 5 次模拟的选择阶段才能继续下降到 $s_1$ 内部，用 $\bigl(Q(s_1,\cdot)+c\sqrt{\ln N(s_1)/N(s_1,\cdot)}\bigr)$ 在 $c$（$Q=1$）与 $d$（$Q=0$）之间选。MCTS 的”深度”是被探索顺序自然生长出来的：先横向铺开每个节点的所有动作，再向下深挖——这就是算法 13.2 第 5 行循环条件”已完全扩展”的全部威力。

思考题 3（UCB 与 UCT 的语义差异）

讲义第 36/38 页与第 37/27 页提出两个 UCT 相关的 Check Your Understanding。(1) 讲义问：“Why is this slightly strange? … Is there an exploration/exploitation problem during simulated episodes?”——给出你的回答。(2) 讲义第 37/27 页的陈述 (1)(2) 的答案是 “T. T”，但紧接着括号里追问 “If this is true, think about if this a good idea?”——请回答这个追问。(3) 讲义第 39/29 页关于 UCB 的三条陈述，为什么第三条的答案是”depends on setting”而不是简单的 True 或 False？

答案.

(1) “奇怪”之处在于目标函数换了。 UCB 之所以在 bandit 中是”正确”的算法，是因为它最小化的环境遗憾 $R(T)=\sum_t(\mu^*-\mu_{a_t})$ 正是我们要优化的量：每次拉臂都有真实的机会成本，且回报分布未知、只能靠采样估计。而在 MCTS 的模拟回合里：(i) 回报由已知模型 $\hat M$ 与已知默认策略 $\pi$ 生成，分布已知，可以无限次重采样；(ii) 每次”拉臂”的真实成本是计算时间，不是环境后悔。所以在模拟里谈”探索/利用”的时候，被权衡的不是“要不要冒险试一个可能更好的动作”，而是”下一步模拟该把算力花在哪条分支上，才能让根节点的最终决策最准“。讲义脚注把这种”关于计算该怎么分配”的推理称为元层推理（metalevel reasoning），并引 Hay, Russell, Tolpin & Shimony (2012)。形式上完全相同（同一个 UCB1 公式），语义上是两件事。

(2) “UCT 在树内最小化遗憾”是好事还是坏事？——很大程度是好事，但有边界。 好的一面：把”探索/利用”这个已被 L9 彻底研究的结构复用到树上，使得”算力分配”有了可证明的对数遗憾，从而根节点决策收敛到最优（13.3.2 的 ascii 收敛图）。有边界的一面有三点：其一，UCB 的遗憾界建立在静态臂（收益分布不随时间变）的假设上，而树上的臂收益随树的增长而改变（同一个动作在不同深度、不同对手策略下的 $q$ 值不同），所以 L9 的严格界并不直接适用，UCT 只是一个启发式；其二，UCB 的遗憾是”对真实奖励的后悔”，UCT 的遗憾是”对模拟回报的后悔”，最小化后者不能保证最小化前者的最终决策误差（因为 $\hat M$ 可能有偏、默认策略可能很差——13.4 实测 $K=20000$ 时 $Q$ 与 $q^*$ 仍差 0.9841）；其三，每次模拟都有固定的墙钟成本（本讲实测约 30–40 μs/rollout），所以 UCT 的”探索”必须在时间预算而非”模拟次数预算”下权衡，否则在小 $c$ 与长 rollout 的组合下会超时。

(3) 第三条之所以”depends on setting”，是因为”奖励模型已知”与”转移模型已知”是两件事。 陈述是”若奖励模型已知，则使用置信上界算法没有额外收益”。拆解：

• 在 bandit 中：只有奖励模型。若奖励分布已知，最优臂就是 $\arg\max_a\mu_a$，直接选它即可实现零遗憾，任何置信界机制都是多余的——没有收益（讲义答案中的 “In bandits, no additional gain”）。
• 在 RL 中：即使奖励函数 $R(s,a)$ 完全已知，只要动力学 $P(s^{\prime}\mid s,a)$ 未知，不确定性仍然存在，乐观（UCB/RMax/乐观初始化）依然能带来指数级的样本效率改进（L11–L12 的 PAC-MDP 结果）——有收益（讲义答案中的 “In RL, if the dynamics model is not known, there will be a gain”）。
• 在 MCTS 中：奖励与动力学都已知（本来就有模型才能做 MCTS），此时 UCB 的作用又回到”元层算力分配“而非”获取外部信息”——收益形式再次改变。

因此这一条既不能判 True 也不能判 False，答案取决于”已知”的是哪一个模型、以及 UCB 被用来解决哪一层的不确定性。这与本讲的另一条主线（讲义第 13 页第 (4) 条优势”Works for black-box models”）完美呼应：MCTS 假装自己面对的是黑箱，但 UCT 心里其实清楚模型是已知的——这正是”略微奇怪”的最终答案。

思考题 4（MCTS 的适用性判断）

针对下面三个 MDP，判断 MCTS 是否为合适选择，并说明理由（可参照讲义第 34/24 页的 CYU，其答案为 F, F, T）： (A) 视界 $H=3$、$\vert \mathcal{S}\vert =20$、$\vert \mathcal{A}\vert =4$ 的确定性 GridWorld； (B) 视界 $H=200$、$\vert \mathcal{S}\vert =50$、$\vert \mathcal{A}\vert =10^6$ 的推荐系统； (C) 视界 $H=150$、$\vert \mathcal{S}\vert \approx10^{170}$、$\vert \mathcal{A}\vert \le361$ 的围棋。

答案.

(A) 不合适。 状态与动作都极小、视界极短，期望极大树的规模是 $(20\times4)^3\approx5.1\times10^5$，直接穷举完全可行且结果精确。用 MCTS 反而引入采样方差（本讲实测在 $16$ 状态、$H$ 较大的 GridWorld 里，$K=10$ 时 $Q$ 的估计完全是噪声：$[-0.3790,-0.3700,-0.1491,-0.2477]$，四个动作的差别完全不反映真实优劣）。结论：小状态小动作短视界 → 用精确规划（值迭代 / 期望极大树），不要用 MCTS。

(B) 不合适。 这是 MCTS 最弱的情形：大动作空间 + 小状态空间。小状态空间意味着可以用值迭代精确求解或用函数逼近高效泛化（根本不需要搜索）；而 $\vert \mathcal{A}\vert =10^6$ 意味着即便有策略网络先验，PUCT 的 bonus 中 $P(a\vert s)$ 也会被摊薄到 $10^{-6}$ 量级，UCT 的”未访问臂优先”规则会导致每个动作都要被至少采样一次——$10^6$ 次模拟才刚够铺满根节点。结论：大动作空间应当走”学习策略 + 函数逼近”（L4/L5–L7），而不是搜索。

(C) 合适。 这是 MCTS 的主场（讲义答案中的 “T”）：状态空间大到完全无法枚举（$10^{170}$，维数灾难），但动作空间小（$\le361$），UCT 的探索成本只随 $\ln K$ 增长，配合策略网络先验（PUCT）可以把有效搜索宽度压到几十个分支，在 $10^3$–$10^4$ 次模拟内完成决策。结论：大状态空间 + 小动作空间 + 长视界 → MCTS（最好配 PUCT 与价值网络）是当前最强的一类方法，这正是 AlphaGo/AlphaZero 的设定。

统一判据：MCTS 的收益来自”用采样替代枚举状态“，其成本来自”必须对每个动作至少采样一次“。因此

附：本讲实验产物