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

Authors: Zijing Shi, Meng Fang, Ling Chen
Primary area: foundation or frontier models, including LLMs
Keywords: Large language model, Monte Carlo tree search, Text-based games

Abstract:
Text-based games provide valuable environments for language-based autonomous agents. However, planning-then-learning paradigms, such as those combining Monte Carlo Tree Search (MCTS) and reinforcement learning (RL), are notably time-consuming due to extensive iterations. Additionally, these algorithms perform uncertainty-driven exploration but lack language understanding and reasoning abilities.
In this paper, we introduce the Monte Carlo planning with Dynamic Memory-guided Large language model (MC-DML) algorithm. MC-DML leverages the language understanding and reasoning capabilities of Large Language Models (LLMs) alongside the exploratory advantages of tree search algorithms. Specifically, we enhance LLMs with in-trial and cross-trial memory mechanisms, enabling them to learn from past experiences and dynamically adjust action evaluations during planning. We conduct experiments on a series of text-based games from the Jericho benchmark. Our results demonstrate that the MC-DML algorithm significantly enhances performance across various games at the initial planning phase, outperforming strong contemporary methods that require multiple iterations. This demonstrates the effectiveness of our algorithm, paving the way for more efficient language-grounded planning in complex environments.

Decision: accept (poster)
Reviewer scores: 5, 8, 8

Reviews and discussion:
<thread>
creation date:
1729799824680

thread_type:
official_review

<thread_object>
creator: reviewer_djd9

<content>
summary:
This paper introduces a new planning and learning algorithm called Monte Carlo with Dynamic Memory-guided Large language model (MC-DML). This method leverages the language understanding capabilities of LLMs and the exploratory advantages of tree search algorithms. The approach is similar to Predictor UCT: actions are selected based on the Q-value function plus a probability distribution over valid actions p(a|s). In this work, p(a|s) is not trained but produced by a prompted LLM. Applied to Jericho text-based games, GPT3.5 is used to generate p(a|s) at each game state based on both an in-trial memory (M_i = sequence of past observations & actions), and a cross-trial memory (M_c = a collection of LLM generated reflections based on previous failures). In addition, the Monte Carlo search used in this work applies dynamic pruning to save search time and favor exploration.
Experimental results on 9 Jericho games show that MC-DML yields better performance when compared to RL-based, LLM-based, and other MCTS-based methods. Ablation studies show the importance of the cross-trial memory M_c.

strengths:
This paper proposes a novel method to combine the advantages of LLMs and tree-search algorithms. The idea of including both in-trial and cross-trial elements inside the decision-making process of choosing the next action is an interesting and effective technique that can inspire future work.
The paper is well written, the experiments correspond to the research questions, and are well motivated.

weaknesses:
**W1.** Some technical aspects are not always clear, see below and the list of questions for things to clarify.

The paper could benefit from a more detailed explanation of the way each LLM prompt is constructed. In particular what is inside the {TRAJECTORY}, {IN-TRIAL MEMORY}, and {CROSS-TRIAL MEMORY} variables. An example in the appendix could help the reader understand what information the LLM has access to when making its decision.
A discussion about how the lengthy game trajectories are handled could also clarify some technical aspects.

**W2.** The Jericho benchmark has been used in many previous works, additional baselines could be included in the experimental results to make them more significant.
In particular MPRC-DQN & RC-DQN from Guo et al. [1], Bike+CBR from Atzeni et al. [2], and LDTs from Gontier et al. [3]

[1] Guo, X., Yu, M., Gao, Y., Gan, C., Campbell, M., & Chang, S. (2020). Interactive fiction game playing as multi-paragraph reading comprehension with reinforcement learning. arXiv preprint arXiv:2010.02386

[2] Atzeni, M., Dhuliawala, S., Murugesan, K., & Sachan, M. (2021). Case-based reasoning for better generalization in textual reinforcement learning. arXiv preprint arXiv:2110.08470.

[3] Gontier, N., Rodriguez, P., Laradji, I., Vazquez, D., & Pal, C. (2023). Language Decision Transformers with Exponential Tilt for Interactive Text Environments. arXiv preprint arXiv:2302.05507.

questions:
Q1. Do you take into account the next step rewards (when present) during the Monte Carlo Tree Search? If so, how? If not, why not?

Q2. What is the average input token length of your two prompts? Given that they include trajectories, they may be longer than the 4191 context length limit of gpt3.5. Do you compress the trajectories in some way? Since states are made of the game state transition message + the description of the room + the description of inventory, sequences of (s, a) could become lengthy. For instance, consecutive room and inventory descriptions can be the same over multiple time steps if actions do not move the player or change its inventory.

Q3. Do you include the initial description of the game as part of the state? Often the opening message of the game will give valuable information about the goal/objective of the game.

Q4. When doing MCTS rollouts/simulations, how do you sample actions? Is it random or do you use an informed process during simulation as well?

Q5. Why did you select these 9 Jericho games? Could you report performance across all 33 games in the appendix?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730683619946

thread_type:
official_review

<thread_object>
creator: reviewer_jbdx

<content>
summary:
This is a neat paper combining well known MCTS with LLM memory. More specifically, MCTS will be guided by past failure trajectories as learned by the LLM. The idea is demonstrated in a number of text games.

strengths:
This is a neat and effective idea. It may also apply to other domains such as robot planning or math problem solving. It is still not clear how the formalism is incorporated into POMDP.

weaknesses:
The method requires the LLM to remember these failure trajectories. Long term memory can be one limitation, or for complex tasks it may be needed to do some sort of RAG to retrieve the relevant memory, and this can introduce noise.

questions:
- can you apply this idea for other MCTS-RL frameworks?
- can you apply this idea for other tasks which require planning, such as robot task completion, complex math problem solving, etc.?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730688267645

thread_type:
official_review

<thread_object>
creator: reviewer_zbkr

<content>
summary:
This paper introduces Monte Carlo planning with Dynamic Memory-guided Large language model (MC-DML) algorithm, which targets at bringing the language model understanding and reasoning capabilities into Monte Carlo Tree Search and RL. Specifically, the authors propose to add in-trial (which includes exploration and results in the current game), and cross-trial memory (which is reflections from previous experiences) into predictor UCT. Experimenting on 9 text-based games in Jericho benchmark, results show that the proposed MC-DML approach improve the performance over other RL-based, LLM-based, and MCTS-based approaches.

strengths:
1. This paper shows that adding LLM reasoning and planning capabilities, especially when augmenting with cross-trial reflections, can improve exploration performance in MCTS. This can be an interesting direction to study and may suggest good research results to people interested in how to make use of LLMs in RL exploration.
2. This paper compares to previous RL-based, LLM-based, and MCTS-based methods, and shows that when combining LLM with MCTS RL methods, we would benefit from stronger reasoning and planning capabilities.

weaknesses:
1. The main contribution in the proposed algorithm actually lies in introducing cross-trial reflection, as LLMs have been studies in the MCTS setup which is also mentioned by the authors. However, although the paper compares to LLM-based and MCTS-based baselines, there is no comparison to LLM + MCTS baselines, which seems to be the most relevant. 
2. Given that combining LLMs and MCTS has been well studies in both text-based games and other RL setups, the contribution of this paper might be relatively limited.

questions:
1. Have you done ablation studies to study the impact of choosing k in the cross-trial memory? Why would 3 reflection be sufficient?
2. How would the proposed method work in other RL setups beyond text-based games?
3. How would the quality of the LLM (for both action prediction, and reflection) impact the overall performance?
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents a more efficient way to do Monte Carlo planning in text games. It is well situated with respect to the literature on text game playing agents, especially those that already attempt to solve them via a mix of Deep RL and search+backtracking methods. The addition of LLMs has always been bottlenecked by the compute costs but the MC-DML could be a good answer to that. The results are also well presented and show a solid improvement over existing methods. Some of the exact implementation details are unclear from the paper itself and I'd encourage the authors to make the code for this work available if they can as that will allow for other papers to build on it - implementation details are critical for such methods especially.