Strategist: Self-improvement of LLM Decision Making via Bi-Level Tree Search

📄 arXiv: 2408.10635v3 📥 PDF

作者: Jonathan Light, Min Cai, Weiqin Chen, Guanzhi Wang, Xiusi Chen, Wei Cheng, Yisong Yue, Ziniu Hu

分类: cs.AI, cs.CL

发布日期: 2024-08-20 (更新: 2025-07-29)

备注: website: https://llm-strategist.github.io

💡 一句话要点

STRATEGIST：基于双层树搜索的LLM决策自提升方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 蒙特卡洛树搜索 强化学习 决策制定 自博弈 策略优化 双层搜索 部分信息博弈

📋 核心要点

  1. 现有强化学习方法需要大量数据训练，而LLM在复杂决策任务中表现不佳。
  2. STRATEGIST利用LLM搜索高层策略，再由MCTS细化执行，实现优势互补。
  3. STRATEGIST在GOPS和《抵抗组织：阿瓦隆》等游戏中超越传统RL和LLM方法，接近人类水平。

📝 摘要（中文）

传统的强化学习和规划通常需要大量的数据和训练才能开发有效的策略。相比之下，大型语言模型（LLM）表现出强大的泛化和零样本能力，但在复杂动作空间中需要详细规划和决策的任务中表现不佳。我们介绍STRATEGIST，一种新颖的方法，它整合了这两种方法的优势。我们的方法利用LLM来搜索和更新高层策略（以文本形式），然后通过低层蒙特卡洛树搜索（MCTS）进行细化和执行。STRATEGIST是一个通用的框架，可以通过基于种群的自博弈模拟来优化策略，而无需任何训练数据。我们证明了STRATEGIST在学习竞争性的、多回合、具有部分信息的游戏（包括纯策略游戏（GOPS）和多智能体、隐藏身份的讨论游戏，如《抵抗组织：阿瓦隆》）的最佳策略方面的有效性。我们的结果表明，配备STRATEGIST的智能体优于使用传统RL方法、其他基于LLM的技能获取技术以及预先存在的LLM智能体，并且在两种游戏环境中都达到了与人类玩家相当的性能。

🔬 方法详解

问题定义：论文旨在解决LLM在复杂决策任务中规划能力不足的问题。现有方法，如传统强化学习，需要大量训练数据，泛化能力有限。而直接使用LLM进行决策，在需要长期规划和复杂推理的场景下表现不佳，难以有效探索和利用策略空间。

核心思路：论文的核心思路是将LLM的泛化能力和MCTS的规划能力相结合。LLM负责生成和更新高层策略，MCTS负责在底层动作空间中进行搜索和优化。通过这种双层结构，可以有效地探索策略空间，并利用LLM的知识来指导搜索过程。

技术框架：STRATEGIST框架包含两个主要层次：高层策略搜索和低层动作执行。在高层，LLM维护一个策略池，并通过自博弈模拟不断更新策略。LLM根据当前游戏状态选择一个策略，并将其传递给低层。在低层，MCTS使用LLM提供的策略作为先验知识，进行蒙特卡洛树搜索，选择最佳动作执行。游戏结束后，根据结果更新LLM的策略池。

关键创新：STRATEGIST的关键创新在于将LLM和MCTS结合成一个双层框架，利用LLM的泛化能力来指导MCTS的搜索过程。与传统的RL方法相比，STRATEGIST不需要大量的训练数据，并且能够更好地泛化到新的游戏环境中。与直接使用LLM进行决策相比，STRATEGIST能够进行更深入的规划和推理。

关键设计：LLM使用文本描述策略，例如在《抵抗组织：阿瓦隆》中，策略可能包括“如果我是梅林，并且我知道A和B是坏人，那么我会指认A”。MCTS使用LLM提供的策略作为先验概率，指导搜索过程。论文使用基于种群的自博弈模拟来更新LLM的策略池，具体更新方式未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

STRATEGIST在GOPS和《抵抗组织：阿瓦隆》游戏中取得了显著成果。在GOPS中，STRATEGIST超越了传统RL方法和LLM基线。在《抵抗组织：阿瓦隆》中，STRATEGIST与人类玩家的性能相当，并在某些情况下超越了人类玩家。这些结果表明，STRATEGIST能够有效地学习复杂策略，并在竞争环境中取得优异表现。

🎯 应用场景

STRATEGIST框架具有广泛的应用前景，可以应用于各种需要复杂决策和规划的任务中，例如：机器人导航、游戏AI、自动驾驶、资源分配等。该方法能够有效利用LLM的知识和推理能力，提高决策效率和性能，尤其是在数据稀缺或环境复杂的场景下具有重要价值。未来，该方法有望进一步扩展到更广泛的领域，例如：医疗诊断、金融投资等。

📄 摘要（原文）

Traditional reinforcement learning and planning typically requires vast amounts of data and training to develop effective policies. In contrast, large language models (LLMs) exhibit strong generalization and zero-shot capabilities, but struggle with tasks that require detailed planning and decision-making in complex action spaces. We introduce STRATEGIST, a novel approach that integrates the strengths of both methods. Our approach leverages LLMs to search and update high-level strategies (as text), which are then refined and executed by low-level Monte Carlo Tree Search (MCTS). STRATEGIST is a generalizable framework to optimize the strategy through population-based self-play simulations without the need for any training data. We demonstrate the effectiveness of STRATEGIST in learning optimal strategies for competitive, multi-turn games with partial information, including Game of Pure Strategy (GOPS) and multi-agent, hidden-identity discussion games like The Resistance: Avalon. Our results show that agents equipped with STRATEGIST outperform those trained with traditional RL methods, other LLM-based skill acquisition techniques, pre-existing LLM agents across both game environments and achieves comparable performance against human players.