This work presents an exploration and imitation-learning-based agent capable of state-of-the-art performance in playing text-based computer games. Text-based computer games describe their world to the player through natural language and expect the player to interact with the game using text. These games are of interest as they can be seen as a testbed for language understanding, problem-solving, and language generation by artificial agents. Moreover, they provide a learning environment in which these skills can be acquired through interactions with an environment rather than using fixed corpora. 
 One aspect that makes these games particularly challenging for learning agents is the combinatorially large action space.
 Existing methods for solving text-based games are limited to games that are either very simple or have an action space restricted to a predetermined set of admissible actions. In this work, we propose to use the exploration approach of Go-Explore (Ecoffet et al., 2019) for solving text-based games. More specifically, in an initial exploration phase, we first extract trajectories with high rewards, after which we train a policy to solve the game by imitating these trajectories.
 Our experiments show that this approach outperforms existing solutions in solving text-based games, and it is more sample efficient in terms of the number of interactions with the environment. Moreover, we show that the learned policy can generalize better than existing solutions to unseen games without using any restriction on the action space. Text-based games became popular in the mid 80s with the game series Zork (Anderson & Galley, 1985) resulting in many different text-based games being produced and published (Spaceman, 2019) . These games use a plain text description of the environment and the player has to interact with them by writing natural-language commands. Recently, there has been a growing interest in developing agents that can automatically solve text-based games by interacting with them. These settings challenge the ability of an artificial agent to understand natural language, common sense knowledge, and to develop the ability to interact with environments using language (Luketina et al., 2019; Branavan et al., 2012) . Since the actions in these games are commands that are in natural language form, the major obstacle is the extremely large action space of the agent, which leads to a combinatorially large exploration problem. In fact, with a vocabulary of N words (e.g. 20K) and the possibility of producing sentences with at most m words (e.g. 7 words), the total number of actions is O(N m ) (e.g. 20K 7 ≈ 1.28e 30 ). To avoid this large action space, several existing solutions focus on simpler text-based games with very small vocabularies where the action space is constrained to verb-object pairs (DePristo & Zubek, 2001; Narasimhan et al., 2015; Zelinka, 2018) . Moreover, many existing works rely on using predetermined sets of admissible actions (He et al., 2015; Tessler et al., 2019; Zahavy et al., 2018) . However, a more ideal, and still under explored, alternative would be an agent that can operate in the full, unconstrained action space of natural language that can systematically generalize to new text-based games with no or few interactions with the environment. To address this challenge, we propose to use the idea behind the recently proposed GoExplore (Ecoffet et al., 2019) algorithm. Specifically, we propose to first extract high reward trajectories of states and actions in the game using the exploration methodology proposed in Go-Explore and then train a policy using a Seq2Seq (Sutskever et al., 2014) model that maps observations to actions, in an imitation learning fashion. To show the effectiveness of our proposed methodology, we first benchmark the exploration ability of Go-Explore on the family of text-based games called CoinCollector . Then we use the 4,440 games of "First TextWorld Problems" (Côté, 2018) , which are generated using the machinery introduced by , to show the generalization ability of our proposed methodology. In the former experiment we show that Go-Explore finds winning trajectories faster than existing solutions, and in the latter, we show that training a Seq2Seq model on the trajectories found by Go-Explore results in stronger generalization, as suggested by the stronger performance on unseen games, compared to existing competitive baselines (He et al., 2015; Narasimhan et al., 2015) . Reinforcement Learning Based Approaches for Text-Based Games Among reinforcement learning based efforts to solve text-based games two approaches are prominent. The first approach assumes an action as a sentence of a fixed number of words, and associates a separate Qfunction (Watkins, 1989; Mnih et al., 2015) with each word position in this sentence. This method was demonstrated with two-word sentences consisting of a verb-object pair (e.g. take apple) (DePristo & Zubek, 2001; Narasimhan et al., 2015; Zelinka, 2018; Fulda et al., 2017) . In the second approach, one Q-function that scores all possible actions (i.e. sentences) is learned and used to play the game (He et al., 2015; Tessler et al., 2019; Zahavy et al., 2018) . The first approach is quite limiting since a fixed number of words must be selected in advance and no temporal dependency is enforced between words (e.g. lack of language modelling). In the second approach, on the other hand, the number of possible actions can become exponentially large if the admissible actions (a predetermined low cardinality set of actions that the agent can take) are not provided to the agent. A possible solution to this issue has been proposed by Tao et al. (2018) , where a hierarchical pointer-generator is used to first produce the set of admissible actions given the observation, and subsequently one element of this set is chosen as the action for that observation. However, in our experiments we show that even in settings where the true set of admissible actions is provided by the environment, a Q-scorer (He et al., 2015) does not generalize well in our setting (Section 5.2 Zero-Shot) and we would expect performance to degrade even further if the admissible actions were generated by a separate model. Less common are models that either learn to reduce a large set of actions into a smaller set of admissible actions by eliminating actions (Zahavy et al., 2018) or by compressing them in a latent space (Tessler et al., 2019) . Experimental results show that our proposed Go-Explore exploration strategy is a viable methodology for extracting high-performing trajectories in text-based games. This method allows us to train supervised models that can outperform existing models in the experimental settings that we study. Finally, there are still several challenges and limitations that both our methodology and previous solutions do not fully address yet. For instance: State Representation The state representation is the main limitation of our proposed imitation learning model. In fact, by examining the observations provided in different games, we notice a large overlap in the descriptions (D) of the games. This overlap leads to a situation where the policy receives very similar observations, but is expected to imitate two different actions. This show especially in the joint setting of CookingWorld, where the 222 games are repeated 20 times with different entities and room maps. In this work, we opted for a simple Seq2Seq model for our policy, since our goal is to show the effectiveness of our proposed exploration methods. However, a more complex Hierarchical-Seq2Seq model (Sordoni et al., 2015) or a better encoder representation based on knowledge graphs (Ammanabrolu & Riedl, 2019a; b) would likely improve the of performance this approach. Language Based Exploration In Go-Explore, the given admissible actions are used during random exploration. However, in more complex games, e.g. Zork I and in general the Z-Machine games, these admissible actions are not provided. In such settings, the action space would explode in size, and thus Go-Explore, even with an appropriate cell representation, would have a hard time finding good trajectories. To address this issue one could leverage general language models to produce a set of grammatically correct actions. Alternatively one could iteratively learn a policy to sample actions, while exploring with Go-Explore. Both strategies are viable, and a comparison is left to future work. It is worth noting that a hand-tailored solution for the CookingWorld games has been proposed in the "First TextWorld Problems" competition . This solution 6 managed to obtain up to 91.9% of the maximum possible score across the 514 test games on an unpublished dataset. However, this solution relies on entity extraction and template filling, which we believe limits its potential for generalization. Therefore, this approach should be viewed as complementary rather than competitor to our approach as it could potentially be used as an alternative way of getting promising trajectories. In this paper we presented a novel methodology for solving text-based games which first extracts high-performing trajectories using phase 1 of Go-Explore and then trains a simple Seq2Seq model that maps observations to actions using the extracted trajectories. Our experiments show promising results in three settings, with improved generalization and sample efficiency compared to existing methods. Finally, we discussed the limitations and possible improvements of our methodology, which leads to new research challenges in text-based games.
This work presents an exploration and imitation-learning-based agent capable of state-of-the-art performance in playing text-based computer games. 
{"src": "scitldr-AIC_train", "paper_id": "BygSXCNFDB"}