MCTS 规划

MCTS (Monte Carlo Tree Search, 蒙特卡洛树搜索) 用树搜索做顺序决策规划,循环四步:选择 (按 UCT 公式 $UCT = \bar{v} + c\sqrt{\frac{\ln N}{n}}$ 平衡探索与利用,$N$ 为父节点访问次数、$n$ 为子节点访问次数)、扩展 (生成新分支)、模拟 (rollout 到叶子)、回溯 (叶子价值沿路径回传)。在经典 RL 中,节点价值来自策略-价值网络:AlphaGo/AlphaZero 用自我对弈数据迭代改进策略,或来自学到的世界模型 (MuZero 在潜空间内做 MCTS,见本模块 muzero 卡)。

RL 视角: 在 LLM 推理场景,节点 = 已生成的部分推理步骤,动作 = 下一步生成,节点价值由 PRM/验证器评分提供,用于推理时搜索 (test-time compute) 与 RL 高质量轨迹生成。详见 LLM 模块: 完整定义与考点见 LLM 模块的 mctsSearch 卡 (id: mcts-search)。

游戏与规划 (AlphaZero 系列)、与学到的模型结合做潜在空间规划 (MuZero)、推理模型的推理时扩展与 RL 训练数据生成。

贪心/单路径决策"一条路走到黑",一步出错不可回溯且错误沿路径传播;MCTS 以多路径探索 + 价值引导剪枝在决策期寻找更优轨迹,显著提升困难任务的成功率。

MCTS 四步 (选择/扩展/模拟/回溯) 分别做什么?写出 UCT 公式及符号含义?

MCTS 与策略-价值网络如何结合 (AlphaGo/AlphaZero 自我对弈范式)?

LLM 推理中 MCTS 的节点、动作、价值分别如何定义?为什么用 PRM 做价值?

MCTS 与简单多次采样 (best-of-N) 的计算复杂度与收益对比?

MuZero 如何在潜空间内做 MCTS?与显式动态模型的区别?