大模型---MCTS/LATS
目录
1.MCTS
（1）Selection
（2）Expansion
（3）Simulation
（4）Backpropagation
2.LATS（Language Agent Tree Search）
（1）Selection
（2）Expansion
（3）Evaluation
（4）Simulation
（5）Backpropagation
（6）Reflection
（7）与ReAct，ToT，Reflexion的区别
（8）LATS的缺点
3.MCTS与LATS的关系
1.MCTS
Monte Carlo Tree Search（MCTS）是一种启发式树搜索方法，核心思想是在搜索树上反复做采样，用有限预算把更多计算分配给“看起来更有希望”的分支。
MCTS 的一个迭代通常包含四步：Selection、Expansion、Simulation、Backpropagation。
其核心流程是从根节点按树策略往下选，到某个可扩展节点后扩一个子节点，再从那里做默认策略下的 rollout（不展开后续所有可能，而是用一次“试跑”来估计这个新节点的好坏）。最后把结果沿路径回传更新统计量。
（1）Selection
这一阶段从根节点开始，沿着当前树一直往下走，直到遇到：一个还没完全展开的节点，或者一个终止节点。因为 MCTS 的计算预算有限，不可能把所有分支都均匀展开。所以Selection会在现在这棵部分展开的树里，选择哪条路径最值得继续深入?
Selection中常用的策略是UCT，它的思想来自多臂老虎机里的UCB，把UCB的“探索-利用（explore and exploit）平衡”搬到了树搜索里（这部分会另讲）。
在树上选子节点时，UCT 不会只看“当前平均收益最高的是谁”，而是同时看：利用(exploit)，哪个节点历史表现更好；探索(explore)，哪个节点还没被充分尝试。
（2）Expansion
当Selection走到一个可扩展节点后，MCTS不会立刻停下，而是会从这个节点挑一个尚未尝试过的动作，把对应的新子节点加到树里。图里底部那个粗黑边框的新圆圈，就是这一步刚长出来的新节点。MCTS的策略不是BFS那种“一层层铺满”，而是渐进式增长，即，先少量扩展，边试边看结果，再把预算集中到更有前途的地方。
（3）Simulation
因为刚扩出的新节点，还没有多少统计信息。如果只看它当前位置，可能不知道它到底值不值得继续发展。于是就从这个点往下按默认策略尝试，看看最终结果怎样，把这个结果当作对当前节点质量的近似评估。
Simulation会从刚刚扩展出来的新节点出发，算法会继续往后尝试下去，直到到达终局，或者到达某个预设停止条件。但关键在于：这时候往后的过程通常不再显式加入搜索树，而是按某个default policy做一次rollout/playout。图里的虚线箭头就表示后面是在树外继续模拟，而不是把所有后继节点都正式画进树里。图中的三角形就表示这次rollout最后到了某个终止结果。
default policy就是rollout时用的“默认走法”。最简单的做法是随机选动作，但文献也强调，默认策略不一定非得随机，可以加入启发式或领域知识。MCTS的强弱，很大程度上取决于：① tree policy怎么选树内路径；② default policy怎么做树外模拟。
（4）Backpropagation
当Simulation得到终局结果后，MCTS会把这次结果沿着刚才那条路径往回传，一直传到根节点。也就是更新从根到扩展节点这一整条路径上的统计量。回传时通常会更新两个值：① 访问次数：这个节点被走到过多少次；② 价值统计：这个节点历史上平均结果怎么样。如果这次 rollout 结果很好，那么这条路径上的节点价值就会上升；如果结果很差，那么它们的统计值就会下降或变得不占优。
就这样，经过很多轮以后，树就会越来越偏向那些高回报且经过足够验证的分支，这就是 MCTS 能在有限预算下把计算集中到“有希望区域”的原因。即“树搜索的精确性+随机采样的通用性”的结合。
注意：Selection用的是tree policy，其只负责树里面怎么走。也就是在已经存在的节点之间，怎么选下一步。UCT属于tree policy；
Simulation用的是