Neural Episodic Control with State Abstraction
Authors: Zhuo Li
Derui Zhu
Yujing Hu
Xiaofei Xie
Lei Ma
YAN ZHENG
Yan Song
Yingfeng Chen
Jianjun Zhao
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Deep reinforcement learning
episodic control
sample efficiency
state abstraction

Abstract: Existing Deep Reinforcement Learning (DRL) algorithms suffer from sample inefficiency. Generally, episodic control-based approaches are solutions that leverage highly rewarded past experiences to improve sample efficiency of DRL algorithms. However, previous episodic control-based approaches fail to utilize the latent information from the historical behaviors (\eg, state transitions, topological similarities, \etc) and lack scalability during DRL training. This work introduces Neural Episodic Control with State Abstraction (NECSA), a simple but effective state abstraction-based episodic control containing a more comprehensive episodic memory, a novel state evaluation, and a multi-step state analysis. We evaluate our approach to the MuJoCo and Atari tasks in OpenAI gym domains. The experimental results indicate that NECSA achieves higher sample efficiency than the state-of-the-art episodic control-based approaches. Our data and code are available at the project website\footnote{\url{https://sites.google.com/view/drl-necsa}}. 

Published as a conference paper at ICLR 2023
NEURAL EPISODIC CONTROL WITH STATE ABSTRAC- TION
Zhuo Li'
Derui Zhu?
Yujing Hu²
Xiaofei Xie
Lei Ma
Yan Zheng'
Yan Song'
Yingfeng Chen'
Jianjun Zhao'
Kyyushu University "Technical University of Munich
*NetEase Fuxi Al Lab
"Singapore Management University SUniversity of Alberta
'The University of Tokyo 'Tiajin University
ma leeleif aaamcoors
zhaofait. u...
ABSTRACT
Existing Deep Reinforcement Learning (DRL) algorithms suffer from sample inef- ficiency. Generally, episodic control- approaches are solutions that leverage highly-rewarded past experiences to improve sample efficiency of DRL algorithms. However, previous episodic control-based approaches fail to utilize the latent information from the historical behaviors (e.g.. state transitions, topological sim- ilarities, etc.) and lack scalability during DRL training. This work introduces Neural Episodic Control with State Abstraction (NECSA), simple but effective state abstraction- based episodic control containing a more comprehensive episodic memory, novel state evaluation, and a multi-step state analysis. We evaluate approach to the MuJoCo and Atari tasks in OpenAl gym domains. The experi- mental results indicate that NECSA achieves higher sample efficiency than the state-of-the-art episodic control-base approaches. Our data and code are available the project website")
INTRODUCTION
Deep reinforcement learning (DRL) has garnered much attention in both research and industry, with applications in various fields related to artificial intelligence (Al) such as games (Mnih et al. [2013]
Silver et al., 2018 Shen et al. 2020), autonomous driving (Xu al., 2020), software testing (Zheng
et al. 2019 2021c) and robotics (Thomaz & Breazeal 2008). DRL usually achieves excellent performance for many tasks and sometimes outperforms human beings. However, human-level
DRL policies usually require a tremendous amount of data and millions of training steps. which are demonstrated to be sample inefficient (Arulkumaran et al., 2017: [sividis al. (017). To mitigate this problem, many approaches have been proposed, such as improving the exploration (Yu 2018 Burda et 2018), modeling the environment (Moerland et al. 2020)) state abstraction (Vezhnevets al., 2017) and knowledge transfer (Lazaric et al.) 2008; Zhang et al., 2020); Cao et al.) 2022).
However, this paper focuses on resolving the problem of sample inefficiency through episodic control.
Episodic control is designed to assist DRL agents in making the appropriate decisions in unseen environments using past experiences. The idea is inspired by biological mechanism, hippocam- pus (Lengyel & Dayan 2007). Moreover, episodic control has been adopted to tackle the sample inefficiency in DRL (Blundell et al. 2016 Pritzel et al. [0177). Previous neural episodic control- based approaches usually store past experiences in tabular memory. Therefore, the agent could retrieve experiences by looking up similar cached states from the episodic memory. Then the state (action) values could be estimated based on the similar states retrieved. In this way, the policy can efficiently reduce the bias between episodic and model estimated state values and generalize the past heghly-rewarded cases.
historical highly-rewarde
Although many episodic control-based approaches were proposed to improve the sample efficiency of DRL policy, all them suffer from obvious limitations (Hu al. [021] Pinto 2020 Kuznetsov Filchenkov 202T In general, they only store the concrete states, actions, and state values (Blundell
https://si google..oooooooooooooooooo 1e. com/ wwweew//ee dr necsa

---

Published as a conference paper at ICLR 2023
et al. 2016). On the other hand, their episodic memory does not record information such time steps and transitions in the traces. As a result, some latent semantics, such as state tramsitions and topological similarities, camnot be explored and exploited. However, many previous works demonstrate that such latent information can be used to improve sample efficiency (Kuznetsov & Filchenkov] 202TT] /Zhu al.) 2020). For instance, DRL model is trained to make decisions continuously, and the influence (e.g., approximation errors) of a state-action pair might be accumulated and affect the forward scenes (Dynkin 1965). In other words, the root cause of bad decision in the current state can either come from the latest state or the much earlier states. The topological state transitions can help trace the root cause of the bad decisions.
Moreover, the data structure of existing episodic memories does not efficiently support storing and exploring latent semantics. The reason that the concrete state representations usually consist of float numbers. Thus almost none of the states are the same. Consequently, we cannot directly count and retrieve them from episodic memory, and is impossible to identify the critical state transitions. In addition, existing episodic control-based approaches, which utilize distance-basee based measurement to retrieve the k-st most similar concrete states (e.g., k-nearest neighbors, i.e., kNN search) and the weighted sum of the state (action) values for the estimation (Pritzel et al. 2017 Lin et al., 2018), are inevitably seoource-cossmiing comprehensive episodic memory analysis (i.e., multi-step state transitions) and (2) a more scalable storage and retrieval strategy for episodic data.
Overall, existing episodic control- control-based approaches lack (I) a more
We propose NECSA, state abstraction-based neural episodic control approach that enables more comprehensive analysis of episodic data and better sample efficiency to address the above issues. Inspired by multi-grid and model-based reinforcement learning (Grzeš & Kudenko, 2008 Kaiser et al. 2019), we discretize the continuous state space into finite grids on each dimension, and the states located in the same grid will be labeled with unique ID. Naturally, we conduct a multi-step analysis of the state transitions by treating the consecutive state transitions as a fixed pattern. Finally, we make the policy generalize different patterns, as we infer that analyzing and generalizing such multi-step patterns might result in better performance than just focusing on single state (Sutton) & Barto 2018). Such abstraction enables the following strengths: (1) based on the abstracted state space, more advanced semantic characteristics, such as state transitions and topological similarities, can be analyzed for improving performance (Grzeš & Kudenko 2008); (2) the complexity of storing and retrieving the episodic data is reduced O(N) to O(1) since using an exact match.
retrieve the episodic memory
Previous episodic controls used average state values the state measurement to correct the DRL policy estimation (Lin et al.] 2018)) Kuznetsov & Filchenkov 2021). Nevertheless, such a state measurement cannot be computed directly for multi-step pattern. Instead, we propose intrinsic state measurement based on state abstraction instead of past state values. Specifically, we record the returns of those episodes where they occur in an abstract pattern. Then we compute the average returns to measure the abstract pattern. This measurement can efficiently identify those patterns which can result in higher rewards. By utilizing such intrinsic rewards (Burda et al., 2018), we revise the policy and accelerate the learning by encouraging those states with higher measurements but punishing those with relatively low measurements.
Finally, we evaluate NECSA on MuloCo (Todorov et al., 2012) and Atari tasks in OpenAl gym (Brock man et al. 2016) domains. The evaluation shows that our approach can significantly improve the sample efficiency and outperform state-of-the-art episodic control. In summary, make the follow- ing contributions: (1) we propose a multi-step analysis of state transitions to achieve better policies; (2) we propose comprehensive episodic memory that enables more advanced analysis of past experiences; (3) we propose an intrinsic awardd-ased episodic control method to optimize the policy.
RELATED WORK
2.1 NEURAL EPISODIC CONTROL
Episodic control (Lengyel & Dayan 2007) was creatively applied on model-free DRL tasks to retrieve episodic memory based state values (Blundell et al. 2016) for resolving sample inefficiency. The distance- based measurements were applied for looking up similar episodic data (Pritzel et al., 2017). The episodic memory buffer can be smaller by applying Gaussian Random Projection to reduce the
2

---

Published as a conference paper at ICLR 2023
Replay Buffer
Episodicc Data
Environment
Agent
Episodic Table
Concrate
Grid-based Abstintter
State action
Figure I: The overview of NECSA. We abstract the concrete state-action pairs, measure the abstract states and combine the state measurement with the traces. Finally, the revised traces will be stored in the replay buffer for the agent to sample.
dimension of concrete states (Lin et al. 2018). The retrieved state values from episodic memory can be combined with the predictions of the eritic network (Hansen al. 2018). Novel episodic memory
structure such as associative memory and generalized memory efficiently propagates state values
to stored memory items (Zhu al., 2020 Hu et al., 202TT. Episodic control was also combined with multi-agent tasks (Zheng et al. [2021a) with curiosity-
exploration and model-based (021). Recently, the episodic control was also applied to the
reinforcement learning (Le continuous control (Zhang et al. Kuznetsov & Filchenkov 2021). which outperformed the state-of-the
th-the-rrt DRL algorithms. The universal episodic control (Hu al. [021] Pinnto| 2020) was proved effective on both discrete and continuous action space by adopting generalized episodic memory (e.g., neural network) to the past state values. Offline tasks can solved by the state value-based episodic buffer and avoid the vverageneralizztion of actions in the dataset (Ma et al.) 202I). Episodic memory was also used to search the optimal hyperparameter for policy gradient methods (Le et al. 2022). This paper proposes NECSA, novel and simple episodic control-based approach. NECSA adopts a grid-based state abstraction instead of distance-bast measurement to operate episodic memory more efficiently. Moreover, unlike previous works, episodic memory is more comprehensive since the state abstraction strategy enables us to explore abstract state transitions and topological information. Such information be used to improve the sample efficiency (Yin & Li 2020).
2.2
STATE ABSTRACTION
The purpose state abstraction to group states which share the same characteristics into a single cluster. One solution is discretizing the continuous domains (Dougherty et al., 1995). In model-
based RL tasks (Kasser et al. 2019), the state abstraction (Jiang et al.) 2015 Burda et al. 2018) plays essential role in reducing the data scales, although such abstraction requires strong domain knowledge the environment or assumptions. In model-free reinforcement learning, the grid-based state abstraction has proved effective (Anderson & Crawford-Hiinss 1994 Grzeš & Kudenko 2008).
Particularly in continuous control, the continuous action space can be divided into equal intervals, then those concrete actions the same value scales can be labeled by a common abstraction (Pazis &
Lagoudakis 2009 Tang & Agrawal 20200 Du et al. 2019 Xie et al.) 22199; Zhu et al. 2021). Another work of state abstraction in reinforcement learning is DreamerV2 (Hafner et al.) (0200) which encodes the observations directly as discrete state variables. The idea of smoothing the state space (Gangwani
al. 2020) shares similarities with our work exploring topological information on state transitions.
Dynamic state clustering (Mannor et al., 2004) is proved to be effective, although it is hard to be applied to the multi-step analysis. Moreover, previous works partially focus on state or action space, and few works have been done abstracting state-action pairs. Inspired by the above works, we use the grid-basee based abstraction to group the state-action pairs simultaneously.
3 BACKGROUND
Generally, the process of reinforcement learning (RL) can be defined as a Markov Decision Process (MDP) (Sutton& & Barto 2018). MDP is four-tuple (S, A, R. P). where S and A represent the sets of states and actions respectively. The agent interacts with the environment at each time step t by observing the current state 8, E S, choosing an action a; to execute, receiving an immediate
3

---

Published as a conference paper at ICLR 2023
Trace
Trace Trace
Sys
$10
(a) Concrete state transitions. (b) Grid-based state abstraction. (c) Abstract state transitions.
Figure 2: Take 2-dimensional concrete state space as example. Concrete states can be labeled by the ID of grids. For example, In trace 1, state 8;-1 is abstract state &1. Concrete state 8:+2 in trace 1 and 8 in trace are located in the same grid; thus, they share the same abstract state 813 (red ones). In this way, trace can be represented as (St, 81, 87, 817, 813).
reward r2 R( St; 0x) after doing de, and transferring P(.) are the reward function and state transition function respectively.
state 81+11 P(se, The R()) and
The agent selects action a (s)) to execute according to a policy -T-) and interacts with the environment to generate a trace, [[50, 4o, ro),... (8t, ax, (t,,))..... where the subscripts denote different time steps. The return of each trace is defined by Σ 7're, where rewards are discounted by factor y E [0, 1). RL generally aims to find an optimal policy to maximize the returns.
The state-action value function: (st o²) = Ex ETT t== 7'relst, ay is widely used in many RL algorithms. In value-based approaches ge.g.. DQN (Mnih et al. 2013)), action with maximal Q=, a) value will be selected, and these approaches have achieved great success in discrete action space environments. The policy-based approaches such as A3C (Mnih et al. 2016) are more efficient and suitable for continuous action spaces than value- approaches, which generate a policy distribution and sample actions from it instead of iterating the infinite action space. DDPG (Lillicrap et al., 2016) is used in continuous action setting to improve the sample efficiency over the vanilla actor-critic, in which the deterministic means the Actor can directly output the actions instead of computing a probability distribution over actions. Twin Delayed DDPG (TD3) (Fujimoto ct al., 2018) tackles the over-estimation of state values. In this work, we build our episodic control in continuous action space based on TD3 (Fujimoto et al. 2018).
4 METHODOLOGY
This paper proposes an effective and efficient episodie control framework, NECSA. Figure T shows the main procedure of our framework. We have two additional modules: (1) grid-based abstraction to convert the concrete states to abstract ID (i.e., the & as noted later); (2) a key-value-manner episodic memory module to store the abstract states with the state measurement (i.e., the reward confidence scores c; as mentioned later). The traces are revised based on the state measurement and further flow the replay buffer for policy optimization. NECSA is highly supplementary, which can be applied to the general reinforcement learning paradigm.
4.1 GRID-BASED BASED STATE ABSTRACTION
The K --dimensional state space R contains infinite concrete states, each state s; is represented as (s?,..., K ). Each component s in the m-th dimension satisfies s." [Im um]. where the i, and
Um are the lower and upper boundaries, respectively. We split each dimension [m,. um into N equal intervals. Thus the concrete state space R² will be divided into N grids as follows:
m = Im + 12 X Um Im Imm + (n + 1) x
Um 1m
(1)
N
N
4

---

Published as a conference paper at ICLR 2023
L-ardrr
PI-2
61-1
8143
2arder
3-order
Figure 3: A schematic diagram of the multi-step analysis. We slide windows with different lengths to extract patterns.
where e, represents the n-th interval on the m-th dimension in the state space. this way, (I) each concrete will fall into grid; (2) all the concrete states 8; which fall into the same grid can be identified as in the same cluster; (3) each cluster (i.e. each grid) can be represented by a unique abstract state 8:
= ( E E E [0, MJ, m E K])
Figure 2 is schematic diagram of grid-based clustering, in which the infinite concrete state space is converted into the finite discrete state space. The environment determines the In and Umn is worth mentioning that we can either perform the abstraction on concrete states or state-action pairs. As experimental results suggest, abstracting state-action pairs can perform better than focusing on concrete states. Take Walker2d-v3 as example; the state vector's s shape is (1,17), and the action vector is (1,6). Then, we combine the state and action vectors into a state-action pair with a shape of (1,23). The boundaries of the state and action vectors are [-10,10] and [-1.1], respectively. For instance, we obtain the fixed lower bounds as (-10,-10, -10, -1, -1, ..., -1). finally, we abstract the state-action pairs by grid-based clustering. Each dimension of state-action pair is split into equal intervals.
In general, the high-dimensional concrete (-action pairs) would increase the difficulty and complexity of state abstraction. Inspired by Gaussian random projection (Dasgupta 2013). we apply random matrix to reduce the dimensions of state (-action) vectors. When creating the matrix, we ensure that the values of the matrix elements follow the Gaussian distribution and that the value scope [-1.1]. By multiplying the state (-action) vector (e.g., (1,376) in Humanoid-v3) random matrix with shape of (376,24), we can obtain a smaller state (-action) representation vector as (1,24). The Gaussian random matrix is initialized the beginning of the training. Then, would remain the same during the training. Finally, all the state (-action) vectors are projected to smaller one by a common Gaussian random matrix.
Gaussian
Note that abstracting images directly can be inefficient in Atari games. Pixel-based image vectors consist of multiple channels, which can be unsuitable for abstraction using grid-base methods. Therefore, we use the hidden outputs for abstraction, considering that (1) the hidden outputs are natural features of images but relatively smaller than the raw images, and (2) hidden outputs reflect the states of actions. Moreover, incorporating hidden outputs with episodic control is also effective in previous episodic control approaches such as EVA (Hansen et al. 2018).
4.2 EPISODIC MEMORY WITH MULTI-STEP ANALYSIS AND STATE MEASUREMENT
Figure 3 shows the logic of extending the state abstraction to multi-step patterns. The abstract patterns are extracted by sliding a N-step window on each trace. We treat N-step continuous abstract states as whole pattern. Moreover, we count the patterns iteratively and orderly, where (8i, 8 8442) and (6++1, 81+2, 51+33 are treated as different patterns.
To revise the state (action) values (i.e. Q) estimation, previous episodic control-based approaches usually leverage shift of episodic returns to correct the critic Q-value. Such approaches can achieve better performance while requiring domain-specifie knowledge of corresponding DRL algorithms, model structure reform, and engineering work efforts. Furthermore, measuring states by the statisties of Q valuues is only applicable in one-step episodic memory. With multi-step patterns, propose a state measurement named reward confidence scores. The score c; represents the expectation of the episode return when occurs. Although the scores similar to state (-action) values in terms
5

---

Published as a conference paper at ICLR 2023
of the definitions, they stand for different semantics. State (action) values represent the forwarding rewards after the state 3,, but the scores measure the episode reward over the whole trace.
We design simple key-value manner episodic memory C' based on state abstraction and mcasurement. Each item in the episodic memory is indexed by the 8; with three values: the current score e, the historical total episodic rewards & earned by the traces which contain the 8;, and the total number of occurrences 7) of 8, The following equation is the implementation of computing scores:
Er E Er, 7 7= m +1,
N ==1,
C4 E,, C. E,
if $
(3)
otherwise,
7
Where the Er is the final episodic return of the trace, which contains 8; In this way, memory buffer can efficiently record past experiences and update the scores. Our episodic memory enables three operations: ADD, LOOKUP, and UPDATE. ADD is the operation to store the & into C. LOOKUP returns score C for & by taking O(1). UPDATE is to revise the a of &, Moreover, the episodic memory enables the normalizing of the scores to [0,1] and the average of the score o; is adopted as the intrinsic reward for abstract pattern 8
Algorithm 1 NECSA.
Input: M: DRL model, E: Environment, B: Replay Buffer
Input: C: An episodic memory to record each 8; and the score G;
Output: M: A tuned DRL model
Initialization: i +- 0, S, R. D 0
2: while TootoTot_seeeee
do
3: 5; - statee 0g + action, r; + reward, d; + done S.append(s:)). (a)) A.cpenda D .append(d.)
4:
5:
& + --State_Al Sttate_Abstract((:.1 a,)
6:
S.append($:)
7:
G Inquire_Scoren Score(s, C)
8:
i + Reward Saavard_Reeisiooffrr R.append(r.)
9:
10:
B. B.add(si,, fi)
11:
if de is true then
12:
C U Seeee_SooorrSS.. C) R.S.A.R,D+- end if
13:
14:
i+i+1
16:
M MrTrranmMM, B. s.somple())
end while
4.3 EPISODIC CONTROL- BASED LEARNING
As inspired by previous episodic control-based approaches, infer that statistic-based measure- ment of statc-action pairs can helpful reference to revise the estimation of state (-action) values by the critic network (Lin et al. 2018 Kuznetsov & Filchenkov 2021). The of our method is to measure the abstract patterns by scores and make the agent generalize the high-score experiences. Previous work like reward shaping (Harutyunyan
al., 2015 Laud DeJong 2003 Devlin & Kudenko 2012 Burda et al. 2018) helps the policy incorporate domain knowledge into policy natural to reshape the reward with score-based intrinsic reward to
optimization. Therefore, revise the policy. Formally, the revised reward f; + A, where is the return of the original reward function, A is the intrinsic reward (computed based on the reward confidence scores) which represents the semantics for improving the rewarding mechanism. We perform reward revision for each pattern as follows:
ΣM Gu
f: = + (c
XE,
(4)
M

---

Published as a conference paper at ICLR 2023
where the ć is the revised reward hased on Ti- M is the total number of abstract patterns. ΣM M
the average of all the scores. The term A will be less than 0 if the 8; score is less than the average. Thus the corresponding concrete state will be punished. The state will be encouraged than O. The agent will earn more rewards if it passes through 8,. In word, the lower the score is, the more the pattern is punished. is a hyperparameter that helps control the magnitude of punishment and encouragement.
is greater
We implement NECSA Algorithm! | We use module named State Abstract in line 5 which can covert the concrete states to abstract patterns run-time. While tuning the model, scores can be inquired from the episodic memory C' in line 7 and the reward will be revised in line We also added a module named Update_Scor _Score line 12] which helps calculate the scores for the abstract patterns S and update the scores in as each termination an episode. The revised rewards will be stored in the replay buffer B. Finally, the policy will be updated with the sampled data from the B
in line 16
5
EXPERIMENT
Walker2d-v3
Hopper-v3
Humanoid-v3
0..0
TED
10.00
TE3
CAR
7214
2500
2000
3500
123
200
500
300
300
255
506
750
1830
Alien
Breakout
Enduro
3000
144
$100
CEM
Destege Rapuum
2000
SOM
SOCIA
200
400
200
Stopa
Figure 4: The evaluation of each approach on MuloCo and Atari tasks. More evaluation results are in Appendix.
5.1 EXPERIMENT SETUP
We conduct the experiments on nine MuJoCo tasks and six Atari games in OpenAl gym (Brockman
al., (016)) domains. For continuous control tasks in MuJoCo, we select four baselines including
EMAC (Kuznetsov & Filchenkov 2021). GEM (Hu et al. 2021 DDPG (Lillicrap et al. 2016) and
TD3 (Fujimoto et (018)) for comparison. We also compare NECSA four baselines, including
DQN (Mnih et al. 2013). Rainbow (Hessel et al., 2018). EVA (Hansen et al. 2018) and GEM (Hu al. 2021) on Atari games, which use image- based states and discrete action spaces. EMAC is of-te-of-the-arr episodic control approach that proved effective on continuous control tasks. EVA is effective on discrete action spaces by performing ephemeral adjustments of Q-values to impact the parametric value functions. GEM integrates neural network to generalize episodic experiences, enabling fast episodic memory retrieval. GEM can be applied to both continuous and discrete action spaces.
5.2 EVALUATION RESULTS
Figure 4 shows the main evaluation results of each approach MuloCo and Atari tasks. Note that more evaluation results are in the Appendix A.2. In our experiments, we set the length of the multi-step abstract pattern m=3. As shown in Figure 4 our approach NECSA significantly
7

---

Published as a conference paper at ICLR 2023
outperforms the baselines on all tasks. Table and Table in the Appendix are the average returns and standard deviations of the learned policies over multiple random seeds. Overall, we found that (1) NECSA is the most sample-efficient algorithm on various tasks, while other algorithms only establish good performance on the part of tasks; (2) NECSA performs better on relatively complex tasks (e.g., high-dimensional states and image-based states). Such results prove that NECSA is scalable episodic control on continuous and discrete control tasks.
Take Humanoid-v3 an example, 376-dimensions state space with five grids on each dimension generates a 5376 abstract state space, which is impossible to efficiently store and retrive in the episodic memory. On Atari games, we take the hidden outputs after the convolutional neural network layers of the policy network to represent the image states (-action pairs). However, the dimension of hidden outputs also unsuitable for grid-based abstraction. Gaussian random projection can be a promising solution to make the concrete states (or hidden outputs) smaller (Pritzel et al. 2017; Kuznetsov & Filchenkov, 2021). Therefore, we perform dimension reduction of the concrete state vectors to 1 24 by random projection and divide each dimension into fixed intervals. The results show that the random projection reduces dimension without significant side effects, thus making NECSA a scalable episodic control on high -ineessinnni continuous control and image-states tasks.
The experimental results on MuJoCo tasks and Atari games prove that NECSA is effective on various DRL tasks. We performed in de-tep ablation studies on the critical parts of NECSA in the following section. Besides, we have conducted detailed hyperparameter analyses. Note that the hyperparameter analyses are in Appendix A.3. We also proved that NECSA is effective continuous control tasks with image-based inputs. The related experiments are conducted on DMControl (Tunyasuvunakool al. 2020) tasks. Please refer to Appendix A.4 for details.
5.3
ABLATION STUDY
Walker2d-v3
Hopper-v3
Alien
0:40
ROCSA- ateg
10.30
MECSA_2-NN Fu
2000
1000
2500
2000
1500
200
Stepe
Figure 5: The evaluation of performance between one-step and m-step NECSA.
One of the most critical parts of this paper is to adopt multi-step analysis of past experiences. To better demonstrate the effectiveness of the multi-step episodic control, we compare the performance between different multi-step settings. The results Figure 5 show that the three-step NECSA outperforms one-step and two-step settings. In our evaluation, the default setting of NECSA multi- step (m) analysis is set to 3. The reason is that longer patterns cause the exact matches to become exceedingly rare, which makes episodic control less helpful for improving performance.
Walker2d.v3
Hopper-v3
Alien
-1:0
19.99
Soore
2000
3500
-2:0
3000
2530
2000
20.00
Averpe
2000
Time Strpe D1e0
Time Strp0 (1xb)
Tinle Stepe (led)
Figure 6: The comparison between measuring the abstract state by scores and Q-values.
We also study the effectiveness of reward confidence scores. We use scores to measure each state- action pair, although previous works mainly focus on the state-action values (i.e. the Q-values). Specifically, we use the average of scores and Q-values (Lin al. 2018 Kuznetsov & Filchenkov
8

---

Published as a conference paper at ICLR 2023
2021 for each abstract state (pattern) to compute the intrinsic reward. Note that cannot directly attain the Q-value of a multi-step abstract pattern. We instead use the average Q value of the corresponding concrete states (Lin et al. 2018). The results in Figure O show that measuring the state-action pairs through scores (NECSA A_SCores) can lead to better sample efficiency than using Q-values (NECSA Q-values). We claim that such state measurement is effective and necessary since the scores contain the overall impact of an abstract on a whole trace. Furthermore, such a difference makes the scores more comprehensive since reference the historical impact on the abstract states.
We conclude that NECSA performs better than the state-of-the-art episodic control-based approaches based on the experiments. State abstraction-buie based episodic memory enables more advanced analysis of past experiences. The scores of state abstractions are valuable, and the rationale for state measure- ment and the multi-step analysis of state transitions can significantly improve the performance.
6 DISCUSSION
We adopt grid-based abstraction instead of KNN. Although kNN can group concrete states into unique IDs, it cannot update episodic memory in real-time. Moreover, kNN does not support inquiries about the state measurement of multi-step patterns. We extend the episodic control to multi-step analysis, which is one of the most important contributions of NECSA. Overall, we select grid-based abstraction (clustering) instead of KNV for (1) more efficient state abstraction and (2) multi-step abstract pattern analysis.
Although NECSA is sample efficient, there still exists room for improvement. First of all, the state abstraction strategy might cause variances or errors. For example, we divide each dimension by the same number of intervals, though sometimes the value scale of each dimension is not the same. Therefore, some concrete states might not be labeled by abstract ID. Based on prior knowledge of the state space. we infer that possible solution may be automatically divide each dimension into appropriate but not fixed intervals.
The motivation behind NECSA is to construct more comprehensive episodic memory. We consider that past experiences need to be further explored, and more valuable information could be obtained and exploited. Furthermore, exploring latent semantics based on the abstraction- episodic memory promises to improve the sample efficiency. In addition, NECSA is highly scalable and can be applied to various DRL algorithms and tasks.
7 CONCLUSION AND FUTURE WORK
We propose NECSA, novel state abstraction -based neural episodic control approach improve DRL's sample efficiency. We transform dense concrete state-action pairs into abstract patterns, which enables efficient storage and retrieval of episodic data. We also perform multi-step analysis of the pattern transitions to enhance their performance. Furthermore, we propose a novel state measurement metric, reward confidence scores, which can be incorporated with extrinsic rewards to accelerate policy optimization. The evaluation results prove that our approach is more sample efficient than state-of-the-ar episodic control approaches.
We believe that more advanced research can be conducted based on the state abstraction, state measurement, and multi-step analysis of state transitions, including (1) abstracting the behaviors of the policy via state abstraction since can build an automaton base on the abstraction; (2) analyzing the state transitions and topological relationships multi-agent tasks (Zheng et al., 2018 2021b);
(3) applying approach to model- based reinforcement learning with dynamic planning. We leave these topics for future work.
ACKNOWLEDGMENTS
This work was supported in part by JSPS KAKENHI Grant No.J919004086 and No.JP20H04 168, JST-Mirai Program Grant NMMMMI028 JST SPRING Grant NoJJPMSPP2136, as well as Canada CIFAR AI Chairs Program, the Natural Sciences and Engineering Research Council of Canada (NSERC No.RGPIN
-GGAA--0021-0034, No. NG.DG 2021-00019), the National Natural Science Foundation of China (Grant No.62 No.62106172) the "New Generation of Artificial Intelli-
CCGPIN-2021-00 200220022222222 -02549,

---

Published as a conference paper at ICLR 2023
gence" Major Project of Science & Technology 2030 (Grant No.20222D00114422), and the Science and Technology on Information Systems Engineering Laboratory (Grant No. www.D22222235500000,, No. No.WDDZC200055504007
REFERENCES
Charles W. Anderson and Stewart Crawford-Hines. Multigrid q-learning. 1994.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. A brief survey of deep reinforcement learning. arXiv preprint
2017.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z. Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv: 04460, 2016.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/1606.01540, 2016. URL http:http/axiiii/ org/
abs/1606 01540
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 120...28944 2018.
Yushi Cao, Zhiming Li, Tianpei Yang. Hao Zhang, Yan Zheng. Li, Jianye Hao, and Yang Liu. GALOIS: boosting deep reinforcement learning via generalizable logic synthesis. In Advances in Neural Information Processing Systems, 2022.
Sanjoy Dasgupta. Experiments with random projection. arXiv preprint 1301.3130133899 2013.
Sam Michael Devlin and Daniel Kudenko. Dynamic potential potential-based based reward shaping. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pp. 433 440. IFAAMAS, 2012.
James Dougherty, Ron Kohavi, and Mehran Sahami. Supervised and unsupervised discretization of continuous features. In Machine learning proceedings 1995, pp. 194-202. Elsevier, 1995.
Xiaoning Du, Xiaofei Xie, Yi Li, Lei Ma, Yang Liu, and Jianjun Zhao. Deepstellar: Model-bard -base quantitative analysis of stateful deep learning systems. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, pp. 477-487, 487,20141 2019.
E. B. Dynkin. Markov processes, pp. 77-104. Springer Berlin Heidelberg, Berlin, Heidelberg, 1965. ISBN 978-3-662-00031--,
doi: 10. 1001/979 0111//7788--62--0031111 URL htttps:///ii.rrge
1007/978 662 00031
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Tanmay Gangwani, Yuan Zhou, and Jian Peng. Learning guidance rewards with trajectory-space smoothing. Advances in Neural Information Processing Systems, 33:822-832, 2020.
Marek Grzeš and Daniel Kudenko. Multigrid reinforcement learning with reward shaping. In International Conference on Artificial Neural Networks, pp. 357-366. Springer, 2008.
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. arXiv preprint arXiv:2010000//93, 2020.
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, André Barreto, and Charles Blundell. Fast deep reinforcement learning using online adjustments from the past. Advances in Neural Information Processing Systems, 31, 2018.
Anna Harutyunyan, Sam Devlin, Peter Vranex, and Ann Nowé. Expressing arbitrary reward functions as potential-based advice. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 29, 2015.
10

---

Published as a conference paper at ICLR 2023
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 artificial intelligence, 2018.
Hao Hu, Jianing Ye, Guangxiang Zhu, Zhizhou Ren, and Chongjie Zhang. Generalizable episodic memory for deep reinforcement learning. arXiv preprint arXiv:2103: 06469, 2021.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 179-188.
Lille, France, 07-09 Jul 2015, PMLR. URL httpps://prcceeeeeeheets
mll wwwpppeesssvv.e
jiang15. html
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, al. Model-based reinforcement learning for atari. arXiv preprint urXiv:7903 1903.0034, 2019.
Igor Kuznetsov and Andrey Filchenkov. Solving continuous control with episodic memory. arXiv preprint arXiv:2106. 088.0882,... 2021.
Adam Laud and Gerald DeJong. The influence of reward on the speed of reinforcement learning: An analysis of shaping. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pp. 440-447, 2003.
Alessandro Lazaric, Marcello Restelli, and Andrea Bonarini. Transfer of samples in batch rein- forcement learning. In Proceedings of the 25th international conference on Machine learning, pp. 544-551, 2008.
Hung Le, Thommen Karimpanal George, Majid Abdolshah, Truyen Tran, and Svetha Venkatesh. Model-based episodic memory induces dynamic hybrid controls. Advances Neural Information Processing Systems, 14:30313-30325, 2021.
Hung Le. Majid Abdolshah, Thommen K George, Kien Do, Dung Nguyen, and Svetha Venkatesh. Episodic policy gradient training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7317-7325, 2022.
Máté Lengyel and Peter Dayan. Hippocampal contributions to control: the third way. Advances in neural information processing systems, 20, 2007.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, In ICLR (Poster), 2016.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. arXiv preprint arXiv: 1805.07603 2018
Xiaoteng Ma, Yiqin Yang. Hao Hu, Qihan Liu, Jun Yang, Chongjie Zhang, Qianchuan Zhao, and Bin Liang. Offline reinforcement learning with value-based episodic memory. arXiv preprint arXiv:21 10..210..099.... 2021.
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 71, 2004.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:1312.5602, 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Thomas M. Moerland, Joost Brockens, and Catholijn M Jonker, Model- based reinforcement learning: A survey. arXiv preprint 200.:20000.11222 2020.

---

Published as a conference paper at ICLR 2023
Jason Pazis and Michail G Lagoudakis. Binary action search for learning continuous-action control policies. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 793-800, 2009.
Rafael Pinto. Model-free episodic control with state aggregation. arXiv preprint wwXiv:2008.09663 2020.
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.
Ruimin Shen, Yan Zheng, Jianye Hao, Zhaopeng Meng, Yingfeng Chen, Changjie Fan, and Yang Liu. Generating behavior-diverse game ais with evolutionary multi-objective deep reinforcement learn- ing. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 3371-3377 ijeai.org, 2020.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yunhao Tang and Shipra Agrawal. Discretizing continuous action space for on-policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5981-5988, 2020.
Andrea Thomaz and Cynthia Breazeal. Teachable robots: Understanding human teaching behavior to build more effective robot learners. Artificial Intelligence, 172(6-7):716-
2008.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-baser control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Pedro A Tsividis, Thomas Pouncy, Jaqueline L Xu, Joshua B Tenenbaum, and Samuel J Gershman. Human learning atari. 2017 AAAI spring symposium series, 2017.
Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, 6: 6:10002,, 2020.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference Machine Learning, pp. 3540-3549, PMLR, 2017.
Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu. Tianshou: A highly modularized deep reinforcement learning library. arXiv preprint ar
2021.
Xiaofei Xie, Lei Ma. Felix Juefei-Xu, Minhui Xue, Hongxu Chen, Yang Liu, Jianjun Zhao, Bo Li, Jianxiong Yin, and Simon See. Deephunter: soverage-guides fuzz testing framework for deep neural networks. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 146 157, 2019.
Zhuo Xu, Jianyu Chen, and Masayoshi Tomizuka. Guided policy search model-based reinforcement learning for urban autonomous driving. arXiv preprint 2XXv:2005500376, 2020.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Mastering visual continuous control: Improved data-augmented reinforcement learning. arXiv preprint arXiv:1107006645, 2021.
Zhao-Heng Yin and Wu-Jun Li. Toma: Topological map abstraction for reinforcement learning.
arXiv preprint arXiv:2005.0606/ 2020.
Yang Yu. Towards sample efficient reinforcement learning. In ISCAI, pp. 5739-5743, 2018.
12

---

Published as a conference paper at ICLR 2023
Peng Zhang, Jianye Hao, Weixun Wang, Hongyao Tang, Yi Ma, Yihai Duan, and Yan Zheng. Kogun: Accelerating deep reinforcement learning via integrating human suboptimal knowledge. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pp. 2291-2297. ijcai.org, 2020.
Zhizheng Zhang, Jiale Chen, Zhibo Chen, and Weiping Li. Asynchronous episodic deep deterministic policy gradient: Toward continuous control in computationally complex enviromments. IEEE transactions on cybernetics, 51(2):004-61,, 2019.
Lulu Zheng, Jiarui Chen, Jianhao Wang, Jiamin He, Yujing Hu, Yingfeng Chen, Changjie Fan, Yang Gao, and Chongjie Zhang. Episodic multi-agent reinforcement learning with curiosity-driven exploration. Advances in Neural Information Processing Systems, 34, 2021a.
Yan Zheng, Zhaopeng Meng, Jianye Hao, Zongzhang Zhang, Tianpei Yang, and Changjie Fan. A deep bayesian policy reuse approach against non-stationary agents. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 962-972. 2018.
Yan Zheng, Changjie Fan, Xiaofei Xie, Ting Su, Lei Ma, Jianye Hao. Zhaopeng Meng. Yang Liu, Ruimin Shen, and Yingfeng Chen. Wuji: Automatic online combat game testing using evolutionary deep reinforcement learning. In 34th IEEE/ACM International Conference Automated Software Engiieeriigg ASE 2019, San Diego, CA, USA, November I 11-5, 2019, pp. 772-784. IEEF, 2019.
Yan Zheng, Jianye Hao, Zongzhang Zhang, Zhaopeng Meng. Tianpei Yang, Yanran Li, and Changjie Fan. Efficient policy detecting and reusing for non-stationarity in markov games. Auton. Agents Multi Agent Syst. 35(1):2, 2021b.
Yan Zheng, Yi Liu, Xiaofei Xie, Yepang Liu, Lei Ma. Jianye Hao, and Yang Liu. Automatic web testing using curiosity-driven reinforcement learning. In 43rd IEEE/ACM International Conference on Software Engineering, ICSE 2021, Madrid, Spain, 22-30 May 2021, pp. 423-433 IEEE, 2021c
Derui Zhu, Jinfu Chen, Weiyi Shang, Xuebing Zhou, Jens Grossklags, and Ahmed E. Hassan. Deepmemory: Model-based memorization analysis of deep neural language models. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2021. doi: 10.1 121109//SE5512244000 1977871.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In ICLR, 2020.
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 COMMON HYPERPARAMETER AND SETTINGS
Our hyperparameter settings listed in Table I and Table 2 In addition, directly evaluate the program released by the authors of EMAC (uuznetoov Filchenkov 202 J. EVA (Hansen et al. 2018), and GEM (Hu et al. 2021). We also adopt the implementation of DDPG, TD3, DON, and Rainbow in (Weng et al. (021). For MuJoCo tasks, the neural network consists two hidden layers. The size of each layer is 256. The activation unit ReLU. Both the Actor and Critic networks share the same structure. For Atari tasks, we use a three-layer convolution neural network head and a fully connected layer output the Q-values of each action. The specific parameter values are listed in Table More details are available in the code repository.
Hyper- paper--aramater
NECSA
Hyperr-paaaatter
NECSA
Critic Learning Rate
3c-4
Learning Rate
lc-4
Actor Learning Rate
3c-4
Optimizer
Adam
Optimizer
Adam
Replay Buffer Size
100000
Replay Buffer Size
100000
Batch Size
32
Batch Size
100
Discount Factor
0.99
Discount Factor
0.99
Filter Sizes
[8, 3]
Episode Length
1000
Filter Strides
[4, 2. 1]
Exploration Policy
N(0, 0.1)
Channels
[32, 64, 64]
Table 1: Hyperparameters for MuJoCo tasks.
Table 2: Hyperparameters for Atari games.
A.2
THE RESULTS OF NECSA AND OTHER BASELINES ON MuJoCo AND ATARI TASKS.
Table 3: The average returns of learned policies on MuJoCo tasks.
Task Name
DDPG
TD3
EMAC
GEM
NECSA
Walker2d
387.732:4.33
1756.094:44.776
2338.2442 2338.24-:215.81
1224.94+-18348
276..0
Hopper
1180.641276.70
2411.154:323356
2347.98 98:799799.9997
1150.244:13.52
3026.57 2922_.7
Humanoid
4311,9-+139.11
3858. 7358.077773391
150 150.324-6555
2380.914757,
5029.99-1:208.1
Ant
811.53::221.40
5223.944::20.36
789.99+ 04
4107 4107.28:t:24.35
15:6.44:::336225
HallCheetah
11314.36::24..11
10120.34
11052.82:1669.1
11458.70:113..1
12097,91 152.
Swimmer
96.73:1:3.10
49.82-15.56
86.54-122.13
126.22-1:2.700
149.63116.69
Reacher
-4.05=0.14
-.01
-5.01
-5.99 39
-3.97-1-0.05
Peadulum
1000.0:::44.7
$35.97+:56.50
1000.0:t:2.550
655.48:2101. 101.19
1000.0:1:8..11
DoublePendulum
9316.833-88885
9333, 194222.444
9327.174:158.00
5858.88 8858.88-18881 ,55
9359.33--223..99
We adopt the implementations of DDPG, TD3, DQN, and Rainhow in Tianshou (Weng et al. 2021)
The implementation of NECSA is based on TD3. We use the public replicate package of the respective baselines for experiments. We run each experiment with five different random seeds counteract the randomness and compare the average performance over respective training steps. All the experiments were run on powerful servers with CPU (Intel(R) Core(TM) 19-10XXXX CPU @ 3.30GHz), and GPU(NVIDIA Corporation GA102GL [RTX A6000]) with 128GB RAM.
We have evaluated NECSA on nine MuJoCo tasks and six Atari games total. Table and Table are the performance and standard deviation of all the learned policies of the respective approaches. Figure 7 is the performance trends of all the approaches on different tasks (i.e., except the results we have reported in Figure 4.. Based on the above results, we found that the learned policies of NECSA achieve the highest performance. Most of the improvements against other approaches are significant. On the tasks such as InvertedPendulum-00 InvertedDoubleeendduiie NECSA reaches the same performance or slightly outperforms the baselines. The reason is that such tasks are relatively easy than others. Therefore NECSA and other baseline approaches achieve state-of-the--e performance in fewer training steps. Overall, the evaluation results demonstrate that NECSA is effective and sample-efficient on MuloCo and Atari tasks.
and Reacher-v2,
14

---

Published as a conference paper at ICLR 2023
Table 4: The average returns of learned policies on Atari games.
Task Name
DQN
Rainbow
EVA
GEM
NECSA
Alien
1188.734:8.37
1488. 14=414
1432.22-+ 109.17
1030.67:-48.17
1725.56:::83.3
Breakout
61. 21.22-444011 0.0
385 02:00.2:3
381. 15.63
220.73:4:4.00 00
412.30:1:9.94
Enduro
748.45-449.008
424.62=45.77
733.50==24.98
729 019.60---99877
1147:48:::299
MsPacman
1997.72::122.55
2075. 16: 106.000.000
1991 78-7771177
1990811-114433
2205.28:181..3
10817.71.1666..0
9617.25
1492.488
112659.28 1.71.99
Spacefnvaders
629.85:4:2.62
810. 42:
799. 799.06:122.32
686.25:4:53366
28.06
Ant-v3
HalfCheetah--33
Swimmer-v3
TE3
5000
CDN
3000
3000
BPA
253
358
150
Staps D42))
Stage (1a2)
Reacher-v2
InvertedPendulum--2
InverteedDoubleeenddlluy
3000
2000
line snape (Led)
MsPacman
Obert
Space
7V00
3300
2000
66'
200
400
Time Stase (1e4s
200
Figure 7: The evaluation of each approach on other MuJoCo and Atari tasks.
A.3 SPECIAL HYPERPARAMETER AND SETTINGS IN NECSA
During the experiments, we evaluated different settings of several hyperparameters, which can help us better understand the effectiveness NECSA. We discuss four settings and answer the following questions through detailed experiments:
1. Should we abstract the state or state-action pairs (or the hidden outputs)?
2. What is the effect of discrete state space grid numbers on performance?
3. How control the magnitude of revising environment rewards via intrinsic reward (i.e., reward confidence scores)?
4. How do the backbone algorithms affect the performance of NECSA?
Figure g shows the performance of abstracting state and state-action pairs. NECSA state is the curve that only abstract the concrete states (or the static features of the image states), On the other hand, NECSA state-action means that we abstract state-action pairs. It reveals that abstracting the state-action pairs can significantly improve performance MuJoCo tasks. The reason is that abstracting state-action pairs can involve more information for modeling the policy than just focusing states.
15

---

Published as a conference paper at ICLR 2023
Walker2d.v3
Hopper-v3
Alien
3000
3000
254
1ame Staps (1ua))
19me Strpps (1n.))
Stepo (led)
Figure 8: Comparison between abstraction of the state, state-action pairs, and hidden outputs.
NECSA hidden means that the hidden outputs of the policy network for abstracting. Using the hidden outputs on Atari games can also outperform the performance of just abstracting the states. The hidden outputs natural features of images but relatively smaller than the raw images. Moreover, the hidden outputs reflect the states of actions. Therefore, we infer that using hidden outputs for abstraction shares the same benefits using state-action pairs.
Figure/])hoore the performance under different abstraction granularities. Grid-N means we divide each dimension state-action pairs into N equal intervals. The results show that grid numbers 8 and 10 are the best abstraction choices in Walker2d-v3, Hopper-v3 and Alien. Our evaluation is limited to 10 grids since a greater grid number causes the exponential growth of the abstract number, which is very meenory-onnuuiing We found that more grids cannot always achieve better performance. For example, Walker2d-v3, 8-grids abstraction outperforms 1 10-grids. The reason that although more grids can cluster similar concrete states more accurately, the grid number of the abstraction becomes smaller, the scores of abstract states and patterns are less representative. For MuJoCo tasks, set the grid numbers to 10 for Swimmer-y3 and Hopper-v3, and for other tasks, respectively. For Atari tasks, we uniformly set the grid numbers to 5.
Walker2d-v3
Hopper-v3
Alien
4000
gio-15
gris
3500
3000
20:0
3000
152
200
060
206
300
-06
Figure 9: Comparison between different granularities of gridd-assed abstraction.
Figure shows how the parameter e in Equation 4 influences the performance. The results suggest two major conclusions: (1) in 10.1, 0.2] is the best choice for controlling reward shaping in Walker2d-v3 and Hopper-v3, respectively; (2) value for that is greater or smaller will reduce performance. The reason is that a smaller reduces the impact of scores, and a greater e will increase the weight of state evaluation and completely reform the rewarding mechanism. In addition, for MuJoCo tasks, we set e = 0.15 for Swimmer-v3 and 0.2 for other tasks, We set e 0.1 for all the Atari games.
Walker
Hopper-v3
Alien
176
2002
agiike Aue
375
35
3000
3200
apelan/33
Time Stato
Stepo
Figure 10: Comparison of performance between different granularities of revising rewards.
16

---

Published as a conference paper at ICLR 2023
Figure I1 shows how the backbone algorithms affect the performance of NECSA. In this evaluation, we build NECSA on TD3 and DDPG and compare the performance with the primary algorithms. The results show that (1) algorithms can achieve better sample efficiency by incorporating with NECSA and (2) the backbone algorithms affect the performance NECSA. A. For example, in Walker2d-v3 and Hopper-v3, TD3 is sample efficient than DDPG. In Alien, Rainbow outperforms DQN. After applying NECSA to these algorithmss, the comparison results remain the same trend. Such conclusion demonstrates that NECSA is scalable and effective on different backbone algorithms.
Walker2d.v33
Hopper-v3
Alien
12:0
TE2
15.00
SECIA,DORC
2000
10,3
10:01
2500
20300
Arence
3000
2000
MECAA 201
Staps D422
Time Shaps (1a3)
Stago (lar))
Figure 11: Comparison of performance between building NECSA on different backbones.
A.4 PERFORMANCE OF APPLYING NECSA TO DMCONTROL TASKS
Figure 12 shows the performance of NECSA DMControl Tunyasuvunakool et al. 2020) tasks. In this evaluation, we build NECSA on DrQ-v2 Yarats et al. 202 1), an approach to solve continuous tasks with image-based states. NECSA outperforms DrQ-v2 on Walker-Wal and Hopper-Stand, and achieves the same performance on Sarpole-BBlance The results show that (1) NECSA improves the sample efficiency of DrQ-v2 and (2) NECSA is general and effective for DRL tasks with image-based states and continuous action spaces.
Walker-Walk
Hopper-Stand
Cartpole-Bar Baalle-BBlaccee
1000
730
231 PAALETT
Figure 12: Performance of applying NECSA to DMControl tasks.
Density of 1-step state visiting
Density of 2-step state visiting
Densily of state visiting
Figure 13: Density of abstract state visiting times Walker2d-v3.
A.5 ANALYSIS OF STATE VISITING DENSITY
We plot the density of state visiting times in Figure 13 Take Walker2d-v3 as an example. The 1-step NECSA generated 198,613 abstract states, the 2-step NECSA generated 282,717 abstract patterns, and the 3-step NECSA generated 377,629 abstract patterns. In 1-step setting, 163,273 abstract patterns were visited by only one time, and 35,340 were visited more than one time. In 3-step setting, 372,253 abstract patterns were visited one time, and 5,376 of them visited more than
17

---

Published as a conference paper at ICLR 2023
time. All 5,376 multi-timer visited patterns were visited 27,747 times, more than the oe-timee visited pattern.
The density plot shows that the number of 1-time visits increases in multi-step statr abstraction. However, the performance in Figure that multi-step analysis can still achieve the best sample efficiency in settings. Therefore, we assume that the multi-times visited patterns played an essential role in enhancing the sample efficiency. Neverthleass, we assume that there exists better choice of the abstraction steps (e.g., S-step. 10-step). Due the abstraction state aprsity issue, might need a novel state encoder instead of grid-based abstraction. We leave the above assumption as future work.
18


Reviews:
[{"review_id": "lNNNmucDFh", "reviewer": "Reviewer_D6zD", "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": "The paper introduces a state abstraction method for neural episodic control. States or state-action pairs are mapped to grid coordinates and dimensionality is reduced further by random projections. The method is suitable for state spaces with a limited number of independent dimensions. The method provides better results than the baselines on Mujoco.", "summary_of_the_review": "The paper is well-written, and makes for an enjoyable read. Contributions are backed by relevant experiments. The method is conceptually simple and elegant.\nThough, as I mentioned in my comments, the lack of extension of the grid abstraction to images limits the relevance of the ideas presented, due to the nature of benchmarks in Deep RL. Also, most of the notations could be reworked (see comments).\n\nI am borderline recommending for acceptance since I like the paper and its ideas but I really think that the mentioned extension would really improve its potential impact.\n", "strength_and_weaknesses": "### Strengths\n\nThe paper is well-written and easy to follow.\n\nThe contributions are clearly stated and suitable experiments are proposed to validate the paper claims.\n\nBoth the grid abstraction and multi-step analysis are interesting ideas that seem to work well in the explored context.\n\nThe method performs well on a variety of Mujoco tasks.\n\n### Weaknesses\n\nThe notations and overall math of the paper could really be improved (for instance using \\pi(\\cdot | s), s_{t + 1}, r(s, a), etc), though I do not think this is a major issue for the comprehension in the current state of the paper.\n\nThe code and data (unless I am wrong) are not available at the specified URL.\n\nThe grid definition is ad-hoc to state spaces with a relatively limited number of components (though it works for Humanoid). Do you have ideas to extend it to synthetic/natural images for instance? This would make the method applicable to other environments (e.g. DMControl, Atari, etc).\n\nI would advocate for a short description of how the gaussian random projections work in 4.1. This is an important component of the method whose details are currently missing.\n\nI would also like the paper to have a small explanation of how actions are handled when using state-action pairs for grid abstraction.\n\nDid you try different intrinsic rewards? While it appears natural to reward state-action pairs proportionally to how much their average return is superior to the average over all state-action-pairs, it might be interesting to use an advantage approximation as reward instead: the approximate advantage could be $\\c(s_t, a_t) - \\mathbb{E}_{a \\sim \\pi}[c(s_t, a)]$ for instance. This would connect the method with Advantage Learning methods (Baird, 1995).\n\nIn Table 1, it is stated that “the best average returns” are reported. Does that mean that only the average return of the best seed is reported? If so, I recommend to report the average over seeds instead (and standard deviation).   \n\nThe impact of the paper would be greater with DMControl experiments included (but that requires an extension to the grid abstraction).\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CjLjXGZlWX", "reviewer": "Reviewer_4xFQ", "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 novel neural episodic-control based approach with state abstraction, named NECSA. The authors motivate their methods by utilizing latent information from historical behaviors, which has been overlooked by prior work. Specifically, this paper proposes a more comprehensive episodic memory, which consists of state abstraction, multi-step analysis of pattern transitions as well as a novel state measurement metric (reward confidence scores). The proposed algorithm is simple and clear. First, NECSA adopts grid-based state abstraction, tokenizing each state dimension, which achieves efficient state clustering. Second, it extracts patter transitions by sliding a N-step window on each trace and updates reward confidence scores for each patter transition into episodic memory. Third, the episodic memory is used to reform intrinsic reward during policy optimization, to encourage the policy to visit states that lead to highly-rewarded trajectories. Experiments on MuJoCo continuous control tasks demonstrate that the proposed approach works well and outperforms state-of-the-art parameteric methods and non-parameterized episodic-control based baselines. Extensive experiments are conducted for ablation study and hyper-parameter sensitivity. ", "summary_of_the_review": "The paper proposes a novel algorithm named NECSA, which outperforms state-of-the-art episodic-control based methods. The authors conduct extensive experiments to demonstrate the effectiveness of their approach. I believe the overall method can benefit future research in RL community. It would be better to evaluate NECSA on a wide range of Atari games to see whether it is scalable in discrete domains.", "strength_and_weaknesses": "Strength:\n+ The proposed approach is technically sound, novel, scalable and works well across a wide range of continuous control tasks compared with state-of-the-art RL baselines.\n+ The idea of building a more comprehensive episodic memory is interesting and differs from existing episodic-memory based approaches, which may benefit the research in related communities.\n+ The authors demonstrate a full experimental analysis for the approach, revealing the main contributions, which makes the whole methods more convincing.\n\nWeaknesses:\n- NECSA seems a little bit sensitive to hyper-parameter choices. For instance, the optimal value of \\epsilon differs across tasks (e.g., 0.2 for Walker2d-v3, 0.1 for Hopper-v3).\n- The method so far has been limited to small steps of transition patterns (m=3).\n- NECSA was not evaluated on discrete domains such as Atari games (which is the most popular benchmark for most of episodic control based work).", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Bc6W8LXkxMX", "reviewer": "Reviewer_QTYi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of sample efficiency in RL by proposing a new episodic control approach. Episodic control consists of maintaining a table-like structure that can easily be accessed to return values associated with states/state-action pairs. The paper proposes NECSA, which introduces several novelties with respect to existing episodic control methods:\n\n1. It discretizes the state space and uses (1-, 2- and 3-state) tuples of discretized states as indices to the episodic memory (an _abstract state_);\n\n2. Each abstract state/state-action pair is mapped to a _score_, which is the average return of all episodes in which such abstract state appears;\n\n3. Scores are used as intrinsic rewards that complement the environment's original reward.\n\nThe proposed approach is shown empirically to outperform competing approaches in several continuous control benchmark problems.", "summary_of_the_review": "The paper addresses a relevant problem and proposes an interesting and novel approach with good empirical results. The relation with reward shaping could be better discussed, as well as the impact of discretization on performance.", "strength_and_weaknesses": "**Strong points:**\n\nThe problem addressed in the paper - sample efficiency in reinforcement learning - is a relevant problem in reinforcement learning. The proposed approach follows several recent works on the topic of episodic control and -- to my knowledge -- is novel. The paper also strikes me as technically sound.\n\n**Weak points:**\n\nOverall, the writing of the paper could be improved for clarity. Mainly, I felt that Section 4 often went on to discuss some element that was not yet introduced, or was introduced only briefly, which made the presentation at times difficult to follow. \n\nAdditionally, the motivation for several choices in the proposed approach is not always evident. Examples include considering multi-step patterns, using scores, rather than returns, or using the scores as intrinsic rewards, rather than improving the policy evaluation. \n\n**Questions for authors**\n* The proposed approach strikes me as very similar to _reward shaping_. Specifically, the proposed intrinsic reward mechanism reminds me of potential-based reward shaping, where the scores actually play the role of potential function (and actually provide estimates of the value function). Is this the case? If so, can this relation to reward shaping explain the improved performance observed by the method?\n\n* Although the appendix provides some added discussion regarding the impact of discretization, how much does the discretization impact the performance of the algorithm? It seems to me that, if the discretization is too coarse, the performance of the proposed method will be significantly impacted. On the other hand, for large-dimensional problems, it seems to me that a fine discretization may render the proposed approach infeasible, due to the curse of dimensionality. In Section 5 the paper mentions the use of random projections in the Humanoid-v3 scenario, but I believe that more discussion on this aspect is necessary.", "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: notable-top-25%