以下数字为教学示例,不构成对任何真实系统或供应商的承诺。
上一节的树搜索回答"从哪里搜",这一节回答一个更微妙的问题:搜索时怎么决定继续挖哪条路。蒙特卡洛树搜索(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. **只报最优动作。** 没有访问次数和均值,无法判断这个最优是否来自噪声。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。