概述
LATS（Language Agent Tree Search）是一种结合推理、行动和规划的框架，旨在增强语言模型（LM）的决策能力。此框架出自论文《Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models》。LATS 的设计关键点包括：
- 树搜索算法：LATS 使用蒙特卡罗树搜索（MCTS）算法，通过平衡探索和利用，找到最优决策路径。
- LM 驱动的值函数：利用预训练的语言模型评估状态并生成反馈，指导搜索过程。
- 环境反馈：通过与外部环境交互获取反馈，增强模型的适应性和问题解决能力。
蒙特卡罗方法
蒙特卡罗方法简介
蒙特卡罗（Monte Carlo）方法是一种通过随机采样模拟来求解问题的方法。这种方法最早在 20 世纪 40 年代的“曼哈顿”计划中被提出，用于研制原子弹。因为这种方法像在赌场中掷骰子一样，所以以蒙特卡罗这个赌城的名字命名。
蒙特卡罗方法通过生成随机数，建立概率模型，以解决难以通过其他方法解决的数值问题。它包括多个分支，如蒙特卡罗算法、蒙特卡罗模拟、蒙特卡罗过程和蒙特卡罗树搜索（如 AlphaGo 中使用的方法）。
蒙特卡罗方法应用：求定积分
蒙特卡罗方法的一个典型应用是求定积分。假设我们要计算函数 f(x) 在[a, b]之间的积分，即阴影部分面积。
蒙特卡罗方法的解法如下：在[a, b]之间取一个随机数 x，用 f(x)⋅(b−a) 来估计阴影部分的面积。为了提高估计精度，可以取多个随机数 x，然后取这些估计值的平均值作为最终结果。
当取的随机数 x 越多，结果将越准确，估计值将越接近真实值。
蒙特卡罗树搜索
蒙特卡罗树搜索（MCTS）是一种基于树结构的蒙特卡罗方法。它在整个 2^N（N 为决策次数，即树深度）空间中进行启发式搜索，通过反馈机制寻找最优路径。MCTS 的五个主要核心部分是：
- 树结构：每一个叶子节点到根节点的路径都对应一个解，解空间大小为 2^N。
- 蒙特卡罗方法：通过随机统计方法获取观测结果，驱动搜索过程。
- 损失评估函数：设计一个可量化的损失函数，提供反馈评估解的优劣。
- 反向传播线性优化：采用反向传播对路径上的所有节点进行优化。
- 启发式搜索策略：遵循损失最小化原则，在整个搜索空间上进行启发式搜索。
MCTS 的每个循环包括四个步骤：
- 选择（Selection）：从根节点开始，按照最大化某种启发式价值选择子节点，直到到达叶子节点。使用上置信区间算法（UCB）选择子节点。
- 扩展（Expansion）：如果叶子节点不是终止节点，扩展该节点，添加一个或多个子节点。
- 仿真（Simulation）：从新扩展的节点开始，进行随机模拟，直到到达终止状态。
- 反向传播（Backpropagation）：将模拟结果沿着路径反向传播，更新每个节点的统计信息。
LATS 工作流程
Language Agent Tree Search (LATS) 是一种将推理、行动和规划统一在语言模型中的通用框架。其工作流程包括以下步骤：
- 选择 (Selection)：从根节点开始，使用上置信区树 (UCT) 算法选择具有最高 UCT 值的子节点进行扩展。
- 扩展 (Expansion)：通过从预训练语言模型 (LM) 中采样 n 个动作扩展树，环境接收每个动作并返回反馈，增加 n 个新子节点。
- 评估 (Evaluation)：为每个新子节点分配一个标量值，以指导搜索算法前进。LATS 通过 LM 生成的评分和自一致性得分设计新的价值函数。
- 模拟 (Simulation)：扩展当前选择的节点直到达到终端状态，优先选择最高价值的节点。
- 回溯 (Backpropagation)：根据轨迹结果更新树的值，路径中的每个节点的值被更新以反映模拟结果。
- 反思 (Reflection)：在遇到不成功的终端节点时，LM 生成自我反思，总结过程中的错误并提出改进方案。这些反思和失败轨迹在后续迭代中作为额外上下文整合，帮助提高模型的表现。
