Multi-Stage Episodic Control for Strategic Exploration in Text Games
Authors: Jens Tuyls
Shunyu Yao
Sham M. Kakade
Karthik R Narasimhan
Venue: ICLR 2022 Spotlight (2022)
Keywords: reinforcement learning
language understanding
text-based games

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 27% and 11% 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.

Published as a conference paper at ICLR 2022
MULTI-STAGE EPISODIC CONTROL FOR STRATEGIC EXPLORATION IN TEXT GAMES
Jens Tuyls', Shunyu Yao',Sham Sham Kakade² & Karthik Narasimhan'
Department of Computer Science, Princeton University
Johnn A. Paulson School Engineering and Applied Sciences, Harvard University {ituyls, shunyuy, farthikn]&prla oetton. edu, sham@ harvard.edu
ABSTRACT
Text adventure games present unique challenges reinforcement learning meth- ods due to their combinatorially large action spaces and sparse rewards. The inter- play of these factors is partieularly demanding because large action spaces re- quire extensive exploration, while sparse rewards provide limited feedback. This work proposes tackle the explore-vs-explor dilemma using multi-stage ap- proach that explicitly disentangles these two strategies within each episode. Our algorithm, called eXploit-Thent Then-eXplore (XTX), begins each episode using an ex- ploitation policy that imitates 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 to combine global de- local
cisions about which parts the game space to return to with curiosity-barn exploration in that space, motivated by how human may approach these games. Our method significantly outperforms prior approaches by 27% and 11% 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 Zorkl, in particular, XTX obtains a score of 103, more than 2x improvement over prior methods, and pushes past several known bottlenecks in the game that have plagued previous state-of-the-un methods
INTRODUCTION
Text adventure games provide unique test-bed for algorithms that integrate reinforcement learning (RL) with natural language understanding. Aside from the linguistic ingredient, key challenge in these games is the combination of very large action spaces with sparse rewards, which calls for delicate balance between exploration and exploitation. For instance, the game of ZORK1 can contain up to fifty valid action commands per state 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 shows several states from ZORK where a player has to issue unique action commands like 'kill troll with sword', 'echo' 'odysseus' 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; Hauskkeech et al.) 2020 Ammanabrolu & Hausknecht 2020 Guo al.) 2020) usually employ a single policy and action selection strategy,
making it difficult to strike the right balance between exploration and exploitation.
(XTX), an algorithm for multi-stage control to ex- plicitly decompose the exploitation and exploration phases within each episode. In the first phase, the agent selects actions according to an exploitation policy which trained using self-imitation
In this paper, we propose
Our code is available at wntttpp:: h/tpttggtttbb.t//// Valid actions are feature in the Jericho simulator (Hausknecht al. 2020) to improve computational tractability for RT.. Without this handicap, the number of possible action commands is almost 200 billion.
1/

---

Published as a conference paper at ICLR 2022
Loud
to room doafoningly loud
of standing an open field.... ..." Score: 0
window"
Aixina you have sword
Troil Room T.. trall blocks pessages ...
"lccho"
"Move
Cellar
Score: 10
Score: 35 troll with sword"
Cyalans Room eyclops, who looks prepared ...
pitch
"Down"
black...
Score:
Score: 40
up"
"Odysseus"
Sample game paths and state observations from ZORK1. Starting from the leftmost state ("West of House'), the agent encounters several novel and unique valid actions (e.g Odysseus, Echo) (in brown) across different states in the game. In order to make progress, our algorithm (XTX) strategically re-visits different frontiers in the state space (red and blue circles) and performs strategic local exploration to overcome bottleneck states (e.g. 'Troll Room') ) and dead-ends (e.g. 'Cellar'). Solid borders indicate visited states, dotted ones indicate potential future states.
Figure 1:
learning mixture of promising trajectories from its past experience sampled using combina- tion of factors such as episodic scores and path length. This policy allows the agent to return to a state the frontier of the state space it has explored far. Importantly, we ensure that this policy trained on a mixture of trajectories with different scores, order to prevent the agent from falling into a local minimum in the state space (e.g. red space in Figure [ In the second phase, an explo- ration policy takes over and the agent chooses actions using a value function that is trained using combination of temporal difference (TD) loss and an auxiliary inverse dynamics loss (Pathak 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 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 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 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 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.) different reward functions train separate exploration policy (Colas) 2018||Schäfer Schäfer et al. (2021; Whitney et al. (021). I. Moreover, in contrast to methods like Go- et al. 2018,
2017 Tang al. 2017)
Explore (Ecoffet al.] [202]] Madotto et al., (020)) 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 the agent goes deeper into the game. XTX also does not make any assumptions about the environment being deterministic, and does not require access underlying game simulator or additional memory archives keep track of game trees.
We evaluate XTX on a set of games from the Jericho benchmark (Hausknecht et al. 2020), consider- ing both deterministic and stochastic variants of the games. XTX outperforms competitive baselines on all 12 games, and achieves average improvement of 5.8% in terms of normalized scores across all games. For instance, on Zorkl, our method obtains a score 103 in the deterministic setting and 67 in the stochastic setting substantial improvements over baseline scores of 44 and 41, respec- tively. We also perform ablation studies to demonstrate the importance of the multi-stage approach, as well several key design choices in our exploitation and exploration policies.
2 RELATED WORK
Reinforcement learning for text-based games Prior work building autonomous agents for text adventure games has explored several variants of reinforcement learning (RL) agents equipped with language understanding module (see Osborne et al. (2021) for detailed survey). Innovations
2

---

Published as a conference paper at ICLR 2022
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 al., (020).. 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 al. 2021b.
Navigating the exploration-exploitation trade-off in RL The trade-off between exploration and exploitation a well-known issue in RI. (Sutton Barto 2018 Franç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 ex- ploration 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 meth- ods. Prior work has also explored the addition of curiosity bonuses encourage exploration (Pathak
let al. 2017: Tang et al.] [017] Li et al. 2020) [ellemare et al. 2016, Machado et al.) [020 Taiga
al.) 2021). While we leverage self-imitation learning for exploitation and inverse dynamics bonuses for exploration, we use a multi-stage mixed policy. Other works learn 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 optimiza- tion (Shani et al. 2019), or learning separate task and exploration policies to maximize different reward functions (Colas et al. 20188 Schäter et al. 2022 W Whitney et al. 2021). While we also train multiple policies, our multi-stage algorithm performs distinct exploitation and exploration phases within each episode, not requiring pre-defined exploration policies or phases. Further, we consider environments with significantly larger action spaces that evolve dynamically as the game progresses.
The second class of algorithms explicitly separate exploitation and exploration in each episode. Methods like 3 (Kearns & Singh 2002; Henaff, 2019) maintain a set of dynamics models to en- courage exploration. Policy-based Go-Explore (Ecoffet 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.] a (2020) used a knowledge-graph based intrinsic motivation reward to encourage exploration. |Jang et al. (020)) incorporated language semanties into action selection for planning using MCTS. Both meth- ods utilize the determinism of the game or require access to simulator to restart the game from specific states. Madotto et al. (2020) modified the Go-Explore algorithm to test generalization in the CoinCollector Yuuan et al.] 2018) and Cooking world domains (Côté 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. (2221) 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.
3

---

Published as a conference paper at ICLR 2022
3 METHOD
Background Text-adventure games can be formalized as a Partially Observable Markov Decision Process (POMDP) (S, (,, O, 7). The underlying state space S contains all configurations of the game state within the simulator, which is unobserved by the agent. The agent receives obser- vations from O from which it has infer the underlying state s E S. The action set A consists of short phrases from the game vocabulary, T(''ss, a) is the transition function which determines the probability of moving to the next state s' given the agent has taken action a state 8, R(s, a) determines the instantancous reward, and y 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 Qo(o, a). This model encodes each observation and action candidate using two recurrent networks fo and fa and aggregates the rep- resentations to derive the Q-value through an MLP q: Qo a) Ia fa(a)). The parameters of the model are trained by minimizing the temporal difference (TD) loss on tuples (a, a, r; o') of observation, action, reward and the next observation sampled from an experience replay buffer:
(o) = (r + max Qold', a') Q)(o,a))²
(1)
e'EA
The agent samples actions using a softmax exploration policy <aloo Φ) x exp(Qo(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 (2257H) = 2.6 10_3 actions at each state of the game. To make this problem more tractable, benchmarks like Jericho (Hausknecht et al. (020)) provide a valid action detector that filters out the set of inadmissible commands (i.c. 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 D. Second, these games have very sparse rewards (see Appendix AA.1) and several bottleneck states (Ammanabrolu et al., (020)), making learning difficult for RL agents that use the same policy for exploration and exploitation (He et al. [016aa] [Haskknehh al.) 2020 Ammanabrolu & Riedl 2019). This results in issues of derailment (Ecoffet et al. 20011). with agents unable to return to promising parts of the state space, resulting in 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- THE-UIT-TEEEEEEEPPLEE (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 two distinct phases of action selection in each episode.
where an agent performs the following
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 & 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 Texploit using self-imitation learning (Oh et al., 2018) (see Section 3.2 for details). The agent then samples actions from Texploit 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 h sampled trajectories. The second condition ensures the agent can always return to the longest of the & sampled trajectories 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 Texplore trained using both temporal difference loss and an auxiliary inverse dynamics bonus (Pathak et al. 2017 Yao et al., 2021) (see Section 3.3 for details). The intuition here is that the exploitation policy Texploit phase has brought the agent to the game frontier, which is under-explored and may
It is possible that the agent needs less steps return to particular part of the game space and hence wastes some steps, hut we empirically didn't 't find this to be a prohlem.
4

---

Published as a conference paper at ICLR 2022
contain combination of common (e.g. "open door") and novel (e.g. "kill troll with sword") ac- tions. Therefore, using a combination of Q-values and inverse dynamics bonus enables the agent to perform strategic, local exploration expand the frontier and discover new rewarding states. The agent continues sampling from Texplore until a terminal state or episode limit is reached.
3.1.1 MIXTURE OF POLICIES FOR FINE-GRAINED CONTROL
While one could employ two completely disjoint policies for the exploitation and exploration phases, we choose more general approach of having a policy mixture, with single parameter À that can be varied to provide more fine-grained control during the two phases. Specifically, we define:
Ta(a,,, o; 0, ④) = (aloo A, Φ) + (1 -1--X -))aa(a((;))
(2)
Here, -yy refers to an exploration-induuee dynamics bonus (Section 3.3) and is parameterized by 0 and Φ. Tu refers to exploitation-inducin policy trained through self-imitation learning (Oh et al. 2018) (Section (.2] and is parameterized by E. Note that the action distribution over actions a induced by duv--dy is conditioned only on the current observation O, while the one induced by Ta is conditioned on context which is an augmen- tation of with past information. We can observe that À provides trade-off between exploration (high A) and exploitation (low A). In our experiments, we choose small, dynamic value, À = 2-T for exploitation (where T 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. 1).k1). We now describe the individual components of the mixture.
policy trained using TD loss with an inverse-
3.2 IMITATION LEARNING FOR BUILDING A GLOBAL POLICY COVER (TT))
We parameterize the imitation policy Wa using Transformer model (Vaswani al. 2017) based
on the GPT-2 architecture (Radford et al. 2019) that takes in a context с = 2 Gr 1: 0.]. i.e. the concatenation of two most recent past actions along with the current observation separated by [SEP] tokens, and outputs sequence of hidden representations ho..... hm where m is the number of tokens in the sequence. hn 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. In- spired by (Yao et al.) 2020), the GPT-2 model is trained to predict the next action a given the context using a language modeling objective (Equation 5 The training data consists of k trajectories sam- pled from an experience replay memory D which stores transition tuples (ct, de, Te: O1+1, terminal).
Sampling trajectories Let us define trajectory as sequence of observations, actions, and re- wards, i.e. т = 01, a1,, ri, 02, 02 .2...... Ot+1, where I, denotes the trajectory length (i.e. number of actions) and thus 1 < T where T is the episode limit. We sample a trajectory from D using two-step process. First, we sample a score u from a categorical distribution:
P(u) x exp (3 pu)/ou), u. E
where Ut is the set of all unique scores encountered in the game so far, pu is the mean of the set U. and du is its standard deviation. 31 is the temperature and determines how biased the sampling process is towards high scores. The second step collects all trajectories with the sampled score and samples a trajectory T based on the trajectory length 1,:
P(T [u] & exp (-32(1, - -ML.)/OL.)) 1, L
(4)
where Ly is the multiset of trajectory lengths I, with score Jrr,, is the mean of the elements in ILu, and or., is its standard deviation. 32 defines the temperature and determines the strength of the bias towards shorter length trajectories. We perform this sampling procedure io times (with replacement) obtain 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 and actions a from the trajectories sampled the previous step, we train Tu by minimizing the cross-entropy loss over action commands (Yao et al. 2020h:
L(E) -E log TH (n(a)c;
(5)
5

---

Published as a conference paper at ICLR 2022
where с defines the context of past observations and actions before, and & defines the parameters of the GPT-2 model. We perform several passes of optimization through the trajectory buffer B until convergened" and periodically perform this optimization every n epochs in gameplay update ma- Furthermore, Ti is renormalized over the valid action set A, during gameplay. Note that while va is trained similarly to the GPT-2 model in (Yao et al. 2020), their model generates action candidates.
3.3 EFFICIENT LOCAL EXPLORATION WITH INVERSE DYNAMICS (Tiv-dy)
In the second phase of our algorithm, we would like to use a policy that tackles (1) the large action space and (2) the dynamic nature of the action set at every step in the game, which makes it crucial to keep trying under-explored actions and is difficult for the Q network alone to generalize over. To this end, we use the inverse dynamics model (INV-DY) from (Yao et al.) 2021). INV-DY a Q- based policy -inv-dy similar to DRRN (He et al. 201 optimized with the standard TD loss (see Background of Section 3). In addition, it adds an auxiliary loss Linv capturing an inverse dynamics prediction error (Pathak et al. 2017), which is added as intrinsic reward to the game reward (r T "game + (1) * Linv) and hence incorporated into the TD loss. Formally, Liny is defined as:
(0,
log finw (concat (o(()))
where 8 denotes the parameters for the recurrent decoder d and the MLP gine (neither of which used in dy during gameplay to score the actions), and fo is the encoder defined in Section 3 This loss optimized together with the TD loss as well with an action decoding loss Ldee to obtain the following overall objective that is used to train dyv-dy:
[( 0) = LTD + agLine (Ø, 0) + ag (o
where Ldee (d) 0) log pa(affa(a)) (a)). Here, fa is recurrent network (see Section Please refer to Yao et al. (2021) for details. We train the model by sampling batches of transitions from a prior- itized experience replay buffer D (Schaul al., 2015) and performing stochastic gradient descent. Inverse dynamics ameliorates the challenges (1) and (2) mentioned above by rewarding underex- plored actions (i.e. a high loss in Equation 6 and by generalizing over novel action commands. Specifically, the INV-DY network might generalize through learning of past bonuses to what new actions would look like and hence identify novel actions before having tried them once.
3.4 EPISODIC ROLLOUTS WITH XTX (ALGORITIM) I
We now deseribe how XTX operates in a single episode. The agent starts in phase I, where actions ag are sampled from exppoitt Following this exploitation policy brings the agent to the game frontier, which we estimate happen when either (1) the current episode score M,, the maximum score in the trajectory buffer B or when (2) the current time step >> Imax. the length of the longest trajectory in B. The agent then enters phase 2 and switches its strategy to sample actions only from Tiny by setting À = 1. At every time step t during all phases, a transition tuple (Ce, rt, Oc+1, terminal) added to the replay buffer D. The policy Texploit is updated every n episodes using the process in Section 3.2 while Texplore is updated within episodes at every step using the TD loss in equation 7
sampling high rewarding trajectories with priority fraction similar to (Guo et al. 2020
3.5 NOVELTY IN COMPARISON TO PRIOR ALGORITHMS
We now more explicitly discuss comparisons to a few other approaches. The most closely related ap- proaches are multi-stage algorithms, including Go- Go-Explore (Ecoffet al. 2021 and PC-PG (Agar- wal et al. 2020) (and somewhat the E algorithm (Kearns & Singh [002 Henaff 2019)). Both of these algorithms can be viewed approaches which explicitly use "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 e
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
*We empirically find 40 passes to sufficient for convergence. 'We slightly differ from their approach as only prioritize transitions from trajectories that achieve the maximum score seen so far.

---

Published as a conference paper at ICLR 2022
Algorithm The eXploit-Then-eXppee (XTX) algorithm
1: Initialize prioritized replay memory D to capacity N with priority fraction p.
2: Initialize Texpinit (with parameters {) and Texplore (with parameters and ().
3: Set max score M, max length max in B to O.
4: Exploration steps = 50; episode limit = 50
5: for episode < 1, ................................ E do
6: for < 1 do
Receive observation o, and valid action set A, A for current state. 8: if current episode score < M and < T R then
7:
b PHASE
9:
2+T
10:
else
> PHASE
1
12:
end if
Sample an action o, from policy x (x dt-1, at-2-- () Step with ae and receive (Tt, 0++1; terminal) from game engine.
Equation
14:
15:
Store transition tuple (ct, Gr, Tt, O++1, terminal) in D. Update dinv-dy using TD loss with inverse dynamics. end for
16:
Equation
17:
18:
if episodes have passed then
19:
Sample & trajectories from D to form the new trajectory buffer Update गi with cross-entropy loss.
> Section 3.2
20:
Equation
21:
Update M, Imax and set T <- Imax + R.
end if end for
23:
approaches, once the agent reaches novel part of the state-space, the agent acts randomly. A key distinction our approach that once the agent reaches novel part of the state space, it uses an exploration with novelty bonuses, which may more effectively select promising actions over random bchavioral 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
ferred to as the "deadly triad" (Jiang et al. (021)). While XTX also uses Q-learning (with novelty bonus), we only use this policy (Tin--dy) in the second phase of the algorithm in contrast to (Yao et al. 202T) where -iuv-dy is used throughout the entire episode; our hope is that this instability can alleviated since we are effectively using Q-learning to solve a shorter horizon exploration problem (as opposed to globally using Q-learning, with novelty bonus).
4 EXPERIMENTS
Environments We evaluate on 12 human-created games across several genres from the Jericho benchmark (Hausknecht et al. 2020). They provide variety challenges such as darkness, non- standard actions, inventory management, and dialog (Hausknecht et al.) 2020). At every step 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) Of (Hausknecht et al.] (019). In addition, we use of the valid action handicap provided by Jericho, which filters actions remove those that do change the underlying game state. We found this action handicap to be imperfect for some games (marked with in Table T]. and manually added some actions required for agent progress from game walkthroughs to the game engine's grammar.
form
Evaluation We evaluate agents under two settings: (a) deterministic setting where the transition dynamics T's'le ss a) is one-hot vector over all the next states s' and (b) a stochastic setting" where the T [s, a) defines distribution over next states s', and the observations o can be perturbed with
"Only six games have stochastic variants, and DRAGON was left due memory issues in the haselines.

---

Published as a conference paper at ICLR 2022
DRRN
INV-DY
RC-DQN
XTX-Uniform
XTX (ours)
A (%)
Game Max
Avg
Max
Avg
Max
Avg
Max
Avg
Max
Avg
Max
ZORK1
40.3
55.0
44.1
105.0
41.7
53.0
34.1
52.3
103.4
152.7
+17%
350
INHUMANE*
56.7
63.3
53.3
76.7
76.7
+5%
90
LUDICORP*
17.1
48.7
19.6
49.3
10.9
40.7
67.3
86.0
78.8
91.0
+8%
150
ZORK3*
4.3
5.0
5.0
4.7
5.0
PENTARI"
45.6
58.3
34.5
53.3
33.4
46.7
43.4
60.0
49.6
60.0
+6%
70
DETECTIVE
320.0
323.3
346.7
336.7
340.0
BALANCES
14.1
25.0
12.5
25.0
10.0
18.3
21.9
25
24.0
26.7
+4%
51
LIBRARY"
24.8
30.0
24.7
30.0
24.2
30,0
26.1
30.0
28.5
30,0
+8%
30
DEEPHOME"
58.8
68.0
58.9
72.7
1.0
1.0
52.6
70.0
77.7
92.3
+6%
300
ENCHANTER*
42.0
66.7
63.3
38.3
28.3
52.0
66.7
+2%
400
DRAGON
-3.7
8.0
-2.3
8.7
3.2
8.0
40.7
126.0
96.7
127.0
0%
25
OMNIQUEST
8.2
10.0
13.3
10.0
10.0
11.6
13.3
+3%
50
Avg. Norm Score
29.5%
48.8%
28.4%
51.8%
29.7%
44.5%
49.2%
58.6%
56.3%
64.0%
100%
Results deterministic games for the best XTX model, where the inverse dynamics scaling coefficient 01 was tuned per game. We outperform the baselines on all 12 games, achieving an average normalized game score of 56%. indicates actions were added to the game grammar. A indicates the absolute performance difference between XTX and the best baseline on Avg scores. Scores are averaged across seeds. Baselines were rerun with the latest Jericho version.
Table 1:
irrelevant sentences such as "you hear in the distance the chirping of 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. X exp(Q(o, a; 6)). parameterized using GRU encoders and decoders, and
trained using the TD loss (Bquation D 2) INV-DY (ao et al. 2021): Refer to Section 3.3 3) RC-DQN (Guo et al. 2020): This is a state-of-the-arr model that uses an object-centric reading comprehension (RC) module to encode observations and output actions. The training loss is that of DRRN above, and during gameplay, the agent uses an e-greedy strategy. 4) XTX- (~Go- Explore): Here, we replace dinv-dy with policy that samples actions uniformly 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. (2221) that returns to promising states and performs random exploration. However, while conceptually similar to Go-Explore, XTX-Uniform does not make use of any addi- tional memory archives, and avoids training goal-based policy. See Appendix A.2 for implemen- tation details and hyperparameters.
4.1 RESULTS
Deterministic games We report results in Table (refer to Appendix A.5 and A.6 for more details). Overall, XTX outperforms DRRN, INV-DY, RC-DQN, and XTx-Unifone by 27%, 28%, 27%, and 7% respectively, 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 17% absolute improvement in average episode score and 14% improvement average maximum score compared to the best bascline. In particular, XTX manages to advance past several documented bottlenecks like the dark Cellar (see Figure ! which have proved to be very challenging for existing methods (Ammanabrolu et al. 2020). While performance with XTX- TTX-Uniform is some- times close, exploration with inverse dynamics instead random exploration pushes past several bottlenecks present in Z and leads to significant gains on Deephome, Enchanter, Omniquest, and Ludicorp. showing the potential usefulness of strategic exploration at the game frontier.
Stochastic games To show the robustness of XTX to stochasticity, stochastic setting (Table XTX outperforms the baselines on 4 out of games, and pushes past the maximum scores of UTix-unifomm on the same fraction. Especially impressive is the performance on Zorkl, which is still higher than the state-of-the-art score in the deterministic setting.
evaluate our agent in the
4.2 ABLATION STUDIES
In order to evaluate the importance of the various components in XTX, we perform several ablations on a subset of the games described below and shown in Figure ( in Appendix A.3 and A.4)
Interestingly, XTX manages achieve a very high score on Dragon by exploiting integer underflow bug.
8

---

Published as a conference paper at ICLR 2022
DRRN
INV-DY
RC-DQN
XTX-Uniform
(ours)
(%)
Game Max
Avg
Max
Avg
Max
Avg
Max
Avg
Max
Avg
Max
ZORK1
41.3
55.7
36.9
85.7
40.3
53.0
31.2
48.0
67.7
143.0
+8%
350
ZORK3*
7
PENTARI
38.2
60.0
37.5
55.0
33.3
41.7
38.8
60.0
47.3
60.0
+12%
70
73.0
ENCHANTER
42.0
36.7
34,5
53.3
27.1
43.3
30.2
45.0
44,8
58.3
+1%
400
Avg. Norm Score 18.95
39.0%
19.75
41.3%
20.996
30.5%
24.3%
39.1%
31.8%
48.9%
4,8%
100%
Table 2: Results on stochastic games. We outperform baselines on 4 out of games, with an average normalized game score of 32%. Scores averaged across 3 seeds. Baselines were with the latest Jericho version.
0.8
0.7
Pure IL 6
9.5)
XTX moo
0.5
0.4
0.3
0.1
0.0
Zork1
Inhumana
Zork3
Ludicorp
Deephome
Omniquest
Game
Figure 2: Average episode scores for 4 ablation models across 6 games. Overall, 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 always use the imitation learning policy As expected, this model performs quite badly since it based on pure exploitation and is hence unlikely reach deep states the game.
equation meaning the agent will
Pure inverse dynamics (A 1) This ablation sets À 1 in equation hence always using the inverse dynamics exploration policy Tinv-dy: resulting the model proposed in (Yao et al. 202T). 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 (Yao et al. 2021).
Mixing exploration and exploitation (A 0.5) By setting À 0.5, this ablation constantly alter- nates between exploitation and exploration, never committing to one or the other. This causes the agent suffer from issues of both the À 0 and À models, resulting in weak results.
Pure separation of exploitation and exploration (XTX no-mix) In this ablation, we examine the importance of having mixture policy in Phase 1 of the algorithm instead of setting À = 0 in Phase and to 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 and completely gets stuck in the game of Zorkl. This shows it is crucial to have a mixture policy in Phase in order get past bottleneck states difficult games.
CONCLUSION
We have proposed XTX, an algorithm for multi-stage episodic control text adventure games. XTX explicitly disentangles exploitation and exploration into different policies, which are used by the agent for action selection different phases of the same episode. Decomposing the policy allows the agent to combine global decisions which state spaces in the environment to (re- ree))exploe, fol- lowed 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 signifi- cantly outperforms prior methods on the Jericho benchmark (Hausknecht et al. 2020) under both deterministic and stochastic settings, and even surpasses several challenging bottlenecks in games like Zorkl (Ammanabrolu et al. (020). Future work can integrate our algorithm with approaches that better leverage linguistic signals achieve further progress in these games.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the members of the Princeton NLP group and the anonymous reviewers for their valuable feedback. JT was supported by graduate fellowship Princeton University, We are grateful the Google Cloud Research program for computational support in running our experiments. We would also like thank Matthew Hausknecht for all the help regarding the Jericho enviromment.
ETHICAL CONSIDERATIONS
This work focuses on building better agents for text-adventure games and hence does not have im- mediate 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 under- standing (e.g. dialog systems). As such agents become more capable and infuential in our lives, it important to make sure their objectives align with those of humans, and that they are free of bias.
REPRODUCIBILITY
Our code is publicly available here http:::/gttttb..... wtt.ccom///rr/ htt.://hww...ooompiitttttcttooot mulp:iinnntooonn//t/tp- We pro- vide all implementation details such as hyperparameters, model architectures and training regimes in Appendix A.2] We used Weights & Biases for experiment tracking and visualizations to develop insights for this paper.
REFERENCES
Ashutosh Adhikari, Xingdi (Eric) Yuan, Mare-Alexandre Côté, Mikulas Zelinka, Marc-Antoine Rondeau, Romain Laroche, Pascal Poupart, Jian Tang, Adam Trischler, and William L. Hamilton Learning dynamic knowledge graphs generalize on text-based games. In NeurlPS 2020, 2020.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed explo- ration for provable policy gradient learning. arXiv preprint 2rXiv:2007.08459, 2020.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in Neural Informa- fion Processing Systems, 34, 2021.
Prithviraj Ammanabrolu and Matthew J. Hausknecht. Graph constrained reinforcement learning for natural language action spaces. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:
/oopezeview..oo fortm//ormmmmmmmmm B= x6
Prithviraj Ammanabrolu and Mark Riedl. Playing text-adventure games with graph-based deep reinforcement learning. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 3557-3565, Minneapolis, Minnesota, 2019, Association for Computational Linguistics. doi: 10.18863/v1/111-1111 13588-1388. htRl:ttps:/ www.///wwwww..woo//w/ww/wwwwwwww aclweb. org/ anthology/
NI 1358
Prithviraj Ammanabrolu, Ethan Tien, Zhaochen Luo, and Mark O Riedl. How to avoid being caten by a grue: Exploration strategies for text-adventure agents. arXiv preprint arXiv:2002.08795
2020.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Andrew Bolt, et al. Never give up: Learning directed exploration strategies. In International Conference on Learning Rep- resentations, 2020.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying caunt-based exploration and intrinsic motivation. Advances in neural information pro- cessing systems, 29:1471-1479, 2016.
10

---

Published as a conference paper at ICLR 2022
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learnngg envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 2013.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforeement learning. Journal of Machine Learning Research, 3(Oct):221322) 1311 2002.
Cédric Colas, Olivier Sigaud, and Pierre-Yver Oudeyer. GEP-PG: Decoupling exploration and exploitation deep reinforcement learning algorithms. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1039-1048. PMLR, 10-15 Jul 2018. URL https://proceddngs. mwr.rrr............m.. wtt...ppe..///////oaaaa.....
Marc-Alexandre Côté, Ákos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnss, Emery Fine, James Moore, Matthew Hausknecht, Layla EI Asri, Mahmoud Adada, Wendy Tay, and Adam Trischler. Textworld: A learning environment for text-based games. CoRR, 2018.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580-555 5860 2021.
Vincent François-Lavet, Peter Henderson, Riashat Islam, Mare G Bellemare, and Joelle Pineau, An introduction to deep reinforcement learning, arXiv preprint arXiv: 125.1000. 2018
Nancy Fulda, Daniel Ricks, Ben Murdoch, and David Wingate. What can you do with a rock? affordance extraction via word embeddings. In Carles Sierra (ed.), Proceedings of the Twenty- Sixth International Joint Conference on Artificial Intelligence, IJCA 2017, Melbourne, Australia, August 19-25, 2017, pp. 1039-1045. org, 2017. doi: 10.24963/jjcai.2011 2017// //doi oraii.org/1e 10. 249 /ttp///00222333/caaaaa..
https:
Xiaoxiao Guo, Mo Yu, Yupeng Gao, Chuang Gan, Murray Campbell, and Shiyu Chang, Interac- tive fiction game playing as multi-paragraph reading comprehension with reinforcement learn- ing. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Pro- cessing (EMNLP), pp. 7755-7765, Online, 2020. Association for Computational Linguistics. doi: 18.18653/v 12218653/1122020.cem wttp://eeee.mmmminn.....o 2020 emn main. 624
URL httph:t///// wwww aclweb. www.web..w..tttoog.........
Matthew Hausknecht, Ricky Loynd, Greg Yang, Adith Swaminathan, and Jason D Williams. Nail: A general interactive fiction agent. arXiv preprint arXiv: 190.::19020042999 2019.
Matthew Hausknecht, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. Inter- active fiction games: colossal adventure. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05):7903-790) Apr. 2020. doi: 10. 10.1609 w3t.033644099900 URL https:
//ojs. a wrwg/nnneeeeeeeeeeeeeeeee php Aww./AAAAaaiiiiiia
6297
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1621- 1630, Berlin, Germany, August 201 Association for Computational Linguistics doi: 10.18653/ v1/P16- 1153. URL
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1621- 1630, Berlin, Germany, 2016b. Association for Computational Linguistics. doi: 18.18653/v1/ P16-1153. https::::: hwtp//wwwwa/ www.::ww.....................ee.
Mikael Henaff. Explicit explore-exploit algorithms in continuous state spaces. arXiv preprint arXiv:1911.00617, 2019.
Vishal Jain, William Fedus, Hugo Larochelle, Doina Precup. and Mare G. Bellemare. Algorithmic improvements for deep reinforcement learning applied interactive fiction. In The Thirty-Fourth
11

---

Published as a conference paper at ICLR 2022
AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applica- tions of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educa- tional Advances in Artificial Intelligence, EAAI 2020, New York, NY. USA, February 7-12, 2020, pp. 4328 4336. AAAI Press, 2020. URI. htt hatp:://aaa..orroo wwwp//////nnn////ieooiio.inneiis php/ AAAT/ siticceeviin article/view/8555
Youngsoo Jang, Seokin Seo, Jongmin Lee, and Kee-Fung Kim. Monte-carlo planning and learning with language action value estimates. In International Conference Learning Representations, 2020.
Ray Jiang, Tom Zahavy, Zhongwen Xu, Adam White, Matteo Hessel, Charles Blundell, and Hado Van Hasselt. Emphatic algorithms for deep reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139. PMLR, 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2):209-232, 2002.
Jing Li, Xinxin Shi, Jiehao Li, Xin Zhang, and Junzheng Wang. Random curiosity-driven explo- ration in deep reinforcement learning. Neurocomputing, 418: 139-147, 2020.
Marlos C. Machado, Marc G. Bellemare, and Michael Bowling. Count-based exploration with the successor representation. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):
5125-5133, Apr. 2020. doi: 10.1609/aaai. ht4p://a....3344....... v34i04.5955. URL https:// aaaii org/ index.php/ http://AAA/artteeeeeeeeee///////
Andrea Madotto, Mahdi Namazifar, Joost Huizinga, Piero Molino, Adrien Ecoffet, Huaixiu Zheng, Alexandros Papangelis, Dian Yu, Chandra Khatri, and Gökhan Tür. Exploration based language learning for text-based games. In Christian Bessiere (ed.), Proceedings the Twemy-Ninth Inter- national Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 1488 1494. ijcai. 2020. doi: 0..24963/icaai22220222
10 240.2229990 249 htl.tttts://aoi..o htt.:///.........../2222/2//////
Karthik Narasimhan, Tejas Kulkarni, and Regina Barzilay. Language understanding for text-based games using deep reinforcement learning. In Proceedings of the 2015 Conference on Empir- ical Methods in Natural Language Processing, pp. 1-11, Lisbon, Portugal, 2015, Association for Computational Linguistics. doi: 10.18653/v1/D15-1100 1001. URL. https: //www acl web.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In International Conference on Machine Learning, pp. 3878-3887. PMLR, 2018.
Philip Osborne, Heido Nömm, and Andre Freitas. A survey of text games for reinforcement learning informed by natural language. arXiv preprint arXiv:2109.00 09478, 2021.
Deepak Pathak. Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pp. 2778-2787. PMLR, 2017.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners, 2019.
Lukas Schäfer, Filippos Christianos, Josiah Hanna, and Stefano V. Albrecht. Decoupling exploration and exploitation reinforcement learning. CoRR, Abs/2107.08966 2021. URL https::/
arxiv. wtw.vvv.rggabb////u// 08966
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay, arXiv preprint arXiv:1511.059%) 2015.
Lior Shani, Yonathan Efroni, and Shie Mannor, Exploration conscious reinforcement learning visited. In International Conference on Machine Learning, pp. 5680-5689, PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
12

---

Published as a conference paper at ICLR 2022
Adrien Ali Taiga. William Fedus, Marlos C Machado, Aaron Courville, and Mare G Belle- mare. On bonus-based exploration methods in the arcade learning environment. arXiv preprint 0rXhv:2109.11052. 2021.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In 31st Conference on Neural Information Processing Systems (NIPS), volume 30, pp. 2017.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
William Whitney, Michael Bloesch, Jost Tobias Springenberg, Abbas Abdolmaleki, and Martin A. Riedmiller. Decoupled exploration and exploitation policies for sample-efficient reinforcement learning. CoRR, abs/2 0.9458, 2021. URL
Yunqiu Xu, Meng Fang. Ling Chen, Yali Du, Joey Tianyi Zhou, and Chengqi Zhang. Deep rein- forcement learning with stacked hierarchical attention for text-based games. Advances in Neural Information Processing Systems, 33, 2020.
Yunqiu Xu, Meng Fang, Ling Chen, Yali Du, and Chengqi Zhang. Generalization in text-based games via hierarchical reinforcement learning. arXiv preprint rxXiv22009009968 2021.
Shunyu Yao, Rohan Rao, Matthew Hausknecht, and Karthik Narasimhan. Keep CALM and explore: Language models for action generation in text-based games. In Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing (EMNLP), pp. 8736-8754, Online, November 2020. Association for Computational Linguisties. doi: 10.18653/v 120020.emmlp-mmt.... main. 704. URL htt.ttss//aaaaaaoollaaacoo owtp:/llooooo..//2222/// emn in. 704.
Shunyu Yao, Karthik Narasimhan, and Matthew Hausknecht. Reading and acting while blind- folded: The need for semantics in text game agents. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, pp. 3097-3102, Online, June 2021, Association for Computational Linguis- tics. doi: 10.18653/v1/2022 1ww.022...aaal--oo..m m4in..27
URL https: Teetps::/aclanthhlooyy org/2021.
naacl-main. 247
Xingdi Yuan,
Côté, Alessandro Sordoni, Romain Laroche, Remi Tachet des Combes, Matthew J. Hausknecht, and Adam Trischler. Counting to explore and generalize in text-based games. CoRR, 2018
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J. Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances Neural Information Processing Systems 31: Annual Conference on Neural Infor- mation Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp.
3576, 2018. URL Abst htm)
www.iinngss.nuiiinee neurips. wccppaper///1////
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1
GAME STATISTICS
Game
ZORKI 9/51
INHUMANE 14/28
LUDICORP 4/45
LIBRARY 5/6
ZORK3 39/4 /4
PENTARI 5/16
Avg/Max
Game
DETECTIVE 2/5
BALANCES 12/54
DREPHOME 6/53
ENCHANTER 15/40
DRAGON 9/24
OMNIQUEST 13/26
Avg/Max
Table 3: Average and maximum number of steps between rewards for games in Jericho (based on human walkthroughs). Several games have long sequences of actions without reward.
Table 3 contains the average and maximum number of steps between rewards in these games, show- casing their challenging nature.
A.2 IMPLEMENTATION DETAILS
We use learning rate of 10 and 10 for Ta and -y respectively. Both policies are trained on batches of size 64, with hidden dimensions size 128. The scaling coefficient 01 for the inverse
dynamics intrinsic reward is set to 1 for all games except for Deephome (01 0.1), Enchanter
(01 0.5), Omniquest (a1 = 2), Ludicorp (a1 0.5). Detective (a1 = 2), and Pentari (ar 2). The Transformer गi has 3 layers and attention heads. 31 in equation iis set to 1, .2 in equation
set to 10k to encourage picking the shortest length trajectory, and is set to 10. equation 6 The priority fraction is set to 0.5. Every time тa is trained, episode length T to have at least remaining steps of exploration by setting T Imax + R, where max 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 RC-DQN which for 100k interaction steps following Guo et al. (2020).
a1 02
also scale the
A.3
FULL SET OF ABLATIONS
0.8
Ablation
Pore 0)
Nomalzze Score
0.6
Pure Inv Dy 1t 11
XTX (novmbi))
0.4
XIX (fui model)
0.2
0.0
Zork1
Inhumane
Zork3
Ludicorp
Deephome
Omniquest
Game
Normalized Score
0.8
0.6
0.4
0.0
Enchanter
Pentari
Balances
Detective
Library
Dragon
Game
Figure Average episode scores for ablation models across 12 games. Overall, find both the strategic inverse dynamics policy and the explicit exploitation policy to be key for our algorithm. Scores for dragon were clipped be between 0 and 1.
14

---

Published as a conference paper at ICLR 2022
A.4
ABLATION TRAINING PloTs
Avg. Episode Score
XTX (full model)
Pure IL (A 0) - Mix (A 0.5)
Pure Inv Dy (A = 1) XTX (no-mix)
120
100
80
40
20
Step
20k
40k
60k
80k
100k
Figure 4: Average episode throughout training for all ablations Zorkl. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy ( 1) - XTX (no-mix)
60
40
20
Step
20k
40k
60k
80k
100k
Figure 5: Average episode score throughout training for all ablations on Inhumane. Shaded areas indicate standard deviation.
15

---

Published as a conference paper at ICLR 2022
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) XTX (no-mix)
4
Step
20k
40k
60k
80k
100k
Figure 6: Average episode score throughout training for all ablations on Zork3. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model) Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) - XTX (no-mix)
80
60
40
20
Step
20k
40k
60k
80k
100k
Figure 7: Average episode score throughout training for ablations on Ludicorp. Shaded areas indicate standard deviation.
16

---

Published as a conference paper at ICLR 2022
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) XTX (no-mix)
25
20
15
10
5
Step
0
20k
40k
60k
80k
100k
Figure 8: Average episode score throughout training for all ablations on Balances. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) - XTX (no-mix)
80
60
40
20
Step
20k
40k
60k
80k
100k
Figure 9: Average episode score throughout training for all ablations on Deephome. Shaded areas indicate standard deviation.
17

---

Published as a conference paper at ICLR 2022
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) XTX (no-mix)
300
250
150
100
Step
0
20k
40k
60k
80k
100k
Figure 10: Average episode score throughout training for all ablations on Detective. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) - XTX (no-mix)
80
60
40
20
Step
20k
40k
60k
80k
100k
Figure 11: Average episode score throughout training for ablations on Enchanter. Shaded areas indicate one standard deviation.
18

---

Published as a conference paper at ICLR 2022
Avg. Episode Score
XTX (full model)
Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A 1) XTX (no-mix)
12
10
6
Step
0
20k
40k
60k
80k
100k
Figure 12: Average episode score throughout training for all ablations on Omniquest. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model)
Pure IL (A 0) Mix (A =0.5)
Pure Inv Dy (A 1) - XTX (no-mix)
50
40
30
20
10
Step
20k
40k
60k
80k
100k
Figure 13: Average episode score throughout training for all ablations on Pentari. Shaded areas indicate standard deviation.
19

---

Published as a conference paper at ICLR 2022
Avg. Episode Score
XTX (full model) Pure IL (A = 0) Mix (A = 0.5)
Pure Inv Dy (A = 1) XTX (no-mix)
100
50
0
-50
Step
20k
40k
60k
80k
100k
Figure 14:
Average episode score throughout training for all ablations on Dragon. Shaded areas indicate one standard deviation.
Avg. Episode Score
XTX (full model)
Pure IL (A 0) - Mix (A 0.5)
Pure Inv Dy (A = 1) XTX (no-mix)
25
20
15
10
Step
20k
40k
60k
80k
100k
Figure 15: Average episode score throughout training for all ablations Library. Shaded areas indicate one standard deviation.
20

---

Published as a conference paper at ICLR 2022
A.5 FULL DETERMINISTIC AND STOCHASTIC RESULTS
Gameo
Ang
DERN
Any
INV-DY
RC-DON
Any
XTE- XTp-Usilm
AYE
XTX couns
Max
A
Game Max
ZOREI
22.3
55. 0.44
44.1 (33.0
IIE. (153)
4127 10.01
330 154)
341.:55
$3.5
1034 10L5
1557 11-21
4175
150
DNEUSSANE
56.8
(6-37
2522 15.3)
(4.37
25.8 (2.30
13.3-4.5
76.7
+55
15..00 15
35.8 (0/7)
13.011.1
338:3-71
21.
23. m0
+75
Zora3
03 13:0200
4.705.5
0.200.5
33 01.2
4.7 00.30
5.0 1100
475
0:30m
0.5.0 13
00003:00
1040
5.:00:0
1.
10:00
+75
PENTARI
43.5/155
52.3
56.3
53.315.21
23.4 16.0
46.7 15.23
43-
00.01200
01.-11.5
4350
166-910111
111.3
386770
717-5
3123:00
142019-71
+35
SALANCIS
(3.4)
13.3
25.0 (022
350 00.11
18,21222 12-)
20.9
25.012.0
24.
145
LIBEARY
12.3-033
170 13
31.
16:211:4
310 (311
21.0000
16.103 03
218.01 10
475
17.90..1 6
06.31 10.55
T6.0 (5.05
1:000:5
1.500:5:
05..09
60.715-7
76.3 15
655
300
58..00
06:0 11
72.7
1:001.5
1:5H0:00
20.0088
70
+85
ENCRANTEES
03.01.3
66.7 (7-4)
63 5:30 60
11.911.0
38.32477
36. 100
(1.3
53. 735
66.7 131.0
+75
400
-32 1044
8.31 82.00
$7/11-7
8.5HOLS
407
1280
10.0
Table 4: Full Deterministic Results. Standard deviations are in parentheses. Scores are averaged across 3 seeds. Note that the average normalized scores only take into account the games listed in Table Baselines were rerun with the latest Jericho version.
Gamao
Arg
DERN
Mas
Are
INV-DY
RC-DDO
Any
XTE-Usibm
AVE
XTTX (ours)
Max
(5)
Game Mas
ZoRaI
(3.3
(3.3
36,9 12-4)
$5-7114.5)
40:-
330 1300
31.2
25.1.310
60.3 (5:00
1458 (H4T)
+5%
150
0.2
10-23
3.8-3.0
1:304:1
40-001
67700m
18:00
0.8.0
37.0.15
4:4055
(0/5)
(2/0)
-15
PENTAAI
03.3
66.8 015
283 03.31
45:9-000
31.21339
38.1
354-133)
90.-1110
48.3 (3.40
048-0310
45%
Dusmous
58.200.00
75.0157)
(3.5)
1.000.06
1.500:5
62.0114.2)
(1
+50
4301 (380)
66.1 01.31
3644 04.53
13.8 (1-41
1.30100
1.50000
10.712.3
09.3-0.0
78.9 22.35
64%
100
EXCRANTER*
42/0
56.7
34.3
393 23.80
29.1 12.71
43. 18.50
39.2
45.9.2244)
44.8 135-41
98.3 223.0
4200
Nomn
11.5 (700
1556
Table Full Stochastic Results. Standard deviations are parentheses. Scores are averaged across 3 seeds. Note that the average normalized scores only take into account the games listed in Table Baselines were rerun with the latest Jericho version.
A.6 AGGREGATE METRICS & PERFORMANCE PROFILES
Median
IQM
Mean
Optimality Gap
XTX
XTX-Uniform RC-DON
INV-DY
DRRN
0.24 0:32 0.40 0,48 0.56 0.24 0.32 0.40 0:48 0.56
0.30 0.36 0.42 0.48 0.54
0.48 0.54 0.60 0.66 0.72
Normalized Score
Figure 16: Aggregate metries with 95% CIs for the deterministic games listed in Table I follow- ing Agarwal et al. (2021). The Cls use percentile bootstrap with stratified sampling.
Median
Optimality Gap
XTX
XTX-Uniform RC-DON
INV-DY
DRRN
0.12 0.15 0.18 0.21
0.12 0.20 0.24 0.28 0.24
0.20 0.24 0.28 0.32
0.68 0.72 0.76 0.80 0.84
Noralized Score
Figure 17: Aggregate metries with 95% CIs for the stochastic games listed in Table ing Agarwal al. (2021). The CIs use percentile bootstrap with stratified sampling.
2 follow-
21

---

Published as a conference paper at ICLR 2022
1.00
INVDY
XTX-Uniform
RC-DON
Fraction runs with score
0.75
0.50
0.25
0.00
0.0
0.2
0.6 Avg. Normalized Score (7)
0.4
0.8
1.0
Figure 18: Performance profiles based on score distributions for the deterministic games listed in Table following AAaawal et al. (2021). Shaded regions show pointwise 95% confidence bands based on percentile bootstrap with stratified sampling.
1.00
DRAN
XTX Uniform
XTX
RC-DON
Fraction of runs with score
0.75
0.50
0.25
0.00
0.0
0.2
0.4 Avg. Normalized Score (v)
0.6
0.8
1.0
Figure 19: Performance profiles based on score distributions for the stochastic games listed in Table following Agarwal et al. (2021). Shaded regions show pointwise 95% confidence bands based on percentile bootstrap with stratified sampling.
22


Reviews:
[{"review_id": "xMrrbzgABl_", "reviewer": "Reviewer_PsKh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution is an exploration strategy with an in-episode switch from an exploitation policy to one aimed at exploration. This approach to combining exploration and exploitation is different from much of the existing literature, where typically a single policy is used throughout the episode, and often throughout training, that merges two reward signals. Since the switching policy in this paper is the element that looks most hardcoded, and therefore potentially brittle, it would be valuable to investigate a bit more whether a more flexible solution is also possible here. While different, Agent57 (whose predecessor NGU is cited) might offer inspiration here: it also uses multiple policies, and manages the switching with a learned (bandit) mechanism. A significant difference is that there the switching only happens between episodes, but a similar switching mechanism might be considered here within episodes nonetheless.\n\nThe in-episode switch is there to ensure that exploration happens at the edge of the known region of state space, where it is needed and meaningful. That is a very sensible thing for the agent to do, but there are other exploration strategies that effectively also do that, such as random network distillation (Burda et al., 2018) and inverse dynamics (Pathak et al., 2017), which the authors use to train their exploration policy. While the exploration region is less explicitly located at the edge of the known state space region in those algorithms than in this paper, the prediction errors that they rely on for intrinsic reward generation are more likely to occur at that edge. One question I have for the authors here is whether the inverse dynamics reward signal itself can be used to indicate when to switch from explore to exploit. In that case, the two-policy solution can be simplified again to a single policy that merges the two behaviours. I did not see this ablation in the paper, but I believe it would be a good thing to include.\n\nConversely, it would be valuable to see the performance of the strategy proposed here on other exploration benchmarks, such as the hard exploration games from the Atari suite (Bellemare et al., 2016). While I appreciate that text adventure games are in some ways different from their video counterparts, since they have a different observation space (language, not pixels) and action set (again language, not moves), they are still both RL environments, and general agents should be able to play both. Furthermore a game like Montezuma’s Revenge has a bottleneck aspect similar to the one that many text based games have, as well as the need for exploration on the frontier of the known region of state space. All in all it seems that the proposed strategy here could work on a wider range of environments than addressed in the paper. If that is not the case, it is still a valuable contribution, but if it is, it would be good to know.\n\nA last comment: the agent proposed in the paper has another unusual feature in that its exploitation policy is trained only by self-imitation. While it is important to find the edge of the explored region of state space, and the self-imitation training regime can help with this, the XTX strategy can also be implemented with an exploitation policy that is trained in a more traditional way, with one of the many RL approaches available. Can the authors comment on why they chose the self-imitation approach instead?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is well written, presents a marked improvement over the baselines provided (I’m not sufficiently familiar with the text adventure game literature to be certain those represent state of the art, but I will assume they do unless corrected), and provides an interesting approach to the exploration problem through the two-policy architecture. I recommend acceptance, but I also feel the paper could be strengthened by addressing the questions raised in the main review section.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "w95EgrMj1TL", "reviewer": "Reviewer_TAdH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well motivated and most parts are well written, but the main method section is written to be difficult to follow. The results demonstrate empirical gains in the Jericho environment. However, the baselines consist only of simple algorithms without an exploration strategy. The detailed comments and questions are as follows:\n\n1. In the experiment, the performance is compared with DRRN and MPRC-DQN, which lack exploration strategy. XTX seems to be an exploration method very similar to Go-Explore. Moreover, in the paper, Go-Explore and PC-PG are mentioned as the most closely related approaches, but they are excluded from the baseline algorithms. It would be better to demonstrate the results of them together.\n\n2. (Page 5, section 3.1.2, sampling trajectories) It is hard to follow the explanation. Can it be understood as a kind of weighted behavior cloning? Moreover, I understand the motivation of biased sampling towards high scores, but don’t understand the motivation for the length. I think that a shorter trajectory length is not necessarily better. Can you give an intuitive explanation?\n\n3. In the paper, policy $\\pi_\\text{il}$ is modeled as GPT-2, and policy $\\pi_\\text{inv-dy}$ is modeled as DRRN. Is there any reason why each policy is modeled differently? Especially, the policy $\\pi_\\text{il}$ is renormalized over the valid action set, is there any reason or advantage to learn the policy with GPT-2?\n\n4. In the experiments, the results demonstrate XTX underperforms DRRN on ENCHANTER. Is there any intuitive explanation for this result? It would be better if a discussion about what characteristics in the ENCHANTER made the XTX not work would be added.\n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This paper is well-motivated, written overall, and demonstrates state-of-the-art performance in the Jericho environment. However, there are relevant but missing baseline algorithms (Go-Explore, PC-PG) for the main table of experiments. I think the results of these algorithms should also be included in the main table, and I think this can further support the main arguments of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UITF31OhBG0", "reviewer": "Reviewer_186e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\nThe paper is generally well-written and easy to follow. \nThe novelty of XTX is clearly elaborated.\nThe method surpasses the existing method with a large margin on text-based games. The ablation studies show the individual components introduced by XTX can bring improvements.\n\nCons:\n\nOne weakness of the paper is these experiments did not clarify why the novel part of XTX (i.e. exploration with novelty bonus on the frontier) is helpful over random actions. The paper hypothesizes that novelty bonuses can encourage the agent to select promising actions in large action spaces. However, the ablation study (Figure 2) casts doubts on this hypothesis. XTX brings significant improvements over Go-explore in Zork1 but not other games. The difference doesn't seem to be correlated to the size of action spaces.\n\nQuestions:\n\nI don't fully get why the method is motivated to solve the problems with large action space. How can an agent receive a novelty bonus if it did not enter that novel state by trying random actions? Do the authors assume the generalization of the neural network plays a key role here?\n\nOther Suggestions:\n\nThe author might want to try other hard-exploration tasks. For example, minigrid or maze can be tested, if not Atari games like Montezuma Revenge. Since these are environments where existing exploration methods are developed, we can have a better understanding of how exactly XTX compares to other exploration algorithms, rather than the existing text-base game agent without directed exploration.\n\n", "summary_of_the_paper": "Summary:\n\nThe 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.\nConceptually, XTX is a method that extends Go-Explore which only acts randomly after reaching the frontier of familiar states.\nThe 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.\nEmpirically, XTX shows strong performance on a large set of text-based games.", "summary_of_the_review": "Reason for the Score:\n\nThe write-up and experiments in this paper are of good quality. The method itself is novel and the empirical finding in this paper might be particularly interesting for the audience of text-based RL. I have minor concerns author's claim about why this method works better than existing exploration algorithms while I'm happy to increase the score if they are addressed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7DQt6IC0PVW", "reviewer": "Reviewer_Exgo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. The disentanglement of exploration and exploitation makes sense. The phase-alternating pipeline is nicely designed. \n2. The paper is clearly written, it is relatively easy to understand how the model look like (although the intuition of each component isn't too clear). \n3. The set of ablation experiments in Section 4.2 are well designed. \n\n**Questions and concerns**\n\n1. What's the reason of choosing this subset of 12 games? While the list seems to cover a wide range of game difficulties, but why not using the entire Jericho suite?\n2. The authors cited the INV-DY agent (Yao et al., 2021) in their Section 3.1.3, and actually, if I understand correctly, the entire Section 3.1.3 is describing Yao et al.'s model, without any new contribution. Why do not the authors compare their agent with INV-DY in result tables?\n3. In Section 3.1.PHASE 1, the authors describe two criteria that switch the agent to exploration phase. Can the authors elaborate on the second criterion, what does it mean if the number of steps in an episode equal to the longest of the $k$ sampled trajectories? If an agent moves back and forth between two locations, which may result a super long steps, but this behavior is not necessarily desired. \n4. In Section 3.1.2, Sampling trajectories, the authors describe the way they use to sample trajectories. However, to my understanding, the loss shown in Eqn. 5 is a game-step-wise loss. Does the authors also sample game steps from the sampled trajectories (if so, how?), or they compute this loss on all game steps within the sampled trajectories?\n5. In the paragraph under Eqn. 2, the authors mentioned that \"Note that the action distribution over actions $a$ induced by $\\pi_{inv-dy}$ is conditioned only on the current observation $o$\". However, according to Eqn. 6, it is also conditioned on $o'$, which is the next observation, i.e., $o_{t+1}$. \n\n\n\n**References**\n1. Keep CALM and explore: Language models for action generation in text-based games. Shunyu Yao, Rohan Rao, Matthew Hausknecht, and Karthik Narasimhan. EMNLP 2020. \n2. Reading and acting while blindfolded: The need for semantics in text game agents. Shunyu Yao, Karthik Narasimhan, and Matthew Hausknecht. NAACL 2021.  \n\n\n---------------------------- Nov 29, 2021\nWe had a good discussion among reviewers, let me give the authors some update.\n\n**1.  Increased my score to 6.** This is because the authors have somewhat addressed my comments, I'm relatively satisfied. There are a few concerns remaining, as listed below:\n\na) on modelling novelty: the novel components are only a) the sampling strategy in exploitation phase and b) the two-phase pipeline. It was a bit weird to (almost) \"copy and paste\" a subsection from a prior work into the main body of this submission, which may confuse readers by giving a false message about the contribution. However, if other co-reviewers are fine with it, I'm fine too. \n\nb) After a few paper updates, the main results (in Table 1) is only marginally higher than prior work. The authors can add more discussion addressing this in their cameraready.\n \n**2.  We recommend the authors to remove the Dragon row from the result tables** (or rerun when the Jericho team fixes the bug):\n\nAs Reviewer PsKh find out, the proposed agent's scores exceed the max score on that game. \n\nI happen to know some core Jericho contributors, and we tested the [Dragon game](https://ifdb.org/viewgame?id=sjiyffz8n5patu8l). \n\nUsually, when reaching the goal, this will pop up:\n\n```\nDragon's Treasure Store\n\nThe Dragon's secret hoard is open before you. By the flickering light of your little candle, you can make out a heaps of treasure stacked untidily around the floor.\nYou can see piles of gold and heaps of jewels, many rising higher than the top of your head. The Dragon has told you it has no use for the treasure and it is now yours.\n\nYou are rich beyond your wildest dreams!\n\n*** You have won ***\n\nIn that game you scored 25 out of a possible 25, in 101 turns.\n\nWould you like to RESTART, RESTORE a saved game, UNDO your last move, give the FULL score for that game or QUIT\n```\n\nIn that game, the scoring function works like this:\n```\n1 for buying the box\n1 for finding the screwdriver\n2 for finding the candle\n1 for finding the matches\n1 for for opening the castle door\n1 for building the hand-glider in the right place\n2 for getting the sword/booklet\n1 for escaping from the tower using the hang-glider\n2 for killing the Troll to get the horn\n5 for talking to the Troll to get the horn\n2 for killing the dragon\n5 for charming the dragon instead of killing him\n5 for finding the treasure\n\n= 25 points maximum total (e.g., multiple ways to get the horn)\n\n(minus 2 points for each RESCUE or 'dead' recovery)\n```\nGiven this -2 points for each RESCUE action, an agent can get negative total points. Because the original game did some *short* to *unsigned char* converting, this caused underflow (-128 vs. 128). \n\nThis may because the author of the Dragon game (in 2003) didn't expect machines to play his game, because most humans will give up playing before reaching this underflow point :)\n\nSo the weird numbers are not the authors' problem. As I mentioned, they can either remove that row, or to rerun whenever Jericho fixes that. \n", "summary_of_the_paper": "In this paper, the authors propose eXploit-Then-eXplore (XTX), a training strategy for agent solving human-generated text-based games. \n\nXTX consists of two training phases:\n\n1. 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. \n\n2. 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)$.\n\nDuring 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. \n\nOn a subset of games from the Jericho suite, the authors show their agent outperform prior works. \n", "summary_of_the_review": "While I like this paper in general, my main concern is its novelty and contribution. As mentioned in my questions and concerns (Q2) above, the entire Section 3.1.3 is describing prior work (Yao et al., 2021), the \"Learning from trajectories\" part of Section 3.1.2 is describing another prior work (Yao et al., 2020). Actually, neither (Yao et al., 2021) nor (Yao et al., 2020) is compared in result table. As a consequence, to my understanding, the contribution of this paper is the two-phase pipeline and the sampling strategies in Section 3.1.2. I am not sure if this paper contains enough contributions to publish at ICLR. \n\nPlease correct me if I understood wrong. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for their submission and active participation in the discussions. All reviewers are unanimously leaning towards acceptance of this paper. Reviewers in particular liked that the paper is well-written and easy to follow [186e,TAdH,Exgo], well motivated [TAdH], interesting [PsKh], novel [186e] and provides gains over baselines [186e,TAdH,PsKh] with interesting ablations [186e,Exgo]. I thus recommend accepting the paper and  I encourage the authors to further improve their paper based on the reviewer feedback.
Decision: Accept (Spotlight)