Replay Memory as An Empirical MDP: Combining Conservative Estimation with Experience Replay
Authors: Hongming Zhang
Chenjun Xiao
Han Wang
Jun Jin
bo xu
Martin Müller
Venue: ICLR 2023 poster (2023)

Abstract: Experience replay, which stores transitions in a replay memory for repeated use, plays an important role of improving sample efficiency in reinforcement learning. Existing techniques such as reweighted sampling, episodic learning and reverse sweep update further process the information in the replay memory to make experience replay more efficient. In this work, we further exploit the information in the replay memory by treating it as an empirical \emph{Replay Memory MDP (RM-MDP)}. By solving it with dynamic programming, we learn a conservative value estimate that \emph{only} considers transitions observed in the replay memory. Both value and policy regularizers based on this conservative estimate are developed and integrated with model-free learning algorithms. We design the metric \textit{memory density} to measure the quality of RM-MDP. Our empirical studies quantitatively find a strong correlation between performance improvement and memory density. Our method combines \emph{Conservative Estimation with Experience Replay (CEER)}, improving sample efficiency by a large margin, especially when the memory density is high. Even when the memory density is low, such a conservative estimate can still help to avoid suicidal actions and thereby improve performance.

Published as a conference paper at ICLR 2023
REPLAY MEMORY AS AN EMPIRICAL MDP: COMBIN- ING CONSERVATIVE ESTIMATION WITH EXPERIENCE REPLAY
Hongming Z Chenjun Xiao??, Han Wang', Jun Jin', Bo Xu², Martin Müller! 'Department of Computing Science, University of Alberta
HHuawei Noah's s Ark Lab IInstitute of Automation, Chinese Academy of Sciences (hongmin2, chenjun, han8, fmmulllere (wwerreuallbtat.coo jun. jinlininnuee @haawei. com, box.@ia.ccommmcccoo aca
ABSTRACT
Experience replay, which stores transitions in a replay memory for repeated use, plays an important role of improving sample efficiency in reinforcement learning. Existing techniques such as reweighted sampling, episodic learning and reverse sweep update process the information in the replay memory to make experience replay more efficient. In this work, we further exploit the information in the re- play memory by treating it empirical Replay Memory MDP (RM-MDP). By solving it with dynamic programming, we learn conservative value estimate that only considers transitions observed the replay memory. Both value and policy regularizers based on this conservative estimate are developed and integrated with model-free learning algorithms. We design the memory density metric to mea- sure the quality of RM-MDP. Our empirical studies quantitatively find a strong correlation between performance improvement and memory density. Our method combines Conservative Estimation with Experience Replay (CEER), improving sample efficiency by a large margin, especially when the memory density is high. Even when the memory density is low, such conservative estimate can still help to avoid suicidal actions and thereby improve performance.
INTRODUCTION
Improving sample efficiency is an essential challenge for deep reinforcement learning (DRL). Expe- rience replay (Lin, 1992) stores transitions in replay memory and reuses them multiple times. This technique plays important role for the success of DRL algorithms, such as Deep Q-Networks (DQN) (Mnih et al., 2015). Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015; Haarnoja et al., 2018) and AlphaGo (Silver et al., 2016; 2017). DRL algorithms optimizers to incrementally update parameters. The learning requires several orders magnitude more training samples than human learning the same task. To speed up learning, many researchers focus on how to better process information in the replay memory before updating networks.
gradient- based
One research direction is measure the relative importance of transitions and sample them with different priorities. Criteria for measuring the importance include temporal-difference (TD) error (Schaul al., 2016). the "age" (Fedus et al., 2020) of transitions (Zhang & Sutton, 2017: Novati & Koumoutsakos, 2019; Sun et al., 2020; Wang et al., 2020: Sinha et al., 2022), errors of target values (Kumar al., 2020a), and coverage of the sample space (Oh et al., 2021a; Pan et al., 2022). Another direction is to analyze the trait of transitions. For example, learning should start in back- ward manner that allows sparse and delayed rewards to propagate faster (Lee et al., 2019); the best episodic experiences can be memorized and supervise the agent during learning (Lin et al., 2018 8); similar episodes may latch on and provide more information for update (Zhu et al., 2020; Hong et al., 2022; Jiang et al., 2022).
WWrk done while intern Huawei Noah's Ark Lab.

---

Published as a conference paper at ICLR 2023
Can we further improve the use of the replay memory? In our work, we consider the Replay Memory as an empirical MDP, called RM-MDP. Solving RM-MDP provides us an estimate that considers all existing transitions in the replay memory together, not just single samples trajectories at time. The estimate is conservative because some actions may not be contained in the memory at all. We propose to use this conservative estimate Q from RM-MDP to regularize the learning of the Q network on the original MDP. We design two regularizers, value regularizer and policy regularizer. The value regularizer computes the target value by combining the estimates from Q and Q network. For the policy regularizer, we derive Boltzmann policies from the Q and Q network, and constrain the distance between the two policies using Kullback-Leibler (KL) divergence.
Our contribution is four-fold: (1) We consider the replay memory as an empirical Replay Memory MDP (RM-MDP) and obtain a conservative estimate by solving this empirical MDP. The MDP is non-stationary and is updated efficiently by sampling. (2) We design value and policy regularizers based on the Conservative Estimate, and combine them with Experience Replay (CEER) to regular- ize the learning of DQN. (3) We introduce memory density as a measure of the quality of RM-MDP, and empirically find strong correlation between the performance improvement and memory den- sity. The relationship gives us a clear indication of when our method will help. (4) Experiments on Sokoban (Schrader, 2018), 8), MiniGrid (Chevalier-Boiseer et al., 2018) and MinAtar (Young & Tian, 2019) environments show that our method improves sample efficiency by a large margin especially when the memory density is high. We also show that even if the memory density is low, the con- servative estimate can help to avoid suicidal actions and still benefit the learning, and our method is effective environments with sparse and delayed rewards.
2 RELATED WORK
Reweighted Experience Replay. Since DQN (Mnih et al., 2015) replays experiences uniformly to update Q network and achieves human-level performance Atari games, improving experience replay (Lin, 1992) became an active direction. Prioritized Experience Replay (PER) (Schaul et al., 2016) is the first and most famous improvement. It replays important transitions as measured by TD errors more frequently. Oh et al. (2021b) additionally learn an environment model and prioritize the experiences with both high model estimation errors and TD errors. Saglam et al. (2022) show that for actor-critic algorithms in continuous control, actor networks should be trained with low TD error transitions. Sampling recent transitions another popular metric (Novati & Koumoutsakos, 2019; Sun et al., 2020; Wang et al., 2020; Cicek et al., 2021). These authors argue that old transitions will hurt the update since the current policy is much different from previous ones. Distribution Cor- rection (DisCor) (Kumar et al., 2020a) reweights transitions inversely proportional to the estimated errors in target values. For these rule-based sampling strategies, Fujimoto et al. (2020) show that correcting the loss function is equivalent to non-uniform sampling, which provides new direction for experience replay. Besides, learning a replay policy (Zha et al., 2019; Oh et al., 2021a) is also a feasible approach. These methods alternately learn replay policy and target policy.
Experience Replay with Episodic RL. Episodic RL (Blundell et al., 2016; Pritzel et al., 2017; Hansen et al., 2018) uses separate lookup table to memorize the best experiences Episodic Memory Deep Q-Networks (EMDQN) (L.in et al., 2018) uses the maximum return from episodic memory as target value. This supervised learning compensates for the slow learning result- ing from single step reward updates. Episodic Reinforcement Learning with Associative Memory (ERLAM) (Zhu et al., 2020) builds graph on top of state transitions and uses as early guidance. The RM-MDP construction in our work is somewhat similar, but more general. We construct the MDP and solve it through modified dynamic programming scheme. We have no constraint on the MDP, so it can be stochastic and can have cycles.
encountered.
Experience Replay with Reverse Update. The work by Dai Hansen (2007); Goyal et al. (2019) focuses on the sequential character of trajectories. They argue that a state's correct Q value is preconditioned on the accurate successor states' Q values. Episodic Backward Update (EBU) (Lee et al., 2019) samples whole episode and successively propagates the value of state to its previous states. Topological Experience Replay (TER) (Hong et al., 2022) builds a graph to remember all the predecessors of each state, and performs updates from terminal states by successively moving backward via breadth- first search. Our method propagates rewards when solving RM-MDP, thereby the sequential character of trajectories is considered in the regularizers.
2

---

Published as a conference paper at ICLR 2023
Model-based RL. A replay memory can be considered as non-parametric model (Hasselt al., 2019). The main difference is that the replay memory only contains true experience, while a model can generate imaginary transitions. Dyna (Sutton, 1991; Sutton et al., 2012) uses model gen- erate imaginary transitions and updates the agent with both real and imaginary transitions. Model- based value expansion (MVE) (Feinberg al., 2018; Buckman et al., 201 8; Xiao et al., 2019) uses model to simulate on-policy rollouts and provides higher-quality target values. The AlphaGo and Al- phaZero algorithms alternately optimize reactive (neural network) and non-reactive (tree search) policy (Silver et al., 2016; 2017; 2018; Sun et al., 2018) 80. World Models (Ha & Schmidhuber, 2018) and Dreamer (Hafner et al., 2020; Hafner et al., 2021) focus on how to learn a high-quality model. Model-based RL has a fundamental appeal since it can generate imaginary transitions and improve sample efficiency. The challenges are that hard to learn a good model, and the wall-clock training time increases dramatically due to model learning and model planning.
3 BACKGROUND
Markov Decision Process (MDP). The interaction of an agent with its environment can be modeled as MDP M = (S, A, R. P. Po: 7). S is the state space, AA is the action space, P A x S [0, 1] is the environment transition dynamics, R: SxAxS + IR is the reward function,
S + RR the initial state distribution and y E (0, i) is the discount factor. The goal of the agent learn an optimal policy that maximizes the expected discounted sum of rewards E| 7'r:]. Q-learning classic algorithm to learn the optimal policy. It learns the Q function with Bellman optimality equation (Bellman, 2021), Q* a) Eir 7 max,' Q"(s', a')]. An optimal policy is then derived by taking an action with maximum Q value at each state. DQN (Mnih et al., 2015) scales up from tabular Q-learning by using deep neural networks and experience replay (Lin, 1992).
Solving An Empirical MDP. We treat the replay memory M an empirical Replay Memory MDP (RM-MDP), M (S, A. R, P, po: 7). All components are the same as M except P. P is the empirical transition dynamics summarized from the transitions in Al collected by behavior policy Let Q be the action value function of the RM-MDP. Solving RM-MDP equals to solving the following equation:
3. We set p(s, a, s') if ((a s)
(s. a) F. P s.0) [r + max a':s(a')=">00
(s(s'aa)))
where Q' is the optimal action value function for RM-MDP'. This is a fundamental problem in offline/batch reinforcement learning (Lange et al., 2012). The learning goal is to maximize the cumulative reward limited to static dataset. This returns conservative policy with best possi- ble performance. The constraint avoids distributional shift caused by taking actions outside of the dataset when estimating target values. Though the replay memory in online learning is usually a time-changing first in first out queue, at a specific time step, the memory can be considered static dataset that contains finite number of transitions. Thus, solving RM-MDP is similar to offline RL setting that solves empirical MDP and results in a conservative estimate (Levine al., 2020).
4 METHOD
We regularize online RL agents with the conservative estimation from replay memory. Figure shows the overview of our method. We first construct the RM-MDP with transitions in the replay memory. We then get a conservative estimate by solving RM-MDP. Finally, we design value and policy regularizers based on the estimate to help online learning. In Section 4.1, we describe the construction of the RM-MDP by building the replay memory graph. In Section 4.2, we describe solving the RM-MDP. In Section 4.3, we describe how we design the value and policy regularizers and summarize the whole method.
4.1 BUILDING RM-MDP
The replay memory changes overtime during online learning, and offline DRL methods usually take tens of thousands of gradient steps to extract good policy (Fujimoto al., 2019; Kumar et al.,
We use Q and Q to denote the estimates from the network and RM-MDP respectively.
3

---

Published as a conference paper at ICLR 2023
Env
Update ?
(s,a,r,s))
as,a,r,s', q.
State in memory RM-MDP M
Agent
Update network
Figure 1:
An overview of our method. Transitions from the interaction with environment constructs RM- MDP, which part of the environment MDP. Green circles denote states in the memory. The solid lines denote existing transitions, and dashed lines denote transitions not in the memory. We obtain value and policy estimates from RM-MDP, which will be provided regularize the learning.
2020b; Kostrikov et al., 2022). To derive a quick and stable estimation from RM-MDP, we focus on constructing the replay memory graph, which can be solved with tabular methods.
Data structure. As introduced in Section 3, M is the replay memory and M (S,A, is the corresponding RM-MDP. obtain M, we construct the replay memory as directed graph G:
g = (V, E), V = {d(s)](s, ()s,)))), = {ō(s) 4 ((s'))((a r, (s, 8')))
(2)
In the graph G. denotes the of vertices, E denotes the set of edges. V contains states s and action value estimation Q(s,)) -). an embedding function to map the high-dimensional states to low-dimensional representation for fast query (keys in the graph G). We store vertices in a dictionary with ái as a hashing function serving as keys, thus we can retrieve state in O(1) time. Q(x .) only contains values for actions that were taken by behavior policy 33, i.e., a 3(aas) > 0. For each edge E, store actions rewards and visit counts [(s,, a, s'). These statistics similar to those in AlphaGo (Silver et al., 2016; 2017; 2018), which are stored a tree structure and used for Monte Carlo Tree Search (MCTS) (Kocsis & Szepesvári, 2006; Browne et al., 2012). Each edge is identified by the tuple (Ø(s), a, ((s'),, thus we can also query the statistics on an edge in O(1) time. Our graph has no limitation the structure of the RM-MDP. The graph can have cycles and the environment dynamics can be stochastic. We estimate P for transition (s, a, s') with visit counts:
ass,a,s)
a() Σ. N(s,,,s')
If state an action has never been tried N(s,a) a)
define p(5'ls, for all s'
Update rule. Besides the graph structure, the memory also maintains the same features as the replay memory used in DQN. It stores the most recent experiences with fixed memory size. Since all these statistics are scalars, the memory consumption is mostly on account of states in vertices V. We count the memory size by the number of vertices. When a new transition (s, a, s') comes, we first check if ((s) exists in the graph. If not, we create a new vertex and edge and initialize (s,,a) O, N(s, a, 8') = 1. Otherwise, if (0s)) already exists, we merge the same states into one node and update the visit count N(s, a, s') = ((s, a, s') + 1. Different trajectories that have the same state representation will intersect. If there is intersection between trajectories, the graph degenerates to separate connected components equivalent to the replay memory used in DQN.
4.2 SOLVING RM-MDP
With the graph G, we have all elements of RM-MDP M. We use value iteration update Q:
((s.a) + Σ ((s''s, ('))('
max Q(s', aa)],
(4)
where f is the empirical dynamics computed by equation 3, 7 is the discount factor, Q(s'.-) and be queried from corresponding vertex and edge in O(1) time. During the learning, each environment interaction step will add a new transition to the memory, which makes RM-MDP non- stationary. Instead of updating all transitions of the new RM-MDP, we only perform the update (4)
4

---

Published as a conference paper at ICLR 2023
on sampled batch of transitions. In DQN, the Q function is updated with sampling batch every four environmental steps (Mnih et al., 2015). We use the same batch to update Q. Besides, when an episode ends, update Q along the episode in reversed order. This is similar EBU (Lee et al., 2019) but we do the backward update for the memory rather than for Q networks. The sampling-base update and episode-based update allow sparse and delayed rewards propagate quickly through all transitions of related trajectories. There is no extra computation for sampling, and the time consumption for equation 4 minor compared the update cost of Q networks.
4.3 CEER: REGULARIZING DEEP Q NETWORKS BY RM-MDP
With the conservative estimation from replay memory, we design value and policy regularizers.
Value regularizer. DQN is known to suffer from substantial overestimation some games due to the combination of deep neural networks with the maximization step in Bellman optimality equa- tion (Van Hasselt et al., 2016). Since Q from the RM-MDP is conservative estimation and is estimated in a tabular manner without function approximation, is not so prone to overestimation. It can be a good complement compute better target Q value. Let q(8, a) = =r+g max, Q , aa) be the target Q value estimated by Q network for state-action pair (s, a), and q(8, a) computed by equation 4 be the value estimated from RM-MDP. The target value for state action pair (s, a) is:
Quarger (5,a) a) = (1 - a) a) + ag(s, a),
(5)
where a E [0, 1] a parameter. Using mean square error with sample batch D, our TD loss is:
LTD
Σ
(Mtargar a) - ((s,a))²
D
(s.0)ED
Policy regularizer. Since the purpose of learning is to derive an optimal policy from the Q network, we design policy regularizer to accelerate policy learning. Let (s) = softmax,,..
be the Boltzmann policy derived from Q at state s, where is the softmax temperature. Action is constrained by behavior policy 8, thus policy क is conservative. Similarly, policy T(x)
()) is derived from the Q network. We regularize policy π by minimizing the Bailbacck-Libble. (KL) divergence between ग and n:
Epolicy
Σ SED
(f(( (s))..
D
where À >> is a parameter, and D batch of experiences. The intuition for this policy regularizer is that because policy î is derived from a conservative estimation, it lower bounds the performance of policy æ. If the RM-MDP M is good approximation of a local part of the environment MDP M, then approximates the optimal policy in M and thereby accelerate the learning. Even the approximation is not good, the conservative á can still help by avoiding suicidal actions in some games and thereby improves the performance. Combining the two regularizers, the update loss is:
L = LTD + Lopticy-
The pseudo-code for CEER is shown in Algorithm 1.
EXPERIMENTS
In this section, we aim answer the following questions: (1) Does conservative estimation-based experience replay (CEER) speed up learning? (2) In which circumstances will CEER help? (3) What are the effects of value and policy regularizers? How does CEER compare to learning from Q
in supervised manner similar to EMDQN (Lin et al., 2018) 8) and ERLAM (Zhu et al., 2022)?
5.1 SETUP
Environments. We evaluate method on Sokoban (Schrader, 2018), MiniGrid (Chevalier- Boisvert et al., 2018) and MinAtar (Young & Tian, 2019) based on OpenAl Gym interface (Brock- man et al., 2016). Sokoban is Japanese for warehouse keeper and traditional puzzle. The player
5

---

Published as a conference paper at ICLR 2023
Algorithm Combine Conservative Estimation with Experience Replay (CEER)
1: Initialize replay memory M with fixed memory size
2: Initialize action value network Q with weights 0, target network Q with weights <- 0
3: Initialize the environment 8o Env
4: for environments step t= to 7" do
5: Select an action at by e-greedy with respect Q(s..+0)
6: Execute in Env and get Te: St+1
7: Store the transition (st, de, Tr, 81+11 in M and update visit count N de, 81+1)
8:
Sample random minibatch of transitions from M
9: Update (8t; 0e) via equation and store the result M
10: Update (st;; Og;; 0) by minimizing & via equation 8
11: Update 0 every C steps
12:
end for
has to push all boxes in room the storage locations without getting blocked. MiniGrid im- plements many tasks in the grid world environment. Most of the games are designed with sparse rewards. MinAtar is image-based miniaturized version of Atari games (Bellemare et al., 2013) which maintains the mechanics of the original games as much as possible and is much faster. For Sokoban and MiniGrid. the map is randomly generated at each episode. For MinAtar, objects are randomly generated at different time steps. So all these environments require the policy to generalize across different configurations. More details about these environments can be found in Appendix B.
Baselines and Implementation Details. We compare our method with DQN (Mnih et al., 2015), PER (Schaul al., 2016), EBU (Lee al., 2019). DisCor (Kumar al., 2020a) and TER (Hong et al., 2022). We use the same network for all algorithms. The architecture is the same in the Mi- nAtar baselines. The network contains a convolutional layer with 163 x convolutions with stride 1, and fully connected hidden layer with 128 units. We search the learning rates for baselines among L.e-,,,c-4.1e-4433e.
and report the best performance. For our method, we fix the learn- ing rate to le-4 and search our particular parameters. Value regularizer weight and policy regularizer weight À E (0,0.01,1,2.55) All other common parameters are set the same as shown in Appendix A Table 2. We run each experiment with 20 different random seeds and show the mean score and the standard error with solid line and shaded area. Each run consists of million steps of interaction with the environment. The performance is evaluated by running 100 episodes after every 100k environmental steps. More details can be found in Appendix A.
(0.0.2.0.5.00..)
5.2 TOY EXAMPLE
We first give a toy example to show the benefit of regularizing DQN with conservative estimation. We consider Cliffworld (Sutton & Barto, 2018) shown in Figure 5 Appendix B. There 48 states and 4 actions. The goal to reach state G starting from state S. The reward of reaching is drop- ping to the cliff gives -1, otherwise is
1.0
CEER
I
learrnngg
DON Only_valus
Mean Score
Q Value Emror
Only_polliy
3,6
-02
This case can be solved by tabular method such as Q-learning easily, but with networks such as DQN, learning is more difficult because of incremen- tal update and parameter interference.
-0.4
75c
30c
7%
3.0
25k
10
100
Steps
Stops
(a) Learning curves.
(b) Q value error.
Figure 2: (a) The learning curve of each algorithm. CEER achieves comparable learning speed with Q-learnin. The pol- icy regularizer contributes error compared with optimal Q value during learning. The value regularizer contributes more reducing the value error.
policy learning. (b) The value
We show the learning curves of mean score, and the mean square error of the Q value in Figure? 2. Onluu and Only policy denote the methods with only one regularizer. CEER uses both regularizers. DQN uses regularizer and Q-learning is tabular method without network. DON struggles and cannot find

---

Published as a conference paper at ICLR 2023
the goal state within 100k interactions. With the two regularizers, the performance improves lot and the learning speed is on par with Q-learning The performance of Only_Ovllaa _value and Only-pa -policy demonstrate that each regularizer plays important and different role. The value regularizer helps learn the optimal value faster. The policy regularizer helps the policy learning, while the Q value loss decreases slower. In this simple case, the replay memory contains almost all the transitions so that we can consider M ~ M, i.e., the RM-MDP is almost the same the environment MDP, and the conservative policy is perfect approximation of the optimal policy for M. Next, we show that the two regularizers still help in more complex environments, even if M is much smaller than M.
5.3 OVERALL PERFORMANCE
We show the final scores on Sokoban, MiniGrid and MinAtar in Table 1. Our method achieves the best performance in most of the environments, especially in hard environments with sparse and de- layed rewards. We evaluate our method on seven Sokoban environments with increasing difficulty. For example, Push-5x5-1 is problem with 5x5 map and box to push. In easy environments such as Push-5x5-1, almost all methods achieve the best performance. When difficulty increases, only method can handle these environments such Push-7x7-2. Similar results in MiniGrid. When the difficulty increases, our method outperforms the baselines by a large margin, for example in LavaCrossing-Harte ments with sparse and delayed rewards. Besides the above goal-conditioned and navigation tasks, method also handle video games with complex mechanics. In MinAtar, CEER performs best or achieves competitive performance in four out of five games. Especially on Breakout, the final score is double that of other algorithms. PER samples transitions with high TD error more frequently. However, the TD error changes dynamically as the network is updated, which may hurt the performance (Cicek al., 2021). EBU and TER consider the sequential character of trajectories and sample transitions in reversed order. Our method propagates rewards when solving RM-MDP, thereby also considers the character of trajectories. Furthermore, our regularizers update the network in supervised manner, which more stable than TD learning. DisCor samples transitions propor- tional to the accuracy of the target value, but such transitions are not necessarily the most related to the optimal policy. In contrast, our method aims to provide accurate target values by combining the conservative estimation Q from RM-MDP with network estimation Q, and treats all transitions as equally important. This can provide accurate target values and does not miss the most related transitions. In summary, our method combines the advantages of several previous methods, and our experimental results indicate that it is suitable for large variety of different tasks. Besides the final scores, we show the learning curves for each environment in Appendix Figures 9, 10, and 11.
be found
These results show that CEER is good at handling environ-
Table 1: Overall performance Sokoban, MiniGrid and MinAtar environments. Numbers in bold represent the method that achieves the highest final scores.
Environment
DQN
DDQN
PER
EBU
DisCor
TER
CEER
Push-5x5-1
10.82
10.78
10.81
10.76
10.82
10.82
Push-5x5-2
10.52
8.72
9.61
6.12
8.39
11.10
11.62
Push-6x6-1
9.26
0.01
0.33
-3.55
-0.04
8.48
10.73
Sokoban
Push-6x6-2
-1.93
-9.71
-9.81
-11.59
-10.43
-10.40
10.54
Push-6x66
-10.06
-10.03
-10.27
-11.71
-10.66
-11.80
7.65
7-11
-5.60
-4.61
-6.39
-4.14
-0.69
10.65
Push-7x7-2
-2.96
-11.76
-11.60
-11.86
-11.81
-11.90
9.97
DoorKey
1.19
3.43
3.45
-3.60
-0.63
-3.60
3,50
Unlock
-0.87
2.72
2.74
-2.88
-2.72
2.59
2,80
RedBlueDoors
5.40
4.67
7.06
-7.22
5.77
6.70
7.09
MiniGrid
SimpleCrossing-
3.09
3.02
3.08
3.11
SimpleCrossing- -ard Hard
3.03
3,02
3.02
-2.85
2.70
3.01
3.09
LavaCrossing Easy
0,58
2.24
1.52
-3.00
-1.13
-2.28
3.10
LavaCrossing-Haan
-3.34
-3.37
-3.38
-3.31
-3.38
-3.09
3,05
Asterix
19.82
20.1
25.8
26.0
31.19
3.07
19.82
Breakout
13.57
16.25
17.76
19.97
17.14
12.73
42.53
MinAtar
Freeway
57.85
57.66
57.79
59.07
56.85
22.08
58.77
Seaquest
14.73
18.57
17.48
12.65
16.69
1.62
17,96
SpaceInvaders
50.71
51.15
55.09
71.83
57.85
45.29
73.43

---

Published as a conference paper at ICLR 2023
5.4 RELATIONSHIP OF PERFORMANCE IMPROVEMENT AND CONSERVATIVE ESTIMATION
To better understand the relationship between performance improvement and conservative estima- tion, we design Average Relative Performance Improvement (ARPI) to measure the improvement for the whole learning process, and Memory Density to measure the quality of RM-MDP.
Average Relative Performance Improvement (ARPI). Suppose we want to compare the perfor- mance of method with method B. Let (A) and R& (B) be the cumulative rewards of and B at evaluating iteration k. Rmmxx max mexx(maxe R& (A), maxe Rg (B) is the maximum cumulative reward that the two methods achieved during the learning process. We define ARPI(A|B) as:
1 K
(A( (B( Rauxx (B) S 1.
ARPI(A|B)
ARPI(A|B presents the relative performance difference of method A compared with method B. If ARPI( (A O, it means performs better than B. When achieves the maximum cumulative reward Rmax at each evaluation k, ARPI(A|BB = shows the maximum performance improvement.
Memory Density, We measure the quality of estimation from RM-MDP based on the density of memory. The intuition here is, if we have tried more different actions at state, we should have a better understanding of the state. Let Dour() be the out-degree of the vertex at state s, |A the size of action space, MT the replay memory. We define the average out-degree of the memory as Doar (M) = M Eeeat [sn(s). Since states are collected as trajectories, usually there is at least one out-degree for each state vertex. The maximum out-degree is the size of action space, so S Doat (M) I |Al. We assume |A| > and define the memory density as:
Density(M) = Dom (M) E 10. |A| -
(10)
We subtract in both numerator and denominator to normalize Density(M)) (MT) between and 1.
Correlation between ARPI and Den- sity. We compare CEER with DQN al- gorithm and compute the Pearson Correla- tion Coefficient p (PCC) (Pearson, 1896; Lee Rodgers & Nicewander, 1988)
0.8
Unlock Doorkey 5xch-5x5-2
LavaCross Easy P
Push-6x6-2
Crassngg RecBlueboors Push 7x7-2
Push Ex6.3
0.6
6ush-6x6-11
simplnCroating Easy
quantify this correlation. PCC is mea- sure of linear correlation between two sets of data. We measure a very strong lin- ear correlation P = 0.881 between perfor- mance improvement and memory density.
Push-5x5-1
ARPI (CEER|DQN)
SimpleCrassing Hard
0.4
Breakout
In Figure 3, each dark point denotes an en- vironment, and the line is the best linear regression. When the memory density in- creases, the performance improves. Even with a low memory density, on MinAtar environments Asterix and SpaceInvaders, there are still improvements. The conser- vative estimation can help the agent avoid suicidal actions, thereby the agent lives longer and gets higher reward. One excep- tion is Freeway, though the final perfor- mance is competitive, the whole learning is slower compared with DQN as shown in Appendix Figure 11. In this environment, the randomly generated objects will move with dif- ferent speeds the game progresses. This feature is not included in the state representation, which breaches the Markov property of MDP. The graph merges different states that look the same but have different speeds, which leads wrong estimation.
0.2
Astari
ppacelnvaders
Seaquest
0.0
Frewwyy
0.0
0.2
0.4
0.6
0.8
1.0
Memory Density
Figure 3: Relationship between memory density and the performance improvement. We compare CEER with DQN. The memory density is the average value during learning. The oblique line shows the result of lincar regression. There is strong correlation between memory density and ARPI.
8

---

Published as a conference paper at ICLR 2023
10
Mean Score
-5
CEFk
20-
10
2
-10-
0
0.0
0.3
1,0
0.0
0.3
1.0
0.5
10
15
2.0
0.0
0.5
10
1:3
2.0
Env. Steps
le6
Env. Steps
1e6
Env. Steps
le6
Env. Steps
1c6
(a) SpaceInvaders
(b) Breakout
(c) Push 6x6-3
(d) SimpleCrossing-
Figure 4: Ablation studies of the two regularizers across environments with different memory densities.
Only value and Only-polic policy only use one regularizer, Conservative- the policy derived from RM- MDP by supervised learning. CEER combines both regularizers.
5.5 ABLATION STUDY
We study two questions: (1) What are the effects of the value and policy regularizers on envi- ronments with different memory density? (2) What is the performance of the conservative policy derived from the replay memory? We choose four environments with increasing memory densities, SpaceInvaders (0.01), Breakout (0.34), Sokoban 6x6-3 (0.53), and SimpleCrossing-Ean (0.89).
Figure 4 compares the learning curves that with 0, and 2 regularizers. Both regularizers inde- pendently benefit the learning. The policy regularizer plays more important role performance improvement. On Sokoban Push-6 6-3, Only value performs worse than DQN, since though the mean square error is reduced, the correct order of actions is maintained due to the function approximation error induced by the neural network. This is similar to the result on Cliffworld in Figure 2, the Q value error of Only reduces faster than Only -policy while the performance improves slower. The curves of Conservative policy show results of the conservative policy derived from the replay memory. Conservative policy remove the target estimation from Q network, so learns from Q in a supervised manner with value weight a = 1. This similar to EMDQN (Lin et al., 2018) and ERLAM (Zhu et al., 2020). The difference is that we still maintain the policy regularizer since find with only supervised learning from Q, the correct order of actions is hard to maintain and results in worse performance. Figure 4 shows that when memory density is high, Conservative policyy outperforms DQN. The conservative estimation from RM-MDP accelerates the learning in these scenarios. However, it is worse than CEER, which emphasizes the importance of combining estimation from both RM-MDP and Q network in target value. When the memory density decreases, Conservative ppoiiyy performs worse than DQN. This could be because the con- servative policy discourages exploration and thereby slows down learning. This indicates that though the conservative estimation can avoid suicidal actions, it will also miss optimal actions. In this case, bootstrapping from Q network works better.
CONCLUSION
We propose consider the replay memory as an empirical Replay Memory MDP (RM-MDP). Solv- ing this RM-MDP combines existing experiences in the replay memory into a conservative estimate. We design two regularizers to accelerate online DRL. We empirically show the effectiveness of our method in many environments and observe a strong correlation between the performance im- provement and memory density of RM-MDP. Results show that our method improves the sample efficiency by large margin, especially when the memory density is high. Even with low memory density, a conservative estimate can help to avoid suicidal actions and thereby improve performance. Our method is also suitable for environments with sparse and delayed rewards.
There are two main directions for future work. Since we have shown a strong correlation between memory density and performance improvement, designing state abstraction methods to merge in- formation from similar states is a significant direction, which can increase the memory density and further improve the performance. Another challenge is extending CEER to environments with tinuous action space. We can use discretization or clustering to construct a discrete RM-MDP with graph structure, or solve it using existing sampling- maased offline RL methods.

---

Published as a conference paper at ICLR 2023
REFERENCES
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.
Richard E. Bellman. Dynamic Programming. Princeton University Press, Princeton, 2021. ISBN 9781400835386. doi: doi:1001511/99811000333333 URL https://cci. org /ot.ooorgg........ 1515/ 9781400835386.
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 (el.:6600.444000 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint arXiv: 540. 2016.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-45 2012.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances Neural Information Processing Systems, volume 31, pp.
2018.
Maxime Chevalier-Boisver Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: / thub. com/mametaaooo httmm//aamecc//eeaeemmmmm mwcb/ www.://emmmmmmmmmmmmm/...... comm-mmnigraa 2018.
Dogan C Cicek, Enes Duran, Baturay Saglam, Furkan B Mutlu, and Suleyman Kozat. Off-policy correction for deep deterministic policy gradient algorithms via batch prioritized experience play. In 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1255-1262. IEBE, 2021.
Peng Dai and Eric A Hansen. Prioritizing bellman backups without a priority queue. In ICAPS, pp. 113-119, 2007.
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International Con- ference on Machine Learning, pp. 3061-3071. PMLR, 2020.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael I. Jordan, Joseph Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforcement learning. arXiv preprint arXiv:1803 100.000000000,, 2018
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. International Conference on Machine Learning, pp. 2052 22222 PMLR, 2019.
Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and non- uniform sampling in experience replay. Advances neural information processing systems, 33: 14219-14230. 2020.
Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal, Timothy Lillicrap, Sergey Levine, Hugo Larochelle, and Yoshua Bengio. Recall traces: Backtracking models for efficient reinforcement learning. In International Conference on Learning Representations, 2019. URL
https:://ppenre
.nt/
Jean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert. Michal Valko, Ioannis Antonoglou, and Rémi Munos. Monte-Carla Tree Search regularized policy optimization. In International Conference on Machine Learning, pp. 3769-3778. PMLR, 2020.
David Ha and Jürgen Schmidhuber. World models. arXiv preprint arXiv: 1803. 10/22, 2018.
10

---

Published as a conference paper at ICLR 2023
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- on machine learning. pp. 1861-1870. PMLR, 2018
Danijar Hafner, Timothy Lillicrap. Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In International Conference on Learning Representations, 2020.
Danijar Hafner, Timothy P Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering Atari with discrete world models. In /CLR 2021: The Ninth International Conference Learning Repre- sentations, 2021.
Jessica B.
Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter W. Battaglia. Combining Q-learning and search with amortized value estimates. In International Conference Learning Representations, 2020. URL https:
/ //openreeiew... wwt.:/nt///ooooeee 2aae//oooori----kkaarr0
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, André Barreto, and Charles Blundell. Fast deep reinforcement learning using online adjustments from the past. Advances in Neural Infor- mation Processing Systems, 31, 2018.
Hado P. Van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in re- inforcement learning. In Advances in Neural Information Processing Systems, volume 32, pp. 19222-1333,, 2019.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-second AAAI conference on artificial intelligence, 2018.
G Zacharias Holland, Erin J Talvitie, and Michael Bowling. The effect of planning shape on dyna- style planning in nigh-dimensional state spaces. arXiv preprint 1rXiv:/806.0166 0005000125, 2018.
Zhang-Was Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological expe- rience replay. International Conference on Learning Representations, 2022.
Zhengyao Jiang, Tianjun Zhang, Robert Kirk, Tim Rocktäschel, and Edward Grefenstette. Graph backup: Data efficient backup exploiting markovian transitions. arXiv preprint arXiv:2205. 15824, 2022.
Andreas Junghanns and Jonathan Schaeffer. Sokoban: A challenging single-agent search problem. In In IJCAI Workshop on Using Games Experimental Testbed for AI Reasearch. Citeseer, 1997.
Levente Kocsis and Csaba Szepesvári. Bandit based Monte-Carlo planning. In ECML '06 Proceed- ings of the 17th European conference on Machine Learning, pp. 282-293, 2006.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q- learning. In International Conference on Learning Representations, 2022. URL https:// openreview. wttprriwww.weeeeeee.e. wttp:/ooorrnndddd22222
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. Advances in Neural Information Processing Systems, 33: 18560-18572, 2020a.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 13:1179-1191 2020b.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pp. 45-73. Springer, 2012.
Su Young Lee, Choi Sungik, and Sae- Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. Advances in Newral Information Processing Systems, 32, 2019.

---

Published as a conference paper at ICLR 2023
Joseph Lee Rodgers and W Alan Nicewander. Thirteen ways to look the correlation coefficient. The American Statistician, 42(1):59- 1988.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives open problems. arXiv preprint arXiv:2005.0164) 2020.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, 'Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint FrXiv:1509.02977 2015.
Long-Ji Lin. Self-improving reactive agents based on reinforcement leaming, planning and teaching. Machine learning, 8(3):293-321, 1992.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep Q-networks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2433- 2439, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-
2015.
Guido Novati and Petros Koumoutsakos. Remember and forget for experience replay. In Interna- tional Conference on Machine Learning, pp. 4851-4860. PMLR, 2019.
Youngmin Oh, Kimin Lee, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Learning to sample with local and global contexts in experience replay buffer. In International Conference on Learning Representations, 2021a.
Youngmin Oh, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Model-augmented prioritized expe- rience replay. International Conference on Learning Representations, 2021b.
Yangchen Pan. Jincheng Mei, Amir-men massoud Farahmand, Martha White, Hengshuai Yao, Mohsen Rohani, and Jun Luo. Understanding and mitigating the limitations of prioritized replay. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Karl Pearson. Vii. mathematical contributions to theory of evolution.-ii.. regression, heredity, and panmixia. Philosophical Transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character, pp. 253-318, 1896.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In International Conference on Machine Learning, pp. 2827-2836. PMLR, 2017.
Baturay Saglam, Furkan B Mutlu, Dogan C Cicek, and Suleyman S Kozat. Actor prioritized expe- rience replay, arXiv preprint arXiv:2209.00532. 2022.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In ICLR (Poster), 2016.
Max-Philipe B. Schrader. gym-sokoban. som-soooban, 2018
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy P. Lillicrap, and David Silver. Mastering Atari, Go, chess and shogi by planning with learned model. Nature, 588(7839):604 609, 2020.
David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lilli- crap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529((587))88) 489, 2016.
12

---

Published as a conference paper at ICLR 2023
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Master- ing the game of Go without human knowledge. Nature, 550(7676):354-35) 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Si- monyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419): 144-199999111111111 144, 2018.
Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with shelihooddffre importance weights. In Learning for Dynamics and Control Conference, pp. 110- 123. PMLR, 2022.
Peiquan Sun, Wengang Zhou, and Houqiang Li. Attentive experience replay. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5900-5907, 2020.
Wen Sun, Geoffrey Gordon, Byron Boots, and Bagnell. Dual policy iteration, Advances Neural Information Processing Systems, 31, 2018.
Richard S Sutton. Dyna, integrated architecture for learning, planning, and reacting, ACM Sigart Bulletin, 264):160-163, 1991.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Csaba Szepesvári, Alborz Geramifard, and Michael P Bowling. Dyna- style plamning with linear function approximation and prioritized sweeping. arXiv preprint arXiv:1206.3283 2012.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Hado Van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in rein- forcement learning? Advances in Neural Information Processing Systems, 32, 2019.
Che Wang, Yanqiu Wu, Quan Vuong, and Keith Ross. Striving for simplicity and performance in oof-cy DRL: Output normalization and non-uniform sampling. In International Conference on Machine Learning, pp. 10070-10080. PMLR, 2020.
Chenjun Xiao, Yifan Wu, Chen Ma, Dale Schuurmans, and Martin Müller. Learning to combat compounding-erro in model-based reinforcement learning. arXiv preprint arXiv:1912.11200 2019.
Kenny Young and Tian Tian. Minatar: An Atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv: 1903:09903.03111 00000003176, 2019.
Daochen Zha, Kwei- Herei-Hergggg Lai, Kaixiong Zhou, and Xia Hu. Experience replay optimization. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2243-4249, 2019.
Shangtong Zhang and Richard Sutton. A deeper look at experience replay. arXiv preprint 172iv:171..01125. 2017.
Deyao Zhu, Li Eran Li, and Mohamed Elhoseiny. Value memory graph: A graph-structured world model for offline reinforcement learning, arXiv preprint arXiv:2206. 04384, 2022.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020. URL https: openreviev net forum? ditimmmddd=xjjoooo j
13

---

Published as a conference paper at ICLR 2023
APPENDIX
A IMPLEMENTATION DETAILS
Network Architecture. For the toy example Cliffworld (Sutton & Barto, 2018) in Section 5.2, we use a network with two fully connected layers. Each layer has 64 units, and we use tanh as activation function. Q-learning does not use network, maintains Q table with size |S] |.A).
For Sokoban, MiniGrid and MinAtar environments, We use a convolutional neural network. The architecture the same as used in MinAtar (Young & Tian, 2019) baselines. It consists of a convo- lutional layer, followed by fully connected layer. The convolutional layer has 16 3 x convolutions with stride 1, the fully connected layer has 128 units. These settings are one quarter of the final con- volutional layer and fully connected layer of the network used in DQN (Mnih et al., 2015).
Hyper-parameters. Our method is based on DQN, other baselines additionally incorporate double Q-learning technique (Van Hasselt et al., 2016) We maintain most parameters the same as original DQN and reduce the interaction steps to run more different random sceds. We run each experiment with 2 million steps of interaction with the environment. We proportionally reduce other parameters based on the interaction steps. The c-greedy exploration is linearly decayed from 1 to 0.01 in million steps. The target network is updated every 1000 steps. The replay memory size is set as 100,000. The minibatch size is 32. The replay ratio is 0.25 (Fedus et al., 2020), that is the Q function is updated once per four environmental steps. The optimizer for the network is Adam. The discount factor is 0.99. Table shows the details of hyper-parameters that used for all methods.
Besides the common parameters, there are other parameters that are specific different methods. For PER (Schaul et al., 2016), the parameter a in sampling probability is set as 0.4, and the pa- rameter / in importance-sampling (IS) weights is linearly annealed from 0.4 to within 0.5 million environmental steps. For EBU (Lee et al., 2019), the diffusion factor ,3 is set as 0.5. For DisCor (Ku- mar al., 2020a), the initial temperature is set as 10, and the error network Ag has one extra fully connected layer as suggested in original paper. For TER (Hong et al., 2022), the batch mixing ra- tio v) is 0.5 for MiniGrid and MinAtar, and 0.1 for Sokoban. We search the replay memory size for TER within {100K,500K, 1M) to ensure there enough terminal nodes when sampling. We search the learning rates for all baselines among performance. For our method, we fix the learning as le-4 and search our particular parameters. Value regularizer weight a E (0.0.2.005.0088,), policy regularizer weight E (0,0.01,1,2.55) and temperature parameter E (1.0.1,0.01).
3,3,,-,,,,11e-433e
and report the best
Evaluation. We run each method on each environment with 20 different random seeds, and show the mean score and standard error with solid line and shaded area. The performance is evaluated by running 100 episodes after every 100K environmental steps. We use e-greedy exploration at evaluation with e 0.01 to prevent the agent from being stuck at the same state.
Table 2: Hyper-parameters of DQN on Sokoban, MiniGrid and MinAtar environments.
Hyperparameter
Value
Minibatch size
32
Replay memory size
100,000
Target network update frequency
1,000
Replay ratio
0.25
Discount factor
0.99
Optimizer
Adam
Initial exploration
Final exploration
0.01
Exploration decay steps
1M
Total steps in environment
2M
14

---

Published as a conference paper at ICLR 2023
B ENVIRONMENT DETAILS
B.I CLIFFWORLD
Cliffworld is simple navigation task introduced by Sutton & Barto (2018) shown in Figure 5. There are 48 states in total which is presented as two-dimensional coordinate axes r and y. The size of action space is with left, right, up and down. The agent needs reach the goal state G starting from the start state S. The reward of reaching the goal is +1, dropped into the cliff gives -I, otherwise is O. We set the discount factor 0.99 and the max episode steps as 100. The arrow on the figure shows the optimal path.
Actions:
S
The Cliff
Figure 5: The illustration of Cliffworld environment. Each grid denotes a state, the arrow shows the optimal path from start state S to goal state G.
B.2 SOKOBAN
(a) Push-5x5-1
(b) Push-5x5-2
(c) Push-6x6-1
(d) Push-6x6-2
(c) Push-6x6-3
(f) Push-7x7-1
gg) Push-7x7-2
Figure 6: Visualization of Sokoban environments.
Sokoban (Junghanns & Schaeffer, 1997; Schrader, 2018) is Japanese puzzle video game. The game played on a board squares, where each square floor or wall. Some floor squares contain boxes, and some floor squares are marked as storage/target locations. The player needs to push all boxes on the target locations. The number of boxes equals the number target locations. The puzzle is solved when all boxes placed target locations. The boxes cannot be pulled, it means a wrong action may lead to irreversible mistakes, which makes these puzzles so challenging especially for reinforcement learning algorithms, which mostly lack the ability to think ahead.
15

---

Published as a conference paper at ICLR 2023
The room is randomly generated each episode. Each time the environment is reset, the walls, the target locations, and the locations of the player and boxes will change. Therefore, it allows to train networks without overfitting difficulties from Push-5 x5-1 to Push-7x7-2. The number in the task name denotes the size of the map and the number of boxes. For example, 5x5-1 means map with size 5x5 and box push. Figure gives the visualization of the seven Sokoban tasks we choose.
set of predefined rooms. We choose
tasks with increasing
State Space. We an image-based state in our experiments. The state has three channels which denote RGB, the size of each channel is the same as the room size. Before inputting state to the neural network, we divide by 255 normalize each pixel into [o, 1].
Action Space. The action space is 8 in total, it consists of moving and pushing both in the cardinal directions, left, right, up and down.
Reward Function. Pushing a box on the target location gets reward +1. Finishing the game gets reward +10. Each step will have a penalty reward -0.1. And the max episode steps 120. So in principle, the maximum reward we can achieve is near to 10 plus the number of boxes. And the minimum rewards -12.
B.3 MINIGRID
(a) DoorKey
(b) Unlock
(c) RedBlueDoors
(d) SimpleCross-Ear SimpleCross-Hor
(f) LavaCrossing Easy
LavaCrossing Hard
Figure 7: Visualization of MiniGrid environments.
MiniGrid (Chevalier-Boisse Boisvert et al., 2018) gridworld Gymnasium (Brockman et al., 2016) en- vironment, which is designed to be particularly simple. lightweight and fast. It implements many tasks in the gridworld environment and most of the games are designed with sparse rewards. We choose seven different tasks as shown in Figure 7.
The map for each task randomly generated each episode to avoid overfitting to fixed map. The state is array with the same size of the map. The red triangle denotes the player, and other objects are denoted with different symbols. The action space is different from tasks. For navigation tasks like SimpleCrossing and LavaCrossing, actions only include turn left, turn right and move forward. For other tasks like DoorKey and Unlock, actions also include pickup key and open a door. Let MaxSteps be the max episode steps, MapWidth and MapHeight be the width and height of the map. We introduce each task as follows.
DoorKey. This task is first pickup the key, then open the door, and finally reach the goal state (green block). MaxSteps defined as 10 x Map Width x MapHeight. Reaching the goal state will get reward +MaxSteps/100) 100, otherwise there penalty reward -0.01 for each step.
16

---

Published as a conference paper at ICLR 2023
Unlock. This task is to first pickup the key and then open the door. MaxSteps is defined as 8 X MapHeight". Opening the door will get reward +MaxSteps/1000 (00, otherwise there is penalty reward -0.01 for each step.
RedBlueDoors. This task is to first open the red door and then open the blue door. MaxSteps is defined as 20 x MapHeight". The agent will get reward +MaxSteps/1000 100 after the red door and the blue door are opened sequentially, otherwise there is penalty reward -0.01 for each step.
This task is to navigate through the room and reach the goal state (green block). Knocking into the wall will keep the agent unmoved. MaxSteps defined as Map width MapHeight. Reaching the goal state will get reward +MMxSttes/1100 100, otherwise there is a penalty reward -0.01 for each step.
HaapleCroos-Easy/Haaeee
LavaCross Erooss-asy/Hard.. This task is to reach the goal state (green block). Falling into the lava (orange block) will terminate the episode immediately. MaxSteps is defined as 4 x MapWidth x MapHeight. Reaching the goal state will get reward +MaxSteps/10M falling into the lava will get reward -MaxSteps/100, otherwise there is penalty reward -0.01 for each step.
B.4 MINATAR
(a) Asterix
(b) Breakout
(c) Freeway
(d) Seaquest
(e) Spacelnvaders
Figure 8: Visualization of MinAtar environments.
MinAtar (Young & Tian, 2019) is image-based miniaturized version of Atari environments (Belle- mare et al., 2013), which maintains the mechanics of the original games as much as possible and is much faster than original version. MinAtar implements five Atari games in total, we show the visualization of each game in Figure 8.
State Space. Each game provides the agent with a 10 x 10 n binary state representation. The channels correspond to game specific objects, such as ball, paddle and brick in the game Breakout. The objects in each game are randomly generated at different time steps. The difficulty will change as the game progresses, for examples, there will be more objects and the objects will move faster. So these environments needs the policy to generalize across different configurations.
Action Space. The action space consists of moving in the cardinal directions, firing, and no-op, and omits diagonal movement well as actions with simultaneous firing and movement. This sim- plification increases the difficulty for decision making. In addition, MinAtar games add stochasticity by incorporating aticks-actions, that the environment repeats the last action with probability 0.1 in- stead executing the agent's 's current action. This can avoid deterministic behaviour that simply repeats specific sequences of actions, rather than learning policies that generalize.
The rewards in most of the MinAtar environments are either or 0. The only exception is Seaquest, where bonus reward between and 10 is given proportional to remaining oxygen when surfacing with six divers.
Reward Function.
C ADDITIONAL EXPERIMENTAL RESULTS
C.1 OVERALL PERFORMANCE
We show the learning curves of each method on Sokoban, MiniGrid and MinAtar in Figure 9, 10 and 11. Each line the average of running 20 different random seeds. The solid line shows the mean score and the shaded area shows the standard emror. We find our method CEER achieves
17

---

Published as a conference paper at ICLR 2023
the best performance most of environments, which indicates the conservative estimation helps the learning by large margin. When the difficulty increases, the performance of CEER remains strong. Since Sokoban and MiniGrid our method is also stable on tasks with sparse and delayed rewards. This highlights that our methods is general method that is suitable for all kinds of tasks.
environments with sparse and delayed rewards, conclude that
10
-51
-9
-10
10
0.0
Env. Steps
le6
Env. Steps
1e6
Env. Steps
166
Env. Steps
1c6
(a) 1
(b) Push-5x5-2
(c) Push-6x6-1
Push-6x6-2
10
10
10
CEER
DQN
EBU
PER
TER
-5
DDQN
-10
-10
DISCOR
00
0.5
1.0
1.5
2.0
6.0
0.5
1.
1.5
2.0
0.0
1.0
1.5
2,5
Env, Steps
Enw. Steps
Emy. Steps
(e)
Push-6x6-3
(1) Tush-7x7-1
(g) Push-7x7-2
Figure 9: Learning curves on Sokoban environments. CEER outperforms other method by a large margin. When the difficulty increases, other methods failed while CEER still achieved high perfor- mance.
Steps
166
Steps
166
Steps
166
Steps
166
(a) DoorKey
(b) Unlock
(c) RedBlueDoors
(d) SimpleCross-En
CEER
DQN
EBU
PER
TER
DDQN
DISCOR
2.0
6.0
0.0
0.5
1.0
Env. Steps
166
Env. Steps
166
Env. Steps
1e6
(c) SimplcCross-Harn Hard
(f) LavaCrossing- Easy
LavaCrossing Hard
Figure 10: Learning curves on MiniGrid environments. CEER performs consistently well across all tasks, which shows method is insensitive sparse and delayed rewards environments.
18

---

Published as a conference paper at ICLR 2023
30
40
Mean Score
30
40
20
20
20
10
10
0.5
1.8 1:5
20
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
15
20
Enw. Steps
Env. Steps
Env. Steps
(a) Asterix
(b) Breakout
(c) Freeway
20
CEER
15
60
DQN
EBU
Moan
10-
PER
TER
20
DDQN
DISCOR
0.0
0.5
1.0
1.5
2.0
0.0
0.3
1.0
1:3
2.0
Env. Steps
Env. Steps
(d) Seaquest
(e) Spacelnvaders
Figure 11: Learning curves on MinAtar environment. CEER performs best achieves comparable performance in four out of five games. And on Breakout, the final score of CEER is twice more than other methods.
C.2 ABLATION STUDIES OF VALUE AND POLICY REGULARIZERS
We show the ablation studies of CEER on Sokoban, MiniGrid and MinAtar in Figure 12, 13 and 14. Only value and Only-policy policy denote the methods that with only value policy regularizer. CEER uses both regularizers and DQN uses no regularizer. Conservative ppoliyy shows the result of the conservative policy derived from the replay memory. It uses the value regularizer with 1 and maintains the policy regularizer unchanged.
We can find that method, CEER, combines the benefits of both value and policy regularizers and achieves the highest final scores on almost all of the environments. Only policy can achieve comparable performance CEER most of environments. It indicates the policy regularizer makes the most contribution for CEER. We can also find that the performance of Only_ value and Conservative is consistent and Only_value valuee performs worse than DQN on environments like Push-6x6-1, SimpleCross- Asterix. Conservative. .policyyeeppeyyyyeooo performs worse on environments like Asterix, Freeway and SpaceIn- vaders. Combining with the memory density of each environment as shown in Figure 3 and Table 3, we can find Only value and Conservative policy perform worse when the memory density de- creases, especially for Only.value.
decrease
environments. For examples,
and
This is because only using value regularizer is not direct regularization on learned policy, which may not maintain the correct order of actions. This emphasizes the importance of policy regularizer. And only learning from the conservative estimation is also not enough, especially on complex video games. The reason may because though the conservative estimation tions that are never tried, will also restrict exploring better actions. This highlights the necessary of learning from Q network, which may take aggressive actions. We can consider the estimation of Q network and the conservative estimation Q from RM-MDP one kind of trade-off between exploration and exploitation. How to balance it is a promising topic which we leave for future work.
help avoid dangerous
19

---

Published as a conference paper at ICLR 2023
10
10
5
0-
-10
-10
-10
Steps
Steps
166
Steps
(a) Push-5x5-1
(b) Push-5x5-2
(c) Push-6x6-1
(d) Push-6x6-2
10
5-
Only_vallue value
onlyypooicyy
Conservativ_pooicy
10
-10
0.5
2.0
0.5
1.0
2.0
0.0
1,5
Env. Stops
166
Env. Steps
1e6
Env. Steps
106
(e) Push-6x6-3
(f) Push-7x7-1
(g) Push-7x7-2
Figure 12: Ablation study on Sokoban environments. Only-policy achieves comparable perfor- mance as CEER. This indicates the policy regularizer makes the most contribution for CEER.
2-
5
2.0 106
6.0
0.0
Env. Steps
Env. Steps
186
Env. Sleps
166
Env. Steps
1e6
(a) DoorKey
(h) Unlock
RedBlueDoors
SimpleCross-Fasy
CEER
Only_value value
Only_pollcy
Conservative_poliy
0.0
0.5
1.0
155
2.0
0.0
0.5
1.0
1.
2.0
0.0
0.5
1.0
1.5
2.0
Env. Steps
186
Env. Steps
166
Env. Steps
166
(e) SimpleCross-HHann Hard
(i) LavaCrossing-Ean
(g) LavaCrossing Hard
Figure 13: Ablation study on MiniGrid environments. Only_value fails on most the tasks, which shows value regularizer is not direct regularization learned policy and cannot maintain the correct order of actions some cases.
C.3 MEMORY DENSITY AND ARPI FOR ENVIRONMENT
We additionally show the statistics of memory density and ARPI for each environment in Table 3. Here, the memory density is the measurement of the RM-MDP's quality, and ARPI measures the relative performance improvement during learning. The definition be found in Section 5.4. In Table 3, the memory density is the average during the whole learning, and the ARPI is the compari- son between CEER and DQN.
20

---

Published as a conference paper at ICLR 2023
60
20
40
50
Mean Score
25
30
40
20
10
10
0.0
0.5
1.8
1:5
20
0.5
1.0
2.0
0.0
0.5
1.0
15
2.
Enw. Steps
Env. Steps
Env. Steps
(a) Asterix
(b) Breakout
(c) Freeway
20
80
Mean Score
DQN
Only_valus
Only_police policy
20
Conservative poyllyv
0.0
0.5
3.0
1.3
2.0
0.0
0.5
1.0
1.5
2.0
Env. Steps
Env. Steps
(d) Seaquest
(e) SpaceInvaders
Figure 14: Ablation study on MinAtar environments. Conservative pepllcy performs poor on most of the environments. It shows though the conservative estimation can help avoid dangerous actions, may also restrict exploring good actions.
On Seaquest environment, though the memory density is O, we still find some improvement com- pared with DQN. This highlights that even the memory density is low, the conservative estimation can still help the learning. Freeway the only exception that the performance decreases. The rea- son is that the speed of objects are not included into the state representation. The graph will merge different states into one vertex and provides wrong estimation, which is harmful for the learning. In addition, since the strong correlation between memory density and ARPI, memory density can be measurement for the difficulty of environment, which is an interesting topic. For example, we can conclude that Push-6x6. 6-3 is harder than 1u-1 and Push-7x7-2.
Table The memory density and ARPI on all environments during learning. The memory density is the average during learning, and ARPI shows the comparison between CEER and DQN.
Environment
Memory Density
ARPI (CCER DQN)
Push-5x5-1
0.93
0.56
Push-5x5-2
0.84
0.76
Push-6x6-1
0.65
Sokoban
Push-6x6-2
0.63
0.70
Push-6x6-3
0.53
0.66
Push-7x7-1
0.83
0.68
Push-7x7-2
0.56
0.64
DoorKey
0.70
0.77
Unlock
0.67
0.77
RedBlueDoors
0.88
0.67
MiniGrid
SimpleCrossing- -asy
0.89
0.58
SimpleCrossing-Harc
0.65
0.45
LavaCrossing-
0.86
0.75
LavaCrossing-Haan Hard
0.64
0.68
Asterix
0.03
0.18
Breakout
0.34
0.38
MinAtar
Freeway
0.02
-0.08
Seaquest
0.00
0.04
SpaceInvaders
0.01
0.10
21

---

Published as a conference paper at ICLR 2023
C.4 COMPARISON WITH MODEL-BASED RL METHODS
To make work more solid, compare method with model-based methods. We summarize three kinds of algorithms, Dyna-style algorithms, Model-based Value Expansion (MVE-style) algo- rithms and Monte Carlo Tree Search (MCTS-style) algorithms. We combine the three paradigms with DQN algorithms, with perfect and learned model. Furthermore, we compare with Dream- erV2 (Hafner et al., 2021), state-of-the-art algorithms that learns powerful world models (Ha & Schmidhuber, 2018). Our results show that CEER is better or competitive with model-based meth- ods with learned model and use much less wall-clock training time.
100
60
40
Mean Score
30
40
60
20
40
20
20
10
0
0:
0.5
2.0
0.5
1.0
1.5
Env. Steps
1e6
Env. Steps
1e6
Env. Steps
1e6
Asterix
(b) Breakout
(c) Freeway
100
40
Mean Score
80
CEER
30
MCTS (P)
60
MVE (P)
Dyna (P)
20
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Env. Steps
1e6
Env. Steps
1e6
(d) Seaquest
(c) Spacelnvaders
Comparison with model-based methods using perfect models. MCTS performs the best in four out of five games. This indicates MCTS is the most efficient model-based method even with small planning budgets.
Figure 15:
Dyna. Dyna-style algorithms (Sutton, 1991; Sutton al., 2012) achieve high sample efficiency by using the model to generate more transitions for training. Dyna first selects some start states from recent experience, then model to generate one-step transitions from those start states. It update the agent with both imaginary transitions and real transitions. In our implementation, besides an experience buffer saving experience from the environment, experience buffer to save experience from the model. With each interaction step with environment, start states are uniformly selected from 10,000 most recent states from experience buffer, then used to simulate for one-step transitions using the model. When updates Q networks, experiences are randomly sampled from both buffers.
additionally maintain simulated
Model-based Value Expansion. Model-free algorithms can improve value estimates by using n- step return and X-return (Sutton Barto, 2018). MBRL, the model can be used for rollouts to improve the targets for temporal difference (TD) learning. This is known as model-based value expansion (MVE) (Feinberg et al., 2018; Buckman et al., 2018; Xiao et al., 2019). In particular, it computes H-step value estimates by simulating on-policy rollouts using the model. For real state Sp. a simulated trajectory with length H is generated the model following current policy, (So, āo, fu. $1, ...
$H @H 1--1...H-- -H- $.). The state-vat value estimate sums up the component pre- dicted by the model HH- 7 ft and the tail estimated by V.
#
VH(50) = Σ
MTx + V(()).
(II)
1=0
22

---

Published as a conference paper at ICLR 2023
With H -tep rollout, we have value estimates (Va(su), (su)..... (s))) Then the target value Y 7 Ei= (5()) Note that when H 0, there is no rollout hence it recovers the model- free TD learning. The main advantages compared model-free algorithms are the flexible on-policy estimates with the model. They do not require the importance weights of off-policy trajectories in mreel-free settings (Feinberg al., 2018). We set H as 5 in our implementation.
Mean Score
20-
30
15
10
20
5-
10
0
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Env. Steps
1e6
Env. Steps
1e6
Env. Steps
1e6
(a) Asterix
(b) Breakout
(c) Freeway
20
100
Mean Score
15
80
CEER
MCTS (L)
10:
40
DreamerV2 (L)
0.0
0.5
1:0
1.5
2.0
0.5
Env. Steps
1e6
Env. Steps
1e6
(d) Seaquest
(c) SpaceInvaders
Figure 16: Comparison with model-based methods using learned models. CEER performs the best on Breakout and is also competitive with MVE and DreamerV2 on other games.
Monte Carlo Tree Search. The AlphaGo and AlphaZero algorithms alternately optimize a re- active (neural network) and a non-reactive (tree search) policy (Silver et al., 2016; 2017: 2018; Sun al., 2018). Monte Carlo Tree Search (MCTS) (Koesis & Szepesvári, 2006; Browne al., 2012) incrementally builds a search tree explore possible future states and actions. Each node in the search tree contains edges (s, a) for legal actions. Each edge stores statistics {N(s,, a), (s,, a), Q(s, a), (ss, a)}. where ((s,, a) is the visit count, ((s, a) is the total action value, Q(s, a) is the mean action value and P(s, a) is the prior probability of selecting that edge.
Each simulation consists of four phases: selection, expansion, evaluation, and backup. In the selec- tion phase, actions are selected according to the statistics in the search tree to traverse from the root node to leaf node. Two terms make up the selection formula,
arg maw.(((sa)))) Uss,))).
(12)
where U(s, a) Cpactl(ss a) [+N(s,a) is exploration term, Opact 1.25 is parameter (Schrit- twieser et al., 2020). Since there is no policy network in DQN, we transform P(s, a) from the Q network via softmax function :)), softmax, (Q(s, -)) with temperature parameter 7 1. In the expansion phase, the leaf node expanded with edges. Each edge (x,a) 3 is initialized with statistics (s, nodes are evaluated by network ((s, a). In the backup phase, statistics are updated backward. ((s, a) N(s a) + 1, W(x, a) W(s, a) Q(s,a) and ((x,a) W(s.)
En N(sbb)
0, W(s, a) 0, 0,{(s,)
0, ((s,())),, In the evaluation phase, the new
N(sa))
At each step, only do five simulations to keep the training time within acceptable range. In this case, comparing to selecting actions by visit counts after tree search, using action values is a more stable choice (Grill al., 2020). Thus, after simulations by MCTS, select actions based the mean action values (8,, () at the root node:
Q(s,a)1/+
π <(ass) = E. Qss 6)//7
(13)
23

---

Published as a conference paper at ICLR 2023
Our implementation is simplified version of AlphaZero and MuZero (Silver et al., 2017; Schrit- twieser et al., 2020) that we don't learn a policy network. This is similar to Search with Amortized Value Estimates (SAVE) algorithm (Hamrick et al., 2020).
We first use perfect model (denote as P) for the three methods. Perfect model can avoid the difficulty of model learning and give clear insight which method is the best. Figure 15 shows the results comparing with CEER. We can find Dyna shows no advantage over other methods. This is because planning to generate one-step transitions provides limited data diversity compared experience buffer, which offers little benefit even with a perfect model (Holland et al., 2018; 18; Hasselt al., 2019). This also gives us a similar results to Van Hasselt al. (2019) that replay- algorithms should be competitive to or better than model- based algorithms if the model is used only to generate fictional transitions. MVE performs hetter than CEER on Asterix and Seaquest but performs worse on other games. We hypothesize the choice of H has trade-off between variance and bias, which is similar to n-step return and depends on the specific problem. MCTS performs the best in four out of five games. This indicates when we have perfect model, MCTS is the most efficient method even with a small planning budgets.
existing
Since perfect model is not an practical setting in real life. Next, we compare with methods that learn a model (denote as L). We consider MCTS with learned model, and the state-of-the-art baseline D2eamerV2 (Hafner et al., 2021). For the learned model in MCTS (L), ture as Q network. The input state 8 and action a, the output the next state s' and reward r. DreamerV2 is method that focuses more on how learn high-quality model. We maintain the architecture as in original paper. There are too many parameters in DreamerV2, which is more com- plex and harder tune than CEER. Figure 16 shows that CEER performs the best on Breakout, and is also competitive with Dreamer V2 and MCTS (L) on other games.
the same architec-
C.5 WALL-CLOCK TIME COMPARISON
Only reporting sample efficiency cannot tell us how long we need to train an agent for each method. We compare the wall-clock time during training in Table 4. We use Frames Per Second (FPS) to measure the training speed. FPS counts the number of frames that the agent interacts with the environment per second. We test the speed on device with GPU (NVIDIA TITAN RTX) and 10 CPUs (Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz). We do 3 runs for DreamerV2 and 5 runs for other methods. We can find our method CEER (FPS: 308) is only slightly slower than DQN (FPS: 402), similar to PER (FPS: 318), and much faster than model-baset methods like DreamerV2 (FPS: 19). Since we use a simple network architecture with a single convolutional layer followed by fully connected layer, the computation burden for the memory part is relatively high comparing with the network training. If we use a large network, the computation burden for the memory part will be lower comparing with the network training.
Table 4: Wall-clock time comparison between different model-free and model-based methods. We use Frames Per Second (FPS) measure the speed of interaction with environments during training. For model-based methods, P denotes the method using a perfect model, L denotes the method that learns a model.
Method
FPS (mean + std)
DQN
402.85 6.78
DDQN
388.73 + 5.97
PER
318.17 + 1.43
Model-Free
EBU
193.60 4.28
DisCor
328.43 5.86
TER
220.84 3.50
CEER
308.72 + 5.68
Dyna (P)
117.67 0.81
MVE (P)
79.09 2.22
Model-Based
MCTS (P)
104.78 0.51
MCTS (L)
50.21 + 0.90
Dreamer (L.
19.36 0.88
24

---

Published as a conference paper at ICLR 2023
C.6 ADDITIONAL COMPARISON WITH RAINBOW ON ATARI PONG ENVIRONMENT
Besides MinAtar environments, we additionally compare our method with Rainbow (Hessel et al., 2018) algorithm full suite of Atari game Pong (Bellemare et al., 2013). The network architecture contains three convolutional layers and a fully connected hidden layer, which is the same as used in DQN (Mnih al., 2015). Rainbow splits the Q values into state-value and the advantages for each action. We show the result on Pong in Figure 17. We can find CEER learns faster than Rainbow, which indicates CEER competitive on the full suite of Atari environments.
20
CEER
Raiinbow
Mean Score
10
0
-10
-20
0.0
0.5
1.0
1.5
2.0
Env. Steps
1e6
Figure 17: Learning curves on Atari Pong environment, CEER learns faster than Rainbow, which indicates CEER is also competitive on the full suite of Atari environments.
C.7 COMPARISON BETWEEN SAMPLING UPDATE WITH SWEEPING UPDATE
Since each interaction step will add a new transition to the memory during the training, RM-MDP is non-stationary. A natural question is if the sampling-hased update and episode-based update (Sam- pling Update for short) introduced in Section 4.2 is enough to obtain accurate estimation? Another time-consuming but completely accurate update is sweep all state-action pairs in the memory at each interaction step (Sweeping Update). We compare the two ways on three enviromments as shown in Figure 18. We can find though RM-MDP non-stationary, CEER with Sampling Update perform almost the same as Sweeping Update, which means Sampling Update is enough to obtain accurate estimation in this stat-ottionar MDP
10
Surpling Upplte
Samsliigg
Swecppigg Updlite
Mean Score
5
2:
40
30
0-
20
-5
2:
10
Sncaping
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2,0
Env. Steps
Env. Steps
1e6
Env. Steps
1e6
(a)
Push-6x6-3
(b) SimpleCross Easy
(c) Spacelnvaders
Figure 18: Comparison between Sampling Update with Sweeping Update. CEER with Sampling Update performs almost the same Sweeping Update, which means Sampling Update can obtain accurate estimation even in this non-stationary MDP.
C.8 PARAMETER SEARCH FOR VALUE AND POLICY REGULARIZERS
We show the parameter search for value (a) and policy (A) regularizers Figure 19 and 20. When report one parameter, we fix the other parameter the optimal one. The vertical axis shows the final score. We can find when the environments are easy,such as Push-5x5-1 and SimpleCrossing- Easy, the two regularizers do not influence the final performance. When the environments are harder, such as Push-6x6-3 and Breakout, the two regularizers play important role in performance improve- ment, which emphasizes the efficiency of method.
25

---

Published as a conference paper at ICLR 2023
16
Final Stora
Finll Scoe
Fiul Scome
Finll Store
Fioll Store
-10
(a) Push-5x5-1
(b) Push-5x5-2
(c) Push-6x6-1
(d) Push-6x6-2
(e) Push Push-6x6-3
Rin Score
Poot Stre
Find Score
Roal Store
(1) Push-7x7-1
(g) Push-7x7-2
(h) DoorKey
(i) Unlock
(i) RedBlueDoors
FralScoo
FrotScore
Scotec
Scome
Rnall Score
1
0:25
035
0.75
1.00
1.00
0:25
003
675
1.20
4.0
022
0.50
3775
1:00
0.00
325
035
6.75
1.0
0,20
025
7.50
275
1.00
(k) HimCross-Easy
(1) SimCross-Hard
(m) LavaCross-Ean -aasy
(n) LavaCross-Harrd
(o) Asterix
025
0300
3.00
8.0 025
050
1.00
000
6.25
0.59
9.75
3/0
0.25
0.50
0.8
1.0
(p) Breakout
(g) Freeway
(t) Seaquest
(s) SpaceInvaders
Figure 19: Parameter search for value regularizer.
26

---

Published as a conference paper at ICLR 2023
Find Scote
And Score
And Score
Ann Score
Anal
02
642
6.0
0.22
90
(a) Push-5x5-1
(b) Push-5x5-2
(c) Push-6x6-1
(d) Push-6x6-2
(e) Push-6x6-3
Fint Score
Rinal Soore
Real Seare
Rnal Score
Fiut
63
Push-7x7-1
(g) Push-7x7-2
(h) DoorKey
Unlock
RedBlueDoors
M
Pial Score
Fiot Score
Frai Score
Frai Score
Rinll Store
B
600
8
(k) SimCross-Easy
(1) SimCross-Hard
(m) LavaCross EavaCross-Easy
(n) LavaCross-Hlan
(o) Asterix
5
Roal
B
300
602
(p) Breakout
(g) Freeway
(r)
Seaquest
(s)
SpaceInvaders
Figure 20: Parameter search for policy regularizer.
27


Reviews:
[{"review_id": "ku08bRNmnIp", "reviewer": "Reviewer_oYzW", "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": "", "summary_of_the_paper": "In Strength And Weaknesses", "summary_of_the_review": "In Strength And Weaknesses", "strength_and_weaknesses": "Summary: This paper considers constructing an empirical MDP from experience replay and estimates a Q-value function and policy from this empirical MDP. Then this paper applies these estimators to help train original Q-network. The benefit of the empirical MDP on replay buffer is the conservative estimation, which helps accelerate the learning process of orinigal Q-network.\n\nOverall, I reckon the idea of this paper is quite novel and interesting, and this paper provides convincing empirical studies of their algorithms. However, there existing some writing issues and some further questions to me in the following. At the first stage, I would give a conservative evaluation of this paper with the score of 6. I will consider change my score with other reviewers' opinions and authors' responses.\n\nQuestions and Comments:\n1. Eqn (1), the LHS is Q(s,a) but the RHS is the expectation over (s,a,s'). I believe it's a typo?\n2. Eqn (3), what does the 't' mean for (s_t, a_t, s_t+1)?\n3. In Data Structure of Section 4.1, the main purpose is to estimate the empirical transition probabilities by frequency estimation. My question is what is the role of the Graph? Without the Graph, it seems the estimation can also be derived.\n4. I think the authors should be more specific on the expression of the sampling method in Section 4.2. Though I can understand what the authors are trying to say, others may not.\n5. The authors should offer references on the overestimation problem on DQN in paragraph \"value regularize\".\n6. Could the authors tell me more about how conservative policy $\\hat{\\pi}$ lower bounds the performance of policy $\\pi$.\n7. In algorithm 1, do updates in Line 9 and Line 10 share the sample minibatch? Why？\n8. Actually, I'm curious about the choice of $\\alpha$ in value regularize. It would be great if the author compare the performances of their algorithm with different choice of alphas.\n9. To my knowledge, the model-free methods mean the memory space is taken up to $\\mathcal{O}(SA)$. However, by constructing empirical MDP with estimation of transition probability, the memory space is taken up to $\\mathcal{O}(S^2A)$, which should be model-based. I think the authors should be more precise on description of their methods in introduction and abstract.\n10. In Section 5.4, the authors investigate the relationship between the performance improvement and conservative estimation. But I'm still confused with the intuition why density is correlated with the performance improvement. Could the authors provide a more high-level explanation in rebuttal?\n\n==========================\n\nAfter reading the authors responses and other reviewers' comments, I find the current version is qualified to be published. At the current stage, I prefer to raise my score to 8. If the other reviewers have more concerns, I'm willing to discuss with them and adjust my evaluation.", "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": "jyc2lJkVk2", "reviewer": "Reviewer_nSvQ", "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": "", "summary_of_the_paper": "This paper presents an idea of combining conservative estimation with experience replay to improve sample efficiency. The key idea is to construct a graph based on the transitions stored in the buffer, where the transition probabilities are estimated based on the visiting counts. Then they use value iteration to solve the graph (i.e., an estimated MDP) to obtain the optimal Q-value for the estimated MDP. The obtained Q-value is further derived to an optimal policy. Finally, the optimal Q-values and policy are used to regularize the policy and value networks, where the optimal Q-values are combined with the RL Q-values with the weighted sum, and the optimal policy network is used as the target of policy distillation with KL divergence loss. Experimental results on several environments show that the proposed method CEER outperforms the baselines.", "summary_of_the_review": "The paper is well-motivated and presents an interesting idea. However, the paper is similar to many works that combine model-based and model-free algorithms. Their relationships have not been discussed. Also, the method may not be able to scale to large or continuous state space.", "strength_and_weaknesses": "Strengths:\n\n1. The motivation is clear. The algorithm is interesting.\n2. The authors show improvement in sample efficiency in a toy environment and some more complex environments in various domains.\n\nWeaknesses:\n\n1. While the paper focuses on the experience repay, I find the idea is actually to combine model-based and model-free algorithms. Several related methods should be discussed and compared, such as World Models [1] [2], and works that combine model-based and model-free methods, such as [3]. That being said, it is unclear what the novelty is without a comparison with these previous works.\n2. Some missing related works in experience replay [4] [5].\n3. I find the idea is very similar to ERLAM [6]. It seems the only difference is the way the regularizer is added.\n4. In Eq. (3), the transition probabilities are estimated by visiting counts. In the case that a state has never been seen or an action has never been tried by the agent, how should the probabilities be estimated?\n5. Can the methods be used in continuous state space? In this case, how to construct the graph, and how the value iteration can be applied?\n6. The paper only reports sample efficiency but not wall-clock time. It is unclear how many additional computational resources are needed for the graph construction and value iteration.\n7. How the memory density in Eq. (10) could be applied in continuous state space.\n\n\n\n\n[1] Ha, David, and Jürgen Schmidhuber. \"World models.\" arXiv preprint arXiv:1803.10122 (2018).\n\n[2] Hafner, Danijar, et al. \"Dream to Control: Learning Behaviors by Latent Imagination.\" International Conference on Learning Representations. 2019.\n\n[3] Sun, Wen, et al. \"Dual policy iteration.\" Advances in Neural Information Processing Systems 31 (2018).\n\n[4] Zha, Daochen, et al. \"Experience replay optimization.\" Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019.\n\n[5] Fujimoto, Scott, David Meger, and Doina Precup. \"An equivalence between loss functions and non-uniform sampling in experience replay.\" Advances in neural information processing systems 33 (2020): 14219-14230.\n\n[6] Zhu, Guangxiang, et al. \"Episodic reinforcement learning with associative memory.\" (2020).\n", "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": "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": "MyIlFDL5Qgx", "reviewer": "Reviewer_PqTv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new way to make experience replay more efficient. Inspired by episodic learning, the authors treat the replay memory as an empirical replay memory MDP (RM-MDP). With dynamic programming, conservative value esimtate is learned by only considering transitions observed in the replay memory. Based on the empirical estimated dynamics, the authors propose value regularizer and policy regularizer and use these two regularizers to boost the learning process of DQN. To better understand the proposed method, the authors design metric for memory density, and empirically find a strong correlation between performance improvement and memory density. Extensive experiments show that the proposed CEER algorithm improves sample efficiency across several benchmarks in discrete action domains.", "summary_of_the_review": "The paper proposes a new way to make replay memory more efficient. The authors conduct thorough empirical analysis to demonstrate the advantages of this work. I think this work could benefit future research on replay memory in RL community. However, further experiments on more complicated should be demonstrated to make the proposed algorithms more convincing.", "strength_and_weaknesses": "Strength:\n+ The perspective of treating the replay memory as an empirical MDP is interesting, and the proposed algorithms successfully improve sample efficiency by leveraging this empirical MDP.\n+ The authors conduct a lot of solid experimental analysis to demonstrate the effectiveness of the methods, and provide interesting insights for future direction based on this work.\n\nWeaknesses:\n- The proposed method is only evaluated on limited environments. I think experiments on more complicated environments such as full suite of atari games are necessary to make the work more solid and convincing.\n- The baseline considered in this work is not strong enough. It would be better to see if the CEER techniques can improve sample efficiency upon more powerful existing RL algorithms such as RAINBOW.", "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": {}}, {"review_id": "KAZveMrfcGD", "reviewer": "Reviewer_MxYs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "By considering it as an empirical Replay Memory MDP (RM-MDP), the authors in this study take advantage of the information contained in the experience replay memory. The authors discovered a conservative value estimate that solely considers transitions seen within the replay memory by solving it using dynamic programming. Based on this conservative estimate, value and policy regularizers are developed and integrated with model-free learning algorithms. To gauge the effectiveness of RM-MDP, they develop a memory density metric. According to the authors' empirical findings, there is a significant correlation between memory density and performance enhancement. They use a technique called Conservative Estimation with Experience Replay (CEER), which significantly boosts sampling efficiency, mainly when the memory density is high. Such a conservative approximation can nonetheless assist in preventing suicidal behavior and hence increase performance even when the memory density is low.", "summary_of_the_review": "Although the paper combines model-based and model-free methods, many other papers have done the same. There hasn't been any discussion of their connections. Additionally, it is clear that the strategy could not be scalable to continuous state space. Moreover, the reproducibility of the introduced work is a major concern. ", "strength_and_weaknesses": "**Strengths:**\n- The paper is well-written and easy to follow.\n- There are not many typos or punctuation mistakes as far as I noticed.\n- The motivation is great, that is, considering the importance of neither temporally correlated nor single transitions but the entire replay buffer.\n- Constructing an MDP over the collected transitions, and solving it through a modified dynamic programming scheme is novel.\n- The authors perform a credible set of experiments on various benchmarks, such as using 20 random seeds and training for 2 million time steps are promising. The experimental setup and implementation details are explained in depth (e.g., hyper-parameter tuning).\n- A comprehensive supplementary material is provided that enlights the depth of the study.\n\n**Weaknesses:**\n- The paper lacks a discussion over the competing methods. The authors only translate the results given in the Tables and Figures into sentences. Please describe in detail why competing methods exhibit poor performance, and what the reasons are. Focusing only on the proposed method in discussions decreases the explainability of the work and the introduced novelties. \n- The authors solve an MDP over the created graph according to the transitions contained in the replay buffer. However, in such a case, the MDP is always changing as new transitions are added to the buffer. Hence, this MDP is non-stationary. The authors did not address this. \n- The proposed method relies on prior offline/batch reinforcement learning approaches as the authors provide a reference to the corresponding papers. Moreover, the authors mention Experience Replay (ER) with reweighted updates, ER with episodic RL, and ER with reverse updates. The proposed framework contains similar entities from these three categories. I suggest the authors also discuss the most similar approach to their method in detail so that the novelty becomes more clear. Moreover, the work is very similar to the [paper](https://openreview.net/forum?id=HkxjqxBYDB) by Zhu et al. Please clarify this.\n- The transition probabilities in Eq. (3) are calculated using visitation counts. How should the probabilities be calculated if the agent has never experienced a state or performed a certain action?\n- The proposed method is _clearly for discrete action spaces_ as I believe constructing a graph for continuous action domains is impossible even under discretized environments because a slight numerical deviation may yield significant results in especially locomotion tasks and result in loss of information. \n- Conservative regularization is used for Q-network and policy to make their update closer to the MDP corresponding to the collected transitions. However, if the behavioral policy never improves (e.g., choosing similar actions for similar states), how come the proposed method is expected to advance the underlying RL algorithm, as the updates are conservatively regularized? Specifically, the conservative updates prevent the RL algorithm from taking large gradient steps; hence, the policy may never improve. This would go on recursively. Am I correct? The authors should discuss this.  \n- Although the introduced performance metric, ARPI, seems to be a reasonable proxy for evaluating the performances, why didn't the authors use other metrics as given in the [work](https://ojs.aaai.org/index.php/AAAI/article/view/11694) of Henderson et al.? At least the authors could've discussed the existing metrics given in that [study](https://ojs.aaai.org/index.php/AAAI/article/view/11694) and maybe tried one of them.\n\n**Detailed Comments**:\n- Although the related work gives insights into the current approaches to experience replay, I believe the following work is worth discussing as they focus on either the Prioritized Experience Replay algorithm or reweighting the importance of transitions:\n1) [An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay](https://papers.nips.cc/paper/2020/hash/a3bf6e4db673b6449c2f7d13ee6ec9c0-Abstract.html) by Fujimoto et al.\n2) [Actor Prioritized Experience Replay](https://arxiv.org/abs/2209.00532) by Saglam et al.\n3) [Model-augmented Prioritized Experience Replay](https://openreview.net/forum?id=WuEiafqdy9H) by Oh et al.\n4) [Off-Policy Correction for Deep Deterministic Policy Gradient Algorithms via Batch Prioritized Experience Replay](https://ieeexplore.ieee.org/abstract/document/9643162) by Cicek et al.\n5) [Experience Replay Optimization](https://www.ijcai.org/proceedings/2019/589) by Zha et al.\n- Fifth line in Section 3: Replace \"expected cumulative rewards\" with \"expected discounted sum of rewards\"\n- First line on page 3: Give a reference to the [Dynamic Programming book](https://www.degruyter.com/document/doi/10.1515/9781400835386/html) when mentioning Bellman optimality equation\n- Third line on page 3: No need to give a reference when mentioning deep neural networks\n- Final paragraph in Section 3: There are sentences: _\"Though the replay memory in online learning\nis usually a time-changing first in first out queue, at a specific time step, the memory can be\nconsidered as a static dataset that contains finite transitions. Thus, solving RM-MDP is similar to\noffline RL setting that solves an empirical MDP and finally results in a conservative estimate.\"_ Are there any references?\n- Fourth sentence in Section 4.3: There is a sentence: _\"Our ˆQ value from RM-MDP is constrained in the replay memory that will never overestimate.\"_ The overestimation is induced by the maximization in the Q-network updates. Similarly, the proposed method also uses maximization even if across the recorded transitions. This sentence should be explained in more detail or a reference should be given, as it is a very strong claim.\n- Please express the considered baseline algorithms in the full form, not using acronyms.", "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": {}}]

Author rebuttal:

Decision: Accept: poster