Graph Constrained Reinforcement Learning for Natural Language Action Spaces

Prithviraj Ammanabrolu, Matthew J. Hausknecht

Introduction

In traditional Reinforcement Learning (RL), agents typically choose from a small, discrete set of actions (e.g., "move left," "jump"). However, in Interactive Fiction (IF)—text-based games like Zork—the agent interacts with the world purely through language. This introduces a massive "combinatorial explosion" of natural language action spaces.

The challenge is two-fold:

  1. Combinatorial Action Spaces: If an agent can type any five-word command from a modest 700-word vocabulary, it faces $1.64 \times 10^{14}$ possible actions at every single step. Most of these are nonsensical (e.g., "eat sword north blue mailbox").
  2. Partial Observability: Unlike Chess or Atari, the agent doesn't see the whole "board." It only knows what the text describes. It must remember that a trophy case is in the living room even after it has moved to the kitchen.

Existing agents have struggled to scale because they couldn't effectively prune this near-infinite "haystack" of nonsense to find the "needle" of a useful command. To solve this, researchers have developed KG-A2C, a reinforcement learning agent that uses dynamic knowledge graphs to build a mental map of its environment and mask out impossible actions, allowing it to efficiently explore complex text-adventures.

Methods: The KG-A2C Architecture

The authors introduce KG-A2C (Knowledge Graph Advantage Actor-Critic). The underlying architecture uses Graph Attention Networks (GATs) to process the knowledge graph and an Advantage Actor-Critic (A2C) framework to learn the policy.

The KG-A2C architecture

The system relies on three main innovations to navigate the massive action space:

  • Dynamic Knowledge Graph (KG): As the agent explores, it uses Open Information Extraction (OpenIE) to parse text descriptions into "triples" (e.g., subject-relation-object like sword-is in-trophy case). This graph serves as the agent's persistent memory of the world state. To handle interactive objects, things the agent can directly see or hold are linked to a "you" node in the graph, creating a clear distinction between immediate surroundings and distant memories.
Example of a dynamic knowledge graph
  • Template-Based Action Space: Instead of generating raw words, the agent first picks a template (e.g., put [ ] in [ ]) and then fills the blanks with objects it has encountered. This reduces the action space from trillions to a more manageable—but still large—115 million.
  • The Graph Mask: This is the core breakthrough of the paper. The agent uses its Knowledge Graph to create a mask that restricts the action decoder. If the KG doesn't contain a "sword," the agent isn't allowed to try to "take sword." This forces the agent to only attempt actions involving objects it actually knows exist, dramatically speeding up exploration.

Key Results and Insights

The agent was evaluated using the Jericho framework, a suite of 28 human-made Interactive Fiction games including classics like Zork1, Enchanter, and Library, which vary widely in difficulty, genre, and vocabulary size.

  • State-of-the-Art Performance: KG-A2C matched or outperformed the previous leading baseline (Template-DQN) on 23 out of 28 games.
  • Scaling Success: In Zork1, KG-A2C achieved a score of 34, reaching a local optimum where it collects most of the rewards available before the game's first major combat encounter.
  • Structure over Raw Power: The paper demonstrates that even with a massive increase in the theoretical action space (six orders of magnitude larger than previous models), providing the agent with the right structural constraints (templates + KG masks) leads to better performance than simpler models working in smaller, restricted spaces.
  • Ablation Clarity: Removing the "Graph Mask" significantly slowed down learning. Without the mask, the agent spent too much time "babbling"—trying actions that were grammatically correct but physically impossible given the current state.

Limitations and Future Work

While KG-A2C represents a significant leap forward, several challenges remain:

  • Parsing Errors: The system relies on OpenIE to build the graph. If the game uses flowery or metaphorical language, the parser might fail to extract accurate triples, leading to a corrupted mental map.
  • The "Valid Action" Handicap: During training, the agent still relies on a "valid action" list provided by the game engine to calculate certain loss terms. An entirely "unsupervised" version of the agent failed to achieve any score, suggesting that truly tabula rasa language learning remains an open challenge.
  • Commonsense Reasoning: While the KG helps with memory, the agent still lacks thematic knowledge (e.g., knowing that a "lantern" provides "light"). Integrating external commonsense knowledge bases, like ConceptNet, is a promising next step for future iterations.

Summary updated

Abstract

We present KG-A2C, a reinforcement learning agent that builds a dynamic knowledge graph while exploring and generates natural language using a template-based action space - outperforming all current agents on a wide set of text-based games.
BibTeX
@inproceedings{ammanabrolu2020graph,
  author = {Prithviraj Ammanabrolu and Matthew J. Hausknecht},
  title = {{Graph Constrained Reinforcement Learning for Natural Language Action Spaces}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=1c1VPQXnigQ},
}
Figure