MCTS: Monte Carlo Tree Search
一句话定位
MCTS 通过构建一棵搜索树，利用随机 rollout 和 UCB 置信上界来平衡探索与利用，在离散动作空间中高效地寻找近似最优策略。
前置依赖
- 强化学习基础（MDP、Bellman 方程）
- 统计学基础（置信区间、假设检验）
- 世界模型的概念
- 2-MPC - MPC 轨迹优化
- 1-Model-based RL总览
核心思想
MCTS 的核心思想是通过增量式地构建搜索树来解决大规模序贯决策问题。与 MPC 的轨迹优化不同，MCTS 构建状态-动作树的显式结构，利用统计置信区间指导搜索：
MCTS 的四个核心步骤：
- Selection：从根节点开始，用 UCB 公式选择子节点，直到到达叶节点
- Expansion：添加一个或多个子节点
- Simulation/Rollout：从新节点进行随机或heuristic rollout 直到终止
- Backup：将 rollout 结果反向传播更新路径上所有节点的统计量
与 MPC 的关键区别：
| 特性 | MPC | MCTS |
|---|---|---|
| 搜索结构 | 轨迹序列 | 树结构 |
| 动作空间 | 连续友好 | 离散为主 |
| 利用信息 | 模型 rollout | 树统计量 |
| UCB 使用 | 否 | 是 |
| 节点访问 | 隐式 | 显式计数 |
模型结构图
┌─────────────────────────────────────────────────────────────┐
│ MCTS 搜索树结构 │
├─────────────────────────────────────────────────────────────┤
│ │
│ (s_0, Q=∞) │
│ / | \ │
│ / | \ │
│ / | \ │
│ (a_0) (a_1) (a_2) │
│ / \ / \ / \ │
│ (s_1) (s_2) (s_3) (s_4) (s_5) (s_6) │
│ Q=0.5 Q=0.3 Q=0.8 Q=0.2 Q=0.6 Q=0.4 │
│ | | | | | | │
│ ... ... ... ... ... ... │
│ │
│ 选择时: UCB = Q(s,a) + c·√(lnN(s)/N(s,a)) │
│ 其中 N(s) 为状态访问次数, N(s,a) 为(s,a)对访问次数 │
└─────────────────────────────────────────────────────────────┘
数学推导
1. UCB (Upper Confidence Bound) 公式
MCTS 的 Selection 步骤使用 UCB 公式来平衡探索与利用：
其中：
：状态-动作对 的平均累积回报（ exploitation 项） ：状态 被访问的总次数 ：状态-动作对 被访问的次数 ：探索常数（通常 ）
推导背景（Bandit 框架）：
将每个
对于独立臂
在概率至少
取
UCB 的直观理解：
- 当
很小时，第二项很大，鼓励探索 - 当
接近 时，探索项消失，倾向 exploitation 控制探索强度： 越大越探索， 越小越利用
2. Q-value 的计算（Backup Operator）
设从节点
或者等价地，采用增量更新：
其中
对于有限 horizon 的 rollout：
3. 扩展策略 (Expansion Strategy)
叶节点选择标准：
何时扩展树取决于 UCB 的变体：
| 策略 | 描述 | 适用场景 |
|---|---|---|
| Best-first | 总是选择 UCB 最大的节点 | 标准 MCTS |
| Robust-first | 选择未被充分探索的节点优先 | 探索敏感任务 |
| RAVE (Rapid Action Value Estimation) | 考虑所有 visit 过的动作 | 围棋等结构化问题 |
单臂扩展 vs 多臂扩展：
- 单臂扩展（AlphaGo 风格）：每步只添加一个子节点
- 多臂扩展：同时添加所有可达子节点
4. MCTS 与 MPC 的对比
| 维度 | MCTS | MPC |
|---|---|---|
| 搜索结构 | 显式树 | 隐式轨迹集合 |
| 动作空间 | 离散/可数 | 连续（通过 CEM） |
| 时间复杂度 | ||
| 内存占用 | ||
| 利用信息 | 历史统计量 | 模型 rollout |
| 收敛性 | UCB 理论保证 | CEM 启发式 |
| 适用领域 | 游戏、离散控制 | 机器人、连续控制 |
5. 世界模型如何启用 MCTS 规划
在 Model-based MCTS 中，世界模型
Standard MCTS（无模型）：
- 需要与真实环境交互获取
- 每次评估需要真实 rollout，开销大
Model-based MCTS（有模型）：
- 使用
模拟转移 - 可以快速批量 rollout
- 模型误差可能导致错误分支被错误利用
Model-based MCTS 流程：
1. 初始化根节点 s_0，构建空树
2. 重复 N 次模拟：
Selection: 从根开始，选择 UCB 最大的 (s,a) 直到到达叶节点 L
Expansion: 如果 L 不是终止节点：
- 使用世界模型预测 L 的所有子节点 s' = f(L, a)
- 为 L 添加一个或多个子节点
Simulation: 从新节点使用世界模型进行 rollout：
- 随机或启发式选择动作
- 模型 roll out 直到终止或 horizon
- 计算累计回报 G
Backup: 反向传播更新 Q(s,a):
- Q(s,a) = (Q(s,a)*N(s,a) + G) / (N(s,a)+1)
- N(s,a) += 1
- N(s) += 1
3. 返回根节点处 Q 值最高的动作
训练细节
MCTS 的在线学习特性
MCTS 的一个关键特性是天然支持 online/in-batch learning：
- 无需预训练：可以直接从空白树开始搜索
- 渐进式增长：树随搜索次数增加而扩展
- 自适应的搜索深度：根据问题难度自动调整
与深度学习的结合
AlphaGo Zero 的创新：
- 用 CNN 预测
和 替代随机 rollout - 用 MCTS 生成的
作为 policy 的训练目标 - 自我对弈产生新数据，迭代训练
Loss 函数：
关键超参数
| 参数 | 典型值 | 影响 |
|---|---|---|
| 探索常数 | 探索-利用平衡 | |
| 搜索次数 | 100-10000 | 规划质量 |
| Rollout horizon | 终止或固定 H | 计算开销 |
| 每次扩展节点数 | 1 或全部 | 树宽度 |
推理/rollout/planning 过程
MCTS 的完整算法流程
class MCTSNode:
def __init__(self, state, parent=None, action=None):
self.state = state
self.parent = parent
self.action = action
self.children = {} # action -> MCTSNode
self.N = 0 # visit count
self.Q = 0.0 # action value
def mcts_search(root_state, world_model, n_simulations=1000, c=1.414):
"""MCTS 主循环"""
root = MCTSNode(root_state)
for _ in range(n_simulations):
node = root
# Selection: 下降直到未扩展节点
while node.children:
node = select_best_child(node, c)
# 检查是否需要 expansion
if not is_terminal(node) and len(node.children) < get_action_dim():
expand(node, world_model)
# Simulation: rollout from selected node
rollout_state = node.state
G = rollout(rollout_state, world_model, horizon=50)
# Backup: 反向传播
while node:
node.N += 1
if node.parent:
# 更新 Q-value
node.Q = node.Q + (G - node.Q) / node.N
node = node.parent
return get_best_action(root)
def select_best_child(node, c):
"""UCB 选择"""
best_score = -float('inf')
best_child = None
for action, child in node.children.items():
ucb_score = child.Q + c * np.sqrt(np.log(node.N) / (child.N + 1e-10))
if ucb_score > best_score:
best_score = ucb_score
best_child = child
return best_child
def expand(node, world_model):
"""扩展子节点"""
for a in get_valid_actions(node.state):
next_state = world_model.predict(node.state, a)
node.children[a] = MCTSNode(next_state, parent=node, action=a)
def rollout(state, world_model, horizon):
"""随机 rollout"""
for _ in range(horizon):
if is_terminal(state):
break
action = random_action(state)
state = world_model.predict(state, action)
return compute_return(state)树停止条件
| 条件 | 描述 |
|---|---|
| 固定迭代次数 | 执行 N 次模拟 |
| 时间预算 | 达到时间限制 |
| 收敛检测 | Q 值变化小于阈值 |
| 节点数限制 | 树大小达到内存限制 |
优点与局限
优点
- 无模型时也有效：可直接用于无模型问题
- 无需假设连续性：适用于离散/结构化问题
- 树结构可视化：决策过程可解释
- 并行友好：各次模拟相互独立
- 理论保证：UCB 有收敛性证明
局限
- 维度灾难：树宽度随时空指数增长
- 连续动作处理困难：需要 discretization 或 parametric action
- 内存占用：大状态空间可能无法存下整棵树
- Rollout 方差：随机 rollout 方差大，需要多次平均
与前后内容的衔接
- 前置：2-MPC - MPC 轨迹优化方法
- 后置：4-value-based planning - 基于价值的规划方法
- 关联：在 AlphaGo/AlphaZero 中，MCTS 与深度学习 policy/value network 结合
可复现实现要点
import numpy as np
from collections import defaultdict
class MCTS:
def __init__(self, world_model, action_space, c=1.414,
n_simulations=1000, rollout_horizon=50):
self.world_model = world_model
self.action_space = action_space
self.c = c # exploration constant
self.n_simulations = n_simulations
self.rollout_horizon = rollout_horizon
# 统计量
self.Q = defaultdict(float) # (state, action) -> Q value
self.N = defaultdict(int) # (state, action) -> visit count
self.N_state = defaultdict(int) # state -> visit count
def search(self, state):
"""从给定状态开始搜索，返回最优动作"""
for _ in range(self.n_simulations):
self._simulate(state)
# 选择访问次数最多的动作
best_action = max(self.action_space,
key=lambda a: self.N[(state, a)])
return best_action
def _simulate(self, state):
"""执行一次 MCTS 模拟"""
path = []
s = state
# Selection: UCB 下降
while True:
valid_actions = self.action_space
if len(valid_actions) == 0:
break
# 计算所有动作的 UCB
ucb_scores = []
for a in valid_actions:
q = self.Q[(s, a)]
n = self.N[(s, a)]
n_s = self.N_state[s] + 1e-10
ucb = q + self.c * np.sqrt(np.log(n_s) / (n + 1e-10))
ucb_scores.append((a, ucb))
# 选择 UCB 最高的动作
best_a, _ = max(ucb_scores, key=lambda x: x[1])
s_next = self.world_model.predict(s, best_a)
path.append((s, best_a))
s = s_next
# 如果是新状态，停止 selection
if self.N_state[s] == 0:
break
# Rollout
G = self._rollout(s)
# Backup
for s_node, a_node in path:
self.N[(s_node, a_node)] += 1
self.N_state[s_node] += 1
self.Q[(s_node, a_node)] += (G - self.Q[(s_node, a_node)]) / self.N[(s_node, a_node)]
def _rollout(self, state):
"""随机 rollout 计算回报"""
G = 0
gamma = 1.0
s = state
for _ in range(self.rollout_horizon):
a = np.random.choice(self.action_space)
s = self.world_model.predict(s, a)
r = self.world_model.reward(s, a)
G += gamma * r
gamma *= 0.99
return G章节摘要
MCTS 是一种基于树搜索的规划方法，通过 UCB 公式平衡探索与利用，在离散动作空间中构建搜索树并进行增量式扩展。与 MPC 的轨迹优化相比，MCTS 显式维护树结构，利用节点访问统计量指导搜索，避免了轨迹优化的局部最优问题。UCB 公式是 MCTS 的核心，
关键词
MCTS, Monte Carlo Tree Search, UCB, Upper Confidence Bound, exploration vs exploitation, tree search, backup, expansion, rollout, AlphaGo, selection, simulation, model-based planning