Title: GRAPH CONSTRAINED REINFORCEMENT LEARNING FOR NATURAL LANGUAGE ACTION SPACES

Abstract: Interactive Fiction games are text-based simulations in which an agent interacts with the world purely through natural language. They are ideal environments for studying how to extend reinforcement learning agents to meet the challenges of natural language understanding, partial observability, and action generation in combinatorially-large text-based action spaces. We present KG-A2C 1 , an agent that builds a dynamic knowledge graph while exploring and generates actions using a template-based action space. We contend that the dual uses of the knowledge graph to reason about game state and to constrain natural language generation are the keys to scalable exploration of combinatorially large natural language actions. Results across a wide variety of IF games show that KG-A2C outperforms current IF agents despite the exponential increase in action space size.

1. INTRODUCTION:

Natural language communication has long been considered a defining characteristic of human intelligence. We are motivated by the question of how learning agents can understand and generate contextually relevant natural language in service of achieving a goal. In pursuit of this objective we study Interactive Fiction (IF) games, or text-adventures: simulations in which an agent interacts with the world purely through natural language-"seeing" and "talking" to the world using textual descriptions and commands. To progress in these games, an agent must generate natural language actions that are coherent, contextually relevant, and able to effect the desired change in the world.

Complicating the problem of generating contextually relevant language in these games is the issue of partial observability: the fact that the agent never has access to the true underlying world state. IF games are structured as puzzles and often consist of an complex, interconnected web of distinct locations, objects, and characters. The agent needs to thus reason about the complexities of such a world solely through the textual descriptions that it receives, descriptions that are often incomplete. Further, an agent must be able to perform commonsense reasoning-IF games assume that human players possess prior commonsense and thematic knowledge-e.g. knowing that swords can kill trolls or that trolls live in dark places. Knowledge graphs provide us with an intuitive way of representing these partially observable worlds. Prior works have shown how using knowledge graphs aid in the twin issues of partial observability (Ammanabrolu & Riedl, 2019a) and commonsense reasoning (Ammanabrolu & Riedl, 2019b) , but do not use them in the context of generating natural language.

To gain a sense for the challenges surrounding natural language generation, we need to first understand how large this space really is. In order to solve solve a popular IF game such as Zork1 it's necessary to generate actions consisting of up to five-words from a relatively modest vocabulary of 697 words recognized by Zork's parser. Even this modestly sized vocabulary leads to O(697 5 ) = 1.64 × 10 14 possible actions at every step-a dauntingly-large combinatorially-sized action space for a learning agent to explore. In order to reduce the size of this space while maintaining expressiveness, Hausknecht et al. (2019a) propose the use of template-actions in which the agent first selects a template (e.g. [put] [in] ) then fills in the blanks using vocabulary words. There are 237 templates in Zork1, each with up to two blanks, yielding a template-action space of size O(237 × 6972 ) = 1.15 × 10 8 . This space is six orders of magnitude smaller than the word-based space, but still six orders of magnitude larger than the action spaces used by previous text-based agents (Narasimhan et al., 2015; Zahavy et al., 2018) . We demonstrate how these templates provide the structure required to further constrain our action space via our knowledge graph-and make the argument that the combination of these approaches allows us to generate meaningful natural language commands.

Our contributions are as follows: We introduce an novel agent that utilizes both a knowledge graph based state space and template based action space and show how to train such an agent. We then conduct an empirical study evaluating our agent across a diverse set of IF games followed by an ablation analysis studying the effectiveness of various components of our algorithm as well as its overall generalizability. Remarkably we show that our agent achieves state-of-the-art performance on a large proportion of the games despite the exponential increase in action space size.

2. RELATED WORK:

We examine prior work in three broad categories: text-based game playing agents and frameworks as well as knowledge graphs used for natural language generation and game playing agents. LSTM-DQN (Narasimhan et al., 2015) , considers verb-noun actions up to two-words in length. Separate Q-Value estimates are produced for each possible verb and object, and the action consists of pairing the maximally valued verb combined with the maximally valued object. The DRRN algorithm for choice-based games (He et al., 2016; Zelinka, 2018) estimates Q-Values for a particular action from a particular state. Fulda et al. (2017) use Word2Vec (Mikolov et al., 2013) to aid in extracting affordances for items in these games and use this information to produce relevant action verbs. Zahavy et al. (2018) reduce the combinatorially-sized action space into a discrete form using a walkthrough of the game and introduce the Action Elimination DQN, which learns to eliminate actions unlikely to cause a world change. Côté et al. (2018) introduce TextWorld, a framework for procedurally generating parser-based games, allowing a user to control the difficulty of a generated game. Yuan et al. (2019) introduce the concept of interactive question-answering in the form of QAit-modeling QA tasks in TextWorld. Urbanek et al. (2019) introduce Light, a dataset of crowdsourced text-adventure game dialogs focusing on giving collaborative agents the ability to generate contextually relevant dialog and emotes. Hausknecht et al. (2019a) have open-sourced Jericho 2 , an optimized interface for playing human-made IF games-formalizing this task. They further provide a comparative study of various types of agents on their set of games, testing the performance of heuristic based agents such as NAIL (Hausknecht et al., 2019b) and various reinforcement learning agents are benchmarked. We use Jericho and the tools that it provides to develop our agents.

Knowledge graphs have been shown to be useful representations for a variety of tasks surrounding natural language generation and interactive fiction. Ghazvininejad et al. (2017) and Guan et al. (2018) effectively use knowledge graph representations to improve neural conversational and story ending prediction models respectively. Ammanabrolu et al. (2019) explore procedural content generation in text-adventure games-looking at constructing a quest for a given game world, and use knowledge graphs to ground generative systems trained to produce quest content. From the perspective of text-game playing agent and most in line with the spirit of our work, Ammanabrolu & Riedl (2019a) present the Knowledge Graph DQN or KG-DQN, an approach where a knowledge graph built during exploration is used as a state representation for a deep reinforcement learning based agent. Ammanabrolu & Riedl (2019b) further expand on this work, exploring methods of transferring control policies in text-games, using knowledge graphs to seed an agent with useful commonsense knowledge and to transfer knowledge between different games within a domain. Both of these works, however, identify a discrete set of actions required to play the game beforehand and so do not fully tackle the issue of the combinatorial action space.

3. STATE AND ACTION SPACES:

Formally, IF games are partially observable Markov decision processes (POMDP), represented as a 7-tuple of S, T, A, Ω, O, R, γ 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 (Côté et al., 2018; Hausknecht et al., 2019a) . To deal with the resulting twin challenges of partial observability and combinatorial actions, we use a knowledge graph based state space and a template-based action space-each described in detail below.

Knowledge Graph State Space. Building on Ammanabrolu & Riedl (2019a) , we use a knowledge graph as a state representation that is learnt during exploration. The knowledge graph is stored as a set of 3-tuples of subject, relation, object . These triples are extracted from the observations using Stanford's Open Information Extraction (OpenIE) (Angeli et al., 2015) . Human-made IF games often contain relatively complex semi-structured information that OpenIE is not designed to parse and so we add additional rules to ensure that we are parsing the relevant information.

Updated after every action, the knowledge graph helps the agent form a map of the world that it is exploring, in addition to retaining information that it has learned such as the affordances associated with an object, the properties of a character, current inventory, etc. Nodes relating to such information are shown on the basis of their relation to the agent which is presented on the graph using a "you" node (see example in Fig. 2a ).

Ammanabrolu & Riedl (2019a) build a knowledge graph in a similar manner but restrict themselves to a single domain. In contrast, we test our methods on a much more diverse set of games defined in the Jericho framework (Hausknecht et al., 2019a) . These games are each structured differentlycovering a wider variety of genres-and so to be able to extract the same information from all of them in a general manner, we relax many of the rules found in Ammanabrolu & Riedl (2019a) . To aid in the generalizability of graph building, we introduce the concept of interactive objects-items that an agent is able to directly interact with in the surrounding environment. These items are directly linked to the "you" node, indicating that the agent can interact with them, and the node for the current room, showing their relative position. All other triples built from the graph are extracted by OpenIE. Further details regarding knowledge graph updates are found in Appendix B.1 An example of a graph built using these rules is seen in Fig. 2a .

Template Action Space. Templates are subroutines used by the game's parser to interpret the player's action. They consist of interchangeable verbs phrases (V P ) optionally followed by prepositional phrases (V P P P ), e.g. ([carry/hold/take]

) and ([drop/throw/discard/put] [at/against/on/onto] ), where the verbs and prepositions within [.] are aliases. As shown in Figure 2b , actions may be constructed from templates by filling in the template's blanks using words in the game's vocabulary. Templates and vocabulary words are programmatically accessible through the Jericho framework and are thus available for every IF game. Further details about how we prioritize interchangeable verbs and prepositions are available in Appendix B.2.

4. KNOWLEDGE GRAPH ADVANTAGE ACTOR CRITIC:

Combining the knowledge-graph state space with the template action space, Knowledge Graph Advantage Actor Critic or KG-A2C, is an on-policy reinforcement learning agent that collects experience from many parallel environments. We first discuss the architecture of KG-A2C, then detail the training algorithm. As seen in Fig. 1 , KG-A2C's architecture can broadly be described in terms of encoding a state representation and then using this encoded representation to decode an action. We describe each of these processes below.

Input Representation. The input representation network is broadly divided into three parts: an observation encoder, a score encoder, and the knowledge graph. At every step an observation consisting of several components is received: o t = (o t desc , o tgame , o tinv , a t-1 ) corresponding to the room description, game feedback, inventory, and previous action, and total score R t . The room description o t desc is a textual description of the agent's location, obtained by executing the command "look." The game feedback o tgame is the simulators response to the agent's previous action and con- sists of narrative and flavor text. The inventory o tinv and previous action a t-1 components inform the agent about the contents of its inventory and the last action taken respectively.

The observation encoder processes each component of o t using a separate GRU encoder. As we are not given the vocabulary that o t is comprised of, we use subword tokenization-specifically using the unigram subword tokenization method described in Kudo & Richardson (2018) . This method predicts the most likely sequence of subword tokens for a given input using a unigram language model which, in our case, is trained on a dataset of human playthroughs of IF games3 and contains a total vocabulary of size 8000. For each of the GRUs, we pass in the final hidden state of the GRU at step t -1 to initialize the hidden state at step t. We concatenate each of the encoded components and use a linear layer to combine them into the final encoded observation o t .

At each step, we update our knowledge graph G t using o t as described in Sec. 3 and it is then embedded into a single vector g t . Following Ammanabrolu & Riedl (2019a) we use Graph Attention networks or GATs (Veličković et al., 2018) with an attention mechanism similar to that described in Bahdanau et al. (2014) . Node features are computed as

H = {h 1 , h 2 , . . . , h N }, h i ∈ IR F ,

where N is the number of nodes and F the number of features in each node, consist of the average subword embeddings of the entity and of the relations for all incoming edges using our unigram language model. Self-attention is then used after a learnable linear transformation W ∈ IR 2F×F applied to all the node features. Attention coefficients α ij are then computed by softmaxing k ∈ N with N being the neighborhood in which we compute the attention coefficients and consists of all edges in G t .

EQUATION

α ij = exp(e ij )

k∈N exp(e ik )

(2) where p ∈ IR 2F is a learnable parameter. The final knowledge graph embedding vector g t is computed as:

EQUATION

where k refers to the parameters of the k th independent attention mechanism, W g and b g the weights and biases of the output linear layer, and represents concatenation. The final component of state embedding vector is a binary encoding c t of the total score obtained so far in the game-giving the agent a sense for how far it has progressed in the game even when it is not collecting reward. The state embedding vector is then calculated as s t = g t ⊕ o t ⊕ c t .

Action Decoder. The state embedding vector s t is then used to sequentially construct an action by first predicting a template and then picking the objects to fill into the template using a series of Decoder GRUs. This gives rise to a template policy π T and a policy for each object π Oi . Architecture wise, at every decoding step all previously predicted parts of the action are encoded and passed along with s t through an attention layer which learns to attend over these representations-conditioning every predicted object on all the previously predicted objects and template. All the object decoder GRUs share parameters while the template decoder GRU T remains separate.

To effectively constrain the space of template-actions, we introduce the concept of a graph mask, leveraging our knowledge graph at that timestep G t to streamline the object decoding process. Formally, the graph mask m t = {o : o ∈ G t ∧ o ∈ V }, consists of all the entities found within the knowledge graph G t and vocabulary V and is applied to the outputs of the object decoder GRUsrestricting them to predict objects in the mask. Generally, in an IF game, it is impossible to interact with an object that you never seen or that are not in your inventory and so the mask lets us explore the action space more efficiently. To account for cases where this assumption does not hold, i.e. when an object that the agent has never interacted with before must be referenced in order to progress in the game, we randomly add objects o ∈ V to m t with a probability p m . An example of the graph-constrained action decoding process is illustrated in Fig. 2b .

4.1. TRAINING:

We adapt the Advantage Actor Critic (A2C) method (Mnih et al., 2016) to train our network, using multiple workers to gather experiences from the simulator, making several significant changes along the way-as described below.

Valid Actions. Using a template-action space there are millions of possible actions at each step. Most of these actions do not make sense, are ungrammatical, etc. and an even fewer number of them actually cause the agent effect change in the world. Without any sense for which actions present valid interactions with the world, the combinatorial action space becomes prohibitively large for effective exploration.

We thus use the concept of valid actions, actions that can change the world in a particular state. These actions can usually be recognized through the game feedback, with responses like "Nothing happens" or "That phrase is not recognized." In practice, we follow Hausknecht et al. (2019a) and use the valid action detection algorithm provided by Jericho. Formally, V alid(s t ) = a 0 , a 1 ...a N and from this we can construct the corresponding set of valid templates T valid (s t ) = τ 0 , τ 1 ...τ N . We further define a set of valid objects O valid (s t ) = o 0 , o 1 ...o M which consists of all objects in the graph mask as defined in Sec. 4. This lets us introduce two cross-entropy loss terms to aid the action decoding process. The template loss given a particular state and current network parameters is applied to the decoder GRU T . Similarly, the object loss is applied across the decoder GRU O and is calculated by summing cross-entropy loss from all the object decoding steps.

EQUATION

y τi = 1 τ i ∈ T valid (s t ) 0 else y oi = 1 o i ∈ O valid (s t ) 0 else

Updates. A2C training starts with calculating the advantage of taking an action in a state A(s t , a t ), defined as the value of taking an action Q(s t , a t ) compared to the average value of taking all possible valid actions in that state V (s t ):

EQUATION

V (s t ) is predicted by the critic as shown in Fig. 1 and r t is the reward received at step t.

The action decoder or actor is then updated according to the gradient:

EQUATION

updating the template policy π T and object policies π Oi based on the fact that each step in the action decoding process is conditioned on all the previously decoded portions. The critic is updated with respect to the gradient:

1 2 ∇ θ (Q(s t , a t ; θ t ) -V (s t ; θ t )) 2 (9)

bringing the critic's prediction of the value of being in a state closer to its true underlying value. We further add an entropy loss over the valid actions, designed to prevent the agent from prematurely converging on a trajectory.

L E (s t , a t ; θ t ) = a∈V (st)

P (a|s t )logP (a|s t ) (10)

5. EXPERIMENTAL RESULTS:

The KG-A2C is tested on a suite of Jericho supported games and is compared to strong, established baselines. Additionally, as encouraged by Hausknecht et al. (2019a) , we present the set of handicaps used by our agents: (1) Jericho's ability to identify valid actions and (2) the Load, Save handicap in order to acquire o t desc and o tinv using the look and inventory commands without changing the game state. Hyperparameters are provided in Appendix C.

Template DQN Baseline. We compare KG-A2C against Template-DQN, a strong baseline also utilizing the template based action space. TDQN (Hausknecht et al., 2019a) is an extension of LSTM-DQN (Narasimhan et al., 2015) to template-based action spaces. This is accomplished using three output heads: one for estimating the Q-Values over templates Q(s t , u)∀u ∈ T and two for estimating Q-Values Q(s t , o 1 ), Q(s t , o 2 )∀o i ∈ O over vocabulary to fill in the blanks of the template. The final executed action is constructed by greedily sampling from the predicted Q-values. Importantly, TDQN uses the same set of handicaps as KG-A2C allowing a fair comparison between these two algorithms. In order to understand the contributions of different components of KG-A2C's architecture, we ablate KG-A2C's knowledge graph, template-action space, and valid-action loss. These ablations are performed on Zork14 and result in the following agents:

A2C removes all components of KG-A2C's knowledge graph. In particular, the state embedding vector is now computed as s t = o t ⊕c t and the graph mask is not used to constrain action decoding.

KG-A2C-no-gat remove's the Graph Attention network, but retains the graph masking components. The knowledge graph is still constructed as usual but the agent uses the same state embedding vector as A2C.

KG-A2C-no-mask ablates the graph mask for purposes of action decoding. The knowledge graph is constructed as usual and the agent retains graph attention.

On Zork1 as shown in Figure 3 , we observe similar asymptotic performance between the all of the ablations -all reach approximately 34 points. This level of performance corresponds to a local optima where the agent collects the majority of available rewards without fighting the troll. Several other authors also report scores at this threshold (Jain et al., 2019; Zahavy et al., 2018) . In terms of learning speed, the methods which have access to either the graph attention or the graph mask converge slightly faster than pure A2C which has neither. To further understand these differences we performed a larger study across the full set of games comparing KG-A2C-full with KG-A2C-no-mask. The results in Table 2 show KG-A2C-full outperforms KG-A2C-no-mask on 10 games and is outperformed by KG-A2C-no-mask on 6. From this larger study we thus conclude the graph mask and knowledge graph are broadly useful components.

We perform two final ablations to study the importance of the supervised valid-action loss and the template action space: KG-A2C-unsupervised In order to understand the importance of training with valid-actions, KG-A2C-unsupervised is not allowed to access the list of valid actions-the valid-action-losses L T and L O are disabled and L E now based on the full action set. Thus, the agent must explore the template action space manually. KG-A2C-unsupervised, when trained for the same number of steps as all the other agents, fails to achieve any score. We can infer that the valid action auxiliary loss remains an important part of the overall algorithm, and access to the knowledge graph alone is not yet sufficient for removing this auxiliary loss. KG-A2C-seq discards the template action space and instead decodes actions word by word up to a maximum of four words. A supervised cross-entropy-based valid action loss L Valid is now calculated by selecting a random valid action a tvalid ∈ Valid(s t ) and using each token in it as a target label. As this action space is orders of magnitude larger than template actions, we use teacher-forcing to enable more effective exploration while training the agent-executing a tvalid with a probability p valid = 0.5 and the decoded action otherwise. All other components remain the same as in the full KG-A2C. KG-A2C-seq reaches a relatively low asymptotic performance of 8 points. This agent, using a action space consisting of the full vocabulary, performs significantly worse than the rest of the agents even when given the handicaps of teacher forcing and being allowed to train for significantly longerindicating that the template based action space is also necessary for effective exploration.

7. CONCLUSION:

Tabula rasa reinforcement learning offers an intuitive paradigm for exploring goal driven, contextually aware natural language generation. The sheer size of the natural language action space, however, has proven to be out of the reach of existing algorithms. In this paper we introduced KG-A2C, a novel learning agent that demonstrates the feasibility of scaling reinforcement learning towards natural language actions spaces with hundreds of millions of actions. The key insight to being able to efficiently explore such large spaces is the combination of a knowledge-graph-based state space and a template-based action space. The knowledge graph serves as a means for the agent to understand its surroundings, accumulate information about the game, and disambiguate similar textual observations while the template-based action space lends a measure of structure that enables us to exploit that same knowledge graph for language generation. Together they constrain the vast space of possible actions into the compact space of sensible ones. A suite of experiments across a diverse set of 28 human-made IF games shows wide improvement over TDQN, the current state-of-the-art templatebased agent. Finally, an ablation study replicates state-of-the-art performance on Zork1 even though KG-A2C is using an action space six orders of magnitude larger than previous agents-indicating the overall efficacy of our combined state-action space. Candidate interactive objects are identified by performing part-of-speech tagging on the current observation, identifying singular and proper nouns as well as adjectives, and are then filtered by checking if they can be examined using the command examine OBJ. Only the interactive objects not found in the inventory are linked to the node corresponding to the current room and the inventory items are linked to the "you" node. The only other rule applied uses the navigational actions performed by the agent to infer the relative positions of rooms, e.g. kitchen, down, cellar when the agent performs go down when in the kitchen to move to the cellar.

B.2 TEMPLATE PREPROCESSING:

Templates are processed by selecting a single verb and preposition from the aliases. For the sake of agent explainability, we pick the verb and preposition that are most likely to be used by humans when playing IF games. This is done by assessing token frequencies from a dataset of human playthroughs such as those given in ClubFloyd5 . This dataset consists of 425 unique play sessions and 273,469 state-action pairs. The examples given earlier, ([carry/hold/take] ) and ([drop/throw/discard/put] [at/against/on/onto] ), would then be converted to take and put on .

C EXPERIMENT DETAILS:

Episodes are terminated after 100 valid steps or game over/victory. Agents that decode invalid actions often wouldn't make it very far into the game, and so we only count valid-actions against the hundred step limit. All agents are trained individually on each game and then evaluated on that game. All A2C based agents are trained using data collected from 32 parallel environments. TDQN was trained using a single environment. Hyperparameters for all agents were tuned on the game of Zork1 and held constant across all other games. Final reported scores are an average over 5 runs of each algorithm. To understand how humans progress in Zork1, a group of 10 human players-familiar with IF games-were asked to play Zork1 for the first time (with no access to walkthroughs). Half of the players reached a game score of around 40 before dying to the first beatable NPC, a troll, mostly due to neglecting to collect a weapon to fight it with beforehand. Three of the remaining players died to hidden traps even before reaching this point, achieving scores between 5 and 15. The final two players made it significantly past the troll gaining scores of around 70.

The following transcript of KG-A2C playing Zork1, shows top predicted probabilities for templates and objects. Action: east Score: 5 ---Obs: Desc: Canyon View You are at the top of the Great Canyon on its west wall. From here there is a marvelous view of the canyon and parts of the Frigid River upstream. Across the canyon, the walls of the White Cliffs join the mighty ramparts of the Flathead Mountains to the east. Following the Canyon upstream to the north, Aragain Falls may be seen, complete with rainbow. The mighty Frigid River flows out from a great dark cavern. To the west and south can be seen an immense forest, stretching for miles around. A path leads northwest. It is possible to climb down into the canyon from here. Inv: You are emptyhanded. Feedback: Canyon View You are at the top of the Great Canyon on its west wall. From here there is a marvelous view of the canyon and parts of the Frigid River upstream. Across the canyon, the walls of the White Cliffs join the mighty ramparts of the Flathead Mountains to the east. Following the Canyon upstream to the north, Aragain Falls may be seen, complete with rainbow. The mighty Frigid River flows out from a great dark cavern. To the west and south can be seen an immense forest, stretching for miles around. A path leads northwest. It is possible to climb down into the canyon from here. Action: west Score: 5 ---Obs: Desc: Behind House You are behind the white house. A path leads into the forest to the east. In one corner of the house there is a small window which is slightly ajar. Inv: You are emptyhanded. Feedback: Behind House You are behind the white house. A path leads into the forest to the east. In one corner of the house there is a small window which is slightly ajar. Template probs: open OBJ: 0.953, west: 0.036, south: 0.006 Object probs: small: 0.898, window: 0.102 Interactive objects: path, window, small, white, house, all Action: open house Score: 5 ---Obs: Desc: Behind House You are behind the white house. A path leads into the forest to the east. In one corner of the house there is a small window which is slightly ajar. Inv: You are emptyhanded. Feedback:

The window is closed. Template probs: open OBJ: 0.943, west: 0.047 Object probs: small: 0.88, window: 0.12 Interactive objects: path, window, small, white, house, all Action: open path Score: 5 ---Obs: Desc: Behind House You are behind the white house. A path leads into the forest to the east. In one corner of the house there is a small window which is slightly ajar. Inv: You are emptyhanded. Feedback: You must tell me how to do that to a way. Template probs: open OBJ: 0.899, east: 0.048, west: 0.044, south: 0.004 Object probs: window: 0.58, small: 0.417, kitche: 0.002 Interactive objects: path, window, small, white, house, all Action: open window Score: 5 ---Obs: Desc: Behind House You are behind the white house. A path leads into the forest to the east. In one corner of the house there is a small window which is open. Inv: You are emptyhanded. Feedback: With great effort, you open the window far enough to allow entry. Template probs: west: 0.997 Object probs: small: 0.951, window: 0.049 Interactive objects: path, window, small, white, house, all Action: west Score: 5 ---Obs: Desc: Kitchen You are in the kitchen of the white house. A table seems to have been used recently for the preparation of food. A passage leads to the west and a dark staircase can be seen leading upward. A dark chimney leads down and to the east is a small window which is open. On the table is an elongated brown sack, smelling of hot peppers. A bottle is sitting on the table. The glass bottle contains A quantity of water Inv: You are emptyhanded. Feedback: Kitchen You are in the kitchen of the white house.

A table seems to have been used recently for the preparation of food. A passage leads to the west and a dark staircase can be seen leading upward. A dark chimney leads down and to the east is a small window which is open. On the table is an elongated brown sack, smelling of hot peppers. A bottle is sitting on the table. The glass bottle contains A quantity of water Template probs: take OBJ: 0.47, west: 0.351, turn on OBJ: 0.061, blow out OBJ: 0.052, down: 0.023, open OBJ: 0.012, east: 0.008, close OBJ: 0.006, throw OBJ at OBJ: 0.006 Object probs: window: 0.683, small: 0.317 Interactive objects: kitchen, window, passage, staircase, glass, sack, water, small, table, chimney, bottle, quantity, brown, all Action: west in the center of the room. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: You must tell me how to do that to a brass lantern.

Template probs: open OBJ: 0.503, push OBJ: 0.129, west: 0.1, take OBJ: 0.053, turn on OBJ: 0.051, throw OBJ at OBJ: 0.041, put down OBJ: 0.029, put OBJ in OBJ: 0.021, put OBJ on OBJ: 0.02, down: 0.009 Object probs: window: 0.677, small: 0.323 Interactive objects: brass, strange, trophy, elvish, rug, oriental, light, lettering, antiquity, sword, gothic , west, door, large, wooden, lantern , case, all Action: push rug Score: 15 ---Obs: Desc: Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: With a great effort, the rug is moved to one side of the room, revealing the dusty cover of a closed trap door.

Template probs: open OBJ: 0.582, push OBJ: 0.082, down: 0.074, take OBJ: 0.065, put down OBJ: 0.025, turn on OBJ: 0. 0.068, put down OBJ: 0.033, south: 0.029, west: 0.019, throw OBJ at OBJ: 0.016 Object probs: west: 0.08, small: 0.08, window: 0.073, door: 0.067, rug: 0.057, letter: 0.047, wooden: 0.045, gothic: 0.041, strang: 0.035, lanter: 0.034 Interactive objects: light, ramp, large, brass, stiletto, crawlway, dark, narrow, lantern, bag, suspicious, metal, all, wall, passageway Action: take dark Score: 40 ---Obs: Desc: Cellar You are in a dark and damp cellar with a narrow passageway leading north, and a crawlway to the south. On the west is the bottom of a steep metal ramp which is unclimbable. There is a suspiciouslooking individual, holding a large bag, leaning against one wall. He is armed with a deadly stiletto. Inv: You are carrying A brass lantern (providing light) Feedback: You cant be serious. Template probs: down: 0.289, open OBJ: 0.201, take OBJ: 0.103, close OBJ: 0.091, turn on OBJ: 0.066, push OBJ: 0.065, put down OBJ: 0.043, throw OBJ at OBJ: 0.022, south: 0.021, west: 0.018 Object probs: west: 0.081, small: 0.076, window: 0.069, door: 0.068, rug: 0.057, letter: 0.048, wooden: 0.045, gothic: 0.042, strang: 0.036, lanter: 0.035 Interactive objects: light, ramp, large, brass, stiletto, crawlway, dark, narrow, lantern, bag, suspicious, metal, all, wall, passageway Action: put out passag Score: 40 ---Obs: Desc: Cellar You are in a dark and damp cellar with a narrow passageway leading north, and a crawlway to the south. On the west is the bottom of a steep metal ramp which is unclimbable. There is a suspiciouslooking individual, holding a large bag, leaning against one wall. He is armed with a deadly stiletto. The thief, finding nothing of value, left disgusted. Inv: You are carrying A brass lantern ( providing light) The thief, finding nothing of value, left disgusted. Feedback: Pushing the chute isnt notably helpful. Someone carrying a large bag is casually leaning against one of the walls here. He does not speak, but it is clear from his aspect that the bag will be taken only over his dead body. Template probs: open OBJ: 0.211, take OBJ: 0.205, push OBJ: 0.188, south: 0.132, west: 0.105, close OBJ: 0.057, turn on OBJ: 0.026, go around OBJ: 0.02, east: 0.017, down: 0.016 Object probs: small: 0.112, window: 0.103, west: 0.075, door: 0.063, rug: 0.054, wooden: 0.044, letter: 0.04, gothic: 0.037, strang: 0.032, kitche: 0.031 Interactive objects: light, ramp, large, brass, stiletto, crawlway, walls, dark, narrow, thief, lantern, chute , bag, suspicious, metal, all, wall, passageway Action: west Score: 40 ---Obs: Desc: Cellar You are in a dark and damp cellar with a narrow passageway leading north, and a crawlway to the south. On the west is the bottom of a steep metal ramp which is unclimbable. There is a suspiciouslooking individual, holding a large bag, leaning against one wall. He is armed with a deadly stiletto. A quick thrust pinks your left arm, and blood starts to trickle down. Inv: You are carrying A brass lantern (providing light) The thief, finding nothing of value, left disgusted. Feedback: You dont have the way. Template probs: take OBJ: 0.246, open OBJ: 0.211, push OBJ: 0.19, south: 0.091, west: 0.082, close OBJ: 0.059, turn on OBJ: 0.041, down: 0.026, go around OBJ: 0.017, east: 0.012 Object probs: small: 0.097, window: 0.087, west: 0.078, door: 0.065, rug: 0.056, wooden: 0.045, letter: 0.043, gothic: 0.038, strang: 0.034, lanter: 0.032 Interactive objects: light, ramp, large, brass, stiletto, crawlway, dark, narrow, lantern, bag, suspicious, metal, all, wall, passageway Action: south Score: 40 ---Obs: Desc: East of Chasm You are on the east edge of a chasm, the bottom of which cannot be seen. A narrow passage goes north, and the path you are on continues to the east. Inv: You are carrying A brass lantern (providing light) Feedback: The brass lantern is now on. East of Chasm You are on the east edge of a chasm, the bottom of which cannot be seen. A narrow passage goes north, and the path you are on continues to the east.

:

Code available at https://github.com/rajammanabrolu/KG-A2C

https://github.com/microsoft/jericho

http://www.allthingsjacq.com/interactive_fiction.html#clubfloyd

A map of Zork1 with annotated rewards can be found in Appendix D along with a transcript of KG-A2C playing this game.

http://www.allthingsjacq.com/interactive_fiction.html#clubfloyd

Figures and Tables:

Figure 1: The full KG-A2C architecture. Solid lines represent computation flow along which the gradient can be back-propagated.

Figure 2: An overall example of the knowledge graph building and subsequent action decoding process for a given state in Zork1, illustrating the use of interactive objects and the graph mask.

Figure 3: Ablation results on Zork1, averaged across 5 independent runs.

Figure 4: Learning curves for KGA2C-full. Shaded regions indicate standard deviations.

shows how KG-A2C fares across a diverse set of games supported by Jericho-testing the agent's ability to generalize to different genres, game structures, reward functions, and state-action spaces. KG-A2C matches or outperforms TDQN on 23 out of the 28 games that we test on. Our agent is thus shown to be capable of extracting a knowledge graph that can sufficiently constrain the template based action space to enable effective exploration in a broad range of games.

Table content: <table><tr><td>6 ABLATION STUDY</td><td/><td/><td/><td/><td/></tr><tr><td>Game 905 acorncourt</td><td>|T | 82 151</td><td>|V | 296 343</td><td>TDQN 0 1.6</td><td>KGA2C 0 0.3</td><td>MaxRew 1 30</td></tr><tr><td>advent  † adventureland anchor awaken balances deephome detective dragon enchanter inhumane jewel karn library ludicorp moonlit omniquest pentari snacktime sorcerer spellbrkr spirit temple zenon zork1 zork3 ztuu</td><td>189 156 260 159 156 173 197 177 290 141 161 161 173 187 166 207 155 201 288 333 169 175 149 237 214 186</td><td>786 398 2257 505 452 760 344 1049 722 409 657 657 510 503 669 460 472 468 1013 844 1112 622 401 697 564 607</td><td>36 0 0 0 4.8 1 169 -5.3 8.6 0.7 0 1.2 6.3 6 0 16.8 17.4 9.7 5 18.7 0.6 7.9 0 9.9 0 4.9</td><td>36 0 0 0 10 1 207.9 0 12.1 3 1.8 0 14.3 17.8 0 3 50.7 0 5.8 21.3 1.3 7.6 3.9 34 .1 9.2</td><td>350 100 100 50 51 300 360 25 400 300 90 90 30 150 1 50 70 50 400 600 250 35 350 350 7 100</td></tr></table>

Raw scores comparing KG-A2C to TDQN across a wide set of games supported by Jericho.

Table content: <table/>

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations (ICLR), 2018. Xusen Yin and Jonathan May. Comprehensible context-driven text game playing. CoRR, abs/1905.02265, 2019.

Table content: <table><tr><td>A ABLATION RESULTS</td></tr><tr><td>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 J 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 Infor-mation Processing Systems 31, pp. 3562-3573. Curran Associates, Inc., 2018. Mikulás Zelinka. Using reinforcement learning to learn how to play text-based games. CoRR, abs/1801.01999, 2018. Game |T | |V | KGA2C-Full KGA2C-unmasked MaxRew 905 82 296 0 0 acorncourt 151 343 0.3 0.3 advent  † 189 786 36 36 adventureland 156 398 0 0 anchor 260 2257 0 0 awaken 159 505 0 0 balances 156 452 10 10 deephome 173 760 1 29.2 detective 197 344 207.9 141 dragon 177 1049 0 -.2 enchanter 290 722 12.1 7.6 inhumane 141 409 3 10.2 jewel 161 657 1.8 1.3 karn 161 657 0 0 library 173 510 14.3 9.6 ludicorp 187 503 17.8 17.9 moonlit 166 669 0 0 omniquest 207 460 3 5.4 pentari 155 472 50.7 50.4 snacktime 201 468 0 0 sorcerer 288 1013 5.8 16.8 spellbrkr 333 844 21.3 30.1 spirit 169 1112 1.3 1.3 temple 175 622 7.6 6.4 zenon 149 401 3.9 3.1 zork1 237 697 34 27 zork3 214 564 .1 .1 ztuu 186 607 9.2 5</td></tr><tr><td>Table 2: Ablations</td></tr><tr><td>B IMPLEMENTATION DETAILS</td></tr></table>

Obs: Desc: West of House You are standing in an open field west of a white house, with a boarded front door.There is a small mailbox here. Inv: You are emptyhanded. Feedback: West of House You are standing in an open field west of a white house, with a boarded front door. There is a small mailbox here. Up a Tree You are about 10 feet above the ground nestled among some large branches. The nearest branch above you is above your reach. Beside you on the branch is a small birds nest. In the birds nest is a large egg encrusted with precious jewels, apparently scavenged by a childless songbird. The egg is covered with fine gold inlay, and ornamented in lapis lazuli and motherofpearl. Unlike most eggs, this one is hinged and closed with a delicate looking clasp. The egg appears extremely fragile. Inv: You are emptyhanded. Feedback: Up a Tree You are about 10 feet above the ground nestled among some large branches. The nearest branch above you is above your reach. Beside you on the branch is a small birds nest. In the birds nest is a large egg encrusted with precious jewels, apparently scavenged by a childless songbird. The egg is covered with fine gold inlay, and ornamented in lapis lazuli and motherofpearl. Unlike most eggs, this one is hinged and closed with a delicate looking clasp. Up a Tree You are about 10 feet above the ground nestled among some large branches. The nearest branch above you is above your reach. Beside you on the branch is a small birds nest. In the birds nest is a large egg encrusted with precious jewels, apparently scavenged by a childless songbird. The egg is covered with fine gold inlay, and ornamented in lapis lazuli and motherofpearl. Unlike most eggs, this one is hinged and closed with a delicate looking clasp. The egg appears extremely fragile. You hear in the distance the chirping of a song bird. Inv: You are emptyhanded. You hear in the distance the chirping of a song bird. Feedback: It is already open. Up a Tree You are about 10 feet above the ground nestled among some large branches. The nearest branch above you is above your reach. Beside you on the branch is a small birds nest. Inv: You are carrying A jewelencrusted egg Feedback: Taken. North of House You are facing the north side of a white house. There is no door here, and all the windows are boarded up. To the north a narrow path winds through the trees. Inv: You are emptyhanded. Feedback: North of House You are facing the north side of a white house. There is no door here, and all the windows are boarded up. To the north a narrow path winds through the trees. West of House You are standing in an open field west of a white house, with a boarded front door.Obs: Desc: Forest This is a forest, with trees in all directions. To the east, there appears to be sunlight. Inv: You are emptyhanded. Feedback: Forest This is a forest, with trees in all directions. To the east, there appears to be sunlight. Template probs: open OBJ: 0.49, south: 0.304, east: 0.116, west: 0.04, north: 0.016, go around OBJ: 0.011, throw OBJ at OBJ: 0.006, northwest: 0.006, blow out OBJ: 0.006 Forest Path This is a path winding through a dimly lit forest. The path heads northsouth here. One particularly large tree with some low branches stands at the edge of the path. Inv: You are emptyhanded. Feedback: Forest Path This is a path winding through a dimly lit forest. The path heads northsouth here . One particularly large tree with some low branches stands at the edge of the path. Forest Path This is a path winding through a dimly lit forest. The path heads northsouth here. One particularly large tree with some low branches stands at the edge of the path. Inv: You are emptyhanded. Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. You hear in the distance the chirping of a song bird. Feedback: Forest This is a dimly lit forest, with large trees all around. You hear in the distance the chirping of a song bird. Clearing You are in a small clearing in a well marked forest path that extends to the east and west . Inv: You are emptyhanded. Feedback: Clearing You are in a small clearing in a well marked forest path that extends to the east and west.Template probs: open OBJ: 0.451, east: 0.364, west: 0.164, north: 0.008, throw OBJ at OBJ: 0.005 Object probs: window: 0.592, small: 0.405, kitche: 0.002 Interactive objects: forest, path, all

Table content: <table><tr><td colspan="2">Template probs: up: 0.386, open OBJ: 0.358, east: 0.123, west: 0.06, north: 0.023, go around OBJ: 0.014, blow</td></tr><tr><td/><td>out OBJ: 0.01, northwest: 0.009, throw OBJ at OBJ: 0.008</td></tr><tr><td colspan="2">Object probs: window: 0.701, small: 0.299</td></tr><tr><td colspan="2">Interactive objects: tree, path, branches, forest, large, all</td></tr><tr><td colspan="2">Action: up</td></tr><tr><td colspan="2">Score: 0 Object probs: window: 0.7, small: 0.3</td></tr><tr><td colspan="2">---Interactive objects: forest, all, trees</td></tr><tr><td colspan="2">Action: east Score: 5 ---Obs: Desc: Template probs: south: 0.386, open OBJ: 0.358, east: 0.123, west: 0.06, north: 0.023, go around OBJ: 0.014, blow out OBJ: 0.01, northwest: 0.009, throw OBJ at OBJ: 0.008 Obs: Desc: The egg Object probs: window: 0.701, small: 0.298</td></tr><tr><td colspan="2">appears extremely fragile. Interactive objects: tree, path, branches, forest, large, all</td></tr><tr><td colspan="2">Template probs: west: 0.43, open OBJ: 0.18, go around OBJ: 0.074, east: 0.064, north: 0.063, south: 0.052, Action: open all</td></tr><tr><td colspan="2">take OBJ: 0.041, put down OBJ: 0.023, down: 0.014, close OBJ: 0.009 Score: 5</td></tr><tr><td colspan="2">Object probs: small: 0.213, window: 0.184, house: 0.116, egg: 0.068, white: 0.067, path: 0.062, branch: 0.042, ---</td></tr><tr><td colspan="2">kitche: 0.024, nest: 0.018, ground: 0.009 Interactive objects: nest, large, egg, ground, branches, all, branch, tree Action: open nest Obs: Desc: Feedback: Its not clear what youre referring to.</td></tr><tr><td colspan="2">Score: 0 Template probs: open OBJ: 0.331, south: 0.259, east: 0.24, west: 0.087, north: 0.031, go around OBJ: 0.013,</td></tr><tr><td>---</td><td>blow out OBJ: 0.011, northwest: 0.01, throw OBJ at OBJ: 0.009</td></tr><tr><td colspan="2">Object probs: window: 0.701, small: 0.299 Interactive objects: tree, path, branches, forest, large, all Action: east Score: 5 ---Obs: Desc: Template probs: west: 0.347, open OBJ: 0.182, go around OBJ: 0.085, east: 0.077, north: 0.073, south: 0.058, take OBJ: 0.045, put down OBJ: 0.026, down: 0.018, close OBJ: 0.013 Obs: Desc: Template probs: south: 0.38, open OBJ: 0.281, east: 0.174, west: 0.072, north: 0.034, go around OBJ: 0.015,</td></tr><tr><td colspan="2">Object probs: small: 0.213, window: 0.183, house: 0.117, egg: 0.068, white: 0.067, path: 0.062, branch: 0.042, blow out OBJ: 0.013, northwest: 0.012, throw OBJ at OBJ: 0.008</td></tr><tr><td colspan="2">kitche: 0.024, nest: 0.018, ground: 0.009 Object probs: window: 0.7, small: 0.299</td></tr><tr><td colspan="2">Interactive objects: nest, large, egg, ground, branches, all, branch, tree Interactive objects: forest, large, all, trees</td></tr><tr><td colspan="2">Action: take egg Action: south</td></tr><tr><td colspan="2">Score: 0 Score: 5</td></tr><tr><td>------</td><td/></tr><tr><td colspan="2">Obs: Desc: Template probs: down: 0.417, open OBJ: 0.181, go around OBJ: 0.074, east: 0.065, north: 0.063, south: 0.053, Obs: Desc:</td></tr><tr><td/><td>take OBJ: 0.042, put down OBJ: 0.025, down: 0.014, close OBJ: 0.01</td></tr><tr><td colspan="2">Object probs: small: 0.213, window: 0.184, house: 0.116, egg: 0.068, white: 0.067, path: 0.062, branch: 0.042,</td></tr><tr><td/><td>kitche: 0.024, nest: 0.018, ground: 0.009</td></tr><tr><td colspan="2">Interactive objects: nest, large, egg, ground, branches, all, branch, tree</td></tr><tr><td colspan="2">Action: down</td></tr><tr><td colspan="2">Score: 5</td></tr><tr><td>---</td><td/></tr><tr><td colspan="2">Obs: Desc: Forest Path This is a path winding through a dimly lit forest. The path heads northsouth here. One</td></tr><tr><td/><td>particularly large tree with some low branches stands at the edge of the path. Inv: You are emptyhanded.</td></tr><tr><td/><td>Feedback: Forest Path</td></tr><tr><td colspan="2">Template probs: south: 0.386, open OBJ: 0.358, east: 0.123, west: 0.06, north: 0.023, go around OBJ: 0.014,</td></tr><tr><td/><td>blow out OBJ: 0.01, northwest: 0.009, throw OBJ at OBJ: 0.008</td></tr><tr><td colspan="2">Object probs: window: 0.701, small: 0.299</td></tr><tr><td colspan="2">Interactive objects: tree, path, branches, forest, large, all</td></tr><tr><td colspan="2">Action: south</td></tr><tr><td colspan="2">Score: 5</td></tr><tr><td>---</td><td/></tr><tr><td colspan="2">Obs: Desc: Template probs: west: 0.502, open OBJ: 0.177, west: 0.147, north: 0.094, south: 0.035, throw OBJ at OBJ:</td></tr><tr><td/><td>0.012, go around OBJ: 0.012, northwest: 0.01, blow out OBJ: 0.005</td></tr><tr><td colspan="2">Object probs: window: 0.724, small: 0.243, trap: 0.014, kitche: 0.009, rug: 0.003</td></tr><tr><td colspan="2">Interactive objects: path, windows, narrow, white, house, all</td></tr><tr><td colspan="2">Action: west</td></tr><tr><td colspan="2">Score: 5 Template probs: open OBJ: 0.339, east: 0.271, south: 0.215, west: 0.094, north: 0.031, go around OBJ: 0.013, ---blow out OBJ: 0.011, throw OBJ at OBJ: 0.01, northwest: 0.009 Obs: Desc: West of House You are standing in an open field west of a white house, with a boarded front door. Object probs: window: 0.7, small: 0.299 There is a small mailbox here. Inv: You are emptyhanded. Feedback: Interactive objects: boarded, small, front, door, white, mailbox, house, all Template probs: open OBJ: 0.536, south: 0.241, east: 0.121, west: 0.053, north: 0.015, go around OBJ: 0.011, Action: west throw OBJ at OBJ: 0.007, blow out OBJ: 0.006, northwest: 0.005 Score: 0 Object probs: window: 0.7, small: 0.3 ---Interactive objects: boarded, small, front, door, white, mailbox, house, all Obs: Desc: Forest This is a forest, with trees in all directions. To the east, there appears to be sunlight. Action: open white Inv: You are emptyhanded. Feedback: Forest This is a forest, with trees in all directions. To the east, Score: 5 there appears to be sunlight. ---Template probs: open OBJ: 0.49, south: 0.304, east: 0.116, west: 0.04, north: 0.016, go around OBJ: 0.011, throw OBJ at OBJ: 0.006, northwest: 0.006, blow out OBJ: 0.006 Object probs: window: 0.7, small: 0.3 Obs: Desc: Template probs: open OBJ: 0.339, east: 0.271, south: 0.215, west: 0.094, north: 0.031, go around OBJ: 0.013, Interactive objects: forest, all, trees blow out OBJ: 0.011, throw OBJ at OBJ: 0.01, northwest: 0.009 Action: east Object probs: window: 0.7, small: 0.299 Score: 0 Interactive objects: boarded, small, front, door, white, mailbox, house, all ---Action: west</td></tr><tr><td colspan="2">Score: 5</td></tr><tr><td>---</td><td/></tr></table>

Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. Feedback: Forest This is a dimly lit forest, with large trees all around. Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. Feedback: The rank undergrowth prevents eastward movement. Template probs: south: 0.434, open OBJ: 0.339, east: 0.076, west: 0.065, north: 0.024, go around OBJ: 0.02, northwest: 0.012, blow out OBJ: 0.011, throw OBJ at OBJ: 0.009 Object probs: window: 0.701, small: 0.299 Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. Feedback: Wheeeeeeeeee!!!!! You hear in the distance the chirping of a song bird. Template probs: south: 0.438, open OBJ: 0.292, east: 0.098, west: 0.075, north: 0.03, go around OBJ: 0.019, Clearing You are in a small clearing in a well marked forest path that extends to the east and west . Inv: You are emptyhanded. Feedback: You dont have the way. Template probs: open OBJ: 0.377, west: 0.341, east: 0.149, south: 0.057, north: 0.022, throw OBJ at OBJ: 0.018, blow out OBJ: 0.011, go around OBJ: 0.011, northwest: 0.008 Object probs: window: 0.7, small: 0.299 Interactive objects: forest, path, all

Table content: <table><tr><td>Template probs: west: 0.444, take OBJ: 0.204, open OBJ: 0.147, blow out OBJ: 0.118, turn on OBJ: 0.027, east: 0.026, down: 0.009, go around OBJ: 0.005, push OBJ: 0.004 Object probs: window: 0.693, small: 0.307 Interactive objects: path, walls, frigid, river, rainbow, wall, all Action: west Score: 5 ---Obs: Desc: Template probs: south: 0.494, open OBJ: 0.241, east: 0.105, west: 0.053, north: 0.038, go around OBJ: 0.018, northwest: 0.015, blow out OBJ: 0.014, throw OBJ at OBJ: 0.007, down: 0.005 Object probs: window: 0.699, small: 0.301 Interactive objects: forest, large, all, trees Action: south Score: 5 ---Obs: Desc: Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. Feedback: Stormtossed trees block your way. Template probs: east: 0.722, north: 0.067, west: 0.061, open OBJ: 0.061, south: 0.048, blow out OBJ: 0.011, northwest: 0.01, go around OBJ: 0.007, throw OBJ at OBJ: 0.005 Object probs: window: 0.7, small: 0.3 Interactive objects: storm, forest, trees, large, all Action: east Score: 5 ---Action: jump Score: 5 ---Obs: Desc: northwest: 0.013, blow out OBJ: 0.012, throw OBJ at OBJ: 0.01 Object probs: window: 0.7, small: 0.299 Interactive objects: forest, large, all, trees Action: south Score: 5 ---Obs: Desc: Forest This is a dimly lit forest, with large trees all around. Inv: You are emptyhanded. Feedback: Stormtossed trees block your way. Template probs: east: 0.694, west: 0.081, north: 0.07, open OBJ: 0.067, south: 0.043, northwest: 0.012, blow out OBJ: 0.011, go around OBJ: 0.007, throw OBJ at OBJ: 0.006 Object probs: window: 0.7, small: 0.3 Interactive objects: storm, forest, trees, large, all Action: north Score: 5 ---Obs: Desc: Clearing You are in a small clearing in a well marked forest path that extends to the east and west . Inv: You are emptyhanded. Feedback: Clearing Template probs: west: 0.437, east: 0.311, open OBJ: 0.171, north: 0.026, throw OBJ at OBJ: 0.015, south: 0.013, blow out OBJ: 0.011, go around OBJ: 0.006, northwest: 0.006 Object probs: window: 0.699, small: 0.301 Interactive objects: forest, path, all Action: throw path at forest Score: 5 ---Obs: Desc: Interactive objects: forest, large, all, trees Obs: Desc:</td></tr></table>

Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The door is nailed shut. Template probs: open OBJ: 0.679, push OBJ: 0.073, down: 0.057, take OBJ: 0.046, put down OBJ: 0.022, turn on OBJ: 0.019, west: 0.017, close OBJ: 0.015, throw OBJ at OBJ: 0.015, put OBJ in OBJ: 0.015 Object probs: window: 0.672, small: 0.328 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The trap door is closed. Template probs: open OBJ: 0.63, down: 0.087, take OBJ: 0.06, put down OBJ: 0.045, push OBJ: 0.04, west: 0.027, turn on OBJ: 0.02, close OBJ: 0.018, throw OBJ at OBJ: 0.018, put OBJ in OBJ: 0.015 Object probs: window: 0.657, small: 0.342 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, trap, Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: You must tell me how to do that to a sword. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: You cant use multiple direct objects with "open". Template probs: open OBJ: 0.529, down: 0.086, put down OBJ: 0.065, take OBJ: 0.063, push OBJ: 0.059, west: 0.044, throw OBJ at OBJ: 0.028, turn on OBJ: 0.028, put OBJ in OBJ: 0.026, close OBJ: 0.021 Object probs: window: 0.661, small: 0.339 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The trap door is closed. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: You dont have the wooden door. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The door cannot be opened. Template probs: open OBJ: 0.648, push OBJ: 0.089, down: 0.053, take OBJ: 0.042, west: 0.025, turn on OBJ: 0.025, put down OBJ: 0.024, throw OBJ at OBJ: 0.021, put OBJ in OBJ: 0.02, close OBJ: 0.013 Object probs: window: 0.665, small: 0.335 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The door cannot be opened. Template probs: open OBJ: 0.637, push OBJ: 0.081, down: 0.058, take OBJ: 0.05, put down OBJ: 0.024, west: 0.024, turn on OBJ: 0.024, close OBJ: 0.019, throw OBJ at OBJ: 0.017, put OBJ in OBJ: 0.016 Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: Pushing the sword doesnt seem to work. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The door cannot be opened. Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a rug lying beside an open trap door. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The door reluctantly opens to reveal a rickety staircase descending into darkness. Template probs: down: 0.876, open OBJ: 0.046, take OBJ: 0.018, east: 0.013, close OBJ: 0.009, put down OBJ: 0.007, north: 0.006 Object probs: window: 0.604, small: 0.387, kitche: 0.006, trap: 0.003 Interactive objects: elvish, strange, trophy, brass, rug, staircase, case, lettering, antiquity, sword, gothic , west, door, trap, wooden, lantern, light, all Action: down Score: 15 ---Obs: Desc: It is pitch black. You are likely to be eaten by a grue. Inv: You are carrying A brass lantern Feedback: You have moved into a dark place. It is pitch black. You are likely to be eaten by a grue. Template probs: take OBJ: 0.141, turn on OBJ: 0.14, open OBJ: 0.122, down: 0.117, close OBJ: 0.073, put down OBJ: 0.069, west: 0.065, push OBJ: 0.056, throw OBJ at OBJ: 0.054, south: 0.02 Object probs: lanter: 0.076, letter: 0.071, window: 0.061, door: 0.059, small: 0.052, gothic: 0.049, sword: 0.049, rug: 0.037, trophy: 0.035, west: 0.031 Interactive objects: brass, dark, lantern, black, all, grue Action: down Score: 40 ---Obs: Desc: It is pitch black. You are likely to be eaten by a grue. Inv: You are carrying A brass lantern Feedback: The chasm probably leads straight to the infernal regions. Template probs: turn on OBJ: 0.167, take OBJ: 0.132, open OBJ: 0.125, down: 0.124, close OBJ: 0.076, push OBJ: 0.067, put down OBJ: 0.066, throw OBJ at OBJ: 0.056, west: 0.05, south: 0.024 Object probs: lanter: 0.077, letter: 0.071, window: 0.06, door: 0.059, small: 0.051, gothic: 0.05, sword: 0.049, rug: 0.037, trophy: 0.035, west: 0.031 Interactive objects: brass, chasm, lantern, black, all, grue Action: turn on lanter Score: 40 ---Obs: Desc: Cellar You are in a dark and damp cellar with a narrow passageway leading north, and a crawlway to the south. On the west is the bottom of a steep metal ramp which is unclimbable. There is a suspiciouslooking individual, holding a large bag, leaning against one wall. He is armed with a deadly stiletto. Inv: You are carrying A brass lantern (providing light) Feedback: You try to ascend the ramp, but it is impossible, and you slide back down. Template probs: down: 0.246, open OBJ: 0.209, take OBJ: 0.122, close OBJ: 0.1, push OBJ: 0.082, turn on OBJ:

Table content: <table><tr><td>025, west: 0.023, close OBJ: 0.021, throw OBJ at OBJ: 0.019, put OBJ in OBJ: 0.016 Object probs: window: 0.674, small: 0.326 Interactive objects: dusty, strange, trophy, cover, case, antiquity, lantern, lettering, sword, gothic, wooden , elvish, brass, west, rug, trap, door, light, all Action: west Score: 15 ---Obs: Desc: trap, wooden, lantern, light, all Action: down Score: 15 ---Obs: Desc: door, wooden, lantern, light, all Action: open sword Score: 15 ---Obs: Desc: Template probs: open OBJ: 0.625, down: 0.075, take OBJ: 0.053, push OBJ: 0.05, put down OBJ: 0.049, west: 0.028, turn on OBJ: 0.021, throw OBJ at OBJ: 0.02, close OBJ: 0.019, put OBJ in OBJ: 0.018 Object probs: window: 0.659, small: 0.34 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: open case Score: 15 ---Obs: Desc: Inv: You are carrying A brass lantern (providing light) Feedback: Opened. Template probs: open OBJ: 0.61, down: 0.081, take OBJ: 0.056, push OBJ: 0.053, put down OBJ: 0.049, west: 0.029, turn on OBJ: 0.023, throw OBJ at OBJ: 0.02, put OBJ in OBJ: 0.019, close OBJ: 0.019 Object probs: window: 0.659, small: 0.341 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: open door Score: 15 ---Obs: Desc: Inv: You are carrying A brass lantern (providing light) Feedback: Which door do you mean, the wooden door or the trap door? Template probs: open OBJ: 0.552, down: 0.085, take OBJ: 0.062, put down OBJ: 0.06, push OBJ: 0.055, west: 0.04, turn on OBJ: 0.026, throw OBJ at OBJ: 0.026, put OBJ in OBJ: 0.024, close OBJ: 0.021 Object probs: window: 0.66, small: 0.33 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, trap, door, wooden, lantern, light, all Action: open all Score: 15 ---Score: 15 ---Obs: Desc: Template probs: open OBJ: 0.569, down: 0.089, take OBJ: 0.063, put down OBJ: 0.059, push OBJ: 0.048, west: 0.036, turn on OBJ: 0.024, throw OBJ at OBJ: 0.024, put OBJ in OBJ: 0.021, close OBJ: 0.021 Object probs: window: 0.658, small: 0.341 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, trap, door, wooden, lantern, light, all Action: shake gothic Score: 15 ---Obs: Desc: Template probs: open OBJ: 0.62, push OBJ: 0.085, take OBJ: 0.055, down: 0.053, west: 0.031, put down OBJ: 0.026, turn on OBJ: 0.025, throw OBJ at OBJ: 0.02, put OBJ in OBJ: 0.019, close OBJ: 0.014 Object probs: window: 0.668, small: 0.332 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: open west Score: 15 ---Obs: Desc: trap, wooden, lantern, light, all Action: open wooden Score: 15 ---Obs: Desc: Object probs: window: 0.671, small: 0.329 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: push sword Score: 15 ---Obs: Desc: Template probs: open OBJ: 0.591, push OBJ: 0.085, down: 0.073, take OBJ: 0.061, turn on OBJ: 0.025, put down OBJ: 0.024, west: 0.024, close OBJ: 0.02, throw OBJ at OBJ: 0.019, put OBJ in OBJ: 0.017 Object probs: window: 0.674, small: 0.326 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: open strang Score: 15 ---Obs: Desc: Template probs: open OBJ: 0.614, push OBJ: 0.085, down: 0.065, take OBJ: 0.059, west: 0.024, turn on OBJ: 0.024, put down OBJ: 0.021, close OBJ: 0.017, throw OBJ at OBJ: 0.017, put OBJ in OBJ: 0.016 Object probs: window: 0.676, small: 0.323 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, door, trap, wooden, lantern, light, all Action: down Score: 15 ---Obs: Desc: Living Room You are in the living room. There is a doorway to the east, a wooden door with strange gothic lettering to the west, which appears to be nailed shut, a trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword of great antiquity. Inv: You are carrying A brass lantern (providing light) Feedback: The trap door is closed. Template probs: open OBJ: 0.665, down: 0.068, push OBJ: 0.052, take OBJ: 0.044, put down OBJ: 0.036, west: 0.026, turn on OBJ: 0.02, throw OBJ at OBJ: 0.018, put OBJ in OBJ: 0.017, close OBJ: 0.015 Object probs: window: 0.661, small: 0.339 Interactive objects: elvish, strange, trophy, brass, case, lettering, antiquity, sword, gothic, west, trap, Obs: Desc: Action: down door, wooden, lantern, light, all</td></tr><tr><td>Action: open trap</td></tr><tr><td>Score: 15</td></tr><tr><td>---</td></tr><tr><td>Obs: Desc:</td></tr></table>

Peer review (iclr2020):
This paper proposes a knowledge graph advantage actor critic (KG-A2C) model to allow an agent to do reinforcement learning in the interactive fiction game. Under the general framework of A2C, the core contribution of the paper is to apply a graph attention network on the knowledge graph to help learn better representation of the game state and reduce the action space. Experiments on Zork1 game environment are done to verify the effectiveness of the proposed method. Overall, this paper presents a novel contribution to reinforcement learning with augmented memory/world-state. However, I do have a few concerns regarding the baselines and other details. Given these clarifications and or comparisons in an author response, I would be willing to increase the score. Pros: 1, I like the idea of constructing the knowledge graph as the agent roll out. I think it is a better way to construct a structural representation of the world rather than assuming the agent gonna learn everything via single hidden state vector. It also permits more explainable policy in the future. Authors do make good progress along this line. 2, The paper is well written and the design of the proposed new model seems technically reasonable. Cons & Questions: 1, The main concern I had is regarding to the baseline. I think it is more convincing to have a baseline which leverages the same entity extraction and template-action space. In particular, it should have the same model architecture except that it uses maybe a LSTM to decode the action rather than a GAT applied on knowledge graph. Note that the baseline I am referring to is different from the LSTM-A2C baseline reported in the paper as: (1) with entity extraction, although you may not get a graph mask, but you can still have a object-mask which also reduces the action space; (2) it is not clear to me that LSTM-A2C uses the same template-action mechanism as the KG-A2C, e.g., the valid action construction procedure described in section 4.1. Without such a baseline, it is hard to fully judge how helpful the knowledge graph is. 2, How do you test the generalization of the proposed models? In particular, do you use different maps during training and testing? If the model is merely trained on one map as shown in figure 5, it may just memorizes it in the knowledge graph and overfit to this map. 3, The details of the interaction fiction problem setup are sparse. It would be very helpful to explain what exactly the observations are in the example of Figure 2. For example, what are the game description, game feedback are in this case? 4, In the caption of figure 1, “Solid lines represent gradient flow” is misleading. If I understood correctly, solid lines refer to the computation flow which has gradient back-propagated in the backward pass. 5, Could you explain why KG-A2C converge slower than DRRN in figure 3? 6, Do you think having a fully differentiable mechanism of building knowledge graph would help or not? Why? ====================================================================================================== Most of my concerns are addressed by the authors* response. I increased my score.