Case-based reasoning for better generalization in textual reinforcement learning
Authors: Mattia Atzeni
Shehzaad Zuzar Dhuliawala
Keerthiram Murugesan
Mrinmaya Sachan
Venue: ICLR 2022 Poster (2022)

Abstract: Text-based games (TBG) have emerged as promising environments for driving research in grounded language understanding and studying problems like generalization and sample efficiency. Several deep reinforcement learning (RL) methods with varying architectures and learning schemes have been proposed for TBGs. However, these methods fail to generalize efficiently, especially under distributional shifts. In a departure from deep RL approaches, in this paper, we propose a general method inspired by case-based reasoning to train agents and generalize out of the training distribution. The case-based reasoner collects instances of positive experiences from the agent's interaction with the world and later reuses the collected experiences to act efficiently. The method can be used in conjunction with any existing on-policy neural agent introduced in the literature for TBGs. Our experiments show that the proposed approach consistently improves existing methods, obtains good out-of-distribution generalization and achieves new state-of-the-art results on widely used environments.

design general CBR Published as a conference paper at ICLR 2022
CASE-BASED REASONING FOR BETTER GENERALIZATION IN TEXTUAL REINFORCEMENT LEARNING
Mattia Atzeni
Shehzaad Dhuliawala
IBM Research, EPFL atz@zurich. ibm. com
ETH Zürich beehzaaad.hulliawaleee..
Keerthiram Murugesan
Mrinmaya Sachan
IBM Research
ETH Zürich mri mrinmaya wwchan@inf.
keerthi www.rraam.muuugaanaaa.. ibm. com
ABSTRACT
Text-based games (TBG) have emerged as promising environments for driving research in grounded language understanding and studying problems like generalization and sample efficiency. Several deep reinforcement learning (RL) methods with varying architectures and learning schemes have been proposed for TBGs. However, these methods fail to generalize efficiently, especially under distributional shifts. In a departure from deep RL approaches, in this paper, we propose a general method inspired by case-based reasoning to train agents and generalize out of the training distribution. The case-based reasoner collects instances of positive experiences from the agent's interaction with the world in the past and later reuses the collected experiences to act efficiently. The method can be applied in conjunction with any existing on-policy neural agent in the literature for TBGs. Our experiments show that the proposed approach consistently improves existing methods, obtains good out-of-distribution generalization, and achieves new state-of-the-an results on widely used environments.
INTRODUCTION
Text-based games (TBGs) have emerged as key benchmarks for studying how reinforcement learning (RL) agents can tackle the challenges of grounded language understanding, partial observability. large action spaces, and -uittf-disttibution generalization (Hausknecht et al., 2020; Ammanabrolu & Riedl, 2019). While have indeed made some progress on these fronts in recent years (Ammanabrolu & Hausknecht, 2020; Adhikari et al., 2020; Murugesan et al., 2021b;a), these agents still very inefficient and suffer from insufficient generalization As an example, statc-of-the-art agents require 5 to 10 times more steps than human to accomplish even simple houschold tasks (Murugesan al., 2021b). As the agents are purely neural architectures requiring significant training experience and computation, they fail to efficiently adapt to new environments and use their past experiences to reason in novel situations. This is in stark contrast to human learning which is much more robust, efficient and generalizable (Lake et al., 2017).
novel environments.
Motivated by this fundamental difference in learning, we propose new agents that rely on case-based reasoning (CBR) (Aamodt & Plaza, 1994) to efficiently act in the world. CBR draws its foundations cognitive science (Schank, 1983; Kolodner, 1983) and mimics the process of solving new tasks based solutions to previously encountered similar tasks. Concretely, framework that enables an agent to collect instances of past situations which led to a positive reward (known cases). During decision making, the agent retrieves the case most similar to the current situation and then applies it after appropriately mapping it to the current context.
The CBR agent stores past experiences, along with the actions it performed, in case memory. In order to efficiently use these stored experiences, the agent should be able to represent relevant contextual information from the state of the game in compact way, while retaining the property

---

Published as a conference paper at ICLR 2022
Observations Actions
Seeded Graph Attention
State Graph
> Take knife.
You take the knife from the ground.
Knife
Troll
Trail
Context ropresentatoo
Disemtizzaiion
Retrieve
2-4-1-4
You find yourself forest. nasty-locking blocks your way.
east
hasa
Player
Foreat pors of
Player
Forest
Memory
1-3-5-2
Put sword
2-4-1-6
Reuse Revise
Admisatble actions
Memory writing
reward
Symbolic action reuse Kill troil with knife
Drop knife
Momory
Retain
Kill troil with knife
Drop key
west
24-1--5 Kill ore with sword
1-3-5-
24-14
Put emerald case
Kiil trail with kniffe
Discreizzaion
2-4-144
Execule or revise action
Neural agent
Figure 1: Overview of the approach and architecture of the CBR agent. A memory stores actions that have been used in previous interactions. The context of the game is learned from the state knowledge graph using a graph attention mechanism. Actions are retrieved from the memory based on this context representation and mapped to the current state. If no valid action is obtained using CBR, the algorithm falls back to a neural agent.
that contexts that require similar actions receive similar representations. We represent the state of the game as a knowledge graph (Ammanabrolu & Hausknecht, 2020) and we address these challenges by utilizing (a) a seeded message propagation that focuses only on a subset of relevant nodes and (b) vector quantization (Ballard, 2000) to efficiently map similar contexts to similar discrete representations. Vector quantization allows the model to significantly compress the context representations while retaining their semantics; thereby, allowing for scalable implementation of CBR in RL settings. An illustration of the framework is shown in Figure 1.
Our experiments show that CBR can be used consistently boost the performance of various policy RL agents proposed in the literature for TBGs. We obtain a new state-of-the-art on the TextWorld Commonsense (Murugesan et al., 2021b) dataset and achieve better or comparable scores on 24 of the 33 games in the Jericho suite (Hausknecht et al., 2020) compared to previous work. We also show that CBR agents are resilient domain shifts and suffer only marginal drops in performance (6%) on -uitt--distiibution settings when compared to their counterparts (35 (35%).
2 PRELIMINARIES
Text-based games. Text-based games (TBGs) provide challenging environment where agent can observe the current state of the game and act in the world using only the modality of text. The state of the game is hidden, so TBGs can be modeled Process (POMDP) (S, O, T, & r), where S is the set of states of the environment of the game, A the natural language action space, O is the set of observations or sequences of words describing the current state, T are the conditional transition probabilities from one state to another, & are the conditional observation probabilities, r x A + the reward function, which maps a state and action to scalar reward that the agent receives.
Partially Observable Markov Decision
Case-based reasoning. Case-based reasoning (CBR) is the process of solving new problems based on the solution of previously seen similar problems. Generally, CBR assumes access to a memory that stores past problems (known as cases) and their solutions. When a new problem is encountered, CBR will (i) retrieve similar problem and its solution from memory; (ii) reuse the solution by mapping it to the current problem; (iii) revise the solution by testing and checking whether it is viable way to address the new problem; and (iv) retain the solution in memory if the adaptation to the new problem successful.
CASE-BASED REASONING IN REINFORCEMENT LEARNING
This section introduces our framework inspired by CBR for improving generalization in TBGs. Even though we situate work in TBGs, it serves as good starting point for applying CBR in more general RL settings. We consider an on on-policy RL agent that, at any given time step t, has access to memory Mr, that can be used retrieve previous experiences. The memory contains
2

---

Published as a conference paper at ICLR 2022
key-value pairs, where the keys context representation of game state and values actions that were taken by the agent w.r. to this context. As mentioned in Section 2, case- aase-based reasoning can be formalized a four-step process. We describe our proposed methodology for each step below. Algorithm provides a detailed formalization of our approach.
Retrieve. Given the state of the game 8 and the valid actions Ar, want to retrieve from the memory Mr previous experiences that might be useful in decision-making at the current state. To this end, for each admissible action at E Ai, we define context selector = context( at). The context selector is an action-specific representation of the state, namely the portion of the state that is relevant to the execution of an action. We will explain later how the context selector is defined in our implementation. For each context C,, we retrieve from the memory the context-action pair (eM M),, such that GM has maximum similarity with Ct. We denote as sim(cs (cz, eTM) E [] the relevance score given the retrieved action. Only actions at with relevance score above a retriever threshold т are retrieved from M, We denote as A the final set of action-relevance pairs returned by the retriever, as shown in Algorithm 1.
Algorithm 1: CBR in Text-based RL
Retrieve
Let C₁ {context(s(, ac) a Ar be a set of context selectors for state 8, at time step 1 AM +
for c E EC, do Let (cM, aaM) ) arg (aM sim(ce, cf
Let ô = sim(c,, cM
i > r then
A AM {(aM 8)}
end
end
Reuse
Build a set of action candidates:
A. (reuse(a (a," 81, 6) (at1 A:M)
Revise
if A, n A + 0 then Let a; 8" = arg max GEA, 5
Reuse. The goal of the reuse step to adapt the actions retrieved from the memory based on the current state. This is accomplished by reuse function, that is applied to each retrieved action to construct set A, of candidate actions that should be applicable to the current state, each paired with confidence level.
else
aj arg max n (atlst)
end
Let r r(s,, at) be the reward obtained at time step / by executing action oz
Retain
Let cj context((;, ai) be the context of action az
Revise. If any of the action candidates A, is valid action, then the one with the highest relevance 6 is executed, otherwise a neural agent is used to select the best action oz. We denote with r; = r(st, a7) the obtained reward. Note that
T (c),aī), (c (G-m+1: ((-m+))
if r. > 0 then
M4+ & Mr U (TT
end
be an existing agent for TBGs (Murugesan et al., 2021c;b; Ammanabrolu & Hausknecht, 2020).
Retain. Finally, the retain step stores successful experiences as new cases in the memory, so that they can be retrieved in the future. In principle, this can be accomplished by storing actions for which the agent obtained positive rewards. However, we found that storing previous actions as well can result in improved performance. Therefore, whenever ri > 0. a retain function is used to select which of the past executed actions and their contexts should be stored in the memory. In experiments, the retain function selects the k most recent actions, but other implementations are possible, as discussed Appendix D.
4 A CBR POLICY AGENT TO GENERALIZE IN TEXT-BASED GAMES
Designing agent that act efficiently in TBGs using the described approach poses several challenges. Above all, efficient memory use is crucial to making the approach practical and scalable. Since the context selectors used as keys for accessing values in the memory, their representation
3

---

Published as a conference paper at ICLR 2022
needs to be such that contexts where similar actions were taken receive similar representations. At the same time, as the state space is exponential, context representations need to be focused only on relevant portions of the state and they need to be compressed and compact.
4.1 REPRESENTING THE CONTEXT THROOGHI SEEDED GRAPII ATTENTION
State space as a knowledge graph. Following previous works (Ammanabrolu & Riedl, 2019; Ammanabrolu & Hausknecht, 2020; Murugesan al., 2021c), represent the state of the game as a dynamic knowledge graph G. = (V,, R2, &t), where a node E Ve represents an entity in the game, r R2 is relation type, and an edge I v' E & represents relation of type E Ra between entities v, o' E Vr. In TBGs, the space of valid actions A, can be modeled as template- based action space, where actions are instances of finite set of templates with given set of entities, denoted as Va, S V4. As an example, the action "kill ore with sword" can be seen as an instance of the template "kill v1 with 02", where and 02 are "orc" and "sword" respectively.
Seeded graph attention. The state graph G. and the entities Va, are provided as input to the agent for each action at E Ar, in order build an action-specific contextualized representation of the state. A pre-trained BERT model (Devlin et al., 2019) is used to get representation h E Rd for each node V. Inspired by Sun et al. (2018), we propose a seeded graph attention mechanism (GAT), so that the propagation of messages is weighted more for nodes close to the entities VaL Let Oen
denote the attention coefficients given by a graph attention network (Velickovic et al., 2018) at layer for nodes v, V/. Then, for each node V2, introduce coefficient 8( that scales with the amount of messages received by node u at layer 1:
if Vac
(4()
[V, 0
((++1) = (1 x)
A
Σ BEN.
Oren a())
otherwise
where Nr denotes the neighbors of v. considering the graph undirected. Note that, layer / 1, only the nodes in Va, receive messages, whereas for increasing values l, 3 will be non-zero for their (1 hhp neighbors as well. The representation of each v E V is then updated as:
e FFN())
h (1-1) + 1
( (wwnh- (t-1)
BEN
where FFN is 2-layer feed-forward network with ReLU non-linearity and W() Rdxd are learnable parameters. Finally, we compute a final continuous contextualized representation ca. of the state by summing the linear projections of the hidden representations of each Va, and passing the result through a further feed-forward network.
4.2 MEMORY ACCESS THROUGH CONTEXT QUANTIZATION
Given continuous representation Ca, of the context, we need efficient way to access the memory Mr to retrieve store actions based on such a context selector. Storing and retrieving based on the continuous representation Ca2 would be impractical for scalability reasons. Additionally, since the parameters of the agent change over the training time, the same context would result in several duplicated entries in the memory even with pre-trained agent over different episodes.
Discretization of the context. To address these problems, we propose to use vector quantization (Ballard, 2000) before reading or writing to memory. Following previous work (Chen et al., 2018: Sachan, 2020), we learn discretization function ó E2 ZR. that maps the continuous representation Ca, into a K-way D-dimensional code E z with |Z = K (we refer to ca as a KD code). With reference to Section 3, then we will use G = context( (s, ax) = o(c.,) ) as the context selector used to access the memory Mr. In order to implement the discretization function, we define a set of K key vectors K; i K, and we divide each vector D partitions k/ E Rd/DD j 1, J...., D. Similarly, we divide ca. in D partitions ca E Rd/D jj = 1...., Then, compute the j-th code 2 of c by nearest neighbor search, as σ arg min, ||c/ k We use the straight- -triggh-throuuh estimator (Bengio et al., 2013) to address the non differentialbility of the argmin operator.
4

---

Published as a conference paper at ICLR 2022
Memory access. The KD codes introduced above used to provide memory--fftcient representation of the keys in the memory. Then, given the KD code representing the current context selector Ct. query the memory by computing similarity measure sim(c,, c(M) between & and each eM' in Mr, The similarity function defined as the fraction codes shared by c and o The context-action pair with the highest similarity is returned result of the memory access, together with a relevance score representing the value of the similarity measure.
4.3 SYMBOLIC ACTION REUSE AND REVISE POLICY
We simple purely symbolic reuse function adapt the actions retrieved from the memory to the current state. Let Ct be the context selector computed based on state and the entities Va, as explained in Sections 4.1 and 4.2. Denote with (cM a:M) the context-action pair retrieved from M, with confidence 5. Then, the reuse function reuse(a; 8t.6) constructs the action candidate â as the action with the same template as a,M applied the entities Va,. the reuse step cannot generate valid action, we revert to the neural policy agent и that outputs probability distribution over the current admissible actions Ar.
TRAINING
In Section 3, we have introduced an on-policy RL agent that relies on case-based reasoning to act the world efficiently. This agent can be trained in principle using any online RL method. This section discusses the training strategies and learning objectives used in implementation.
Objective. Two main portions the model need to be trained: (a) the retriever, namely the neural network that computes the context representation and accesses the memory through its discretization, and (b) the main neural agent æ which is used in the revise step. All agents и used in experiments are trained with an Advantage Actor-Critic (A2C) method. For optimizing the parameters of オ, we use the same learning objectives defined by Adolphs & Hofmann (2019), described in Appendix A. Whenever the executed action of is not chosen by the model but comes from the symbolic reuse step, then we optimize instead an additional objective for the retriever, namely the following contrastive loss (Hadsell al., 2006):
2/ -1 y1)(1 sim(c,, G M) + 2 max {0, p- 1 (om(ce,MM)3
14-1-
where e denotes the context selector of the action executed at time step t, cM is the corresponding key entry retrieved from Mr. μ the margin parameter of the contrastive loss, and y/: = 1 if 0, = O otherwise. This objective encourages the retriever to produce similar representations for two contexts where reusing an action yielded positive reward.
Pretraining. To make learning more stable and allow the agent to act more efficiently, we found beneficial pretrain the retriever. This minimizes large shifts in the context representations over the training time. We run baseline agent (Ammanabrolu & Hausknecht, 2020) to collect instances of the state graph and actions that yielded positive rewards. Then we train the retriever to encode to similar representations the contexts for which similar actions (i.e., actions with the same template) were used. This is achieved using the same contrastive loss defined above.
EXPERIMENTS
This section provides detailed evaluation of our approach. We assess quantitatively the performance of CBR combined with existing RL approaches and we demonstrate its capability to improve sample efficiency and generalize out of the training distribution. Next, provide qualitative insights and examples of the behavior of the model and we perform an ablation study understand the role played by the different components of the architecture.
6.1 EXPERIMENTAL. SETUP
Agents. We consider several agents obtained by plugging existing RL methods in the revise step. We first define two simple approaches: CBR-only, where we augment random policy with the
5

---

Published as a conference paper at ICLR 2022
Easy
Medium
Hard
#Steps
Norm. Score
#Steps
Norm, Score
#Steps
Norm. Score
Text
23.83 2.16
0.88 + 0.04
44.08 + 0.93
0.60 0.02
49.84 0.38
0.30 0.02
TPC
20.59 5.01
0.89 + 0.06
42.61 + 0.65
0.62 + 0.03
48.45 + 1.13
0.32 0.04
KG-A2C
22.10 2.91
0.86 + 0.06
41.61 + 0.37
0.62 + 0.03
48.00 + 0.61
0.32 0.00
BiKE
18.27 1.13
0.94 + 0.02
39.34 + 0.72
0.64 + 0.02
47.19 + 0.64
0.34 0.02
CBR-only
22.13 1.98
0.80 + 0.05
43.76 + 1.23
0.62 0.03
48.12 1.30
0.33 0.06
Text CBR
17.53 3.36 3.36
0.93 = 0.04
39.10 + 1.77
0.66 + 0.04
47.11 = 1.21
0.34 0.02
TPC CBR
16.81 3.12
0.94 + 0.03
37.05 + 1.61
0.67 + 0.03
47.25 + 1.56
0.37 0.03
KG-A2C CBR
15.91 2.52
0.95 + 0.03
36.13 + 1.65
0.66 + 0.05
46.11 + 1.13
0.40 0.04
BiKE CBR
15.72 1 1.15
0.95 + 0.04
35.24 + 1.22
0.67 + 0.03
45.21 + 0.87
0.42 1: 0.04
Table 1: Test-set performance for TWC in-distribution games
Easy
Medium
Hard
#Steps
Norm. Score
#Steps
Norm, Score
#Steps
Norm. Score
Text
29.90 2.92
0.78 + 0.02
45.90 + 0.22
0.55 + 0.01
50.00 + 0.00
0.20 0.02
TPC
27.74 4.46
0.78 + 0.07
44.89 + 1.52
0.58 + 0.01
50.00 + 0.00
0.19
KG-A2C
28.34 + 3.63
0.80 + 0.07
43.05 + 2.52
0.59 + 0.01
50.00 + 0.00
0.21 0.00
25.59 1.92
1: 0.01
41.01 1: 1.61
0.61 1:
1 0.00
CBR-only
23.43 2.09
0.80 1 0.04
44.03 + 1.75
0.63 0.04
48.71 + 1.15
0.31 0.03
Text CBR
20.91 1.72
0.89 + 0.02
40.32 + 1.27
0.66 + 0.04
47.89 + 0.87
0.32 0.06
TPC CBR
18.90 + 1.91
0.92 + 0.01
37.30 + 1.00
0.66 + 0.02
47.54 + 1.67
0.34 0.03
KG-A2C
18.21
0.02
37.02 1 1.22
0.68 1
1 1.12
0.02
BiKE + CBR
17.15 1.45
0.93 1: 0.03
35.45 1: 1.40
0.67 1 0.03
45.91 +: 1.32
0.40 11 0.03
Table 2: Test-set performance for TWC out-of-distribution games
CBR approach, and Text + CBR, which relies on the CBR method combined with simple GRU- based policy network that consumes as input the textual observation from the game. Next, select three recently proposed TBG approaches: Text+ Text=Commonsense (TPC) (Murugesan et al., 2021b), KG-A2C (Ammanabrolu & Hausknecht, 2020), and BiKE (Murugesan al., 2021c), ,), to create the TPC CBR, KG-A2C CBR and BiKE + CBR agents. We treat the original agents baselines.
Datasets. We empirically verify the efficacy of our approach on TextWorld Commonsense (TWC) (Murugesan al., 2021b) and Jericho (Hausknecht el., 2020). Jericho is well-known and challenging learning environment including 33 interactive fiction games. TWC is an environment which builds on Tex/World (Côté al., 2018) and provides a suite of games requiring commonsense knowledge. TWC allows agents to be tested on two settings: the in-distribution games, where the objects that the agent encounters in the test set are the same the objects the training set, and the out-of -of--iitribution games which have no entity in common with the training set. For each of these settings, TWC provides three difficulty levels: easy, medium, and hard.
Evaluation metrics. Following Murugesan et al. (2021b), we evaluate the agents on 7WC based on the number of steps (#Steps) required to achieve the goal (lower is better) and the normalized cumulative reward (Norm. Score) obtained by the agent (larger is better). On Jericho, we follow previous work (Hausknecht et al., 2020; Guo et al., 2020; Ammanabrolu & Hausknecht, 2020) and report the average score achieved over the last 100 training episodes.
6.2 RESULTS ON TEXTWORLD COMMONSENSE
Table I reports the results on 7WC for the in in-distribution set of games. Overall, we observe that CBR consistently improves the performance of all the baselines. The performance boost is large enough that even simple method as Text + CBR outperforms all considered baselines except BiKE.
Out-of-distribution generalization. CBR's ability to retrieve similar cases should allow our method better generalize to new and unseen problems. We test this hypothesis the outof-

---

Published as a conference paper at ICLR 2022
0.70
0.00
TPa
KG420
1P0+
040
Ki--00 EBR
E9C
0.35
0.5
0.99
Essadio
15
40
Figure 2: Performance TWC (showing mean and standard deviation averaged over 5 runs) for the three difficulty levels: easy (left), medium (middle), Hard (right) using normalized score and number of steps.
distribution games in TWC. The results of this experiment reported in Table 2. all existing approaches fail to generalize out of the training distribution and suffer a substantial drop in performance this setting. However, when coupled with CBR, the drop is minor (on average 6% with CBR vs 35% % without on the hard level). Interestingly, even the CBR-only agent achieves competitive results compared to the oo-pprforriig baselines.
We notice that
Sample efficiency. Another key benefit of our approach comes as better sample efficiency. With its ability to explicitly store prior solutions effectively, CBR allows existing algorithms to learn faster. Figure shows the learning curves for our best agents and the corresponding baselines. The plots report the performance of the agent over the training episodes, both in terms of the number of steps and the normalized score. Overall, we observe that the CBR agents obtain faster convergence to their counterparts all difficulty levels.
6.3 PERFORMANCE ON THE JERICHO GAMES
We evaluate our best performing variant from the experiments on TWC (BiKE + CBR) against existing approaches on the 33 games in the Jericho environment. We compare our approach against strong baselines, including TDQN (Hausknecht al., 2020), DRRN (He al., 2016), KG-A2C (Ammanabrolu & Hausknecht, 2020), MPRC-DQN (Guo et al., 2020), and RC-DQN (Guo et al., 2020). The same experimental setting and handicaps as the baselines are used, as we train for 100 000 steps and we assume access to valid actions. Table 3 summarizes the results of the Jericho games. We observe that our CBR agent achieves comparable or better performance than any baseline on 24 (73%) of the games, strictly outperforming all the other agents in 18 games.
6.4 QUALITATIVE ANALYSIS AND ABLATION STUDIES
Insights on the model. Figure 3 provides interacting with the zorkl game. In the example on top, the agent retrieves an experience that can be successfully reused and turned into a valid action at the current time step. The heat maps visualize the value of the context similarity function defined in Section 4 for the top entries in the memory. In the negative example at the bottom instead, the agent retrieves an action that is not useful and needs to fall back to the neural policy x. Figure 4 (top) shows the fraction of times that actions retrieved from the memory are reused successfully in the TWC games. We observe that, both for in-distribution and out-of-disttibuttio games, the trained agent relies CBR from 60% to approximately 70% of the times. Figure 4 (bottom) further shows the fraction of times that the neural agent would have been able to select rewarded action well, when the CBR reuses successful action. The plot shows that, for the out di-iittibbttion games, the neural agent would struggle to select good actions when the CBR is used.
examples showing the BiKE CBR agent
7

---

Published as a conference paper at ICLR 2022
Human
Human (Valkthrough-100)
Game
TDQN
DRRN
KG-A2C
MPRC-DON
RC-DQN
BIKE CBR
905
0
0
0
acorucourt
adventureland
100
42
20.6
24.2
21.7
27.3
afflicted
awaken
50
50
detective
350
197.8
207.9
317.7
291.3
dragon
25
25
-5.3
-3,5
0.04
4.84
8,3
inhumane
70
0.7
24.2
library
30
6.3
17
14.3
17.7
18.1
22.3
moonlit
1
omniquest
50
16.8
IN
10
17.2
pentari
60
1744
27.2
50.7
44,4
43.8
52.1
reverb
50
0.3
8.2
snacktime
50
9.7
0
22.1
temple
20
ztuu
100
100
49
21.6
9.2
85.4
79.1
87.2
advent
63,9
balances
51
30
4.8
I0
10
10
10
11.9
deephome
gold
100
30
4.1
0
0
2.1
jewel
4.46
karn
170
40
0.7
2.1
10
10
ludicorp
37
13.8
17.8
19.7
17
yomomma
34
0.4
1
zenon
20
zork1
350
102
32.6
38.3
38.8
44.3
work3
3
0.5
0.1
3.63
2.83
3.2
anchor
100
11
enchanter
125
12.1
20
20
36.3
400
150
20.8
38.6
38.3
24.5
spellbrkr
600
160
18.7
37.8
21.3
25
25
41.2
spirit
250
3.8
5.2
4.2
tryst205
350
50
9.6
10
10
13.4
agent
(18%))
(18%)
(15%)
12 (36%)
10 (30%)
(73%)
the Jericho games. We denote with colors the difficulty of the games (green for possible games, yellow difficult games and red for extreme games). The row reports the fraction and the absolute number of games where an agent achieves the best score. We additionally report human performance (Human max) and the 100-step results from human-writte walkthrough (Human Walkthrough 100). Results are taken from the original papers or "_" is used if result was not reported.
Table 3: Average
Obsorvations & Actions
Memory
Hard Medium Easy
Take diamond
Put emerald in case
OUT
Living Room
[..]
jewels case
0.8
Above the trophy case hangs [...]
Take diamond
-44
greet antiquity.
Take emerald
-12
IN
reuse: emerald
diamond
s/Action reuse
Nouural agent
Observations & Actions
Memory
Hard Medium Essy
Climb
Go west
OUT
Beside you on the branch is bird's
[..]
Take jewels
bird's is a large egg encrusted with precious jowels...
OUT
Take emerald
000
Action reuse: No valid action, falbbakk to neural policy
Rewarded Action
@Noo-rewarded action
Figure 3: Examples from the zorkl game, showing the content of the memory and the context similarities, in previous where the revise stop is needed.
Figure 4: Fraction of times that a retrieved action is reused successfully that the neural agent would have picked rewarded action when CBR used successfully (bottom).
TWC (top). Fraction of times
situation where the agent is able experience and
Ablation studies. order to understand the role of main modules of our CBR agent, we designed some ablation studies. First, instead of using the seeded GAT, define the context of state-action pair context(s;, az) as just one of the entities that a, is applied to. This definition suits well the TWC games because rewarded actions are always applied one target object and location for that object (see Appendix for details). Note that, since the set entities discrete, no context quantization is needed. We report the performance of the resulting BiKE CBR (w/o GAT) agent in
8

---

Published as a conference paper at ICLR 2022
Easy
Medium
Hard
10"
OOM
Memony s2e
BiKE+ CBR (w/o GAT)
16.32 1 1.10
36.13 1 1.40
45.72 1 0.63
10"
BIKE + CBR (w/o VQ)
22.67 1.23
43.18 2.10
49.21 1. 0.55
BIKE CBR (wlo GAT)
18.15 + 1.51
37.10 + 111
46.70 + 0.71
10f
BKE
BIKE CBR (w/ VQ)
27.75 + 2.11
44.55 + 1.67
50.00 + 0.00
BKE CBR (wto VQ)
Table 4:
Results of the ablation study on TWC, evaluated based on the number of steps (#Steps) to solve the games.
Figure 5: Number of entries in the memory over training.
Table The results show that CBR on 7WC is effective even with this simple context definition, but the lower performance of the agent demonstrates the advantage of incorporating additional context information. Finally, we investigate the role played by vector quantization, by experimenting with an agent (BiKE~ CBR w/o VQ) that stores the continuous context representations. In general, this poses scalability challenges, but since TWC has only 5 games per difficulty level, each with a small number of objects, were able evaluate the performance of this agent the three levels separately. The results, reported in Table 4, show that this agent performs much worse than the other CBR implementations. This happens because storing continuous representations over the training results in duplicated entries in the memory and makes it harder to retrieve meaningful experiences. Figure demonstrates how the size (number of entries) in the memory grows over the training time. In this experiment, we trained the agent on all difficulty levels at the same time, resulting in the implementation running out of memory (OOM) on the GPU, More ablation studies are reported in Appendix C, D, E, F, and G.
7 RELATED WORK
Text-based RL. TBGs are rich domain for studying grounded language understanding and how text information can be utilized in control. Prior work has explored text-based RL to learn strategies for multi-user dungeon games (Narasimhan et al., 2015) and other environments (Branavan et al., 2012). Zahavy et al. (2018) proposed the Eliminnti Deep Q-Network (AE-DQN), which learns to predict invalid actions in the text-adventure game Zork. Recently, Côté et al. (2018) introduced TextWorld
sandhox learning environment for training and evaluating RI. agents on text-based games. On the same line. Murugesan al. (2021b) introduced TWC that requires agents with commonsense knowledge (Murugesan et al., 2020; Basu et al., 2021). The LeDeepChef system (Adolphs & Hofmann, 2019) achieved good results on the First Textoor Problems (Trischler et al., 2019) by supervising the model with entities from FreeBase, allowing the agent to generalize to unseen objects. A recent line of work learns symbolic (typically graph-structure)) representations of the agent's belief. Notably, Ammanabrolu & Riedl (2019) proposed KG-DQN and Adhikari al. (2020) proposed GATA. We also use graphs model the state of the game.
Case-based reasoning in RL. In the context of RL, CBR has been used to speed up and improve transfer learning in basse RL. Celiberto Jr al. (2011) and Bianchi et al. (2018) have shown that cases collected from one domain can be used as heuristics to achieve faster convergence when learning an RL algorithm on different domain. scalable way of using CBR alongside deep RI methods in settings with very large state spaces. More recently, CBR has been successfully applied in the field of knowledge-based reasoning, Das et al. (2020) and Das et al. (2021) show that CBR can effectively learn to generate new logical reasoning chains from prior cases, to answer questions on knowledge graphs.
contrast to these works, we present a
CONCLUSION AND FUTURE WORK
In this work, we proposed new agents for TBGs using case-based reasoning. contrast to expensive deep RL approaches, CBR simply builds collection of its past experiences and uses the ones relevant to the current situation to decide upon its next action in the game. Our experiments showed that CBR when combined with existing RL agents can make them more efficient and aid generalization in out-of- distriiiintt settings. Even though CBR was quite successful the TBGs explored in our work, future work is needed to understand the limitations of CBR in such settings.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was funded in part by an IBM fellowship to SD and in part by small project grant to MS from the Hasler Foundation.
REFERENCES
Agnar Aamodt and Enric Plaza. Case-based reasoning: Foundational issues, methodological variations, and system approaches. Al communications, 7(1):39-59) 1994.
Ashutosh Adhikari, Xingdi Yuan, Marc-Alexandre Côté, Mikuláš Zelinka, Mare-Antoing 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 arXiv:2002.09127, 2020.
Leonard Adolphs and Thomas Hofmann. Ledeepchef: Deep reinforcement learning agent for families of text-based games. ArXiv, abs/1909.01646, 2019.
Prithviraj Ammanabrolu and Matthew Hausknecht. Graph constrained reinforcement learning for natural language action spaces. arXiv preprint arXiv:2001.08837, 2020.
Prithviraj Ammanabrolu and Mark Riedl. Playing text-adventure games with graph-based deep reinforcement learning. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 3557-3565, 2019.
Prithviraj Ammanabrolu, Ethan Tien, Matthew J. Hausknecht, and Mark O. Riedl. How to avoid being eaten by a grue: Structured exploration strategies for textual worlds. CoRR, abs/2006.07440, 2020. URL https://arxiv. http:/wwww..r//////.......0
Mattia Atzeni and Maurizio Atzori. Translating natural language to code: An unsupervised antology-based approach. In First IEEE International Conference on Artificial Intelligence and Knowledge Engineering, AIKE 2018, Laguna Hills, CA, USA, September 26-28, 2018, pp. 1-8. IEEE Computer Society, 2018. doi: 10. 10.1109/AIKE.201 8.0009. URL https:
/doi org/
10.1109/AIKE.
Mattia Atzeni, Jasmina Bogojeska, and Andreas Loukas. SQALER: Scaling question answering by decoupling multi-hop and logical reasoning. In A. Beygelzimer, Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htttss://ppenrett
net forum?id-2CQQ cli0b.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron C. Courville. Systematic generalization: What is required and can it be learned? In ICLR 2019.
Dana H. Ballard. An introduction to natural computation. Complex adaptive systems, MIT Press, 2000. ISBN 978-0-262-52258-
Kinjal Basu, Keerthiram Murugesan, Mattia Atzeni, Pavan Kapanipathi, Kartik Talamadupula, Tim Klinger, Murray Campbell, Mrinmaya Sachan, and Gopal Gupta. A hybrid neuro-symbolic approach for text-based games using inductive logic programming. In Combining Learning and Reasoning: Programming Languages, Formalisms, and Representations, 2021.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, abs/1308.3432. 2013. URL 3432.
http:/ /tt::///rxiine wttpaaawwi.ggaaaaaaaaaaa wtt.oorg//a/aaaaa/ooos
Reinaldo AC Bianchi, Paulo E Santos, Isaac Da Silva, Luiz A Celiberto, and Ramon Lopez de Mantaras. Heuristically accelerated reinforcement learning by means of case-based reasoning and transfer learning. Journal of Intelligent Robotic Systems, (1))3301--312, 2018.
SRK Branavan, David Silver, and Regina Barzilay. Learning to win by reading manuals in a monte- carlo framework. Journal of Artificial Intelligence Research, 43:661-704, 2012.
10

---

Published as a conference paper at ICLR 2022
Luiz A Celiberto Jr, Jackson P Matsuura, Ramon Lopez De Mantaras, and Reinaldo AC Bianchi. Using cases as heuristics reinforcement learning: a transfer learning application. In Twenty- Second International Joint Conference Artificial Intelligence, 2011.
Ting Chen, Martin Renqiang Min, and Yizhou Sun. Learning k-way d-dimensional discrete codes for compact embedding representations. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Muchine Learning, ICML, 2018, Stockholmsmüsssnn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, htw.eee..sssss...ses.s.eeee.esse
pp. 853-862. PMLR, 2018. URL httt:://prcceed: ngs mll. wwwspprsssvveee / chen' Bg. html.
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. 2018.
Rajarshi Das, Ameya Godbole, Shehzaad Dhuliawala, Manzil Zaheer, and Andrew McCallum. A simple approach to case-based reasoning in knowledge bases. arXiv preprint urXiv:2006.44199 2020.
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay- Yoy-Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases. arXiv preprint (rXiv:2104008760 2021.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HIT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019. URL https: /ttp://wwwwwo/// ac www.eb. anthology NN11-12331111
Xiaoxiao Guo, Mo Yu, Yupeng Gao, Chuang Gan, Murray Camphell, and Shiyu Chang. Interactive fiction game playing multi-paragraph reading comprehension with reinforcement learning. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7755-7765, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v 1/2020.emnlp main.624.
URL https: //tpa//taaaanttt..c..//. org 202C.
manlp-maiin 624.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), 17-22 June 2006, New York, NY, USA, pp. 1735-1742, IEEE Computer Society, 2006.
doi: 10. 10.1109/CVPR.20066 100. URL https /oi. oreeiiorrg1100 1109/CVPR. 2006.100.
Matthew Hausknecht, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. Interactive fiction games: A colossal adventure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7903-7910, 2020.
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. The Association for Computer Linguistics, 2016. doi: 10. 18653/v1/p16-1153 1153. URL https: http://o..o///////// /tt./oiiool.0001 1ttp:/00..1133/1111111111111
Pavan Kapanipathi, Veronika Thost, Siva Sankalp Patel, Spencer Whitehead, Ibrahim Abdelaziz, Avinash Balakrishnan, Maria Chang, Kshitij Fadnis, Chulaka Gunasekara, Bassem Makni, Nicholas Mattei, Kartik Talamadupula, and Achille Fokoue. Infusing knowledge into the textual entailment task using graph convolutional networks. AAAI, 2020.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Mare Zee, and Olivier Bousquet. Measuring compositional generalization: A
11

---

Published as a conference paper at ICLR 2022
comprehensive method realistic data. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. net fot.:/oorurridd-Syyccnll.....
URL Reconstructive memory: A computer model. Cognitive science, 7(4))281-328,
Janet L Kolodner. 1983.
Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman, Building machines that learn and think like people. Behavioral and Brain Sciences, 40:e253, 2017. doi: 10.1017/S0140522 00525516001837.
K. Murugesan, Subhajit Chaudhury, and Kartik Talamadupula. Eye of the beholder: Improved relation generalization for text-based reinforcement learning agents. ArXiv, abs/2106.05387, 2021a.
Keerthiram Murugesan, Mattia Atzeni, Pushkar Shukla, Mrinmaya Sachan, Pavan Kapanipathi, and Kartik Talamadupula. Enhancing text-based reinforcement learning agents with commonsense knowledge. CoRR, abs/2005.008 2020. URI.ttps::// /aa//aaivvvvo// http//aaww..og////////aaaa/////a
2005lbb///000000.0 00811.
Keerthiram Murugesan, Mattia Atzeni, Pavan Kapanipathi, Pushkar Shukla, Sadhana Kumaravel, Gerald Tesauro, Kartik Talamadupula, Mrinmaya Sachan, and Murray Campbell. Text-based rl agents with commonsense knowledge: New challenges, environments and baselines. In Thirty Fifth AAAI Conference on Artificial Intelligence, 2021b.
Keerthiram Murugesan, Mattia Atzeni, Pavan Kapanipathi, Kartik Talamadupula, Mrinmaya Sachan, and Murray Campbell. Efficient text-based reinforcement learning by jointly leveraging state and commonsense graph representations. In Proceedings of the 59th Aunual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pp- 719-725, 2021c
Karthik Narasimhan, Tejas Kulkarni, and Regina Barzilay. Language understanding for text-based games using deep reinforcement learning, arXiv preprint arXiv:/506.008 08941, 2015.
Mrinmaya Sachan. Knowledge graph embedding compression, In Dan Jurafsky. Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 2681-2691. Association for Computational Linguistics, 2020. doi: 1/2288663/11002.cclll doi. 10. 1ew.1/16611voo/ att.mmi..cmmmm.22.mm. 238.
URL https://
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of BERT: smaller, faster, cheaper and lighter. CoRR, abs/1910.01108, 2019. URL http://
01108.
Roger C Schank. Dynamic memory: A theory of reminding and learning in computers and people. cambridge university press, 1983.
Ishika Singh, Gargi Singh, and Ashutosh Modi. Pre-trained language models as prior knowledge for playing text-based games. CoRR, abs/2107. 084408808 2021. URL https://axxxv...r abs/ 2107. 08 08405.
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen. Open domain question answering using early fusion of knowledge bases and text. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 4231 2018.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Adam Trischler, Marc- Alexandre Côté, and Pedro Lima. First TextWorld Problems, the competition: Using text- games advance capabilities of Al agents, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine
Learning Research, 9:2579-2605, 2008. URL http: /www. jmlr. wwtppaapers//aaaaaooeoea//e/eeep
vandermeaten08ee html.
12

---

Published as a conference paper at ICLR 2022
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liô, and Yoshua Bengio. Graph attention networks. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: / openreview. net. forum? i d=rJXMpp kCZ.
Yunqiu Xu, Ling Chen, Meng Fang, Yang Wang, and Chengqi Zhang. Deep reinforcement learning with transformers for text adventure games. IEEE Conference on Games, CoG 2020, Osaka, Japan, August 24-27, 2020, pp. 65-72. IEEE, 2020. doi: 10. N1110//6647336620022222222 URL https: /ooi org / 10. 09 CCC//3666736 2020. 9231 622.
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3562-3573, 2018.
13

---

Published as a conference paper at ICLR 2022
A TRAINING DETAILS
All agents used in our experiments are trained with an Advantage Actor Critic (A2C) method according to the general scheme defined below. We use the n-step temporal difference method (Sutton & Barto, 2018) to compute the return R(s;, ax) of a single time step a session of length T as:
T-t
R(s =-)== (
Σ (S a(te),
where (8T)) denotes the value of 8T computed by the critic network, 7 is the discount factor, and r is the reward function. We then compute the advantage A(s,, a.) = R(s,, a.) V(s)). The final objective term consists of four separate objectives. First, we have c that denotes the objective of the policy, which tries to maximize the the advantage A:
C (st, a;) log (s)
We then add the objective of the critic as:
c (R(s), - -
c encourages the value of the critic V to better estimate the reward R by reducing the mean squared error between them. To prevent the policy from assigning a large weight on a single action, perform entropy regularization by introducing additional term:
L =
Σ T())())) log (())s)))
B.EAA
The 7 parameter helps balance the exploration-exploitaiii above objectives defines the loss when the neural agent used select the action of In actions are reused from the memory, then we use the contrastive loss as discussed in Section 5, namely we compute the loss as:
trade-off for the policy. The sum of the
1
C 21 y.)(1 - simmmii, 1)² + 2 max p- - 1 sim(ce, ee c,2)
B ENHANCING BASELINE AGENTS WITH CBR ON JERICHO
In this section, we report additional experimental results on a subset of the Jericho games, in order show the performance improvement obtained by different baseline agents when enhanced with case-based reasoning. 'abble 5 shows the results obtained when coupling the agents described in Section 6.1 with CBR. Similarly to what we discussed for 7WC in Section 6.2, we observe that CBR consistently improves the performance of all the agents. The best performing agent is BiKE CBR, which the agent that we evaluated on the complete set of games Section 6.3.
Game
KG-A2C KG-A2C + CBR
Text
Text CBR
TPC
TPC
CBR
BiKE
BiKE CBR
detective
207.9
255.6
205.8
242.3
245.6
315.1
278.2
326.1
inhumane
15.6
1.1
14.5
4.5
18.3
9.2
24.2
snacktime
15.5
8.1
9.8
15.7
19.3
18.8
22.1
karn
0
0
0
0
0
0
zork1
34
34,2
31.5
38.2
36
39.2
39,5
44,3
zork3
0.1
1.7
0
1.6
1.7
1.9
2.5
3,2
enchanter
12.1
26.2
10.1
26.4
13.2
24.5
19.7
36,3
spellbrkr 21.3
36.1
20.4
33.2
38.1
40.2
38.8
41.2
Table 5: Additional results on Jericho showing the performance improvement obtained by enhancing several baseline agents with CBR.
C ABLATION STUDY ON MEMORY ACCESS
In this section, we investigate the effectiveness of approach based vector quantization for efficient memory access. We consider several variants, where VQ either dropped completely or replaced with other techniques.
14

---

Published as a conference paper at ICLR 2022
C.1 ALTERNATIVES VECTOR QUANTIZATION
All the agents we consider are variants of the best-performing agent on Jericho and TWC, namely the BiKE CBR agent. We experiment with the following techniques.
BiKE + CBR (w/o VQ) completely removes the vector quantization and stores the continuous context representations keys in the case memory. In order to make this feasible, for the experiments on Jericho, we limit the size of the memory to the 5000 most recent entries.
BiKE + CBR (RP) relies on random projection (RP) in order reduce the dimensionality the context representations stored by the CBR approach. In this case, each context representation is projected into a y-dimensional space using random matrix R E IRpxd with components drawn from normal distribution (0, , with mean 0 and standard deviation
BiKE CBR (SRP) employs sign random projection (SRP) in order obtain discrete representation the context. In this variant, after projection to p-dimensional space, the context representations are discretized by applying an element-wise sign function.
BiKE + CBR (LSH) replaces vector quantization with locality sensitive hashing (LSH)). In this case, context representations are converted into h-bit hash codes for different hash tables. The retrieve step selects the representation with the highest cosine similarity to the query context encoding, among the vectors falling in the same bucket.
C.2 RESULTS AND DISCUSSION
Table 6 shows the scores achieved by each variant of the BiKE + CBR method on subset of the Jericho games. We notice that the approaches relying on continuous context representations (w/o VQ and RP) perform poorly compared the others and the plain BiKE agent. This confirms hypothesis that CBR needs discrete context representations to make the retrieve step more stable.
The BiKE CBR (LSH) agent, which relies locality sensitive hashing, achieves competitive results and consistently outperforms the BiKE agent. This shows that locality sensitive hashing can be viable alternative vector quantization. However, based on vector quantization, achieves better results on almost all the games, confirming the benefit well. Note also that LSH requires storing the complete
observe that our BiKE CBR agent,
of learning the discrete representation continuous representations to be able to detect false positives, namely contexts with the same hash code the query vector, but low cosine similarity. This makes this alternative less memory efficient compared to our implementation based on VQ.
Game
BiKE CBR (w/o VQ)
BiKE CBR (RP)
BiKE CBR (SRP)
BiKE CBR (LSH)
BiKE CBR
detective
205.2
203.1
223.2
319.1
326.1
inhumane
1.5
3.2
1.1
20.1
24.2
snacktime
9.1
14.3
13.2
20.3
22.1
karn
0
0
zorkl
31.5
36.3
40.5
41.2
44.3
zork3
2.7
2.7
3.6
3.2
enchanter 10.2
9.2
10.6
35.3
36.3
spellbrkr 21.3
23.8
30.8
39.3
41.2
Table 6: Ablation study showing the results obtained on a subset of the Jericho games when the vector quantization is removed (w/o VQ) replaced with random projection (RP), sign random projection (SRP) locality sensitive hashing (LSH).
D ABLATION STUDY ON THE RETAIN MODULE
In this section, we evaluate different alternatives to select which actions should be retained in the memory of the agent.
D.1 ALTERNATIVES FOR THE RETAIN MODULE
In our main experiments described in Section 6, the retain module has been implemented to store the last & context-action pairs in the memory, whenever the reward obtained by the agent is positive.
15

---

Published as a conference paper at ICLR 2022
For Jericho, we set ls 3, specified in Appendix J. However, other design choices are possible. We consider the following variants the BiKE + CBR agent.
BiKE CBR (rewarded action only) retains only the rewarded context-action pair, without sampling any of the previous actions. This variant is a simple implementation that works well in practice, but may fail to identify useful actions that were not rewarded.
BiKE + CBR (TD error) samples previous context-action pairs based on the temporal difference (TD) error. In details, the agent still retains k context-action pairs: whenever the reward re at time step is positive, the rewarded context-action pair (ct at) is retained, together with k 1 additional pairs sampled from the current trajectory, with a probability proportional to the TD error.
D.2 RESULTS AND DISCUSSION
Table 7 shows the scores obtained by the agents subset of the Jericho games. Our main implementation storing the last
actions achieves the best results, whereas the BiKE CBR (rewarded action only) agent performs slightly worse than the other two implementations. The agent based on the TD error achieves competitive results and a state-of-the-art score on the snacktime game. We observe that all variants perform well in practice and achieve overall better results than the baselines in Table 3.
Game
BiKE + CBR (rewarded action only)
BiKE + CBR (TD error)
BiKE + CBR
detective inhumane
324.1
324.8
326.1
20.1
23.5
24.2
snacktime
20.3
23.4
22.1
karn
0
zork1
40.2
42.4
44.3
zork3
3.2
3.2
3.2
enchanter
35.3
34.1
36.3
spellbrkr
40.3
40.8
41.2
Table 7: Ablation study showing the results obtained on subset of the Jericho games when only the context- action pair achieving positive reward is retained (rewarded action only), when context-action pairs are sampled using the TD error (TD error), and when the last 3 pairs retained (BiKE- CBR).
E TRAINING THE AGENT AND THE RETRIEVER JOINTLY
In this experiment, we try to understand if training the neural agent and the CBR retriever jointly would improve upon our choice of just training the two networks separately.
Our implementation works by training the neural agent π and the CBR retriever separately with different objectives, as described in Appendix A. However, we can make the neural agent aware of the CBR retriever and train the two networks jointly. this case, we need modify the architecture of the neural agent æ in order to take into account the action candidates As produced by the CBR. In details, we compute action selector by attention between the valid actions At and the candidates A and we concatenate this action selector to the vector used by the neural agent to score admissible actions. Then, the agent and the retriever can be trained jointly, optimizing an objective given by the sum of all the losses in Section A.
Table and show the results obtained by the baseline agents when they are trained jointly with the CBR retriever. On 7WC, we observe that the joint variants of the agents achieve comparable results with their counterparts in Table 1 and 2. On Jericho, the agents trained jointly with the retriever achieve strong results, but they perform slightly worse than the retriever separate from the neural agent. This shows that the joint version is slightly harder to train. Also, it brings the disadvantage that the architecture of the neural agent has to be changed to take the CBR into account, whereas our main approach that keeps the retriever separate allows readily plugging any on-policy agent for TBGs.
main approach that keeps
16

---

Published as a conference paper at ICLR 2022
Easy
Medium
Hard
#Steps
Norm. Scure
#Steps
Norm. Score
#Steps
Norm, Score
Tex CBR (joint)
17.91 3.80
0.04
40.22 + 1.70
0.65 +
47.94 1.10
0.33 0.02
TPC+ (joint)
KG-A2C+ CBR (joint)
16.40 = 1.89
0.95 + 0.05
36.50 = 1.13
0.68 +
46.58 0.91
0.40 = 0.06
BIKE + CBR (joint)
16.01 + 1.37
0.94 1 0.03
35,93 1 1.11
0.67 1
46.11 1.14
0.42 0.04
Text + CBR (joint)
21.47 1 2.32
0.88 1 0.07
39.10 1 1.33
0.67 1 0.02
48.10 1 0.92
0.31 1 0.03
OUT
TPC CBR (joint)
17.89 = 1.82
0.93 = 0.01
38.11 = 1.33
0.65 = 0.03
47.92 1.55
0.34 = 0.03
KG-A2C+ CBR (joint)
18.19 = 2.12
0.93 = 0.02
37.72
= 2.91
0.66 + 0.03
47.53 1.11
0.40 = 0.04
BiKE CBR (joint)
18.12 + 1.21
0.94 0.05
35.77
1.05
0.69 + 0.05
46. 16 1.00
0.40 0.04
Table 8:
Test-set results obtained on TWC in-distribution (IN) and ont-of-distribution (OUT) games training different neural agents and the CBR retriever jointly.
Game
KG-A2C CBR (jontt
Text CBR (joint)
TPC CBR (joint)
BiKE + CBR (joint)
detective
250.1
241.5
316.2
324.2
inhumane
15.1
13.2
16.3
24.1
snacktime
13.2
11.2
20.1
21.8
karn
0
0
0
0
zorkl
36.4
36.5
36.3
43.7
zork3
1.5
1.5
1.8
3.6
enchanter
25.1
26.1
21.1
35.6
spellbrkr
32.3
33.3
39.2
41.8
Table 9: Results obtained subset of the Jericho games training different neural agents and the CBR retriever jointly. Bold values indicate when the joint variant achieves better scores than the main counterparts reported in Table 5.
F MULTT-PARAGRAPH TEXT-BASED RETRIEVER
Knowledge graphs have been used extensively in text-based games and other areas of natural language understanding (Ammanabrolu & Hausknecht, 2020; Atzeni & Atzori, 2018; Kapanipathi al., 2020). This section describes alternative to rrpphbbaeed retriever, which only relies the textual observations without modeling the state of the game as a graph.
Recent work (Guo al., 2020) has shown that enriching the current observation with relevant observations retrieved from the history of interactions with the environment can achieve competitive results on Jericho. Therefore, in order assess the effectiveness of our graph-based implementation. we compare to multi-paragraph text-based retriever (MTPR) inspired by the work of Guo et al. (2020). In this case, we do not model the state as graph and, subsequently, we remove the seeded graph attention mechanism from the retriever. Instead, given the current natural language observation o,, we compute an action-specific representation following Guo et (2020), concatenating with the n most recent observations that share objects with it or with the given action. The encoded observation is then discretized using vector quantization as our main architecture.
We evaluated the text-based retriever on Jericho, integrating it in the same baseline agents described in Section 1. Table 10 shows the scores obtained by the agents. We observe that, overall, the graph-based retriever performs better on the vast majority of the games. This result confirms the ability of our approach based on seeded graph attention to extract relevant information from the state the game, compared to retriever that only relies on text information.
G ADDITIONAL RESULTS USING ENTITIES AS CONTEXT SELECTORS
As mentioned in Section 6.4, we performed an ablation study where the seeded graph attention and the state graph where not used in the retriever. Instead, we represent the context as just a single focus entity. This choice suits very well the TWC games, the goal of each game is to tidy up house by putting objects in their commonsensical locations. Hence, each rewarded action 7WC is the form "put S "insert in c², where is entity of type object, supporter, and is
17

---

Published as a conference paper at ICLR 2022
Game
KG-A2C + CBR (MPTR)
Text + CBR (MPTR)
TPC + CBR (MPTR)
BiKE CBR (MPTR)
detective
245.2
233.7
302.3
321.2
inhumane
13.4
13.2
12.3
20.3
snacktime
12.1
8.2
18.1
19.5
karn
0
0
zork1
36.2
36.2
37.4
42.2
zork3
0.8
1.2
3.2
3,6
enchanter
19.3
24.3
20.2
32.1
spellbrkr
31.3
30.3
39.3
40.8
Table 10: Results obtained subset of the Jericho games using the multi-paragraph text-based retriever (MPTR) instead of the graph-base basp- one. Bold values indicate when the MPTR variant achieves better scores than the main counterparts reported Table
container (Murugesan et al., 2021c; Côté et al., 2018). As example, rewarded action could be "insert dirty singlet in washing machine", where dirty singlet is the object and washing machine is the container.
Representing the context as just single entities of type object, means that the memory of the CBR agent is storing what action to apply each object in the game, and therefore the agent is in practice constructing a registry where each object paired with commonsensical location. Let Gus Cu. be two context entities. The retriever then computes the similarity between the contexts as:
sim( Ca) = cosine(FFN((h)j) FFN(h))),
where cosine denotes the cosine similarity, FFN is 2-layer feed-forward network and he, ba are the BERT encodings of the [CLS] token objects v and respectively. The retriever is therefore encouraged to map objects that should be placed in the same location (either supporter or a container) to similar representations.
Figure 6 depicts t-SNE (van der Maaten & Hinton, 2008) visualization of the representations FFN(h.) learned by the retriever of the BiKE + CBR (w/o GAT) agent. The plot shows that entities that belong to the same location mapped to similar representationss. This holds both for objects in the in-distribution games and for objects in the out-of-distribution games.
welt T-shirt wot hoodle aoo white shirt white
brown cap
* OUT
stop
scarf
derby
checkered shirt singlet
pullover
while
x
dirly gray underpents dirty yellow T-shirt
xdrrly magenta skirt
vvogetable oil
yccloan white skint
wel azure drees
seblack gray blazer
wet blue jumper
celcaan skit olean white pullover
eleen dreas
Figure Visualization of the entity representations learned by retriever. Colors denote the target location of each object.
We evaluated all the CBR agents with the simple retriever defined above. Table 11 reports the results for the in-distribution and out-of-distribure games. The results confirm that the entity-basee context selection performs well and achieves good out-of-distribution generalization. However, we remark that the complete retriever deseribed in Section 4 consistently achieves better results, showing the importance of incorporating additional structured information.
18

---

Published as a conference paper at ICLR 2022
Easy
Medium
Hard
#Steps
Norm, Score
#Steps
Norm, Score
#Steps
Norm. Score
CBR (w/o GAT)
22.70 2.05
0.81 0.07
44.13 + 1.15
0.62 0.04
48.05 = 1.30
0.33 0.05
Text + CBR (w/o GAT)
19.01 3.99
0.89 0.05
40.10 1 1.52
0.67 0.05
47,80 = 1.32
0.33 0.02
2
TPC CBR (wlo GAT)
17.15 2.91
0.94 0.04
38.32 + 1,76
0.66 0.03
47. = 1.35
0.36 0.03
KG-A2C+ CBR (wlo GAT)
16.67 2.30
0.96 0.03
38.05 + 1.84
0.66 0.04
46.45 = 1.02
0.38 0.02
BiKE CBR (w/o GAT)
16.32 1.0
0.95 0.03
36.13 = 1.40
0.67 0.04
45.72 = 0.63
0.41 0.03
CBR (w/o GAT)
23.90 2.17
0.79
44.71 1.50
0.61 0.04
48.87 + 1.89
0.31 0.0
Text CBR (w/ GAT)
21.64 2.52
0.88 0.02
41.12 1.21
0.66 0,05
48,00 1.10
0.32 0.06
TPC CBR (w/o GAT)
19.82 2.13
0.92 0.03
39.34 1,01
0.67 0,02
47.33 1: 1.30
0.36 0.04
KG-A2C+ CBR (wlo GAT)
19.07 2.50
0.92 0.02
38.41
1.94
0.65 0,04
46.89 + 2.21
0.37 0.03
BIKE CBR (w/o GAT)
18.15 1.51
0.92 0.03
37,10
1.41
0.67 0.03
46.70 0.71
0.39 0.03
Table 11: Test-set performance for TWC in-distribution (IN) and out-of-distribution (OUT) games using
entities as context selectors.
H CASE-BASED REASONING AND OUT-OF-DISTRIBUTION GENERALIZATION
Out-of-distribution generalization has recently fueled significant research effort and several datasets and approaches have been proposed in the past few years (Bahdanau et al., 2019; Keysers et al., 2020; Atzeni et al., 2021). Our experiments on TWC allowed assessing the hypothesis that case-based reasoning can be used to tackle out-of-distrre ofstiiibiiittiion (OOD) generalization in text-based games. Table 12 shows the absolute OOD generalization gap of the different agents evaluated in our experiments. Note that this table does not report any new result, but it simply provides the absolute difference between the values in Table 1 and 2. We observe that the agents relying on CBR achieve a considerably better generalization performance out of the training distribution, almost comparable to the results obtained on the same distribution as the training data. some cases, the normalized score achieved by the CBR agents in the of-iisriibbttoinnn games equals the score obtained in the in-distribution games. This happens because case- case-based reasoning forces the agent to map contexts including entities that were not seen at training time to the most similar contexts in the CBR memory. CBR allows the agent to solve completely new problems and generalize by effectively retrieving past cases and mapping the retrieved actions from the training distribution to the most similar options in the OOD setting. Note that the only good OOD generalization gap for the agents that are not relying on CBR (the #Steps of the Text agent on the Hard level) an artifact of the experiment, as all agents were limited to maximum of 50 steps.
Figure 6 shows a nice example of the capability of the agent to generalize OOD. this case, entity embeddings were used as the context representations, and we observe that entities that are not included in the training distribution are correctly mapped to the right cluster. This shows that the CBR approach learns effective and generalizable context representations based on the objective of the games. These representations are then used by the agent to select relevant experiences and map the actions used at training time the most viable alternative in the OOD test set.
Easy
Medium
Hard
#Steps
Norm. Score
#Steps
Norm. Score
#Steps
Norm. Score
Text TPC
6.07
0.10
1.82
0.05
0.16
0.10
7.15
0.11
2.28
0.04
1.55
0.13
KG-A2C
6.24
0.06
1.44
0.03
2.00
0.11
BiKE
7.32
0.11
1.67
0.03
2.81
0.11
CBR-only
1.30
0.00
0.27
0.01
0.59
0.02
Text + CBR
3.38
0.04
1.22
0.00
0.78
0.02
TPC CBR
2.09
0.02
0.25
0.01
0.29
0.03
KG-A2C CBR
2.30
0.05
0.89
0.02
0.99
0.02
BiKE CBR
1.43
0.02
0.21
0.00
0.70
0.02
Table 12: Absolute out-of-distribution generalization gap in 7WC
19

---

Published as a conference paper at ICLR 2022
I ADDITIONAL BASELINES ON JERICHO
Several methods have been proposed recently for text-based games. order to keep the results the main paper compact, only included in Table 3 well-known and top-performing baselines that were evaluated on the full (or almost) set of Jericho games. For completeness, this section compares best agent (BiKE + CBR) with the following additional methods:
Q*BERT (Ammanabrolu al., 2020) is deep reinforcement learning agent that plays text games by building a knowledge graph of the world and answering questions about
Trans-y-DRRN (Xu et al., 2020) relies lightweight transformer encoder to model the state of the game;
DBERT-DRRN (Singh et al., 2021) makes use of DistilBERT (Sanh et al., 2019) fine-tuned on an independent set of human gameplay transcripts.
Table 13 shows the scores obtained by these baselines compared to our agent enhanced with CBR.
Overall, observe that the BiKE CBR agent outperforms the baselines the majority of the games, confirming the effectiveness of case-based reasoning viable approach to boost the performance of text-based RL agents.
QBRRT Trans-y-DRRN
DBERT-DRRN
BiKE
905
acorncourt
adventureland
25.6
27.3
afllicted
2
awaken
detective
246.1
288.8
326.1
dragon
8.3
inhumane
32.8
24.2
library
10.0
17
17
22.3
moonlit
omniquest
4.9
pentari
48.2
34.5
52.1
reverb
10.7
snacktime
20
22.1
temple
7.9
ztuu
4.8
87.2
advent
balances
9.8
11.9
deephome
gold
2.1
jewel
6.5
karn
ludicorp
12.5
yomomma
0.5
zork1
33,6
36.4
44.7
44.3
anchor
enchanter
20.0
36.3
sorcerer
24.5
spellbrkr
38.2
41.2
spirit
2.1
4.2
tryst205
9.6
9.3
Table 13: Average the Jericho games. Results taken from the original papers or "_" used result was not reported.
J HYPERPARAMETERS AND REPRODUCIBILITY
All CBR agents are trained using the same hyperparameter settings and the same hardware/software configuration. As mentioned in Section 4, we use a pre-trained BERT model (Devlin et al., 2019) to represent initial node features in the state graph. BERT is only used to compute the initial representations of the entities and is not fine-tuned. We use the following hyperparameters for our experiments.
We set the hidden dimensionality of the model to d = 768 and we use 12 attention heads for the graph attention network, each applied to 64-dimensional inputs.
20

---

Published as a conference paper at ICLR 2022
We use 2 seeded GAT layers for 7WC and ny for Jericho.
On both datasets, we apply a dropout regularization on the seeded GAT with probability of 0.1 at each layer.
Similarly, for the experiments TWC, we only sample the most recent context-action pair from T. whereas we sample k = 3 pairs for Jericho. We used k for the scalability
analysis depicted in Figure
The retriever threshold is kept constant to 0.7 across all experiments.
On TWC, we train the agents for 100 episodes and maximum of 50 steps for each episode. On Jericho, as mentioned, we follow previous work and we train for 100 000 valid steps, starting episode every 100 steps whenever the games ends.
We set the discount factor y to 0.9 on all experiments.
For the ablation study on memory access, we set the output dimensionality of the RP and SRP methods to p 64. For LSH, set the number of hash tables to / = 16 and the length of the hash codes of bits. We artificially limit the size of each bucket to the most recent entries.
Experiments were parallelized cluster where each node dedicated separate run. The configuration of the execution nodes is as reported Table 14.
Resource
Setting
CPU
Intel(R) Xcon(R) CPU E5-2690 v4 2.60GHz
Memory
128GB
GPUs
1x NVIDIA Tesla k80 12 GB
Diskl
100GB
Disk2
600GB
OS
Ubuntu 18.04-64 Minimal for VSI
Table 14: Hardware and software configuration used to train the agents
21


Reviews:
[{"review_id": "vqcohPwDVfl", "reviewer": "Reviewer_HscQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Authors show that combining CBR with existing RL methods improves agent performance significantly. \n2. Authors conduct detailed experiments (existing RL models + CBR) which show the effectiveness of the proposed approach. The proposed model is more sample efficient and generalizes better.    \n\nWeaknesses:\n1. The different components proposed in the paper, (e.g., CBR, KG) are not novel per se for the text-based RL agents. The paper has limited novelty. \n2. There has been recent work that has used transformer-based LMs for text-based RL agents [e.g., 1,2,3]. Since Transformers are trained on very large corpora, they have been shown to encode world knowledge and hence work well in text-based world settings when combined with an RL agent. The authors do not compare to these approaches. It would be nice to have a comparison with these knowledge-based approaches as well.   \n\n[1] Deep reinforcement learning with transformers for text adventure games, Y. Xu, et al., 2020: https://ieeexplore.ieee.org/document/9231622  \n[2] Pre-trained Language Models as Prior Knowledge for\nPlaying Text-based Games, Singh, et al., 2020: https://arxiv.org/abs/2107.08408\n[3] Stabilizing transformers for reinforcement learning. Parisotto, et al., 2020: https://arxiv.org/abs/1910.06764 \n\nSuggestion:\n\nAuthors say that they use A2C as the RL agent, however, they cite the paper that describes A3C, so it is not exactly clear if they are using a synchronous or asynchronous version of the Advantage Actor-Critic agent. More details on this would help. ", "summary_of_the_paper": "In this paper, the authors propose to improve the existing policy-based RL algorithms for the text-based world environments by incorporating knowledge via a case-based reasoning module. This improves out of distribution performance. The key idea in Case-Based Reasoning is to collect interactions that led to positive rewards in the past and try to map a novel situation to one of these past interactions to decide on the action in the current situation. In particular, authors represent the state of a text-based game by a knowledge graph and use message propagation (focussed on the sub-set of the nodes) to get the most similar representation of a new context. ", "summary_of_the_review": "The paper proposes the use of Case-Based Reasoning combined with Knowledge Graphs for improving RL agents for text-based environments. However, the approach has limited novelty as similar approaches have been proposed in the past. On the evaluation side, authors should also compare with other approaches (e.g., based on Transformers) that make use of external knowledge to generalize better. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "saAdd8c9e4_", "reviewer": "Reviewer_aw9P", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Using the Neurips rubric:\n\nOriginality: As the related work shows,  CBR to speed up RL has been tried before, however those methods are very different and not meant for the modern scale of deep RL and contextualized representations+retrieval methods. The actual details of the CBR model used in this paper, seeded graph attention and vector quantization to aid retrieval seem relevant at least in their application to doing CBR for RL. \nThe basic experiments are straightforward, applying combinations of CBR and sota RL methods on the 2 TAG domains. However, there are a couple of novelties in the ablations and a very good qualitative analysis to show where the gains from CBR are coming from (fig 3).\n\nQuality: I thought the model described in sec 4 was interesting and mostly well-motivated. Some minor questions:\n  a. comparing the 2 equations in seeded graph attention, it looks like the h's dependency on $\\alpha$ is quadratic, which seems unusual for attention?\nb. why sum for the final representation and not average? it could lead to wierd biases when the number of entities are different between states.\nc. The VQ approach is interesting, but I am a bit skeptical that it is necesary. Very efficient methods exist to do retrieval in large dim spaces, with some effort. So for practical applications, it might just be easier to do that. Can you share some quantitative measurements to show that this code splitting approach is necessary?\nd.  The claim that CBR lets you generalize OOD seems not supported and my intuition is almost the opposite. Can you elaborate?\ne. The CBR and neueral agent seem to be separately trained. Can they be jointly optimized or at least can the neural agent be trained with  some knowledge of when the CBR will over-ride it so that it's policy can adapt to that?\nf. Fig 4: it would be more interesting if this could show the \"counterfactual\" probabilties. since the neural agent always loses to the CBR in action selection, what if the neural agent had been allowed to execute, would it still have been successful?\ng. Is locality sensitive hashing another way to do efficient retrieval that can generalize?\n\nClarity: the paper is well written and all major parts are well-explained. A few details could use some clarity:\na.  when you say \"the final set of all retrieved actions and the corresponding relevance\", can you be more precise and define the tuple or whatever exactly the data structure is.\nb. sec 4.3: \"applied to the entities\": how does it choose which entities to use?\nc. Please elaborate on the Adolphs and Hofmann method, even though it's not an original contribution it is a core part of your system.\nd. The jump from 24% to 73% in win rate on Jericho seems really big ! You should highlight it more.", "summary_of_the_paper": "This paper describes how to apply  a combination of case-based reasoning and RL methods to improve performance of agents on text-adventure game type tasks. It introduces a GNN representation of state and a vector-quantized encoding scheme so that contextual information about successful actions from the past can be retrieved and re-used. Experiments show a significant increase in performance, along with ablations showing value of the CBR  especially on OOD environments.Finally there is qualitative insights  of the memory representation showing how the CBR helps.", "summary_of_the_review": "Fairly well-thought out scalable approach to adding CBR to a tough RL setting which has got some attention recently. Strong results and good empirical analysis. It would be beneficial to get RL practitioners to seriously consider adding CBR type approaches as a new type of strategy for boosting Deep RL.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nsGrYH1ia33", "reviewer": "Reviewer_eX6x", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- The core idea is well defined and motivated. \"Lets get agents to use previous useful experiences to better improve the current policy\"\n\n- The paper is well written overall I was mostly able to follow along, model design choices are mostly explained.\n\n- The paper compares to multiple existing methods and the line up of related work baselines strengthens the work.\n\nClarifications/Concerns/Weaknesses:\n\n- Section 3&4 in particular are a bit unclear and can be consolidated more. I think providing details of each portion under the relevant subsection of the 4 step CBR algorithm would make it a lot more clear.\n\n- The retrieve portion in particular seems very similar to many other retrieval methods recently seen in text based game literature and the wider NLP community. It would be nice to see a comparison/ablation in *just the retrieve portion* to not use the knowledge graph and only text on *Jericho* (one obvious way would be to frame it as a Machine Reading Comprehension task to retrieve passages as in Guo et al. 2020 https://arxiv.org/abs/2010.02386 [which is cited and compared to for TWC]). Without such experiments it is relatively unclear whether the portions shown in Sec 4.1 are aiding, and if so how.\n\n- The \"Baseline agent + CBR\" comparisons are good to have but would probably be more useful to have in Jericho than TWC. The main reason being that TWC is a singular \"home\" domain in which the commonsense knowledge (the text descriptions + genre knowledge) are more likely to be uniform throughout than with the varying genres like Jericho. This tests the limits of the CBR process and gives you the ability to analyze exactly in what portion of cases in certain types of knowledge transferable. In my opinion, such an analysis would likely prove to be the most valuable contribution of a work like this.", "summary_of_the_paper": "The paper presents, at its core, a case-based reasoning (CBR) centered approach to solving text-based games. The CBR process shown is a 4 step process consisting of: retrieve (useful past experiences), reuse (the past experiences in a meaningful manner), revise (modify the current policy to account for prior experiences), and retain (decide which experiences to keep). This method is applied to an A2C agent that uses a knowledge graph based state representation, though it can be used along with other types of text game agents too.\n", "summary_of_the_review": "The paper is well written and presents a useful paradigm for thinking about text game agents and the results are interesting. The main thing holding the paper back is the lack of analysis/ablations on certain portions of the proposed algorithm that make it unclear where the gain are coming from.\n\n\n====Rebuttal Update====\nI've read the rebuttal across the reviewers and am satisfied enough to increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "euOAlQ66Iv5", "reviewer": "Reviewer_Da5u", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n- Solid approach combining CBR and RL\n- Experiments are thorough and convincing.\n- Writing is quite clear\n\nWeaknesses:\n- Some design choices may need more justification/analysis (see below, mainly points 3 and 4)\n\nComments:\n1. In the retriever module, how is the threshold $\\tau$ chosen?\n2. Algorithm 1 describes performing retrieval using multiple context selectors $\\mathcal{C}_t$. How are these specified and how are they different from each other? Do they store different types of contexts?\n3. The ‘Retain’ module seemed a bit ad-hoc to me since the module stores actions with positive rewards only. This goes against the key premise of performing good credit assignments in RL since the crucial action that led to this positive reward may occur 5 or 10 or even 20 steps before the transition with the positive reward. I suspect this is why storing previous actions helps empirically. So, to me, this design choice seems arbitrary and not well motivated. In fact, why not store negative actions as well or even use a prioritization scheme based on TD error similar to that in https://arxiv.org/abs/1511.05952 ? An ablation on this (even on a small subset of the games) may be helpful.\n4. The context discretization scheme in 4.2 reminds me of this paper (https://arxiv.org/abs/2103.13552) that used hash functions to represent the state. Would just hashing the state (e.g. with locality sensitive hashing (LSH) on fixed pre-trained BERT representations) with a random function work as well as the learned discretization scheme? Again, an ablation on just a subset of the games might be useful here. \n5. On the same point as above, the paper mentions that the discretization scheme helps tackle the issue of changing representations over the course of training. However, since the discretization is also a learned function, wouldn’t that also potentially change over time? It wasn’t clear how this solves the issue of the same context mapping to two different entries in the memory.\n6. In table 3, the term “win rate/win count” for the last row was confusing. I took it to be the win rate on the games themselves, but it seems to be a comparison across the different models. I suggest changing it to something clearer.\n7. It is also unclear how exactly the model chooses between two actions which have the same template, since they have the same relevance $\\delta$ value (which depends only on the template?). For example, in figure 3, I’m not sure how the agent picks `Put emerald in case` over `Put jewels in case`.", "summary_of_the_paper": "This paper proposes an approach to combine case-based reasoning with reinforcement learning for text-based games. The method works by keeping track of states that received positive rewards in the game, and then having a retrieval mechanism to retrieve similar contexts at a new state in the game. The authors use a quantization technique for efficient storage and retrieval, and a fallback neural policy (trained with RL) in cases where none of the retrieved action templates result in an admissible action in the current state. The writing is quite clear and the experiments are mostly convincing, barring a few questions I have.", "summary_of_the_review": "I think this paper is exploring a novel direction, has good empirical results and would be a valuable addition to the literature. Addressing the points mentioned above would further strengthen the paper and I’m happy to raise my score if the authors can provide convincing responses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes how to apply a combination of case-based reasoning and RL methods to improve the performance of agents in text-adventure games.  The reviewers unanimously recommend acceptance.  This work is both insightful and practical.  This is a valuable contribution.  Well done!
Decision: Accept (Poster)