增强学习（1）：蒙特卡洛、树搜索与 Q-learning

小象实战讲义 · 机器学习算法精讲

本节从一件朴素的事情出发：蒙特卡洛——用随机采样去逼近真实情况。先用它把圆周率 $\pi$ 算出来（讲师给了一条与教科书常见的写法稍有不同的比值推导，值得单独走一遍）；再把同样的思想搬到围棋下不完的问题上——rollout 与蒙特卡洛树搜索；然后进入正题：把「走房间」写成一张 reward 矩阵，学增强学习里最简单的方法 Q-learning——它的公式只有一行，但一行里藏着「用未来的估值回传给现在」的全部思想。最后是整门课的大总结：从 $(x, y)$ 到模型谱系，到 80 年代的万金油们，再到那句「俱往矣，数风流人物，还看今朝」。

💡 核心导读

• 蒙特卡洛：名字来自赌场（Monte Carlo）；最早的蒙特卡洛 simulation 做的是对不确定性的逼近——撒点数圆内圆外，$\pi = 4/(\alpha + 1)$。
• rollout：围棋延伸不到终局，就对节点随机采样若干条路径、取平均得分当节点的值——再用估计值代替真实值。
• 树搜索的循环：selection（选目前值最大的）→ expansion（延伸出分支）→ simulation（分支做路径采样估值）→ 估值反馈回来告诉你延伸得好不好。
• Q-learning：$Q(\text{state}, \text{action}) = R(\text{state}, \text{action}) + \gamma \cdot \mathrm{Max}[Q(\text{next state}, \text{all actions})]$——对目前状态的估值，来自它未来状态的估值，值沿着衰减系数 $\gamma$ 一路回传。
• 全课收束：假设对了模型才好；人的重要任务是选好模型。

蒙特卡洛：用随机采样逼近真实

简单来讲，蒙特卡洛就是一个估计——对真实情况的一个逼近。名字的来历就是那个赌城（Monte Carlo）；而最早的蒙特卡洛 simulation，做的就是对不确定性的逼近。

讲师用一个特别简单的问题演示：估计圆周率 $\pi$。圆的周长是 $2\pi R$、面积是 $\pi R^2$；给它画一个外接正方形，边长 $2R$、面积 $4R^2$。把整个正方形当成一个随机区域，均匀地随机取点——取得够密、够均匀时，就可以数：多少点落在圆的外面、多少点落在圆的里面。

讲师的推导走的是比值这条路。设 $\alpha$ = 圆外的点数 / 圆内的点数，那么（$R$ 取 1）：

$$\alpha = \frac{4 - \pi}{\pi} = \frac{4}{\pi} - 1 \quad\Longrightarrow\quad \pi = \frac{4}{\alpha + 1}$$

$\alpha$ 是可以直接从点数里估出来的——所以只要把 $\alpha$ 估计好，$\pi$ 就算出来了。跑一遍：

import random, math

rng = random.Random(42)

n_total, n_inside = 20000, 0
for _ in range(n_total):
    x, y = rng.uniform(-1, 1), rng.uniform(-1, 1)
    if x * x + y * y <= 1.0:
        n_inside += 1
n_outside = n_total - n_inside

alpha = n_outside / n_inside
pi_hat = 4 / (alpha + 1)

print(f"采样 {n_total} 个点: 圆内 {n_inside}, 圆外 {n_outside}")
print(f"比值 alpha (圆外/圆内) = {alpha:.4f}")
print(f"pi = 4 / (alpha + 1) = {pi_hat:.4f}")
print(f"math.pi             = {math.pi:.4f}")

采样 20000 个点: 圆内 15736, 圆外 4264
比值 alpha (圆外/圆内) = 0.2710
pi = 4 / (alpha + 1) = 3.1472
math.pi             = 3.1416

两万个均匀的点，$\alpha$ 估到 0.2710（理论值 $4/\pi - 1 \approx 0.2732$），代回去 $\pi \approx 3.1472$——离真值 3.1416 已经很近。点数越多、越均匀，这个估计就越好。不断地均匀取点，用样本的统计特性逼近我们关心的目标量——这就是蒙特卡洛 simulation。（教科书更常见的是「圆内点占比 $p = \pi/4$，所以 $\pi = 4p$」；讲师用圆外比圆内的 $\alpha$，两条路完全等价。）

顺带提两个名字：这套思想有一支大名鼎鼎的后裔叫 MCMC（Markov chain Monte Carlo，马尔可夫链蒙特卡洛），用来估计一个后验概率——本课没有时间详细讲；还有吉布斯采样，讲师预告了一句「一会简单描述一下」，后面其实也没展开——留个名字在这里，感兴趣的同学自行深入。

围棋下不完怎么办：rollout 与蒙特卡洛树搜索

把蒙特卡洛的思想搬到搜索上。回忆这类问题：一个状态的值，要根据它不断延伸的下面的值来得到——一直延伸到有了输赢，值才返回来（propagation）。但围棋这种问题，很多情况下延伸不到最后，怎么办？

随机延伸。与其等着延伸到终局，不如从当前节点随机选几条轨道走下去——这就是 rollout：对某一个节点的估计，可以随机采样它 10 条、20 条或者 100 条路径，把这些路径里得到的平均得分，作为这个节点的得分。仍然是那句话：用一个估计出来的点，去估计真实的情况。

import random

rng = random.Random(7)

def rollout(p_win):
    """随机模拟一条完整路径: 赢得 1 分, 输得 0 分。"""
    return 1 if rng.random() < p_win else 0

branches = [("分支A", 0.9), ("分支B", 0.5), ("分支C", 0.1)]   # 每个分支的真值(赢率)

for n in (10, 100, 1000):
    ests = {name: sum(rollout(p) for _ in range(n)) / n for name, p in branches}
    best = max(ests, key=ests.get)
    row = ", ".join(f"{k}={v:.2f}" for k, v in ests.items())
    print(f"每支 {n:>4} 次 rollout: {row}  -> 选 {best}")

每支   10 次 rollout: 分支A=1.00, 分支B=0.60, 分支C=0.10  -> 选 分支A
每支  100 次 rollout: 分支A=0.95, 分支B=0.51, 分支C=0.07  -> 选 分支A
每支 1000 次 rollout: 分支A=0.90, 分支B=0.50, 分支C=0.11  -> 选 分支A

10 次时分支 A 抽出过满分 1.00（样本太少、运气成分大）；到 1000 次，三个估计 0.90 / 0.50 / 0.11 已经贴住真值 0.9 / 0.5 / 0.1——平均得分随路径数增加而稳定，这就是 rollout 的底气。

在 rollout 之上，就是蒙特卡洛树搜索（Monte Carlo tree search）的基本循环（讲师：它有很多具体的算法和不同的情况，时间有限，这里给大家一个基本的 taste）：

1. Selection（选择）：对某一支的延伸需要做选择——走到目前值最大的那一支（所谓延伸，就是选择一个 action）；
2. Expansion（扩展）：把这个状态进行延伸，比如分成大概三个分支；
3. Simulation（模拟）：每一个分支的值是多少，做一次刚才说的路径采样——simulation 就是 rollout；
4. 反馈：把 simulation 得到的值返回到刚才扩展出来的节点上。比如这一支做出 0.8、另一处延伸后做出来 0.4——那我觉得 0.8 更好，就往这个地方走。

之后往下走的每一部分，都遵循同样的 procedure：先选目前值最大的；值最大的地方需要有子节点往外延伸；每个子节点做 simulation 估值；估值反馈回来，告诉刚才延伸的节点延伸得好不好——延伸的方式有好几种，你选值最大的那个去延伸。

走房间：reward 矩阵与 Q 值

现在把 reinforcement learning 的地面规则摆出来。还是那个走迷宫式的小问题：几个屋子，用一个矩阵描述——reward 和 action 的矩阵，叫 reward 矩阵。纵坐标是 state（0～5，目前的房间），横轴是下一时刻你选择去哪个屋子。这个例子里 action 很简单——就是「从哪个屋子到哪个屋子」，所以它是一个方阵，状态过渡本身就默认是 action（不像「上下左右」那种动作，但可以理解成一回事）。

矩阵的读法（三种格子）：

• $-1$ 是不能走的——非常差的值，比如从 0 号房间没有门通到某些屋子；
• $0$ 是能走、但没有任何好处的——比如 3 到 2、2 到 3，reward 都是 0；这些就是「目前状态下还没达到目标」的可走路线；
• $100$ 是通向目标的——目标是走出屋子（状态 5）：4 到 5 给 100 分，1 到 5 给 100 分；5 自己到自己也给 100 分——5 也是一个状态，这个格子代表「我已经在 5 了，不要往回走，保持现在的状态」——就像下棋走到最后的赢棋局面，这是我们希望达到的最后状态。

有了 R，Q-learning——reinforcement learning 里最简单的一个学习方法——算的是 state-action 函数的 Q 值：Q 函数是关于目前状态和它所选择 action 的函数，我们通过它的取值来决定怎么选下一个 action。Q 值怎么计算？讲师强调：「非常容易的一个公式，大家可以记住这个」：

$$Q(\text{state}, \text{action}) = R(\text{state}, \text{action}) + \gamma \cdot \mathrm{Max}\left[Q(\text{next state}, \text{all actions})\right]$$

拆开读：选了某个 action，你先拿到多大的 reward；再加上伽马（$\gamma$ 是个常数，0.8、0.9 都行——一个衰减/损耗系数）乘上下一个状态所有 action 的 Q 值里的最大值。所以这件事的本质是：对目前状态的估值，是通过它未来状态的估值——很多 reward、很多状态，都是把后面的东西加到前面来；就像走到最后程序赢或输、有了正 100 分负 100 分，这些值每次通过衰减的权重回传回来，每个状态就都有了自己对应的 Q 值。

第一步手算（课件上现成的例子）：求 $Q(1, 5)$。

$$Q(1,5) = R(1,5) + 0.8 \times \mathrm{Max}\left[Q(5,1), Q(5,4), Q(5,5)\right] = 100 + 0.8 \times 0 = 100$$

选了「1→5」先得 100 分；到了 5 号屋，下一状态能去 1、去 4、留在 5——这些 Q 值一开始全是 0（还没更新过），最大就是 0——所以 $Q(1,5) = 100$。把整张表不断更新到收敛、再让 agent 拿它当向导：

R = [
    [-1, -1, -1, -1,   0,  -1],
    [-1, -1, -1,   0,  -1, 100],
    [-1, -1, -1,   0,  -1,  -1],
    [-1,   0,   0,  -1,   0,  -1],
    [  0, -1, -1,   0,  -1, 100],
    [-1,   0,  -1,  -1,   0, 100],
]

def q_learn(R, gamma=0.8, rounds=60):
    n = len(R)
    Q = [[0.0] * n for _ in range(n)]
    for _ in range(rounds):
        for s in range(n):
            for a in range(n):
                if R[s][a] >= 0:
                    Q[s][a] = R[s][a] + gamma * max(Q[a])
    return Q

print("第一步手算: Q(1,5) = R(1,5) + 0.8 * max[Q(5,1), Q(5,4), Q(5,5)] = 100 + 0.8 * 0 =", 100 + 0.8 * 0)
Q = q_learn(R, gamma=0.8)
print()
print("收敛后的 Q 表 (gamma=0.8):")
print("        " + "  ".join(f"{a:>5}" for a in range(6)))
for s in range(6):
    print(f"  s={s}:  " + "  ".join(f"{v:5.0f}" for v in Q[s]))
print()
print("以 Q 为向导, 从房间 2 出发:")
s = 2
path = [s]
while s != 5:
    s = max(range(6), key=lambda a: Q[s][a])
    path.append(s)
print("  路径: " + " -> ".join(map(str, path)))

第一步手算: Q(1,5) = R(1,5) + 0.8 * max[Q(5,1), Q(5,4), Q(5,5)] = 100 + 0.8 * 0 = 100.0

收敛后的 Q 表 (gamma=0.8):
            0      1      2      3      4      5
  s=0:      0      0      0      0    400      0
  s=1:      0      0      0    320      0    500
  s=2:      0      0      0    320      0      0
  s=3:      0    400    256      0    400      0
  s=4:    320      0      0    320      0    500
  s=5:      0    400      0      0    400    500

以 Q 为向导, 从房间 2 出发:
  路径: 2 -> 3 -> 1 -> 5

对着收敛表读三件事。第一，100 分是怎么长出脚的：$Q(1,5)$ 从第一轮的 100 涨到 500——因为住进 5 号屋这个状态本身值钱（$Q(5,5)=500$），于是「1→5」= 100 + 0.8×500。第二，值在沿路回传、逐级衰减：一步就能进 5 的 1、4 号屋，值是 500；两步之外的 3、0 号屋值 400；三步之外的 2 号屋只剩 320——每远一步打一次八折，这正是 $\gamma$ 在公式里干的事。第三，拿 Q 当向导走一遍：从房间 2 出发，2 号屋里最大的 Q 是去 3（320）；3 号屋里去 1 和去 4 打平（都是 400，任选其一，这里选了 1）；1 号屋里去 5（500）——路径 2-3-1-5，正是课件上给出的答案。

全课总结：从 $(x, y)$ 到「数风流人物」

最后把整门课收个总。我们自始至终做的是：给定一组数据 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$——这是有监督学习，想学 $f$：把 $x_i$ 映射到 $y_i$（$y_i$ 一般属于 $\mathbb{R}$，$x_i$ 属于 $\mathbb{R}^n$）；把 $y$ 去掉，就是非监督学习——学的还是 model $f$、还是这个函数关系。模型的谱系是从线性函数开始的（每个维度满足线性关系），到决策树；之后是万能的算法——不关心 $f$ 具体是什么函数：用概率逼近它、用神经网络逼近它、用高斯过程逼近它；甚至对数据分布不做假设，直接 kernel density estimation、按 empirical 分布来。但有一条贯穿的判断：如果你对数据生成的假设是正确的，模型会更好；假设错了，模型就更差——好与坏，完全由模型设计者对这个问题的理解程度决定。所以机器学习到最后，不只是拿算法去做实验的过程，需要人对看到的问题有深刻理解、找到最合适的模型；设计新模型显得过于高大上，那人的重要任务，就是怎么去选这些好的模型。

盘点一下课程覆盖：supervised、unsupervised 都讲了；semi-supervised 基本没讲，reinforcement learning 几乎没讲——有兴趣的同学可以去 GitHub 上找 reinforcement learning 的材料深入。多说一步现在的热点 Deep Reinforcement Learning：它做的事情，是把我们刚才那个从 state 到 action 的 reward（或者 Q 的选择）不用概率的形式，用一个神经网络；action 的选择也可以是个神经网络——输入现在的 state、给出最后的 action。就像最早的阿尔法狗：给定一个棋盘作为 state，目的是对每一个点估值——通过一个神经网络，给定状态就出一个 value；如果给定状态、输出的是下一个棋落在哪的概率，那就更像一个 autoencoder——输入是状态、输出一个向量，代表 19×19 棋盘上（$19 \times 19 = 361$ 格；讲师口播「381」为口误）哪一格下的概率最大。神经网络的好处是可以逼近任何复杂的关系，坏处是需要大量的数据——好在今天有大量数据、大量计算资源、很好的 framework，不用从头写；但也有一个现实的坏处：大家现在都拿神经网络去套，并不了解问题的本质是什么，只是想从数据里逼近它而已。这件事对不对，我们不做评价。

历史地看一眼：神经网络在 80 年代就已经是一个万金油。八九十年代的人工智能文章，可以特别有意思地分成三类：一类用神经网络解决各种疑难问题；一类用遗传算法解决各种优化问题；还有一大类用模糊逻辑——把以前不确定性的东西用模糊逻辑建模，把以前可能用概率表示的、跟人相关的知识都用 fuzzy 规则来表示。俱往矣——数风流人物，还看今朝：希望大家把以前这些好处坏处、把基础打好之后，对实际问题加深理解，提出自己的模型。这，就是整门课希望达到的目的。

📝 动手练一练

1. 两种「随机逼近」：本节开头的 $\pi$ 估计，与树搜索里的 rollout，都在「用随机采样逼近一个难以直接计算的值」。请说出它们在目标、过程、作用上的异同。

2. 换个 $\gamma$ 重算：把正文代码块 2 的衰减系数从 0.8 改成 0.5，重新跑到收敛。手算：$Q(5,5)$、$Q(1,5)$、$Q(0,4)$ 各是多少？$\gamma$ 变小意味着什么？

本章小结

本节三件事、一个总结。蒙特卡洛：用随机采样逼近真实——均匀撒点、数圆内圆外，$\pi = 4/(\alpha+1)$（代码块 1，两万点估到 3.1472）；它的后裔 MCMC 用来估计后验概率（本课未展开）。树搜索：围棋延伸不到终局，就 rollout——随机采样 10 条、100 条路径取平均分当节点值（代码块 3）；循环是 selection 选最大 → expansion 延伸分支 → simulation 采样估值 → 反馈比较、往值大的走。Q-learning：reward 矩阵（-1 不能走 / 0 白走 / 100 通目标）+ 一行公式 $Q = R + \gamma \cdot \mathrm{Max}[Q(\text{下一状态})]$——对现在的估值来自未来的估值、值沿 $\gamma$ 逐级衰减回传；$Q(1,5) = 100 + 0.8 \times 0 = 100$ 起步，收敛后 5 号屋值 500、回传成 400、320，agent 拿 Q 当向导走出 2-3-1-5（代码块 2）。全课收束：监督学 $f: x \to y$、非监督去掉 $y$；线性→决策树→万能逼近（概率/神经网络/高斯过程/KDE）；假设对了模型才好——人的任务是选好模型；Deep RL 把 reward/action 换成神经网络（阿尔法狗：棋盘进、value 或落子概率出）；80 年代的万金油们——神经网络、遗传算法、模糊逻辑——俱往矣，数风流人物，还看今朝。

📋 行动清单

• 手推比值公式：不看正文，从 $\alpha = (4R^2 - \pi R^2)/\pi R^2$ 推出 $\pi = 4/(\alpha + 1)$。
• 手算两步 Q 更新：先算第一轮的 $Q(1,5)$ 和 $Q(5,5)$（都是 $100 + 0.8 \times 0 = 100$），再对照代码块 2 的收敛表，说说多出来的 400 是从哪来的。
• 改 $\gamma$ 重跑：把代码块 2 的 $\gamma$ 改成 0.5，验证动手练第 2 题的手算（200 / 200 / 100）。
• 去 GitHub 找一个 RL 入门仓库：跑通一个 gym 小例子，对照本节的 reward、state、action 三件套。

—— 小象教研组