Monte-Carlo Planning and Learning with Language Action Value Estimates

Youngsoo Jang, Seokin Seo, Jongmin Lee, Kee-Eung KimICLR 2021 · OpenReview

Interactive Fiction (IF) games, or text adventures, represent a "grand challenge" for artificial intelligence. Unlike board games such as Chess or Go, where moves are mathematically defined and constrained, IF games require an agent to process and generate natural language commands. This creates a massive combinatorial explosion: at any given moment, an agent might face hundreds of valid but useless actions.

Standard planning algorithms like Monte-Carlo Tree Search (MCTS) struggle in these environments because they are inherently "language-agnostic." They treat commands like "open mailbox" and "take sword" as arbitrary discrete tokens, failing to recognize that if "take sword" was useful previously, "take lantern" might be useful now. Consequently, agents often get stuck at "bottlenecks"—game states requiring a specific sequence of non-obvious actions to progress.

To address this, researchers have introduced Monte-Carlo planning with Language Action Value Estimates (MC-LAVE), a novel algorithm that allows AI agents to navigate complex action spaces by combining MCTS with semantic intuition.

Methodology: Injecting Semantic Intuition into Planning

The core innovation of MC-LAVE is how the agent decides which branches of the search tree to explore. It shifts away from blind exploration by leveraging the inherent "priors" found in natural language.

Overview of the MC-LAVE-RL architecture.

The system operates through four primary mechanisms:

  1. Credit Assignment via Q-Learning: The agent maintains a Q-network (based on the Deep Reinforcement Relevance Network architecture) that estimates the value of observation-action pairs based on past search experiences.
  2. Language Action Value Estimates (LAVE): When the agent encounters a new action, it evaluates its semantic neighborhood—other actions that are linguistically similar, calculated using the cosine similarity of pre-trained word embeddings. It then calculates an exploration bonus based on the known high-value actions within that neighborhood.
  3. Language-Driven Selection: The agent uses a modified version of the Predictor Upper Confidence Bound applied to Trees (PUCT) formula. Instead of exploring solely based on uncertainty, it adds the LAVE bonus to prioritize actions that "sound" like they should work based on past successes.
  4. MC-LAVE-RL: This planning mechanism is wrapped into a full Reinforcement Learning loop. The agent plans using MC-LAVE, then uses those successful trajectories to "teach" its policy network via behavioral cloning and its Q-network via TD-learning.

Key Insights

The most powerful idea behind MC-LAVE is semantic generalization. If an agent learns that "taking" an item generally leads to long-term progress, it can generalize that intuition to new, unseen items, drastically pruning the search space.

This semantic generalization helps overcome the "myopia" (short-sightedness) common in standard RL agents. For example, in the game Zork1, a player must take a lantern before entering a dark cellar to avoid being eaten by a grue. Taking the lantern yields 0 immediate points, while entering the cellar yields points. A standard, myopic agent will rush into the cellar and die. MC-LAVE, however, identifies the lantern's value through look-ahead planning and semantic prioritization, successfully navigating the bottleneck.

Through ablation studies, the researchers also identified a "sweet spot" for semantic similarity (denoted as $\delta$). If the semantic neighborhood is too small, the agent fails to generalize; if it is too large, the search becomes noisy as unrelated actions are lumped together.

Key Results

The researchers evaluated MC-LAVE using the Jericho framework, a suite of IF games categorized by difficulty.

Performance comparison of MC-LAVE-RL against baseline algorithms across Jericho games.

MC-LAVE-RL outperformed or matched state-of-the-art results on 8 out of 9 evaluated games:

  • Zork1: The agent achieved a new high score of 45.2, significantly beating the previous state-of-the-art (MC!Q*BERT at 41.6) and standard RL baselines (DRRN at 32.6).
  • Deephome: On highly difficult games like Deephome, MC-LAVE-RL demonstrated remarkable efficiency, scoring 35 compared to the previous best of 8.

Limitations and Future Work

While highly effective, MC-LAVE has limitations. Like most MCTS-based methods, it requires a "resettable" simulator—the ability to jump back to a previous state during planning. While trivial in a game engine, this is difficult to implement in real-world robotics or live dialogue systems. Furthermore, the method relies heavily on the quality of pre-trained word embeddings; if the embeddings fail to capture the specific nuances of a game's world, the semantic neighborhood logic can falter.

Future work may explore combining LAVE with more advanced state representations, such as Knowledge Graphs, to further enhance the agent's common-sense reasoning capabilities.

Summary updated

Abstract

Interactive Fiction (IF) games provide a useful testbed for language-based reinforcement learning agents, posing significant challenges of natural language understanding, commonsense reasoning, and non-myopic planning in the combinatorial search space. Agents based on standard planning algorithms struggle to play IF games due to the massive search space of language actions. Thus, language-grounded planning is a key ability of such agents, since inferring the consequence of language action based on semantic understanding can drastically improve search. In this paper, we introduce Monte-Carlo planning with Language Action Value Estimates (MC-LAVE) that combines a Monte-Carlo tree search with language-driven exploration. MC-LAVE invests more search effort into semantically promising language actions using locally optimistic language value estimates, yielding a significant reduction in the effective search space of language actions. We then present a reinforcement learning approach via MC-LAVE, which alternates between MC-LAVE planning and supervised learning of the self-generated language actions. In the experiments, we demonstrate that our method achieves new high scores in various IF games.
BibTeX
@inproceedings{jang2021monte,
  author = {Youngsoo Jang and Seokin Seo and Jongmin Lee and Kee-Eung Kim},
  title = {{Monte-Carlo Planning and Learning with Language Action Value Estimates}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=7_G8JySGecm},
}
Figure