2020

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

Ammanabrolu, Prithviraj, Tien, Ethan, Hausknecht, Matthew et al.

Understand

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.

Built on

Comprehensible context-driven text game playing
Original
X. Yin and J. May · 1905
Earlier work this paper cites.
Learn how to cook a new recipe in a new house: Using map familiarization, curriculum learning, and common sense to learn families of text-based adventure games
Original
X. Yin and J. May · 1908
Earlier work this paper cites.
Interactive fiction games: A colossal adventure
Original
M. Hausknecht, P. Ammanabrolu, M.-A. Côté, and X. Yuan · 1909
Earlier work this paper cites.
Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning
R. S. Sutton, D. Precup, and S. Singh · 1999
Earlier work this paper cites.
Bringing stories alive: Generating interactive fiction worlds
Original
P. Ammanabrolu, W. Cheung, D. Tu, W. Broniec, and M. O. Riedl · 2001
Earlier work this paper cites.
Automatic discovery of subgoals in reinforcement learning using diverse density
A. McGovern and A. G. Barto · 2001
Earlier work this paper cites.
Learning options in reinforcement learning
M. Stolle and D. Precup · 2002
Earlier work this paper cites.
Leveraging Linguistic Structure For Open Domain Information Extraction
G. Angeli, J. Premkumar, M. Jose, and C. D. Manning · 2015
Earlier work this paper cites.
Language understanding for text-based games using deep reinforcement learning
K. Narasimhan, T. D. Kulkarni, and R. Barzilay · 2015
Earlier work this paper cites.
Increasing the action gap: New operators for reinforcement learning
M. G. Bellemare, G. Ostrovski, A. Guez, P. Thomas, and R. Munos · 2016
Earlier work this paper cites.

Similar

Deep reinforcement learning with a natural language action space
J. He, J. Chen, X. He, J. Gao, L. Li, L. Deng, and M. Ostendorf · 2016
Cited alongside, same era.
SQuAD: 100,000+ questions for machine comprehension of text
P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang · 2016
Cited alongside, same era.
What can you do with a rock? affordance extraction via word embeddings
N. Fulda, D. Ricks, B. Murdoch, and D. Wingate · 2017
Cited alongside, same era.
Textworld: A learning environment for text-based games
Original
M.-A. Côté, A. Kádár, X. Yuan, B. Kybartas, T. Barnes, E. Fine, J. Moore, M. Hausknecht, L. E. Asri, M. Adada, W. Tay, and A. Trischler · 2018
Cited alongside, same era.
BERT: pre-training of deep bidirectional transformers for language understanding
Original
J. Devlin, M. Chang, K. Lee, and K. Toutanova · 2018
Cited alongside, same era.
Counting to explore and generalize in text-based games
Original
X. Yuan, M. Côté, A. Sordoni, R. Laroche, R. T. des Combes, M. J. Hausknecht, and A. Trischler · 2018
Cited alongside, same era.
Learn what not to learn: Action elimination with deep reinforcement learning
T. Zahavy, M. Haroush, N. Merlis, D. J. Mankowitz, and S. Mannor · 2018
Cited alongside, same era.
Using reinforcement learning to learn how to play text-based games
Original
M. Zelinka · 2018
Cited alongside, same era.
Ledeepchef: Deep reinforcement learning agent for families of text-based games
Original
L. Adolphs and T. Hofmann · 2019
Cited alongside, same era.
Playing text-adventure games with graph-based deep reinforcement learning
P. Ammanabrolu and M. O. Riedl · 2019
Cited alongside, same era.
Transfer in deep reinforcement learning using knowledge graphs
P. Ammanabrolu and M. Riedl
Cited in the paper.

Then

Go-explore: a new approach for hard-exploration problems
Original
A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune · 2019
Later among the works it cites.
Learning norms from stories: A prior for value aligned agents
Original
S. Frazier, M. O. Al Nahian, Md Sultan Riedl, and B. Harrison · 2019
Later among the works it cites.
Algorithmic improvements for deep reinforcement learning applied to interactive fiction
Original
V. Jain, W. Fedus, H. Larochelle, D. Precup, and M. G. Bellemare · 2019
Later among the works it cites.
Learning to speak and act in a fantasy text adventure game
Original
J. Urbanek, A. Fan, S. Karamcheti, S. Jain, S. Humeau, E. Dinan, T. Rocktäschel, D. Kiela, A. Szlam, and J. Weston · 2019
Later among the works it cites.
Interactive language learning by question answering
X. Yuan, M.-A. Côté, J. Fu, Z. Lin, C. Pal, Y. Bengio, and A. Trischler · 2019
Later among the works it cites.
Learning dynamic knowledge graphs to generalize on text-based games
Original
A. Adhikari, X. Yuan, M.-A. Côté, M. Zelinka, M.-A. Rondeau, R. Laroche, P. Poupart, J. Tang, A. Trischler, and W. L. Hamilton · 2020
Closest in time.
Graph constrained reinforcement learning for natural language action spaces
P. Ammanabrolu and M. Hausknecht · 2020
Closest in time.
Albert: A lite bert for self-supervised learning of language representations
Z. Lan, M. Chen, S. Goodman, K. Gimpel, P. Sharma, and R. Soricut · 2020
Closest in time.
Exploration based language learning for text-based games
Original
A. Madotto, M. Namazifar, J. Huizinga, P. Molino, A. Ecoffet, H. Zheng, A. Papangelis, D. Yu, C. Khatri, and G. Tur · 2020
Closest in time.
Enhancing text-based reinforcement learning agents with commonsense knowledge
Original
K. Murugesan, M. Atzeni, P. Shukla, M. Sachan, P. Kapanipathi, and K. Talamadupula · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…