# Graph Constrained Reinforcement Learning for Natural Language Action Spaces

arXiv: https://arxiv.org/abs/2001.08837 · HTML: https://mlsanity.com/paper/2001.08837/

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 30 of 80)

- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022)
- [Is Reinforcement Learning (Not) for Natural Language Processing: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization](https://mlsanity.com/paper/2210.01241/) (2022)
- [Do the Rewards Justify the Means? Measuring Trade-Offs Between Rewards and Ethical Behavior in the MACHIAVELLI Benchmark](https://mlsanity.com/paper/2304.03279/) (2023)
- [SwiftSage: A Generative Agent with Fast and Slow Thinking for Complex Interactive Tasks](https://mlsanity.com/paper/2305.17390/) (2023)
- [A Survey on Large Language Model-Based Game Agents](https://mlsanity.com/paper/2404.02039/) (2024)
- [AriGraph: Learning Knowledge Graph World Models with Episodic Memory for LLM Agents](https://mlsanity.com/paper/2407.04363/) (2024)
- [CLIN: A Continually Learning Language Agent for Rapid Task Adaptation and Generalization](https://mlsanity.com/paper/2310.10134/) (2023)
- [What Would Jiminy Cricket Do? Towards Agents That Behave Morally](https://mlsanity.com/paper/2110.13136/) (2021)
- [Can Language Models Serve as Text-Based World Simulators?](https://mlsanity.com/paper/2406.06485/) (2024)
- [On Transforming Reinforcement Learning by Transformer: The Development Trajectory](https://mlsanity.com/paper/2212.14164/) (2022)
- [Aligning to Social Norms and Values in Interactive Narratives](https://mlsanity.com/paper/2205.01975/) (2022)
- [Learning Knowledge Graph-based World Models of Textual Environments](https://mlsanity.com/paper/2106.09608/) (2021)
- [Interactive Natural Language Processing](https://mlsanity.com/paper/2305.13246/) (2023)
- [Can Large Language Models Play Text Games Well? Current State-of-the-Art and Open Questions](https://mlsanity.com/paper/2304.02868/) (2023)
- [Introspective Tips: Large Language Model for In-Context Decision Making](https://mlsanity.com/paper/2305.11598/) (2023)
- [Multi-Stage Episodic Control for Strategic Exploration in Text Games](https://mlsanity.com/paper/2201.01251/) (2022)
- [Monte Carlo Planning with Large Language Model for Text-Based Game Agents](https://mlsanity.com/paper/2504.16855/) (2025)
- [Pre-trained Language Models as Prior Knowledge for Playing Text-based Games](https://mlsanity.com/paper/2107.08408/) (2021)
- [Reading and Acting while Blindfolded: The Need for Semantics in Text Game Agents](https://mlsanity.com/paper/2103.13552/) (2021)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [A Systematic Survey of Text Worlds as Embodied Natural Language Environments](https://mlsanity.com/paper/2107.04132/) (2021)
- [Inherently Explainable Reinforcement Learning in Natural Language](https://mlsanity.com/paper/2112.08907/) (2021)
- [Training Value-Aligned Reinforcement Learning Agents Using a Normative Prior](https://mlsanity.com/paper/2104.09469/) (2021)
- [A Survey of Text Games for Reinforcement Learning informed by Natural Language](https://mlsanity.com/paper/2109.09478/) (2021)
- [Goal-Directed Story Generation: Augmenting Generative Language Models with Reinforcement Learning](https://mlsanity.com/paper/2112.08593/) (2021)
- [TextWorldExpress: Simulating Text Games at One Million Steps Per Second](https://mlsanity.com/paper/2208.01174/) (2022)
- [Learning to Follow Instructions in Text-Based Games](https://mlsanity.com/paper/2211.04591/) (2022)
- [TextQuests: How Good are LLMs at Text-Based Video Games?](https://mlsanity.com/paper/2507.23701/) (2025)
- [Modeling Worlds in Text](https://mlsanity.com/paper/2106.09578/) (2021)
- [Generalization in Text-based Games via Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2109.09968/) (2021)

## Abstract (arXiv)

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.