Abstract
Interactive Fiction games are text-based simulations in which an agent interacts with the world purely through natural language. They are ideal environments for studying how to extend reinforcement learning agents to meet the challenges of natural language understanding, partial observability, and action generation in combinatorially-large text-based action spaces. We present KG-A2C, an agent that builds a dynamic knowledge graph while exploring and generates actions using a template-based action space. We contend that the dual uses of the knowledge graph to reason about game state and to constrain natural language generation are the keys to scalable exploration of combinatorially large natural language actions. Results across a wide variety of IF games show that KG-A2C outperforms current IF agents despite the exponential increase in action space size.
Introduction
Interactive Fiction (IF) games, such as the classic Zork, represent a significant frontier for Reinforcement Learning (RL). Unlike traditional environments with discrete, low-dimensional action spaces, IF agents must navigate world states and generate actions entirely through natural language. This presents three primary challenges:
- Combinatorial Action Spaces: A simple command in Zork1 can be drawn from a vocabulary of hundreds of words, leading to over $10^{14}$ possible combinations per step.
- Partial Observability: Agents must maintain a mental model of the world based solely on textual descriptions.
- Common Sense Reasoning: Success often requires understanding implicit logical relationships (e.g., "keys open doors").
Methodology: The KG-A2C Architecture
The Knowledge Graph Advantage Actor-Critic (KG-A2C) agent addresses these challenges by integrating a dynamic knowledge representation into the RL loop.
The architecture consists of several key components:
- Dynamic Knowledge Graph (KG): The agent extracts (subject, relation, object) triples from text using Open Information Extraction (OpenIE), building a persistent memory of the game world.
- Graph Attention Networks (GAT): A GAT processes the KG into a vector representation, allowing the agent to attend to relevant spatial and object-oriented information.
- Template-Based Action Decoder: To manage the action space, the agent first selects a template (e.g.,
take [OBJ]) and then populates the slots with objects identified in the KG. - Graph Masking: This is the central innovation. The agent uses the KG to "mask" actions involving objects it has not encountered or does not possess, effectively pruning the search space to contextually valid commands.
Experimental Results
The researchers evaluated KG-A2C across 28 human-made IF games using the Jericho framework. Performance was compared against the Template-DQN (TDQN) baseline.
As shown in the results, KG-A2C matched or outperformed the baseline in 23 out of 28 games. In Zork1, KG-A2C reached a score of 34 significantly faster than previous methods. Ablation studies (removing the graph mask or GAT) demonstrated that structural world knowledge is essential for efficient exploration; without these components, convergence was slower and final scores were lower.
Discussion and Conclusion
KG-A2C demonstrates that a Knowledge Graph can serve a dual purpose: as a memory aid for reasoning about state and as a structural constraint for natural language generation. By framing action generation as a retrieval problem constrained by a KG, the agent avoids the "hallucination" issues common in pure language models.
While successful, limitations remain, particularly regarding long-term dependencies in complex puzzles and the noise inherent in automated KG construction. Future work may involve integrating external common-sense knowledge bases like ConceptNet to further enhance the agent's understanding of object properties and world logic.
Summary updated