Skip to content

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

🕒 Published (v1): 2025-01-01 · Source: ICLR · Venue: ICLR 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

MC-DML integrates LLMs as prior policies within MCTS for text-based game agents, augmenting them with dual memory mechanisms (in-trial and cross-trial) to dynamically adjust action probability estimates during tree search. The system outperforms strong MCTS+RL baselines that require multiple costly planning-then-learning iterations, achieving superior scores on the first planning pass alone.

Problem

Standard MCTS-based agents for text-based games (e.g., PUCT-RL, MC-LAVE-RL) require multiple expensive planning-then-learning iterations because their neural policy networks need warm-up from self-generated data. They also lack language understanding, making them blind to semantic meaning of game states and actions. Pure LLM agents, conversely, cannot balance exploration vs. exploitation and get stuck in bottleneck states requiring deferred rewards.

Method

MC-DML replaces the learned policy network in PUCT with an LLM, using it to produce a non-uniform prior π(a|s) over valid actions. The LLM receives two memory inputs at each selection step:

  • In-trial memory (Máµ¢): a short trailing window of (o_{t-1}, a_{t-1}, o_t) representing recent trajectory context, grounding the LLM in current game state.
  • Cross-trial memory (Mâ‚“): up to k=3 natural-language reflections generated by the LLM when a simulation reaches a terminal failure. Each reflection analyzes the failed trajectory and suggests behavioral corrections (e.g., "ensure you have a light source before entering dark areas").

Action selection uses the PUCT formula with the LLM policy: a* = argmax[Q(s,a) + C_puct · LLM(a|Mᵢ,Mₓ,p) · √(N(s)/1+N(s,a))]. Log-probabilities over the top 20 tokens from GPT-3.5-turbo are softmax-normalized (temperature 5) to form the prior. A dynamic pruning strategy adjusts search depth between d_min and d_max, increasing depth when max Q-value remains 0.

Key Contributions

  • MCTS algorithm that uses an LLM as the PUCT prior policy without any imitation learning or training iterations.
  • Dual memory architecture: short-term in-trial trajectory context + interpretable cross-trial reflections from failure episodes.
  • Demonstrated that cross-trial reflection enables an agent to escape bottleneck states where greedy semantic signals are misleading (e.g., choosing take lantern over open trapdoor despite the former yielding no immediate reward).
  • Dynamic depth pruning strategy that adapts tree search depth based on reward sparsity.

Results

  • On 9 Jericho benchmark games, MC-DML outperforms or matches RL-based baselines in 6/9 games and LLM/MCTS-based baselines in 8/9 games.
  • On Zork1: MC-DML scores 48.66 ± 1.89 at iteration 1 vs. MC-LAVE-RL's 45.2 ± 1.2 after 4 full iterations (each with 25 planning sessions + RL update).
  • On Deephome: 67 ± 1.41 vs. MC-LAVE-RL's 35 ± 0.6 — nearly 2× improvement.
  • Fully completes Pentari (70/70) and Detective (346.67/350 approx.) games.
  • Ablation: removing Mâ‚“ drops Zork1 from 48.66 to 38.33; removing both Mâ‚“ and Máµ¢ further drops to 31.67. Dynamic pruning is critical specifically for Ztuu (23.67 → 7.8 without it).

Limitations

  • In-trial memory is restricted to a short trailing window; puzzles requiring recall of items or clues from much earlier in the game stress the LLM's "needle-in-a-haystack" retrieval capacity.
  • Relies on GPT-3.5-turbo log-probability access; APIs without token probabilities require approximate workarounds (self-consistency or verbalized probability elicitation).
  • Cross-trial memory is capped at k=3 reflections per root node, which may be insufficient for highly complex games.
  • Valid-action handicap from the Jericho engine is assumed; performance under open action spaces is not evaluated.
  • No multi-iteration refinement means the system cannot recover from systematically wrong LLM priors the way RL-based baselines can over iterations.

Relevance to Agentic AI / LLM Agents

This work directly addresses a core challenge in LLM agent design: integrating structured search with language-grounded reasoning without expensive fine-tuning loops. The dual-memory pattern — short-term trajectory context plus persistent reflective episodic memory from failures — is a reusable architecture motif applicable to any sequential decision-making agent operating under partial observability. The Reflexion-inspired cross-trial memory shows how verbal reinforcement signals can substitute for gradient-based policy updates, pointing toward sample-efficient agents that improve within a single deployment episode. For researchers tracking agentic AI, MC-DML is a concrete existence proof that LLMs can replace learned value networks in tree search while adding language-grounded generalization that RL cannot provide without domain-specific features.