Monte Carlo Planning with Large Language Model for Text-Based Game Agents

本文提出MC-DML算法，通过整合大型语言模型的动态记忆机制与蒙特卡罗树搜索，提升文本-based游戏代理的规划效率和性能，实验结果显示其在初始阶段就优于需多次迭代的强基线。

Large Language Model, Reinforcement Learning, Reasoning, Planning, Agent, Human-AI Interaction

Zijing Shi, Meng Fang, Ling Chen

University of Technology Sydney, University of Liverpool

Generated by grok-3-mini-latest

Background Problem

文本-based游戏是研究自然语言处理（NLP）和顺序决策问题的宝贵环境，但它们具有有限的可观察性、动态状态空间和稀疏奖励等挑战。现有方法如结合蒙特卡罗树搜索（MCTS）和强化学习（RL）的规划-学习范式需要大量迭代，耗时长，而单纯的MCTS或RL方法缺乏语言理解和推理能力。大型语言模型（LLMs）虽有强大的语言能力和少样本学习能力，但难以平衡探索与利用，且在将计划转化为可执行动作方面存在困难。本文旨在通过整合LLMs与MCTS，解决这些问题，提高代理在文本-based游戏中的规划效率和性能。

Method

核心思想是提出MC-DML（Monte Carlo Planning with Dynamic Memory-guided Large Language Model）算法，结合LLMs的语言理解和推理能力与MCTS的探索优势。具体实现：在MCTS的四个阶段（选择、扩展、模拟、回传）中，使用LLMs作为先验策略，通过试内记忆（in-trial memory，包括当前轨迹历史）和试间记忆（cross-trial memory，包括过去失败轨迹的反思）动态调整行动评估。行动选择公式为：$a^* = \arg\max_{a \in \mathcal{A}} \left[ Q(s, a) + C_{pact} \cdot LLM(a|\mathcal{M}_i, \mathcal{M}_c, p) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)} \right]$ 主要步骤包括：初始化根节点，进行模拟选择行动、扩展树、进行回滚评估并更新Q值和访问计数。

Experiment

实验使用Jericho基准的9个文本-based游戏数据集，包括Zork1、Deephome等困难游戏和Pentari等可能游戏。实验设置包括与多种基线方法（如DRRN、KG-A2C-Hard、PUCT-RL、MC-LAVE-RL等）的比较，评估指标为游戏得分。MC-DML在初始规划阶段就显著提升性能，平均得分在多个游戏中优于基线，尤其在Deephome中 nearly double the performance of MC-LAVE-RL。消融实验证实了动态记忆机制和动态剪枝策略的重要性，结果符合预期，表明方法改进明显，实验设计全面合理。

Further Thoughts

本文的动态记忆机制为LLMs在交互式任务中的应用提供了新思路，例如可以扩展到机器人导航或多代理系统中，通过结合检索增强生成（RAG）技术改进长期记忆检索，解决”针在 haystack”问题；此外，与其他工作如Reflection或Tree-of-Thought的结合，可能进一步增强代理在不确定环境中的泛化能力，推动LLMs与强化学习的深度融合。