LLM o1 中的蒙特卡洛树搜索算法，DeepSeek论文中提到
LLM o1 中的蒙特卡洛树搜索算法，DeepSeek论文中提到
凌青羽 2025年02月09日 09:30 上海
蒙特卡洛树搜索算法的核心是：选择与模拟。
蒙特卡洛树搜索算法的主要目标是：给定一个游戏状态来选择最佳的下一步。
前言
在讲解蒙特卡罗树算法之前，我们先玩一个“赌博”游戏。多臂老虎机（Multi-Armed Bandits)。
多臂老虎机（Multi-Armed Bandits)
游戏规则如下：赌博机有K个摇臂，每次摇动其中的任意一个摇臂，赌博机都会随机吐出一些硬币。现在允许你摇T次，请问如何尝试使得收益最大化。（有限次数的尝试的收益最大化）
思考一下，你会如何尝试？（是下面的玩法中的哪一种类型呢？）
• 纯随机(Random)：每次随机选一个摇臂进行摇动。
• 劣势：能算个期望收益，但收益不是最大的。
• 仅探索（Exploration-only)：每个摇臂摇动T/K次。
• 相当于每个摇臂摇动的次数都一样。(劣势：浪费次数在收益较差的摇臂上)
• 仅利用（Exploitation-only）： 首先对每个摇臂摇动一次，记录收益。随后对剩余的T-K次机会全部摇收益最大的摇臂。
• 劣势：摇动一次记录的收益随机性太强，不可靠）
上述 仅探索（Exploration-only) 与 仅利用（Exploitation-only）所带来的困境也称为 Exploration-Exploitation Dilemma。
为了克服该困境
其它可以尝试的解决算法为：
（1） -贪心算法：在探索与利用之间进行平衡的搜索算法
具体执行过程为，在第t步，-贪心算法按照如下机制来选择摇动赌博机：
• 以 的概率，选择在过去t-1次摇动赌博机所得平均收益最高的摇臂进行摇动；
• 以 的概率，随机选择一个摇臂进行摇动。
上述贪心算法的不足为没有充分的考虑到每个摇臂被探索的次数。
(2)上限置信区间算法（Upper Confidence Bounds, UCB）:为每个动作的奖励期望计算一个估计的范围，优先采用估计范围上限较高的动作。(也是蒙特卡洛树用到的算法）
假设每个摇臂的收益的均值为 ，估计的偏差为 ，则每次根据 的上界选择摇臂。
选择区间上界对应的摇臂
但如果仅根据 的上界选择摇臂，也没有充分考虑到每个摇臂被探索的次数。因此需要额外引入探索的次数的奖励。（即该节点被探索的越少，我们认为该节点越值得被探索），表示为：
其中j表示第j个摇臂， 表示第j个摇臂的平均收益，C为固定常数， 为截至目前摇动摇臂的总次数， 为第j个摇臂被摇动的次数。
然而，上述多摇臂赌博机每轮只需要做一次决策（即摇动哪根杆子），在一些更复杂的游戏中（例如下围棋、打文明6、打LOL），你的每一步决策都会影响到你的游戏的胜率，你最后的输赢取决于你所有的决策步骤。如何能依据当前的状态做好决策，对于游戏的输赢至关重要。
蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS）
概述
蒙特卡洛树搜索的目的就是选择最优决策。结合了随机模拟的通用性和树搜索的准确性。理论上，任何可以被用{State，Action}所定义且能通过模拟预测结果的问题，都可以用MCTS来解决。
MCTS的具体实现步骤如下图所示，主要包含4部分。
1. 选择 (Selection)
从根节点R开始，递归地选择最优子节点（通过UCB，后续节点选择展开讲解），直到到达叶子节点L。
2. 探索 (Expansion)
如果L不是终止节点（即它没有结束游戏），则创建一或多个子节点并从中随机选择一个子节点C进行探索。
3. 模拟/仿真 (Simulation、Rollout)
从C运行一个模拟的rollout，直到获得一个结果。（后续节点模拟会举例子展开讲解如何模拟）
4. 反传 (Backpropagation)
用模拟结果（终止节点的代价或游戏的终局分数）更新当前的移动序列，更新模拟路径中节点的奖励均值和被访问次数。注意，反传的过程中，每个节点必须包含两个重要的信息：基于模拟结果的估计值和它被访问的次数。
在完成了反向传播这一步，我们就会持续迭代，回到选择这一步，然后再进行探索仿真，然后再反向传播，再回到选择探索仿真，不断地迭代下去，直到算法结束并且给出最终决策。
在其最简单和最节省内存的实现中，MCTS将在每次迭代中添加一个子节点。不过，根据应用程序的不同，每次迭代添加多个子节点可能是有益的，这个需要通过实验来评估。
节点选择
和刚刚上面提到的赌博机类似，我们在树的递归选择最优子节点时，通常会选择预期收益最大的子节点。因此，我们可以利用上限置信区间算法（Upper Confidence Bounds, UCB）来选择子节点。
其中j表示第j个子节点， 表示第j个子节点的预期收益，C为固定常数， 为截至目前其父节点被访问到的总次数， 为第j个子节点被访问的次数。
可以看到UCB公式在利用已知奖励进行开发的同时，鼓励对未被充分探索的节点进行探索。由于预期收益的估计值基于随机模拟，因此节点必须被多次访问后，这些估计值才变得可靠；MCTS估计值在搜索的初期通常不可靠，但在足够的时间和无限的时间下，会趋向于更可靠的估计值。
在后续的研究中，Kocsis and Szepervari (2006)将UCB扩展到minimax 树搜索中，称之为Upper Confidence Bounds for Trees (UCT)。 UCT=MCTS + UCB。
节点模拟
从子节点C开始，运行一个模拟的输出，直到游戏结束。举个例子：例如说 五子棋，给你一个下到一半的残局（子节点C），让你和AI下十次（模拟十次），如果你赢了九次（获胜 9次），那么这个残局（子节点C）的奖励得分就会很高，反之则比较低。
更详细的示例在的Blog中有描述:
https://blog.csdn.net/qq_41033011/article/details/109034887[1]
LLM o1中的蒙特卡洛搜索树算法
GPT4-o1中（可能）有用到蒙特卡洛搜索树算法，可以在不训练模型的情况下，通过增加模型的推理时间，增强模型的推理性能。
本Blog所讲解的算法主要参考《Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B- A Technical Report》
MCT Self-Refine (MCTSr)
MCT Self-Refine算法将蒙特卡罗树搜索（MCTS）与大型语言模型（LLMs）结合。通过Self-reflective 驱动 Self-improvement来改进最终LLM输出的结果。
符号定义（建议参考论文原文）
符号 表示
• P 待解决的问题（Problem）
• A 一系列节点，每个节点表示问题P的潜在的答案
• M 一个set，存储每个节点上的一系列的actions，表示对于答案的可能的自我完善的修正
• R 一个function，可以通过对原始答案修改的质量和有效性来采样得到nodes的self-rewards。
• R_a 一个set，用于存储节点a中从函数R中得到的self-rewards的采样的结果。
• T 一个function，用于评估搜索过程是否达到了最大迭代次数或者满足性能需求。
• Q(a) 一个value function，用于评估节点a处的答案的价值；由累积的rewards R_a 和 从子节点中的反传结果得到。
• U(a) 一个function，用于得到节点a处的Q所对应的上限置信区间，用于平衡探索和利用阶段，避免Exploration-Exploitation Dilemma。
• Father(a) 一个function，用于返回节点a的父节点。如果节点a已经是父节点，则返回 null。
• Children(a) 一个function，用于返回节点a的所有的子节点的集合（set）。表示通过执行一系列actions m \in M，所得到的所有的可能的状态。
• N(a) 一个function，用于返回节点a被访问到的次数，用于计算UCB的值，评估被探索和被利用的状态。本质上， N(a) = |R_a|
方法
MCTSr的方法是基于MCTS改进而来，其流程和MCTS很相似，但是结合了LLM：
1. 初始化（Initialization）
建立根节点，即用LLM生成的初始答案或预设响应（如‘I don't know’）构造。来最小化模型过拟合的趋势。
2. 选择（Selection）
为了进一步的探索，利用函数Q来对所有未被探索到的节点的答案进行价值排序。随后选择价值最高的节点进行进一步探索，并且用贪心算法进行细化。
3. Self-Refine
对被选择到的 答案a 进行自我优化。即通过用LLM生成答案反馈m，来指导LLM得到优化后的 答案a'
4. Self-Evaluation
对优化后的 答案a' 计算价值得分 Q。
5. 回传（Backpropagation）
对优化后的答案的价值得分进行回传到其父节点和其他的相关节点，来更新 树的信息。如果任意节点的Q值发生变化，其父节点的Q值也会随之改变。
6. UCT update
在所有节点的Q值被更新后，需要确定候选的节点集合用于进一步的探索和选择。我们需要使用UCT来更新所有节点的UCT值，用于下一次的选择（Selection）。
上述流程会不断迭代，直到满足函数T为止。（即达到最大迭代次数，或得到满意答案）
更多细节展开
• Self-Refine 阶段
在Self-Refine 阶段，模型在多轮对话的提示的引导下，对问题P的答案a进行优化。首先，模型对a产生反思性或批评性评论m。随后，在m的引导下，模型修改a，产生改进版本*a'。*这种迭代的Refine提高了响应的质量，利用结构化的反馈来驱动答案的修正。
• Self-Evaluation 阶段
在对问题P的精炼过程中，由于从答案a到其改写形式的答案a'的马尔可夫性质，我们将答案a的Q值定义为进一步将答案a精炼为更优答案的期望。不像传统的MCTS， Q（s, a）估计状态s中动作a的值，这里的Q(a)来自于答案a的奖励函数值的多个采样。
注意，模型利用 Self-reward 方法来 评估答案a的reward，因此需要提供一个 reward 分数，从 -100到100。如果在没有约束的情况下，模型的reward可能会趋向一个均值，导致不同的答案之间缺乏差异性，为了解决这个问题，对Self-reward方法加了一些约束：
1. Prompt 约束： LLM被要求严格遵循Prompt，来得到reward scoring
2. 满分抑制 (Full Score Suppression)：模型被限制提交满分，任何超过95分的分数都会被减去一个常数，来限制高分
3. 重复采样 (Repeated Sampling)：通过对被选择的节点进行重复采样，来增强Self-Evaluation的可靠性。
完成采样后，需要对 答案a 计算 价值 Q。为了避免价值Q过于平滑，对其价值Q的计算加入一个 最小价值，来进一步提高答案的评估质量：
其中 Q(a)是对答案a 的 价值评估值。 是一系列由答案a 得到的 reward samples，min 表示最小的 reward。| | 是一共采样的数量。即通过多次采样和加上最小的reward值，来得到一个Q(a)均值。
• Backpropagation 阶段
在得到所有节点的rewards后，下一步需要将这些rewards反传回其父节点和相关的祖先节点。即可表示为：
其中，Q(a)是仅考虑其reward samples的原始Q值， 表示其一系列子节点的最高的Q值。
• UCT update 和 选择阶段
在完成对所有节点的Q的更新后，下一步是计算每个节点的UCT值，以方便下一轮的迭代与选择。作者利用数学问题优化过程的马尔可夫性质，选择所有叶节点和未完全扩展的节点作为候选集C。
然而，LLM产生的候选状态有很多，如何定义 未完全扩展？作者设置了两种完全扩展的约束：
1. 节点的子节点数量达到了预先定义好的限制。
2. 至少一个子节点Q的值超过了当前节点的Q值
确定候选集C后，如何来从中选择要探索的节点a，作者使用了UCT的公式：
其中 Q(a)表示节点a（答案a）的价值Q。N(·)表示节点a被访问的次数。c是常数，用来平衡 探索和利用困境。
● 停止阶段（函数T）
当搜索结果的改进减少或连续搜索产生重复结果时终止。一旦满足搜索结果，就可以从树中选择最佳答案。
参考与引用
引用链接
[1] https://blog.csdn.net/qq\_41033011/article/details/109034887:https://blog.csdn.net/qq_41033011/article/details/109034887\
[2]https://www.geeksforgeeks.org/ml\-monte\-carlo\-tree\-search\-mcts/:https://www.geeksforgeeks.org/ml-monte-carlo-tree-search-mcts/
[3]https://www.lamda.nju.edu.cn/guolz/introai\-slides/lec4\.pdf:https://www.lamda.nju.edu.cn/guolz/introai-slides/lec4.pdf
[4]https://blog.csdn.net/qq\_41033011/article/details/109034887:https://blog.csdn.net/qq_41033011/article/details/109034887\
[5]https://www.cs.swarthmore.edu/\~mitchell/classes/cs63/f20/reading/mcts.html:https://www.cs.swarthmore.edu/~mitchell/classes/cs63/f20/reading/mcts.html
[6]https://arxiv.org/pdf/2406\.07394:https://arxiv.org/pdf/2406.07394
[7] https://zhuanlan.zhihu.com/p/9644482549
