Never Give Up: Learning Directed Exploration Strategies
Authors: Adrià Puigdomènech Badia
Pablo Sprechmann
Alex Vitvitskyi
Daniel Guo
Bilal Piot
Steven Kapturowski
Olivier Tieleman
Martin Arjovsky
Alexander Pritzel
Andrew Bolt
Charles Blundell
Venue:  (2020)
Keywords: deep reinforcement learning
exploration
intrinsic motivation

Abstract: We propose a reinforcement learning agent to solve hard exploration games by learning a range of directed exploratory policies. We construct an episodic memory-based intrinsic reward using k-nearest neighbors over the agent's recent experience to train the directed exploratory policies, thereby encouraging the agent to repeatedly revisit all states in its environment. A self-supervised inverse dynamics model is used to train the embeddings of the nearest neighbour lookup, biasing the novelty signal towards what the agent can control. We employ the framework of Universal Value Function Approximators to simultaneously learn many directed exploration policies with the same neural network, with different trade-offs between exploration and exploitation. By using the same neural network for different degrees of exploration/exploitation, transfer is demonstrated from predominantly exploratory policies yielding effective exploitative policies. The proposed method can be incorporated to run with modern distributed RL agents that collect large amounts of experience from many actors running in parallel on separate environment instances. Our method doubles the performance of the base agent in all hard exploration in the Atari-57 suite while maintaining a very high score across the remaining games, obtaining a median human normalised score of 1344.0%. Notably, the proposed method is the first algorithm to achieve non-zero rewards (with a mean score of 8,400) in the game of Pitfall! without using demonstrations or hand-crafted features.

Published as a conference paper at ICLR 2020
NEVER GIVE UP: LEARNING DIRECTED EXPLORATION STRATEGIES
Adrià Puigdomènech Badia"
Pablo Sprechmann"
Alex Vitvitskyi
Daniel Guo
Bilal Piot
Steven Kapturowski
Olivier Tieleman
Martín Arjovsky
Alexander Pritzel
Andew Bolt Charles Blundell
DeepMind (adriap, psprechmann, avlife, danielguo, piot, skapturowski, tieleman, apritzel, abolt, cblundell) @blundell@@googless @google com
ABSTRACT
We propose reinforcement learning agent to solve hard exploration games by learning a range of directed exploratory policies. We construct an episodic memory- based intrinsic reward using k-nearest neighbors over the agent's 's recent experience to train the directed exploratory policies, thereby encouraging the agent to repeat- edly revisit all states in its environment. A self-supervised inverse dynamics model is used to train the embeddings of the nearest neighbour lookup, biasing the novelty signal towards what the agent can control. We employ the framework of Universal Value Function Approximators (UVFA) to simultancously learn many directed exploration policies with the same neural network, with different trade-offs be- tween exploration and exploitation. By using the same neural network for different degrees of exploration/exploitttion, transfer is demonstrated from predominantly exploratory policies yielding effective exploitative policies. The proposed method can be incorporated run with modern distributed RL agents that collect large amounts of experience from many actors running in parallel on separate environ- ment instances. Our method doubles the performance of the base agent in all hard exploration in the Atari-57 suite while maintaining very high score across the remaining games, obtaining median human normalised score of 1344.0%. Notably, the proposed method is the first algorithm to achieve non-zero rewards (with a mean score of 8,400) in the game of Pitfall! without using demonstrations hand-crafted features.
INTRODUCTION
The problem of exploration remains one of the major challenges deep reinforcement learning. In general, methods that guarantee finding an optimal policy require the number of visits to each state-action pair to approach infinity. Strategies that become greedy after a finite number of steps may never learn to act optimally; they may converge prematurely to suboptimal policies, and never gather the data they need to learn. Ensuring that all state-action pairs are encountered infinitely often the general problem of maintaining exploration (François-Lavet al. 2018 Sutton & Barto 2018). The simplest approach for tackling this problem to consider stochastic policies with a non-zero probability of selecting all actions in each state, e.g. e-greedy Boltzmann exploration. While these techniques will eventually learn the optimal policy in the tabular setting, they are very inefficient and the steps they require grow exponentially with the size of the state space. Despite these shortcomings,
they can perform remarkably well in dense reward scenarios (Mnih et al.) 2015). In sparse reward settings, however, they can completely fail learn, as temporally-extee extendeed exploration (also called deep exploration) is crucial to even find the very few rewarding states (Osband et al. 2016).
"Equal contribution.

---

Published as a conference paper at ICLR 2020
Recent approaches have proposed to provide intrinsic rewards to agents to drive exploration, with focus on demonstrating performance in non-tabular settings. These intrinsic rewards are proportional to some notion of saliency quantifying how different the current state is from those already visited (Bellemare et al. 2016; Haber et al. 2018: Houthooft et al., 2016) Oh et al. 2015 Ostrovski et al. 2017 al. 2017 7| (tadie al. (0115). As the agent explores the environment and becomes familiar with it, the exploration bonus disappears and learning is only driven by extrinsic rewards. This is a sensible idea as the goal is to maximise the expected sum of extrinsic rewards. While very good results have been achieved on some very hard exploration tasks, these algorithms face a fundamental limitation: after the novelty of a state has vanished, the agent is not encouraged to visit it again, regardless of the downstream learning opportunities it might allow (Bellemare et al. 2016; Ecoffet et al.] 2019; Stanton & Clune| 2018). Other methods estimate predictive forward models (Haber et al. 2018; Houthooft et al., 2016 Oh et al., 2015: Pathak et al.] 2017 Stadie ct al. 2015) and use the prediction error as the intrinsic motivation. Explicitly building models like this, particularly from observations, is expensive, error prone, and can be difficult to generalize to arbitrary environments. In the absence of the novelty signal, these algorithms reduce to undirected exploration schemes, maintaining exploration in a non-scalable way. To overcome this problem, careful calibration between the speed of the learning algorithm and that of the vanishing rewards is required (Bcoffet al. 2019 Ostrovski et al. 2017).
The main idea of our proposed approach is to jointly learn separate exploration and exploitation policies derived from the same network, in such a way that the exploitative policy can concentrate on maximising the extrinsic reward (solving the task at hand) while the exploratory ones can maintain exploration without eventually reducing to an undirected policy. We propose to jointly learn a family of policies, parametrised using the UVFA framework (Schaul et al. 2015a), with various degrees of exploratory behaviour. The learning of the exploratory policies can be thought of as a set of auxiliary tasks that can help build shared architecture that continues to develop even in the absence of extrinsic rewards (Jaderberg et al., 2016). We use reinforcement learning to approximate the optimal value function corresponding to several different weightings of intrinsic rewards.
We propose an intrinsic reward that combines per-episode and life-long novelty to explicitly encourage the agent to repeatedly visit all controllable states in the environment over an episode. Episodic novelty encourages an agent to periodically revisit familiar (but potentially not fully explored) states over several episodes, but not within the same episode. Life-long novelty gradually down-modulates states that become progressively more familiar across many episodes. Our episodic novelty uses an episodic memory filled with all previously visited states, encoded using the self-supervised objective Pathak et al. (017)) to avoid uncontrollable parts of the state space. Episodic novelty is then defined as similarity of the current state to previously stored states. This allows the episodic novelty rapidly adapt within an episode: every observation made by the agent potentially changes the per-episode novelty significantly. Our life-long novelty multiplicatively modulates the episodic similarity signal and is driven by a Random Network Distillation error (Burda et al. 2018b). In contrast to the episodic novelty, the life-long novelty changes slowly, relying upon gradient descent optimisation (as opposed to an episodic memory write for episodic novelty). Thus, this combined notion of novelty is able to generalize in complex tasks with large, high dimensional state spaces in which given state is never observed twice, and maintain consistent exploration both within an episode and across episodes.
This paper makes the following contributions: (i) defining an exploration bonus combining life-long and episodic novelty to learn exploratory strategies that maintain exploration throughout the agent's 's training process (to never give up), (ii) to learn a family of policies that separate exploration and exploitation using a conditional architecture with shared weights, (iii experimental evidence that the proposed method is scalable and performs on par or better than state-of-the-ar methods on hard exploration tasks. Our work differs from Savinov et al. (2018) in that is not specialised to navigation tasks. our method incorporates a long- term intrinsic reward and is able to separate exploration and exploitation policies. Unlike |Stanton & Clune 2018), our work relies on no privileged information and combines both episodic and non-episodic novelty, obtaining superior results. Our work differs from Beyer et al. (2019) in that we learn multiple policies by sharing weights, rather than just a common replay buffer, and our method does not require exact counts and so can scale to more realistic domains such as Atari. The paper is organized as follows. In Section 2 we describe the proposed intrinsic reward. In Section 3] we describe the proposed agent and general framework. In Section 4 we present experimental evaluation.
2

---

Published as a conference paper at ICLR 2020
life-long novelty module
RND random network
plafze,ztt1l 1++1)
multipicatiiee modulation
classifier h
RND prediction network
embedding network
k-nearest neighbors
controllable state
episodic
episodic novelty module
emboddinn network
T1
Tt+1
opisodic memory
M
Figure 1: (left) Training architecture for the embedding network (right) NGU's reward generator.
2
THE
INTRINSIC REWARD
We follow the literature on curiosity-driven exploration, where the extrinsic reward is augmented with an intrinsic reward (or exploration bonus). The augmented reward at time is then defined as rf + Bri. where of and rf are respectively the extrinsic and intrinsic rewards, and 8 is a positive scalar weighting the relevance of the latter. Deep RL agents are typically trained on the augmented reward rt, while performance is measured extrinsic reward rf only. This section describes the proposed intrinsic reward r(-
Our intrinsic reward rt satisfies three properties: (i) it rapidly discourages revisiting the same state within the same episode, (ii) it slowly discourages visits to states visited many times across episodes, (iii) the notion of state ignores aspects of an environment that not influenced by an agent's actions.
We begin by providing a general overview of the computation of the proposed intrinsic reward. Then we provide the details of each one of the components. The reward is composed of two blocks: an episodic novelty module and an (optional) life-long novelty module, represented in red and green respectively in Fig. (right). The episodic novelty module computes our episodic intrinsic reward and is composed of an episodic memory, M, and an embedding function f. mapping the current observation to a learned representation that we refer to as controllable state. At the beginning each episode, the episodic memory starts completely empty. At every step, the agent computes episodic intrinsic reward, ri epiiodiic and appends the controllable state corresponding to the current observation to the memory M. To determine the bonus, the current observation is compared to the content of the episodic memory. Larger differences produce larger episodic intrinsic rewards. The episodic intrinsic reward r? This means that the notion of novelty ignores inter-episode interactions: a state that has been visited thousands of times gives the same intrinsic reward as a completely new state as long as they are equally novel given the history of the current episode.
eppiooicc promotes the agent to visit as many different states as possible within a single episode,
life-long (or inter-episodic) novelty module provides a long-term novelty signal to statefully control the amount of exploration across episodes. We do by multiplicatively modulating the exploration bonus spisodic with life-long curiosity factor, ag Note that this modulation will vanish over time, reducing our method using the modulated reward. Specifically, we combine a, with r as follows (see also Fig. (right))
episodic
r cpisodic min (max {a,, 1}
where L is a chosen maximum reward scaling (we fix = for all our experiments). Mixing rewards this way, we leverage the long-term novelty detection that a₁ offers, while rž continues to encourage our agent to explore all the controllable states.
Embedding network: f O R maps the current observation to p-dimensional vector corre- sponding to its controllable state. Consider an environment that has a lot of variability independent of the agent's actions, such navigating busy city with many pedestrians and vehicles. An agent could
3

---

Published as a conference paper at ICLR 2020
visit large number of different states (collecting large cumulative intrinsic rewards) without taking any actions. This would not lead to performing any meaningful form of exploration. To avoid such meaningless exploration, given two consecutive observations, we train a Siamese network (Bromley et al. 1994, Koch et al., 2015) f to predict the action taken by the agent to go from one observation to the next (Pathak al. 2017). Intuitively, all the variability in the environment that is not affected by the action taken by the agent would not be useful to make this prediction. More formally, given a triplet {Te, Qt F composed of two consecutive observations, Tt and It+1, and the action taken by the agent at, we parameterise the conditional likelihood as p(a 2(+1) h(f f (zz)) fIz++1) where h is a one hidden layer MLP followed by a softmax. The parameters of both h and are trained via maximum likelihood. This architecture can be thought of Siamese network with one-layer classifier on top, see Fig. | (left) for an illustration. For more details about the architecture, see App. H.T. and hyperparameters, see App. F
Episodic memory and intrinsic reward: The episodic memory M is a dynamically-sized slot- based memory that stores the controllable states in an online fashion (Pritzel et al. 2017). At time t, the memory contains the controllable states of all the observations visited in the current episode, {f f (21).... ................................ (x)-1)) Inspired by theoretically-justffe
exploration methods turning state- action counts into a bonus reward (Strehl& & Littman 2008), we define our intrinsic reward as
episodic
vn(s(ze)) VENEN, K(f(z)) f.) +
where (x))) is the counts for the visits to the abstract state f (xx). We approximate these counts (xx)) as the sum of the similarities given by a kernel function IRP x Rp -> R. over the content of M. In practice, pseudo-counts are computed using the k-nearest neighbors of f (ax) in the memory M, denoted by N {fi}== The constant guarantees a minimum amount of "pseudo-counts" (fixed to 0.001 in all our experiments). Note that when K is a Dirac delta function, the approximation becomes exact but consequently provides no generalisation of exploration required for very large state spaces. Following Blundell al. (2016); Pritzel et al. (2017), we use the inverse kernel for K,
K(x,y)
d2
where is a small constant (fixed to 10-3 3 in all our experiments), d is the Euclidean distance and de is running average of the squared Euclidean distance of the k-th nearest neighbors. This running average is used to make the kernel more robust to the task being solved, as different tasks may have different typical distances between learnt embeddings. A detailed computation of the episodic reward can be found in Alg. T in App.
Integrating life-long curiosity: In principle, any long-term novelty estimator could be used basis for the modulator 04 We found Random Network Distillation (Burda et al. 2018b RND) worked well, is simple to implement and easy to parallelize. The RND modulator a, is defined by introducing random, untrained convolutional network O + R and training a predictor network 9 O + R that attempts to predict the outputs of g on all the observations that are seen during training by minimizing err(z,) = 110(2;; f) g(*x)]l )1 with respect to the parameters of g. O. We then define the modulator a, as normalized mean squared error, as done in Burda al. (2018b): a = 1 + erv(z,)- where de and me are running standard deviation and mean for err( For more details about the architecture, see App. H.2. and hyperparameters, see App. F
3 THE NEVER-GIVE-UP AGENT
In the previous section we described an episodic intrinsic reward for learning policies capable of maintaining exploration in meaningful way throughout the agent's training process. We now demonstrate how to incorporate this intrinsic reward into a full agent that maintains a collection of value functions, each with different apploration-exploiatatio trade-off.
Using intrinsic rewards as a means of exploration subtly changes the underlying Markov Decision Process (MDP) being solved: if the augmented reward r; rf + Bri varies in ways unpredictable from the action and states, then the decision process may no longer be a MDP, but instead be a Partially Observed MDP (POMDP). Solving PODMPs can be much harder than solving MDPs, so to
4

---

Published as a conference paper at ICLR 2020
avoid this complexity we take two approaches: firstly, the intrinsic reward is fed directly as input to the agent, and secondly, our agent maintains an internal state representation that summarises its history of all imputs (state, action and rewards) within an episode. As the basis of our agent, use Recurrent Replay Distributed DQN (Kapturowski et al., 2019 R2D2) as it combines a recurrent state, experience replay, off-policy value learning and distributed training, matching our desiderata.
Unlike most of the previously proposed intrinsic rewards (as seen in Section D. the never-give-up intrinsic reward does not vanish over time, and thus the learned policy will always be partially driven by it. Furthermore, the proposed exploratory behaviour is directly encoded in the value function and as such it cannot be easily turned off. To overcome this problem, we proposed to jointly learn an explicit exploitative policy that is only driven by the extrinsic reward of the task at hand.
Proposed architecture: We propose to use universal value function approximator (UVFA) Q a, B:) to simultaneously approximate the optimal value function with respect to family of augmented rewards of the form re rf + -.rr. We employ discrete number N of values { ) +=0 including the special case of 30 = and By-1 = 3 where 3 is the maximum value chosen. In this way, one turn-off exploratory behaviour simply by acting greedily with respect to Q(2r, a, 0). Even before observing any extrinsic reward, we are able to learn a powerful representation and set of skills that can be quickly transferred to the exploitative policy. In principle, one could think of having an architecture with only two policies, one with 30 = 0 and one with 31 > 0. The advantage of learning a larger number of policies comes from the fact that exploitative and exploratory policies could be quite different from behaviour standpoint. Having larger number of policies that change smoothly allows for more efficient training. For a detailed description of the specific values of 3; we use in our experiments, see Apple A We adapt the R2D2 agent that uses the dueling network architecture of Wang et al. (2015) with an L.TTM layer after a convolutional neural network. We concatenate to the output of the network a one-hot vector encoding the value of 3 the previous action a, the previous intrinsic reward ri and the previous extrinsic reward rē. We describe the precise architecture in App. H.3 and hyperparameters in App. F
N-1
As a training loss we use a transformed Retrace double Q-learnig loss. In App. [E] we provide the details of the computation of the Retrace loss (Munos et al. 2016). In addition, we associate for each 3 %. with 70 0.997, and YM-1 = 0.99. We remark that the exploitative policy B0 is associated with the highest discount factor 70 Tmax and the most exploratory policy 9N-1 with the smallest discount factor To = Tmmin We can use smaller discount factors for the exploratory policies because the intrinsic reward is dense and the range of values is small, whereas we would like the highest possible discount factor for the exploitative policy in order to be as close as possible from optimizing the undiscounted return. For a detailed description of the specific values of Y's we use in our experiments, see App.
RL Loss functions:
Distributed training:
Recent works in deep RL have achieved significantly improved performance by running on distributed training architectures that collect large amounts of experience from many actors running parallel on separate environment instances (Andrychowicz et al. 2018 ( Marth-Maron
et al. [2018] Burda et al. 201 8b Espeholt al.) 2018 Horgan et al. [0188] Kapturowski et al. 2019 Silver et al. 2016). Our agent builds upon the work by Kapturowski et al. (001)) to decouple learning from acting, with actors (256 unless stated otherwise) feeding experience into a distributed replay buffer and the learner training on randomly sampled batches from it in a prioritized way (Schaul
et al. 2015b). Please refer App. A for details.
4 EXPERIMENTS
We begin by analyzing the exploratory policy of the Never Give Up (NGU) agent with a single reward mixture. We perform such analysis by using minimal example environment in Section 4.1 We observe the performance of its learned policy, as well as highlight the importance of learning a representation for abstract states, In Section 4.2 we analyze the performance of the full NGU agent, evaluating its effectiveness on the Arcade Learning Environment (ALE; Bellemare et al. (013)). We measure the performance of the agent against baselines on hard exploration games, as well as dense reward games. We expand on the analysis of the NGU agent by running it on the full set of Atari games, well showing multiple ablations on important choices of hyperparameters of the model.
5

---

Published as a conference paper at ICLR 2020
100
states expltedd
MMH
Bealin rebert
40-
250030
Figure 2: (Left and Center) Sample screens of Random Disco Maze. The agent is in green, and pathways in black. The colors of the wall change at every time step. (Right) Learning curves for Random projections vs. learned controllable states and a baseline RND implementation.
4.1 CONTROLLED SETTING ANALYSIS
In this section we present simple example to highlight the effectiveness of the exploratory policy of the NGU agent, as well as the importance of estimating the exploration bonus using a controllable state representation. To isolate the effect of the exploratory policy, restrict the analysis to the case of a single exploratory policy (N = 1, with | 0.3). We introduce gridworld environment, Random Disco Maze, implemented with the pycolab game engine (Stepleton 2017), depicted in Fig. 2 (left). At each episode, the agent finds itself in a new randomly generated maze of size 21x21. The agent can take four actions {left, right, up, down), moving a single position at time. The environment is fully observable. If the agent steps into a wall, the episode ends and a new maze is generated. Crucially, every time step, the color of each wall fragment is randomly sampled from a set of five possible colors, enormously increasing the number of possible states. This irrelevant variability in color presents a serious challenge algorithms using exploration bonuses based on novelty, as the agent is likely to never see the same state twice. This experiment is purely exploratory. with no external reward. The goal is to see if the proposed model can learn meaningful directed exploration policy despite the large visual distractions providing a continual stream of observation novelty to the agent. Fig. shows the percentage of unique states (different positions in the maze) visited by agents trained with the proposed model and one in which the mapping f is a fixed random projection (i.c. f is untrained). The proposed model Iearns to explore any maze sampled from the dask-distribution. The agent learns strategy that resembles depth- forth-first search: it explores as far as possible along each branch before backtracking (often requiring backtracking a few dozen steps to reach unexplored area). The model with random projections, well our baseline of RND, do not show such exploratory behaviour" Both models do learn to avoid walking into walls, doing so would limit the amount of intrinsic reward would receive. However, staying alive is enough: simply oscillating between two states will produce different (and novel) controllable states at every time step.
4.2 ATARI RESULTS
In this section, we evaluate the effectiveness of the NGU agent on the Arcade Learning Environment (ALE; (Bellemare et al. 2013)) ). We use standard Atari evaluation protocol and pre-processing as described in Tab. of App. F.4 with the only difference being that we do not use frame stacking. We restrict NGU to using the same setting and data consumption as R2D2, the best performing algorithm on Atari (Kapturowski et al. 2019). While we compare our results with the best published methods on this benchmark, we note that different baselines use very different training regimes with very different computational budgets. Comparing distributed and non-distributed methods is in general difficult. In an effort to properly assess the merits the proposed model we include two additional baselines: as NGU is based on R2D2 using the Retrace loss (instead of its n-step objective) include this as a baseline, and since we use RND as a reward modulator, we also include R2D2 with Retrace using the RND intrinsic reward. These methods are all run for 35 billion frames using the same protocol as that of R2D2 (Kapturowski et al. 2019). We detail the use of compute resources of the algorithms in App. D We report the return averaged over different seeds.
Architecture: We adopt the same core architecture as that used by the R2D2 agent to facilitate comparisons. There are still few choices make, namely: the size of the learned controllable states,
See video of the trained agent here: https://youtu. be/ 99T 4ruPrHo

---

Published as a conference paper at ICLR 2020
Average Human Normalized Score
Human normalized score
NGU(N=32)
2.0
20
CMR=0.5
Nw16
1.5
15
8=0.2
1.0
10
B=0.5
w/o RND
0.5
5
w/o r
0.0
Hard exploration games
Dense reward games
Figure
Human Normalized Scores on dense reward and hard exploration games.
the clipping factor L in (1). and the number of nearest neighbours for computing pseudo-counts in (2). We selected these hyperparameters by analysing the performance the single policy agent, representative exploration games: Montezuma's 's Revenge and Pitfall!. We
NGU(N = 1), report this study in App. B. We used the same fixed set of hyperparameters in all the remaining experiments.
We performed further ablations in order to better understand several major design choices of the full NGU agent on a set of 8 Atari games: the set of dense reward games chosen to select the hyperparameters of Mnih et al. (2015), as well as 3 hard exploration games (Montezuma" 's Revenge, Pitfall!, and Private Eye). For detailed description of the results on these games as well as results on more choices of hyperparameters, please see App The ablations we perform are on the number of mixtures N, the impact of the off-policy data used (referred to as CMR below), the maximum magnitude of B (by default 0.3 if not explicitly mentioned), the use of RND to scale the intrinsic reward, and the performance of the agent in absence of extrinsic rewards. We denote by Cross Mixture Ratio (CMR) the proportion in the training batches of experience collected using different values of 3; from the one being trained. A CMR
NGU agent:
means training each policy only with data produced by the same 3, while CMR of 0.5 means using equal amounts of data produced by 3r and Bjzi. Our base agent NGU has a CMR of 0.
The results are shown in Fig. 3 Several conclusions
be extracted from these results: Firstly, sharing experience from all the actors (with CMR of 0.5) slightly harms overall average performance on hard exploration games. This suggests that the power of acting differently for different condi- tioning mixtures is mostly acquired through the shared weights of the model rather than shared data. Secondly, we observe an improvement, on average, from increasing the number of mixtures N on hard exploration games. Thirdly, one can observe in analyzing the value of B, the value of B 0.3 is the best average performing value, whereas 3 = 0.2 and 3 = 0.5 make the average performance worse on those hard exploration games. These values indicate, in this case, the limits in which NGU is either not having highly enough exploratory variants (3 too low) or policies become too biased towards exploratory behavior (3 too high). Further, the use of the RND factor seems to be greatly beneficial on these hard exploration games. This matches the great success of existing literature, in which long-term intrinsic rewards appear to have great impact (Bellemare et al. 2016 Ostrovski et al. 2017 Choi et al. 2018). Additionally, as outlined above, the motivation behind studying these variations on this set of 8 games is that those hyperparameters are of general effect, rather than specific to exploration. However, surprisingly, with the exception of the case of removing the extrinsic reward, they seem have little effect on the dense reward games we analyze (with all eиror bars overlapping). This suggests that NGU and its hyperparameters are relatively robust: as extrinsic rewards become dense, intrinsic rewards (and their relative weight to the extrinsic rewards) naturally become less relevant. Finally, even without extrinsic reward r we can still obtain average superhuman performance on the 5 dense reward games we evaluate, indicating that the exploration policy of NGU is an adequate high performing prior for this set of tasks. That confirms the findings of Burda et al. (018a)), where they showed that there is high degree of alignment between the intrinsic curiosity objective and the hand-designed extrinsic rewards of many game environments. The heuristics of surviving and exploring what is controllable seem to be highly general and beneficial, as have seen in the Disco Maze environment in Section 4.1 well as on Atari.
7

---

Published as a conference paper at ICLR 2020
Algorithm
Gravitar
MR
Pitfall!
PrivateEye
Solaris
Venture
Human
3.4k
4.8k
6.5k
69.6k
12.3k
1.2k
Best baseline
15.7k
11.6k
0.0
11k
5.5k
2.0k
RND
3.9k
10.1k
8.7k
3.3k
1.9k
R2D2+RND
15.6k=0.6k
10.4k
-0.5+0.33
19.5k
4.3k:t0.6k
2.7k:t0.0k
ReDa(Retrace)
13.3k=0..k
2.3k=00.4k
-3.5
32.5k
2.0k+-0.0k 1.0k
-GUNN=I)-RND
12.4k-t0.8kk
3.0k++0.0k
15.2k+
40.6k+t0.0k
1.7k
46.4+t37.99
NGU(N=1)
11.0k+00.7k
8.7k+112k
9.4k-42.2k
60.6k+16.3k
1.9k+11.kk
876,3++14.55
NGU(N=32)
14.1k
8.4k+t4.5k 1.64
100.0k+0.4k
4.9k-t0.3k
1.7k+t0.1k
Table 1: Results against exploration algorithm baselines. Best baseline takes the best result among R2D2 (Kapturowski et al. (2019), DQN+ + PixeICNN (Ostrovski et al., 2017), DQN + CTS (Bellemare
et al. 2016). RND (Burda et al. 2018b), and PPO CoEx (Choi et al. (018)) for each game.
1.79
Moan Score Hard Exploration Cames
1.75
Modian IN Score Hard Exploration Gannes
Normaited Score
1.30
Vomnea Notmalieed Score
1.30
NGUN321
1.25
NGUII RND
1.00
1.00
IND
0.75
NGU(S3)
0.75
0.30
NGGU111
0.50
0.25
MEGUIT-INN
0.25
J0DD
0.00
0.5
1.5
2.0
3.5 1ot0
0.00
0.5
2.0
2.5
3.5
Prames
Prames
1et0
Figure 4: Human Normalized Scores on the 6 hard exploration games.
Hard exploration games: We now evaluate the full NGU agent on the six hard exploration games identified by [Blllemare al. (201)). We summarise the results on Tab The proposed method achieves on similar or higher average return than state-of-the-an baselines on all hard exploration tasks. Remarkably, to the best of our knowledge, this is the first method without use of privileged information that obtains a positive score on Pitfall!, with NGU(N = I>-RND obtaining a best score of 15,200. Moreover, in 4 of the 6 games, NGU(N = 32) appears to substantially improve against the single mixture case NGU(N = 1). This shows how the exploitative policy is able to leverage the shared weights with all the wiwtinniccaalyyonittiiiio
mixtures to explore games in which it is hard to do so, but still optimize towards maximizing the final episode score. In Fig. 4 we can see these conclusions more clearly: both in terms of mean and median human normalized scores, NGU greatly improves upon existing algorithms.
While direct comparison of the scores is interesting, the emphasis of this work is on learning directed exploration strategies that encourage the agent to cover as much of the environment as possible. In Fig. 4.2 (left) we observe the average episodic return of NGU run with and without RND on Pitfall!. NGU(N = 32) is able to learn directed exploration policy capable of exploring average of 46 rooms per episode, crossing 14 rooms before receiving the first extrinsic reward. We also observe that, in this case, using RND makes our model be less data efficient. This is also the case for NGU(N = 1), as observed on NGU(N = 1>-RND in Tab. [ the best performing Pirfall! agent. We conjecture three main hypotheses explain this: firstly, on Pitfall! (and unlike Montezuma's 's Revenge) rooms frequently aliased to one another, thus the agent does not obtain a large reward for discovering new rooms. This phenomenon would explain the results seen in Fig. (right), in which RND greatly improves the results of NGU(N = 32). Secondly, the presence of a timer in the observation acts as spurious source of novelty which greatly increases the number of unique states achievable even within a single room. Thirdly, as analyzed in Section 3.7 of Burda et al. (2018b), often keep 'interacting with danger' instead of exploring further, and Pirfall! is a game in which this can be highly detrimental, due to the high amount of dangerous elements in each room. Finally, we observe that NGU(N- = 1) obtains better results than NGU(N = 32). Our intuition is that, in this case, single policy should be simpler to learn and can achieve quite good results on this task, since exploration and exploitation policies are greatly similar.
traited agents
Dense reward games: Tab. 2 shows the results of our method on dense reward games. NGU(N = 1) underperforms relative to R2D2 on most games (indeed the same can be said of R2D2(Retrace) that serves the basis of NGU). Since the intrinsic reward signal may be completely misaligned with the goal of the game, these results may be expected. However, there are cases such as Pong, in which NGU(N = 1) catastrophically fails to learn perform well. Here is where NGU(N = 32) solves
8

---

Published as a conference paper at ICLR 2020
(SUU on pttball
NOUGZ) on Monterunna's Revenge
RND 100 IND
Moar Epionds Return
w/ RND
15000
12000
Wi RND
7500
5000
2000
2500
0.0
1.0
3.5
2.0
2.5
3.5
0.0
0.5
3.0
2.0
2.5
3.0
3.5
Figure 5: Mean episodic return for agents trained (left) Pitfall! and (right) Montezuma's 's Revenge.
Algorithm
Pong
QBert
Breakout
Space Invaders
Beam Rider
Human
14,6
13,4k
30.5
1.6k
16.9k
R2D2
21.0
408.8k
837.7
43.2k
188.2k
R2D2+RND
20.7++000
3 ..k
815.8+5.3
54.5k+2.8k
85.7k+99.0k
R2D2(Retrace)
20.9+0.0
415.6k 8k
838.3+7.00
35.0k+13.0k
111.
NGU(N=1)-RND
-8.1
507.
8.4.0=+0.0
45.3k+t4.9k
166.5k 6k6
NGU(N=I)
-9.412266
684.7k18.88k
864.0.10.0
43.9k
114.6k
NGU(N=32)
19.6.10.1
465.8k
532.8116..5
44.6
Table 2: Results against baselines on dense reward games.
this issue: the exploitative policy learned by the agent is able reliably learn to play the game. Nevertheless, NGU(N- = 32) has limitations: even though its learned policies are vastly superhuman and empirically reasonable, they do not match R2D2 on Breakout and Beam Rider. This suggests that the representations learned by using the intrinsic signal still slightly interfere with the learning process of the exploitative mixture. We hypothesize that alleviating this further by having non-shared representations between mixtures should help in solving this issue.
Results on all Atari 57 games: The proposed method achieves an overall median score of 1354.4%, compared to 95% for Nature DQN baseline, 191.8% for IMPALA, 1920.6% for R2D2, and 1451.8% for R2D2 using retrace loss. Please refer to App. G for separate results on individual games. Even though its overall median score is lower than R2D2, NGU maintains good performance all games, performing above human level on 51 out of the 57 games. This also shows further confirmation that the learned exploitative mixture is still able to focus maximizing the score of the game, making the algorithm able to obtain great performance across all games.
Analysis of Multiple Mixtures: in Fig. 6 we can see NGU(N 32) evaluated with Bu 0 (used in all reported numerical results) against NGU(N = 32) evaluated with 3ar = 0.3. We can observe different trends in the games: on Be the policies of the agent seem converge to the exploitative policy regardless of the 3 condition, with its learning curve being almost identical to the one shown for R2D2 in Kapturowski al. (2019). As seen in App. G this common in many games. The second most common occurrence is what we see on Pitfall! and Beam Rider, in which the policies quantitatively learn very different behaviour. objective, and sometimes it does so by benefiting from the learnings of the exploratory policy, as it is the case in Pitfall [] where R2D2 never achieves a positive score. Finally, there is the exceptional case of Montezuma's 's Revenge, in which the reverse happens: the exploratory policy obtains better score than the exploitative policy. In this case, extremely long-term credit assignment is required order for the exploitative policy to consolidate the knowledge of the exploratory policy. This is because, to achieve scores that are higher than 16k, the agent needs to go to the second level of the game, going through many non-greedy and sometimes irreversible actions. For more detailed analysis of this specific problem, see App. I.2
these cases, the exploitative learns to focus on its
5 CONCLUSIONS
We present a reinforcement learning agent that can effectively learn on both sparse and dense reward scenarios. The proposed agent achieves high scores all Atari hard-exploration games, while still maintaining very high average score over the whole Atari-57 suite. Remarkably, it is, to the best of our knowledge, the first algorithm to achieve non-zero rewards on the challenging game of Pitfall! without relying on human demonstrations, hand-crafted features, manipulating the state of the environment. central contribution of this work is a method for learning policies that can maintain
"ee videos of NGU Pitfall with 8o, 8ai:

---

Published as a conference paper at ICLR 2020
Montezuma's is Revenge
PRiail!
20000
10000
10000
5000
1.5 Frames
3.5
0.5
1.5
3.5
1610
Eramus
1610
12filert
(temm Rider
500000
Boturr
250000
1010
1610
Figure 6: NGU(N=32) behavior for 3o (blue) and A51 (orange).
exploration throughout the training process. In the absence of extrinsic rewards, the method produces policy that aims at traversing all controllable states of the MDP in a depth-first first manner. We highlight that this could have impact beyond this specific application and/or algorithmic choices. For instance, could use it as a behaviour policy facilitate learning models of the environment for planning methods.
prior
The proposed method is able to leverage large amounts of compute by running on distributed training architectures that collect large amounts of experience from many actors running in parallel on separate environment instances. This has been crucial for solving most challenging tasks in deep RL in recent years (Andrychowicz et al., 2018 Espeholt et al.) 2018 Silver et al. 2016). and this method is able utilize such compute obtain strong performance on the set of explorrttoo games on Atari. While this is certainly desirable feature and allows NGU to achieve remarkable performance, it comes at the price of high sample complexity, consuming large amount of simulated experience taking several days of wall-clock time. An interesting avenue for future research lies in improving the data efficiency of these agents.
Further, the episodic novelty measure relies on the notion of controllable states to drive exploration. As observed on the Atari hard-exploration games, this strategy performs well on several tasks, but it may not be the right signal for some environments. For instance, in environments it might take more than two consecutive steps to see the consequences of the actions taken by the agent. An interesting line for future research is learning effective controllable states beyond a simple inverse dynamics model.
Additionally, the proposed work relies the assumption that while different, exploratory and exploitative policies that are similar enough to be effectively represented using a shared parameterization (implemented using the UVFA framework). This can be limiting when the two policies are almost adversarial. This can be seen in games such as 'Surround' and 'Ice hockey".
find good
Finally, the hyperparameter depends on the scale of the extrinsic reward. Thus, environments with significantly different extrinsic reward scales, might require different values of J3. An interesting avenue forward is the dynamic adaptation of (, which could be done by using techniques such as Population Based Training (PBT)(Jaderberg et al., 2017) or Meeta-graients/ Xu et al., 2018). Another advantage of dynamically tuning this hyperparameter would be to allow for the model to become completely exploitative when the agent has reached a point in which further exploring does not lead to improvements on the exploitative policy. This not trivially achievable however, as including such mechanism would require calibrating the adaptation to be aligned to the speed of learning of the exploitative policy.
ACKNOWLEDGMENTS
We thank Daan Wierstra, Steph Hughes-Fitt, Andrea Banino, Meire Fortunato, Melissa Tan, Benigno Uria, Borja Ibarz, Mohammad Gheshlaghi Azar, Remi Munos, Bernardo Avila Pires, Andre Barreto, Vali Irimia, Sam Ritter, David Raposo, Tom Schaul and many other colleagues at DeepMind for helpful discussions and comments on the manuscript.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, al. Learning dexterous in-hand manipulation. arXiv preprint 12Xi::800800017 2018.
Gabriel Barth-Maron, Matthew Hoffman, David Budden, Will Dabney, Dan Horgan, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint arXiv: 1rXiv:184.008617 2018.
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. 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.
Lucas Beyer, Damien Vincent, Olivier Teboul, Sylvain Gelly, Matthieu Geist, and Olivier Pietquin. Mulex: Disentangling exploitation from exploration in deep rl. arXiv preprint 2019.
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: (606::6666004400 04460, 2016.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. In Advances in neural information processing systems, pp. 737-744, 1994.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexci A Efros. Large-scale study curiosity-driven learning. arXiv preprint 1rXi::8808.04355 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv:1810. 1814. 2018b.
Jongwook Choi, Yijie Guo, Marcin Moczulski, Junhyuk Oh, Neal Wu, Mohammad Norouzi, and Honglak Lee. Contingency-aware exploration in reinforcement learning. arXiv preprint 1rXiv:1811.01483. 2018.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901. 10995, 2019.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, al. Impala: Scalable distributed deep-rl with importance weighted letor-learner architectures. arXiv preprint arXiv: 1802.01561, 2018.
Vincent François-Lavel Peter Henderson, Riashat Islam, Mare G Bellemare, Joelle Pineau, et al. An introduction to deep reinforcement learning. Foundations and Trends in Machine Learning, 11 (3-4):219-33) 354, 2018
Nick Haber, Damian Mrowca, Stephanie Wang, Li F Fei-Fei, and Daniel L Yamins. Learning to play with intrinsicallymootiali self-aware agents. In Advances in Neural Information Processing Systems, pp. 8388-8399, 2018.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv:1803 00993, 2018.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, pp. 1 1109-1111 17, 2016.
11

---

Published as a conference paper at ICLR 2020
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611.05397 2016.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv: 1.09846, 2017.
Steven Kapturowski, Georg Ostrovski, Will Dabney, John Quan, and Remi Munos. Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019.
Hyoungseok Kim, Jaekyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Exploration with mutual information maximizing state and action embeddings. arXiv preprini arXiv:1810.01176. 2018.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. Advances in Neural Information Processing Systems, pp. 1046-1054, 2016.
Junhyuk Oh, Xiaoxiao Guo, Honglak Lee, Richard L Lewis, and Satinder Singh. Action-conditional video prediction using deep networks in atari games. In Advances in neural information processing systems, pp. 2863-2871 2015.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances In Neural Information Processing Systems, pp. 4026 4034, 2016.
Georg Ostrovski, Marc G Bellemare, Aäron van den Oord, and Rémi Munos. Count-based exploration with neural density models. Proceedings of the 34th International Conference on Machine Learning-
Learning-Volume Volume 70, pp. 2721-2730. JMLR. org, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pp. 16-17, 2017.
Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, et al. Observe and look further: Achieving consistent performance on atari. arXiv preprint arXiv:1805.11599. 2018.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomênech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. ICML, 2017.
Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Mare Pollefeys, Timothy Lilli- crap, and Sylvain Gelly. Episodic curiosity through reachability. arXiv preprint 1rX.v:1810.02274, 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pp. 1312-1320, 2015a.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. CoRR, abs/15 1.05952, 2015b.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
12

---

Published as a conference paper at ICLR 2020
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv:1507.008844
2015. 2015.
Christopher Stanton and Jeff Clune. Deep curiosity search: Intra-life exploration can improve perfor- mance challenging deep reinforcement learning problems. arXiv preprint arXiv:/806.0055: 2018.
Tom Stepleton. The pycolab game engine. htt.pp///gshhh...ccmm////eaaappp trre/maatter/pycolla 2017.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):130--1333 2008.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 1..661, 2015.
David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. arXiv preprint arXiv:1811.11335 2018.
Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-gradient reinforcement learning. In Advances in neural information processing systems, pp. 2396-2407, 2018.
13

---

Published as a conference paper at ICLR 2020
A EVALUATION SETUP
The evaluation we do is also identical to the one done in R2D2 Kapturowski et al. (2019): a parallel evaluation worker, which shares weights with actors and learners, runs the Q-network against the environment. This worker and all the actor workers are the two types of workers that draw samples from the environment. For Atari, we apply the standard DQN pre-processing, as used in R2D2. More concretely, this is how actors, evaluators, and learner are run:
Learner:
Sample from the replay buffer a sequence augmented rewards rt, intrinsic rewards ri. observations x, actions and discounts 7
Use Q-network to learn from (Tt, H. a)) with retrace using the procedure used by R2D2. As specified in Fig. ri is sampled because it is fed as an input to the network.
Use last frames of the sampled sequences to train the action prediction network as specified in Section[]] This means that, for every batch of sequences, all time steps are used to train the RI. loss, whereas only 5 time steps per sequence are used to optimize the action prediction loss.
(If using RND) also use last 5 frames of the sampled sequences to train the predictor of RND as also specified in Section
Evaluator and Actor
Obtain 24, rf ri and discount %/-
With these imputs, compute forward pass of R2D2 obtain de-
With 3e, compute ri using the embedding network described in Section
(actor) Insert It, dt, Tr rf Barf, Ti, and r in the replay buffer.
Step on the environment with de.
Distributed training
As in R2D2, we train the agent with a single GPU-based learner, performing approximately network updates per second (each update
mani-batch of 64 length-80 sequences, explained below, and each actor performing ~ 260 environment steps per second on Atari. We assign to each actor fixed value the set {B,), N-1 and the actor acts according to an e-greedy version of this policy. More concretely for the j-th actor assign the value 8h with h mod N - 1. In our experiments, use the following 3;
0
if f
8.
3
if N
B (10 (N-2)) otherwise
where a is the sigmoid function. This choice of 3r, as you can see in 7(a) allows to focus more on the extreme cases which are the fully exploitative policy and very exploratory policy.
In the replay buffer, we store fixed-length sequences of (x, r) tuples. In all our experiments we collect sequences of length timesteps, where adjacent overlap by 40 time-steps. These sequences never cross episode boundaries. Additionally, we store in the replay the value of the 8r used by the actor as well the initial recurrent state, that we use initialize the network at training time. Please refer to Kapturowski et al. (2019) for detailed experimental of trade-off's on different treatments of recurrent states in replay. Given single batch of trajectories we unroll both online and target networks the same sequenee of states to generate value estimates. We use prioritized experience replay. We followed the same prioritization scheme proposed in Kapturowski et al. (2019) using a mixture of max and mean of the TD-errors with priority exponent 7) 1.0. In addition, associate for each 3 a 7/2 such that:
(N - 2) log (1- 7max) ) + log 7min)
7/4 = exp
(4)
N
14

---

Published as a conference paper at ICLR 2020
where 7max is the maximum discount factor and Ymin is the minimal discount factor. This form allows to have discount factors evenly spaced in log-space between Ymax and - Yminn For more intuition, we provide a graph of the { W- in Fig 7(b in App We remark that the exploitative policy Po is associated with the highest discount factor 70 "mmx and the most exploratory policy 0y-1 with the smallest discount factor To 7min- We can use smaller discount factors for the exploratory policies because the intrinsic reward is dense and the range of values is small, whereas we would like the highest possible discount factor for the exploitative policy in order to be as close Tmax 0.997 and
possible to optimizing the undiscounted return. In experiments,
Tmin = 0.99.
Values of the intrinsic reward scale
0.30
Values the discount factor
0.25
0.996
0.20
0.994
0.15
0.10
0.992
0.05
0.990
10
10
20
Indices of the policy
Indices of the policy
(a) Values taken by the (-)
(b) Values taken by the {7; [r
N-1
Figure Values taken by the [ N-1 and the {m)) for 32 and 0.3.
A.1 NEVER-GIVE-UP INTRINSIC REWARD ALGORITHM
We present the algorithm for computing the intrinsic reward in Alg. [ We follow the notations defined in Sec. in the paragraph relative to the episodic intrinsic reward:
M the episodic memory (xo)), (f.)),..,,((.......
containing at time t the previous embeddings
& is the number of nearest neighbours.
N (ff) is the set of k-nearest neighbours of f(x) in the memory M.
the kernel defined as K (xx y)
where is small constant, the Euclidean 3"
d2
distance and d² running average of the squared Euclidean distance of the k-nearest neighbors.
i the pseudo-counts constant.
f cluster distance.
Sm maximum similarity.
A.2 COMPLEXITY ANALYSIS
The space complexity constant. The number of weights that the network has can be computed from the architecture seen in App. F Furthermore, for episodic memory buffer, pre-allocate memory at the beginning of training, with size detailed in App. F cases in which the episode is longer than the size of the memory, the memory
ring buffer, deleting oldest entries first.
Time complexity is O(M N). where is the number of frames, and M is the size our memory. This is due the fact that do one forward pass per frame, and we compute the distance from the embeddings produced by the embeddings network to the contents of our memory in order to retrieve the k--narest neighbors.
15

---

/* Normalize the distances de with the updated moving average di Published as a conference paper at ICLR 2020
Algorithm 1: Computation of the episodic intrinsic reward at time t: ri
episodic
Input :M; k; (x)); C; e; E; 8mi dm
Output:r? Epiiioiii
Compute the k-nearest neighbours of f(z)) in M and store them in list Ni Create a list of floats du of size k
/* The 1ist dæ will contain the distances between the embedding f(x)) and its neighbours N
for ( do
dxli] - d' Nf(z),
end
Update the moving average de with the list of distances da
*/
dn de 2
/* Cluster the normalized distances dn i.e. they become 0 if too small and 0g is list of & zeros.
dn + max - {,),
Compute the Kernel values between the embedding f(x)) and its neighbours No.
K2 -h=
/* Compute the similarity between the embedding f(x) and its neighbours No.
V K.[i+c +c
* Compute the episodic intrinsic reward at time t: r/.
8m then episodic
12
13 else
episadic
B ABLATIONS FOR NGU(N=1)
As mentioned in Section 4.2 here show ablations the size of the learned controllable states, the clipping factor L in and the number of nearest neighbours to use for computing pseudo-coume in (2)
Due to the lack of pure exploitative mode, as seen in 4.2 NGU(N=1) fails to perform well in dense reward games. Therefore, in order to obtain high signal from these ablations, we analyze the performance of NGU(N=1) on the two most popular sparse reward games: Montezuma's 's Revenge and Pirfall!
B. SIZE OF CONTROLLABLE STATES
In Fig. 8 and Fig. we can the performance of NGU(N=1) with different sizes of the size of the controllable state on Pitfall! and Montezuma's Revenge respectively. As we can observe, that there is small to no impact on Pitfall!. with scores that sometimes reach more than 25,000 points. On Montezuma's 's Revenge 32 the value that consistently better than 64. A size of 16 as the controllable state size sometimes solves the level, but is in general less stable.
B.2 NEAREST NEIGHBORS USED
We proceed to show a similar analysis on Fig. 10 and Fig. IT regarding the amount of nearest neighbors Pitfall! and Montezuma's 's Revenge respectively. As see, there slight gains
16

---

Published as a conference paper at ICLR 2020
Controllable state size abiation Pizzall
Controllubllo on Montegume'ss Bovenge
40000
Moan Apptend Return
64
15000
64
32
10000
Mean
20000
5000
1.5
Frames
1e10
Fintues
le10
Figure 8: Mean episodic return for agents trained Pitfall!.
Figure 9: Mean episodic return for agents
trained Montezuma's Revenge.
NN ablation Pitfall
NN ablation Mentezuma's Revenge
Mean Reeuur
50000
Neighbors
Meai Eepitod Retum
10030
Neighburs
40000
hoors
10 Noighbors
Netghbors
Neughbors
20000
5000
250n
Frames
1w10
Frames
1610
Figure 10: Mean episodic return for agents trained Pitfall!.
Figure 11: Mean episodic return for agents trained Montezuma'ss 's Revenge.
from using more neighbors on Pitfall!, whereas there is a clear difference in performance in using 10 neighbors Montezuma's ''s Revenge when compared using 5 or 30 neighbors.
B.3 CLIPPING FACTOR
Finally, we show the performance of NGU(N=1) on Fig. 12 and Fig. 13 regarding the clipping factor Pirfall! and Montezuma's Revenge respectively. As we can observe, Pitfall! again robust to the value of this hyperparameter, with marginally worse performance in the case of L 10. This is expected, as RND is generally detrimental to the performance NGU on Pitfall!, as seen in Section On the other hand, the highest value of clipping appears to work best on Montezuma's 's Revenge. nn our initial investigations, we observed that clipping this value was required on Montezuma Revenge make the algorithm stable. Further analysis is required in order show the range of values I, that are higher than 10 and are detrimental to the performance of NGU(N=1) on this task.
C ABLATIONS FOR NGU(N=32)
C GENERAL ABLATIONS
Tab. 3 shows the results for all the ablations we performed on 8 games for NGU(N = =32). We can see that the conclusions of Sec. 4.2 hold, with a few additional facts to observe:
The best score in Montezuma's Revenge is obtained by using a non-zero Cross Mixture Ratio, even though it is relatively close to the score obtained by NGU(N = 32).
and N have lower average human normalized score on the set of hard exploration games when compared to N 16 or N 32. Concretely on the set of hard
Clipping L on Patall
Clipping L ablation on Monteruma's Revenge
40000
L-2.5
Moan Eppisoca Return
15000
L-2
30000
L-10
10000
L-10
20000
5000
10000
Mean
0.0
0.5
1.5
2,0
2.5
3.5
0.5
1.0
1.5
2.0
2.5
3.5
Frames
1e10
Frames
1610
Figure 12: Mean episodic return for agents trained Pitfall!.
Figure 13: Mean episodic return for agents trained Montezuma's 's Revenge.
17

---

Published as a conference paper at ICLR 2020
Space
Algurithm
Pong
Qbert
Breakout
Beum Rider
MR
Piial!
Privateliye
Invaders
Human
14.6
13.4k
30.5
L,6k
16.9k
4.8k
6.5k
69.6k
NGU(N=32)
19.6:001
165.8k.184.90
532.8.166.5
1..6k
68.7k
10.4k116k
8.5k
100.0k100.4k 00.4k
N=2
20.6=0.11
457.7k=+22..0
576.0:224.9
68.0k=6..2k
7..kk=9.0k
11.1411k
-1.64:099
40.6k:t00.1K
N=8
20.0=0.3
481 8k:4411211 .k
524.11:28.3
43.1k=2..5k
64.0k=3.8k
7.8k20.3k
-1.9::04
38.5k-4
N=16
17.2=1.0
444.2k:461.7k
549.0::1..0
46.4k#3.5k
53.9
9.5k
5.0k=1.2k
22.0k
CMR=0.5
19.0=0.3
73..9k:43.99
516.9:220.1
40.3V:17.11K
74.9k-55.9
12.0k-0..k
16.89-466..k
0=0,2
20.3=002
250.1k:424.7k
525.0==38.2
13.9k=1.33k
10.6k=
6.9k=0.1k
3.3k#1.4k
40.00++0.0k
9.0.5
1..8-112
480 58.54k
451.6:117.2
40.2k:14.8k
62.3k
11.3k-10.5k
1.3k
44.5k:13.2k
w/o RND
19.7=0.4
680.3k::444kk
19..7419.1
47.6k=3.7k
87.1k:9.1Ik
3.0k=0.0kk
7.7k#0.9k
10.5k:20.1k
w/o pd
.8.4.11.9
1..
38..01:0.0
5.5k
6.4k
3.4k10.7k
600.4.146889
7.5k
Table 3: Ablation results 8 Atari games.
Algorithm
Gravitar
Solaris
Venture
Human
12.3k
NGU(N=32)
14. 0.1kk
4.9k=033k
1.7k
3=0.2
14.2k=0.3k
6.4k=1.4k
2.3ksb0.2k
83005
13.5k-10.4k
2.0kc:::
Table 4: Further ablation results on hard exploration games.
exploration games of Tab. they only achieve super-human performance on Montezuma's Revenge.
Even though we have seen that the results of B 0.2 and 3 0.5 have lower average on the 3 hard exploration games of Tab. they still individually outperform RND, R2D2, R2D2(Retrace), and R2D2+RND on Pirfall! and Private Eye.
In the case of Private Eye the distance in score might be misleading, rewards are very sparse of large value. For instance, after reaching score of 40k, if we ignore minor rewards, there are only
rewards to be collected of around 30k points. This creates what seems be large differences in scores.
On Breakout, a high score achieved without extrinsic reward. This due to the fact that the exploratory policy learns to survive, which eventually leads to a high score.
C.2 FURTHER ABLATIONS ON HARD EXPLORATION
On Tab we show further results on the case of 3 0.2 and 0.5. We compare them human performance as well as the base NGU(N = 32), with 5 = 0.3.
As we can observe, in this case the difference in terms relative performance among games less pronounced than the ones observed on Tab. 3 In fact, results are slightly better for both values of B on all games, with a maximum difference We hypothesize that this is due the nature of these specific games: the policies learnt these three games seem to focus on exploitation rather than extended exploration of the environment, and that case, similar to what we see for dense reward games in Sec. 4.2 the method shows less variability with respect to this hyperparameter.
1.5k points on Solaris between / 0.3 and B = 0.2.
D ALGORITHM COMPUTATION COMPARISON
On Tab. we we can see a comparison of the computation used between different algorithms.
Computation is still difficult to compare even when taking actor steps and parameter updates into account: distributed the number actors in distributed setups will affect how much data the learner will be able consume, but also how off-policy such data is (e.g. in R2D2, if learner is learning from many actors, the data that sampled from the replay buffer will be more recent than with fewer actors).
E DETAILS ON THE RETRACE ALGORITHM
Retrace (Munos al. 2016) is off off-policy Reinforcement Learning algorithm that can be used for evaluation or control. In the evaluation setting the goal is mainly to estimate the action-value function Q" of target policy from trajectories drawn from behaviour policy μ.. In the control
18

---

Published as a conference paper at ICLR 2020
Algorithm
Number of actors
Total Number of frames
R2D2 Kapturowski et al. (2019)
256
35 B
(2D2(Kerrace)
256
35
R2D2 RND
256
35 B
NGU-RND(N=1)
256
35 B
NGU (N=1)
256
35 B
NGU (N=32)
256
35 B
DQN PixelCNN Ostrovski al. (2017)
1
150 M
DQN + CTS Bellemare et al. (2016)
1
150 M
RND** Burda et (018b)
1024
16 B (2 B)
PPO + CoExCChoi
Choi et al. 2018
1024
2 B
Table Comparison number of steps.
**o obtain its best reported result Montezuma's Revenge 16B (which we compare against), the results table of the work are with 2B.
setting the target policy, or more precisely the sequence of target policies, depends on the sequence of Q-functions that will be generated through the process of approximating Q". To do so, we consider trajectories starting from the state-action couple (I, a) and then following the behaviour policy of the form:
(It, de, Yt, Fe+ 1e
(5)
with (zu, ag) = (a, a). Vt 2 1, p(|[z)), 2 0, = r(æ,, a)) and Vt 2 0,41 ~ P(I a.). The expectation E,, is over all admissible trajectories generated by the behaviour policy μ starting in state æ doing action a and then following the behaviour policy μ.
The general Retrace operator T, that depends μ and æ, is:
TQ(x, Q(x, E,
Σn 120
Cs
(6)
1==1
where the temporal difference 5, is defined as:
8 = + Σ
x(altc=1)((0411.)) Q(xr ar), aE
(7)
and the cutting traces coefficients
C2 min (1, [1a
(8)
p(a, (x,))
Theorem of Munos al. 2016) explains in which conditions the sequence of Q-functions:
Q TRQ
where Ta depends on the policy-couple (pR, Tx) converges to the optimal Q-value Q" In particular one of the conditions that the sequence of target policies ग is greedy or c-greedy with respect to Q2 (more details can be found in Munos et al. (016)).
In practice, at a given time f, we can only consider finite sampled sequences (I., 02. Fay Fo+1 ) starting from (z,, at) and then following the behaviour policy μ. Therefore, we define the finite sampled-Retrace operator as:
a=t
h+k-
TQ a.) Q(1,, +
Σ x-t
II 1-t+1
C₁ 5z-
(10)
In addition, we use two neural networks. One target network Q(x, a; 0-) and an online network Q(x, 0). The target network is used to compute the target value in that the online network will try to fit:
(11)
++--1
QQ(a, 0-)
Σ -- a=t
II i=
rss [.+7
Σ 1((0s,1)) Q(xs as; 0-) aEA
(12)
19

---

Published as a conference paper at ICLR 2020
In the control scenario the policy chosen T(alz) is greedy e-greedy with respect to the online network Q( a; 0). Then, the online network is optimized to minimize the loss:
M a1, 0) (Q o6: 0) 0.)².
(13)
More generally, one can use transformed Retrace operators Pohlee et al.
2018
T")(x, = Bp h (Q(2
Σ e t20
II
Cs
8
(14)
where h E R is real-function and the temporal difference 0 is defined as:
8 r
Σ oEA
- h (Q(r,,))))
(15)
The role of the function h is to reduce (squash) the scale of the action-vall value function to make it easier to approximate for neural network without changing the optimal property of the operator T. In particular, we use the function h:
V2 R. h(2) igg(()(v/l)+++ 1) E2,
(16)
4c(12| + +1+)) -1 -11
E h (2) sign(2)
(17)
2
with 10 10-2
20

---

Published as a conference paper at ICLR 2020
F HYPERPARAMETERS
F.1 SELECTION OF HYPERPARAMETERS
In order to select the hyperparameters used for NGU(N 32) for all 57 Atari games, which are shown on Tab. 6 we ran a grid search with the ranges shown on Tab. 9 We used 3 seeds on the set of 8 Atari games shown in Tab. 3 Regarding the hyperparameters concerning the kemel K (Kernel and the number of neighbors used), we fixed them after determining suitable ranges of the intrinsic reward in our initial experimentation on Atari. After running the grid search with those selected the combination with the highest amount games (out of 8) that held score greater than our human benchmark. As one can see on the multiple mixtures ablations seen on Tab. 3 well as the single mixture ablations on App B the only agent that achieved superhuman performance on the set of 8 games is NGU(N = 32).
hyperparameters.
Finally, in order to obtain the R2D2+RND baseline, ran sweep over the 3 hyperparameter with values 0.1, 0.3, and 0.5, over the 8 games shown in Tab. 3 Coincidentally, like NGU(N = =32), the
best value of /3 was determined to be 0.3.
F.2 COMMON IYMPERSARAMETERS
These are the hyperparameters used in all the experiments. We expose a full list of hyperparameters here for completeness. However, as one can see, the R2D2-related architectural hyperparameters are identical to the original R2D2 hyperparameters. Shown in Tab. 6
Hyperparameter
Value
Number of Seeds
Cross Mixture Ratio
0.0
Number of mixtures N
32
Optimizer
AdamOptimizer (for losses)
Learning rate (R2D2)
0.0001
Learning rate (RND and Action prediction)
0.0005
Adam epsilon
0.0001
Adam betal
0.9
Adam beta2
0.999
Adam clip norm
40
Discount r¹
0.99
Discount r"
0.997
Batch size
6-1
Trace length
80
Replay period
40
Retrace A
0.95
R2D2 reward transformation
sign (x) (v |x||
+ 1
- 1) + 0.001 x
Episodic memory capacity
30000
Embeddings memory mode
Ring buffer
Intrinsic reward scale
0.3
Kernel c
0.0001
Kernel num. neighbors used
10
Kernel cluster distance E
0.008
Kernel pseudo-counts constant e
0.001
Kernel maximum similarity 8m
Replay priority exponent
0.9
Replay capacity
5e6
Minimum sequences to start replay
6250
Actor update period
100
Target Q-network update period
1500
Embeddings larget update period
once/episode
Action prediction network L2 weight
0.00001
RND clipping factor L
Evaluation
0.01
Target e
0.01
Table 6: Common hyperparameters.
21

---

Published as a conference paper at ICLR 2020
F.3 DISCO MAZE HYPERPARAMETERS
Hyperparameters are shown in Tab.
Hyperparameter
Value
Episodic memory capacity
5000
Learning rate (R2D2 and Action prediction)
0.001
Replay capacity
le6
Intrinsic reward scale 8
0.5
Trace length
50
Replay period
50
Retrace À
0.97
Retrace loss transformation
identity
Num. action repeats
Target Q-network update period
100
Q-network filter sizes
(3, 3)
Q-network filter strides
(1,
Q-newwork num. filters
(16, 32)
Action prediction network filter sizes
(3,3)
Action prediction network filter strides
(1,1)
Action prediction network num. filters
(16, 32)
Kernel
0.01
Evaluation
0
Table 7: Disco Maze hyperparameters.
F.4
ATARI PRE-PROCESSING HYPERPARAMETERS
Hyperparameters are shown Tab,
Hyperparameter
Value
Max episode length
30 min
Num. action repeats
4
Num, stacked frames
Zero discount on life loss
false
Random noops range
30
Sticky actions
false
Frames max pooled
3 and 4
Grayscaled/RGB
Grayscaled
Action set
Full
Table 8: Atari pre-procceee pro-esocgs hyperparameters.
F.5 HYPERPARAMETER RANGES
On Tab. g we can see the ranges used to sweep over in our experiments.
Hyperparameter
Value
Intrinsic reward scale 3
{0.2, 0.3, 0.5)
Number of mixtures N
[1, 2, 8, 16, 32)
Cross Mixture Ratio # Episodes w/o wiping Episodic Memory
{0.0, 0.25, 0.5
{1, 3}
Table 9: Range of hyperparameters sweeps.
22

---

Published as a conference paper at ICLR 2020
G DETAILED ATARI RESULTS
Jmn
2000
2000
2000
1000
2000
Exik
Figure 14: R2D2(eetrrce)) (green), NGU(N=32) with eval 3 = 0.0 (blue) and eval B = 0.3 (orange).
23

---

Published as a conference paper at ICLR 2020
Game
Retracet
NGU(32) eval beta=0.0
NGU(32) evall beta=0.3
alien
189.1k=1566k
248.1k-22.44k
225.5k+36.96
asteroids
338.5k+4.5kk
230.5k=t4.0k
181 18..6kk2..kk
time pilot tutankham
44698k=33.9k
344.7k=31.0k
336.1 322
452.2.120.0
191.111.22
125.7.5.2
up n down
678.8k11..34
620.1k 13.7k
575.2k
venture
2.0k
1.7k
779.91188.77
video pinball
948 1.8.66=t5.22 2k
965.3k=12.8k
596.7k=
wizard of wor
120.2k=7.6k
106.2k=7.0k
85.1k+12.3K
atlantis
165
1653.6k+t2.3k
1638.00 4k.66
yars revenge
990.4k
98.20k-3..2k
993.8k-
zaxxon
94.8k-t-33.7k
111.1k=11.8
190.1k-6.9k
bank heist
15.0k-t5.7k
17.4k 12.00k
1.4k-t-0.0k
battle
433.Ik=15.22k
691.7k=22.6k
571.5k:145..4
beam rider
103.9k11.Ik
63.6k=8.6k
31.9k=10.66
berzerk
69.8k-5.8kk
36.2k
27.3k
bowling
253.0+1122
211.9=8.4
161.8
boxing
100.0=:0.0
99.7=0.0
3.8+1.44
breakout
839.7=16.0
559.2=29.0
387.6+51.0
centipede
700.2k111..8 19.8k
577.8K113.IK
574.6k
chopper command
0.0k
10.0k
974.1k
amidar
2.22k
17.8k
8.5k-10.4k
crazy climber
294.2k:122577
31.74k
357.0k
defender
675.6k13.2kk
664. 1.KK
6.6.3k=7.2k
demon attack
1.0.
143.5k=000k
136.6k=3.3k
double dunk
24.0=1.00
-14.1=2.4
-2.75
enduro
2.4k-t0.0k
2.0k+O0.1k
682.5++24.0
fishing derby
86.8+00.9
32.0=1.9
-29.3+4.11
freeway
33.2++0.1
28.5-1.1
21.2+00.5
frostbite
10.5k
206.4k1150.00
67.9k
gopher
117.8k
10.64
86.6k 4k
gravitar
12.9k-10.6k
1.52k
13.2k-LO.3k
assault
36.7k=3..0k
34.8k=5.4k
1.9k
hero
54.5k=3.0k
69.4k-5.7k
64.2k+7.0k
ice hockey
0..1
-4.1
-0,5+0022
jamesbond
30.8k 2.33k
2..6k
22.4k-L0.33
kangaroo
14.7k:1.0.1k
35.1k=2.1k
16.9k-t2.00k
krull
131.1k::2..7k
127.4k
2..2k
kung fu master
220.7k:1:.9k
212.1K=11.2k
203.2k
montezuma revenge
2.3k:00.4k
10.4k=1.5k
16.8
pacman
40.3k=1..1k
40.8k=1.1k
38. 1k
this game
7..3k
23.9k=0.5k
15.6k-t0.3k
phoenix
935.2k-13.554
959.1k-2.7k
933.3k=t477k
asterix
99.93k-t0.9k
23.07k-23.1k
953. 953.1k+221.7k
pitfall
-.72
7.8k
1.3k
pong
20.9
19.6-0.2
-9.711.44
private eye
3..4k
100.0k-10.4k
65.6k
qbert
496.6k=46.44k
451.9k=82.1K
149.0k=+108.22
riverraid
38. 18.99
36.7k=2.3k
42.6k=4.0k
road runner
105. 105.2k=16..3 8k
128.6k=28.7k
103.9k=7.1k
robotank
142.4:10.8
9.1--0.7
24.9+
seaquest
1000.0k+t0.0k
1000.0k-L0.0K
10.0.0k+0..0k
skiing
-1 -10081.7+97..
-22977.9 -2079.9-5059.9
21907.4436477
solaris
5.6k:i..Ik
1..33
1.3
space invaders
33.4k=112.2k
43.4k=1.3k
12.0k .9k
star gunner
4k
614.6k=66.88.
452.5k
surround
9.8
-9.6-0.2
-7.3+0.4
tennis
2..0
10.2=3.5
-3.5+5.7
Table 10: Scores over all 57 Atari games.
24

---

Published as a conference paper at ICLR 2020
H NETWORK ARCHITECTURES
H.1 ARCHITECTURE OF THE EMBEDDING NETWORK WITH INVERSE DYNAMICS PREDICTION
plaelai, H(f()))
Comone
f(x))
(am41)
BBV
San AOAND Pramnn
F6+1
Figure 15: Embedding Network Architecture.
H.2 ARCHITECTURE OF THE RANDOM NETWORK DISTILLATION
g(x))
g(11; 0)
Folly Conteced Llrbs
Cerneded
HELU
Stide Charadu 84)
Steae Charretiudd)
RELU
ABU
Conn /Kemettol Eittle Chernehi
Cany Hemersot Smoeece Coamrch-H
RELU
TEU
Chemmetu33
Crasrebri21
FE
Figure 16: RND Network Architecture.
25

---

Published as a conference paper at ICLR 2020
Q+
RL Head
LSTM Core
Convolutional
at
2 r
rt-
B
Lt
(a) Sketch of the R2D2 Agent
(b) Detailed R2D2 Agent
Figure 17: R2D2 Agent Architecture.
H.3 ARCHITECTURE OF THE R2D2 AGENT
I CONTROLLABLE STATES
In this section we evaluate properties of the learned controllable states. We further present study of the performance of the algorithm when having access to oracle controllable states containing only the necessary information. We use Montezuma's Revenge case-study.
1.1 INSPECTING THE PROPERTIES LEARNED CONTROLLABLE STATES
As explained in Section 2 we train the embedding network f using inverse dynamics model as done by Pathak et al. 2017). Intuitively, the controllable states should contain the information relevant to the action performed by the agent given two consecutive observations. However it might contain other type of information as long as it can be easily ignored by our simple classifier, g.
As noted in Burda et al. 2018b), for this game, one can identify novel state by using five pieces of information: the (ær, y) position of the player, a room identifier, the level number, and the number of keys held. This information can be easily extracted from the RAM state of the game described in Section I.3 bellow. One question that we could ask is whether this information is present (or easily decodable) not in the learned controllable state. We attempted to answer this question by training linear classifier to predict the (æ,, y) coordinates and the room identified from the learned controllable state. Importantly we do backpropagate the errors to the embedding network f. Figure 19 shows the average results over the episodes as the training of the agent progresses. We can see that the squared error predicting the (ar, y) position of the agent stabilises to more or less constant value, which suggests that it can successfully generalise to new rooms (we do not observe an increase in the error when new rooms are discovered). The magnitude of the error of the order of 12 units, which less than 10% of the range (see Section I.3). This is to be expected, it is the most important information for predicting which action was taken. It shows that the information is quite accessible and probably has significant influence in the proposed novelty measure. The room identifier. on the other hand, is information that is not necesary to predict the action taken by the agent. Unlike the jumps in the error training progresses the problem becomes harder.
previous
26

---

Published as a conference paper at ICLR 2020
Predictabliity Position In Mocteruma's Revenge
3000
200
300000
1000000
1000000
200000 250000 SOCODDO 200DO00
Learner Updates
Pradictabiliy
Montenume's Revenge
Chosttaatte CrTOr
0.2
0.1
1000000
1500000
2500000
Updates
Figure 18: Prediction loss from learned controllable states of the position (top) and room (bottom) on Montezuma's 's Revenge against minibatch updates.
It stabilises around an error slightly above 20%, which is reasonably good considering that random chance is 96%. This means that even if there is nothing specifically encouraging this information to be there, it is still present and in turn influence the proposed novelty signal.
An avenue of future work is to research alternative methods for learning controllable states that directly search for retaining all relevant information. While very good results can be obtained with one of the simple alternative an inverse dynamics model, it is reasonable to think that better results could be attained when using better crafted one. To inform this question, we investigate in the next section what results could we obtain if we explicitly use as controllable states the quantities that we were trying to predict in this section.
1.2 MONTEZUMA'S 'S REVENGE WITH HAND-CRAFTED CONTROLLABLE STATES
In the previous section we analysed the properties of the learned controllable states. A valid question to ask is: how would the NGU work if we had access to an oracle controllable state containing only the relevant information? This analysis is a form of upper bound performance for given agent architecture. We ran the NGU(N=1) model with two ablations: without RND and without extrinsic rewards. Instead of resetting the memory after every episode, we do it after small number of consecutive episodes, which we call a meta-episode. This structure plays an important role when the agent faces irreversible choices. In this setting. approaches using non-episodic exploration bonuses even more susceptible to suffer from the "detachment" problem described in Ecoffet et al. (2019). The agent might switch between alternatives without having exhausted all learning opportunities, rendering choosing the initial option uninteresting from novelty perspective. The episodic approach with meta-episode of length one would be forced to make similar choices. However, when run with multiple episodes it can offer interesting alternative. In the first episode, the agent starts with an empty episodic memory can can choose arbitrarily one of the options. In the second episode, the episodic memory contains all the experience collected in the first episode. The agent is then rewarded for not repeating the strategy followed in the first one, as revisiting those states will lead to lower intrinsic reward. Thus, the agent encourage to learn diverse behaviour across episodes without needing to choose between alternatives nor being susceptible to the detachment problem. Results are summarized in Fig. 19 We report the average episodic return (left) as well as the average number of visited rooms per meta-episode (right). The model achieves higher scores than the one using learned controllable states (as reported in Section
Incorporating long-term novelty in the exploration bonus, encourages the agent to concentrate in the less explored areas the environment. Similarly to what we observed with learned controllable states, this provides boost both in data efficiency as well as final performance, obtaining close to 15,000 average return and visiting an average of 25 rooms per episode. In this run, three out five seeds reach the second level of the game, one of which reaches the third level with average of fifty different rooms per episode. We also observe that, when running in the absence of extrinsic rewards, the agent remarkably still achieves very high extrinsic reward. Secondly, the agent is able
27

---

Published as a conference paper at ICLR 2020
40000
Without RND
Without ItS
35000
Moan episodo returns
30000
RNI With
Mean visited rooms
With RND
25
25000
20
20000
15-
15000
10-
10000
5000
5B
10B
15B
20B
258
30B
5B
10B
15B
208
25B
30B
Number of frames
Number of frames
Figure 19: Mean episodic return (left) and mean number of visited rooms per episode (right) vs environment frames for agents trained Montezuma's Revenge with hand-crafted controllable states,
to consistently reach a large number of rooms and explore more than rooms without any extrinsic guidance.
As noted in Burda et al. (2018b), Montezuma's Revenge each level contains doors and keys. If the agent walks through door holding a key, it receives reward of 300 consuming the key in the process. In order to clear a level, the agent needs open two doors located just before the final room. During exploration, the agent needs to hold on to two keys to what it could do with them later in the episode, sacrificing the immediate reward of opening more accessible doors. Any agent that acts almost greedily will struggle with what looks like high level choice. With the right representation and using meta-episodes, our method can handle this problem in an interesting way. When the number of keys held is represented in the controllable state, the agent chooses different key-door combination on each of the three episodes in which we do not wipe our episodic memory. At the end of training. in the first episode after wiping the episodic memory, our agent shows a score of 14, 660 + 196, while the third episode the agent shows a score of 34, 040 + 9, 835, exploring on average over 30 rooms and consistently going to the second leve The agent learns complex exploratory policy spanning several episodes that can handle irreversible choices and overcome "distractor" rewards. We do not observe different key-door combinations across episodes when using learned controllable states. Presumably the signal of the number of held keys in the learned controllable states is not strong enough to treat them as sufficiently different.
The results describe in this section support the idea that significant gains can be obtained by im- proving the respresentation of the controllable states, suggesting that the study of learning better representations an interesting line for future work. Recent works have explored ways of measuring novelty by learning controllable aspects of an environment (Kim et al. 2018 Warde-Farley et al. 2018), and we believe that some of these ideas could be also useful in this setting.
1.3 HAND-CRAFTED STATE FEATURES FOR MONTEZUMA'S REVENGE
We obtain the hand-crafted features for Montezuma's Revenge by observing the RAM state of the game every time step. More concretely:
x and y can be observed at positions OxAA and OxAB respectively, represented by integers with range of [0, 153] x [0, 122].
Room id and level number can be found in positions 0x83 and 0xB9 respectively. We provide this information as single integer to our agent the form of rid + 24 L, where Tia E {0, ... 23} is the room id, and I, is the level number.
Byte 0xC1 is the player's inventory. We count the number of keys being held (and provide this information the agent) by adding the bits {2...., 6). which correspond the binary slots for keys.
See video of the three episodes
28


Reviews:
[{"review_id": "rkgUCLxTKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work is motivated by the goal of having a comprehensive exploration of an agent in deep RL. For achieving that, the authors propose a count-based NGU agent, combining intrinsic and extrinsic bonuses as new rewards. An extrinsic/ long-term novelty module is used to control the amount of exploration across episodes, a life-long curiosity factor as its output. In the intrinsic/episodic novelty module, an embedding net and a KNN on episodic memory are applied to compute the current episodic reward. In the experiment, a universal value function approximator (UVFA) framework is used to simultaneously approximate the optimal value function with a set of rewards. The proposed method is tested on several hard exploration games. Other recent count-based models are compared in the paper.\n\nCons:\n- To my acknowledge, the task and the count-based methods are not too novel. \n- They use 35 billion environment frames.\n\nOverall, this paper is well-written. Methods and results are clearly described.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlUtgf2Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a novel intrinsic reward/curiosity metric that combines both episodic and “life-long” novelty. Essentially two competing pressures that push agents to explore as many novel states in a single rollout as possible and to explore as many states as possible as evenly as possible. The primary contribution here is the episodic novelty measure, which relies on a state embedding that takes into account stochasticity in the environment. The paper covers this episodic curiosity measure and how it’s integrated with the life-long curiosity metric. It then demonstrates the impact of these metrics and variations compared to baselines on particular games and all 57 Arcade Learning Environment games.\n\nThis is a clear accept. This paper demonstrates a novel episodic curiosity metric and a means of integrating that with a more standard life-long curiosity metric. The writing is clear and the results are good and well-explained. \n\nI would appreciate in the final paper some discussion of whether it would be possible to adjust the hyper-parameters of the approach during training, given that different variations of the approach seemed to do consistently better or worse as the authors described. Further, I would have appreciated a summarization of the limitations towards the end of the paper. \n\nI recognize that the life-long curiosity approach is fairly arbitrary, but given that the controllable state is already available, I’m not sure why it isn’t used for this measure. It seems naively it would be helpful. If not, some clarity on this would be appreciated.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1lEldIhtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-after rebuttal:\nI read the replies from the authors and re-read the modified version of the paper and I believe there has been a noticeable improvement in the presentation. I still think it could be improved more (in terms of wording and better exposition of the results) but due to the in-place improvements I increase my score to weak accept. \n----------------------------------------------------------------------------------------------------------------------------------------------------\nIn this paper, the authors present a methodology for generating intrinsic rewards for reinforcement learning agents targeting hard exploration environments. The intrinsic reward is generated using an episodic memory module and a lifelong novelty module.  A state representation is learnt in such a way that the novelty signals are biased towards what the agent can control. A single neural network learns the q-values of exploratory policies with different degrees of exploration. Several experiments on a simple domain and on Atari domains are conducted to evaluate and compare the performance of the proposed method against the baselines. \n\n\nIn my opinion, this is an interesting idea as it present a novel combination of methods (Random Network Distillation and Episodic Memory) that works and can inspire other researchers in the field.  However, I would like to see clearer explanations in the experimental section before acceptance. For this reason I rate this paper as a weak reject but if clarity is improved I will increase my score.  See below for more general comments and detailed explanation about the experimental section.\n\nGeneral comments:\n\n- The authors state that a novel contribution is to disentangle exploration and exploitation. This is not true: see [1] for a recent paper on the topic. I believe the authors should cite this paper.\n\n- In page 3: “To determine the bonus, the current observation is compared to the content of the episodic memory. Larger differences produce larger episodic intrinsic rewards” When computing the intrinsic reward for a new state, it must be compared to the episodic memory, which is composed by recent states (and old). Therefore, in this situation the intrinsic reward is always high? Specially because it is compared with the k-nearest neighbours?  Maybe the authors could elaborate on this?\n\n\n\nExperiment Section:\n\nThis section should be tidied up in my view.  In general, I feel that there are too many fine-grained results / experiments. I think some aggregation of results would be good for clarity. Without this aggregation there are statements made from the authors that are difficult to believe, e.g. a general result statement is valid for one or two games but not for the rest (but still the statement is formulated in a general way). This can lead to misunderstandings and overstatements.  This together with lack of some experimental details makes the section very dense and difficult to parse. Below I make my points. They are in order of appearance in the main manuscript. I marked with (*) the ones I consider the most important. \n\nSection 4.1:\n\n- Why the exploration policy in this section is set to have $\\beta = 0.3$ ? Is my understanding correct that any value of $\\beta$ would produce similar results since this is just a scaling of the intrinsic reward (i.e. it does not balance exploration vs exploitation)?\n\n- The parameter $\\beta$ appears in the construction of the reward r = r^e + \\beta r^i , but also the output of Algorithm 1 scales the similarity by $\\beta$ does that mean that the final contribution of $\\beta$ is squared? Is this intended? If so, why?\n\n- At the end of this section: “However, staying still is enough: staying still every state will produce ….” Since the agent can only take 4 action {left, right, up, down}, what do the authors mean by “staying still”, is really the agent doing some sort of cyclic policy e.g. left right left right … ?\n\nSection 4.2:\n\n- In the appendix A it is stated “use last 5 frames of the sampled sequences to train the action prediction network… “ Does this refer to frame-stacking? I assume it is not since at the beginning section 4.2 it is stated that there is no frame-stacking. If it is not frame-stacking, the authors could explain in more detail what do they refer to.\n\n- In the paragraph “Architecture” it is stated that 8 games were selected to choose the hyperparemeters and that the results are in Appendix B. However, appendix B only shows 2 games (Pitfall and Montezuma’s Revenge). Is this a typo?\n\n- (*) In paragraph “NGU Agent”: This is the most dense paragraph and the most difficult to parse. First of all Table 1 shows all the results, but as one can see, the different ablations have very similar performance on most games with only a few exceptions. Note that most of the mean performances with error bars, have actually overlapping error bars for many combinations of games and methods. Therefore, further statements about this table are difficult to believe since they could have been just the result of random seeds. I think it is fine to show these fine-grained results on the appendix, but I would say it would be better to aggregate them in the main paper and show that the statements made by the authors still hold for this aggregation.\n\nSpecific comments about NGU agent paragraph:\n\n- “ we observe an improvement from increasing the number of mixtures (with diminishing returns) on hard exploration games.” I would say the authors cannot claim this since the hard exploration games are the ones in table 2, which are different from the ones in table 1 (only Pitfall, MR and Private Eye coincide). Also the statement is only true for 2 the three that are hard exploration games (Pitfall and Private Eye).\n\n- (*)  “for smaller $\\beta$ we observe better performance on Pong and Beam Rider, but worse performance on all hard exploration games” This is a strange result in my opinion. If I understood correctly, the base agent has $\\beta = 0.3$, which supposedly has been selected to be good on hard-exploration games. However, here only changing $\\beta$ slightly, reduces the performance on hard-exploration games (Pitfall and Private Eye) significantly. Is this due to the parameter being very sensitive? If so, I believe the authors should report how sensitive are the results to this parameter, specially, on the full hard-exploration games.\n\n- “superhuman performance on 3 games”: which ones?\n\nComments on paragraph on “hard exploration games”: \n- “with NGU(N=1)-RND ….” what do the authors mean by this? This seems to be the best setting for Pitfall but it is actually not using mixture of explorations and (I guess) neither RND?\n- Table 2 first row “best base” what does this mean?\n\n\nMinor Comments:\n\n-In Equation 3 the squared distance is normalized by a running average. Why?\n\n- Right after Equation 3: “… episodic reward can be found in Alg. 14” . Probably meant Alg 1.\n\n- Similarly why the errors are normalized by a running average when computing \\alpha_t ?\n\n\n[1] MULEX: Disentangling Exploitation from Exploration in Deep RL ( Lucas Beyer et al )\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles hard-exploration RL problems. The idea is to learn separate exploration and exploitation strategies using the same network (representation). The exploration is driven by intrinsic rewards, which are generated using an episodic memory and a lifelong novelty modules. Several experiments (simple and Atari domains) show that the proposed approach compares favourably with the baselines.

The work is novel both in terms of the episodic curiosity metric and its integration with the life-long curiosity metric, and the results are convincing. All reviewers being positive about this paper, I therefore recommend acceptance.
Decision: Accept (Poster)