Episodic Reinforcement Learning with Associative Memory
Authors: Guangxiang Zhu*
Zichuan Lin*
Guangwen Yang
Chongjie Zhang
Venue:  (2020)
Keywords: Deep Reinforcement Learning
Episodic Control
Episodic Memory
Associative Memory
Non-Parametric Method
Sample Efficiency

Abstract: Sample efficiency has been one of the major challenges for deep reinforcement learning. Non-parametric episodic control has been proposed to speed up parametric reinforcement learning by rapidly latching on previously successful policies. However, previous work on episodic reinforcement learning neglects the relationship between states and only stored the experiences as unrelated items. To improve sample efficiency of reinforcement learning, we propose a novel framework, called Episodic Reinforcement Learning with Associative Memory (ERLAM), which associates related experience trajectories to enable reasoning effective strategies. We build a graph on top of states in memory based on state transitions and develop a reverse-trajectory propagation strategy to allow rapid value propagation through the graph. We use the non-parametric associative memory as early guidance for a parametric reinforcement learning model. Results on navigation domain and Atari games show our framework achieves significantly higher sample efficiency than state-of-the-art episodic reinforcement learning models.

Published as a conference paper at ICLR 2020
EPISODIC REINFORCEMENT LEARNING WITH Asso- CIATIVE MEMORY
Guangxiang Zhu'; Zichuan Lin", Guangwen Yang', Chongjie Zhang'
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China DDeparmeent of Computer Science and Technology. Tsinghua University, Beijing, China guangxlangzzuu@ut
com, 1inzc1 6emailemmmmll tsinghua. edu. ygw@tsinghua. edu. cn, chongjie@tsinghuue eew.:ttssiinnuuuueee.......
ABSTRACT
Sample efficiency has been one of the major challenges for deep reinforcement learning. Non-parametric episodic control has been proposed to speed up para- metric reinforcement learning by rapidly latching previously successful poli- cies. However, previous work on episodic reinforcement learning neglects the relationship between states and only stored the experiences as unrelated items. To improve sample efficiency of reinforcement learning, we propose a novel frame- work, called Episodic Reinforcement Learning with Associative Memory (ER- LAM). which associates related experience trajectories to enable reasoning effec- tive strategies. We build graph on top of states memory based on state tran- sitions and develop eveers-trajectory propagation strategy to allow rapid value propagation through the graph. We use the non-part con-paramttric associative memory as early guidance for parametric reinforcement learning model. Results on the nav- igation domain and Atari games show our framework achieves significantly higher sample efficiency than ofate-of-the-at episodic reinforcement learning models.
INTRODUCTION
Deep reinforcement learning (RL) has achieved remarkable performance on extensive complex do- mains (Mnih et al. 2015 Lillicrap et al. 2016 Silver et al., 20166; Schulman et al. 2017). Deep RL research largely focuses on parametric methods, which usually depend on a parametrized value function. The model-free approaches are quite sample inefficient and require several orders of mag- nitude more training samples than human. This is because gradient-baad based updates are incremental and slow and have global impacts on parameters, leading to catastrophic inference issues.
Recently, episodic reinforcement learning has attracted much attention for improving sample eff- ciency of deep reinforcement learning, such as model-free episodic control (MFEC) (Blundell et al.) 2016), neural episodic control (NEC) (Pritzel et al. 2017). ephemeral value adjustments (EVA) (Hansen et al. 2018), and episodic memory deep g-networks (EMDQN) (Lin et al. 2018). Episodic control is inspired by the psychobiological and cognitive studies of human memory (Sutherland & Rudy 1989 Marr al. [991 Lengyel & Dayan 20088 Botvinick al. 2019) and follows the idea of instance-based decision theory (Gilboa & Schmeidler 1995). It builds a non-parametric episodic memory store past good experiences and thus can rapidly latch onto successful policies when encountering states similar to past experiences.
However, most of the current breakthroughs have focused on episodic memory and leave the asso- ciation of memory largely unstudied. Previous work usually uses tabular-like memory, and expe- riences stored unrelated items. Studies in psychology and cognitive neuroscience (Kohonen) 2012 Anderson & Bower, 2014) discover that associative memory in the hippocampus plays a vital role in human activities, which associates past experiences by remembering the relationships be- tween them. Inspired by this, we propose a novel associative memory based reinforcement learning framework to improve the sample-effciency of reinforcement learning, called Episodic Reinforce- ment Learning with Associative Memory (ERLAM), which associates related experience trajectories
"Equal Contribution

---

Published as a conference paper at ICLR 2020
to enable reasoning effective strategies. We store the best historical values for memorized states like episodic memory, and maintain graph on top of these states based on state transitions at the same time. Then develop an efficient reverse-trajectory propagation strategy to allow the values of new experiences to propagate to all memory items through the graph rapidly. Finally, we use the fast-adjusted non-parametric high values in associative memory early guidance for a parametric RL agent so that it can rapidly latch on states that previously yield high returns instead of waiting for many slow gradient updates.
To illustrate the superiority of the associative memory in reinforcement learning, consider robot exploring in maze to seek out the apple (place G), as shown in Fig- ure It collects two trajectory experiences starting from place A and B (i.e., blue dash line A-D-C and B-D-G), respectively. All the states of trajectory A-D-C receive no reward because the agent terminates (place C). While trajectory B-D-G, the final non-zero reward of catching apple (place G) pack-propagate to all the states of this trajectory. Episodic memory keeps a higher value of trajectories at the intersection (place D) when taking actions toward the lower-right corner, but the other states trajectory A-D are still O. If an episodic memory based robot starts from place A again, it will wander around A because there are no positive values in- dicating the way to the goal. Thus based on the episodic memory, the robot may eventually take policy like the green line (A-B-D-G) after multiple attempts. However, the robot adopts associative memory, the high value the place D collected from trajectory B-D-G will be fur- ther propagated to the start point A, and thus the robot can correctly take the red-line policy (A-D-G).
C
A
non-reward state
D
G
B
Episodic
Associative
Past Experiences
Memory
Memory
Figure 1: Comparison of selected poli- cies based on episodic memory and as- sociative memory. An agent starts from two places A and B, collect two periences.
To some extent, our associative memory is equivalent to automatic augmentation of counterfactual combinatorial trajectories in memory. Thus, framework significantly improves the sample- efficiency of reinforcement learning. Comparisons with state-of-the-art episodic reinforcement learning methods show that ERLAM is substantially more sample efficient for general settings of reinforcement learning. In addition, our associative memory can be used as plug-and-play module and is complementary other reinforcement learning models, which opens the avenue for further research on associative memory based reinforcement learning.
2 BACKGROUND
In the framework of reinforcement learning (Sutton Barto 1998), an agent learns a policy to maximize its cumulative rewards by exploring in a Markov Decision Processes (MDP) environment. a finite set of states, A is a finite set of
An MDP defined by a tuple (S,A, P, R),). where actions available to the agent, P S x A x + R defines the transition probability distribution, R the reward function, and 7 E (0, is the discount factor. At each time step t, the agent observes state s; S, selects action a, AA according to its policy π S - A, and receives scalar reward rt. In the setting of finite horizon, the accumulated discounted return is calculated as, E T where T is the episode length and goal of the agent is to maximize the expected return for each state St.
R2 =
The state-action value function Q* a) E[Riss = s, a. is the expected return for executing action on state s and following policy afterwards. DQN (Mnih et al.) 2013) parameterizes this action-value function by deep neural networks Qo(s, a) and use Q-learning (Warkins & Dayan 1992] to learn it to rank which action at is best to take in each state 8; at time step The parameters of the value network 0 are optimized by minimizing the Le difference between the networks output Qo(s,a) a) and the Q-learning target Ye rt + y max, Q5(s(+1, oz), where Ô are parameters of target network that is a older version of the value network and updated periodically. DQN uses an off- off-policy learning strategy, which samples (St, 0e, Ft, 81+1) tuple from replay buffer for training.
2

---

Published as a conference paper at ICLR 2020
DQN, typical parametric reinforcement learning method, suffers from sample inefficiency be- cause of slow gradient- based updates. Thus episodic reinforcement learning is proposed to speed up the learning process by a non-parametric episodic memory. Episodic reinforcement learning en- ables fast learning by modeling hippocampal instance-based learning. The key idea is to store good past experiences in a tabular-based con-parametric memory and rapidly latch onto past successful policies when encountering similar states instead of waiting for many steps of optimization.
3 RELATED WORK
Deep Reinforcement Learning Our method is closely related to DQN (Mnih et al. 2015). As the seminal work of deep reinforcement learning, DQN learns a deep neural network for state-action value function by gradient back-propagation and conducts parametric control. Following this line, large number of extensions have been proposed to improve the learning efficiency of the parametric model. Double DQN (Van Hasselt et al. 2016) alleviates the over-estimation issue of Q-Network. Ducling network (Wang et al. 2015) separates Q-Network into two streams which predict state value and advantage value respectively and achieves better generalization across actions. Prioritized expe- rience replay (Schaul et al. 2015b) changes the sampling priority of each training sample according its learning error. Apart from these prior improvements, many algorithms have been proposed to accelerate reward propagation and backup mechanism. Optimality Tightening method He et al.) 2016) combines the strength of DQN with a constrained optimization approach to rapidly propagate close-by rewards. Q" (A) (Harutyunyan et al. 2016) and Retrace(A) (Munos et al. (016)) incorporate on-policy samples into off- off-policy learning targets. Noisy Net (Fortunato et al.) 2017) adds noise to the parametric model during learning to improve the exploration ability. Distributional RL (Belle- mare et al., 2017) learns the value function as a full distribution instead of a expected value. Unlike these works, we focus on combining non non- non-parametrie memory and parametric model in this paper. Thus our method is complementary to these prior extensions and can be combined with them seam- lessly.
Episodic Reinforcement Learning Our work is also related to episodic reinforcement learning. Model-free episodic control (Blundell et al. (016) uses a completely non-parametris model that keeps the best Q values of states in tabular- based memory and replays the sequence of actions that so far yielded the highest return from a given start state. At the end of each episode, the Q values in memory are updated by the greater of the existing values and the accumulated discounted returns in the current episode. In the execution stage, the agent selects actions according to a k-nearest- neighbors lookup in the memory table. Recently, several extensions have been proposed to inte- grate episodic control with parametric DQN. Neural episodic control (Pritzel et al.] 2017)) develops end-to-end episodic control by differentiable neural dictionary generate semi-tabular represen- tation as slow-changing keys and then retrieves fast-updating values by context-based lookup for action selection. To better leverage the trajectory nature of experience, ephemeral value adjustments method (Hansen et al. 2018) 8) proposes to further leverage trajectory information from replay buffer to propagate value through time and produce trajectory-cent from EVA in that we associate memory by graph, and thus we can leverage not only intra-episode but also inter-episode information. Episodic memory deep q-networks (Lin et al. 2018) distills the information of episodic memory into parametric model by adding a regularization term in the objective function and significantly boosts up the performance of DQN. Unlike these prior works, which adopt either tabular memory or semi-tabular memory, our work builds graph on memory items based on their relationship to form an associative memory.
value estimates. Our method differs
Graph Based Methods in Deep Reinforvement Learning Recently, several works have also been proposed to use graph for planning in deep reinforcement learning. [Eyeenbach et al. (2019) builds a directed graph directly on top of states in replay buffer and runs graph search to find the se- quence of waypoints, leading to many easier sub-tasks and thus improve learning efficiency. Huang (et al. (2019) abstracts state space as a small-scale map which allows it to run high-level planning using a pairwise shortest path algorithm. Unlike these prior works that use graphs for planning, our method reorganizes episodic memory by a graph to allow faster reward propagation. In addition, these graph-based models rely goal-conditioned RL (Kaelbling 1993 Schaul et al.) 2015a) and only demonstrate their performance in navigation-like like problems, while our approach is intended for general RI. settings.
3

---

Published as a conference paper at ICLR 2020
Exploration Efficient exploration is long-standing problem in reinforcement learning. Prior works have proposed guiding exploration based on criteria such as intrinsic motivation (Stadie et al. 2015), state-visitation counts (Tang et al. 2017). Thompson sampling and bootstrapped mod-
els Chapellee & Lij 2011 [Osband et al. 2016)), optimism in the face of uncertainty (Kearns & Singh 2002)) parameter-space exploration (Paapeert et al. 2017 Fortunato et al., (017). Recently, [Oh al. (2018) proposed self-imitation learning (SIL) and found that exploiting past good experiences can indirectly drive deep exploration. In their work, the agent imitates its own decisions in the past only when such decisions resulted in larger returns than expected. Like SIL. EMDQN (Lin et al. 2018) learns from episodic memory to replay past best decisions, therefore incentivizing exploration. In our method, we build associative memory through a graph, which enhances the exploitation of past good experiences and thus can indirectly encourage deeper exploration than EMDQN (Lin et al. 2018).
4 EPISODIC REINFORCEMENT LEARNING WITH ASSOCIATIVE MEMORY
4.1 ASSOCLATING EPISODIC MEMORY AS A GRAPH
Similar with previous episodic reinforcement learning, we adopt an episodic memory to maintain the historically highest values (ec(e(s), a) of cach state-action pair, where ø is embedding function and can be implemented as a random projection or variational auto-encoders (VAE) (Kingma & Welling, 2013). When receiving new state, the agent will look up in the memory and update the values of states according to the following equation,
{ max ((c(((()), at), Rs) R
(()())))a)) E QEC otherwise.
ax)
(1)
However, episodic memory stores states as unrelated items and does not make use of the relationship between these items. To fully exploit information in episodic memory, further build directed graph G on top of items in the episodic memory to form an associative memory, as shown in Figure 2 In this graph, each node corresponds to memory item that records the embedded vector of state (s)), and we leverage transitions of states to bridge the nodes. The graph is defined as,
g = (V, V (ds), E = (s- s' (s, a, 3') is stored in memory).
Given a sampled trajectory, we temporarily add each state to the graph. We add directed edges from the given state to every other previously memorized state that the successor of it under a certain action. Our associative memory reorganizes the episodic memory and connects these fragmented states that previously yielded high returns by graph. We rewrite these stored values (Fc(Ø(s), a) as Qo ((((s, a) in our graph augmented episodic memory. In addition, we adopt strategy of discarding the least recently used items when the memory is full.
4.2 PROPAGATING VALUES THROUGH ASSOCIATIVE MEMORY
Typical deep RI. algorithms sample experience tuples uniformly from the replay buffer update value function. However, the way of sampling tuples neglects the trajectory nature of an agent's experience (i.e., one tuple occurs after another, and thus information of the following state should be quickly propagated into the current state). EVA (Hansen et al.) 2018) encourages faster value propagation by introducing trajectory-centric planning (TCP) algorithm. Nonetheless, EVA only propagates value through the current episode, which we refer to as intra-episode propagation. Our insight here is that one state might appear in different trajectories, and such join points can help connect different trajectories. Therefore, we explicitly build the graph between states from different trajectories in memory and thus allows inter-episode value propagation.
Since the graph over states is complicated (e.g., not tree structure), value propagation over such graph is always slow. To accelerate the propagating process, we propagate values using the sequen- tial property. The pseudo-code of value propagation is shown in Algorithm []] Our general idea is to update the values of the graph in the reverse order of each trajectory. Specifically, when adding a new state to the memory, we record the sequential step ID t of the state the current trajectory. For memory associating, we first sort the elements in memory by their sequential step IDs in descending order and propagate the value from states with large sequential step IID to small one for several
4

---

Published as a conference paper at ICLR 2020
Experiences
Algorithm 1 Value propagation in Associative Memory
Trajectories
h: embedded vector of state, h ((s)
G + Sort nodes in graph & by sequential step ID in descending order
Key
Value
Value Propsgation
repeat
1
for m = 1...... do
_n_
Get current state-action pair (s.u)
(Sm: (m))
Get successor state embedding s' and
Join points
action using graph G.
Episodic Memory
Associative Memory
Update graph augmented memory us-
ing Eq. 3
end for until Q5 converges
Figure 2: Comparison of episodic memory and as- sociative memory.
iterations until Qç values converge. At each update, we get all successor state-action pairs (s', a') of the current one (s, a) and current reward according the graph G and apply operation cessor action a' to propagate the values to current state-action pair. Formally, our graph augmented memory is updated as follow:
Qo(o(s), + + max Qo(o(s'),a))
Since most of states the beginning similar across different episodes, our reverse order updating strategy can efficiently propagate all the values of the graph. In addition, as we show Theorem graph-based value propagation algorithm converge are shown in Appendix A
unique optimal point. The proofs
Theorem 1. Denote the Bellman backup operator in Equation 3 as B RISIX|A TR| x and
mapping Q S x A - [|SSX|AI with [S] < oo and IA) co, and define Qu+z BQ Repeated application of the operator B for our graph-based state-action value estimate Q5 converges unique optimal value Qz.
In the previous episodic reinforcement learning with graph built, only the values of exactly the same or similar states can be updated. This is because in the typical update rule of episodic memory, shown in Eq. the relationship between states has been neglected. Episodic memory does not leverage the information of edges E in our graph G. Consequently, stored values in episodic memory often violate Bellman's equation. On the contrary, associative memory allows efficient value propagation through the edges of the graph to compute the more accurate values for each state.
4.3 LEARNING WITH ASSOCIATIVE MEMORY
Building associative memory can be viewed as a way of augmenting counterfactual experiences. As shown in Figure 2 the same states might appear in N > trajectories. Vanilla episodic memory maps such states to the highest values among N trajectories, while our associative memory regards such states as join points connect different trajectories, leading to totally 2 trajectories. This is equivalent to sample more combinatorial trajectories from environments and thus can significantly improve sample efficiency RL algorithms.
Our associative memory can be applied to both the learning and control phases. In this paper, we use our associative memory as guidance for the learning of the Q function. The overall framework shown as Figure 3 Specifically, function to supervise the learning of the Q network. The Q network is learned by minimizing the following objective function:
associative memory regularization term of objective
Le ((s.a,""r)-> (1- (1+
max Qs(s', Qo(s, ((Qp(o(s),a) - Qo(s.a)) (4)
where À is the weight of the regularization term, 0 represents parameters of parametric Qenetwork. Similar with DQN (Mnih al. 2015)), also adopt a target network parameterized by 0 to stabi-

---

Published as a conference paper at ICLR 2020
Value Network
value
O bservation
Value Propagation on Graph
Guidance
I
Random Projection
Hidden Vectors
E Experienced High Value
Associative Memory
Figure 3: Overall framework ERLAM.
lize the learning process. Through the combination of parametric and non-parametric term, we can efficiently guide the learning of conventional Q-network by the fast-adjusted high values in asso- ciative memory so that the agent can rapidly latch on strategies that previously yield high returns instead of waiting for many steps of slow gradient update. The pseudo code of our method is shown in Algorithm 2
Algorithm 2 ERLAM: Episodic Reinforcement Learning with Associative Memory
D: Replay buffer
G: Graph (Associative memory)
T:: Trajectory length of e-th episode
K: Associate frequency
for Episode number =... F do
for f= 1...f do
Receive initial observation s; from environment with state embedding he c(st)
t c-greedy policy baesd on Qo (0:, a)
Take action a,, receive reward r, and next state st+1
Append (s,, 7,, $t+ to D if mod updale. == then
Sample training experiences (s, a,,, () from D Retrieve (d()(s), a) from associative memory Update parameter 0 using Eq. 4 end if end for
for f Te... do
Rs rr + Ru+ if To RS + Tr, ift T.
Append (he, ae, rr, L, RS to G if (1)
ax) $
Update Qg using Eq D if at) E G end for
e mod = 0 then
Run Algorithm to update Qg
end
end for
4.4 CONNECTION GRAPH-BAL BASED DEEP REINFORCEMENT LEARNING
When the general RL setting used in our approach degenerates to a setting of navigation-like task that is usually adopted by conliconnitional RL (Kelbling 1993 Schaul et al. 2015a), the update target of associative memory in Eq. y = max, Qg (o("(s) a' can be rewritten as,
if s' is terminal state, otherwise.
(5)
max Qo(o(s'), a')
Optimizing with the target in Eq. Blis equivalent to finding the shortest path in the graph of all states. In this case, algorithm [1 is analogous to Bellman-Foo Food algorithm (Bellman) 1958), which is proved

---

Published as a conference paper at ICLR 2020
that the value converge in limited iterations. In the context of goal-conditional RL, some graph- based methods (Huang et al. 2019 Eysenbach et al. 2019) also calculated shortest path. They focus on graph of waypoints learned by goal-conditional RL instead of memorized states that previously yield high returns. In addition, they use a parametric approach for value approximation, while we develop a non-parametric approach to improve sample efficiency of parametric RI. agent.
EXPERIMENTS
5.1 EXPERIMENT SETTING
We follow the same setting for network architecture and all hyper-parameters DQN (Mnih al. 2015). The raw images are resized to an 84 grayscale image 8t, and consecutive frames stacked into one state. The Q value network alternates convolutions and ReLUs followed by 512-unit fully connected layer and an output layer whose size is equal to the number actions in each game. Denote Conv(W, F, S) the convolutional layer with the number of filters W. kernel size F, and stride S. The convolutional layers can be indicated as Cony(32,8,44 Conv(64,4,2), and 1onv(64,3,1). We used the RMSProp algorithm (Tieleman & Hinton 2012) with learning rate = 0.00025 for gradient descent training. The discount factor y is set to 0.99 for all games. We use annealing e-greedy policies from 1.0 to 0.1 in the training stage while fixing 0.05 during evaluation.
of associative memory, we set the value of À as 0.1 and associate frequency K as 10 in the navigation domain, Monster Kong. In Atari games, we use the same settings for all games. The value of À is 0.3, and the associate frequency K is 50. The memory size is set million. We use random projection technique and project the states into vectors with the dimension of d 4. For efficient table lookup, we build a kd-tree for these low-dimension vectors.
For
(a) MonsterKongl
(b) MonsterKong2
(c) MonsterKong3
Figure 4: Maps of Monster Kong. Compared to MonsterKongl, MonsterKong2 has different goal
and MonsterKong3 has a totally different MDP.
5.2 RESULTS NAVIGATION DOMAIN
We first test our model on the navigation domain, which contributes to demonstrate the superiority of our algorithm and understand the contribution of associative memory. We video game Monster Kong from Pygame Learning Environment (PLE))Tasf) 2016) to set up the navigation experiments. In this game, the goal of the agent to approach the princess with actions up, down, left, right, jump and noop from random starting positions. The agent will win with an extra reward +1 when touching the princess and lose when hitting the thorns (silver triangles). We run ERLAM on three maps of Monster Kong (see Figure 4 and compare it with EMDQN and DQN.
As shown in Figure 5 the sample-efficiency of ERLAM significantly outperforms EMDQN and DQN. ERLAM with only 10M samples can gain higher scores than EMDQN with 80M samples on map MonsterKong2 and MonsterKong3. Then, we inspect the value estimation of Q networks and the stored values memory provide insight into our reinforcement learning results. We plot the average values states in associative memory (orange line in the bottom row of Figure 5 dur- ing the training process of ERLAM. To better understand the contribution of the value propagation

---

Published as a conference paper at ICLR 2020
Asstrgg Score For Echeade
Score Per
Muie
ERLAN
EMOOON
Model ENLAM
Nocel
DON
EHD3M
EALAN
ENDON
62
DQN
DCR
U80
lons
True
Monetentong)
M
30
Volie ext mation
Volue Estination Networt
Vilue extination
Networs
ketwork
Associative Nerrary
Ansoc after Memory Eplaodi: Memrryy
Associtive Heroory Nemory
50
Merory
Nillonn of Crammes
Hillons of Trames
MElton of Tramee
of ERLAM, EMDQN, and DQN Monster Kong. The top com- pares the average scores per episode between all models. The bottom row shows state-action value estimates by associative memory, episodic memory, and Q networks when running ERLAM. The black dash line represents the actual discounted state-action values of the best learned policy.
Figure 5: Learning
process in associative memory, we maintain a memory without value propagation (which amounts episodic memory, shown the green line in the bottom row of Figure 5 in the meanwhile and compare the state-action values of it to associative memory. As expected, the values after value propagation of associative memory grow higher, indicating associative memory provides a better non-parametric lower bound of Q value than episodic memory. Values estimated by associative memory are closer the true values of optimal policy (black dash line) and capable of guiding the learning of the Q network (blue line). We further visualize and compare the execution policies according to associative memory and episodic memory to gain a deeper understanding of their con- nections. We study case in Figure 6 We observe that the policy provided by associative memory (yellow dash line) is exactly the combination of two policies episodic memory (blue line and red line), and such combinatorial trajectory is not a real trajectory in replay buffer. This result suggests that the value propagation in associative memory enables automatic augmentation of counterfactual combinatorial trajectories, which accounts for the improvement of sample efficiency in ERLAM.
5.3 RESULTS ON ATART GAMES
To further evaluate the sample efficiency of ERLAM on a di- verse set of games, we conduct experiments on the benchmark suite of Atari games from the Arcade Learning Environment (ALE) (Bellemare et al. 2013). which offer various scenes to test RL algorithms low the training and evaluation protocol as (Mnih et al.) 2015). We train agents for 10 epochs, each containing million frames, thus 10 million frames in total. For each game, we evaluate our agent at the end of every epoch for 0.5 million frames, with each episode up to 18000 frames, and start the game with up 30 no-op actions to provide random starting positions for the agent.
different settings. We largely fol-
In our experiments, we compare ERLAM with episodic rein- forcement learning basclines, MFEC (Blundell et al., 2016). NEC (Pritzel et al. 2017), EMDQN (Lin et al. 2018). EVA (Hansen et al. 2018). as well as an ablation (i.e., DQN with no associative memory). MFEC directly uses the non-parametric episodic memory for action selection, while NEC, EMDQN, and EVA combine non paraametetiic episodic memory and a parametric Q-network. Different from previous work, ER- LAM adopts associative memory to guide the learning of a --nttwrrk.
Figure 6: Visualization of trajecto- ries. The blue line and red line vi- sualize two policies using episodic memory, while the yellow dash line represents the combinatorial trajectory by value propagation in associative memory.
8

---

Published as a conference paper at ICLR 2020
5/127%
500%
2110%
F1OM)
EMDON (40M)
400%
320%
100%
0%
Dafendorr
Domonsttua
Prost de
Assaee
Anibe
Eodweo
Alon
Roweak
Ya Yartheronge
Souquoo
Boding
Kingl
Figure 7: Comparison between ERLAM (i.e., DQN with associative memory) and EMDQN (i.e..
DQN with episodic memory) measured in improvements of scores over DQN as shown in Eq. 6 Bars indicate how much each algorithm outperforms the DQN (i.e.. DQN with no memory) agent. 0% means the performance equal DQN and higher is better.
Table 1: Performance comparisons mean and median human normalned scores in (Mnih et al. 2015). All agents are trained using 10 million frames except for EMDQN which is trained with 40
million frames.
DQN
A3C
Prior. DQN
MFEC
NEC
EVA
EMDQN(40M)
ERLAM
Mean 83.6
40.1
116.6
77.7
106.1
172.2
250.6
515.4
Median
16.0
6.9
32.3
40.9
53.3
39.2
95.5
103.5
We tested ERLAM on 25 popular and challenging Atari games. To evaluate our approach, we follow Wang et al. (2015) and measure improvement in percentage in score over the better of human and DQN agent scores for both ERLAM and EMDQN:
Score ScorepoN
max max{ (Scort ScorepoN] Score
To test the sample efficiency of our method, we limit our training data 10 million frames and compare with state-of-the-art results episodic RL (i.e., EMDQN (Lin et al., (018)). which are trained with 40 million frames and reported in their original paper. The results are shown Fig- ure 7 We found that even though our agent uses 4 times fewer training samples than EMDQN, ERLAM still outperforms EMDQN on 17 games. Overall, ERLAM significantly outperforms all baselines over most games. This suggests that associative memory efficiently guide the learning of a parametric RL agent, and our framework of combining associative memory with parametric RL can achieve significantly better sample efficiency than existing RL algorithms. For the games where ERLAM does not perform very well, we summarize the reasons as follows. First, ERLAM good at improving the sample-efficiency in near-deterministic environments but may suffer from overestimation in highly stochastic environments, such as Tutankham. Second, since representations learning is not the focus of this paper, we simply use the naive random projection as the state repre- sentations in memory. Random projection is only used for dimension reduction and does not contain useful high-level features or knowledge (e.g., objects and relations). Thus in some games with rarely revisited states, there are not enough joint nodes in our graph, and our algorithm does not perform well, such as FirhingDerby and Jamesbond. addition, We compare the overall performance (mean and median) of ERLAM with other methods in Table I which also shows that ERLAM has the best performance.
To gain better understanding of our superior performance, further plot learning curves (Figure g) on four games, which include three general good cases (Atlantis, BattleZone, StarGunner) and a bad case (BankHeist) demonstrate when associative memory works extremely well and when it is

---

Published as a conference paper at ICLR 2020
not particularly effective. In addition, plot the average values of states in memory (Figure 8 for better revealing the performance difference on game scores. Across most games, ERLAM signifi- cantly faster at learning than EMDQN and DQN, but ERLAM only has slightly better performance than EMDQN on BankHeist. The reasons lie in two folds. Firstly, there are more crossed experi- ences on Atlantis, Battle/one, StarGunner than BankHeist. Thus the first three games, the values computed by associative memory are significantly larger than those in episodic memory. Secondly, we observe that the background objects in BankHeeist have abnormally changeable appearance and complex behaviors, which are intractable for memory-based -base methods (e.g., MFEC, NEC, EMDQN, and ERLAM),, especially with a simple random projection embedding function for state feature ab- straction (we also discuss this in Conclusion Section). It also accounts for the reason why ERLAM and EMDQN have similar performance with DQN on this game.
BattleZone
Bankkeelst
40000
300C
BSLAM
AM
2000
0 2.400
LOM
LA25
78.00
14.04
33003
1440
403
10000
50300
12:03
500
of Fruntic
Mitioo Froneo
Millora fromtts
Milkem Trammi
Datteedone
StarGurnet
Baricieent
3.7m
2225
3.7
1150
26
200
123
200
200
300
52
130
120
200
250
300
50
300
224
300
208
306
50
305
224 206
304
305
Figure 8: Examples of learning curves 10 million frames compared with EMDQN and DQN. The top row shows average scores per episode and the bottom row shows average values of states in memory. One Plot Number is equivalent to about 30K frames. Note that O indicates the first million.
We also add experiments to verify our superior performance benefits from associative memory rather than representations (e.g., random projection). As shown in Appendix Figure 9 DQN with only random projections as inputs has much worse performance than ERLAM and the vanilla DQN, which suggests that is associative memory that matters.
CONCLUSION
In this paper, we propose biologically inspired sample efficient reinforcement learning frame- work, called Episodic Reinforcement Learning with Associative Memory (ERLAM), Our method explicitly organizes memorized states as a graph. We develop an efficient reverse-trajectory prop- agation strategy to allow the values of new experiences to propagate to all memory items through the graph rapidly. Experiments in the navigation domain and Atari games demonstrate that our pro- posed framework can significantly improve the sample efficiency of current reinforcement learning algorithms.
In the future, there are some interesting research directions that can be pursued within our proposed framework. Firstly, this paper, following the work of Blundell et al. (2016) and Lin et al. (2018), our state embedding function & is implemented advanced representation learning approaches that can capture useful features into our framework to support more efficient memory retrieval and further boost up performance. Secondly, existing episodic reinforcement learning algorithms mainly focus on value-based methods. It will be an in- teresting future work to extend episodic memory to policy gradient methods. Thirdly, instantiate our associative memory in the learning phase in this paper. However, associative memory can also be used in explicit episodic control enhance exploitation further. Fourthly, the current stage, ERLAM, as a kind of episodic RL approach, is only good at improving sample-efficiency in near- deterministic environments. To deal with completely stochastic environments, our model can be potentially extended by storing the distribution of Q values (Bellemare et al. 2017 Dabney et al.) 2018) instead of the maximum Q value in the associative memory.
random projection. It is possible to incorporate
10

---

Published as a conference paper at ICLR 2020
REFERENCES
John R Anderson and Gordon H Bower. Human associative memory. Psychology press, 2014.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling, The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. Proceedings of the 34th International Conference on Machine Learming- Volume 70, pp. JMLR. org. 2017.
Richard Bellman. On routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Richard Bellman. Dynamic programming. Science, 153(3731))34-37,, 1966.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:1606.04440 (66666040400, 2016.
Mathew Botvinick, Sam Ritter, Jane X Wang. Zeb Kurth-Nelson, Charles Blundell, and Demis Hassabis. Reinforcement learning, fast and slow. Trends cognitive sciences, 2019.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pp. 2249-2257, 2011.
Will Dabney, Georg Ostrovski. David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. arXiv preprint 1806.0688360033 2018.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridg- ing planning and reinforcement learning. arXiv preprint arXiv: (00:::996.000000 05253, 2019.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: / 706. 10295, 2017.
Itzhak Gilboa and David Schmeidler. Case-hased decision theory. The Quarterly Journal of Eco- nomics, 110(3):005-639 1995.
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, André Barreto, and Charles Blundell. Fast deep reinforcement learning using online adjustments from the past. In Advances in Neural In- formation Processing Systems, pp. 10567-10577, 2018
Anna Harutyunyan, Mare Bellemare, Tom Stepleton, and Rémi Munos. Q(A) with off-policy corrections. In International Conference Algorithmic Learning Theory, pp. 305-320. Springer, 2016.
Frank He, Yang Liu, Alexander G Schwing, and Jian Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. arXiv preprint
2016.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching, arXiv preprint arXiv: 090779988555555 2019.
Leslie Pack Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In Pro- ceedings of the tenth international conference on machine learning. volume 951, pp. 167-173, 1993.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2-3):209-232 2002.
Diederik Kingma and Max Welling. 1312:6 2013.
Auto-encoding variational bayes.
arXiv preprint
11

---

Published as a conference paper at ICLR 2020
Teuvo Kohonen. Self-organization and associative memory, volume 8. Springer Science & Business Media, 2012.
Máté Lengyel and Peter Dayan. Hippocampal contributions to control: the third way. In Advances in neural information processing systems, pp. 889-896, 2008
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Brez, Yuval Tassa,
David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. Interna- tional Conference on Learning Representations, 2016.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. 07600, 2018.
arXiv preprint
David Marr, David Willshaw, and Bruce McNaughton. Simple memory: theory for archicortex.
In From the Retina to the Neocortex, pp. 59-128. Springer, 1991.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 5 518(7540)529,, 2015.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1062-1062, 2016.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. arXiv preprint arXiv:1806.05633 2018.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 4026-4034, 2016.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. arXiv preprint arXiv: /706:0070000000 0095, 2017.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In Proceedings of the 34th International Conference Machine Learning-Volan Volume 70, pp. 2827-2836. JMLR. org, 2017.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International Conference on Machine Learning, pp. 1312-1320, 2015a.
Tom Schaul, John Quan, Joannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv: 1ete::1111..02.... 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv: (5005550008000 2015.
Robert J Sutherland and Jerry W Rudy. Configural association theory: The role of the hippocampal formation in learning, memory, and amnesia. Psychobiology. 17(2):129-144, 1989.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2011.
12

---

Published as a conference paper at ICLR 2020
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schul- man, Filip DeTurck, and Pieter Abbeel. exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pp. 2753- 2762, 2017.
Norman Tasfi. Pygame learning environment.
https://ggttubb.commmtass
LyGame-Loarainn-BBaLLooeeeet 2016.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):66
31, 2012.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Thirtieth AAAI conference artificial intelligence, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 1tr.Xi:1111.06555 2015.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-2 1992.
13

---

Published as a conference paper at ICLR 2020
A
THEORETICAL CONVERGENCE
Proof.
Note that our graph-based value propagation is similar to the proof of value iteration (Bell-
man 1966
Bertsekas al. 1995 Sutton & Barto 2011). For any estimate of our graph-based
action-value function Qg
BQ R(x,a) + max a'EA e'ES
Σ
where (s'ss, defines transition probability given graph G. For any action-value function esti- mates 23. Lg.
[BQ a) - (()(
Σ (o(
Po(''18, ())
=7 max d'EA e'ES
max d'EA
e'ES
Σ Pc(5)1,,)0(((11.0
E Po(s'|s, Q3 N'ES
S max a'EA
s'ES
Σ
Po a) QQ)((, (3(6''''))
-y max a'EA e'ES
SY max sEA.
(Q)(s,a) - a))
So the contraction property of Bellman operator holds:
(B (s) max sES.
-(((s,))Q(((,aa)) (s,
max
sES,aEA
For the fixed point Qū. we have:
max [BQo(s,a) (&] SS max =ES,aEA
(0((,,)) Q}(s, = Q - -
(8)
sES,aEA
Therefore, prove that our graph-based based value propagation algorithm can converge to unique opti- mal value.
14

---

Published as a conference paper at ICLR 2020
B RAw SCORES ON ATARI GAMES
Table Raw scores on Atari games at 10 million frames. All agents are trained using million
frames except for EMDQN which is trained with 40 million frames.
DQN
A3C
Prior
MFEC
NEC
EVA
EMDON(GOM))
ERLAM
Alien
634,80
415.50
800.50
1717.70
3460.60
1007.93
1662.00
2070.85
Amiddar
126.80
96.30
99.10
370.90
811.30
231.19
374.10
980.47
Assault
1489.50
720.80
1339.90
510.20
599,90
550.77
2566.80 80
3230.18
Atlantis
14210.50
36383.00
12579. 10
95499.44 40
51208.00 00
180367 20
200953.30
389530.00
BankHeist
29.30
343.30
4022.45
92
BatileZone
6961.00
2354.20
13500.00
19053.60
13345.50
14000.47
28,300.00
33095.24
BeamRider
3741.70
749.60
5980
Boxing
31.30
2,50
64,70
10.70
72.80
58.43
89.30
87.77
ChupperComanamd
827.20
1036.70
1426.50
3075.60
5070.30
1612.93
3106.77
4172.83
CrazyClimher
66061
70103.50
76574,
9892.20
34344.00
90656.27
107038.70
106538.71
Defender
2877,90
4596.00
3486.40
10052,80
6126.10
2890.44
14408.00
705833..3
DemonAttack
5541.90
11056.75
Enduro
364.90
0.00
1125.80
0.00
1,40
1 1106.35
659.00
912.73
FirhhngDerhy
.48.20
Frostbite
339.10
218.90
1.3.00
925,10
2747.40
1005,44
596.30 30
3193.83
Hero
1050.70
45598.20
5164.50
14767.70
16265.30
1
7247. 80
13615.00
Jamesbond
65590
31.50
203.80 80
244,70
376.80
252.
586.70
518.42
Krull
6015510
3627 60
6700.70
4555 20
5179.20
4030.04
7798.30
7755.80
Musterr
21456.20
12906.50
Riverraid
3144,90
2.112.60
4871 80
4195 .90000
5498. 10
4026. 74
7728. 30
8138.66
ReadRunner
7285.40
60
12661.40
28194
27856.00
Robotank
14,60
2.40
8.50
7.30
11,10
15.13
5,30
25.44
Senquest
618.70
514.10
1192.20
71 1,1660
1015.30 30
1714.15
4235.990
2693.96
StarGunner
604-80
613.60
11:31.0
14843,90
1171.40
2006.22
23933.30
9432.99
Tulankham
148.70
108.30
194.00
86.
121.60
171.33
148.00
146. 94
YarsRevenge
7614,10
14259.26
Allantis
SattiaZooe
StarGuuneer
Bannkiaes
2013
2:000
23000
30009
000
20000
13000
35.00
303
20006
Figure 9: Learning curves on 10 million frames compared with ERLAM, DQN with random project and vanilla DQN.
15


Reviews:
[{"review_id": "rJeP9zTptr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new method for organizing episodic memory in with deep Q-networks. It organizes the memory as a graph in which nodes are internal representations of observed states and edges link state transitions. Additionally, nodes from different episodes are merged into a single node if they represent the same state, allowing for inter-episode value propagation of stored rewards. The authors experimentally evaluate the method against reasonable baselines and show improved performance in the majority of tasks.\n\nWhile the proposed method seemingly leads to better performance, the analysis of the results appears superficial. First, it lacks theoretical rigor to explain why the proposed propagation mechanism works, for instance, a proof of the optimal substructure in Eq. (3) would be helpful. While I see the authors mentioned previous work which do not have optimal substructures and mention this for the case of navigation-like tasks, the matter is not discussed and unclear in other scenarios. \n\nThis in itself would not be much of an issue if the experiments highlighted advantages and limitations of the proposed method, but that is not the case. For instance, per-task comparisons to EVA (mentioned in the paper) could indicate how useful inter-episode value propagation was in each task.  Table 1 mentions EVA, but only on aggregated results, thus not providing insight into this. Furthermore, the experiments selected to be detailed in Figure 4 are, in my opinion, suboptimal choices, as the worst-performing of the selected tasks is still better than the baselines. It would be more insightful to also compare those whose performance is close to the baselines, such as the Boxing environment, and significantly worse than baselines, such as the StarGunner environment (as shown in Figure 3). With those issues in mind, my conclusion is to recommend to reject the paper in the current state.\n\nMinor comments:\n- Thoroughly review the writing and grammar, the text in its current state needs significant improvement in this regard\n- Equation references missing parentheses\n- Introduction, 1st paragraph, second sentence is incomplete\n- Algorithm 2: tuples taken from/appended to sets G and D are not consistent (cf. lines 11 and 13)\n- Figure 3: The large amount of bars in the plot would benefit from horizontal lines across the plot for each tick on the y axis\n- Table 1: caption before the table; should also state the meaning of numbers (percentage or normalized score, calculated from what?)\n- Figure 4: labels (all text except plot titles) are impossible to read in print\n- Section 3 could be placed before Section 2, laying the mathematical framework, and then following the discussion with related work\n- There is redundant content in Sections 2 and 3\n\n\n----\n\nI am happy with the authors response and changed the score accordingly", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgePooptS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to combine DQN with a nonparametric estimate of the optimal Q function based on the graph of all observed transitions in the buffer. Specifically, they use the nonparametric estimate as a regularizer in the DQN loss. They show that this regularizer facilitates learning, and compare to other nonparametric approaches. I found the paper easy to read. The ideas are intuitive and seem to work.\n\nIt would be great to have more experiments providing insight into when the associative memory estimate works and when it doesn't. Since at the end of the day both DQN and the non-parametric estimate use the same data, there's no fundamental reason why the later should contain more information. Is it possible that more aggressive training of DQN would eliminate the need for the nonparametric estimate? Why would I expect the nonparametric estimate based on random projections to generalize better to new states than DQN? What would be the performance of DQN with only the random projections as inputs? I believe including experiments probing in this direction would make the paper better.\n\n-------------------------------------------------------------------------------------------------------------------\nThanks for your response and the additional experiments. I still find the paper interesting and hence keeping my score as is.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "B1eG6-ZzcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Episode Reinforcement Learning with Associative Memory (ERLAM), which maintains a graph based on the state transitions (i.e. nodes correspond to states, and edges correspond to transitions) and propagates the values through the edges in the graph in the reverse order of each trajectory. The learned associative memory is then used for the regularization loss for training Q-network. Experimental results show that ERLAM significantly improves the sample efficiency in Atari benchmarks.\n\n- Overall, the paper is well-motivated and easy to follow. The experimental results demonstrate that the proposed method is promising. For the states that are already visited, instead of simply replacing the value to the better return (i.e. Eq. (1)), ERLAM makes join points to connect different trajectories, which enables further improvement via Bellman optimality-like backup (i.e. Eq. (3)).\n\n- Can ERLAM deal with a stochastic environment? It seems that ERLAM would more likely to over-estimate the values for the state than the existing episodic RL algorithms.\n\n- In order to make join points, it should be possible to determine whether two features of states are equal or not. How was this determined? It seems rare to reach the 'exact' same feature in Atari domains (i.e. 4 consecutive frames should be equal).\n\n- In Algorithm 2, the pseudo-code is somewhat confusing in that R_t is appended to G before the episode ends.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission tackles the problem of data efficiency in RL by building a graph on top of the replay memory and propagate values based on this representation of states and transitions. The method is evaluated on Atari games and is shown to outperform other episodic RL methods.

The reviews were mixed initially but have been brought up by the revisions to the paper and the authors' rebuttal. In particular, there was a concern about theoretical support and the authors added a proof of convergence. They have also added additional experiments and explanations. Given the positive reviews and discussion, the recommendation is to accept this paper.
Decision: Accept (Poster)