# How to Avoid Being Eaten by a Grue: Structured Exploration Strategies for Textual Worlds

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

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

- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (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)
- [AriGraph: Learning Knowledge Graph World Models with Episodic Memory for LLM Agents](https://mlsanity.com/paper/2407.04363/) (2024)
- [Do Embodied Agents Dream of Pixelated Sheep: Embodied Decision Making using Language Guided World Modelling](https://mlsanity.com/paper/2301.12050/) (2023)
- [LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models](https://mlsanity.com/paper/2311.18232/) (2023)
- [What Would Jiminy Cricket Do? Towards Agents That Behave Morally](https://mlsanity.com/paper/2110.13136/) (2021)
- [On Transforming Reinforcement Learning by Transformer: The Development Trajectory](https://mlsanity.com/paper/2212.14164/) (2022)
- [Learning Knowledge Graph-based World Models of Textual Environments](https://mlsanity.com/paper/2106.09608/) (2021)
- [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)
- [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)
- [A Framework for Learning to Request Rich and Contextually Useful Information from Humans](https://mlsanity.com/paper/2110.08258/) (2021)
- [Modeling Worlds in Text](https://mlsanity.com/paper/2106.09578/) (2021)
- [TALES: Text Adventure Learning Environment Suite](https://mlsanity.com/paper/2504.14128/) (2025)
- [Knowledge-enhanced Agents for Interactive Text Games](https://mlsanity.com/paper/2305.05091/) (2023)
- [Multi-Turn Puzzles: Evaluating Interactive Reasoning and Strategic Dialogue in LLMs](https://mlsanity.com/paper/2508.10142/) (2025)
- [Situated Dialogue Learning through Procedural Environment Generation](https://mlsanity.com/paper/2110.03262/) (2021)
- [Case-based Reasoning for Better Generalization in Textual Reinforcement Learning](https://mlsanity.com/paper/2110.08470/) (2021)
- [Conceptual Reinforcement Learning for Language-Conditioned Tasks](https://mlsanity.com/paper/2303.05069/) (2023)
- [Dialogue Shaping: Empowering Agents through NPC Interaction](https://mlsanity.com/paper/2307.15833/) (2023)
- [STARLING: Self-supervised Training of Text-based Reinforcement Learning Agent with Large Language Models](https://mlsanity.com/paper/2406.05872/) (2024)
- [Story Shaping: Teaching Agents Human-like Behavior with Stories](https://mlsanity.com/paper/2301.10107/) (2023)
- [Large Language Models Think Too Fast To Explore Effectively](https://mlsanity.com/paper/2501.18009/) (2025)
- [Thespian: Multi-Character Text Role-Playing Game Agents](https://mlsanity.com/paper/2308.01872/) (2023)
- [Learning to Play Like Humans: A Framework for LLM Adaptation in Interactive Fiction Games](https://mlsanity.com/paper/2505.12439/) (2025)
- [Learning to Query Internet Text for Informing Reinforcement Learning Agents](https://mlsanity.com/paper/2205.13079/) (2022)

## Abstract (arXiv)

Text-based games are long puzzles or quests, characterized by a sequence of sparse and potentially deceptive rewards. They provide an ideal platform to develop agents that perceive and act upon the world using a combinatorially sized natural language state-action space. Standard Reinforcement Learning agents are poorly equipped to effectively explore such spaces and often struggle to overcome bottlenecks---states that agents are unable to pass through simply because they do not see the right action sequence enough times to be sufficiently reinforced. We introduce Q*BERT, an agent that learns to build a knowledge graph of the world by answering questions, which leads to greater sample efficiency. To overcome bottlenecks, we further introduce MC!Q*BERT an agent that uses an knowledge-graph-based intrinsic motivation to detect bottlenecks and a novel exploration strategy to efficiently learn a chain of policy modules to overcome them. We present an ablation study and results demonstrating how our method outperforms the current state-of-the-art on nine text games, including the popular game, Zork, where, for the first time, a learning agent gets past the bottleneck where the player is eaten by a Grue.