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

We appreciate your recognition of our work and your valuable feedback. We hope the following responses address your concerns.

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

A1: Thank you for your question. Below, we provide detailed explanations of the prompt components, and specific examples will be presented in the Appendix.

Trajectory: We define a trajectory as the sequence of observation-action pairs from the initial root node up to a terminal node in the search tree. Formally, it is represented as: $\tau = \left( o_0, a_0, o_1, a_1, \ldots, o_T, a_T, o_{T+1} \right)$. Here $T$ denotes the final time step before reaching the terminal observation $o_{T+1}$.

The trajectory terminates when the search process either:

• Reaches the maximum allowed depth, or
• Encounters a game victory or death.

In our method, we specifically select trajectories that lead to game death to generate reflections.

In-Trial Memory: The in-trial memory is a sequence of recent observation-action pairs within a small time window in the current trial. It is defined as: $\left( o_{t-1}, a_{t-1}, o_t \right)$ . This sequence represents the immediate history leading up to the current state at time t.

Cross-Trial Memory: The cross-trial memory consists of reflections from previous trials, up to a maximum of $k$ reflections. In our experiments, we set $k = 3$. A reflection is a brief statement summarizing the reason for the previous rollout's failure, such as: "Moving down into the dark place without a light source or any other items to help navigate."

Q2: Additional baselines could be included in the experimental results...

A2: Thank you for your suggestions. We have included these baselines into our experiments. For MPRC-DQN, RC-DQN, and Bike+CBR, we use similar settings to ensure a fair comparison. However, the LDTs baseline operates under a different setup as it requires an additional input—a Goal—at each step. This Goal is learned from offline trajectories collected from the environment. The direct comparison with LDTs would therefore be inequitable.

The table compares our MC-DML approach with selected baselines, excluding the game ztuu due to infinite reward loop issues reported in baseline papers. Our method outperforms MPRC-DQN and RC-DQN across all games, with significant gains in challenging games like zork1 and deephome, and achieves state-of-the-art results on 5 games compared to BiKE+CBR. We will include these baselines in the revised version of the paper.

Q3: Do you take into account the next step rewards (when present) during the MCTS? If so, how? If not, why not?

A3: Yes, the next-step rewards are taken into account during the MCTS. Specifically, the algorithm calculates the cumulative reward by combining the immediate reward from the current action and the discounted rewards from future steps. These cumulative rewards are then used to update the Q-value of the action node, which is computed as a softmax-weighted sum of accumulated rewards.

Q4: ...Considering the input limitations of LLMs, do you compress the trajectories?

A4: Thank you for your question. In the case of in-trial memory, which represents a very short time window, it naturally stays within the context length limit as it includes only the most recent observations and actions. However, trajectories, which consist of sequences of state-action pairs over time, can become lengthy. To ensure they fit within the token limit, we compress them when necessary by using a truncation function. If the trajectory exceeds the maximum token limit, the function discards the earliest information while retaining the most recent information.

We appreciate your recognition of our work and your valuable feedback. Below, we provide detailed responses to your questions.

Q1: Can you apply this idea for other MCTS-RL frameworks?

A1: Yes, our approach can be extended to other MCTS-RL frameworks. The core concept lies in leveraging a dynamically memory-guided LLM in conjunction with the exploratory properties of tree search. In our work, the LLM functions as a policy network, guiding MCTS to search more effectively by generating dynamic action probability distributions. This enables the search process to concentrate on the most promising actions. Furthermore, the LLM can be adapted to evaluate the value of state nodes, providing value estimates for each node. Incorporating value estimation would improve the accuracy of node evaluations while reducing reliance on extensive simulations. Additionally, within an RL framework, the integration of the LLM and MCTS can facilitate data augmentation, generating more training samples for RL algorithms and further enhancing their performance.

Q2: Can you apply this idea for other tasks which require planning, such as robot task completion, complex math problem solving, etc.?

A2: Thank you for your question. The MC-DML algorithm we propose is applicable to other planning tasks, especially in environments with large-scale state-action spaces. The core components of our method—the integration of LLMs for heuristic guidance and reflection, and the use of the PUCT algorithm for efficient search—are not limited to natural language inputs or outputs.

In other planning tasks, states and actions can be represented in structured formats such as key observation sequences and discrete, tokenized actions. These representations can be fed to LLMs for processing and evaluation. Additionally, prompts and memory mechanisms can be tailored to meet the specific requirements of the target tasks. For example, in chess, chess positions and moves can be converted into textual descriptions, allowing effective policies to be learned from them [1]. Similarly, in robotic planning, LLMs can assist in understanding complex instructions or environmental descriptions, while MCTS is used to explore optimal action sequences.

We chose text-based games as our environments primarily because of their challenges, such as sparse rewards and the need for long-term planning. Future research could explore the potential of MC-DML across diverse planning tasks and RL environments beyond text-based games.

[1] Feng X, Luo Y, Wang Z, et al. ChessGPT: bridging policy learning and language modeling[C]//Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023: 7216-7262.

References

[1] Zhao Z, Lee W S, Hsu D. Large language models as commonsense knowledge for large-scale task planning[C]//Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023: 31967-31987.

[2] Yao S, Yu D, Zhao J, et al. Tree of thoughts: deliberate problem solving with large language models[C]//Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023: 11809-11822.

[3] Hao S, Gu Y, Ma H, et al. Reasoning with language model is planning with world model[J]. arXiv preprint arXiv:2305.14992, 2023. Zhou A, Yan K, Shlapentokh-Rothman M, et al. Language agent tree search unifies reasoning acting and planning in language models[J]. arXiv preprint arXiv:2310.04406, 2023.

[4] Shinn N, Cassano F, Gopinath A, et al. Reflexion: language agents with verbal reinforcement learning[C]//Thirty-seventh Conference on Neural Information Processing Systems.

Q1: There is no comparison to LLM + MCTS baselines, which seems to be the most relevant.

A1: Thank you for your question. In our ablation study, we evaluated the performance of MC-DML without cross-memory (refer to Table 3, "MC-DML w.o. Mc​, DP"), which aligns with the setup of the LLM-MCTS approach [1]. While LLM-MCTS demonstrates strong performance in commonsense reasoning tasks, our experimental results indicate that MC-DML achieves superior performance in text-based games.

Q2: Given that combining LLMs and MCTS has been well studied in both text-based games and other RL setups, the contribution of this paper might be relatively limited.

A2: Thank you for raising this point. While combining LLMs and MCTS has been explored in previous studies, our work offers a distinct contribution. We appreciate the opportunity to elaborate on the distinctions.

Environment Complexity: Previous studies, such as Tree of Thought [2], Reasoning via Planning [3], and Language Agent Tree Search [4], primarily focus on relatively simple environments like Game of 24 and Blocksworld. In contrast, our study addresses environments with larger state spaces and highly branched structures. For instance, in the Zork1 game, the state space undergoes combinatorial explosion due to factors such as player location and task progress. The valid actions in each state can reach up to dozens. These environments demand both extensive exploration and long-term reasoning.

Methodological Differences: Previous studies have utilized LLMs as agents to iteratively generate reasoning paths, leveraging search-based methods to navigate these paths. While effective in simpler environments, this approach falls short in addressing the complexity of the environments in our study. LLMs often struggle to align their generated reasoning with executable actions and lack the ability to effectively balance exploration and exploitation. Even when provided with predefined executable actions, their performance remains constrained (as in our baseline ''LLM agent''). In contrast, our framework incorporates the PUCT algorithm and integrates LLMs as a prior policy to guide the search process, enhancing its capability to address these challenges.

Q3: Have you done ablation studies to study the impact of choosing k in the cross-trial memory? Why would 3 reflections be sufficient?

A3: Thank you for your question. In our experiments, we observed that the choice of k is closely linked to the complexity of the game. For games with multiple traps, a larger k may be required, whereas simpler games can perform well with a smaller k. Rather than fine-tuning k for each game, we adopted the setup from Reflection [4], selecting k=3. This approach strikes a balance by enabling multiple reflections while maintaining manageable experimental costs.

Q4: How would the proposed method work in other RL setups beyond text-based games?

A4: Thank you for your question. The MC-DML algorithm we propose is applicable to other RL setups, especially in environments with large-scale state-action spaces. The core components of our method—the integration of LLMs for heuristic guidance and reflection, and the use of the PUCT algorithm for efficient search—are not limited to natural language inputs or outputs. In other RL environments, states and actions can be represented in structured formats such as key observation sequences and discrete, tokenized actions. These representations can be fed to LLMs for processing and evaluation. Similarly, in robotic planning, LLMs can assist in understanding complex instructions or environmental descriptions, while MCTS is used to explore optimal action sequences. Future research can explore the capabilities of MC-DML in a variety of RL environments beyond text-based games.

Q5: How would the quality of the LLM (for both action prediction, and reflection) impact the overall performance?

A5: Thank you for your question. We acknowledge that the in-context learning capabilities of different LLMs can affect action prediction and reflection. Existing studies have extensively explored the scaling laws in this area. We utilized GPT-3.5 as the backend model for our MC-DML approach in the experiments to demonstrate its effectiveness. This choice aligns with prior work such as LLM-MCTS [1], which also relied exclusively on the GPT-3.5 model.