2019

Action Assembly: Sparse Imitation Learning for Text Based Games with Combinatorial Action Spaces

Tessler, Chen, Zahavy, Tom, Cohen, Deborah et al.

Understand

We propose a computationally efficient algorithm that combines compressed sensing with imitation learning to solve text-based games with combinatorial action spaces.

Specifically, we introduce a new compressed sensing algorithm, named IK-OMP, which can be seen as an extension to the Orthogonal Matching Pursuit (OMP).
We incorporate IK-OMP into a supervised imitation learning setting and show that the combined approach (Sparse Imitation Learning, Sparse-IL) solves the entire text-based game of Zork1 with an action space of approximately 10 million actions given both perfect and noisy demonstrations.

Built on

Reinforcement learning: An introduction , volume 1
Richard S Sutton and Andrew G Barto · 1998
Earlier work this paper cites.
Lectures on modern convex optimization: analysis, algorithms, and engineering applications , volume 2
Ahron Ben-Tal and Arkadi Nemirovski · 2001
Earlier work this paper cites.
Atomic decomposition by basis pursuit
Scott Shaobing Chen, David L Donoho, and Michael A Saunders · 2001
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Ronen I Brafman and Moshe Tennenholtz · 2002
Earlier work this paper cites.
Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization
David L Donoho and Michael Elad · 2003
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Error correction via linear programming
Emmanuel Candes, Mark Rudelson, Terence Tao, and Roman Vershynin · 2005
Earlier work this paper cites.
Decoding by linear programming
Emmanuel J Candes and Terence Tao · 2005
Earlier work this paper cites.
A swapping-based refinement of orthogonal matching pursuit strategies
Miroslav Andrle and Laura Rebollo-Neira · 2006
Earlier work this paper cites.
Stable recovery of sparse overcomplete representations in the presence of noise
David L Donoho, Michael Elad, and Vladimir N Temlyakov · 2006
Earlier work this paper cites.

Similar

Gradient pursuits
Thomas Blumensath and Mike E Davies · 2008
Cited alongside, same era.
Action assembly theory
John O Greene · 2008
Cited alongside, same era.
A fast iterative shrinkage-thresholding algorithm for linear inverse problems
Amir Beck and Marc Teboulle · 2009
Cited alongside, same era.
Iterative hard thresholding for compressed sensing
Thomas Blumensath and Mike E Davies · 2009
Cited alongside, same era.
Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain
Robert Calderbank, Sina Jafarpour, and Robert Schapire · 2009
Cited alongside, same era.
A plurality of sparse representations is better than the sparsest one alone
Michael Elad and Irad Yavneh · 2009
Cited alongside, same era.
Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing
Michael Elad · 2010
Cited alongside, same era.
Spectrum sensing for cognitive radio: State-of-the-art and recent advances
Erik Axell, Geert Leus, Erik G Larsson, and H Vincent Poor · 2012
Cited alongside, same era.
A k-best orthogonal matching pursuit for compressive sensing
P. Lin, S. Tsai, and G. C. . Chuang · 2013
Cited alongside, same era.
Convolutional neural networks for sentence classification
Original
Yoon Kim · 2014
Cited alongside, same era.

Then

Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Later among the works it cites.
Soft-feedback omp for the recovery of discrete-valued sparse signals
Susanne Sparrer and Robert FH Fischer · 2015
Later among the works it cites.
Deep reinforcement learning with a natural language action space
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf · 2016
Later among the works it cites.
Generating bags of words from the sums of their word embeddings
Lyndon White, Roberto Togneri, Wei Liu, and Mohammed Bennamoun · 2016
Later among the works it cites.
A compressed sensing view of unsupervised text embeddings, bag-of-n-grams, and lstms
Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, and Kiran Vodrahalli · 2018
Later among the works it cites.
Textworld: A learning environment for text-based games
Original
Marc-Alexandre Côté, Ákos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, et al · 2018
Later among the works it cites.
Towards solving text-based games by producing adaptive action spaces
Original
Ruo Yu Tao, Marc-Alexandre Côté, Xingdi Yuan, and Layla El Asri · 2018
Later among the works it cites.
Counting to explore and generalize in text-based games
Original
Xingdi Yuan, Marc-Alexandre Côté, Alessandro Sordoni, Romain Laroche, Remi Tachet des Combes, Matthew Hausknecht, and Adam Trischler · 2018
Later among the works it cites.
Learn what not to learn: Action elimination with deep reinforcement learning
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor · 2018
Later among the works it cites.
Using reinforcement learning to learn how to play text-based games
Original
Mikuláš Zelinka · 2018
Later among the works it cites.

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…