You will be shown sections from a scientific research paper, together with a question about the paper. Your task is to answer the question based on the contents of the paper. Your response should be a `json` object with two fields:

"answer": An array of strings extracted directly from the paper which, collectively, answer the question.
"evidence": An array of strings. Each should be an excerpt from the paper, in which one or more of the extracted answers can be found.

For instance, for the question "What baselines did the authors compare against?", a sample response might be:

{
  "answer": ["BERT", "RoBERTa"],
  "evidence": ["In our experiments, we compare the performance of our model against BERT and RoBERTa."]
}

Do not include any text in your response other than the json.

If the question is unanswerable given the provided excerpts, respond with the single word "null".

Paper: Exploration Based Language Learning for 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. 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 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.

Introduction
Text-based games became popular in the mid 80s with the game series Zork BIBREF1 resulting in many different text-based games being produced and published BIBREF2. 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 BIBREF3 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 BIBREF4, BIBREF5.
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 \approx 1.28 e^{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 BIBREF6, BIBREF7, BIBREF8, BIBREF9. Moreover, many existing works rely on using predetermined sets of admissible actions BIBREF10, BIBREF11, BIBREF12. 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 Go-Explore BIBREF0 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 BIBREF13 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 BIBREF8. Then we use the 4,440 games of “First TextWorld Problems” BIBREF14, which are generated using the machinery introduced by BIBREF3, 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 BIBREF10, BIBREF7.

Introduction ::: Exploration in Reinforcement Learning
In most text-based games rewards are sparse, since the size of the action space makes the probability of observing a reward extremely low when taking only random actions. Sparse reward environments are particularly challenging for reinforcement learning as they require longer term planning. Many exploration based solutions have been proposed to address the challenges associated with reward sparsity. Among these exploration approaches are novelty search BIBREF19, BIBREF20, BIBREF21, BIBREF22, BIBREF23, intrinsic motivation BIBREF24, BIBREF25, BIBREF26, and curiosity based rewards BIBREF27, BIBREF28, BIBREF29. For text based games exploration methods have been studied by BIBREF8, where the authors showed the effectiveness of the episodic discovery bonus BIBREF30 in environments with sparse rewards. This exploration method can only be applied in games with very small action and state spaces, since their counting methods rely on the state in its explicit raw form.

Methodology
Go-Explore BIBREF0 differs from the exploration-based algorithms discussed above in that it explicitly keeps track of under-explored areas of the state space and in that it utilizes the determinism of the simulator in order to return to those states, allowing it to explore sparse-reward environments in a sample efficient way (see BIBREF0 as well as section SECREF27). For the experiments in this paper we mainly focus on the final performance of our policy, not how that policy is trained, thus making Go-Explore a suitable algorithm for our experiments. Go-Explore is composed of two phases. In phase 1 (also referred to as the “exploration” phase) the algorithm explores the state space through keeping track of previously visited states by maintaining an archive. During this phase, instead of resuming the exploration from scratch, the algorithm starts exploring from promising states in the archive to find high performing trajectories. In phase 2 (also referred to as the “robustification” phase, while in our variant we will call it “generalization”) the algorithm trains a policy using the trajectories found in phase 1. Following this framework, which is also shown in Figure FIGREF56 (Appendix A.2), we define the Go-Explore phases for text-based games.
Let us first define text-based games using the same notation as BIBREF8. A text-based game can be framed as a discrete-time Partially Observable Markov Decision Process (POMDP) BIBREF31 defined by $(S, T, A, \Omega , O, R)$, where: $S$ is the set of the environment states, $T$ is the state transition function that defines the next state probability, i.e. $T(s_{t+1}|a_t;s_t) \forall s_t\in S$, $A$ is the set of actions, which in our case is all the possible sequences of tokens, $\Omega $ is the set of observations, i.e. text observed by the agent every time has it to take an action in the game (i.e. dialogue turn) which is controlled by the conditional observation probability $O$, i.e. $O(o_t|s_t, a_{t-1})$, and, finally, $R$ is the reward function i.e. $r=R(s,a)$.
Let us also define the observation $o_t \in \Omega $ and the action $a_t \in A$. Text-based games provide some information in plain text at each turn and, without loss of generality, we define an observation $o_t$ as the sequence of tokens $\lbrace o_t^0,\cdots ,o_t^n\rbrace $ that form that text. Similarly, we define the tokens of an action $a_t$ as the sequence $\lbrace a_t^0,\cdots ,a_t^m\rbrace $. Furthermore, we define the set of admissible actions $\mathcal {A}_t \in A$ as $\mathcal {A}_t=\lbrace a_0,\cdots ,a_z\rbrace $, where each $a_i$, which is a sequence of tokens, is grammatically correct and admissible with reference to the observation $o_t$.

Methodology ::: Phase 2: Generalization
Phase 2 of Go-Explore uses the trajectories found in phase 1 and trains a policy based on those trajectories. The goal of this phase in the original Go-Explore algorithm is to turn the fragile policy of playing a trajectory of actions in sequence into a more robust, state-conditioned policy that can thus deal with environmental stochasticity. In our variant of the algorithm the purpose of the second phase is generalization: although in our environment there is no stochasticity, our goal is to learn a general policy that can be applied across different games and generalize to unseen games. In the original Go-Explore implementation, the authors used the backward Proximal Policy Optimization algorithm (PPO) BIBREF32, BIBREF33 to train this policy. In this work we opt for a simple but effective Seq2Seq imitation learning approach that does not use the reward directly in the loss. More specifically, given the trajectory $\mathcal {T}_g$, we train a Seq2Seq model to minimize the negative log-likelihood of the action $a_t$ given the observation $o_t$. In other words, consider a word embedding matrix $E \in \mathbb {R}^{d \times |V|}$ where $d$ is the embedding size and $|V|$ is the cardinality of the vocabulary, which maps the input token to an embedded vector. Then, we define an encoder LSTM$_{enc}$ and a decoder LSTM$_{dec}$. Every token $o_t$ from the trajectory $\mathcal {T}_g$ is converted to its embedded representation using the embedding matrix $E$ and the sequence of these embedding vectors is passed through LSTM$_{enc}$:
The last hidden state $h_{|o_t|}^{enc}$ is used as the initial hidden state of the decoder which generates the action $a_t$ token by token. Specifically, given the sequence of hidden states $H \in \mathbb {R}^{d \times |o_t|}$ of the encoder, tokens $a_t^j$ are generated as follows:
where $W \in \mathbb {R}^{2d \times |V|}$ is a matrix that maps the decoder hidden state, concatenated with the context vector, into a vocabulary size vector. During training, the parameters of the model are trained by minimizing:
which is the sum of the negative log likelihood of each token in $a_t$ (using teacher forcing BIBREF34). However, at test time the model produces the sequence in an auto-regressive way BIBREF35 using greedy search.

Results ::: CookingWorld ::: Joint
In this setting, a single model is trained on all the games at the same time, to test whether one agent can learn to play multiple games. Overall, as expected, all the evaluated models achieved a lower performance compared to the single game setting. One reason for this could be that learning multiple games at the same time leads to a situation where the agent encounters similar observations in different games, and the correct action to take in different games may be different. Furthermore, it is important to note that the order in which games are presented greatly affects the performance of LSTM-DQN and DRRN. In our experiments, we tried both an easy-to-hard curriculum (i.e. sorting the games by increasing level of difficulty) and a shuffled curriculum. Shuffling the games at each epoch resulted in far better performance, thus we only report the latter. In Figure FIGREF28 we show the score breakdown, and we can see that all the baselines quickly fail, even for easier games.

Discussion
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:

Discussion ::: 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 BIBREF37 or a better encoder representation based on knowledge graphs BIBREF38, BIBREF39 would likely improve the of performance this approach.

Discussion ::: 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 BIBREF3. This solution 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.

Table 2: Statistics of the two families of text-based games used in the experiments. The average is among the different games in CookingWorld and among different instance of the same game for CoinCollector.

Table 3: CookingWorld results on the three evaluated settings single, joint and zero-shot.

Figure 3: High level intuition of the Go-Exlore algorithm. Figure taken from Ecoffet et al. (2019) with permission.

Figure 11: Zero-Shot all the games

Question: How is trajectory with how rewards extracted?
{"answer": ["explores the state space through keeping track of previously visited states by maintaining an archive"], "evidence": ["Go-Explore BIBREF0 differs from the exploration-based algorithms discussed above in that it explicitly keeps track of under-explored areas of the state space and in that it utilizes the determinism of the simulator in order to return to those states, allowing it to explore sparse-reward environments in a sample efficient way (see BIBREF0 as well as section SECREF27). For the experiments in this paper we mainly focus on the final performance of our policy, not how that policy is trained, thus making Go-Explore a suitable algorithm for our experiments. Go-Explore is composed of two phases. In phase 1 (also referred to as the \u201cexploration\u201d phase) the algorithm explores the state space through keeping track of previously visited states by maintaining an archive. During this phase, instead of resuming the exploration from scratch, the algorithm starts exploring from promising states in the archive to find high performing trajectories. In phase 2 (also referred to as the \u201crobustification\u201d phase, while in our variant we will call it \u201cgeneralization\u201d) the algorithm trains a policy using the trajectories found in phase 1. Following this framework, which is also shown in Figure FIGREF56 (Appendix A.2), we define the Go-Explore phases for text-based games."]}