Monte Carlo Planning with Large Language Model for Text-Based Games
Large language model;Monte Carlo tree search;Text-based games
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
- 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.?
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.
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.
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.
Yes
No ethics review needed.
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?
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.
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.
**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.
@inproceedings{
anonymous2024monte,
title={Monte Carlo Planning with Large Language Model for Text-Based Games},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=r1KcapkzCt},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Large language model Monte Carlo tree search Text-based games
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/333d529e6cb1d9e5cdf16280e6aa8e3f760a8f02.pdf
foundation or frontier models, including LLMs
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Monte Carlo Planning with Large Language Model for Text-Based Games
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission