Source-linked AI summary
Playing Text-Adventure Games with Graph-Based Deep Reinforcement Learning
Prithviraj Ammanabrolu, Mark O. Riedl
TL;DR
Text-adventure agents must act from partial textual observations despite a combinatorially large natural-language action space. The paper uses a learned knowledge graph for action pruning and question-answering pretraining for action selection; KG-DQN converges faster without loss of quest-solution quality.
Problem
Text-adventure agents must infer hidden world state from textual observations and choose among a combinatorially large set of natural-language actions.
Source: §3.2 · p. 3Method
KG-DQN learns a knowledge graph to prune actions and uses question-answering pretraining to predict appropriate actions from state observations.
Source: §1 · pp. 1–2, §4 · p. 5Results
KG-DQN converges faster without loss of quest-solution quality, and converges 40% faster than baseline on the small game.
Source: §6 · pp. 7–8Takeaways & Limitations
KG-DQN makes efficient-action knowledge explicit in the graph and retrieves it with graph attention, unlike LSTM-DQN's cell-state representation.
Source: §6 · p. 8Question-answering alone cannot solve text-adventure play; some trial and error remains necessary.
Source: §7 · p. 9
Abstract
from arXiv · showhide
Text-based adventure games provide a platform on which to explore reinforcement learning in the context of a combinatorial action space, such as natural language. We present a deep reinforcement learning architecture that represents the game state as a knowledge graph which is learned during exploration. This graph is used to prune the action space, enabling more efficient exploration. The question of which action to take can be reduced to a question-answering task, a form of transfer learning that pre-trains certain parts of our architecture. In experiments using the TextWorld framework, we show that our proposed technique can learn a control policy faster than baseline alternatives. We have also open-sourced our code at https://github.com/rajammanabrolu/KG-DQN.
1 Introduction
Text adventures challenge agents to act from incomplete observations using a combinatorially large natural-language action space. The paper proposes a learned knowledge graph and KG-DQN, with question-answering pretraining, to prune actions and accelerate learning.
1 Introduction
- Agents must infer the world from incomplete textual descriptions and past interactions, while expressing actions through natural-language commands in a combinatorially large action space.Text adventures are also presented as a stepping stone toward real-world settings where agents communicate to understand and affect the world.Source: §1 · p. 1
- A knowledge graph represents state and relationships among entities, supports action-space pruning, and provides persistent memory that helps identify actions to avoid.The graph gives the agent a prior notion of unsuitable actions at a particular game stage.Source: §1 · p. 1
- KG-DQN estimates state-action Q-values using graph embeddings, attention over relevant graph portions, and natural-language action inputs.The architecture learns which graph portions to attend to given an input state description.Source: §1 · pp. 1–2
- Question-answering pretraining frames action selection as answering what to do in a situation and transfers knowledge from different games.The paper reports that pretraining certain network components with existing question-answering methods improves performance.Source: §1 · p. 2
- KG-DQN converges to the highest reward more than 40% faster than the best baseline, while question-answering pretraining achieves high-quality quest solutions measured by completion steps.The introduction reports the result from ablative experiments comparing the knowledge-graph approach with strong baselines.Source: §1 · p. 2
2 Related Work
Prior text-game agents encode observations or state and actions, while action-elimination methods reduce exploration; knowledge graphs have also aided language understanding beyond games.
2 Related Work
- Narasimhan et al. (2015) score verbs and argument objects from an LSTM observation encoding, while He et al. (2016) use DRRN to score encoded states and actions.Neither method conditions on previous observations or prunes the action space, which can waste trials on low-value pairs in large spaces.Source: §2 · p. 2
- Haroush et al. (2018) use emulator feedback to train an Action Eliminating Network that restricts each state to its top-k likely actions, but it is not conditioned on previous observations.Their work reports that reducing the action space enables more effective exploration and better performance.Source: §2 · p. 2
- Guan et al. (2018) use ConceptNet features and graph attention to improve story-ending prediction; the paper builds on such graph methods while addressing ineffective exploration and limited long-term context.The paper describes its state representation and action pruning as combining strengths of existing approaches while avoiding those shortcomings.Source: §2 · p. 2
3 Knowledge Graph DQN
Section 3 presents a learned knowledge-graph representation, graph-based action pruning, and a Q-learning architecture for text-game control.
3.1 Knowledge Graph Representation
- The agent builds an RDF-triple world graph from observations, augments OpenIE with inferences, and updates agent links after each action while retaining inventory and other relations.Hand-crafted rules link rooms to items and exits and encode room transitions.Source: §3.1 · pp. 2–3
3.2 Action Pruning
- With action counts growing as O(|V| × |O|^2), the graph ranks actions by object presence and directed paths, then retains the top-k, assuming at most two objects per action.Source: §3.2 · p. 3
3.3 Model Architecture and Training
- Graph attention embeds the graph using third-order neighbors, while an SB-LSTM encodes the observation; their vectors are combined into the state representation.Source: §3.3 · p. 4
- The model encodes pruned action strings with an LSTM and estimates Q-values from state and action representations.Source: §3.3 · p. 4
- Training combines Q-learning with positive-reward-prioritized replay and ϵ1, ϵ2 exploration, which sometimes samples unpruned actions when pruning may exclude quest-critical actions.Source: §3.3 · pp. 3–5
4 Game Play as Question Answering
The section frames action selection as a question-answering problem and uses offline pre-training to teach an agent to answer from text observations. Because generated games vary in configuration and quests, this approach is intended to transfer QA competence rather than memorize quests.
4 Game Play as Question Answering
- The agent can treat each game situation as the question “What is the right action to perform?” while still requiring exploration during play.The authors hypothesize this framing may reduce testing-time exploration and allow faster quest completion.Source: §4 · p. 5
- An oracle generates optimal state–action traces, which train DrQA encoders to predict actions from text observations and initialize components of the KG-DQN architecture.The pre-training transfers SB-LSTM weights and embedding weights into the game-playing model.Source: §4 · p. 5
- Generated games share a domain but vary in world configuration and quests, so pre-training must support general QA competence rather than quest memorization.The paper characterizes this as a form of transfer learning.Source: §4 · pp. 5–6
5 Experiments
The experiments use procedurally generated TextWorld games of two difficulty levels to evaluate KG-DQN, its ablations, and baselines. They assess reward convergence and post-training quest completion, alongside pre-training QA accuracy and human performance.
5 Experiments
- Small games have ten rooms and quests of length five, while large games have twenty rooms and quests of length ten.Quest length counts required actions; additional actions may be needed to navigate and find objects.Source: §5 · p. 6
- TextWorld rewards actions that move the agent closer to quest completion with +1, penalizes actions that extend the minimum required steps with -1, and assigns 0 otherwise.Maximum rewards are 5 for small games and 10 for large games; maximum reward can still accompany varied quest quality.Source: §5 · p. 6
- The QA pre-training evaluation reports Exact Match, precision, recall, and F1, with token-based metrics and Exact Match requiring the full predicted answer to match.Training, development, and held-out sets contain 160, 20, and 20 generated games, respectively.Source: §5 · p. 6, Table 2 · p. 6
- The comparison includes random-command, LSTM-DQN, and Bag-of-Words DQN baselines, with randomized grid search for the latter two baseline configurations.The grid search selects their hyperparameters.Source: §5 · p. 6
- KG-DQN variants isolate un-pruned actions with pre-training, pruned actions without pre-training, and the full pruned, pre-trained model.The agent does not receive TextWorld's initial quest instructions or its list of admissible actions.Source: §5 · pp. 6–7
- Models are evaluated by time to reward convergence and average steps to finish games after training, with ε = 0.1 over five episodes and results averaged across five trials.The non-zero ε reflects that quest completion requires exploration.Source: §5 · p. 7
- Human performance is measured by steps to finish, with one condition providing quest instructions and another providing none.Human players also receive score feedback, using the same reward function as the agents.Source: §5 · p. 7
6 Results and Discussion
KG-DQN converges faster than the baselines on both small and large games, while quest-step results indicate that full KG-DQN retains solution quality. The results also compare agent performance with human players under different instruction conditions.
6 Results and Discussion
- Uninstructed human players completed no quests and gave up after averages of 184 steps on the small map and 190 on the large map; instructed players averaged 23 steps on the large map.The oracle requires five steps on the small map and 10 on the large map, though the paper notes that this ideal is impossible given the quest structure.Source: §6 · p. 7
- KG-DQN converges faster than baselines on both map sizes; it is 40% faster on the small game, while LSTM-DQN takes more than 300 episodes to reach KG-DQN’s level on the large game.Neither approach reaches the large-game maximum reward of 10; on the small game, both reach the maximum reward of five.Source: §6 · pp. 7–8, Figure 3 · p. 8, Figure 4 · p. 8
- Full KG-DQN requires an equivalent number of quest-completion steps to LSTM-DQN on both games, with no statistically significant difference (p = 0.199).Unpruned and non-pre-trained KG-DQN require many more steps; the authors conclude QA pre-training helps select good actions on an unseen final test game.Source: §6 · p. 8, Table 3 · p. 8, Table 4 · p. 8
7 Conclusions
The conclusions attribute faster reward convergence to knowledge graphs as persistent memory, while noting that faster convergence alone does not guarantee high-quality quest solutions. QA-based pre-training and graph-based action pruning are associated with shorter quest action sequences, but exploration remains necessary.
7 Conclusions
- Knowledge graphs provide persistent memory that reduces training time, but reaching optimal reward does not ensure a high-quality quest solution.The authors speculate that persistent memory of the explored world explains faster convergence.Source: §7 · p. 8
- Action pruning and pre-training embeddings yield shorter quest action sequences, while QA pre-training frames each step as selecting what is most important to try.The paper describes this pre-training as transfer learning from different but related games.Source: §7 · p. 8
- Question-answering alone cannot solve text-adventure play because trial and error is still required.The paper presents text-adventure games as a stepping stone toward more complex real-world tasks involving partial understanding through communication and language-based action.Source: §7 · p. 9