《AI Agent 技术原理与架构·决策、记忆与学习》5.2 MCTS:价值估计与探索

蒙特卡洛树搜索把“多试几次”变成可控的探索:价值估计来自采样,探索用置信上界引导。本节用三个动作的确定性奖励序列演示 UCT 在不同探索系数下的访问分布与最终选择,解释 c=0 的纯利用陷阱与 c 过大的探索浪费,并给出搜索预算与探索系数的调参判据。

以下数字为教学示例,不构成对任何真实系统或供应商的承诺。

上一节的树搜索回答"从哪里搜",这一节回答一个更微妙的问题:搜索时怎么决定继续挖哪条路。蒙特卡洛树搜索(MCTS)的答案是把"多试几次"变成一个可控的过程:用采样估计价值,用置信上界引导探索。价值估计回答"这条路径看起来多好",探索回答"还没看够的路径值不值得再看"。

这一节用一个三动作的最小树演示 UCT(Upper Confidence Bound for Trees):探索系数 c 从 0 变到 2,访问分布和最终选择如何变化。重点是理解 c 的语义,而不是背 UCT 公式。

MCTS 的三个环节

MCTS 在高层只有三个环节,不断循环:

环节做什么关键问题
选择用 UCB 从根往下选一个节点选"当前最好"还是"没看够"
扩展/模拟从选中节点采样一次结果每次模拟的回报
回传把回报累加到路径上的节点访问次数与均值更新

对 Agent 来说,“模拟"可以是真实执行一步动作,也可以是打分器给一次评估。真实执行贵但可信,评估快但可能偏。MCTS 不关心模拟来自哪,只关心访问次数和平均回报这两个统计量。

UCT 公式在说什么

$$\text{UCB}(a) = \bar{Q}(a) + c \cdot \sqrt{\frac{\ln N}{n(a)}}$$

其中 $\bar{Q}(a)$ 是动作 a 的平均回报,$n(a)$ 是 a 被访问的次数,$N$ 是父节点的总访问次数,$c$ 是探索系数。两项各有含义:

  • 第一项 $\bar{Q}(a)$ 是利用:选看起来最好的。
  • 第二项 $c \cdot \sqrt{\ln N / n(a)}$ 是探索:访问次数少的动作获得一个加分,鼓励去试。

c=0 时第二项消失,变成纯利用——永远选当前均值最高的。问题在于,均值来自少量采样,可能只是运气好。c 越大,探索权重越高,越愿意去试访问少的动作。

最小实验:三动作的 UCT

下面的实验给根节点三个动作,每个动作带一组确定性的奖励序列,按访问顺序循环出现,因此模拟是确定性的:同一组参数永远得到同一张表。三个动作的真实均值分别是 A=6.0、B=7.5、C=2.5。

# file: agp_lab/mcts.py | write
# tier: 3
# verify: python3 -m unittest tests.test_mcts
"""UCT 的最小实验:价值估计与探索的取舍。

根节点有三个动作。每个动作下面有一组固定奖励,按访问顺序循环出现,
因此模拟是确定性的:同一组参数永远得到同一张表。UCT 用

    Q(a) + c * sqrt(ln N / n(a))

在“当前估计最好的动作”和“访问较少的动作”之间做选择。c=0 是纯利用,
c 越大越偏向探索。实验比较不同 c 下的访问分布与最终选择。

所有奖励与参数均为教学假设,不是任何真实系统的测量值。
"""
from __future__ import annotations

import math
from dataclasses import dataclass, field

# 三个动作的确定性奖励序列;真实均值分别为 6.0、7.5、2.5。
OUTCOMES: dict[str, tuple[int, ...]] = {
    "A": (9, 3, 9, 3),
    "B": (3, 9, 9, 9),
    "C": (10, 0, 0, 0),
}
CORRECT_ACTION = "B"


@dataclass
class ActionNode:
    name: str
    outcomes: tuple[int, ...]
    visits: int = 0
    total: float = 0.0
    cursor: int = 0

    @property
    def mean(self) -> float:
        return self.total / self.visits if self.visits else 0.0

    def next_reward(self) -> int:
        reward = self.outcomes[self.cursor % len(self.outcomes)]
        self.cursor += 1
        return reward

    @property
    def true_mean(self) -> float:
        return sum(self.outcomes) / len(self.outcomes)


@dataclass
class Root:
    children: list[ActionNode] = field(default_factory=list)
    visits: int = 0

    def ucb(self, child: ActionNode, exploration: float) -> float:
        if child.visits == 0:
            return math.inf
        bonus = exploration * math.sqrt(math.log(self.visits) / child.visits)
        return child.mean + bonus

    def select(self, exploration: float) -> ActionNode:
        return max(self.children, key=lambda node: (self.ucb(node, exploration), -ord(node.name[0])))


def build_root() -> Root:
    return Root([ActionNode(name, outcomes) for name, outcomes in OUTCOMES.items()])


def run_mcts(simulations: int, exploration: float) -> Root:
    """执行固定次数的确定性 UCT 模拟。"""
    if simulations < 1:
        raise ValueError("simulations 必须至少为 1")
    if exploration < 0:
        raise ValueError("exploration 不能为负")
    root = build_root()
    for _ in range(simulations):
        child = root.select(exploration)
        reward = child.next_reward()
        child.visits += 1
        child.total += reward
        root.visits += 1
    return root


def best_action(root: Root) -> str:
    if not root.children:
        raise ValueError("根节点没有动作")
    return max(root.children, key=lambda node: (node.mean, -ord(node.name[0]))).name


@dataclass(frozen=True)
class Row:
    action: str
    visits: int
    estimate: float
    true_mean: float


def summarize(root: Root) -> list[Row]:
    return [
        Row(child.name, child.visits, child.mean, child.true_mean)
        for child in root.children
    ]


if __name__ == "__main__":
    for exploration in (0.0, 1.0, 2.0):
        root = run_mcts(60, exploration)
        print(f"c={exploration:.1f} 选择={best_action(root)} "
              f"根访问={root.visits}")
        print(f"{'动作':<6}{'访问':>6}{'估计价值':>10}{'真实均值':>10}")
        for row in summarize(root):
            print(f"{row.action:<6}{row.visits:>6}{row.estimate:>10.2f}{row.true_mean:>10.2f}")

运行:

cd private/labs/agp-lab
python3 -m agp_lab.mcts

输出:

c=0.0 选择=A 根访问=60
动作        访问      估计价值      真实均值
A         57      6.05      6.00
B          1      3.00      7.50
C          2      5.00      2.50
c=1.0 选择=A 根访问=60
动作        访问      估计价值      真实均值
A         56      6.00      6.00
B          1      3.00      7.50
C          3      3.33      2.50
c=2.0 选择=B 根访问=60
动作        访问      估计价值      真实均值
A         28      6.00      6.00
B         29      7.34      7.50
C          3      3.33      2.50

这张表是理解 UCT 的三块拼图。

**c=0 是纯利用陷阱。** 60 次模拟里 A 被访问了 57 次,B 只有 1 次。为什么?A 的前两次奖励是 9、3,均值很快变高;B 的前两次是 3、9,第一次采到 3 后均值掉到 3.0,被纯利用规则放弃。但 B 的真实均值是 7.5,是正确答案。**纯利用把早期运气当成结论**,这正是 c=0 不可用的原因。

**c=1 还是不够。** 访问分布几乎没变:A 56 次、B 1 次。B 只被访问过一次,均值 3.0 仍然是噪声;而 ln(60)/1 的探索项不算小,为什么 B 还是只被访问一次?因为 UCB 选的是**总和最大**:A 的均值 6.0 加一个不大的探索项,仍然压过 B 的 3.0 加一个大探索项。初期的一两次坏采样,把 B 推到了深坑里,之后的探索加分不足以把它拉回来。

**c=2.0 找到了正确答案。** B 被访问 29 次,估计价值 7.34,最终被选择。更大的探索系数让 B 有机会积累足够的样本,均值回归到接近真实值 7.5,然后利用项开始主导,访问量追上 A。这就是 UCT 的自我纠错:**探索积累信息,利用兑现信息**。

## c 的调参语义

c 不是"越大越好"或"越小越好",它决定的是**你愿意为探索付多少代价**:

- c 太小:早期样本的噪声被当成结论,可能锁定错误动作;
- c 过大:访问量在好动作和差动作之间来回摆,浪费预算在注定不优的动作上;
- c 合适的标志:**选择的结果对 c 不那么敏感**——在一段区间里,无论 c 是多少,最终选择都稳定。

最后一个标志是工程上最实用的判据。你不需要精确知道最优 c,只需要确认在合理的 c 区间里结论稳定。如果 c 从 0.5 到 3.0 结论都一样,这个结论就相对可信;如果换一个 c 结论就翻,说明信息还不够,再多模拟一些。

## 价值估计的噪声来源

MCTS 的估计质量受两个因素支配:

1. **采样次数**:访问越多,均值越接近真实值;但真实值本身可能随时间变化(非平稳环境)。
2. **模拟器质量**:如果模拟器给每个动作的系统性偏差,采样再多也消除不了。

第二个因素在 Agent 场景里尤其危险。假设打分器对长答案有偏见,那么"访问最多"的动作其实是"打分器最喜欢"的动作,而不是真实最优。MCTS 只解决估计的随机误差,不解决模拟器的系统偏差。

## 架构含义

MCTS 对架构有三个直接约束:

1. **模拟器要便宜或可复用。** 真实执行做模拟太贵,通常需要一层可取消的评估器。
2. **访问统计要持久。** 不同运行之间保留访问次数与均值,才能做增量搜索,而不是每次都从头搜。
3. **探索系数要可配。** 不同任务的信息价值不同:高风险任务要多探索,成本敏感任务要早利用。

第 2 条经常被忽略。每次重新搜一遍,等于把上一轮学到的东西全部丢掉;真正的 Agent 里,搜索树的访问统计应该跨步骤保留。

## 架构判据

| 判据 | 合格的样子 | 不合格的样子 |
| --- | --- | --- |
| 探索显式 | 有 UCB 系数 c 可调 | 只按当前均值贪心 |
| 估计有方差意识 | 报告访问次数与均值 | 只报"最优动作" |
| 结论稳定 | c 区间内选择不变 | 换个 c 结论就翻 |
| 模拟器可审计 | 模拟器与真实结果有对照 | 模拟器是黑盒 |
| 统计可持久 | 跨运行保留访问统计 | 每次从零开始 |

"结论稳定"是唯一能自动检查的一条:调参时扫一段 c,看选择是否稳定。不稳定就该加模拟,而不是继续调 c。

## 与三条工作负载的关系

- W1 检索问答:价值估计可以是引用命中率的近似模拟,探索预算小(几百次内)。
- W2 代码修复:模拟可以是一次"跑测试",贵但可信;探索集中在候选补丁,深度优先于广度。
- W3 运维处置:模拟器本身有风险,探索只能发生在**只读动作**上;写动作不进 MCTS,走审批。

W3 是 MCTS 最不该用的场景:模拟"重启服务"的后果既不便宜也不安全。搜索的价值估计必须建立在可逆、只读的模拟上;不可逆动作应该由人工审批与固定流程决定,而不是被一个搜索算法探索。

## 小结

- MCTS 的三个环节是选择、模拟、回传;统计量只有访问次数与均值。
- UCB 第一项是利用、第二项是探索;c 决定探索权重。
- c=0 的纯利用会被早期噪声锁定,可能错过真实最优。
- 探索积累信息,利用兑现信息;合适的 c 让最终选择对 c 不敏感。
- 价值估计消除随机误差,但消除不了模拟器的系统偏差。
- 搜索树统计要跨运行持久,模拟器对不可逆动作必须禁用。

阅读导航:上一节:[5.1 树搜索与 Beam](/agp-decide-05-1-tree-search-beam/) · 下一节:[5.3 搜索何时值得:成本/质量判据](/agp-decide-05-3-search-worth-it/)。

## 常见错误与边界

1. **用纯利用。** c=0 把早期采样运气当结论,可能稳定地选错。
2. **c 一刀切。** 高风险任务要多探索,成本敏感任务要早利用;系数要按任务配。
3. **忽略模拟器偏差。** 访问最多只能代表"模拟器最喜欢",不代表真实最优。
4. **每次重新搜。** 访问统计不持久,等于丢掉了上一轮学到的信息。
5. **对不可逆动作做搜索。** 模拟重启、模拟写库既不便宜也不安全;探索只限只读动作。
6. **只报最优动作。** 没有访问次数和均值,无法判断这个最优是否来自噪声。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图