NovelD: A Simple yet Effective Exploration Criterion
Authors: Tianjun Zhang
Huazhe Xu
Xiaolong Wang
Yi Wu
Kurt Keutzer
Joseph E. Gonzalez
Yuandong Tian
Venue: NeurIPS 2021 Poster (2021)
Keywords: RL
Exploration

Abstract: Efficient exploration under sparse rewards remains a key challenge in deep reinforcement learning. Previous exploration methods (e.g., RND) have achieved strong results in multiple hard tasks. However, if there are multiple novel areas to explore, these methods often focus quickly on one without sufficiently trying others (like a depth-wise first search manner). In some scenarios (e.g., four corridor environment in Sec 4.2), we observe they explore in one corridor for long and fail to cover all the states. On the other hand, in theoretical RL, with optimistic initialization and the inverse square root of visitation count as a bonus, it won't suffer from this and explores different novel regions alternatively (like a breadth-first search manner). In this paper, inspired by this, we propose a simple but effective criterion called NovelD by weighting every novel area approximately equally. Our algorithm is very simple but yet shows comparable performance or even outperforms multiple SOTA exploration methods in many hard exploration tasks. Specifically, NovelD solves all the static procedurally-generated tasks in Mini-Grid with just 120M environment steps, without any curriculum learning. In comparison, the previous SOTA only solves 50% of them. NovelD also achieves SOTA on multiple tasks in NetHack, a rogue-like game that contains more challenging procedurally-generated environments. In multiple Atari games (e.g., MonteZuma's Revenge, Venture, Gravitar), NovelD outperforms RND. We analyze NovelD thoroughly in MiniGrid and found that empirically it helps the agent explore the environment more uniformly with a focus on exploring beyond the boundary.  

NovelD: A Simple yet Effective Exploration Criterion
Tianjun Zhang'
Huazhe Xu'
Xiaolong Wang?
Yi Wu
Kurt Keutzer'
Joseph E. Gonzalez'
Yuandong Tian*
University of California, Berkeley
Unveristy of California, San Diego
Tsinghua University
Facebook Al Research
Shanghai Qi Zhi Institue
Abstract
Efficient exploration under sparse rewards remains key challenge in deep inforcement learning. Previous exploration methods (e.g., RND) have achieved strong results in multiple hard tasks. However, if there multiple novel areas explore, these methods often focus quickly on one without sufficiently trying others (like depth-wise first search manner). In some scenarios (e.g., four corridor envi- ronment in Sec. 4.2 we observe they explore in one corridor for long and fail to cover all the states. On the other hand, in theoretical RL, with optimistic initializa- tion and the inverse square root of visitation count as a bonus, it won't 't suffer from this and explores different novel regions alternatively (like a breadth-firs search manner). In this paper, inspired by this, we propose a simple but effective criterion called NovelD by weighting every novel area approximately equally. Our algorithm is very simple but yet shows comparable performance even outperforms multiple SOTA exploration methods many hard exploration tasks. Specifically, NovelD solves all the static procedurally-generaae environment steps, without any curriculum learning. In comparison, the previous SOTA only solves 50% of them. NovelD also achieves SOTA on multiple tasks in NetHack, rogue-like game that contains more challenging procedurally- gelerrteg environments. In multiple Atari games (e.g., MonteZuma'ss 's Revenge, Venture, Gravitar), NovelD outperforms RND. We analyze NovelD thoroughly Mini- Grid and found that empirically it helps the agent explore the environment more uniformly with a focus on exploring beyond the boundary.
tasks in Mini-Grid with just 120M
Introduction
Deep reinforcement learning (RL) has experienced significant progress over the last several years, with an impressive performance in games like Atari 41 StarCraft [61] Go and Chess (57-59). However, its success often requires massive computational resources or manually designed dense rewards. The dense rewards are often impractical for real-world settings as they require significant amount of task- ssecifpc domain knowledge.
An alternative approach is to allow the agent to explore the environment freely until reaches the goal. While basic RL. exploration criteria (e.g., e-greedy) quite simple, it fails to explore sufficiently in hard tasks. Modern works adopt various Intrinsic Reward (IR) designs to guide exploration in hard-exploration settings. However, observe (Sec. 4.2b in experiments if there multiple
'Correspondence to: Tianjun Zhang haanjjunnn@ebereeee..ddd....... Our code is available at htttp://githu/: com/ com/tian htmm/tianjuu//NoveeDD
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

High
RND
Relative
AND assign high throughout the envionment
2. AND temporariy focuses uppar right
AND by chance explores bottom right corner and forgets it already explored upper rignt
AND re-eaplores the upper right bottom right, gets trapped
Low IN
F LEAS
T
High IR
NovelD
Relative High IR
NovelD assigns high near the start and low IR for the rest
pushes every direction to the frontier of exploration uniformly
NovelD continuuusly pushes the exploration frontier
NovelD reaches of exploratiio
Low
Figure 1: hypothetical demonstration of how exploration is done in NovelD versus Random Network Distillation (RND) (IT), terms distribution of intrinsic reward (IR). NovelD reaches goal by continuously pushing the frontier of exploration while RND gets trapped in the explored regions. Note that IR is defined differently in RND versus NovelD (See Eqn. 2 and different colors are used to represent IR of RND and NovelD.
regions of interest, these methods sometimes quickly are trapped one area without sufficiently exploring others. This results in poor overall exploration of large state space [2] This is also known as detachment problem in Go-Explore [17]
On the other hand, provably optimal theoretical RL equipped with optimistic initialization and visitation count bonus explores the environment much more uniformly [I]. Inspired by that, we introduce a very simple but effective exploration criterion by weighting each novel area approximate equally. Our algorithm uses regulated Novelty Difference (NovelD) consecutive states trajectory. The novelty of a state is calculated by Random Network Distillation (RND (II). The underlying intuition is that this criterion provides a large intrinsic reward at the boundary between the explored and the unexplored regions (Fig. Ib. As result, it induces very different exploration and yields a much broader coverage
pattern comparing to count-based approaches
the state space.
We evaluate NovelD on three very challenging exploration environments: MiniGrid [K] NetHack [E]] and Atari games (9] MiniGrid is a popular benchmark for evaluating exploration algorithms
[52 2 2 NetHack, built from a real game, is a much more realistic, PG-generated
environment with complex goals and skills. Atari games is a widely used benchmark for RL algo- [8 NovelD manages to solve all the static environments
rithms 40 I
MiniGrid within 120M
environment steps, without curriculum learning. In contrast, previous SOTA AMIGo [1]] solves 50% of the tasks, categorized as "easy" and "medium", by training a separate goal- goal-generating teacher network in 500M steps. In NetHack, NovelD also outperforms all baselines with a significant margin on various tasks. Novell) is also tested in various Atari games (e.g.. MonteZuumass 's Revenge, Venture), using image-based input and outperforms RND for both CNN and RNN-based networks.
Compared to previous works (e.g., RIDE (2). AMIGo
and Go-Explore 17) ) NovelD has
few design advantages: (1) in NovelD, there is almost no hyperparameters: (2) NovelD is one-stage approach and can be readily combined with any policy learning methods (e.g., PPO), while many approaches (e.g., RIDE, Go-Explore) are two-stage approaches. (3) NovelD is asymptotic consistent: its IR vanishes after sufficient exploration, while approaches like RIDE and AMIGo do not. During experiments, we observe that compared to the count-bascd approach and RND, NovelD prioritizes the unexplored boundary states, yielding much more efficient and broader exploration patterns.
2 Background
In Markov Decision Process (MDP), we define state space S, action space A, and (non-deterministic) transition function T x A - P(S) where P(S) is the probability of next state given the current
state and action. The goal is to maximize the expected reward R E E is the reward and y is the discount factor. In this paper, the total reward received at time step / is given by r; = rf + arf, where rf the extrinsic reward given by the environment, of the intrinsic reward from the exploration criterion, and is scaling hyperparameter.
*=+++ *
where r

---

Trajectory
Novelty(s:)
Novelty(st)
m
2
10101010
Explored region Novelty(s) & m
Trajectory
Trajectory A
Trajectory
Figure The mechanism of NovelD. Two trajectories, A and В. Trajectory A is within the "explored region" defined as the subset of states with (o)elt S m for some constant m and tends to have high accumulated novelty, while Trajectory B explores out of explored regions. RND assigns comparable IR on A ((1 + 5/2)m 3.5m) and B ((1 4/10 + 2)m 3.4m), while NovelD assigns much higher IR B ((2 - 1/10)m 1.9m) than A (0), Moreover, this effect becomes more prominent for longer trajectories. The value a in Eq. is design choice and we use a here for showing an intuitive example.
3 Exploration via Novelty Difference
3.1 NovelD Intrinsic Reward Criterion
NovelD is a meta-criterion that can be applied on top of any novelty measure novelty(s) that tells how familiar state is for the agent. Formally, along a trajectory, we give agent IR if the previous state Sy has been sufficiently explored but St+1 is not:
(s ay St+1) max (novelty(s+41) - novelty(s:).
(1)
Here a is a scaling factor. Intuitively, if we define {s novelty(s) S m) to be an explored region, then NovelD) gives intrinsic reward (IR) to the agent when it explores beyond the boundary of explored regions. Note that IR is clipped to avoid negative IR if the agent transits back from a novel state to familiar state. From the equation, only crossing the frontier matters to the intrinsic reward; if both S and S, are novel or familiar, their difference would be small. For each trajectory going towards the frontier/boundary, NovelD assigns an approximately equal IR, regardless of the length (see Sec. 3.2) Like RIDE [52), in our actual implementation, partial observation O, are used instead of the true state St, when Sy not available.
Episodic Restriction on Intrinsic Reward (ERIR). Simply using Eqn. to guide exploration can result in the agent going back and forth between novel states 1 and their previous states s,. RIDE [52] avoids this by scaling the intrinsic reward (s) by the inverse of the episodic state visitation counts. NovelD puts more aggressive restriction: the agent is only rewarded when it visits the state s for the first time in an episode. Thus, the intrinsic reward of NovelD becomes:
(st, ag, S1+1) max inovelt((s-7)
novelty 0) ((NN())+11 =
(2)
Ne here stands for episodic state count and is reset every episode. In contrast, the novelty measure novelty(-) is life-long counter throughout training.
Novelty Measure using Random Network Distillation. How accurate measure the novelty of state s in large-scale stochastic environments remains an open problem [d. Similar to RND [ we the difference hetween random fixed target network and trainable predictor network & as a novelty measure: novelty(s.) novelty w) == ((o(s)) - K'u (s:))la,
Once the novelty score for state s; is computed, we minimize novelty (s;; w) with respect to wr and perform a one-step weight update for w, which is the parameter of the predictor network & Therefore, when s; visited again, the quantity nsvelty(s;; w)) will be lower, showing that the state has been seen in the past.
3.2 Conceptual Advantages of NovelD over Existing Criteria
We show the distinct preference exploration directions between RND and NovelD. We also see that NovelD is a consistent algorithm, the intrinsic reward converges to zero after sufficient exploration.
Explore via Novelty Difference. Fig. shows the conceptual comparison between NovelD (Eq. 2 and exploration with novelty measure alone (e.g., RND). We could clearly see their distinctive preferences: our criterion tends to reward more the trajectories that move out the explored regions (Trajectory B), which typically show a profile of stable novelty measure until a sudden boost when it ventures into an unknown region. On the other hand, count-based approaches can trapped within explored regions where the trajectories have low but consistent novelty rewards (Trajectory A).

---

MRNS
MBNOS-
MIN12-
MCS3R3
ICS4R3
KCSSRI
ICSSOO
DI220-
DM2DK
DMBR
OMDO
OMPULL
NeyContoo
Figure 3: MiniGrid Environments. Left: procedurally eereedurlly--geeeratedd OMPull environment. Right: NovelD solves challenging tasks which previous approaches cannot solve. Note that evaluate methods for 120M steps. AMIGo gets better results when trained 500M steps as shown in 12 but still not as good as results obtained by NovelD in 120M steps.
Asymptotic Inconsistency. Approaches that define IR as the difference between state representations suffer from asymptotic inconsistency. In other words, their IR does not vanish even after sufficient exploration: r' A 0 when N + oo. This is because when the embedding network converges after sufficient exploration, the agent can always obtain non-zero IR if significant change occurs in state representation (e.g., opening a door or picking up a key MiniGrid). Therefore, the learned policy does not maximize the extrinsic reward r deviating from the goal of RL. Automatic curriculum approaches [12 have similar issues due to an ever-present IR. In contrast, our Eq. 4 is asymptotically consistent as 0 when co.
(t) a learned embedding network) 63 38
Experiments
We evaluate NovelD on challenging procedurally-generaae environment MiniGrid [3] several hard-exploration scenarios in Atari games, and NetHack [<]] with sparse rewards (i.c., get reward only when reaching the final goal). For all the experiments and all exploration approaches (including NovelD), we use PPO [5 as the base RL algorithm and add intrinsic reward specified by various methods, to encourage exploration.
In MiniGrid, we compare NovelD with RND ITI, ICM 49 RIDE 5 and AMIGo [2].
We only
evaluate AMIGo for 120M steps in our experiments. The algorithm obtains better results when trained for 500M steps as shown in [12] For all other baselines, we follow the same training paradigm from
22
Mean and standard deviation across four runs of different seeds are computed.
NovelD solves all the static tasks provided by MiniGrid. In contrast, all the baselines end up with zero rewards on half of the tasks tested. In NetHack, NovelD achieves SOTA with large margin over baselines (IMPALA 19 without exploration bonus and RND).
4.1 MiniGrid Environments
We mainly three challenging environments from MiniGird: Multi-Roon (MR), Key Corridor (KC) and Obstructed Maze (OM). We use these abbreviations for the rest of the paper (e.g., OM2D1h stands for ObstructedMaaze2Dllh) Fig. shows example of rendering OMFull well as all the environments we tested with their relative difficulty.
In MiniGrid, all environments are of size K x K (K is environment-speene -spenenntssseiicc where each tile contains an object: wall, door, key, ball, chest, etc. The action space defined as turn left, turn right, move forward, pick up object, drop object, and toggle an object (e.g., open close door). MR consists of series of rooms connected by doors and the agent must open door to get to the next room. Success is achieved when the agent reaches the goal. In KC, the agent has to explore the environment to find the key and open the door along the way to achieve success. OM is the hardest: the doors are locked, the keys are hidden in boxes, and doors obstructed by balls.
Results. NovelD manages solve all the static environments MiniGrid. In contrast, all baselines solve only up to medium-level tasks and fail to make any progress on more difficult ones. Note that some medium-level tasks we define here are categorized as hard tasks RIDE and AMIGo (e.g.. KCS4R3 is labeled as "KCHard" and KCS5R3 is labeled as "KCHarder" in their works). Fig. H shows the results of our experiments. Half of the environments (e.g., KCS6R3, QM1Q) are extremely hard and all the baselines fail. In contrast, NovelD easily solves all listed above without any curriculum learning. We also provide the testing performance NovelD and all baselines in Tab. The results averaged across four seeds and 32 random initialized environments.

---

RND
AMEO
EoyCornda
Aherage betumm
Aograge Retium
0.75
0.75
0.73
0.75
0.50
5.20
0.00
0.25
6.50
6.75
3.00
0.00
0.25
0.50
0.25
1.0
0.0
1.0
1.5
2.0
NeyComkdursaas"
KeGaaddarssad
Aleence becom
Nouage Notum
0.75
0.75
0.73
0.75
0.50
0.30
0.50
5.30
6.0
1.9
1.5
2.6
0.0
0.5
1.0
15
200
Awerze betum
Aouaay Room
0.75
0.72
0.75
0.75
0.50
Awcryy
0.50
5.30
0.0
0.5
Figure 4: Results for various hard exploration environments from MiniGrid. NovelD successfully solves all the
environments while all other baselines only manage to solve two to three relatively easy ones.
Table I:
Visitation counts for the toy corridor environment after 3K episodes. NovelD explores corridors more uniformly than count- count-based approaches.
Table 2: Entropy of the visitation counts of each room. Such state distribution NovelD is much more uniform than RND.
C2
C4
Estrpp
0.2M
Room]
3.8/354
3.1/3353
3.56
3.59
Room?
2,87
309/322
13.53
/.35/3.54
Namel Thhetar
20K 3K
3SK
AK
29R
1.
Room3
- -4402
/4.01
RND
0.2X 0:3K
10K = 33K
03K + 0.07K
25K 44K
0.24 = 0.26
Room4
-1274
2,85 2287
NimeD
27K, J: AK:
24k J. 3K
XIX 125
263 IK
196 3: 8/45
Results are presented the orlar of "RND Novelt":
AND
100K
2:54
FrAmonert
NovelD
Figure 5: Normalized visitation counts NZ (Z is normalization constant) for the locations of agents. NovelD successfully explores all rooms within 4. 66M steps while RND gets stuck in the fifth room within 9.8M steps.
Multi-Roon environments are relatively easy in MiniGrid. However, all the baselines except RIDE fail. As we increase the room size and number (e.g.. MRMM21110 NovelD can achieve the goal quicker than RIDE. Our method quickly solves these environments within 20M environment steps.
On Key Corridor environments, RND, AMIGo, RIDE, IMPALA and NovelD successfully solves KCS3R3 while ICM makes reasonable progress. However, when increase the size (e.g., KCS5R3), none of the baseline methods work. NovelD manages to solve these environments in 40M environment steps. The agent demonstrates the ability to explore the room and finds the corresponding key to open the door in randomized, procedurally generated environment.
Obstructed Maze environments are also tricky. As shown in Fig. RIDE and RND manage to solve the easiest task 0M2D1h which doesn't contain any obstructions. In contrast, NovelD not only rapidly solves OM2DIh, but also solves four more challenging environments including OMFull. These environments have obstructions blocking the door (as shown in Fig. 3 and are much larger than 0M2D1h. Our agent leamss move the obstruction away from the door open the door and enter the next room in these environments. This "skill" is hard to learn since no extrinsic reward assigned to moving the obstruction. However, learning the skill is critical achieving the goal.
5

---

room
Focus 1 2dd room
Focus 1 2d room
Focus 2rd
room
Focus 1 room
Focus 2d room
Focus on 2d room
Focus on 3 room
NovelD
Figure 6: IR heatmaps for three- room environment. We that the high-IR region of NovelD has clear focus (the frontier) comparing RND.
4.2 Analysis of Intrinsic Reward in Pure Exploration
We observe that NovelD leads more focused exploration the boundary and broader state coverage by only using IR in the environment ("pure exploration" setting).
Broader State Coverage in Cor-ior Environment. We design a toy environment with four disconnected corridors with lengths 40, 10, 30, and 10 respectively. The agent starts from the common entry of the corridors and picks which corridor enter. In this example, there no extrinsic reward, and the agent's exploration is guided by IR. We use deep Q-learning (i.e.. Q function is parameterized by deep network) and try various IRs. This includes tabular IR (count-based and NovelD tabular) and
approximated IR (RND and NovelD) respectively for this experiment. We remove clipping from NovelD for fair comparison. Tab, shows the visitation counts across runs w.r.t. each corridor after 600 episodes of training. NovelD tabular explores all four corridors uniformly. On the other hand, count-based approaches focus on only two out of four corridors. NovelD also shows much more stable performance across runs as the standard deviation is much lower than RND.
Visitation Counts Analysis in MiniGrid. To study whether NovelD yields broader state coverage in MiniGrid, we test NovelD and RND in a fixed (instead of procedurally generated for simplicity) MRN7S8 environment. It contains 7 rooms connected by doors. We define metrics measure the effectiveness of an exploration strategy: (1) visitation counts ((s) at every state over training, and N(s))
(2) entropy of visitation counts in each room: H(p' (s)) where p'(s) Eoes, N(s)'
Fig. 5 shows the heatmap of normalized visitation counts N (s.)/Z, where Z is the normalization constant. At first, RND enters room 2 faster than NovelD. However, NovelD consistently makes progress exploring new states and discovers all the rooms in 5M steps, while RND gets stuck in room even trained with 10M steps.
In Tab. 2 the entropy of distribution each room H(p' (s)) for NovelD is larger than that of RND. This suggests that Novell) encourages more uniform exploration of the states than RND.
Intrinsic Reward Heatmap Analysis in MiniGrid. We visualize the IR produced in our algorithm and study whether it has higher focus on the boundary. We generate the plot by running the policy from different checkpoints for 2K steps and plot the IR associated with each state in the trajectory. States that do not receive IR from the sampled trajectories that before opening the door to the 2nd room, the NovelD IR is only high in the first one. As soon as the agent opens the door, the boundary of the explored region gets pushed to the next one. This can also be illustrated in the figure that regions with high IR are also changed correspondingly. In other words, this shows that when the door between rooms becomes a bottleneck for exploration, IR of NovelD focuses on solving this. similar phenomenon happens between the 2nd and 3rd rooms. In contrast, the IR in RND is more spread out (e.g., both 1st and 2nd room in the second figure).
left blank. From Fig. 6 we see
4.3 Ablation Study
Episodic Restriction on IR and Clipping NovelD. To illustrate the importance of exploring via novelty difference, we compare NovelD with modified version of RND: RND+ERIR, ERIR only gives RND intrinsic reward when visiting new state for the first time in an episode. As shown in Fig. the ERIR also improves the performance RND, but NovelD has much better results. We remove ERIR from NovelD and performance also drops.

---

AND with
AC36
apph-00775
Novil dip.66.0
NoveD
alphwi..5
RcyCumidv33Ra
SoyCorrida 39R3
Mulittomm 412 S19
0.0
0.8
0.8
02-
0.2
0.0
0.4
Envinomment Steps
1a7
Envinoment Steas
1a7
Ereiooment Stass
147
Figure 7: Ablation Study on NovelD with different scaling factor a and clipping threshold B. Results show that there exist an optimal choice for a 0.5 and 3 0.
NoveD
NevelD Random
NovelD
NovalD DBC
KeyConiderStee
Muttioonn N12 S10
1.0
1.0
2.0
0.8
0.6
0.6
0.4
0.4
0.4
3.5
0.2
0.4
l07
Figure 8: Ablation for NovelD under different representations. Successor representation sometimes works better than random feature, but not consistently.
IMPAAA
RAD
Nevvll
starcase
Auwraga Palum
102
2.2
0.2
0.4
0.6
0.5
1.0
0.2
0.2
0.4
0.5
0.5
1.0
0.0
0.2
0.4
0.6
score
SCOLE
or3ce
2002
Averge hetum
1500
Average Retum
-05
602
-1.
0.5
0.6
Eedfromment
Enufronment
Figure 9: Results for tasks on NetHack. NovelD achieves the SOTA results comparing to RND and IMPALA.
The optimal sealing ratio and clipping factor. We did an ablation on how different scaling ratio a and clipping factor 3 is affecting the performance of NovelD. Specifically, with the hyperparameter a and 3, the intrinsic reward now takes the form:
r (s, a,, s,+1) = max [novelty (s.41) - a novelty(s.),
(4)
Results show that a 0.5 and B = O works the best. We also compare with AK18 15 since they use difference-basee IR as well. AK18 achieves zero-reward
don't run them all the tasks.
NovelD under Different Representations. To study how NovelD performs under different represen- tations, we set both the target d(v) and predictor network o' (v) in RND to be MLP and uses the same CNN-based encoders e = fs) to project the image to vector for both of them. We trains another CNN-based encoder fs(s) according to different criteria and replace fs) with f'(s) periodically. Note that once we changed the representation of states, the novelty measure changes. So we store all the samples and retrain the predictor and target from scratch. We tries four different representations of the encoder: ICM 49 tries to learn a compact representation that are informative about state transition, Random embedding, DBC 62) follows the criterion of aggregating model-irrelevant states and Successor Features 377 of random embedded states captures the expected future features (s,) E (0((s:) where & is random embedding network).
We see that from Fig & DBC and ICM got zero reward since their representations are very compact and every state look similar to the RND networks. Thus, the predictor network quickly approximates the target network well and induces zero IR. For successor representation of random embedding, works better than random in KC series of maps but worse in MR maps.
4.4 Atari Games
Atari games are common benchmarks for RL. exploration. We test Novell on multiple hard explo- ration tasks (c.g., MonteZuma's 's Revenge, Gravitar, Solaries). We use the same paradigm as RND |I|
7

---

Venbure
Ale Retum
Anc-sye Netum
1502
2020
1003
HND
3200
1000
HNN
1300
Envirnmene Sheps
Envfronment Steps
Inl
Cnvirnment
leb
Figure 10: Results for hard exploration Atari games on Venture, Solaries and Gravitar. NovelD achieves strong results comparing to RND.
Norsscare Kazange shM
NeviD
Nevel
33003
4030
9003
3030
3.5
0.50
0.39
3.53
1.25
1,50
1.79
2.53
0-4
0.5
Figure 11: Results for hard exploration MonteZuma's Revenge. NovelD achieves good performance on both CNN and RNN networks comparing RND.
and the same set of hyperparameters on 128 parallel environments. We use the code base from RND and 84x84 image of the game as input. In NovelD, same RNN network architecture is used for all the tasks (except for the fourth figure Fig. M we use simple CNN architecture). The baseline algorithm being used is PPO. Due to the computation limit, didn't 't run NovelD to 2 billion steps as originally reported in the RND paper. We mark the performance of RND at the similar steps as red dot. Note that didn't t compare with SOTA method Go- Go-Explore since it involves lot of hand-tuned hyperparameters and highly incorporates domain knowledge. For another strong baseline NGU [5), since there is open-sourced implementation online, it is hard for to evaluate their code and do fair comparison with them.
In Fig. I can see that using CNN-based model, NovelD achieves approximately 10000 external rewards after two Billion frames while the performance reported RND [T] is around 6700. When using an RNN-based model, NovelD reached around 13000 external rewards in 100K updates while RND only achieves 4400. In Fig. I0 we also see that NovelD manage to explore 23 rooms in the given steps while RND only explores 17. For other games (e.g.. Venter, Gravitor and Solaries), NovelD is consistently better than RND in the given steps, achieving 500 to 1000 more rewards.
For the implementation of ERIR, a simple lixel-based hash table is used for counting. We found that the hash table gives reasonable performance even in the stochastic environments. This is different from Ex-Exxllre
7 where heavy domain-knowlede knowledge is incorporated.
4.5 The NetHack Learning Environment
We also evaluate NovelD in NetHack Learning Environment environment. The player needs to descend over 50 ppcedurally--gneeeee levels to the bottom and find "Amulct of Yendor" in the dungeon. The procedure can be described as first retrieve the amulet, then escape the dungeon and finally unlock five challenging levels (the four Elemental Planes and the Astral Plane). We test NovelD on set of tasks with tractable subgoals in the game: Staircase: navigating to a staircase to the next level, Pet: reaching a staircase and keeping the pet alive, Gold: collecting gold, Score: maximizing the score in the game, Scout: scouting to explore unseen areas in the environment, and Oracle: finding the oracle (an in in-game character at level 5-9).
3 more challenging and realistic
Results in Fig. D show that NovelD surpasses PPO+RND and IMPALA (without exploration bonus) on all tasks. Especially on Pet, NovelD outperforms the other two with a huge margin. This again illustrates the strong performance of NovelD in an environment with huge action spaces and long- horizon reward. Oracle the hardest task and no approaches are able find the oracle and obtain reward of 1000. NovelD still manages to find a policy with less negative rewards (i.e., a penalty of taking actions that do not lead to game advancement, like moving towards wall).
Discussion
"On NetHack, we do not report RIDE performance. Our attempt fails and the authors verify it doesn't work yet on NetHack.
8

---

Muttioomm NelsyTV N7 54
Determinstic and Stochastic Environments. Nov- elD can both work with determiniitic(MMniGrrj) and stochastic(NetHaat and Atari) environments. Al- though reaching the frontier of a stochastic environ- ment is itself hard problem, by putting a high IR on the boundary states and training the agent with RL algorithms, the policy will prefer to reach those frontier states more frequently. In such case, NovelD also manage to achieve its exploration purpose. In addition to that, we also test NovelD in stochastic environments like NetHack showing superior performance. Finally, the hash- tabled based ERIR do have some potential issue in stochastic environments. However, in all of the tasks tested, it doesn't show clear problem of directly applying it in stochastic environments.
1.0
NeveID
0.8-
RIDE
0.6
Average
0.4
0.2
0.0
5
6
Environment Stops
166
FA and Atari games,
Figure 12: Results for NovelD under the Noisy-
TV setting introduced in RIDE [52]. NovelD still have strong performance under the noisy TV envi- ronment.
Noisy TV problem. As mentioned [T], curiosity-basee and count-based criterion will get stuck in nosity-TV problem. However, RND manages to mitigate this problem [л. Since also adopt RND as the novelty measure, NovelD also shows the resilient to the problem. We also test NovelD in manually-made noisty-TV setting in MiniGrid introduced in RIDE [52], where there always some blocks changing color at every time step. NovelD still gain a strong performance even under this setting. In addition, empirically we don't 't see the performance degrade of NovelD due to the nosiy-TV problem in all our experiments including MiniGrid, Atari Games and NetHack.
Limitations. We don't test NovelD in some continuous RL domains. Especially, directly applying ERIR to that for those tasks (e.g., some roboties tasks) might lead to some performance degrade. We leave more general solution of this to future work.
6 Related Work
In addition to the two criteria (count-based and state-diff based) mentioned above, another stream of defining IRs is curiosity-based The main idea is to encourage agents explore prediction of the next state from the current learned dynamical model is wrong. Dynamic-AB [60] computes the distance between the predicted and the real state on the output of an autoencoder, ICM 49 learns the state representation through forward and inverse model and EMI (32] computes the representation through maximizng mutual information I([s, a]; and I s));a.
where the
Another line of research is using information gain to reward the agent. VIME 28 uses a Bayesian network to measure the uncertainty of the learned model. Later, to reduce computation, deterministic approach has been adopted [ Other works also propose to use an ensemble of networks for measuring uncertainty (50) [66] We can also reward the agent by Empowerment
33
25
53 42)
prioritizing the states that the agent can take control through its actions. is different from state-diff:
s differs from St but not due agent's choice of actions, then the empowerment at s; zero. [6 or the KL divergence between current distribution over states and target distribution of states 335
Other criteria exist, e.g., diversity [20] feature control 30
Outside of intrinsic reward, researchers have proposed to use randomized value functions to encourage exploration 46 27 47). Adding noise the network is also shown to be effective [ 51] There
has also been effort putting to either explicitly or implicitly separate exploration and exploitation [4] Go-Explore series 177 [
22 RG
also fall in this category. We might also set up different goals for Another stream of research studies exploration problem using model-based
exploration 26
43
3
approaches
45
They either assume world model is given attempt learn it, which is
often impractical when the environment is complex. However, NovelD is completely model-free and can be applied widely complicated environments.
Curriculum learning / has also been used to solve hard exploration tasks. The curriculum can be explicitly generated by: searching the space [54], teacher-student setting [39], increasing distance between the starting point and goal [2 or using a density model to generate a task distribution for the meta learner (1]]. NovelD never explicitly generates curriculum.

---

7 Conclusion
In this work, inspired by breadth-fine firstt search, we introduce a new criterion for intrinsic reward (IR) that encourages exploration using a regulated difference of novelty measure using RND. Based on the criterion, our algorithm NovelD successfully solves all static tasks in a procedurally generated MiniGrid environment, which is a significant improvement over the previous SOTA. In multiple environments, NovelD shows a broader state coverage with a focus of on the boundary states, We also evaluate NovelD on NetHack, more challenging task. NovelD outperforms all the baselines by a large margin. summary, this simple criterion and the ensuing algorithm demonstrate effectiveness in solving sparse reward problems in reinforcement learning, opening up new opportunities to many real-world applications.
Acknowledgements
This project occurred under the BAIR Commons UC-Berkeley and we thanks Commons sponsors for their support. In addition to NSF CISE Expeditions Award CCF-1730622 UC Berkeley research is supported by gifts from Alibaba, Amazon Web Services, Ant Financial, CapitalOne, Ericsson, Facebook, Futurewei, Google, Intel, Microsoft, Nvidia, Scotiabank, Splunk and VMware.
References
[1] Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint
2017.
[2] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. PC-PG: Policy cover directed exploration for provable policy gradient learning. arXiv preprint arXiv:2007.0845 08459,, 2020.
[3] Marcin Andrychowicz. Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong. Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, pages 5048-5058, 2017.
[4] Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. arXiv preprint arXiv:2003. 13350, 2020.
[5] Adrià Puigdomênech Badia, Pablo Sprechmann, Alex Vitvitskyi. Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, et al. Never give up: Learning directed exploration strategies. arXiv preprint arXiv:2002.06038 2020.
[6] 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, pages 1471-1479, 2016.
[7] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41-48, 2009.
[8] Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for npar-optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):213-231, 2002.
[9] Greg Broekman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
[10] Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of auriosity-driver learning. arXiv preprint 18Xiv:1808. 04355, 2018.
[11] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv:18100 10.10./2899 /2894, 2018.
[12] Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv preprint 200::2006..1222 2020.
10

---

[13] Maxime Chevalier- Boiisertiettt Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. /ttt:://gttbbb https:///gthubb.cmmmmaaaaaeeeee wwwp//xwiwwb///aeeeeeeecoo gaaeeeebbgymmaeeg hymm-minggrd, 2018.
[14] Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. Gep-pg: Decoupling exploration and exploitation in deep reinforcement learning algorithms. arXiv preprini arXiv: /eoi. 2018.
[15] Ildefons Magrans de Abril and Ryota Kanai. Curiosity-driven reinforcement learning with homeostatic regulation. In 2018 International Joint Conference on Neural Networks (IJCNN), pages 1-6. IEEE, 2018.
[16] Nat Dilokthanakul, Christos Kaplanis, Nick Pawlowski, and Murray Shanahan. Feature control as intrinsic motivation for hierarchical reinforcement learning. IEEE transactions on neural networks and learning systems, 30(1 (00011):34000 33:3949-34,8, 2019.
[17] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint 1rXiv:1901.1099) 2019.
[18] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return then explore. arXiv preprint arXiv:2004. 12919, 2020.
[19] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint 1rXXiv1802..000 01561, 2018.
[20] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without a reward function. arXiv preprint arXiv: ToX.00/002.00000, 2018.
[21] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. arXiv preprint arXiv:1707.05300 2017.
[22] Sébastien Forestier, Yoan Mollard, and Pierre- Yves Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. arXiv preprint arXiv:1708.0211 02100, 2017.
[23] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: 10295, 2017.
[24] Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Yoshua Bengio, and Sergey Levine Infobot: Transfer and exploration via the information bottleneck. arXiv preprint arXiv:1901.1090) 2019.
[25] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint 16 2016.
[26] Zhaohan Daniel Guo and Emma Brunskill. Directed exploration for reinforcement learning. arXiv preprint arXiv:1906.000 008550 2019.
[27] Matteo Hessel, Joseph Modayil, Hado Van Hasselt. Tom Schaul, Georg Ostrovski, Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. arXiv preprint arXiv: 1710.0229,, 2017.
(28) 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, pages 1109-1117, 2016.
[29] Allan Jabri, Kyle Hsu, Abhishek Gupta, Ben Eysenbach, Sergey Levine, and Chelsea Finn. Un- supervised curricula for visual rentrreeiffr learning. In Advances in Neural Information Processing Systems, pages 00519-10531, 2019.
[30] Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czamecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint xrXiv:1611.05397,200 2016.

---

[31] Chi Jin, Zeyuan Allen Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances Neural Information Processing Systems, pages 4863 1663,4873,00 2018.
[32] Hyoungseok Kim, Jaekyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Exploration with mutual information. arXiv preprint arXiv:/810.0111111 2018.
[33] Alexander S Klyubin, Daniel Polani, and Chrystopher L Nehaniv. All else being equal be empowered. In European Conference on Artificial Life, pages 744-753. Springer, 2005.
[34] Heinrich Küttler, Nantas Nardelli. Alexander H Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The nethack learning environment. arXiv preprint arXiv:2006. 13760, 2020.
[35] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Rus- lan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv:/906.0522 055774 2019.
[36] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-1 1373, 2016.
[37] Marlos C Machado, Mare G Bellemare, and Michael Bowling. Count-based exploration with the successor representation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3133-5133, 2020.
[38] Kenneth Marino, Abhinav Gupta, Rob Fergus, and Arthur Szlam. Hierarchical RL using an ensemble of proprioceptive periodic policies. In International Conference on Learning Representations, 2019. URL. httpttt:
[39] Tambet Matüsen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE transactions on neural networks and learning systems, 2019.
[40] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:1312.5602, 2013.
[41] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015,
[42] Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. In Advances in neural information processing systems, pages 2125-2133, 2015.
[43] Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. arXiv preprint arXiv: 1806 05635, 2018
[44] P Ortner and R Auer. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in Neural Information Processing Systems, 19:49, 2007.
[45] Ian Oshand, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. arXiv preprint arXiv: 1306.0300090 2013.
[46] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances neural information processing systems, pages 4026-4034, 2016.
[47] Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
[48] Georg Ostrovski, Mare G Bellemare, Aaron van den Oord, and Rémi Munos. Count-based exploration with neural density models. arXiv preprint arXiv: 1703. 01310, 2017.
[49] 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 Pattern Recognition Workshops, pages 16-17, 2017.
12

---

[50] Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagree- ment. arXiv preprint arXiv:1906.04100 2019.
[51] Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. arXiv preprini arXiv: 1706.77909900 2017.
[52] Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-drive exploration for pnceeuurally-geneaate environments. arXiv preprini arXiv:2002. 12292, 2020.
[53] Christoph Salge, Comelius Glackin, and Daniel Polani. Empowerment an introduction. In Guided Self- Organization: Inception, pages 67-114, Springer, 2014.
[54] Jürgen Schmidhuber. Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem. Frontiers in psychology, 4:313, 2013.
[55] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:177700637, 2017.
[56] Pranav Shyam. Wojeiech Jaškowski, and Faustino Gomez. Model-based active exploration. In International Conference on Machine Learning, pages 5779-5788, 2019.
[57] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):48444555 2016.
[58] David Silver, Julian Schrittiesser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[59] David Silver, Thomas Hubert. Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(64199;1140-11444 2018.
[60] Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint / 00 2015.
[61] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-355 -5440 2019.
[62] Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006.10744 10742, 2020.
[63] Jingwei Zhang, Niklas Wetzel, Nicolai Dorka, Joschka Boedecker, and Wolfram Burgard. Scheduled intrinsic drive: A hierarchical take on intrinsically motivated exploration. arXiv preprint 1rXiv:1903.074000 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We claim propose efficient exploration criterion that achieves strong results. The experiments are conducted MiniGrid, NetHack and MonteZuma's 's Revenge.
(b) Did you describe the limitations of your work? [Yes] We discuss limitations in the Discussion section.
13

---

(c) Did you discuss any potential negative societal impacts of your work? [No] We do foresee any obvious negative societal impacts from our work, which contributes general-purpose exploration algorithm.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full assumptions of all theoretical results? [N/A] We don't 't have theorem part.
(b) Did you include complete proofs of all theoretical results? [N/A] We don't have theorem part.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] We upload the code in supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We include the training detail in supplemental material.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We include the error bars for experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We use publicly available datasets/tasks.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] We don't 't use data of this sort.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zWXxORMPqVZ", "reviewer": "Reviewer_JUfr", "summary": "This paper presents a simple exploration criterion NovelD. The basic idea is to use the difference of the novelties between the next state and the current state as an intrinsic reward, which is the \"boundary\" of the explored and unexplored regions. This idea is implemented with a max operation to avoid negative rewards, a binary indicator that only rewards the state visited for the first time, and RDN as the novelty measure. The experiments are conducted on MiniGrid, NetHack, and some hard exploration environments in Atari.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The idea of exploration \"boundary\" is interesting. The intrinsic reward is simple and intuitive. \n2. The results are strong. It solves all the tasks in MiniGrid in a short time. It significantly outperforms the baselines. In addition, it also shows advantages in NetHack and some hard exploration problems in Atari.\n3. The paper is clearly written.\n\nWeaknesses:\n1. The paper mentions SOTA many times. However, some SOTA algorithms in MiniGrid are not discussed/compared. [AGAC](https://openreview.net/forum?id=_mQp5cr_iNy) seem to also be able to solve many tasks in MiniGrid. In particular, AGAC is shown to be able to solve KeyCorridorS8R3, which is more challenging and is not included in this paper. [RAPID](https://openreview.net/forum?id=MtEE0CktZht) can also solve many MiniGrid environments efficiently. In particular, RAPID seems to be more sample efficient than NovelD on some MultiRoom environments (such as MultiRoom-N7-S8) based on the reported results. It is unclear why these two methods are not compared in MiniGrid tasks and are not even discussed.\n2. The authors noted that \"NovelD puts a more aggressive restriction: the agent is only rewarded when it visits the state for the first time in an episode.\" It is unclear why the authors apply this aggressive restriction. How will it perform if using the scaling method in RIDE?\n3. The authors noted \"Asymptotic Inconsistency\" is one of the advantages of NovelD. However, the authors ignore a simple strategy. One could simply anneal the coefficient of the intrinsic to zero in the training process. In this way, the policy could still maximize the extrinsic reward eventually.\n4. For Atari games, the NovelD uses a simple pixel-based hash table for counting. The pixel-based hash table seems to be not well-suited for image input. A possible reason it works is that the Atari environments are not procedurally generated so that we can encounter the same states in different episodes. It is unclear how this method can be applied to procedurally generated settings, such as procgen.\n\nQuestions:\n1. The authors mention \"two-stage\" and \"one-stage\" approaches. I can not find an explanation for this.\n2. In procudually-generated environments, both $s_t$ and $s_{t+1}$ could be very novel if the observation space is large. MiniGrid has a very simple observation space. Can NovelD handle procedurally-generated image input, such as procgen?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "mrckcWC_nQi", "reviewer": "Reviewer_acG2", "summary": "This paper introduces a simple but effective improvement for novelty-based exploration methods: using regulated novelty difference of consecutive states in a trajectory. Extensive experiments on MiniGrid, Atari and NetHack demonstrate the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The proposed modification is simple but effective, significantly outperforming prior works on MiniGrid benchmark.\n* The experiments are extensive and solid.\n* The writing is clear and easy to follow.\n\nComments:\n* In Section 3.1, NovelD is described as a general meta-criterion that can be applied on top of any novelty measure. However, the authors only use RND in experiments. It would be better to test other novelty measures.\n* In Section 3.2, the authors mention that one of the advantages of NovelD is asymptotic consistency. But it is unclear whether this is a severe issue. How seriously it would affect exploration if an approach is asymptotic inconsistent? The authors could add more discussions on this.\n* Some implementation details are missing. The authors say they use PPO in Section 4. However, the hyper-parameters mentioned in Appendix are more like for IMPALA. Did the authors implement NovelD with PPO and other baselines with IMPALA? Is the policy a feed-forward one or recurrent one? For PPO, hyper-parameters like num_epoch, num_minibatch and GAE lambda are missing. I suggest the authors doing a through check on this and include missing implementation details.\n* Some descriptions in Section 4.3 (NovelD under Different Representations) are a little bit confusing. Why \"replace f(s) with f'(s) periodically\"? I do not quite understand how training with different representations is done. Please give some clarifications.\n* For the main results in Figure 4, it would be better to include comparisons to recent SOTAs (RAPID [1] and AGAC [2]).\n\nMinor points (I do not factor these into my assessment):\n\n* The authors should carefully go through the paper and fix some typos and errors:\n  * Extra right parenthesis in Line 111.\n  * Line 196: \"Clipping n NovelD\" -> \"Clipping in NovelD\"?\n  * Line 225: Figure 11 does not have 4th figure.\n* Please, use up-to-date reference instead of arXiv version, e.g., PC-PG, Agent 57, NGU. Please go over all of them.\n\nOverall, I think the method is simple and works well as demonstrated by extensive experiments. However, the concerns need to be addressed before acceptance.\n\n[1] Daochen Zha, Wenye Ma, Lei Yuan, Xia Hu, and Ji Liu. Rank the episodes: A simple approach for exploration in procedurally-generated environments. In International Conference on Learning Representations, 2021.\n\n[2] Yannis Flet-Berliac, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adversarially guided actor-critic. In International Conference on Learning Representations, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Ns46c8l6fRB", "reviewer": "Reviewer_fYfB", "summary": "This paper introduced NoveId, a new exploration technique that can extend any exploration bonus. The new bonus is computed by looking at the difference in novelty between a new state and the previous state. The authors argue that this bonus does not suffer from detachement and improves exploration in many complex environments. These claims are substantiated by experiments on Mini Grid, the Arcade learning environment and NetHack that shows that NoveId outperforms existing exploration methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I enjoyed this paper, I think that the NoveID bonus is a good idea to encourage the agent towards regions with large intrinsic reward variance. The idea is simple and builds on existing techniques nevertheless it was properly evaluated through a series  of experiments.\nExploration remains a big challenge in reinforcement learning and papers like this one making progress in this area are important.\n\nWhile I agree that NoveID improves exploration it is not clear to me if it actually fixes detachement. In particular I don't agree with the explanation provided in Figure 1. I am not sure that RND would forget that it visited the upper right corner and increase the reward in 3. after decreasing it in 2. My guess would be that instead in 3 the whole right side would be light blue. In this case the agent might indeed get stuck if it is in the middle of this region however I believe the same thing would happen with NoveID. NoveID will do better here because the agent will receive a higher reward signal if it manages to reach the exploration frontier; however NoveID will not provide a better signal than RND in regions already explored.\n\nI'm also not sure I agree with the asymptotic inconsistency mentioned in section 3.2. Once the prediction network has gathered enough data about the environment is should be able to match the embedding network, in this case I don't see why a state in representation would happen. It is also not clear why NoveID would asymptotically consistent, can the authors provide more insight here?\n I also really enjoyed the different visualizations to help understand how NoveId behaves differently from existing algorithms. \n\nRegarding experiments I found the MiniGrid experiments in section 4.1 and 4.2 particularly interesting and they demonstrate well the benefits of NoveID. Though in section 4.3 I found it hard to draw any statistically significant conclusion from plots given that there are only 4 seeds. Given the lower computation resources needed to run MiniGrid vs other benchmarks like Atari it would have been nice to see more seeds here.\n\nIt is also hard to draw any conclusion from Atari experiments as only evaluating hard exploration games is not enough to evaluate an exploration algorithm (see [1]). Evaluating NoveID on more games is necessary to properly evaluate its performance on Atari games and see if the increased performance on hard exploration games does not lead to a decrease performance on easier exploration games. It would also be helpful to add epsilon-greedy as a baseline and mention whether or not sticky actions were used.\n\nIn the end I still lean towards acceptance given the results on MiniGrid and NetHack however the paper would stronger with a better evaluation on Atari games.\n\nL55: \"in NoveID, there is almost no hyperparameters\", I don't think this is a fair statement given that NoveID adds a new hyperparameter on top of the novelty algorithm it is using.\n\n**Clarity**\n\nOverall I found the paper well written and easy to follow. The authors made an effort to provide many graphics to back up their claim and help the reader.\n\n\n**Small typos:**\n \nL47: Atari games is\nL52: MonteZuma's Revenge instead of Montezum's Revenge\nL64: What is t?\nL112: Is it Eq 4 or 2? If it is 4 it is a bit confusing as this equation is only referenced many pages later.\n\n[1] On bonus-based exploration methods in the arcade learning environment, ICLR 2020\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Np1_Ixjxijs", "reviewer": "Reviewer_a3jn", "summary": "The paper proposes a novel exploration bonus for reinforcement learning, NovelD, which consists in adding a weighted clipped difference of the novelty of two consecutive states to the reward. The paper argues that this provides a breadth-first kind of exploration, in contrast to pure novelty based methods that would provide a more depth-first exploration. The paper provides extensive experimental validations, on a variety of environments. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I have very few complaints about the paper. The idea provided by the paper is novel, interesting, and the presentation is clear. \n\nMy main comment is that the paper introduces two distinct contributions to exploration: the exploration bonus, based on a difference of novelty of subsequent states, and Episodic Restriction on Intrinsic Reward, which only limits intrinsic rewards to state that were only visited once in an episode. While the exploration bonus is very general and can be used in most RL problems, ERIR is arguably more ad-hoc: it requires discrete or hashable states, potentially with a well-suited hash. The authors provide an ablation of ERIR on one of the environments, and show that NovelD with ERIR outperforms RND with ERIR. However, I feel that the relative weighting of the two contributions could be better explicited, by providing:\n  - Results for NovelD - ERIR on the MiniGrid environment.\n  - Results for both NovelD - ERIR and RND + ERIR on Nethack and Atari.\n\nIn addition to this comment I have a few minor comments:\n- There are a few english mistakes, including, but not restricted to:\n  l5. in a depth-first manner\n  l8. it won't suffer -> optimistic ... won't suffer\n  l9-10. in a breadth-first manner\n  l29. they fail\n  l30. we observe that\n  l32. these methods can get trapped\n  l34. the detachment\n  l37. approximately\n  l42. compared\n  l51. by a significant\n  l55. is a one-stage\n  l57. asymptotically consistent\n  l58. are not\n  l72. has not\n- There is a small notational inconsistency: alpha is used twice, once for the intrinsic reward weighting, once for the weighting between the current and next state novelty.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, to the best of my understanding.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the reviews, the authors response and the discussions, I suggest to accept the paper. All reviewers agree that the paper presents an original idea in a clear way. Minor questions and concerns have been answered during the rebuttal by the authors. Overall the idea is simple but yet effective on a spectrum of different tasks. In addition, the method is compared with state of the art baselines. To improve the paper, experiments on more challenging environments such as 3D visual game could be considered.
Decision: Accept (Poster)