Graph Constrained Reinforcement Learning for Natural Language Action Spaces

• Interactive Fiction games are text-based simulations in which agents use natural-language descriptions and commands to interact with the world and pursue goals.Source: §1 · p. 1
• IF agents must reason from incomplete textual descriptions because they cannot access the true underlying world state, while also relying on commonsense knowledge.Prior work used knowledge graphs for partial observability and commonsense reasoning, but not natural-language generation.Source: §1 · p. 1
• In Zork1, generating actions of up to five words from a 697-word vocabulary creates a combinatorially large action space.Source: §1 · p. 1
• The agent combines a knowledge-graph-based state space with a template-based action space to generate meaningful natural-language commands.The template-action space is six orders of magnitude smaller than the word-based space, yet six orders larger than action spaces used by previous text-based agents.Source: §1 · p. 2
• KG-A2C achieves state-of-the-art performance on a large proportion of IF games despite the exponential increase in action-space size.Source: §1 · p. 2

• Text-game agents have used verb-noun actions, state-action Q-value estimates, affordance-based verbs, and action elimination to reduce or select actions.LSTM-DQN (Narasimhan et al., 2015), DRRN (He et al., 2016; Zelinka, 2018), Fulda et al. (2017), and Zahavy et al. (2018) represent these approaches.Source: §2 · p. 2
• TextWorld, QAit, Light, and Jericho provide frameworks or datasets for generated games, interactive question answering, dialog, and human-made game benchmarking.The authors use Jericho and its tools to develop their agents.Source: §2 · p. 2
• Knowledge graphs have supported conversational generation, story-ending prediction, and quest-content generation, as well as text-game state representations.Source: §2 · p. 2
• Prior knowledge-graph text-game agents required a discrete action set in advance and therefore did not fully address the combinatorial action space.Ammanabrolu & Riedl (2019a, 2019b) are cited as examples.Source: §2 · p. 2

• IF games are modeled as partially observable Markov decision processes, and the approach uses a knowledge-graph state space with a template-based action space.Source: §3 · p. 3
• The knowledge graph stores subject-relation-object triples extracted from observations using OpenIE, supplemented by rules for parsing semi-structured game information.Source: §3 · p. 3
• Updated after each action, the graph maps the explored world and retains information such as object affordances, character properties, and inventory.Graph nodes are related to the agent through a “you” node.Source: §3 · p. 3
• Interactive objects link directly to the agent and current room, while other triples are extracted with OpenIE to support graph building across diverse game structures.The authors relax rules used in prior work to accommodate varied genres in Jericho.Source: §3 · p. 3
• Parser templates contain verb phrases, optionally with prepositional phrases, and actions are formed by filling their blanks with words from the game vocabulary.Templates and vocabulary are programmatically accessible through Jericho.Source: §3 · p. 3

4 KNOWLEDGE GRAPH ADVANTAGE ACTOR CRITIC

• KG-A2C combines a knowledge-graph state space and template action space in an on-policy agent that gathers experience from parallel environments.Its architecture encodes a state representation and then decodes an action.Source: §4 · p. 3
• The input representation combines separately encoded observation components, a knowledge-graph embedding, and a binary encoding of the total score.The observation includes the room description, game feedback, inventory, and previous action.Source: §4 · pp. 3–5
• At each step, the agent updates its knowledge graph from the observation and embeds it into a single vector using graph attention.The state embedding combines the graph embedding, encoded observation, and score encoding.Source: §4 · pp. 4–5
• The action decoder predicts a template first, then selects its objects sequentially, conditioning each choice on the encoded state and previously decoded action parts.A graph mask restricts object predictions to entities found both in the knowledge graph and vocabulary; objects may be randomly added to the mask to handle cases where an unseen object must be referenced.Source: §4 · p. 5

4.1 TRAINING

• The A2C updates use an advantage comparing an action’s value with the critic’s state value, and update the actor’s template and object policies.Each decoding step is conditioned on previously decoded portions of the action.Source: §4.1 · p. 6
• Training identifies actions that can change the world using game feedback and Jericho’s valid-action detection algorithm.Valid-action sets support cross-entropy losses for template and object decoding; an entropy loss over valid actions is intended to prevent premature convergence on a trajectory.Source: §4.1 · p. 6

5 EXPERIMENTAL RESULTS

• Evaluation covers Jericho-supported games and uses Jericho valid-action identification and Load/Save access to obtain observations without changing game state.Each agent is trained and evaluated individually on each game; A2C agents use 32 parallel environments, while TDQN uses one.Source: §5 · p. 7
• TDQN is a template-based extension of LSTM-DQN with separate Q-value heads for templates and vocabulary words that fill template blanks.TDQN and KG-A2C use the same handicaps, allowing a fair comparison.Source: §5 · p. 7
• KG-A2C matches or outperforms TDQN on 23 of the 28 tested games.The suite tests generalization across different genres, game structures, reward functions, and state-action spaces.Source: §5 · p. 7

6 ABLATION STUDY

• The study ablates the knowledge graph, template action space, and valid-action loss; A2C removes graph components, while no-GAT and no-mask variants remove graph attention and graph masking, respectively.The no-GAT variant retains graph masking; the no-mask variant retains graph attention.Source: §6 · p. 7
• On Zork1, all ablations reach approximately 34 points, while access to either graph attention or the graph mask yields slightly faster convergence than pure A2C.The figure reports ablation results averaged across five independent runs.Source: §6 · p. 7, Figure 3 · p. 8
• KG-A2C-full outperforms KG-A2C-no-mask on 10 games and loses to it on 6 in the broader comparison.The authors conclude that the graph mask and knowledge graph are broadly useful components.Source: §6 · p. 8
• Without valid-action access, KG-A2C-unsupervised scores nothing after the same number of training steps; the authors infer that valid-action auxiliary loss remains important.The variant disables the template and object valid-action losses and bases its entropy loss on the full action set.Source: §6 · p. 8
• KG-A2C-seq removes templates, decodes up to four words, and reaches only 8 points despite teacher forcing and substantially longer training.During training, it executes a randomly selected valid action with probability 0.5.Source: §6 · p. 8

7 CONCLUSION

• KG-A2C combines a knowledge-graph state space with a template-based action space to constrain possible commands to sensible actions.The graph helps represent surroundings, accumulate information, and disambiguate similar textual observations; templates give structure for language generation.Source: §7 · p. 8
• Across 28 human-made IF games, KG-A2C shows wide improvement over TDQN, the current state-of-the-art template-based agent.Source: §7 · p. 8
• On Zork1, an ablation study replicates state-of-the-art performance with an action space six orders of magnitude larger than previous agents.Source: §7 · p. 8

A ABLATION RESULTS

• Table 2 is identified as an ablation table.Source: Table 2 · p. 11

B.1 KNOWLEDGE GRAPH UPDATE RULES

• Candidate objects are drawn from observation nouns and adjectives, then filtered by whether they can be examined.Only interactive objects absent from the inventory are linked to the current room.Source: §B.1 · p. 11
• Inventory items link to the “you” node rather than the current room.Source: §B.1 · p. 11
• Navigation actions infer relative room positions, as when going down from the kitchen yields ⟨kitchen, down, cellar⟩.Source: §B.1 · p. 11

B.2 TEMPLATE PREPROCESSING

• A human-playthrough dataset supplies token frequencies for choosing the most likely verb and preposition aliases.ClubFloyd5 contains 425 unique play sessions and 273,469 state-action pairs.Source: §B.2 · p. 11
• The selected aliases convert [carry/hold/take] to “take” and [drop/throw/discard/put] [at/against/on/onto] to “put on.”Source: §B.2 · p. 11
• The authors choose human-likely forms to support agent explainability.Source: §B.2 · p. 11

C EXPERIMENT DETAILS

• Episodes end after 100 valid actions or game over or victory; invalid actions do not count toward the step limit.Source: C EXPERIMENT DETAILS · p. 12
• A2C agents train with data from 32 parallel environments, while TDQN uses one environment.Source: C EXPERIMENT DETAILS · p. 12
• Each agent is trained and evaluated on each game separately, with hyperparameters tuned on Zork1 and held fixed across the other games.Source: C EXPERIMENT DETAILS · p. 12
• Final reported scores average five runs per algorithm; Figure 4 presents KGA2C-full learning curves with standard-deviation shading.Source: C EXPERIMENT DETAILS · p. 12, Figure 4 · p. 12
• Figure 5 maps Zork1, annotates some initial rewards, and marks the overworld–dungeon connection with a blue arrow.Source: Figure 5 · p. 13

D ZORK1

• Zork1 is a dungeon-crawler with a vast labyrinth, puzzles, enemies, sparse rewards for treasures or correct paths, and random enemy movements.The game was identified as one of the suite’s most difficult and has been the subject of prior work.Source: D ZORK1 · p. 13
• Among 10 IF-familiar first-time players without walkthroughs, five reached around 40 before dying to the troll (mostly weaponless), three died to traps at 5–15, and two passed it with around 70.The troll was the first beatable NPC; the five who died there had mostly neglected to collect a weapon beforehand.Source: D ZORK1 · p. 13
• Turning on the brass lantern succeeds, while attempts to take the trophy or push the case fail.The lantern is reported on; the trophy case is securely fastened, and pushing it has no effect.Source: D ZORK1 · p. 17
• Pushing the rug succeeds, moving it aside and revealing a closed trap door.The feedback reports that the rug was moved to one side, exposing the trap door’s dusty cover.Source: D ZORK1 · p. 18
• Opening the case succeeds, but opening the wooden door fails and the generic “open door” command is ambiguous.The game reports “Opened” for the case, says the wooden door cannot be opened, and asks which door is meant by “open door.”Source: D ZORK1 · pp. 18–19
• Opening the trap door reveals a staircase, and descending moves the agent into a pitch-black area where it risks being eaten by a grue.The opening and descent each score 15 in the trace.Source: D ZORK1 · pp. 19–20
• In the cellar, the agent’s attempted ascent fails, the thief attacks, and a southward command receives the feedback “You dont have the way.”The trace also shows the thief leaving after finding nothing of value and then remaining in the cellar encounter.Source: D ZORK1 · p. 20
• In the gallery, opening the painting fails, but taking it succeeds and adds a painting to the agent’s inventory.A later attempt to open the art receives the response “You must tell me how to do that to a painting.”Source: D ZORK1 · p. 21

D.1 PENTARI TRANSCRIPT

• In the Charlie Company sequence, the agent enters a Pentarian Transporter and selects the city action, then materializes indoors rather than at the expected outdoor destination.Source: §D.1 · pp. 21–22
• The agent breaks the Magical Seal, collects a dagger and dirty scroll, and later obtains an emerald during castle exploration.The transcript reports score increases after breaking the seal, taking the dagger and scroll, and taking a jewel.Source: §D.1 · pp. 22–23
• After the Dark Elf steals the emerald, the agent joins the fight and kills Vamvevmew, but subsequent commands include unsuccessful attempts to manipulate unseen objects.The transcript also shows the platinum box opening to reveal the Empirical Emerald.Source: §D.1 · p. 23
• The later castle sequence contains repeated zero-reward commands involving dagger, floor, and box, with the game returning rejection messages before the episode ends.Source: §D.1 · pp. 23–24