Year: 2021

Abstract:
Text adventure games present unique challenges to reinforcement learning methods due to their combinatorially large action spaces and sparse rewards. The interplay of these two factors is particularly demanding because large action spaces require extensive exploration, while sparse rewards provide limited feedback. This work proposes to tackle the explore-vs-exploit dilemma using a multi-stage approach that explicitly disentangles these two strategies within each episode. Our algorithm, called eXploit-Then-eXplore (XTX), begins each episode using an exploitation policy that imitates a set of promising trajectories from the past, and then switches over to an exploration policy aimed at discovering novel actions that lead to unseen state spaces. This policy decomposition allows us to combine global decisions about which parts of the game space to return to with curiosity-based local exploration in that space, motivated by how a human may approach these games. Our method significantly outperforms prior approaches by 24% and 10% average normalized score over 12 games from the Jericho benchmark (Hausknecht et al., 2020) in both deterministic and stochastic settings, respectively. On the game of Zork1, in particular, XTX obtains a score of 103, more than a 2x improvement over prior methods, and pushes past several known bottlenecks in the game that have plagued previous state-of-the-art methods.1

heading: 1 INTRODUCTION
text: Text adventure games provide a unique test-bed for algorithms that integrate reinforcement learning (RL) with natural language understanding. Aside from the linguistic ingredient, a key challenge in these games is the combination of very large action spaces with sparse rewards, which calls for a delicate balance between exploration and exploitation. For instance, the game of ZORK1 can contain up to fifty valid action commands per state2 to choose from. Importantly, unlike other RL environments (Bellemare et al., 2013; Todorov et al., 2012), the set of valid action choices does not remain constant across states, with unseen actions frequently appearing in later states of the game. For example, Figure 1 shows several states from ZORK1 where a player has to issue unique action commands like ‘kill troll with sword’, ‘echo’ or ‘odysseus’ to progress further in the game. This requires a game-playing agent to perform extensive exploration to determine the appropriateness of actions, which is hard to bootstrap from previous experience. On the other hand, since rewards are sparse, the agent only gets a few high-scoring trajectories to learn from, requiring vigorous exploitation in order to get back to the furthest point of the game and make progress thereon. Prior approaches to solving these games (He et al., 2016a; Hausknecht et al., 2020; Ammanabrolu & Hausknecht, 2020; Guo et al., 2020) usually employ a single policy and action selection strategy, making it difficult to strike the right balance between exploration and exploitation.
In this paper, we propose eXploit-Then-eXplore (XTX), an algorithm for multi-stage control to explicitly decompose the exploitation and exploration phases within each episode. In the first phase, the agent selects actions according to an exploitation policy which is trained using self-imitation learning on a mixture of promising trajectories from its past experience sampled using a combination of factors such as episodic scores and path length. This policy allows the agent to return to a
1Our code is available in supplementary material. 2Valid actions are a feature in the Jericho simulator (Hausknecht et al., 2020) to improve computational
tractability for RL. Without this handicap, the number of possible action commands is almost 200 billion.
state at the frontier of the state space it has explored so far. Importantly, we ensure that this policy is trained on a mixture of trajectories with different scores, in order to prevent the agent from falling into a local minimum in the state space (e.g. red space in Figure 1). In the second phase, an exploration policy takes over and the agent chooses actions using a value function that is trained using a combination of a temporal difference (TD) loss and an auxiliary inverse dynamics loss (Pathak et al., 2017). This allows the agent to perform strategic exploration around the frontier by reusing values of previously seen actions while exploring novel ones in order to find rewards and make progress in the game. To allow for more fine-grained control, we use a mixture of policies for both exploration and exploitation, and only change a single interpolation parameter to switch between phases.
The two-stage approach to gameplay in XTX allows an agent to combine global decisions about which parts of the game space to advance, followed by local exploration of sub-strategies in that space. This is similar to how humans tackle these games: if a player were to lose to a troll in the dungeon, they would immediately head back to the dungeon after the game restarts and explore strategies thereon to try and defeat the troll. XTX’s multi-stage episodic control differs from prior approaches that add exploration biases to a single policy through curiosity bonuses (Pathak et al., 2017; Tang et al., 2017) or use different reward functions to train a separate exploration policy (Colas et al., 2018; Schäfer et al., 2021; Whitney et al., 2021). Moreover, in contrast to methods like GoExplore (Ecoffet et al., 2021; Madotto et al., 2020), XTX does not have global phases of random exploration followed by learning —instead, both our policies are continuously updated with new experience, allowing XTX to adapt and scale as the agent goes deeper into the game. XTX also does not make any assumptions about the environment being deterministic, and does not require access to underlying game simulator or additional memory archives to keep track of game trees.
We evaluate XTX on a set of games from the Jericho benchmark (Hausknecht et al., 2020), considering both deterministic and stochastic variants of the games. XTX outperforms competitive baselines on 8 out of 12 games, and achieves an average improvement of 2.7% in terms of normalized scores across all games. For instance, on Zork1, our method obtains a score of 103 in the deterministic setting and 67 in the stochastic setting — substantial improvements over baseline scores of 40 and 41, respectively. We also perform ablation studies to demonstrate the importance of the multi-stage approach, as well as several key design choices in our exploitation and exploration policies.

heading: 2 RELATED WORK
text: Reinforcement learning for text-based games Prior work on building autonomous agents for text adventure games has explored several variants of reinforcement learning (RL) agents equipped with a language understanding module (see Osborne et al. (2021) for a detailed survey). Innovations on the language representation side include using deep neural networks for handling text sequences trained using RL (Narasimhan et al., 2015; He et al., 2016a), knowledge graphs to track states
across trajectories (Ammanabrolu & Hausknecht, 2020; Adhikari et al., 2020; Xu et al., 2020), and incorporating question answering or reading comprehension modules (Ammanabrolu et al., 2020; Guo et al., 2020). While these approaches focus mainly on the issues of partial observability and language semantics, they all suffer from challenges due to the large action space and sparse rewards found in games from benchmarks like Jericho (Hausknecht et al., 2020). Some approaches aim to navigate the large action space by filtering inadmissible actions (Zahavy et al., 2018; Jain et al., 2020), leveraging pre-trained language models for action selection (Yao et al., 2020; Jang et al., 2020) or word embeddings for affordance detection (Fulda et al., 2017). Recent work has also explored tackling sparse rewards by employing hierarchical policies (Xu et al., 2021).
Navigating the exploration-exploitation trade-off in RL The trade-off between exploration and exploitation is a well-known issue in reinforcement learning (Sutton & Barto, 2018; François-Lavet et al., 2018; Kearns & Singh, 2002; Brafman & Tennenholtz, 2002). In this respect, we can broadly categorize prior techniques into two types. The first type includes methods with mixed objectives that balance exploration with exploitation. Oh et al. (2018) introduced the idea of self-imitation learning on high-scoring episodes to exploit good trajectories, as an auxiliary objective to standard actor-critic methods. Prior work has also explored the addition of curiosity bonuses to encourage exploration (Pathak et al., 2017; Tang et al., 2017; Li et al., 2020; Bellemare et al., 2016; Machado et al., 2020; Taiga et al., 2021). While we leverage self-imitation learning for exploitation and inverse dynamics bonuses for exploration, our multi-stage mixed policy allows for more strategic exploration in text games. Other works learn a mixture of policies for decoupling exploration and exploitation, either by using a conditional architecture with shared weights (Badia et al., 2020), pre-defining an exploration mechanism for restricted policy optimization (Shani et al., 2019), or learning separate task and exploration policies to maximize different reward functions (Colas et al., 2018; Schäfer et al., 2021; Whitney et al., 2021). While we also train multiple policies, our multistage algorithm performs distinct exploitation and exploration phases within each episode, and does not require pre-defined exploration policies or phases. Further, our work considers environments with significantly larger action spaces that evolves dynamically with deeper progress in the game.
The second class of algorithms explicitly separate exploitation and exploration in each episode. Methods like E3 (Kearns & Singh, 2002; Henaff, 2019) maintain a set of dynamics models to encourage exploration. Policy-based Go-Explore (Ecoffet et al., 2021) uses self-imitation learning to ‘exploit’ high-reward trajectories, but requires choosing intermediate sub-goals for the agent to condition its policy on. PC-PG (Agarwal et al., 2020) uses a policy cover to globally choose state spaces to return to, followed by random exploration. Compared to these approaches, we perform more strategic local exploration due to the use of a Q-function with inverse dynamics bonus and do not require any assumptions about determinism or linearity of the MDP. We provide a more technical discussion on the novelty of our approach at the end of Section 3.
Directed exploration in text-based games As previously mentioned, the large dynamic action space in text games warrant specific strategies for directed exploration. Ammanabrolu et al. (2020) used a knowledge-graph based intrinsic motivation reward to encourage exploration. Jang et al. (2020) incorporated language semantics into action selection for planning using MCTS. Both above methods utilize the determinism of the game or require access to underlying simulator to restart the game from specific states. Madotto et al. (2020) modified the Go-Explore algorithm to test generalization in the CoinCollector (Yuan et al., 2018) and Cooking world domains (Côté et al., 2018). Their method has two phases — the agent first randomly explores and collects trajectories and then a policy is learned through imitation of the best trajectories in the experience replay buffer. In contrast, our algorithm provides for better exploration of new, unseen actions in later stages of the game through the use of an inverse dynamics module and performs multiple rounds of imitation learning for continuous scaling to deeper trajectories in the game. Recently, Yao et al. (2021) used inverse dynamics to improve exploration and Yao et al. (2020) used a language model to generate action candidates that guide exploration. However, both approaches did not employ a two-stage rollout like our work, and the latter considers a different setup without any valid action handicap.

heading: 3 METHOD
text: Background Text-adventure games can be formalized as a Partially Observable Markov Decision Process (POMDP) ⟨S, T,A,O,R, γ⟩. The underlying state space S contains all configurations of
the game state within the simulator, which is unobserved by the agent. The agent receives observations from O from which it has to infer the underlying state s ∈ S. The action set A consists of short phrases from the game vocabulary, T (s′|s, a) is the transition function which determines the probability of moving to the next state s′ given the agent has taken action a in state s, R(s, a) determines the instantaneous reward, and γ is the reward discount factor.
Existing RL approaches that tackle these games usually learn a value function using game rewards. One example is the Deep Reinforcement Relevance Network (DRRN) (He et al., 2016b) which trains a deep neural network with parameters ϕ to approximate Qϕ(o, a). This model encodes each observation o and action candidate a using two recurrent neural networks fo and fa and aggregates the representations to derive the Q-value through an MLP q: Qϕ(o, a) = q(fo(o), fa(a)). The parameters ϕ of the model are trained by minimizing the temporal difference (TD) loss on tuples (o, a, r, o′) of observation, action, reward and the next observation sampled from an experience replay buffer:
LTD(ϕ) = (r + γmax a′∈A Qϕ(o ′, a′)−Qϕ(o, a))2 (1)
The agent samples actions using a softmax exploration policy π(a|o;ϕ) ∝ exp(Qϕ(o, a)). Challenges There are two unique aspects of text adventure games that make them challenging. First, the action space is combinatorially large – usually games can accept action commands of 1-4 words with vocabularies of up to 2257 words. This means an agent potentially has to choose between O(22574) = 2.6 ∗ 1013 actions at each state of the game. To make this problem more tractable, benchmarks like Jericho (Hausknecht et al., 2020) provide a valid action detector that filters out the set of inadmissible commands (i.e. commands that are either unrecognized by the game engine or do not change the underlying state of the game). However, this still results in the issue of dynamic action spaces for the agent that change with the state. For example, the action ‘echo’ is unique to the Loud Room (see Figure 1). Second, these games have very sparse rewards and several bottleneck states (Ammanabrolu et al., 2020), making learning difficult for RL agents that use the same policy for exploration and exploitation (He et al., 2016a; Hausknecht et al., 2020; Ammanabrolu & Riedl, 2019). This results in issues of derailment (Ecoffet et al., 2021), with agents unable to return to promising parts of the state space, resulting in a substantial gap between average episode performance of the agent and the maximum score it sees in the game (Yao et al., 2020).
3.1 OUR ALGORITHM: EXPLOIT-THEN-EXPLORE (XTX)
We tackle the two challenges outlined above using a multi-stage control policy that allows an agent to globally pick promising states of the game to visit while allowing for strategic local exploration thereafter. To this end, we develop eXploit-Then-eXplore, where an agent performs the following two distinct phases of action selection in each episode.
PHASE 1: Exploitation In the exploitation phase, the agent makes a global decision about revisiting promising states of the game it has seen in its past episodes. We sample k trajectories from the experience replay D using a combination of factors such as game score and trajectory length. These trajectories are then used to learn a policy cover πexploit using self-imitation learning (Oh et al., 2018) (see Section 3.1.2 for details). The agent then samples actions from πexploit until it has reached either (1) the maximum score seen during training or (2) a number of steps in the episode equal to the longest of the k sampled trajectories. The second condition ensures the agent can always return to the longest of the k sampled trajectories3. Once either of the above conditions is satisfied, the agent transitions to the exploration phase, adjusting its policy.
PHASE 2: Exploration In the exploration phase, the agent uses a different policy πexplore trained using a combination of the temporal difference loss and an auxiliary inverse dynamics bonus (Pathak et al., 2017; Yao et al., 2021) (see Section 3.1.3 for details). The intuition here is that the exploitation policy πexploit in phase 1 has brought the agent to the game frontier, which is under-explored and may contain a combination of common (e.g. “open door”) and novel (e.g. “kill troll with sword”) actions. Therefore, using a combination of Q-values and inverse dynamics bonus enables the agent to perform strategic, local exploration to further expand the frontier and discover new rewarding states. The agent continues sampling from πexplore until a terminal state or episode limit is reached.
3It is possible that the agent needs less steps to return to a particular part of the game space and hence wastes some steps, but we empirically didn’t find this to be a problem.

heading: 3.1.1 MIXTURE OF POLICIES FOR FINE-GRAINED CONTROL
text: While one could employ two completely disjoint policies for the exploitation and exploration phases, we choose a more general approach of having a policy mixture, with a single parameter λ that can be varied to provide more fine-grained control during the two phases. Specifically, we define:
πλ(a|c, o; θ, ϕ, ξ) = λπinv−dy(a|o; θ, ϕ) + (1− λ)πil(a|c; ξ). (2) Here, πinv−dy refers to an exploration-inducing policy trained using TD loss with an inversedynamics bonus (Section 3.1.3) and is parameterized by θ and ϕ. πil refers to an exploitationinducing policy trained through self-imitation learning (Oh et al., 2018) (Section 3.1.2) and is parameterized by ξ. Note that the action distribution over actions a induced by πinv−dy is conditioned only on the current observation o, while the one induced by πil is conditioned on context c which is an augmentation of o with past information. We can observe that λ provides a trade-off between exploration (high λ) and exploitation (low λ). In our experiments, we choose a small, dynamic value, λ = 12∗T for exploitation (where T is episode limit) and λ = 1 for exploration. As we demonstrate later (Section 4.2), the non-zero λ in exploitation is critical for the agent to avoid getting stuck in regions of local minima (e.g. Zork1). We now describe the individual components of the mixture.
3.1.2 IMITATION LEARNING FOR BUILDING A GLOBAL POLICY COVER (πil)
We parameterize the imitation policy πil using a Transformer model (Vaswani et al., 2017) based on the GPT-2 architecture (Radford et al., 2019) that takes in a context c = [at−2; at−1; ot], i.e. the concatenation of two most recent past actions along with the current observation separated by [SEP] tokens, and outputs a sequence of hidden representations h0, . . . , hm where m is the number of tokens in the sequence. hm is then projected to vocabulary size by multiplication with the output embedding matrix, after which softmax is applied to get probabilities for the next action token. Inspired by (Yao et al., 2020), the GPT-2 model is trained to predict the next action at given the context c using a language modeling objective (Equation 5). The training data consists of k trajectories sampled from an experience replay memoryD which stores transition tuples (ct, at, rt, ot+1, terminal). Sampling trajectories Let us define a trajectory τ as a sequence of observations, actions, and rewards, i.e. τ = o1, a1, r1, o2, a2, r2 . . . , ol+1, where lτ denotes the trajectory length (i.e. number of actions) and thus l ≤ T where T is the episode limit. We sample a trajectory from D using a two-step process. First, we sample a score u from a categorical distribution:
P (u) ∝ exp (β1(u− µU )/σU ) , u ∈ U (3) where U is the set of all unique scores encountered in the game so far, µU is the mean of the set U , and σU is its standard deviation. β1 is the temperature and determines how biased the sampling process is towards high scores. The second step collects all trajectories with the sampled score u and samples a trajectory τ based on the trajectory length lτ : P (τ | u) ∝ exp (−β2(lτ − µLu)/σLu) , lτ ∈ Lu (4) where Lu is the multiset of trajectory lengths lτ with score u, µLu is the mean of the elements in Lu, and σLu is its standard deviation. β2 defines the temperature and determines the strength of the bias towards shorter length trajectories. We perform this sampling procedure k times (with replacement) to obtain a trajectory buffer B on which we perform imitation learning. This allows the agent to globally explore the game space by emulating promising experiences from its past, with a bias towards trajectories with high game score and shorter lengths. The motivation for sampling shorter length trajectories among the ones that reach the same score is because those tend to be the ones that waste less time performing meaningless actions (e.g. “pick up sword”, “drop sword”, etc.).
Learning from trajectories Given the trajectory buffer B containing single-step (c, a) pairs of context c and actions a from the trajectories sampled in the previous step, we train πil by minimizing the cross-entropy loss over action commands (Yao et al., 2020):
L(ξ) = −E(c,a)∼B log πil(a|c; ξ), (5) where c defines the context of past observations and actions as before, and ξ defines the parameters of the GPT-2 model. We perform several passes of optimization through the trajectory buffer B until convergence4 and periodically perform this optimization every n epochs in gameplay to update πil. Furthermore, πil is renormalized over the valid action set Av during gameplay. Note that while πil is trained similarly to the GPT-2 model in (Yao et al., 2020), their model generates action candidates.
4We empirically find 40 passes to be sufficient for convergence.
3.1.3 EFFICIENT LOCAL EXPLORATION WITH INVERSE DYNAMICS (πinv−dy)
In the second phase of our algorithm, we use the inverse dynamics model (INV-DY) from (Yao et al., 2021). INV-DY is a Q-based policy πinv−dy similar to DRRN (He et al., 2016a), optimized with the standard TD loss as explained in Section 3. In addition to this, it adds an auxiliary loss capturing an inverse dynamics prediction error (Pathak et al., 2017), which is added as an intrinsic reward to the game reward and hence incorporated into the TD loss. We find that using this bonus is important for text games because of (1) the large action space and (2) the dynamic nature of the action set at every step in the game, thus making it crucial for the agent to try under-explored actions, which is difficult for the Q network alone to generalize over. Formally, the inverse dynamics loss is defined as:
Linv(θ, ϕ) = − log pd(a|ginv(concat(fo(o), fo(o′))), (6) where θ denotes the parameters for the recurrent decoder d and the MLP ginv (neither of which are used in πinv−dy during gameplay to score the actions), and fo is the same encoder as defined in Section 3. Inverse dynamics ameliorates the challenges mentioned above by giving a bonus to underexplored actions since these are still hard to predict and hence result in a high loss in equation 6.
This loss is optimized together with the TD loss, as well as with an action decoding loss Ldec to obtain the following overall objective that is used to train πinv−dy:
L(ϕ, θ) = LTD + α1Linv(ϕ, θ) + α2Ldec(ϕ, θ), (7)
where Ldec(ϕ, θ) = − log pd(a|fa(a)). Here, fa is a recurrent neural network as defined in Section 3. This loss is added in order to regularize the action decoding and avoid mode collapse in the text representations. We train the model by sampling batches of transitions from a prioritized experience replay buffer D (Schaul et al., 2015) and performing stochastic gradient descent. Episodic rollouts with XTX (Algorithm 1) We now describe how XTX operates in a single episode. The agent starts in phase 1, where actions at are sampled from πexploit. Following this exploitation policy brings the agent to the game frontier, which we estimate to happen when either (1) the current episode score ≥M , the maximum score in the trajectory buffer B or when (2) the current time step t > lmax, the length of the longest trajectory in B. The agent then enters phase 2 and switches its strategy to sample actions only from πinv−dy by setting λ = 1. At every time step t during all phases, a transition tuple (ct, at, rt, ot+1, terminal) is added to the replay buffer D. The policy πexploit is updated every n episodes using the process described in Section 3.1.2, while πexplore is updated within episodes at every step using the TD loss in equation 7, sampling high rewarding trajectories with priority fraction ρ, similar to prior work (Guo et al., 2020)5.
Novelty in comparison to prior algorithms We now more explicitly discuss comparisons to a few other approaches. The most closely related approaches are multi-stage algorithms, including Go-Explore (Ecoffet et al., 2021) and PC-PG (Agarwal et al., 2020) (and somewhat the E3 algorithm (Kearns & Singh, 2002; Henaff, 2019)). Both of these algorithms can be viewed as approaches which explicitly use a “roll-in” policy, with the goal of visiting a novel region of the state-action space. Go-Explore is limited to deterministic MDPs (where it is easy to re-visit any state in the past), while PC-PG (applicable to more general MDPs with provable guarantees under certain linearity assumptions) more explicitly builds a set of policies (‘policy cover’) capable of visiting different regions of the state space. However, in both of these approaches, once the agent reaches a novel part of the state-space, the agent acts randomly. A key distinction in our approach is that once the agent reaches a novel part of the state space, it uses an exploration with novelty bonuses, which may more effectively select promising actions over a random behavioral policy in large action spaces.
The other broad class of approaches that handle exploration use novelty bonuses, with either a policy gradient approach or in conjunction with Q-learning (see Section 2). The difficulty with the former class of algorithms is the “catastrophic forgetting” effect (see Agarwal et al. (2020) for discussion). The difficulty with Q-learning approaches (with a novelty bonus) is that bootstrapping approaches, with function approximation, can be unstable in long planning horizon problems (sometimes referred to as the “deadly triad” (Jiang et al., 2021)). While XTX also uses Q-learning (with a novelty bonus), we only use this policy (πinv−dy) in the second phase of the algorithm in contrast to (Yao et al., 2021) where πinv−dy is used throughout the entire episode; our hope is that this instability
5We slightly differ from their approach as we only prioritize transitions from trajectories that achieve the maximum score seen so far.
Algorithm 1 The eXploit-Then-eXplore (XTX) algorithm 1: Initialize prioritized replay memory D to capacity N with priority fraction ρ. 2: Initialize exploitation policy πexploit with parameters ξ. 3: Initialize exploration policy πexplore with parameters θ and ϕ. 4: Set max score M , max length lmax in B to 0. 5: Exploration steps R = 50; episode limit T = 50 6: for episode← 1, . . . , E do 7: for t← 1, . . . , T do 8: Receive observation ot and valid action set Av ⊂ A for current state. 9: if current episode score < M and t < T −R then ▷ PHASE 1 10: λ← 12∗T 11: else ▷ PHASE 2 12: λ← 1 13: end if 14: Sample an action at from policy π(at|ot, at−1, at−2;ϕ, θ, ξ). ▷ Equation 2 15: Step with at and receive (rt, ot+1, terminal) from game engine. 16: Store transition tuple (ct, at, rt, ot+1, terminal) in D. 17: Update πinv−dy using TD loss with inverse dynamics. ▷ Equation 7 18: end for 19: if n episodes have passed then 20: Sample k trajectories from D to form the new trajectory buffer B. ▷ Section 3.1.2 21: Update πil with cross-entropy loss. ▷ Equation 5 22: Update M, lmax and set T ← lmax +R. 23: end if 24: end for
can be alleviated since we are effectively using Q-learning to solve a shorter horizon exploration problem (as opposed to globally using Q-learning, with a novelty bonus).

heading: 4 EXPERIMENTS
text: Environments We evaluate on 12 human-created games across several genres from the Jericho benchmark (Hausknecht et al., 2020). They provide a variety of challenges such as darkness, nonstandard actions, inventory management, and dialog (Hausknecht et al., 2020). At every step t, the observation from the Jericho game engine contains a description of the state, which is augmented with location and inventory information (by issuing “look” and “inventory” commands) to form ot (Hausknecht et al., 2019). In addition, we use of the valid action handicap provided by Jericho, which filters actions to remove those that do not change the underlying game state. We found this action handicap to be imperfect for some games (marked with * in Table 1), and manually added some action required for agent progress from game walkthroughs to the game engine’s grammar.
Evaluation We evaluate agents under two settings: (a) a deterministic setting where the transition dynamics T (s′|s, a) is a one-hot vector over all the next states s′ and (b) a stochastic setting6 where the T (s′|s, a) defines a distribution over next states s′, and the observations o can be perturbed with irrelevant sentences such as “you hear in the distance the chirping of a song bird”. We report both the episode score average (Avg) over the last 100 episodes at the end of training, as well as the maximum score (Max) seen in any episode during training.
Baselines We consider four baselines. 1) DRRN (He et al., 2016a): This model uses a Q-based softmax policy, i.e. π ∝ exp(Q(o, a;ϕ)), parameterized using GRU encoders and decoders, and trained using the TD loss (Equation 1). 2) INV-DY (Yao et al., 2021): This model augments DRRN with an auxiliary inverse dynamics loss as described in section 3.1.3. 3) MPRC-DQN (Guo et al., 2020): This is a state-of-the-art model that uses an object-centric reading comprehension (RC) module to encode observations and output actions, to mitigate partial observability. The training loss is the same as for the DRRN above, and during gameplay, the agent uses an ϵ-greedy strategy. 4) XTXUniform (∼Go-Explore): Here, we replace πinv−dy with a policy that samples actions uniformly
6Only six games have stochastic variants, and DRAGON was left out due to memory issues in the baselines.
during Phase 2, keeping all other factors of our algorithm the same. This is closest to a version of the Go-Explore algorithm (Ecoffet et al., 2021; Madotto et al., 2020) that returns to promising states and performs random exploration. However, while conceptually similar to Go-Explore, XTX-Uniform does not make use of any additional memory archives, and avoids the complexities of training a goal-based policy. Instead, the exploitation phase of XTX-Uniform relies purely on self-imitation learning to implicitly learn a policy cover over the most promising parts of the game space.
Implementation details We use a learning rate of 10−3 and 10−4 for πil and πinv−dy, respectively. Both policies are trained on batches of size 64, with hidden dimensions of size 128. The Transformer πil has 3 layers and 4 attention heads. β1 in equation 3 is set to 1, β2 in equation 4 is set to 10k to encourage picking the shortest length trajectory, and k is set to 10. In equation 6, α1 = α2 = 1. The priority fraction ρ is set to 0.5. Every time πil is trained, we also scale the episode length T to have at least R remaining steps of exploration by setting T = lmax + R, where lmax is the length of the longest trajectory in the trajectory buffer B. In practice, R = 50, and hence the agent will be guaranteed at least 50 steps of exploration each episode. XTX and DRRN are run for 800k interaction steps, while MPRC-DQN which is run for 100k interaction steps following Guo et al. (2020).

heading: 4.1 RESULTS
text: Deterministic games We report results in Table 1. Overall, XTX outperforms DRRN, INV-DY, MPRC-DQN, and XTX-Uniform by 24%, 24%, 24%, and 3.9% respectively, in terms of average normalized game score (i.e. average episode score divided by max score, averaged over all the games). Our algorithm performs particularly well on Zork1, achieving a 17% absolute improvement in average episode score and a 14% improvement in average maximum score compared to the best baseline. In addition, XTX also nearly solves Library. In particular, XTX manages to advance past several documented bottlenecks like the dark Cellar (see Figure 1) which have proved to be very challenging for existing methods (Ammanabrolu et al., 2020). While performance with XTXUniform is close on most games, random exploration is not enough to push past bottlenecks present in Zork1, showing the potential usefulness of strategic exploration at the game frontier. Surprisingly, DRRN performs very well on the game of Enchanter. For an analysis of this, refer to Appendix A.2.
Stochastic games To show the robustness of XTX to stochasticity, we evaluate our agent in the stochastic setting. We report these results in Table 2. XTX outperforms the baselines on 3 out of 5 games, and pushes past the maximum scores of XTX-Uniform on the same fraction of games. Especially impressive is the performance on Zork1, which is still higher than the state-of-the-art score in the deterministic setting. Interestingly, on the games of Deephome and Enchanter XTX actually performs better than its corresponding scores in the deterministic setting.

heading: 4.2 ANALYSIS
text: In order to evaluate the importance of the various components in XTX, we perform several ablations on a subset of the games as described below and shown in Figure 2 (full set in Appendix A.3).
Games DRRN MPRC-DQN XTX-Uniform XTX (ours) ∆ (%) Game MaxAvg Max Avg Max Avg Max Avg Max ZORK1 41.3 55.7 41.2 53.0 31.2 48.0 67.7 143.0 +8% 350 ZORK3* 0.2 4.0 2.7 4.7 2.3 4.3 2.6 5.0 -1% 7 PENTARI* 38.2 60.0 33.3 41.7 38.8 60.0 46.2 60.0 +11% 70 DEEPHOME* 43.0 65.7 1.0 1.0 50.7 69.3 75.4 91.7 +8% 300 ENCHANTER* 42.0 56.7 27.1 43.3 30.2 45.0 33.8 36.7 -2% 400 Avg. Norm Score 18.86% 38.96% 20.94% 30.5% 24.27% 39.14% 31.18% 47.54% +4.8% 100%
Zork1 Inhumane Zork3 Ludicorp Deephome Omniquest Game
Figure 2: Average episode scores for 4 ablation models across 6 games. Overall, we find both the strategic inverse dynamics policy and the explicit exploitation policy to be key for our algorithm.
Pure imitation learning (λ = 0) This ablation sets λ = 0 in equation 2, meaning the agent will always use the imitation learning policy πil. As expected, this model performs quite badly since it is based on pure exploitation and is hence unlikely to reach deep states in the game.
Pure inverse dynamics (λ = 1) This ablation sets λ = 1 in equation 2, hence always using the inverse dynamics exploration policy πinv−dy, resulting in the model proposed in (Yao et al., 2021). While this model can sometimes achieve high maximum scores, it is unable to learn from these and hence its average episode score remains quite low, consistent with findings in (Yao et al., 2021).
Mixing exploration and exploitation (λ = 0.5) By setting λ = 0.5, this ablation constantly alternates between exploitation and exploration, never committing to one or the other. This loses the benefit of having an explicit exploitation policy in the first place, since it can only guide the agent for a few steps before it gets interrupted by the exploration policy. Hence, results are not strong.
Pure separation of exploitation and exploration (XTX no-mix) In this ablation, we examine the importance of having a mixture policy in Phase 1 of the algorithm instead of setting λ = 0 in Phase 1 and to 1 in Phase 2. This explicitly separated model, denoted as XTX (no-mix), performs a bit better in the games of Inhumane and Zork3, but sometimes fails to push past certain stages in Ludicorp (hence the high variance) and completely gets stuck in the game of Zork1. This shows it is crucial to have a mixture policy in Phase 1 in order to get past bottleneck states in difficult games.

heading: 5 CONCLUSION
text: We have proposed XTX, an algorithm for multi-stage episodic control in text adventure games. XTX explicitly disentangles exploitation and exploration into different policies, which are used by the agent for action selection in different phases of the same episode. Decomposing the policy allows the agent to combine global decisions on which state spaces in the environment to (re-)explore , followed by strategic local exploration that can handle novel, unseen actions – aspects that help tackle the challenges of sparse rewards and dynamic action spaces in these games. Our method significantly outperforms prior methods on several games from the Jericho benchmark (Hausknecht et al., 2020) under both deterministic and stochastic settings, and even surpasses several challenging bottlenecks in games like Zork1 (Ammanabrolu et al., 2020). Future work can integrate our algorithm with approaches that better leverage linguistic signals to achieve further progress in these games.

heading: ETHICAL CONSIDERATIONS
text: This work focuses on building better agents for text-adventure games and hence does not have immediate direct ethical concerns. However, the techniques introduced in this paper may be generally useful for other autonomous agents that combine sequential decision making with language understanding (e.g. dialog systems). As such agents become more capable and influential in our lives, it is important to make sure their objectives align with those of humans, and that they are free of bias.

heading: REPRODUCIBILITY
text: Our code is provided in the supplementary material and we plan to publicly release the code upon acceptance. We provide all implementation details such as hyperparameters, model architectures and training regimes in Section 4.

heading: A APPENDIX

heading: A.1 GAME STATISTICS
text: Table 3 contains the average and maximum number of steps between rewards in these games, showcasing their challenging nature.

heading: A.2 DRRN’S SUPERIOR PERFORMANCE ON ENCHANTER
text: We found the XTX agent is getting stuck when needing to use a specific spell to open a gate, where the spell needs to be learned or carried with on a scroll found several steps ago (this is a bottleneck where the score bumps from 20 to 40). The XTX agent is rarely able to use the spell at the gate, while the DRRN agent can consistently do this. Our current hypothesis for this is that DRRN is given a larger number of exploration steps per episode. Specifically, we found that the first +20 reward in the game always happens at the very first step, so essentially all trajectories in XTX’s trajectory buffer B are length 1, causing the number of environment steps per episode to always be 51, which is significantly lower than the 100 steps of exploration every episode that DRRN is able to use. To verify this, we ran XTX with 100 steps of exploration instead of 50 (i.e. R = 100 in Algorithm 1), and found the performance to be similar to DRRN (DRRN avg: 42.0, DRRN max: 66.7, XTX avg: 42.9, XTX max: 55). This shows that there is no fundamental flaw or reason why XTX underperformed on Enchanter; simply tuning a hyperparameter closed most of the gap.

heading: A.3 FULL SET OF ABLATIONS
text: Zork1 Inhumane Zork3 Ludicorp Deephome Game
0.0
0.2
0.4
0.6
0.8
No rm
al ize
d Sc
or e
Ablation Pure IL ( = 0) Pure Inv Dy ( = 1) Mix ( = 0.5) XTX (no-mix) XTX (full model)

heading: Full set of ablations

heading: A.4 ABLATION TRAINING PLOTS

heading: A.5 FULL DETERMINISTIC AND STOCHASTIC RESULTS

Review summaries:
In this paper, the authors propose eXploit-Then-eXplore (XTX), a training strategy for agent solving human-generated text-based games.   XTX consists of two training phases:  1. In the exploitation phase, the agent samples high quality experiences (in terms of score and trajectory length) from its replay buffer. Using the sampled trajectories, an action generation module is trained. At a certain game step $t$, the action generation module takes the observation $o_t$, as well as the two most recent past actions $a_{t-1}$ and $a_{t-2}$ as input, and generates the new action $a_t$ in a word-by-word auto-regressive manner. This process is referred as self-imitation by the authors.   2. In the exploration phase, in addition to the Q-learning loss as used in DRRN, the authors use two auxiliary losses to encourage the model to capture useful representations. First, the inverse dynamics loss $L_{inv}$ optimizes a module that predicts an action $a_t$ given two consecutive observations $o_t$ and $o_{t+1}$, where $o_{t+1}$ is resulted by $a_t$ given $o_t$. The second loss $L_{dec}$ is a regularizer that optimizes a module reconstructs an action $a_t$ from its encoding $f_a(a_t)$.  During training, the two phases take control in an (almost) alternate manner, however, there is a coefficient $\lambda$ controls the interpolation between the phases. The authors show that it is beneficial to not having the exploitation take control solely.   On a subset of games from the Jericho suite, the authors show their agent outperform prior works.  

Summary:  The paper proposes a multi-stage directed exploration algorithm, XTX. It first imitates previous high score trajectories and then switches to an exploration policy with novelty bonuses. Conceptually, XTX is a method that extends Go-Explore which only acts randomly after reaching the frontier of familiar states. The paper argues that with novelty bonuses, the agent will be encouraged to explore more promising actions. This can especially be helpful when the action space is large like text-based games. Empirically, XTX shows strong performance on a large set of text-based games.

This paper presents a new exploration algorithm, eXploit-Then-eXplore (XTX), for text-based games which require extensive exploration. The authors propose an algorithm that explicitly disentangles exploitation and exploration strategies within each episode. XTX first learns the exploitation policy that imitates the promising trajectories from past experiences, then uses exploration policy to discover the novel state-action spaces. Finally, the authors demonstrated the outperforming results in the Jericho environment. 

This paper introduces an agent with a built-in exploration strategy that is aimed at text adventure games, or more generally, environments with large action spaces and sparse rewards. The exploration strategy is constructed from two independent policies: one trained with self-imitation learning on successful trajectories, and one trained on an inverse dynamics intrinsic reward. The agent plays episodes by starting with the exploitation policy for a number of steps that depends on the experience collected up to that point, and then switching to the exploration policy. The paper is well-written, describes the contributions clearly, and places itself in the context of the existing literature on exploration. It includes results on a number of text exploration games from a recent benchmark, where it shows by and large a significant improvement relative to the baselines included.