Robust Exploration via Clustering-based Online Density Estimation
Authors: Alaa Saade
Steven Kapturowski
Daniele Calandriello
Charles Blundell
Michal Valko
Pablo Sprechmann
Bilal Piot
Venue: Submitted to ICLR 2023 (2023)
Keywords: exploration
representation learning
density estimation
reinforcement learning

Abstract: Intrinsic motivation is a critical ingredient in reinforcement learning to enable progress when rewards are sparse. However, many existing approaches that measure the novelty of observations are brittle, or rely on restrictive assumptions about the environment which limit generality. We propose to decompose the exploration problem into two orthogonal sub-problems: (i) finding the right representation (metric) for exploration (ii) estimating densities in this representation space.

To address (ii), we introduce Robust Exploration via Clustering-based Online Density Estimation (RECODE), a non-parametric method that estimates visitation counts for clusters of states that are similar according to the metric induced by any arbitrary representation learning technique. We adapt classical clustering algorithms to design a new type of memory that allows RECODE to keep track of the history of interactions over thousands of episodes, thus effectively tracking global visitation counts. This is in contrast to existing non-parametric approaches, that can only store the recent history, typically the current episode.

The generality of RECODE allows us to easily address (i) by leveraging both off-the-shelf and novel representation learning techniques. In particular, we introduce a novel generalization of the action-prediction representation that leverages multi-step predictions and that we find to be better suited to a suite of challenging 3D-exploration tasks in DM-HARD-8. We show experimentally that our approach can work with a variety of RL agents, and obtain state-of-the-art performance on Atari and DM-HARD-8.

Under review as a conference paper at ICLR 2023
ROBUST EXPLORATION VIA CLUSTERING-BASED ONLINE DENSITY ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Intrinsic motivation is critical ingredient in reinforcement learning to enable progress when rewards are sparse. However, many existing approaches that mea- sure the novelty of observations are brittle, or rely on restrictive assumptions about the environment which limit generality. We introduce Robust Exploration via Clustering- Online Density Estimation (RECODE), a non-parametric method that estimates visitation counts for clusters of states that are similar according the metric induced by a specified representation learning technique. We adapt classical clustering algorithms to the online setting design new type of mem- ory that allows RECODE to efficiently track global visitation counts over thousands of episodes. RECODE can easily leverage both off-the-shelf and novel represen- tation learning techniques. We introduce a novel generalization of the action- prediction representation that leverages transformers for multi-step predictions. which we demonstrate to be more performant on suite of challenging 3D- exploration tasks in DM-HARD-8. We show experimentally that our approach can work with a variety of RL agents, obtaining fate-of-the-add performance on Atari and DM-HARD-8, and being the first agent to reach the end and-screeen in Pitfal!!
INTRODUCTION
Exploration mechanisms are key component of reinforcement learning (RL, Sutton & Barto 2018)
agents, especially in sparse-reward tasks where long sequences of actions need to be executed be- fore collecting reward. The exploration problem has been studied theoretically (Kearns & Singh
2002 Azar et al. 2017: Brafman & Tennenholtz) 2003 Auer et al.] [002] Agrawal Goyal 2012
Audibert et al. 2010; Jin | (020)) in the context of bandits (Lattimore & Szepesvári (0220) and
Markov Decision Processes (MDP, Puterman 1990; Jaksch et 2010). Among those theoretical
works, one simple and theoretically sound approach to perform exploration efficiently in MDPs is to use a decreasing function of the visitation counts as an exploration bonus (Strehl & Littman| 2008
Azar et al. 2017). However, this approach is intractable with large or continuous state spaces, as generalization between states becomes essential. Several experimental works have tried to come up with ways to estimate visitation counts/densities complex environments where counting is not trivial. Two partially successful approaches have emerged to empirically estimate visitation counts/densities in deep RL: (i) the parametric approach that uses neural networks and (ii) the non- parametrie approach that uses slot-based memory to store representations of visited states, where the representation learning method serves to induce a more meaningful metrid between states.
Parametric methods either explicitly estimate the visitation counts using density models (Bellemare et al. 2016 Ostrovski et al., 2017) or implicitly estimate the counts using e.g., Random Network Distillation (RND, Burda et al.) 2019; Badia et al.] (0200b). Non- parametric methods rely on memory to store encountered state representations (Badia et al. (020b) and representation learning construct metric that differentiates states meaningfully (Pathak al. 2017). Parametric methods do not store individual states explicitly and as such their capacity is not directly bound by memory constraints; but they are less well suited rapid adaptation on short timescales (c.g.. within single episode). To obtain the best of both worlds, Never Give Up (NGU, Badia et al. 2020b) combines
Ussully this is pseudometric on the space of ohservations, since d(z, y) 0 for * is permitted by typical network architectures, and may be desirable as means discard noisy or uncontrollable features

---

Under review as a conference paper at ICLR 2023
short-term novelty signal based episodic memory and a long-term novelty via RND, into single intrinsic reward. However, this approach also naturally inherits the disadvantages of RND; in particular, susceptibility to uncontrollable noisy features (see Section 5), and being difficult to tune. More details on related works are provided in App.C
In this paper, we propose to decompose the exploration problem into two orthogonal sub-problems. First, (i) Representation Learning which is the task of learning an embedding function on observa- tions or trajectories that encodes meaningful notion of similarity. Second, (ii) Density Estimation which is the task of estimating smoothed visitation counts to derive a novelty-based exploration bonus. We first present a general solution to (ii) which is computationally efficient and scalable to complex environments. We introduce Robust Exploration via Clustering-basee Online Density Estimation (RECODE), a non-parametric method that estimates visitation counts for clusters of states that are similar according to metric induced by any arbitrary representation. We adapt classical clustering algorithms to an online setting, resulting in a new type of memory that allows RECODE to keep track of histories of interactions spanning thousands of episodes. This is in contrast to existing non-parametric exploration methods, which store only the recent history and in practice usually only account for the current episode. The resulting exploration bonus is principled, simple, and matches or exceeds state-of oftte-of-thh-art exploration results on Atari; being the first agent to reach the end-screen in Pitfall!. In the presence of noise, we show that it strictly improves over state-of-the-arr explo- ration bonuses such as NGU or RND. The generality of RECODE also allows us to easily leverage both off-the-shell and novel representation learning techniques, which leads in to our second contribu- tion. Specifically, we generalize the action-predictio several state-of- ofthe-tf exploration agents, by applying transformers to masked trajectories of state and action embeddings for multi-step action prediction. We refer to this method as CASM for Coupled Action-Stae -tate Masking. In conjunction with RECODE, CASM can yield significant performance gains in hard 3D-exploration tasks included in the DM-HARD-8 suite; achieving new state of the art in the single-task setting.
representations (Pathak et al. 2017)) used in
2 BACKGROUND AND NOTATION
In this section, we provide the necessary background and notation to understand our method (see Sec.B). First, we present a general setting of interaction between an agent and its environment. Second, we define the terms embeddings, atoms and memory. Third, present our notation for visitation counts. Finally, we show how we derive intrinsic rewards from visitations counts.
Interaction Process between an Agent and its Environment. We consider a discrete-time inter- action process (McCallum 1995 Hutter] 2004, Hutter al. 2009 Daswani et al. 2013) between an agent and its environment where, at each time step t E N. the agent receives an observation o E O and generates an action a E A. We consider an environment with stochastic dynamics p H x AA- - A maps a history of past observations-action ability distribution over future observations. More precisely, the space of past observations-acte actions is H USEN Hr where Ho = O and Vt E N', He+1 He x A x O. We consider policies to a probability distribution over
and current action to a prob-
T : H + AA that maps a history of past observations-actions actions. Finally, extrinsic reward function r. H x A + IR maps a history to scalar feedback.
Embeddings, Atoms and Memory. An embedder is parameterized function fo H - E where & is an embedding space. Typically, the embedding space is the vector space TR. where N E No is the embedding size. Therefore, for given time step E N, an embedder is function fo that associates to any history he E H, a vector e = fe (h,) called an embedding. There are several ways to train an embedder fe such as using an auto-encoding loss of the observation o, (Burda al.) 2018a), using an inverse dynamics loss (Pahhak et al. 2017) or using multi-step prediction-ere loss at the latent level (Guo et al., 2020; (022). Those techniques are referred as representation learning methods. An atom / E & is a vector in the embedding space that is contained in a memory M (ʃi E | which is a finite blot- container, where |M| N is the memory size. The memory M is updated at each time step t by non- non-parametri, function of the memory M and the embedding e, In the simplest case, the memory is filled in first-in first-out (FIFO) manner along
We write Ay the set of probability distributions over set y
2

---

Under review as a conference paper at ICLR 2023
the interactions (Badia al. 2020b and atoms simply the embeddings themselves. However, more complex mechanisms than FIFO can be considered to fill/update a memory. For instance given memory M and embedding e,, the embedding e, can be inserted in the memory if and only if it sufficiently different from the other atoms the memory and the memory is not at capacity. The update rule that defines the atoms in the memory is key component of method.
Visitation Counts. The exact visitation count, (s(M,e). for given embedding e E with respect the memory M can be written as:
[ad]
Na(M,e) e) = Σ e), where (c. f1 if otherwise,
(1)
t=1
However, when the state-space is very large or continuous, the exact visitation count is often un- informative since the same embedding may rarely be encountered twice. To overcome this prob- lem, we can instead compute visitaisitttonn counts Nx(M, e) == E KCff,,)) e), where K. E R, is definite positive kernel. Different choices of kernel can be made such Gaussian kernel e)( = exp(-Ile f13) or an inverse kernel K( = filee-fll where |1-1|2 is the Fu- clidean distance in the embedding space E. Finally,
can compute weighted soft visitation count Nx(M,,, e, { = E wrK((ftt, e), where the weights w E R.+ are positive real num- bers denoting the count each atom. Note that the exact visitation count can be recovered from the more general weighted soft visitation count as a special case by setting the weights wi = 1 and K. == 5.
Intrinsic Rewards from Visitation Counts. It is straightforward to define an intrinsic reward from visitation counts. Indeed, as the goal of an exploratory agent is go to less-visited states, an intrinsic reward can be any decreasing function of the visitation counts. In the literature, the inverse of the square root of the visitation counts known to be theoretically sound (Azar et al. 2017).
Therefore, for given time f, the intrinsic reward associated to the transition (0,, qz 0(+1) 1, can be defined as:
r (VNe(AM, e411, (w))/ +C)
(2)
where a small constant E IR is added to avoid numerical instability.
3 RECODE
In this section, we introduce our Robust Exploration via Clustering-based Online Density Estima- tion (RECODE) approach that computes intrinsic rewards for exploration. At high level, RECODE stores fixed number of weighted atoms (typically 5 10 or 2 10 depending on the domain) that are interpreted the following as cluster-centers, along with their counts. The update rule of our memory M for each new embedding & and the computation of the intrinsic reward are detailed in Algorithm. [ To each atom/cluster-center fi E E, we associate a count c E N (initialized to 0) that is updated after each new embedding is observed. When a new embedding is inserted we prob- abilistically choose either to add as a new cluster (if it is far away from existing clusters relative to adaptive threshold) increment the count of its nearest neighbor and adjust the cluster center toward the new embedding. The update rule has a close connection to the DP-means algorithm of Kulis & Jordan (2011), with two key differences:
the counts of the cluster-centers are discounted at each step, allowing our approach to deal with the non-stationarity of the data due both to changes in the policy and the embedding function, effectively reducing the weight of stale cluster-centers in the memory,
when creating a new cluster-center, we remove an underpopulated one, so to keep the size of the memory constant. We compare the qualitative behavior of different removal strategies in Fig. 8
theoretical analysis is sketched in Appendix D To help build some intuition about the quality of density estimation, illustrate in Figure the result of Algorithm T on toy example with
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1: RECODE
Input Emheddinn e, Memory M = (fr) cluster-center counts {cr)--( number of neighhors k; relative tolerance x, squared
[Md]
distance estimate d',, decay rake 7, discount n, insertion probubility kemel function K., intrinsic reward constant
Output: Updated memory M (f)) updated cluster-center counts {ez {=:)_. updated squared distance di intrinsic reward
Compute weighted smoothed
count (M,(M,,,
(1)=)) (1 ce) K(f..e))
Compute intrinsic reward
(Ne + )
Find nearest & cluster centers to the embeddding e: Nx(e)
Update squared distance estimate: di
d' EyeN, lle fl1
Discount all cluster-center center counts o; <- 7. 4I (1..., ......M).. |M]
Find index of nearest cluster center arg min; M) II eel2
Sample uniformly a real number (U, 1]: U
llfe
2 de, and y Sample index j of center to remove with probability P(j) oc 1/o3 mrgmin;-1. 188111 lift fylla
10
Renove under-populated cluater
11
Find index of nearest cluster center removed center: Cn. +- cj
Redistribute
13
Insert index j count fg t- c,
Create new cluater
15
ebe
16
Update nearest cluster center fi 2 0:1T"
17
Update ncarest cluster-center count 6 4- 0j
18
end
10
Figure I: Density estimation using RECODE on a toy example: for step O,..., 100, we sample batch of 64 2D-embeddings uniformly from the square of side 1+ /t. The support the embedding distribution therefore expands over time simulate non-stationary distribution akin to the distri- bution of states visited by an RL agent over the course exploration. We plot the clusters learned by RECODE with size proportional their count. We find that for small enough discount, RECODE exhibits short-term memory, accurately approximating the distribution of the final distribution. As we increase the discount. RECODE exhibits longer-term memory. approximating the historical density of states, as can be seen by the concentration of probability mass in the bottom-left corner.
non-stationary embedding distribution. We find in particular that tuning the discount allows to smoothly interpolate between short-term and long-term memory, a property that will prove crucial achieve the strong experimental results of Section
Note that contrary to the usual episodic memory used in Badia et al. 2020b a), the memory is never reset, and shared between actors in our distributed RL agent. We use the following kernel function defined for (e, f) E E² by:
K(f.e)
1 [1le-1113 113
(3)
- d=
E +
where E R_, d is an estimate of the squared distance between embedding and its nearest neighbors in the memory (see Algorithm. [T and 1l is the indicator function. Compared to Badia et al. 2020bla). our smoothed visitation-counts computes the normalized distances from given embedding é to all its neighbors within df -ball, instead of only the k-nearest neighbors. This change avoids undesirable property of the k-NN approach where inserting cluster with unit-
4

---

Under review as a conference paper at ICLR 2023
count close to the embedding might reduce its pseudo-count instead of increasing it if the k-th nearest neighbor of e had a large count.
We now detail how RECODE can be integrated in typical distributed RL agent (Espeholt et al, 2018 Kapturowski et al. 2018) that comprises several processes that run in parallel and interact with each other. Classically, a Learner performs gradient steps to train a policy wo and an embedding (representation) function fa. forwarding the parameters to an Inference Worker. A collection of independent Actors query the inference worker for actions that they execute in the environment and send the resulting transitions to the Learner, optionally through a (prioritized) Replay (Maih) al. 2015; Schaul et al. 2015). When using RECODE, the Actors additionally communicate with a shared Memory implementing Algorithm|] []] at each step t. they query from the Inference Server an embedding (h+) of their history and send it to the shared Memory which returns an intrinsic reward that is then added to the extrinsic reward to train the policy in the Learner process. In practice, we normalize the intrinsic reward by a running estimate of its Handard-deviation as in Burda et al. (2019). A diagram giving overview of distributed agent using RECODE is given in Fig. 10
REPRESENTATION LEARNING METHODS
The Learner process uses the data sent by the actors to train the policy Ty via an RL algorithm and to train the embedder fo via a representation learning loss. As noted in Section [ the choice of the embedding function fo : H + & induces metric in the embedding space & allowing to compare histories. Many different representation learning techniques have been studied in the context of exploration in RL (Burda et al., 2 Guo al., 2020; 2022 2021 [Erraqbbi et al.) 202T). In the following, we focus on action prediction embeddings, introducing first the standard 1-step prediction formulation (Pathak et al. 2017 [Badia et al. 22020b a). Our embedding function fo is parameterized as fewd-forward neural network taking or, the observation at time t, as inputs. We further define a classifier go that, given the embeddings of two consecutive observations an estimate (a ot, 0t+1) Ie (fo(ot), (o(+1)) of the probability of taking an action given two consecutive observations (oe, 01+1). Both fo and Iø are then jointly trained by minimizing an expectation of the following loss:
ff
outputs
min L(0, (a.) In(po, 0c+1)),
(4)
0,6
where [(,, (ax)) is the negative log likelihood and a, is the true action taken between o and ot+1- These embeddings have been shown to be helpful in environments with many uncontrollable features in the observation (Badia et al.. 2020b), such as the game of Pitfall! in Atari, where they might result in spurious sources of novelty even when the agent is standing still.
We note however that RECODE can be used with an arbitrary embedding function, e.g. one tailored for the domain of interest. One downside of the standard, 1-step action-prediete method is that the simplicity of the prediction task may only require highly localized and low-level features to be learned for its solution, which may not be informative of more geometrical or topological notions of environment structure, that partially-observable or 3D-exploration tasks might require. Other popu- lar forms of representation learning such as Contrastive Predictive Coding (CPC, Oord et al. (2018) or Predictions of Bootstrapped Latents (PBL, Guo et al. (2020) utilize cemporally-extender extennded predic- tion tasks but do not enforce any notion of controllability. We now present a novel generalization of action-pree preddiciooniiiinnn embeddings that we show to yield strong results on DM-HARD-8 in section [
A straightforward generalization of 1-step action prediction is to predict sequences of actions be- tween observations o, and 0t+ks but in general there may be many such sequences which are possi- ble, besides the one which is obtained by the behavior policy. This introduces an additional policy- dependent non-stationarity in the prediction task which could potentially hinder learning efficiency and stability. To counteract this problem we could provide all but one of the intervening actions to our context (oe, ae at+1 a1+k-2, oc++), and predict only a;+k-1. However, in partially observed domains it is possible that these two observations alone are insufficient to accurately localize the agent's 's state, and therefore it may be beneficial to provide additional context before ot-
Concretely, we propose to apply causally- causally-masked masked transformer to sequences of observation and action embeddings, such that at each timestep t exactly one of o, and a, is provided. The transformer output is then projected down to the size of the embedding (dim 2 dim fo(o:)), and the difference
5

---

Under review as a conference paper at ICLR 2023
between the two is input into final MLP classifier, 9e. During training, randomly sample N = masks per trajectory to help reduce gradient variance. Note that we use é = fo(or), , the transformer inputs, the embeddings for RECODE in order avoid leaking information about the agent's trajectory. As with 1-step action prediction, we train the representation using maximum likelihood. We refer to this approach Coupled Action-State Masking (CASM) in the following. Figure Segurs shows diagram of the architecture.
F
F6++1
F
p(aelect1,
transformer stack
action prediction network J
masked inputs
ezz
Q,.2
Cz
encoder
fo
-
network
Opk
0r
1t
Figure 2: Coupled Action- -tate Masking (CASM) architecture used for learning representations in partially observable environments. Note that masked inputs are shaded in pink.
EXPERIMENTS
In this section, we experimentally validate the generality of our approach by applying it to several domains with distinct properties. We first show that match improve statc-of-the-art learn- ing efficiency on the hardest exploration games contained in the well-established Atari benchmark. We then turn to DM-HARD-8, suite of partially-observable 3D hard exploration tasks, where obtain results that match or exceed the recently proposed BYOL-Explore (Guo et al. (022) agent. All the candidates evaluated in the experiments in the main paper and the extended experiments in App. E are composed by three main modules: (1) base agent, responsible for core RL aspects such collecting observations and updating the policy, (2) an algorithm responsible generate an exploration bonus, and (3) representation learning algorithm responsible to generate latent repre- sentation of the observations that allow the exploration bonus names in the experiments will reflect which specific algorithm is responsible for each of the three modules. For example, in our more detailed taxonomy the original MEME agent described in Kap- turowski et al. (2022) is denoted as the MEME-NGU-AP bascline. Similarly, our SEME-RECODEEAT uses the same base agent (MEME) and representation learning algorithm (AP), with the only modification being the intrinsic reward mechanism being swapped from NGU to RECODE. For full description of all the baselines we refer the reader to App. A We use memory comprised of 5 10 atoms for Atari experiments and 2 10 atoms for DM-HARD-8 experiments. We find that the resulting agent runs at roughly the same speed as the original MEME agent. More hyperparameters values can be found in App.
meaningful. Each of the agent
5.1
ATARI
The Atari Learning Environment (ALE, Bellemare et al. 2013) is one of the most used RL bench- marks for deep RL,, comprising 57 Atari games which are mostly 2-D, and have a limited degree of partial observability which can often be rectified by stacking a small number of frames. On the other hand, many games have a long optimization horizon (with episodes lasting up to 27000 steps using the standard action-repeat of 4), and rewards vary considerably in both scale and density. Among the 57 Atari games, only few are considered hard-exploration (Bellemare et al., 2016) such as Montezuma's s Revenge, Pitfall and Privats Eye. For evaluation,
follow the classical 30 random no-ops evaluation regime (Mnih et al., 20155] Van Hasselt et al,, 2016), and average perfor- mance 3 seeds. This evaluation regime does sticky actions (Machado al. 2018).

---

Under review as a conference paper at ICLR 2023
jiffall
scleris
130003
2000
50000
7503
2003
500.0
69003
50030
60009
20003
2000
1c0
Tel
Telt
Tel
peaques!
tero
obert
veritre
1.0
(5000)
MEVE RE:00E
MEVE-WOUR WCB-P
030003
UEME 2N0
0.4
150000
MEME EHM
MEME 19630
120009
230003
1060
509
16
1.5
30
4.5
8.8
7.5
8.
3.9
4.5
7.5
8.0
1.5
30
4.5
6.6
7.5
60
1.5
23
4.5
60
7.5
Number of dTrorres
128
Numbbel of Stamnes
168
Namberr tarres
1e8
Number of fames
168
Figure 3: Comparison of RECODE against other exploration bonuses using MEME base agent on 8 hard exploration games from the Atari domain.
Average Episode Length
10
RECODE
Count
10a
10'
101
10a
10
10
10 10*
10²
10a
Cluster Age Actor Steps
Figure 4: Age distribution of the clusters learned by RECODE on Montezuma's Revenge. We set ? 0.999 in the experiments of Figure We indicate in red the average length of an episode, showing that in this setting, RECODE's memory reaches back thousands of episodes.
We compare our approach with MEME-NGU-AP and its ablations on of the hardest exploration games on Fig. We find that MEME-RECODE-AR AP matches the performance of the original MEME agent with a single, simpler intrinsic reward, achieving super-human performance on all 8 hard exploration games. Indeed, as shown in Fig. 3 MEME-NGU-AP requires the full NGU exploration bonus (i.e., both RND and EMM) to solve uncontrollable features in its observations, while EMM its own cannot solve Montezuma's 's Revenge because requires long-term memory. Because RECODE estimates the visitation counts over many episodes using AP embeddings that discard uncontrollable dynamics, is able solve both games with a single intrinsic reward. We probe how far back the memory of RECODE goes in Montezuma's Revenge in Figure 4 and find that the distribution of the age of the clusters learned by RECODE exhibits mode around 2 10 actor steps, which corresponds to hundreds of episodes, with a significant number of clusters
games: RND on its own cannot solve Pitfall! because of the many
times older than that. We also compare our approach with MEME- RNDoNAP (detailed in Appendix E). modification of RND built on top of AP embeddings, in an attempt to fix the aforementioned undesirable properties of RND. We find that this approach does not allow to solve some of the hardest games such as Montezuma's 's Revenge or Pitfall!. One possible explanation of this failure is the fact that a large RND error can be caused by either the observation of a state, drift in the representation of an already observed one. The failure of RND to disentangle these two effects results in poor exploration.
5.2 NOISY MONTEZUMA'S REVENGE
Atari Games are deterministic with respect to the RAM state, which property that most real- world environments do not share (e.g.: observations may be noisy due to imperfect sensors). As RND relies on predicting a random embedding of the raw observation to determine whether a state is new not, it cannot learn discard noisy features, hindering its ability to detect meaningful novelty

---

Under review as a conference paper at ICLR 2023
Notsy Montecuma
14330
12330
8839
E
NEVERISHP
6239
Number frames
Figure 5: (Left): :
Performance of RECODE compared to NGU on Noisy Montezuma. (Middle and Right): A frame of Noisy Montezuma where the noise is concatenated to the original frame.
in the presence of noise. In this section, we show that MEME-NGU-AP inherits the limitations of RND. To this end, we consider the game of Montezuma's 's Revenge, for which effective exploration requires long-term memory as shown by the ablations of Section 5.1 We challenge RND by concatenating the original grey-scale, 210 160 pixels frame with a noisy frame of the same shape, where each pixel is sampled uniformly at random from the range [0, 255]. This type of noise is commonly referred to as noisy TV (Pathak et al., (017). The results of our experiments on this environment are presented on 5 Perhaps as expected, we find that the performance of MEME-NGU-AP is strongly deteriorated, since it relies on RND for the long-term component of its exploration bonus, and performs no better than pure RL baseline without exploration bonus (Kapturowski al. 2018). RECODE, the other hand, relies on action- space, states that only differ in the noisy, uncontrollable part of the observation tend to be aliased together, so that the effect of the noise on exploration vanishes. Indeed, the performance of MEME- RECODE-AP Montezuma's Revenge is unchanged when adding noise.
action-predicteo prediction embeddings to estimate global visitation-coumi
In this embedding
5.3 DM-HARD-8
DM-HARD-8 (uucchhre et al. 2019) is benchmark comprised of 8 hard exploration tasks, originally built emphasize the difficulties encountered by an RL. agent when learning from sparse rewards in a procedurally-geneene variable initial conditions. Each task requires the agent to interact with specific objects in its en- vironment in order to reach a large apple that provides reward (see Figure IT in the Appendix for an example). Being procedurally-geeeratee,, properties such as object shapes, colors, and positions different every episode. A recently proposed exploration bonus called BYOL-Explor ore (Guo) let al. 2022) was shown to be effective on this domain, while previous successes were only achieved through the use of human demonstrations (Gulcehre al., 2019).
3-D world with partial observability, continuous control, and highly
We first assess the effect of using the RECODE bonus over NGU by performing a drop-in replacement of the intrinsic reward in the MEME base agent as in Section 5 We consider the performance of the resulting agent in the single-task version of DM-HARD-8 since the MEME base agent is not designed to work in the multi-task setting out-of-the--ox The results, presented on Fig. 6 show that MEME- RECODE-AF AP approach can solve 4 out of 8 games, strictly improving over the onginal MEME agent using either NGU or EMM in this direct comparison. Second, we turn to using the CASM representation learning approach introduced in Section 4 for our embedding. We find that the resulting MEME- RECODE-CASM agent attains state-of-the-arr results on the DM-HARD-8 benchmark, reliably solving 6 out of 8 games. This matches and often improves over the state-of-the-art performance of Guo cct al. (2022), which combined the BYOL-Explore exploration bonus with a VMPO-based base agent. Finally, ly, to demonstrate the generality of our approach, also test the combination of VMPO base agent similar to that used in Guo et al. (2022) with RECODE and AP embeddings. The resulting agent evaluated in the multi- task setting, reliably solving 4 games with zero additional tuning (App. G matching the result obtained with Human Demonstrations in Gulcehre et al. (2019).
6 CONCLUSION AND DISCUSSION
We have introduced Robust Exploration via Clustering- based Online Density Estimation (RECODE), principled yet simple exploration bonus for deep Reinforcement Learning (RI.) agents that allows
8

---

Under review as a conference paper at ICLR 2023
Baseball
Drawbridge
Nav Cubss
Push B ocis
10
12.5
E0000 5000
2
1e0
1e0
te0
Rerrember Seancr
Thros Across
Servsor
Well Sensor Stack
MINE-C3044P
Farme
E1todd
168
Namber francs
Humber
Figure Performance of RECODE compared to MEME on the single-task version of DM-HARD-8
Besebell
Drowtritge
part Cubes
Push ocos
13.0
53000
0
Sensor
Across
VoFO Exglon
Ikma
Number
1e9
Number
Number
Number of
Figure 7: Performance of RECODE using CASM embeddings compared to BYOL-Explore the single-task version of DM-HARD-8. 8. The BYOL-Explore results correspond to the final performance reported in Guo et al. 2022). after 10 environment frames, averaged over 3 seeds.
to perform robust exploration by computing visitation counts from a slot-based memory. Contrary to previous work, where the memory short-term (i.e. only able to attend to the current episode due to memory limit), our memory is able to model a wide range of timescales determined by the choice of discount. This is made possible the use of online clustering algorithm that is able to approximate the density of visited states and from which we derive a simple and easy-to-tune intrinsic reward.
We evaluate our exploration bonus on top of the recent MEME agent, which a value-based agent making use of the NGU intrinsic reward, that achieves state-of-the-art results the Atari domain. We show that we can replace the complex NGU intrinsic reward that combines RND and episodic memory with the simpler RECODE reward without loss of performance on the hardest exploration levels in Atari. Furthermore, we highlight important failure modes of NGU in the presence of noise, and show that RECODE's performance is unaffected. Similarly, highlight the limitations of NGU in procedurally-genenaae
3D environments such as DM-HARD-8, and demonstrate the improvements brought by using RECODE as an intrinsie reward. Next we introduce a novel representation learning method better suited to 3D and partially observable domains, which provides a significant boost in performance on this task suite, enabling to achieve a new state-of-the-an on DM-HARD-8 in the single-task setting.
Importantly we note that RECODE is agnostic to the choice of embeddings fo(h),, and while CASM presents one compelling option to extend 1-step action prediction, hypothesize that much progress could be made in challenging exploration problems by developing more sophisticated rep- resentations which be used in conjunction with RECODE.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit prob- lem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012.
Jean-Yve Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pp. 41-53. Citeseer, 2010.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-25 256, 2002.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 263-272. JMLR. org, 2017.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020a.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Andrew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies. In International Conference on Learning Representations, 2020b.
André MS Barreto, Doina Precup, and Joelle Pineau. Practical dernel-based reinforcement learning. The Journal of Machine Learning Research, 17(1)2372-2441, 2016.
Mare Bellemare, Joel Veness, and Erik Talvitie. Skip context tree switching. In International conference on machine learning, pp. 1458-1466. PMLR, 2014.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski. Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in neural information processing systems, pp. 1471-1479, 2016.
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.
Ronen Brafman and Moshe Tennenholtz. R-max - a general polynomial time algorithm for near- optimal reinforeement learning. Journal of Machine Learning Research, 3:213-231, 2003.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv: 1808004558 04355, 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 1810. 12894, 2018b.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In Seventh International Conference Learning Representations, pp. 1-17, 2019.
Mayank Daswani, Peter Sunehag, and Marcus Hutter. Q-learning for history-based reinforcement learning. Asian Conference on Machine Learning, pp. 213-228. PMLR, 2013.
Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Kernel-based reinforcement learning: A finite-time analysis. In Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2783-2792. PMLR, 2021a.
Omar Darwiche Domingues, Corentin Tallec, Rémi Munos, and Michal Valko. Density-based bonuses on learned representations for reward-free exploration in deep reinforcement learning. In ICML 2 Workshop, b.21b.
10

---

Under review as a conference paper at ICLR 2023
Akram Erraqabi, Mingde Zhao, Marlos C Machado, Yoshua Bengio, Sainbayar Sukhbaatar, Ludovic Denoyer, and Alessandro Lazaric. Exploration-driven representation learning in reinforcement learning. In JCML 2021 Workshop Unsupervised Reinforcement Learning, 2021.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with im- portance weighted actor-learner architectures. In International conference on machine learning, pp. 1407-1416. PMLR, 2018.
Caglar Gulcehre, Tom Le Paine, Bobak Shahriari, Misha Denil, Matt Hoffman, Hubert Soyer, Richard Tanburn, Steven Kapturowski, Neil Rabinowitz, Duncan Williams, et al. Making effi- cient use of demonstrations to solve hard exploration problems. In International conference learning representations, 2019.
Zhaohan Daniel Guo, Bernardo Avila Pires, Bilal Piot, Sean-Bastier Grill, Florent Altché, Rémi Munos, and Mohammad Gheshlaghi Azar. Bootstrap hatent-predictive representations for multi- task reinforcement learning. In International Conference on Machine Learning, pp. 3875-3886. PMLR, 2020.
Zhaohan Daniel Guo, Mohammad Gheshlagi Azar, Alaa Saade, Shantanu Thakoor, Bilal Piot, Bernardo Avila Pires, Michal Valko, Thomas Mesnard, Tor Lattimore, and Rémi Munos. Ge- ometric entropic exploration. arXiv preprint arXiv:2101.02033 2021.
Zhaohan Daniel Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tallec, Alaa Saade, Daniele Calandriello, Jean-Bastien Grill, Yunhao Tang, et al. Byol- explore: Exploration by bootstrapped prediction. arXiv preprint wwXiv:2206.08332. 2022.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pp. 2681-269) 2019.
Mareus Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic proba- bility. Springer Science & Business Media, 2004.
Marcus Hutter et al. Feature reinforcement learning: Part I. unstructured MDPs. De Gruyter Open, 2009.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1533-1600 2010.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879. PMLR, 2020.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney, Recurrent ex- perience replay in distributed reinforcement learning. In International conference on learning representations, 2018.
Steven Kapturowski, Victor Campos, Ray Jiang, Nemanja Rakićević, Hado van Hasselt, Charles Blundell, and Adrià Puigdomenech Badia. Human-level atari 200x faster. arXiv preprint arXiv:2209.07550. 2022.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2-3):209-25) 2002.
Brian Kulis and Michael I Jordan. Revisiting k-means: New algorithms via bayesian nonparamet-
rics. arXiv preprint arXiv:1111.000 2011.
Branislav Kveton and Georgios Theocharous.
Kernel-based reinforcement learning representa- tive states. Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdi- nov. Efficient exploration via state marginal matching. arXiv preprint arXiv: arXiv:/906.00 190..002644.444 2019.
11

---

Under review as a conference paper at ICLR 2023
Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34: 34:18459-18473, 2021.
Marlos C Machado, Mare G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
Andrew McCallum. Instance-based utile distinctions for reinforcement learning with hidden state. In Machine Learning Proceedings 1995, pp. 387-395, Elsevier, 1995.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7540):52--33,, 2015.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv:1807.03745. 2018.
Dirk Ormoneit and Šaunak Sen. Kernel-basee reinforcement learning. Machine Learning, 2002.
Georg Ostrovski, Mare G Bellemare, Aäron den Oord, and Rémi Munos. Count-based ploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning-Volee Volume 70. pp. 2721-2730. JMLR. org, 2017.
Emanuel Parzen. On estimation of a probability density function and mode. The Annals of Mathe- matical Statistics, 33, 1962. ISSN 0003-4851. doi: 10. 10.1224/aoms/ 177704472.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self- prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16-17, 2017.
Jason Pazis and Ronald Parr. Pac optimal exploration in continuous space markov decision pro- cesses. In Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering self-supervised reinforcement learning. arXiv preprint 2019.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomênech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. ICML, 2017.
Martin L. Puterman. Markov decision processes. Handbooks in operations research and management science, 2:331-434 4344, 1990.
Murray Rosenblatt. Remarks on some nonparametric estimates of density function. The Annals of Mathematical Statistics, 27, 1956. ISSN 0003-4851, doi: 12..214/ 117mmm//97777899
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. CoRR, abs/151 .05952, 2015.
Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. In International Conference on Machine Learning, pp. 9443-9454 PMLR, 2021.
Alexander L Strehl and Michael L Littman. An analysis of model interval estimation for markov decision processes. Journal of Computer and System Sciences, 1309 2008.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, study of count-
John Schulman, Filip DeTurck, and Pieter Abbeel. #Exploration: based exploration for deep reinforeement learning. In Advances in Neural Information Processing Systems, 2017. URL https: https://procceddigg neurips.e..m wttccc/cpppppp.... cc/ppaper/011//Elle) pdf
12

---

Under review as a conference paper at ICLR 2023
Ruo Yu Tao, Vincent François-Laved and Joelle Pineau. Novelty search in representational space for sample efficient exploration. Advances in Neural Information Processing Systems, 14-6112, 2020.
Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al. Con- ditional image generation with pixelenn decoders, Advances in neural information processing systems, 29, 2016.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
13

---

Under review as a conference paper at ICLR 2023
A HYPER-PARAMETERS
We omit hypers which do not differ from the base agent, MEME.
Table I: Atari Hyper-parametens
Parameter
Value
RECODE memory size
x 10*
RECODE discount
0.999
RECODE relative tolerance
0.01
RECODE insertion probability 7)
0.05
RECODE reward constant
0.1
RECODE decay rate
0.9999
RECODE neighbors
IM Reward Scale 9IM
1.0
Max Discount
0.9997
Min Discount
0.97
Replay Period
Trace Length
160
Replay Ratio
6.0
Replay Capacity
x 10 trajectories
Batch Size
64
RI. Adam Learning Rate
x 10
Emedding Adam Learning Rate
x 10-4
RI. Weight Decay
0.05
Embedding Weight Decay
0.05
RI. Torso initial stride
RL Torso num blocks
(2, 3, 3,444. 4)
RL Torso channels
(64, 128, 128, 64)
RL Torso strides
(1, 2,
Table 2: DM-HARD-8 Hyper-parameters
Parameter
Value
RECODE memory size
2 x 105
RECODE discount
0.997
RECODE relative tolerance
0.2
RECODE insertion probability 7
0.2
RECODE reward constant
0.01
RECODE decay rate т
0.9999
RECODE neighbors
20
IM Reward Scale 3IM
0.1
Max Discount
0.997
Min Discount
0.97
Replay Periol
40
Trace Length
Replay Ratio
2.0
Replay Capacity
5000 trajectories
Batch Size
128
RI. Adam Learning Rate
x 10
Emhedding Adam Learning Rate
3 10
RL Weight Decay
0.1
Embedding Weight Decay
0.1
RI. Torso initial stride
2
RL Torso num blocks
(2, 4, 12, 6)
RL Torso num channels
(64, 128, 128, 64)
RI. Torso strides
(1, 2,,),
14

---

Under review as a conference paper at ICLR 2023
Table 3: CASM Slyper-parameter
Parameter
Value
Transformer Type
GatedTTranffrmmeXI
State Mask Rate
0.8
Num Masks Per Trajectory
4
Action Embedding Size
32
Num Layers
2
Attention Size
128
Num Attention Heads
4
MLP Hidden Sizes
(512.)
Predictor Hidden Sizes
(128.)
B AGENT TAXONOMY
All methods evaluated in the experiments in the main paper and the extended experiments in App. are composed by three main components.
A base agent that oversees the overall RL learning process (e.g.. executing actions and collection observations, computing adjusted returns, updating the policy, We focus on MEME (Kapturowski et al.] 2022), recent improvement over Agent57 (Badia et al.) 2020a) that achieves much greater sample efficiency and is the current state-of-ther on Atari, and VMPO-based agent (Guo et al. 2022) that is the current state-of-the-art on DM-HARD-8.
An algorithm to generate intrinsic rewards. In addition to RECODE, we also consider the recent BYOL-Explore Guo al. (2022), NGU Badia et al. (2020b) and NGU's two building blocks, RND Burda et al. (201 8b) and Episodic Memory (EMM) Pritzel et al. (2017).
A representation learning mechanism to generate observation embeddings which are fed to the intrinsic reward generator. We consider both Action Prediction (AP) and CASM embed- dings. Note that some intrinsic reward modules cannot make effective use of the represen- tation learning module (e.g., RND), while others merge both second and third module in single approach (e.g., BYOL-Explore)
For example, in our more detailed taxonomy the original MEME agent described in Kapturowski al. (2022) is denoted as the MEME-NGU-AP baseline, and compared against our novel HEME-RECODS AP agent where the only modifications the changed exploration reward. Table reports more details on all combinations available present in our experiments.
Table 4: Taxonomy of agents used in the experiments.
Agent name
Base agent
Intrinsic reward
Representation learning
PEME-NGU-AP
Kapturowski et al. 2022
MEME MENE
NGU
AP
MEME-RND
(ablation)
N/A
TENE-EMM-AP
(ablation)
MENE
ENM
HEME-RNDONAA
(ablation)
(b)
TEME-RECODEL
(this paper)
MENE
RECODE
MEME-RECODE RECODE-CASM
(this paper) (ablation)
MENE
RECODE
CASM
MEME-KGU-CASM
MEME
NGU
CASM
VMPO-BYOL-Este -xpplor
Guo et 2022
VMPO
BYOL-Explore
BYOL-Explore (6)
(a) As in the original paper RND takes as input raw observations.
(b) To test RND's ability to cope with non-statinnary representations, train an encoder concurentlyy with the create emheddings of the observations that fed in RND (i.c., running AND top of AP). (c) The BYOL-Explore mechanism internally trains neural network to predict the dynamical evolution of the observations. This provides the agent with both reward/novelty signal (prediction error) as well as an embedded representation of the observations (that can be extracted from the last few layers of the network).
policy and
15

---

Under review as a conference paper at ICLR 2023
C RELATED WORKS
In this section, we give brief and non-exhaustive overview of past works computing visitation counts or estimating densities in RI.. We classify them as either parametric or non-parametrie.
Parametric methods. Bellemare al. (2016) and Ostrovski et al. (2017) propose to com- pute pseudo-visitation counts using density estimators on images such as Context Tree Switching (CTS/Bellemare et al., 2014) PixelCNN (Van den Oord et al. 2016). On the other hand, [Tang] et al. (017) use locality-sensitve hashing to map continuous states to discrete embeddings, where explicit visitation counts are computed. Some methods such as RND (Burda et al. 2019) can be inter- preted as estimating implicitly the density of observations by training neural network to predict the
output of a randomly initialized and untrained neural network which operates on the observations. Hazan et al. (2019); [Pog et al. (2019); Lee et al. ) Guo et al. (202I) propose algorithms that search policy maximizing the entropy its induced state-space distribution. In particular, the loss optimized by Guo et al. (202T) allows to compute a density estimate as well as maximizing the entropy. Finally. Domingues et al.] (2021b) computes density estimation on top of learned representations, which are inspired by bonuses used in reward- finite MDPs.
Non- Non-parametrie methods. Non-parametric density estimates that we build on date back to Rosen- blatt (1956); Parzen (1962) Crarzen-Rosenley window) and are widely used in machine learning as they place very mild assumptions on the data distribution. proaches have been already used in RL and shown to be empirically successful on smaller scale environments by K & Theocharous (2012) and Barreto et al. (2016) and are theoretically an- alyzed by Ormoneit Sen (2002); Pazis & Parr (0013): Domingues et al. (2021a).
Non-parametric, kernel-basee ap-
NGU (Badia et al. 2020b), Agent57 (Badia et al.) 2020a) and MEME (Kapturowski et al. 2022), non-parametric approach is used to compute a short term reward at the episodic level. Liu & Abbeel (202T) propose an unsupervised pre-training method for reinforcement learning which explores the environment by maximizing a non- non-parametric entropy computed an abstract representation space. The authors show improved performance on transfer in Atari games and continous control tasks. [Seo et al. (2021) use random embeddings and a non-paraeetric approach to estimate the state-visitation entropy, but do not generalize to concurrently learned embeddings. Tao al. (2020) show that K-NN based exploration can improve exploration and data efficiency in model-based RL. While non-parametric methods are good models for complex data, they come with the challenge of storing and comput- ing densities on the entire data set. We tackle this challenge in Sec. 3 by proposing method that estimates visitation counts over a long history of states, allowing our approach scale to much larger problems than those considered in previous works, and without placing assumptions on the representation, that can be trained concurrently with the exploration process and doesn't need to be fixed priori.
D A CLUSTERING VIEW OF RECODE
The update rules of RECODE for its memory structure Algorithm 1 can be interpreted as an ap- proximate inference scheme in a latent probabilistic clustering model. We explore this connection here as means better understand and justify the proposed algorithm as a density estimator. Briefly, our scheme is related to DP-means (Kulis & Jordan 2011), with adaptations made to accommodate the additional complexities of our setting, which follows a streaming protocol (i.e., data must be explicitly consumed or stored as it arrives and data that are not stored cannot be accessed again) and is non-stationary (i.e., data are not assumed to identically distributed as time advances). The clustering algorithm resulting from these adaptations is shown in Algorithm 2
We first address the modifications introduced to deal with the memory limitations of the streaming setting: 1) each datum (embedding e, in our notation) is incorporated into cluster distribution ap- proximation, once, then discarded, 2) the total number of clusters is stochastically projected down onto an upper limit on the number of clusters (otherwise they would grow without bound albeit progressively more slowly). Both modifications allow our method to maintain constant space com- plexity in the face of infinite stream of data.
16

---

Under review as a conference paper at ICLR 2023
Algorithm 2: A streaming clustering algorithm.
Parameters
Number of clusters L
Namber of nearest cluster centres k
Discounting of counts at each step Y
Scaling of threshold on new cluster creation n.
Probability of actually creating new cluster when threshold exceeded γ)
State
Threshold on creating new cluster =0
Cluster centres μl 0 El...
10 Cluster counts cı = 0 EI.....
11 Indices of k--nearest neighbours of point e: Nu(e)
12 Implementation
13 for each received embedding e feo, 62, 62,... do
Update threshold inter-cluster distances ò (1 7)6 + Eie l1m ell Discount all cluster-center counts c f- c 1I E I,...,
15
16
Find index of nearest cluster center arg min. I| c|l2 if || =l12 > 8 and with probability then
Sample index of cluster center remove with probability P()) x 1/c Find index of nearest cluster center to my; k = arg min Il H;lla
20
21
Redistribute the count of removed cluster center: C% f- cj + ck
22
Replace cluster with singleton (by f e, +
23
clse
24
Update nearest cluster center μ4s f
c+tl 14 + c++1
Update nearest cluster-eenter count C; Ci +
end
27 end
The step-wise justification of the Algorithm 2is relative straightforward. At step t, for embedding
ex, we show that the following objective is minimised:
min LE (EI.......
||m -
(5)
s.t. [14 e,113 S nō
Working backwards: Updating the cluster center of the closest cluster reduces the objective directly and will not violate the constraint (unless it was already in violation; this excluded in the precondi- tion of this branch). This accounts for the "clse" branch. The "if" branch introduces a new cluster center precisely es, thus equation 5ss minimised completely: it is zero for this branch. Finally, se- lecting the index of the nearest cluster center directly minimises placement of the branch according to equation 5 ignoring the constraint (which is latest ensured by the "if/else"). Note that the hard constraint of equation takes the place of the soft cluster penalty of DP-means (Kulis & Jordan 2011].
The updates to the cluster centers, unlike k-means and DP-means are done in an exponentially- weighted moving average of the embeddings, rather than as global optimisation step utilising all of the data. Consequently, and importantly, what happens to equation evaluated for e, where of t, of significant interest, as objectives for k-means and DP-means account for all data, rather than a single datum.
We now turn to this question, which will be answered by examining the modifications we introduced to deal with the non-stationarity of our data stream: 1) the cluster count decays, 2) merging two clusters to accommodate new one, 3) the exponentially weighted moving average update of cluster centers.
17

---

Under review as a conference paper at ICLR 2023
In k-means, all of the data retained. This makes k-means costly: at each step of fitting the entire data set is examined to update the cluster assignments and update the cluster means. Instead, we take distributional approximation to the data associated with each cluster, and when re-adjusting cluster assignments according to equation 5
we do so in terms of this distributional approximation.
In particular, each cluster is approximated by Gaussian distribution with precision and whose mean is unknown but with prior zero and precision 1. Specifically:
my NV(0, co)
e ~ 1)
where (H, r) denotes a Gaussian (or normal) distribution with mean μ and precision 7 (precision is the inverse variance). Since the prior on my is conjugate to the likelihood on et, we know that the posterior on my will have the form N ((u,,a) Updating this posterior with a single embedding e; has the form:
CI
1 a+b
1 +
14 ++
Ci
+
a +1
This is precisely the update in Algorithm
Note that in this model, the counts e also the precision parameters of the distribution representing the inverse spread (or the concentration) of each cluster. At each step of Algorithm 2 these counts decayed. Effectively, this causes the variance of the distribution representing each cluster to spread out: thus at each time step, each cluster becomes less concentrated and more uncertain about which data points belong it. The hyperparameter 7 captures the rate of diffusion of all clusters in this manner. This uncertainty increase applied at each step acts as a "forgetting" mechanism that helps the algorithm deal with a changing data distribution.
Cluster re-sampling, as already justified for e, above in terms of equation 5 ensures that the number of clusters bounded by L. There are two details to examine: what merged, and how it is merged. As C + 0, the probability assigned by the Gaussian likelihood of cluster j to any new datum approaches zero also, thus the cluster with the lowest counts is likely to have the least impact on future density estimates (as it is most diffuse). When ej >> 0, however, it is not so clear which cluster should be removed, therefore, we stochastically select which cluster to remove inversely proportional to the square of the counts (using the square of the counts emphasizes small differences in counts more than 1/c,). The cluster could potentially be removed completely, but we instead choose re-assign its counts to the nearest cluster experimentally found this strategy to be less sensitive to the choice of hyperparameters.
E RND ON TOP OF ACTION PREDICTION EMBEDDINGS
We adapt RND leverage trained action-prediction embeddings, which we refer RNDonAP. To that effect, we use a randomly initialize Multi-Layer Perceptron (MLP) to perform a random projection of the embedding, and use a second, trained MLP, to reconstruct this random projection. The reconstruction егrоr provides an intrinsic reward for exploration, which we normalize by running estimate if its standard deviation in BBurdda et al. (2019). We find that the resulting agent is unable to solve some of the hardest exploration games such as Montezuma's 's Revenge or Pitfall. The results of this ablation is shown in Fig. 9 Preliminary experiments with pre-trained embeddings do seem to indicate that RNDonAP to concurrently train the embeddings greatly limits the general applicability of the method.
obtain stronger performance in this setting, but the inability
F ARCHITECTURE OF AN AGENT USING RECODE
Figure shoss the typical architecture of a distribued RL agent using RECODE.
G MULTITASK EXPERIMENTS
We also implemented RECODE in a VMPO-based agent similar to the one used with BYOL- Explore (Guo al. 2022), and compared our performance with BYOL-Explore in the multi-task
18

---

Under review as a conference paper at ICLR 2023
Pt) 1/c
P() 1/c
argmin,(c)
100
80
80
[=500
60
60
20
20
20
0
100
80
80
500
60
60
40
20
20
20
75 100
25 75
100
25 50
100
Figure 8: Effect of removal strategy on evolution of cluster centers and counts (with counts corre- sponding to the size of the marker). At each timestep we sample batch of 64 2D- 2D-embedinggs from a square of side min(100, t). After t 100 the distribution remains stationary and we would like the distribution of cluster centers and counts to be to become approximately uniform after enough time has passed. For deterministic removal strategy which selects the clusters with the lowest counts, the cluster centers can remain skewed long after the distribution has stopped changing. For both probabilistic removal strategies, the cluster centers become approximately uniform, but only for the 1/cž removal strategy do we observe both cluster centers and counts become uniform. (Note that we use a discount 0.9999)
noniccume revenge
pitall
privite Srt
solaris
12303
12000)
130003
10693
9X00
80003
20000
4000
20009
20000
10000
3.0
1.5
3.0
4.5
18
7.5
0.0
1.5
3.0
4.5
8.5
7.5
8.0
1.
3.0
4.5
6.
7.5
6.0
1.5
3.3
4.5
6.0
35
166
160
1:0
Geaquest
obart
venture
550000
23000
Epode
MEVE 190
MEVE-EMM--1
430003
1500
0.2
12000
Human
230003
S1000
1.5
6.6
7.5
80
4.5
8.0
1.5
300
6.
7.5
600
3.
4.5
Figure 9: Performance RECODE compared to MEME and ablations on hard exploration Atari games.
19

---

Under review as a conference paper at ICLR 2023
Replay
Queue
Transitions
Transitions
Embeddings falhu)
Learner
Actors
Memory
Intrinsic rewards it
Poramsters
Hatories
Embeddiings /s0h) Actions
Inference Worker
Figure 10: Overview of the architecture of a distributed agent using RECODE.
1" frama
Look for baf
Plck bat
Throw bal down
meeik
apple goal)
Figure 11: ji-ppeson-vieww snapshots an agent solving the Baseball task. Images are ordered chronologically from left to right and top to bottom. Each image depicts specific stage of the task.
Desebell
Diandeidge
Nevipete Cubes
Push Brocks
12.5
50000 2000
53
160
1:5
160
Remrember Serpor
Throw Across
Wall Sersor
Well Sensor Steck
Exgloss
Epoode gort
Figure 12: Performance of RECODE compared to BYOL-Explore on the multi-task version of DM--HARD-8. Our RECODE implementation in this experiments is based on VMPO, using con- tinuous action set.
20

---

Under review as a conference paper at ICLR 2023
setting. This experiment serves two different purposes. First, this demonstrates the generality of our exploration bonus, that thus shown to be useful in widely different RL agents, be they value-based policy-based. Second, agent in the multi-task settings. We however note that the representation learning technique used in this experiment, 1-step Action Prediction, is based past history, and may therefore not be the best fit for exploration in Partially Observable MDPs (POMDPs). Still, show in Fig. 12 that the performance BYOL-Explore, with only one level missing to match its performance. Improving this performance using suiter- representations, such as CASM, is left for future work.
do direct comparison with the state of the art BYOL-Explore
feed-forward embedding that discards
RECODE is competitive with that of
H AGGREGATED RESULTS
Here we present our main results aggregated over all enviromments in each task suite. To ensure that no single environment dominates due to larger reward scales we use the Human Normalized Score (Mnih al., 2013) in each environment, and then cap scores above 100% prior to averaging. As can be observed in Fig. 13 (Left), the uncapped score can swing significantly over time, which in this case simply an artifact the high variance present in b*bert.
Mean HNS over 8 Atari hard exploration games
Mean Capped HNS over Atari hard exploration games
1000
100
800
Capped HNSS
HNS
REMEERECODE.A MEME-NGU-AP
200
0.0
6.0
3.0
Number of frames
1e8
Number of frames
Figure 13: (Left): Mean Houman-Normalizer Scores DEME-RECODE-AP AP compared to MEME-NGU-AN on Atari games. (Right): Capped Human-Normalizze Scores.
Mean Capped HNS DM-HARD-8
30
Capped HNS
60
30
30
MEME-RECODE-CASIL
VMPO-BYYL-Expp
4
Number of frames
1e9
Figure 14: Mean Capped Normal-Nrr Scores MEME-RECODE-CASM compared to VMPO- BYOL-Explore on DM-HARD-a games.
TThis variance arises due bug in berrt, which allows for much larger scores he obtained if exploited
21


Reviews:
[{"review_id": "Z7ibjohllz7", "reviewer": "Reviewer_vYnp", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 focuses on  generalizing the action/prediction representation that leverages multi-step predictions and that we find to be better suited to a suite of challenging 3D-exploration tasks in DM-HARD-8. We show experimentally that our approach can work with a variety\nof RL agents, and obtain state-of-the-art performance on Atari and DM-HARD-8.\n\nThe paper extends previous work,  limited to short-term memory (current episode), to address a wide range of timescales determined by the choice of discount. The authors propose an online clustering algorithm that is able to approximate the density of visited states.", "summary_of_the_review": "The ideas are interesting and have novelty, but the paper is poorly written and has inadequate experiments. The experiments should include a clear comparison with the standard Markov assumptions of RL and the general methods included here.", "strength_and_weaknesses": "Strengths:\nThis is a challenging area, and the paper has clear novelty.\n\n\nWeaknesses:\n\nOverall, the ideas are interesting but the paper is poorly written and has inadequate experiments. The experiments should include a clear comparison with the standard Markov assumptions of RL and the general methods included here.\n\nTheoretically, the paper is muddled and confusing. The authors need to distinguish the standard RL assumption of Markov models, vs. the exploration length allowed. This is unclear in the paper. The authors attempt to define \"history\" to incorporate exploration length allowed, but it is difficult to understand if this is actually the case.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "8RAHVtbFJcW", "reviewer": "Reviewer_TrKY", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 work proposes Robust Exploration via a Clustering-based Online Density Estimation (RECODE) algorithm. RECODE calculates an exploration bonus that any RL agent can use as an intrinsic reward signal to explore unknown environment areas. To compute intrinsic reward signal the visitation counts of observations is considered. For this purpose, an online clustering algorithm is applied over learned representations of observations that estimates visitation counts for clusters of observations that are close to each other.  Experiments have been conducted on hard-exploration tasks of Atari and DM-HARD-8 suits.\n", "summary_of_the_review": "This work proposes an interesting idea to drive agents to explore unknown environment areas, but its novelty is incremental. Apart from that, some details are missed, and that makes it hard for the reader to understand all the details and reproduce the results if needed. Finally, the experiments do not validate the superiority of the  RECODE algorithm over the MEME algorithm in each examined environment. ", "strength_and_weaknesses": "\n**Strengths**\n\n- The proposed RECODE algorithm can estimate a simple exploration bonus that can be considered by any RL agent\n-  The idea of using an online clustering algorithm over learned representations of observations to estimate visitation counts for clusters of observations close to each other is quite interesting.\n- Experiments have been conducted on hard-exploration tasks of Atari and DM-HARD-8 suits, showing that *RECODE* algorithm can explore the environment efficiently.\n\n**Weaknesses**\n- The idea of grouping similar observations and keeping visitation counts for clusters is not quite novel. The main novelty of this work can be considered to be the representation learning of from the observations.\n- Some parts of the paper are not well presented and therefore hard to be followed by the reader. Specifically, Section 4 which describes the representations learning process should be revised carefully.\n- It is not verified by the presented empirical results that the RECODE algorithm outperforms the MEME algorithm.", "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": "-QAgGlni6tg", "reviewer": "Reviewer_zKdb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper proposes a new clustering-based non-parameteric way of estimating the state visitation density, and uses it to construct a reward to encourage more exploration of less-visited states. The paper also proposes a way of converting the state input into some embedding space. Overall, both ideas seem to have some novelties and merits despite the experiment section can be improved as detailed below.", "summary_of_the_review": "The paper has a potential to demonstrate a novel algorithm. While it shows that it achieves a similar performance as the SOTA on atari games, it does not deliver enough ablation studies to help readers understand how good each component is, and what the new exploration algorithm brings, what the new insights are, why these design choices, etc.", "strength_and_weaknesses": "**Strength**:\n\n* Estimating the state visitation via clustering-based non-parameteric way is intuitive. \n* The results in the figure show that the proposed method achieves similar performance as SOTA on several hard-exploration Atari games. When the tasks contain noisy observations, the proposed method surpasses the SOTA.\n\n**Weaknesses**:\n\n* The paper lacks an intuitive explanation of the detailed RECODE algorithm. There is barely any discussions on why the algorithm is designed as it is. It's not easy to understand when there is only a (rather complex) pseudocode block describing the algorithm.\n* Similarly, in the experiment section, there is no comparison against other exploration algorithms or density estimation algorithms to show the effect of RECODE. The paper compares RECODE and MEME. But it would be more insightful to compare just on the exploration part of the algorithm. Does RECODE leads to different coverage or exploration pattern than other count-based or curiosity-based exploration methods?\n* As for representation learning, it's important to do an ablation study on how good the proposed casual action-state masking method is compared to other representation learning methods such as contrastive learning on observation input, forward/inverse dynamics model learning, reconstruction on observation input, etc. When doing ablation studies, other factors (such as the exploration method) should be controlled to be the same.", "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: Reject