How to Avoid Being Eaten by a Grue: Structured Exploration Strategies for Textual Worlds
Authors: Prithviraj Ammanabrolu
Ethan Tien
Matthew Hausknecht
Mark Riedl
Venue:  (2021)
Keywords: text-based games
reinforcement learning
exploration
intrinsic motivation
knowledge graphs
question answering
natural language processing

Abstract: Text-based games are long puzzles or quests, characterized by a sequence of sparse and potentially deceptive rewards. They provide an ideal platform to develop agents that perceive and act upon the world using a combinatorially sized natural language state-action space. Standard Reinforcement Learning agents are poorly equipped to effectively explore such spaces and often struggle to overcome bottlenecks---states that agents are unable to pass through simply because they do not see the right action sequence enough times to be sufficiently reinforced. We introduce Q*BERT, an agent that learns to build a knowledge graph of the world by answering questions, which leads to greater sample efficiency. To overcome bottlenecks, we further introduce MC!Q*BERT an agent that uses an knowledge-graph-based intrinsic motivation to detect bottlenecks and a novel exploration strategy to efficiently learn a chain of policy modules to overcome them. We present an ablation study and results demonstrating how our method outperforms the current state-of-the-art on nine text games, including the popular game, Zork, where, for the first time, a learning agent gets past the bottleneck where the player is eaten by a Grue.

Under review as a conference paper at ICLR 2021
HOW TO AVOID BEING EATEN BY A GRUE: STRUCTURED EXPLORATION STRATEGIES FOR TEXTUAL WORLDS
Anonymous authors Paper under double-blind review
ABSTRACT
Text-based games are long puzzles or quests, characterized by a sequence of sparse and potentially deceptive rewards. They provide an ideal platform to develop agents that perceive and act upon the world using combinatorially sized natural language state-action space. Standard Reinforcement Learning agents are poorly equipped to effectively explore such spaces and often struggle to overcome bottlenecks- states that agents unable to pass through simply because they do not see the right action sequence enough times to be sufficiently reinforced. We introduce Q"BERT, agent that learns to build knowledge graph of the world by answering questions, which leads to greater sample efficiency. To overcome bottlenecks, we further intrinsic
introduce MCIQ*BERT an agent that uses an knowledge-graph-boe motivation to detect bottlenecks and a novel exploration strategy to efficiently learn a chain of policy modules overcome them. We present an ablation study and results demonstrating how our method outperforms the current state-of-the-art on nine text games, including the popular game, Zork, where, for the first time, a learning agent gets past the bottleneck where the player is eaten by Grue.
INTRODUCTION
Text-adventure games such as Zorkl (Anderson et al., 1979) (Fig. 1) are simulations featuring language-basse baaagd state and action spaces. Prior game playing works have focused on few chal- lenges that are inherent to this medium: (1) Partial observability the agent must reason about the world solely through incomplete textual descriptions (Narasimhan et al., 2015; Côté et al., 2018; Ammanabrolu Riedl, 2019b). (2) Commonsense reasoning to enable the agent to more intelligently interact with objects in its surroundings (Fulda et al., 2017; Yin & May, 2019; Adolphs & Hofmann, 2019; Ammanabrolu & Riedl, 2019a). (3) A combinatorial state-action space wherein most games have action spaces exceeding billion possible actions per step: for example the game Zork/ has 1.64 x 1014 possible actions at every step (Hausknecht et al., 2020; Ammanabrolu & Hausknecht, 2020). Despite these challenges, modern text-adventure agents such as KG-A2C (Ammanabrolu & Hausknecht, 2020), TDQN (Hausknecht et al.. 2020), and DRRN (He et al., 2016) have relied on surprisingly simple exploration strategies such as e-greedy or sampling from the distribution of possible actions.
Most text-adventure games have relatively linear plots in which players must solve a sequence of puzzles to advance the story and gain score. To solve these puzzles, players have freedom to explore both new areas and previously unlocked areas of the game, collect clues, and acquire tools needed to solve the next puzzle and unlock the next portion of the game. From a Reinforcement Learning perspective, these puzzles can be viewed as bottlenecks that act as partitions between different regions of the state space. We contend that existing Reinforcement Learning agents that are unaware of such latent structure and are thus poorly equipped for solving these types of problems.
In this paper we introduce two new agents: Q*BERT and MC!Q*BERT, both designed with this latent structure in mind. The first agent, Q*BERT, improves on existing text-game agents that use knowledge graph-based state representations by framing knowledge graph construction during exploration question-answering task. To train BERT' knowledge graph extractor, we introduce the tricho--AA dataset for question-answering in text-games. We show that it leads improved knowledge graph

---

Under review as a conference paper at ICLR 2021
accuracy and sample efficiency compared to prior methods for constructing knowledge graphs in text-games (Ammanabrolu & Riedl, 2019b).
However, improved knowledge graph accuracy not enough to overcome bottlenecks; does not improve asymptotic performance. To this end, MC!Q" BERT (Modular policy Chaining! Q*BERT) extends Q*BERT by combining two innovations: (1) an intrinsic motivation based on expansion of its knowledge graph both way to encourage exploration as well as a means for the agent to self-detect when is stuck; and (2) by additionally introducing a structured ex- ploration algorithm that, when stuck on a bot- tleneck, will backtrack through the sequence of states leading to the current bottleneck, in search of alternative solutions. As "CCIQ*BERT overcomes bottlenecks, it constructs a modu- lar policy that chains together the solutions to multiple bottlenecks. Like Go Explore (Ecoffet al., 2019), MC!Q*BERT relies on the deter- minism present in many text-games to reliably revisit previous states. However, we show that ability to detect bottlenecks via the knowledge graph state representation enable it to outperform such alternate exploration strategies on nine different games.
Observation: West of House You standing open field west of a white house, with hoarded front door. There is small mailbox here.
Action: Open mailbox
Observation: Opening the small mailbox reveals leaflet.
Action: Read leaflet
Observvttinn: (Taken) "WELCOME TO ZORK: ZORK is game adventure, danger,
cunning. it you explore some of the most amazing territory ever seen by mor- tals. computer should be without one!"
Action: Go north
Observation: North of House You are facing the north side There is here, the windows are boarded up. To the north narrow path winds through the trees.
Figure 1: Excerpt from Zorkl.
Our contributions are as follows: 1) We develop an improved knowledge-gras -raah extraction procedure based on question answering and introduce the open-source Jericho-QA training dataset. 2) We show that intrinsic motivation reward based on knowledge graph expansion is capable of reliably identifying bottleneck states. 3) Finally, we show that structured exploration in the form of backtracking can be used to overcome these bottleneck states and reach state-of-the-ar levels of performance on the Jericho benchmark (Hausknecht et al., 2020).
UNDERSTANDING BOTTLENECK STATES
Overcoming bottlenecks is not as simple as selecting the correct action from the bottleneck state. Most bottlenecks have long-range dependencies that must first be satisfied: Zork/ for instance features a bottleneck in which the agent must pass through the unlit Cellar where a monster known as Grue lurks, ready to eat unsuspecting players who enter without light source. To pass this bottleneck the player must have previously acquired and the latern. Other bottlenecks don't rely on inventory items and instead require the player to have satisfied external condition such visiting the reservoir control to drain water from a submerged room before being able to visit it. In both cases, the actions that fulfill dependencies of the bottleneck, e.g. acquiring the lantern draining the room, are not rewarded by the game. Thus agents must correctly satisfy all latent dependencies, most of which are unrewarded, then take the right action from the correct location overcome such bottlenecks. Consequently, most existing agents regardless of whether they use a reduced action space (Zahavy et al., 2018; Yin & May, 2019) or the full space (Hausknecht et al., 2020; Ammanabrolu & Hausknecht, 2020) have failed to consistently clear these bottlenecks.
To better understand how design algorithms that pass these bottlenecks. we first need gain a sense for what they are. We observe that quests in text games can be modeled in the form of dependency graph. These dependency graphs are directed acyclic graphs (DAGs) where the vertices indicate either rewards that can be collected or dependencies that must be met to progress and are generally unknown to a player a priori. text-adventure games the dependencies are of two types: items that must be collected for future use, and locations that must be visited. An example of such graph for the game of Zork/ can found in Fig. 2. More formally, bottleneck states are vertices in the dependency graph that, when the graph is laid out topographically. are (a) the only state a level, and (b) there is another state at a higher level with non-zero reward. Bottlenecks can be mathematically expressed as follows: let D (V, F)) be the directed acyelic dependency graph for a particular game
2

---

Under review as a conference paper at ICLR 2021
Loc: Focsst Path None
Golden
+05
Loc: Tral Room Irx. Lamp, Bward
relger
Loc:
Noww
Bchind None
Oue
Küshen Inc. None
+10
perword nadgas
Kay Rotteracko
Loct Gallery InstLams, Sword Fuinding
Figure 2: Portion of the /ork/ quest structure visualized as a directed acyelic graph. Fach node represents a state; clouds represent areas of high branching factor with labels indicating some of the actions that must be performed to progress
where each vertex is tuple (s), ss r()) containing information on some state such that st are location dependencies, 8; are inventory dependencies, and r(s) is the reward associated with the state. There is directed edge meets the requirements 9j and 8; of the terminating vertex. 'D can be topologically sorted into levels L == (1,,...,4..) where each level represents set of game states that are not dependant on each other. We formulate the set of all bottleneck states in the game:
E between any two vertices such that the originating state
B {b: (14 1, V) ( s. (j>ijiAnA 0)))
This reads as the set of all states that that belong to a level with only one vertex and that there exists some state with a non-zero reward that depends on it. Intuitively, regardless of the path taken get to bottleneck state, any agent must pass it in order to continue collecting future rewards. Behind House is example of bottleneck state as seen Fig. The branching factor before and after this state is high but is the only state through which one can enter the Kitchen through the window.
RELATED WORK AND BACKGROUND
We use the definition of text-adventure game as
Markov Decision Process (Côté et al., 2018; Hausknecht et al., 2020). game can represented as a 7-tuple of (5, T, S2 O, R. 7) representing the set of environment states, mostly deterministic conditional transition probabilities between states, the vocabulary or words used to compose text commands, observations returned by the game, observation conditional probabilities, reward function, and the discount factor respectively. LSTM-DQN (Narasimhan et al., 2015) and Action Elimination DQN (Zahavy et al., 2018) operate on reduced action space of the order of 102 actions per step by considering either verb-noun pairs by using a walkthrough of the game respectively. The agents learn how to produce Q-value estimates that maximize long term expected reward. The DRRN algorithm for choice-based games (He et al., 2016; Zelinka, 2018) estimates Q-values for a particular action from particular state. Fulda et al. (2017) use word embeddings to model affordances for items in these games.
Exploration strategies: Jain et al. (2019) extend consistent Q-learning (Bellemare et al., 2016) to text-games, focusing on taking into account historical context. terms of exploration strategies, Yuan et al. (2018) detail how counting the number of unique states visited improves generalization in unseen games. Yuan al. (2019) introduce the concept of interactive question-answente answering the form of Qodr-modeling QA tasks in TextWorld (Côté et al., 2018), simplified text-game testbed.
Knowledge Graphs: Ammanabrolu Riedl (2019b) introduce KG-DQN, using knowledge graphs as state representation for text-game agents; Ammanabrolu & Riedl (2019a); Murugesan et al. (2020) explore transfer of commonsense knowledge text-games with knowledge graphs. Ammanabrolu & Hausknecht (2020) showcase the KG-A2C, for the first time tackling the fully combinatorial action space and presenting ofate-of-the-ar results on many man-mad mane text games. In similar vein, Adhikari al. (2020) present the Graph-Aides Transformer Agent (GATA) which learns to construct knowledge graph during game play and improves zero-shot generalization on procedurally generated Tex: World (Côté al., 2018) games.
3

---

Under review as a conference paper at ICLR 2021
greph
Sequentaal
Action
R-GON
Actor
Decoder
KG,
Value
Updata
Value
Bohind
east
Recument Text Ennoder
house
Bouth
Lecaliona Sum Onl Coga
bahind the white the forest to the cast. In one corner of the house there is small window which is slightly ajar. You carrying: jewellenerasseed egg
Behind House
path
Oxeetions:
Where an leceled)
ALBERT-QA
What do hovee
Q'BERT
Observation
Attribuless ulkabbe, openable, animato, freasure
Figure 3: One-step knowledge graph extraction in the Jericho- QA format, and overall Q*BERT architecture at time step At each step the ALBERT-QA model extracts a relevant highlighted entity set V2 by answering questions based on the observation, which is used to update the knowledge graph.
4 Q*BERT
BEBR is reinforcement learning agent that uses a knowledge-graph represent its understanding of the world state. A knowledge graph (Fig. 3) is a set of relations (s, r, o) such that s is a subject. is a relation, and o is an object. Instead of using relation extraction rules as KG-A2C (Ammanabrolu & Hausknecht, 2020), Q*BERT uses variant of the BERT (Devlin et al., 2018) natural language transformer answer questions and populate the knowledge graph from the answers.
Knowledge Graph State Representation We treat the problem of constructing the knowledge graph as a question-answering task. Our method first extracts a set of graph vertices V by asking question-answering system relevant questions and then linking them together using set of relations R. to form knowledge graph representing information the agent has learned about the world. Examples of questions include: "What is my current location?", "What objects are around me?", and "What am I carrying?" respectively extract information regarding the agent's 's current location, surrounding objects, inventory objects. Further, we predict attributes for each object by asking the question "What attributes does object have?". An example of the knowledge graph that can be extracted from description text and the overall Q*BERT architecture are shown in Figure 3.
For guestion-answerrigg, use the pre-trained language model, ALBERT (Lan et al., 2020), variant of BERT that is fine-tuned for question answering on the SQuAD 2.0 (Rajpurkar et al., 2018) crestion-annwering dataset. We further fine-tune the ALBERT model on dataset specific to the text-game domain. This dataset, dubbed Jericho-QA, was created by making question answering pairs about sat--games the Jericho (Hausknecht et al., 2020) framework as follows: For each game in Jericho, we use an oracle an agent capable of playing the game perfectly using information normally off-limits such as the true game state and a random exploration agent to gather ground truth state information about locations, objects, and attributes. From this ground truth, we construct pairs of questions the form that Q will ask as it encounters environment description text, and the corresponding answers. These question-answer pairs used to fine-tune the Q/A model and the ground truth data are discarded. No data from games we test Q*BERT on are used during ALBERT fine-tuning. Additional details can be found in Appendix A.1.
In a text-game the observation is a textual description of the environment. For every observation received, Q*BERT produces fixed set of questions. The questions and the observation text sent to the question-answert the knowledge graph. The complete knowledge graph the input into Q*BERT's neural architecture (described below), which makes a prediction of the next action to take.
system. Predicted answers are converted into (s, r, o) triples and added to
https://githhub... http:://gggthhb..co////ooo//////
4

---

Under review as a conference paper at ICLR 2021
QEBERT Training At every step observation consisting of several components is received: or = (Dls gamme Uua y at-1) corresponding to the room description, game feedback, inventory, and previous action, and total score R. The room description Oticue is a textual description of the agent's is location, obtained by executing the command "look". The game feedback gume is the simulators response to the agent's previous action and consists of narrative and flavor text. The inventory Onee and previous action Qt-1 components inform the agent about the contents of its inventory and the last action taken respectively.
Each of these components is processed using GRU based encoder utilizing the hidden state from the previous step and combined to have single observation embedding og. each step, we update our knowledge graph G2 using or as described in earlier in Section 4 and it is then embedded into single vector ge. This encoding is based on the R-GCN and is calculated as:
ΣΣ PER Ci,
Wo "h, )
gt =
Wgo
+ bg
Where R is the set of relations, .N.' the 1-step neighborhood of a vertex with respect to relation r, w, (1) and h. are the learnable convolutional filter weights with respect to relation r and hidden state of vertex j in the last layer I of the R-GCN respectively, Gar normalization constant, and W g and bg the weights and biases of the output linear layer. The full architecture can be found in Fig. 3. The state representation consists only of the textual observations and knowledge graph. Another key use of the knowledge graph, introduced as part of KG-A2C, is the graph mask, which restricts the possible set of entities that can predicted to fill into the action templates every step to those found in the agent's knowledge graph. The rest of the training methodology is unchanged from Ammanabrolu & Hausknecht (2020), more details can be found in Appendix A.I.
5 STRUCTURED EXPLORATION
This section describes MCTQ*BERT an exploration method built on Q*BERT that detects overcomes bottlenecks by backtracking and policy chaining. This method of chaining policies and backtracking can be thought of in terms of options (Sutton et al., 1999; Stolle & Precup, 2002), where the agent decomposes the task of solving the text game into the sub-tasks, each of which has it's own policy. In our case, each sub-task delivers the agent to bottleneck state.
5.1 BOTTLENECK DETECTION USING INTRINSIC MOTIVATION
Inspired by McGovern & Barto (2001), we present an intuitive way of detecting bottleneck states such as those in Fig. 2-or or sub-tasks in terms of whether or not the agent's ability collect reward stagnates. If the agent does not collect new reward for number of environment interactions defined in terms of a patience parameter-then is possible that it is stuck due to a bottleneck state. An issue with this method, however, is that the placement of rewards does not always correspond to an agent being stuck. Complicating matters, rewards are sparse and often delayed; the agent not collecting reward for while might simply indicate that further exploration is required instead of truly being stuck.
To alleviate these issues, we define intrinsic motivation for the agent that leverages the knowledge graph being built during exploration. The motivation is for the agent to learn more information regarding the world and expand the size of its knowledge graph. This provides us with better indication of whether an agent is stuck or not-a stuck agent does not visit any new states, learns no new information about the world, and therefore does expand its knowledge graph-leading to more effective bottleneck detection overall. To prevent the agent from discovering reward loops based on knowledge graph changes, we formally define this reward in terms of new information learned.
[-1
FIM. = A(KG global KCG,) where K.Gglobal
U Kg, i=1
Here XGGglahal is the set of all edges that the agent has ever had in its knowledge graph and the subtraction operator is set difference. When the agent adds new edges to the graph perhaps
5

---

Under review as a conference paper at ICLR 2021
the result of finding happen when that room is rediscovered in subsequent episodes. This is then scaled by the game score so the intrinsic motivation does not drown out the actual quest rewards, the overall reward the agent receives at time step /. looks like this:
room glotall changes and positive reward is generated this does not
Tg: +
Tr = Tg. + OTTMM
Tmax
where is small smoothing factor, ar is scaling factor, l'g. is the game reward, fmmx is the maximum score possible for that game, and rt is the reward received by the agent on time step t.
5.2 MODULAR POLICY CHAINING
Algorithm 1 Structured Exploration
primary reason that agents fail to pass bottlenecks is not satisfying all the required dependencies. To solve this problem, we introduce a method of policy chaining. where the agent utilizes the determinism of the simula- tor to backtrack to previously visited states in order to fulfill dependencies required to overcome bottleneck.
[Tehainn bb, } f- (Sr,
Chained, backtrack, current policy Backtrack, current state buffers
8o, Finit <- ENY.RESETO Jmax +- :wa: P 4- 0
for timestep in O...M do
> Train for M Steps
$141, S S+ 8141 p p -+1 if ((T) S Jmx then if p 2 patience then
Q*BERTUPDATE(s;
> Append current state state buffer
b Lose patience
Stuck a bottleneck BACKTRACK(Ts; S.)
Specifically, Algorithm optimizes the policy as usual, but also keeps track of buffer S of the distinct states and knowledge graphs that led up to each state (we use state 8, to collo- quially refer to the combination of an observation Or and knowledge graph KGG.. Similarly, bottleneck buffer Sp and policy my reflect the sequence of states and policy with the maxi- mal return Jaux consisting of the cumulative intrinsic well as game rewards. A bottleneck is identified when the agents fails to improve upon Tmax after patience number of steps, i.c no improvement in raw game score or wwwwwlege-grahh-beee trinsic motivation reward. The agent then backtracks by searching back-
8t, Tmax; > Bottleneck passed; Add æ the chained policy
Tehnin <-
Tchain +
if (TT) > Tmax then
New highscore found Jmax t J (T)) Th f- S, S; 0
return Webain
Chained policy that reaches
function Q"BERTUPDATE(S; 81; R)
P One-step update
8t+1, + ENV. 8t, CALCULATEREWARD A2C.UPDATE(S,.1)) return 8141, Tt, .
P Section 4 Eq. 4
(t.11
Appendix A.I
function BACKTRACK(TT, St)) for b in REVERSE(Se) do + b; +
Try overcome bottleneck
D. States leading to highscore
for timestep in O...N do
Train for N steps
8t-1, Ft, π + Q BERTUPPATTE(S.. m)
in-
J(T) > J(Fb) then return 8t, Tt, w
Terminate
b Can't find better score; Give up.
wards through the state sequence Sb, restarting from each of the previous states-and training for N steps in search of more optimal policy overcome the bottleneck. When such policy is found, it is appended to modular policy chain Tehain- Conversely, if no such policy is found, then we have failed pass the current bottleneck and the training terminates.
EVALUATION
We first evaluate the quality of the knowledge graph construction supervised setting. Next we perform an end-to-end evaluation in which knowledge graph construction is used by Q*BERT. We further measure the utility of the knowledge graph-based intrinsic motivation bottleneck detection and conduct empirical comparison between MC!Q BERT and other exploration strategies.
6.1 GRAPH EXTRACTION EVALUATION
Table 1 (columms 2-5) shows the QA performance, and consequently the accuracy of the knowledge graphs built during exploration, on the Jericho- Bacho-QAAco dataset using the rules-based approach of KG-A2C and the trained Albert-QA model in Q*BERT. Exact match (EM) is the percentage of times the model

---

Under review as a conference paper at ICLR 2021
Expt.
QA Graph sccuracy
Game reward
Intrinsic
Agent
KG-A2C
Q"BERT
KG-A2C
Q"BERT
MCIQ
MCIQ
GO:Q
Eps.
Eps.
Max
Max
Max
zork1
6.08
8.42
43.93
48.31
34
34.1
35
32
41.6
library
10.33
26.74
49.78
52.76
14.3
10.0
18
19
detective
7.51
246.1
304
balances
32.53
36.09
85.81
86.18
10
10
10
10
10
10
10
pentari
56
2tou
14.40
21.74
49,44
49.82
9
5
11.8
5
ludicorp
14.47
18.48
57.58
60.95
17.8
19
19
22.8
20,6
deephome
3.34
3.86
9.31
9.84
1
6
temple
7.42
9.44
98
49.17
7.6
7.9
8
Table 1: QA results (EM and F1) Jericho- QA test set and averaged asymptotic scores games by different methods across 5 independent runs. For KG-A2C and Q*BERT, we present scores averaged across the final 100 episodes well as scores. Methods using exploration strategies show only max scores because Episode Average Score (Eps.) conflates forward progress and backtracking. Agents are allowed 10t steps for each parallel A2C agent with batch size of 16.
1003]
zork1
Paintng
Calleriigz
Cellar
Mide
MCIQ GO'Q"BERT
QUBERT
(a) Episode rewards for KG-A2C QEBET (b) Max reward curves for exploration strategies.
Figure 4: Select ablation results on Zork/ conducted across independent runs per experiment. We see where the agents using structured exploration pass each bottleneck seen Fig. Q*BERT without IM is unable to detect nor surpass bottlenecks beyond the Cellar.
was able predict the exact answer string, while Fl measures token overlap between prediction and ground truth. We observe a direct correlation between the quality of the extracted graph and an agent's performance the games BERTT in general possessing knowledge graphs of much higher quality than KG-A2C. On games where Q* BERRT performed comparatively better than KG-A2C in terms of asymptotic scores (columns 7 and 9), e.g. defective, the QA model had relatively high EM and F1, and vice versa as seen with ztuu. In general Q*BERT reaches comparable asymptotic performance KG-A2C on of games. However, illustrated on zorkl in Figure 4a, BERT reaches asymptotic performance faster than KG-A2C, indicating that the QA model improves learning; this trend is consistent on other games as shown in additional plots Appendix the graph to constrain the action space and provide richer input state representation. Q uses a QA model fine-tuned on regularities of a text-game producing more relevant knowledge graphs than those extracted by OpenlE (Angeli et al., 2015) in KG-A2C for this purpose.
Both agents rely on
6.2 INTRINSIC MOTIVATION AND EXPLORATION STRATEGY EVALUATION
We evaluate intrinsic motivation through policy chaining, dubbed MC!Q"BERT (Modularly Chained QEBERT) by first testing policy chaining with only game reward and then with both game reward and intrinsic motivation. We provide qualitative analysis of the bottlenecks detected with both methods with respect to those found in Fig. 2 on Zorkl. Because MC!Q*BERT exploits structural domain assumptions that B and KG-A2C cannot, we create a strong alternative baseline that looks at whether modular chaining improves over related exploration strategy used in Go-Explore (Ecoffet et al., 2019). GO!Q*BERT is baseline that makes the same underlying assumptions regarding the simulator MC!Q*BER? but operates differently by tracking sub-optimal and under-explored states in order to allow the agent to explore upon more optimal states that may be a result sparse rewards. This baseline trains BERTT in parallel to generate actions from the full action space used for
7

---

Under review as a conference paper at ICLR 2021
exploration. Further details are found in Appendix A.3. When MCIQ*BERT only uses game reward it matches Q*BERT on 5 out of games and outperforms on 3 out of games. When M uses intrinsic motivation plus game reward, it strictly outperforms KG-A2C and Q*BERT on 6 out of 9 games and matches it on the rest. MC! outperforms GO!Q*BERT on 7 games and matches on 2, indicating that the modular chaining exploration strategy exploits the intrinsic motivation of knowledge graph learning better than the closest alternative exploration strategy.
7 ANALYSIS
Table shows that across all the games MC!Q*BERT matches or outperforms the current otate-of- the-art when compared across the metric of the max score consistently received across runs. There are two main trends: First, BC!Q*BERT strongly benefits from the inclusion of intrinsic motivation rewards. Qualitatively, we illustrate this with ZorkI, the canonical commercial cext-adventure game that no RL agent has ever beaten. An analysis of bottlenecks detected by each agent in this game reveals differences in the overall accuracy of the bottleneck detection between MC!Q "ERT with and without intrinsic motivation. With intrinsic motivation, across 5 independent runs, MC!Q*BERT had average true positive bottleneck state detection rate of 63%, false positive of 37%, with 50% coverage; and without it has a true positive rate of 58%, false positive of 42%, with coverage of 25% assumingg that the states such as Fig. 2 represent the ground truth for bottlenecks. Coverage here refers to the number of unique bottlenecks states found during exploration compared to the total number of such states in the ground truth. This indicates that overall quality of bottleneck detection significantly improves given intrinsic motivation enabling MC!Q*BERS to backtrack and surpass them. Figure 4b shows when each of these agents detect and subsequently overcome the bottlenecks outlined in Figure 2.
When intrinsic motivation is not used, the agent discovers that it can get to the Kitchen with a score of +00 and then Cellar with score of +-25 immediately after. It forgets how to get the Egg with a smaller score of +5 and never makes it past the Grue in the Cellar. Intrinsic motivation avoids this in two ways: (1) it makes it less focused
locally high-reward trajectory- making it less greedy and helping it chain together rewards for the Egg and Cellar, and (2) provides rewards for fulfilling dependencies that would otherwise not be rewarded by the game-this is seen by the fact that it learns that picking up the lamp is the right way to surpass the Cellar bottleneck and reach the Painting. A similar behavior is observed with GOIQ*BERT: the agent settles prematurely on locally high-reward trajectory and thus never has incentive to find more globally optimal trajectories by fulfilling the underlying dependency graph. Here, the likely cause due to GO!Q*BERT's inability to backtrack and rethink discovered locally-maximal reward trajectories.
The second trend is that using both the improvements to graph construction in addition to intrinsic motivation and structured exploration consistently yields higher max scores across a majority of the games when compared to the rest of the methods. Having just the improvements to graph building or structured exploration by themselves is not enough. Thus we infer that the full MCTQ*BERT space more effectively by virtue of being
agent is fundamentally exploring this combinatorialll-sizzz able to more consistently detect and clear bottlenecks. The improvement over systems using default exploration such as KG-A2C or QEBRRT by itself indicates that structured exploration is necessary when dealing with sparse and ill- ill-placed reward functions.
8 CONCLUSIONS
Modern deep reinforcement learning agents using default exploration strategies such as e-greedy are ill-equipped to deal with the latent structure of dependencies and bottlenecks found in many text-based games. To help address this challenge, we introduced two new agents: Q*BERT, an agent that constructs a knowledge graph of the world by asking questions about it, and BCRQ which uses intrinsic motivation to grow the graph and detect bottlenecks arising from delayed rewards. A key insight from ablation studies is that the graph-bases intrinsic motivation is crucial for bottleneck detection, preventing the agent from falling into locally optimal high reward trajectories due to ill ill-placed rewards. Policy chaining used in tandem with intrinsic motivation results in agents that explore further in the game by clearing bottlenecks more consistently.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ashutosh Adhikari, Xingdi Yuan, Mare-Ales Alex-ndee Côté, MikuláK Zelinka, Marc-Antoine Rondeau, Romain Laroche, Pascal Poupart, Jian Tang, Adam Trischler, and William L. Hamilton. Learning dynamic knowledge graphs to generalize on text-based games. arXiv preprint 2020.
Leonard Adolphs and Thomas Hofmann. Ledeepchef: Deep reinforcement learning agent for families of text-based games. arXiv preprint arXiv: 2019.
Prithviraj Ammanabrolu and Matthew Hausknecht. Graph constrained reinforcement learning for natural language action spaces. In International Conference on Learning Representations, 2020.
URL https: /tfpp::/ooge /tpp:::////////////eeeeee ew net forum? x.
Prithviraj Ammanabrolu and Mark Riedl. Transfer deep reinforcement learning using knowledge graphs. In Proceedings of the Thirteenth Workshop on Graph-Based Methods for Natural Lan- guage Processing (rex at EMNLP, 2019a. URL https: wwww. http:/ww.wwww....o/////o/oo org/
anthology/D19- 5301.
Prithviraj Ammanabrolu and Mark O. Riedl. Playing text-adventure games with graph-based deep reinforcement learning. In Proceedings of 2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-IILT 2019, 2019b.
Tim Anderson, Marc Blank, Bruce Daniels, and Dave Lebling. Zork. http://ifdb.tads... view viewgame ? 4 jaat wckkm) 1979.
Gabor Angeli, Johnson Premkumar, Melvin Jose, and Christopher D. Manning. Leveraging Linguistic Structure For Open Domain Information Extraction. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), 2015.
Marc G. Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Remi Munos. Increasing the action gap: New operators for reinforcement learning In AAAI Conference Artificial Intelligence, 2016. URL https: //tp:://wwww /wwp//wwwww. aaai. wrt. /cg//cc/// index. wwwpdxxwpppp/eeeeee/ Chap/AAAI/AAAAIL htgp://view/1242/111772
Marc-Alexandre Côté, Ákos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, Wendy Tay, and Adam Trischler. Textworld: A learning environment for text-based games. CoRR, abs/1806. 11632,15,,,10 2018.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, tabs/1810.04880 2018.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go-explore: new approach for exploorloo problems. CoRR, abs/1901.10099, 2019.
Nancy Fulda, Daniel Ricks, Ben Murdoch, and David Wingate. What can you do with rock? affordance extraction via word embeddings. In IJCAI, pp. 1039-1045, 2017. doi: 10.24963/ijcai. 2017/144.
Matthew Hausknecht, Prithviraj Ammanabrolu, Mare-Alexandre Côté, and Xingdi Yuan. Interactive fiction games: A colossal adventure. In Fhirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), 2020. URL https:
05398.
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with a natural language action space. In ACL, 2016.
Vishal Jain, William Fedus. Hugo Larochelle, Doina Precup, and Mare G. Bellemare. Algorithmic improvements for deep reinforcement learning applied to interactive fiction. CoRR, abs/ htss/1911.. 1.251,, 2019.

---

Under review as a conference paper at ICLR 2021
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. Internationaa Conference Learning Representations, 2020. URL https: https//////eeeeeeee.eeeeeeeeeeee i.c=Hee77AEtv.
Andrea Madotto, Mahdi Namazifar, Joost Huizinga, Piero Molino, Adrien Ecoffet, Huaixiu Zheng, Alexandros Papangelis, Dian Yu, Chandra Khatri, and Gokhan Tur. Exploration based language learning for text-based games, CoRR, abs/2001.08868. 2020.
Amy McGovern and Andrew G Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. 2001.
Keerthiram Murugesan, Mattia Atzeni, Pushkar Shukla, Mrinmaya Sachan, Pavan Kapanipathi, and Kartik Talamadupula. Enhancing text-based reinforcement learning agents with commonsense knowledge, arXiv preprint arXii:2205.008// 00811, 2020.
Karthik Narasimhan, Tejas D. Kulkarni, and Regina Barzilay, Language understanding for text-based games using deep reinforcement learning. In EMNLP, pp. 1-11, 2015.
Pranav Rajpurkar, Robin Jia, and Perey Liang. Know what you don't know: Unanswerable questions for SQuAD. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 784-789, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18-22 org/ htts//nthllogyy////oo 211-2124.
URL https: www. aclweb.
Martin Stolle and Doina Precup. Learning options in reinforcement learning. In Proceedings of the 5th International Symposium on Abstraction, Reformulation and Approximation, pp. 212-223, Berlin, Heidelberg, 2002.
Verlag. ISBN 3540439412.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-111, 1999.
Xusen Yin and Jonathan May. Comprehensible context-driven text game playing. CoRR, abs/1905. 00265, 2019.
Xingdi Yuan, Maec-Alexandre 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, Abs//800.111255 2018
Xingdi Yuan, Marc-Alexandre Côté, Jie Fu, Zhouhan Lin, Christopher Pal, Yoshua Bengio, and Adam Trischler. Interactive language learning by question answering. In EMNLP, 2019.
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Informa- tion Processing Systems 37, pp. 3562-3573. Curran Associates, Inc., 2018.
Mikulás Zelinka. Using reinforcement learning to learn how to play text-based games. CoRR, htts/80010199// 2018
10


Reviews:
[{"review_id": "xwwdz3c01xU", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies reinforcement learning setting where the agent's decision is augmented with external knowledge representation. Termed Q*BERT, this proposed method uses question answering to build a knowledge graph of the world. Results show the agent was able to pass the bottleneck for a popular game where most other algorithms failed.\n\nPros:\nThe proposed method seems well motivated and reasonable to improve agent's performance. Authors provide good review of text games' literature. Experimental results seem solid.\n\nCons:\n1. The novelty in terms of methodology seems a bit low. The idea of Q*BERT training is not new.\n2. I have some questions regarding authors' \"Knowledge Graph State Representation\". First of all, pretrained language models such as BERT contain rich information about world knowledge. For example, BERT will give a strong association between \"door\" and \"key\", while an agent that learns from scratch will not understand unless it receives an reward from \"use key to open the door\" (or the game hints the agent to do so). It's unclear why the authors argue using QA to augment agent's state representation. It is possible that using BERT's representation alone, the agent's performance will be much better and training will be more efficient already.\n3. Another question relates to the way authors conduct this QA. The authors use an oracle agent to explore the word and a random agent to gather information such as attributes. Is there already information leakage during this process? In a fair experimental setup, there is no way an agent can foresee the world. Maybe I am misunderstanding here, and I hope the authors can help clarify.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jiZq1PnGM2X", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper focuses on learning to play text adventure games using reinforcement learning. The paper presents two new algorithms: Q*BERT and MC!Q*BERT, as well as a QA dataset to help training a component of these agents that builds a knowledge graph of the current game state based on the textual descriptions received by from the game.\n\nReasons for score:\n\nI gave this paper a 7, as I think the overall contributions to the text-based adventure game playing literature are strong. There are a few minor technical issues here and there (see my detailed feedback below), but those are minor things that can be easily fixed. In particular, the new approach to integrate exploration strategies to overcome \"bottlenecks\" in the search space is interesting and, to the best of my knowledge, novel.\n\nAdditional feedback:\n\n- page 1: \"We contend that existing Reinforcement Learning agents that are unaware of\" -> \"We contend that existing Reinforcement Learning agents are unaware of\"\n- page 2: nit, \"In text-adventure games the dependencies are of two types\" -> I can recall many bottlenecks from text adventure games that do not fit either of these two categories. So, perhaps instead of \"are of two types\" you could say that these are the two dependencies you considered (e.g., some games require many unrewarded actions (in terms of in-game points) like visiting locations more than once, or visiting them at some particular times, or even interacting with certain characters in certain ways, etc.). Basically, location and inventory are not the only state of the game, but there are many other state variables in many of these games.\n- I am not convinced that the dependency graph of Zork can be divided into a linear set of  \"level\" subdivisions the authors state before Equation 1. For example, how about branches? If there are parallel tasks that need to be performed each with their own \"bottlenecks\" (for example, completing three tasks that can be done in any order), then the \"j>i\" condition in Equation 1 breaks, as it will result in some spurious bottlenecks. Thus, I think this part of the paper needs some work (authors mention \"relatively linear plots\", but \"relative linear\" does not mean \"completely linear\"). Edit after reaching Section 5: and since this definition is not the one used by MC!Q*BERT anyway, why have it in the paper in any case?\n- Table 1: bolding the highest scores for each game would be useful to understand the table at a glance.\n- page 8: about the bottleneck identification rates reported: how were ground truths established? was this manually labeled? If it was automatically labeled, I'm not sure if the definition used earlier in the paper was used, but if it was, I am not confident it is a good definition.", "extra_scores": {}, "extra_text": {}}, {"review_id": "HRj8OWzRdwd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper proposes two RL agents for the text adventure games: QBERT learns (relational) knowledge about the game world with assistance of a trained QA-model and then constrains its action space with help of the knowledge base, enjoying greater sample efficiency; MCQBERT learns to escape from local optima by backtracking through the navigation trajectories, guided by the learned knowledge base and a manually-designed intrinsic reward function. \n\nPros: \n\nThis is a very dense paper with multiple key ideas, namely (1) using QA model to construct knowledge base; (2) escaping local optima by backtracking; and (3) modular policy chaining. \n\nBoth (1) and (2) are interesting and novel. But the novelty of (1) is limited because using QA to build graph has been used by e.g., Ammanabrolu et al. Bringing Stories Alive: Generating Interactive Fiction Worlds. \n\nEmpirical results demonstrate the effectiveness of the proposed methods. Not being eaten by Grue is impressive. \n\nCons: \n\nPresentation is the main reason that I’d like to reject the current version: \n(1) Several key claims are misleading and over-bold. \n(2) Many essential technical details are not clear. \n\n[Misleading/Over-bold claims]\n\nThe authors claimed, at many places, that they learned the \"dependencies'', namely the quest structure. For example, they said the agent \"learns that picking up the lamp is the right way to surpass the Cellar bottleneck and reach the Painting\". \n\nThis claim is wrong: the agent only successfully passes that room because it has done enough exploration (and the exploration is efficient because the intrinsic reward function is cleverly designed).\n\nIf this comment is not clear enough, let me be a bit more specific. \nIn the \"lamp-Grue\" example, the agent doesn't know the sense like \"if I pick up this lamp, I can pass the Grue room'' or \"now I am in the Grue room and the lamp is helpful\". \nInstead, the agent only picks the lamp up because it is encouraged to discover new information. \n\nOr, in other words, the agent doesn't really learn the quest structure as shown in Figure-2. \n(But I agree that Figure-2 is useful to illustrate the interesting idea.)\n\nI believe that the right way to view the method is: exploration is guided by not only environment reward but also intrinsic desire to discover new information, which leads to more efficient exploration and higher long-term reward. \nSimilar problems in other RL domains have been tackled and here is a paper that is similar to this submission in spirit: \nConti et al NeurIPS 2018 Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents. \nQuote them: \"reward functions are often deceptive, and solely optimizing for reward without some mechanism to encourage intelligent exploration can lead to getting stuck in local optima\"---same problem as in text adventure games. \nIn this submission, the agents also rely on the learned knowledge base. \nNote: the learned knowledge base is very different from the quest (or dependency) structure---the former is like Figure-3 while the latter is Figure-2. \n\nThen in what sense can the authors confidently claim that their agents learned things like \"the virtue of being able to more consistently detect and clear bottlenecks\" or \"deal with latent structure of dependencies and bottlenecks\"? My opinion is: only if they can actually learn some structures like shown in Figure-2. \n\nThat being said, I request the authors to rewrite all the claims like mentioned above.\n\n[Technical clarity]\n\nThe most important clarity problem is about the modular policy chaining method: it is not clear how the method is integrated with the entire framework. \nE.g., how is $\\pi_{\\text{chain}}$ is used? It is only mentioned in Algo-1 but nowhere else. \nOther related detailed questions include: \nWhat is the \"policy\" in this paper? Is it a function to be learned, or a set of parameters, or a specific action for a given state? When a policy is buffered or chained, what is actually stored and how? \nAlgorithm-1 always has \"Bottleneck passed\". What if the bottleneck isn't passed? BACKTRACK procedure may not find a better score, so bottleneck is not passed, is it consistent with \"bottleneck passed\"?\nIs the BACKTRACK algorithm greedy? It looks like it returns immediately once it finds a higher $\\mathcal{J}$? \nHow is $\\mathcal{J} computed?$ It looks like it is stored and then indexed somehow. But how? How can you index a value by a \"policy\" as a key? This is related to the ``what is policy\" question. \n\nThere are other things about the framework that need to be clarified as well. \n\nIs the training algorithm online or offline? In Algo-1, A2C is called, indicating it is trained (step by step) during exploration: thus it seems an online algorithm. But what about QBERT which doesn't have modular policy chaining? \n\nWhat is the full action space? There should be some discussion about it in main paper, referring to the related appendices then. \n\nHow could one know the \"maximum score possible for the game\"? \n\nDoes the agent ask the same set of questions (to QA model) every step? Then how could it handle consistency? E.g., if \"what am I carrying\" is asked many times while your inventory is not changed at all, would it generate exactly the same answer all the time and how could you handle any difference? \n\nIn Figure-3, why ALBERT-QA doesn’t point to $KG$ but only points to $V_t$? Is ALBERT-QA used specifically to build knowledge graph? \nIn general, it is a little hard to connect the elements of Figure-3 to formula in section-4. \n\nHere are some presentation issues about the math formula: \nIndex-$i$ and index-$j$ in eqn-(1) are not grounded: they are mentioned in text; they don't loop over anything. \nSimilar problem for index-$i$ in eqn-(2). \n\nHere are some minor presentation issues: \n\"MCQBERT an agent that uses\" -> \"MC!QBERT, an agent that uses\"\n\"freedom to a explore\" -> \"freedom to explore\"\n\"these dependency graphs are … either … or … to progress and … a priori\" -> this sentence is too convoluted to correctly parse\n\"mostly deterministic … probabilities\" -> odd phrase: do you mean degenerative distribution? \n\"and without it has a true positive …\" -> ungrammatical \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "G4M9b3fTEFc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary/Overall Quality: The authors make the following contributions.\n- focus on text based adventure games\n- create agent that can build knowledge graph by answering question\n- introduce novel exploration strategy\n- IM reward: expand size of knowledge graph\nBecause the authors present a number of interesting and well tested strategies for a well-justified task, the paper is above the acceptance threshold. If the clarity could be improved (specifically by making the contribution in the general case more explicit) and if the experiments could be made more thorough (+ a stronger improvement of prior work) it would be a strong paper.\n\nClarity: The authors did a reasonable job of familiarizing readers with the challenges of text-based games. However, the description of the research contribution and its potential impacts could have been more focused. For example, in the abstract the authors don't mention that they collect a Jericho-QA dataset, but it is listed as one of the three contributions in the final paragraph of the related work. The paper spans a lot of material--from the research merit of text based games to intrinsic motivation based on knowledge graph formation to using QA models for knowledge graph construction to modular policy chaining--and it is difficult to walk away from the paper with a cohesive understanding of the research contribution.\n\nOriginality: While the individual components are not extremely novel, taken together they create an interesting and original system design. E.g., even though the notion of using intrinsic motivation to un-sparsify a reward space is far from new, the authors devise an interesting formulation of IM to apply to knowledge graph construction.\n\nSignificance:\n- _For text based games_: the authors provide numerous method contributions and a dataset for this application specifically. However, looking at table 1 and figure 4, its not clear that the fullest version of their method has a consistent advantage over prior work.\n- _Generally_ Text-based games could be an important benchmark/milestone for systems that need to reason well into the past and over a large action, discrete action space. The authors do not address this much beyond some prose in the abstract and introduction. Certainly some components of the methods they have developed (e.g., exploration over a knowledge graph) has broad-spanning applications.\n\nStrengths:\n- The authors provide a variety of methods to help agents excel is text based games: knowledge graph creation with a QA system, a dataset to train the QA system, intrinsic motivation based on knowledge graph expansion, modular policy training.\n- Show results over a large number of text-based games. On several games, their model, MC!Q* sees a substantial improvement over prior work.\n\nWeaknesses:\n- Improvement over prior work is not consistent (see library, balances, and temple tasks in table 1, in figure 4a Q*bert converges more quickly on average but not above variance of KG-A2C)\n- As someone unfamiliar with text based games, it's hard to interpret the results in table 2 and to understand what problems are being addressed in each game.\n- More experiments to better understand how bottlenecks are addressed by the model (e.g., more of figure 4b) would be enlightening", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes very interesting work that advances the state of the art in Zork by going beyond an important state bottleneck.  While there is an important engineering contribution, the reviewers raised important concerns regarding the novelty of the question-answering approach to construct knowledge graphs, the clarity of the backtracking heuristic and the extent to which the proposed approach outperforms previous work.  I also read the paper and I agree with the concerns of the reviewers.  In particular, I encourage the authors to provide more details about the backtracking procedure, a formal description of the algorithm and its assumptions to help readers apply the approach in other domains, as well as a formal analysis to better understand when it will or will not pass a bottleneck state.
Decision: Reject