BeBold: Exploration Beyond the Boundary of Explored Regions
Authors: Tianjun Zhang
Huazhe Xu
Xiaolong Wang
Yi Wu
Kurt Keutzer
Joseph E. Gonzalez
Yuandong Tian
Venue:  (2021)
Keywords: reinforcement learning
exploration

Abstract: Efficient exploration under sparse rewards remains a key challenge in deep reinforcement learning. To guide exploration, previous work makes extensive use of intrinsic reward (IR). There are many heuristics for IR, including visitation counts, curiosity, and state-difference. In this paper, we analyze the pros and cons of each method and propose the regulated difference of inverse visitation counts as a simple but effective criterion for IR. The criterion helps the agent explore Beyond the Boundary of explored regions and mitigates common issues in count-based methods, such as short-sightedness and detachment. The resulting method, BeBold, solves the 12 most challenging procedurally-generated tasks in MiniGridwith just 120M environment steps, without any curriculum learning. In comparison, previous SoTA only solves 50%of the tasks. BeBold also achieves SoTAon multiple tasks in NetHack, a popular rogue-like game that contains more challenging procedurally-generated environments.

Under review as a conference paper at ICLR 2021
BEBOLD: EXPLORATION BEYOND THE BOUNDARY OF EXPLORED REGIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Efficient exploration under sparse rewards remains a key challenge in deep rein- forcement learning. To guide exploration, previous work makes extensive use of intrinsic reward (IR). There are many heuristics for IR, including visitation counts, curiosity, and state-difference. In this paper, we analyze the pros and cons of each method and propose the regulated difference of inverse visitation counts sim- ple but effective criterion for IR. The criterion helps the agent explore Beyond the Boundary of explored regions and mitigates common issues in count-based methods, such as short-sightedness and detachment. The resulting method, Be- Bold, solves the 12 most challenging with just 120M environment steps. without any curriculum learning. In compar- ison, previous SoTA only solves 50% of the tasks. BeBold also achieves SoTA multiple tasks in NetHack, a popular rogue-like game that contains more chal- lenging procedurally-genee
seceduralllygeneratte
tasks in MiniGrid
environments.
INTRODUCTION
Deep reinforcement learning (RL) has experienced significant progress over the last several years, with impressive performance in games like Atari (Mnih et al., 2015; Badia et al., 2020a). Star- Craft (Vinyals et al., 2019) and Chess (Silver al., 2016; 2017; 2018). However, most work quires either a manually-designed dense reward (Brockman et al., 2016) or a perfect environment model (Silver et al., 2017: Moravčík et al., 2017). This is impractical for real-world settings, where the reward is sparse; in fact, the proper reward function for a task is often even unknown due to lack of domain knowledge. Random exploration (e.g., c-greedy) in these environments is often insufficient and leads to poor performance (Bellemare et al., 2016).
Recent approaches have proposed to use intrinsic rewards (IR) (Schmidhuber, 2010) to motivate agents for exploration before any extrinsic rewards are obtained. Various criteria have been pro- posed, including curiosity/surprise--riiv
(Pathak et al., 2017), count-based (Bellemare et al., 2016; Burda et al., 201 8a;;; Ostrovski et al., 2017; Badia et al., 2020b), and state-diff approaches (Zhang et al., 2019; Marino et al., 2019).
Each approach has its upsides and downsides: Curiosity- -riven approaches look for prediction errors in the learned dynamies model and may be misled by the noisy TV (Burda et al., 2018b) problem, where environment dynamics are inherently stochastic. Count-based approaches favor novel states in the environment but suffer from detachment and derailment (Ecoffet et al., 2019), in which the agent gets trapped into one (long) corridor and fails to try other choices. Count-based approaches are also short-sighted: the agent often settles in local minima, sometimes oscillating between two states that alternately feature lower visitation counts (Burda et al., 2018b). Finally, state-diff approaches offer rewards if, for each trajectory, representations of consecutive states differ significantly. While these approaches consider the entire trajectory of the agent rather than a local state, it is asymptoti- cally inconsistent: the intrinsic reward remains positive when the visitation counts approach infinity. As result, the final policy does not necessarily maximize the cumulative extrinsic reward.
In this paper, we propose a novel exploration criterion that combines count-based and state-diff ap- proaches: instead of using the difference of state representations, we use the regulated difference of inverse visitation counts of consecutive states in trajectory. The inverse visitation count approx- imated by Random Network Distillation (Burda et al., 2018b). Our IR provides two benefits: (1) the stafe-diff, since the inverse visitation count vanishes
This addresses asymptotic inconsistency with sufficient explorations. (2) Our IR is large at the end of a trajectory and at the boundary be- tween the explored and the unexplored regions (Fig. 1). This motivates the agent to move Beyond

---

Under review as a conference paper at ICLR 2021
TA
RND
assiess high (dark green) throughout the environment
temporanly focuses on the upper right comnrr [velow)
3. chance starts exploring bortom right conner heavlly, resulting the it top right higher than botton right
no socoloooe upper right and forgets bottom right, gets trapped
THE
F
PAAS
PAC
BeBold
fellildd Idark red) the fight red]
BuBold pushas direction the franbler unilornly
SuBoid comtincusly exploration
ixploration
(yeliow)
Figure 1: Hypothetical Demonstration of how exploration is done in BeBold versus Random Network Distillation (Burda et al., 2018b), in terms of distribution of intrinsic rewards (IR). BeBold reaches the goal by continuously pushing the frontier of exploration while RND got trapped. Note that IR is defined differently in RND (s:N(s:)) versus BeBold (max(1/N) (S:41) I/N (s:), 0). See Eqn. 3), and different color is used.
the Boundary of the explored regions and step into the unknown, mitigating the short-sighted issue in count-based approaches.
Following this simple criterion, we propose a novel algorithm BeBold and evaluate it on two very challenging procedurally eeeeddrrllyyggeeraatedd (PG) environments: MiniGrid (Chevalier -hevallir-Boiiverrt et al., 2018) and NetHack (Küttler al., 2020). MiniGrid is popular benchmark for evaluating exploration algorithms (Raileanu and Rocktäschel, 2020; Campero et al., 2020; Goyal et al., 2019) and NetHack realistic environment with complex goals and skills. BeBold manages to solve the 12 most challenging cnvironments MiniGrid within 120M environment steps, without curriculum learning. In contrast, (Campero et al., 2020) solves 50% of the tasks, which were categorized as "easy" and "medium", by training separate goal-generating teacher network in 500M steps. environment, BeBold also outperforms all
much
In NetHack, a more challenging baselines with a significant margin on various tasks. In addition, we analyze BeBold extensively in MiniGrid. The quantitative results show that BeBold largely mitigates the detachment problem, with much simpler design than Go-Explore (Ecoffet et al., 2020) which contains multiple hand- tune stages and hyper- apper-parameters..
Most Related Works. RIDE (Raileanu and Rocktäschel, 2020) also combines multiple criteria to- gether. RIDE learns the state representation with curiosity-driven approaches, and then uses the difference of learned representation along trajectory as the reward, weighted by pseudo counts of the state. However, tion of the learned representation on novel states. As a result, BeBold shows substantially better performance in the same sereeddurallygeeeerate environments.
two-stage approach, RIDE heavily relies the quality of generaliza-
Go-Explore (Ecoffet et al., 2020) stores many visited states (including boundaries), reaches these states without exploration, and explores from them. BeBold focuses on boundaries, perform explo- ration without human-designed cell representation (e.g., image downsampling) and is end-to-end.
Frontier-basee exploration (Yamauchi, 1997; 1998; Topiwala et al., 2018) is used to help specific robots explore the map by maximizing the information gain. The "frontier" is defined as the 2D spatial regions out of the explored parts. No automatic policy optimization with deep models is used. In contrast, BeBold can be applied to more general partial observable MDPs with deep policies.
BACKGROUND
Following single agent Markov Decision Process (MDP), we define a state space S, an action space A. and (iemmittermiiistic) transition function T S x A - P(S) where P(S) is the probability of next state given the current state and action. The goal is maximize the expected reward R. E > where Ft is the reward, is the discount factor, and the expectation is taken w.r.t. the policy и and MDP transition P(S). In this paper, the total reward received at time step t is given by = rf ari, where of is the extrinsic reward given by the environment, rद is the intrinsic reward from the exploration criterion, and is a scaling hyperparameter.
2

---

Under review as a conference paper at ICLR 2021
3 EXPLORATION BEYOND THE BOUNDARY
ex
Our new exploration criterion combines both counting- based and state-diff- sife--iiff-ased based criteria. Our crite- rion doesn't It suffer from short- sighteiight BeBold and then analyse the advantages of BeBold over existing criteria in Sec. 4.
s and is asymptomatiedl consistent. We Wl'll first introduce
Exploration Beyond the Boundary. BeBold gives intrinsic reward (IR) to the agent when it ex- plores beyond the boundary of explored regions, i.c., along trajectory, the previous state S, has been sufficiently explored but 8 is new:
((R))) )
1
(St, ar, S1+1) = max N(s++)
(I)
Here N is the visitation counts. We clip the IR here because we don't t want to give a negative IR to the agent if it transits back from novel state to a familiar state. From the equation, only crossing the frontier matters to the intrinsic reward; if both (ss)) and (s++1) are high or low, their difference would be small. As we will show in Sec. 4, for each trajectory going towards the frontier/boundary, BeBold assigns an approximately equal IR, regardless of their length. As result, the agent will willi continue pushing the frontier of exploration in a much more uniform manner than RND and won't t suffer
suffer from sighteiighs This motivates the agent to explore different trajectories uniformly. Also Eq. is asymptotically consistent as r² - 0 when N - x..
Like RIDE (Raileanu and Rocktäschel, 2020), in our implementation, partial observation og are used instead of the real state Sy, when S; is not available.
Episodic Restriction on Intrinsic Reward (ERIR). In many environments where the state tran- sition is reversible, simply using intrinsic reward to guide exploration would result in the agent going back and forth between novel states S14-1 and their previous states S,. RIDE (Raileanu and Rocktäschel, 2020) avoids this by scaling the intrinsic reward r(s) by the inverse of the state visita- tion counts. BeBold puts a more aggressive restriction: the agent is only rewarded when it visits the state for the first time in an episode. Thus, the intrinsic reward of BeBold becomes;
))
1
r't (sc, ag, 5 max
(((
N(s.) ((N( = 13
(2)
N₂ here stands for episodic state count and is reset every episode. In contrast, the visitation count N is a life-long memory bank counting state visitation across all of training.
Inverse visitation counts as prediction difference. We use the difference between a teacher á and
a student network ø' approximate visitation counts: 1()++1) ~ Telo4:)) (outoon here 0++11
the observation of the agent in state 8,+1. This yields the following implementation of BeBold:
= max([1o(o -ei)))-''ooe (((o+1))la - llx(o)) - & (((oo)ll2:0) 0) * 1 ((Nc(oe1)) = 13) =1))
(st, a,, S++1) =
(3)
Shared visitation counts (s:)) in the training of Procedurally-Geneet Snncedurally-Generaae During training, the environment changes constantly (e.g., blue keys becomes red), while the se- mantic links of these objects remain the same. We use shared RND (ő, ø') across different PG unvironments. and treat these semantically similar states as new without using domain knowledge (e.g., image downsampling like in Go- Go-Explore (Ecoffet et al., 2019)). Partial observability and gen- eralization of neural network & handles these differences and leads to count-sharing. For episodic count N₂ (0++1), since it is not shared across episodes (and environments), we use hash table.
(PG) Environments.
4 CONCEPTUAL LONCEPTUALAAAE ADVANTAGES OF BEBOLD OVER EXISTING CRITERIA
Short-sightedness and Detachment. One issue in the caset approach is its sight-ssg M starting at Sy and extending Let's assume in simple environment, there are M corridors {T, )
to different parts of the environment. The corridor Ty has length of Tj. The agent starts at So- For each visited state, the agent receives the reward of Nis) where N(-) is the visitation count, and learns with Q-learning. Then with some caleulation (See Appendix), we see that the agent has e strong preference on exploring the longest corridor first (say TT). and only after a long period does it start to explore the second longest. This is because the agent initially receives high IR in Ti due to explore
g
its length, which makes the policy и visit 71 more often, until it depletes the IR in 71-
This behavior of "dedication" could lead to serious issues. If M 2 3 and 2 corridors are long enough (say 7i and 72 long), then before the agent is able to explore other corridors, its policy n
3

---

Under review as a conference paper at ICLR 2021
has already been trained long enough so that it only remembers how get into Ti and T2. When TI has depleted its IR, the agent goes to 72 following the policy. After that, the IR in Ti revives since the visitation counts in 7i is now comparable Ti again following the policy. This leaves other corridors (e.g., T3) unexplored for very long time. Note that using& neural-netwer network-apprroxinnaee
even smaller than 72, which lures the agent to explore
IR (RND) instead of tabular IR could potentially alleviate this issue, but it is often far less than enough in complex environments.
As mentioned in Go-Explore series (Ecoffet et al., 2019; 2020), count- based approaches also suffer from detachment: if the agent by chance starts exploring 72 after briefly exploring the first few states of 71, it would not return and explore Ti further since T₁ is now "shorter" than 72 and has lower IR than for long period. Go-Explore tries to resolve this dilemma between "dedication" and "exploration" by using a two-stage approach with many hand-tuned parameters.
In contrast, IR of BeBold depends on the difference of the visitation counts along the trajectory. and is insensitive to the length of the corridor. This leads to simultaneuus exploration of multiple corridors and yields a diverse policy π (See Sec. 5.2 for empirical evidence). Moreover, the IR focuses on the boundary between explored and unexplored regions, where the two goals (dedication and exploration) align. yielding a much cleaner, one-stage method.
Asymptotic Inconsistency. Approaches that define IR as the difference between state representa- tions [|+)(s) *b(s)]l (t) is learned embedding network) (Zhang et al., 2019; Marino et al., 2019) suffer from asymptotic inconsistency. In other words, their IR does not vanish even after sufficient exploration: r' ب 0 when N + 0o. This is because when the embedding network & converges after sufficient exploration, the agent can always obtain non-zero IR if a major change in state represen- tation occurs (e.g.. opening door or picking up a key in MiniGrid). Therefore, the learned policy does not maximize the extrinsic reward re, deviating from the goal of RL. Automatic curriculum approaches (Campero et al., 2020)) have similar issues due to an ever-present IR.
For this, (Zhang et al., 2019) proposes learn separate scheduler switch between intrinsic and extrinsic rewards, and (Raileanu and Rocktäschel, 2020) divides the state representation difference by the square root of visitation counts. In comparison, BeBold does not require any extra stage and is a much simpler solution.
EXPERIMENTS
We evaluate BeBold on challenging procedurally-genenaa environment MiniGrid (Chevalier- Boisvert et al., 2018) and the hard-exploration environment NetHack (Küttler et al., 2020). These environments provide a good testbed for exploration in RL since the observations are symbolic rather than raw sensor input (e.g., visual input), which decouples perception from exploration. In MiniGrid, we compare BeBold with RND (Burda et al., 2018b), ICM (Pathak et al., 2017), RIDE (Raileanu and Rocktäschel, 2020) and AMIGo (Campero et al., 2020). We only evaluate AMIGo for 120M steps in our experiments, the algorithm obtains better results when trained for 500M steps as shown in (Campero et al., 2020). For all the other baselines, we follow the exact training paradigm from (Raileanu and Rocktäschel, 2020). Mean and standard deviation across four runs of different seeds are computed. BeBold successfully solves the 12 most challenging environments provided by Min- iGrid. By contrast, all the basclines end up with zero reward on half of the environments tested. In NetHack, BeBold also achieves SoTA results with a large margin over baselines.
5.1 MINIGRID ENVIRONMENTS
We mainly use three challenging environments from MiniGird: Multi-Room (MR), Key Corridor (KC) and Obstructed Maze (OM). We use these abbreviations for the remaining of the paper (e.g.. OM2D1h stands for ObstructedMaze2DDih)) Fig. 2 shows one example of a rendering on OMFull as well as all the environments we tested with their relative difficulty.
In MiniGrid, all the environments are size N X N (N is environment-speccffe where each tile contains an object: wall, door, key, ball, chest. The action space is defined as turn left, turn right, move forward, pick up an object, drop an object, and toggle an object (e.g., open or close a door). MR consists of a series of rooms connected by doors and the agent must open the 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.
4

---

Under review as a conference paper at ICLR 2021
510
ICM
RMO
Aputt
AMGO
Solved wiriin 12BM staps
"MRle for Nubilteen KCla Comida,,, OM Obitnucuciie
Figure 2: MiniGrid Environments. Left: pnweedurally-geeennae OMFull environment. Right: BeBold solves challenging tasks which previous approaches cannot solve. Note that evaluate all methods for 120M steps. AMIGo gets better results when trained for 500M steps as shown in (Campero al., 2020).
NAAIA
Play Bitaeernn. Ad
Bayy Mulliooess
Pray Ne
Palay CepCanians
3.2
18
26
3xt
167
367
1et
1.0
Mecium KoyComieddess
16
Medum 1o
10
Mesum KnCombeetees
1.
Moduure Chdmnciseeett
0.0
08
00
0.0
Aoiagg 0.5
0.6
0.0
Entorment Stons
167
Envirnmentt Steas
147
Diverment Steps
Cnviomment Slea
Figure 3: Results for various hard exploration environments from MiniGrid. BeBold successfully solves all the environments while all other baselines only manage to solve two three relatively easy ones.
Results. We test BeBold on all environments from MiniGrid. BeBold manages to solve the 12 most challenging environments. By contrast, all baselines solve only up medium-level tasks and fail to make any progress on more difficult ones. Note that some medium-level tasks we define here are categorized hard tasks in RIDE and AMIGo (e.g., 4R3 is labeled as "KCHard" and KCS5R3 labeled as "KCHarder"). Fig. 3 shows the results of our experiments. Half of the environments (e.g., KCS6R3 OM1 Q) are extremely hard and all the baselines fail. In contrast, BeBold easily solves all such environments listed above without any curriculum learning. We also provide the final testing performance for BeBold in Tab. 1. The results is averaged across 4 seeds and 32 random initialized environments.
Multi Room environments are relatively easy in MiniGrid. However, all the baselines except RIDE fail. As we increase the room size and number (e.g.. MRN1 2510). BeBold can achieve the goal quicker than RIDE. Our method casily solves these environments within 20M environment steps.
On Key Corridor environments, RND, AMIGo, RIDE, IMPALA and BeBold successfully solves KCS3R3 while ICM makes reasonable progress. However, when we increase the room size (e.g., KCS5R3), none of the baseline methods work. BeBold manages to solve these environments in 40M environment steps. The agent demonstrates the ability explore the room and finds the correspond- sorodduurall-ggeertttee environment.
ing key to open the door in a randomized,
Obstructed Maze environments are also difficult. As shown in Fig. 3, RIDE and RND manage to solve the easiest task OM2D1h which doesn't contain any obstructions. contrast, BeBold not only rapidly solves OM2D1h, but also solves four more challenging environments including OMF ull. 1. These environments have obstructions blocking the door (as shown in Fig. and are much larger in size than OM2D h. In these environments, our agent learns to move the obstruction away from the door open the door and enter the next room. This "skill" is hard to learn since there no extrinsic reward assigned to moving the obstruction. However, learning the skill critical to achieve the goal.
5

---

Under review as a conference paper at ICLR 2021
Table 1: Final testing performance for BeBold and all baselines.
MRN6
MRN7S8
MRN12810
KCS3R3
KCS4R3
KCS5R3
ICM
0.00 + 0.0
0.00 + 0.0
0.00 + 0.0
0.45 + 0.052
0.00 + 0.0
0.00 + 0.0
RIDE
0.005
0.001
0.002
0.003
0.002
0.00 0.0
RND
0.00 0.0
0.00 + 0.0
0.00 + 0.0
0.91 + 0.003
0.00 + 0.0
0.00 + 0.0
IMPALA
0.00
0.00
0.004
0.0
AMIGO
0.0
0.00 0.0
0.00 0.0
0.89 = 0.005
0.00 + 0.0
0.00 0.0
BeBold
0.64 = 0.003
0.67 = 0.001
0,65 = 0.002
0,92 0.003
= 0.003
+ 0.001
KCS6R3
OM2Dih
OM2Dlbb
OMIQ
OM2Q
OMFULL
ICM
0.00 0.0
0,00 0:00::000
0,00 0.0
0.00 = 0.0
0.00 0.0
0.0
0.015
0.00
0.00 0,00=000
0.0
RND
0.00++0.0
0.95 + 0.0066
1.00+00.0
0.00 0.0
0.00 + 0.0
0.00+-00
IMPALA
0.00
AMIGO
0.0
0.00 = 0.0
0,00 : 0.0
0.00 = 0.0
0.00 0.0
0.00 0.0
BeBold
0,94
0.005
0.89 0.063
0.067
0.93
0.96 0.058
RND
yo
24M
Bebuld
MuluhoomkISSS
Reamil
Figure 4: Normalized visitation counts (s.)) / (Z a normalization constant) the location of agents.
BeBold successfully explores all rooms at 4.6M steps while RND gets stuck in the fifth room at 9.8M steps.
5.2 ANALYSIS OF INTRINSIC REWARD USING PURE EXPLORATION
We analyze how BeBold mitigates the short-sightednnss issue by only using IR to guide exploration.
Shorted-Sighted Problem in Long-Corridor Environment. To verify Sec. 4, design toy environment with four disconnected corridors with length 40, 10, 30, and 10 respectively starting from the same state. In this example, there is extrinsic reward and the exploration of the agent guided by IR. We combine Q-learning with tabular IR (count-based and BeBold tabular) and approxiaapp IR (RND and BeBold) respectively for this experiment. We remove clipping from BeBold for fair comparison. Tab. shows the visitation counts across 4 runs w.r.t. each corridor after 600 episodes of training. in much more uniform manner. On the other hand, count-based approaches are greatly affected by short-sightedness and focus only on two out of four corridors. BeBold also shows much more stable performance across runs as the standard deviation is much lower comparing with RND. Note that comparing to the analysis in Sec, in practical experiments, we perceive that the preference of the corridors for count-batt based methods can be arbitrary because of the random initialization of the Q-network.
clear that BeBold tabular explores each corridor
Visitation Counts Analysis in MiniGrid. To study how different intrinsic rewards can affect the exploration of the agent, test BeBold and RND in fixed (instead of procedurally simplicity) MRN7S8 environment. The environment contains rooms connected by doors. successful exploration strategy, the agent should explore all states and give all states equal amount of exploration. We define two metrics measure the effectiveness of an exploration strategy: (1) visitation counts at every state over training (s). and (2) entropy of visitation counts in each room: H(p((s)) where p'(s)
for
Eess, (Ns)). We do not calculate entropy across all states, because the agent always starts in the first room and may not visit the last one as frequently. As result, the visitation counts for states in the first room will be several magnitudes larger than the last room.
((s).
Fig. shows the heatmap of normalizd visitation counts [Zs;)/Z, where Z is the normalization constant. At first, RND enters the second room faster than BeBold. However, BeBold consistently makes progress by pushing the frontier of exploration and discovers all the rooms in 5M steps, while RND gets stuck in the fifth room even trained with 10M steps.
In Tab. the entropy distribution in each room H((p(ss) for BeBold is larger than that of RND. This suggests that BeBold encourages the agent to explore the state in much more uniform manner.

---

Under review as a conference paper at ICLR 2021
Table 2: Visitation counts for the toy corridor environment after 3K episodes. BeBold explores corridors more uniformly than count-based approaches.
Table 3: Entropy of the visitation counts of each room. Such state distribution of Be- Bold much more uniform than RND.
0.3M
20M
5.0M
Estrog
3.84/554
341/353
5.51
3.59/3.5
Leughs
Room2
339/323
/
3.55
9K
138 19K
1. D.
-14.02
3.42/4.01
Room4
-12.74
2
RND
Bellave
0.K
27K
1 6X
N0K 1 238 1K
0:K LOOK
TIK 12K
MK
28R MK
136 1 BJIS
Resilts presented order of "RND) BeRold"
LCW
c Man
Figure 5: IR heatmaps for the location of agents. BeBold mitigates the short- sighted problem.
RMD
AND with ERIR
Bello EAIR
BeBrM Cigerg
1,4
GoyLstrizees4e
1.0
<eyCamiaes5k3
MUAiHoom M7 se
Muii Racim RU12 Si5
0.8
0.5
0.4
0.4
3.4
0.4
0.0
0.0
0.0
0.5
1.0
3.5
2.0
0.0
2.5
1.0
15 Strpe
2.0
Steps
Figure 6: Ablation Study on BeBold comparing with RND with episodic intrinsic reward. BeBold significantly outperforms RND with episodic intrinsic reward on all the environments.
Intrinsic Reward Heatmap Analysis in MiniGrid. We also plot the heatmap of IR at different training steps. 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 are left blank. For BeBold, the IR is computed as the difference of inverse visitation counts (approximated by RND) between consecutive states s; and St+1 in the trajectory. From Fig. 5, we can see that BeBold doesn't suffer from short-sighted problem, as we can clearly see that the areas with high IRs are continuously pushed forward from room] to room7. This is true of the whole training process. On the contrary, the IR heatmap for RND bounces between two consecutive rooms. This is due to sightedigtt when exploring the second room, the IR of that room will significantly decrease. Since (a) the policy has assigned the first room non-zero probability and (b) the first room now has lower vistation count, RND will revisit the first room. This continues indefinitely, the agent oscillates between the rooms.
5.3 ABLATION STUDY
Episodic Restriction on Intrinsic Reward. We analyze the importance of each component in BeBold. To illustrate the importance of exploring beyond the boundary, we compare BeBold with slightly modified RND: RND with ERIR. We only give RND intrinsic reward when it visits new state for the first time in episode. We can in Fig. 6 that although ERIR helps RND to solve KCS4R3 and MRN7S8, without BeBold, the method still fails on more challenging tasks KCS5R3 and MRN1 251 0. A symmetric experiment of removing ERIR from BeBold is also conducted.
Clipping in Beyond the Boundary Exploration. We also study the role of clipping max(-, 0) in our method. Fig. 6 shows the effect of removing clipping from BeBold. We conclude it is suboptimal to design an IR that incurs negative reward when transitioning from unfamiliar to familiar state.
5.4 THE NETHACK LEARNING ENVIRONMENT
To evaluate BeBold on a more challenging and realistic environment, we choose the NetHack Learn- ing Environment (Küttler et al., 2020). In the game, the player is assigned role of hero at the beginning of the game. The player needs to descend over 50 procedurally-generaa bottom and find "Amulet of Yendor" in the dungeon. The procedure can be described as first retrieve
levels to the
7

---

Under review as a conference paper at ICLR 2021
PIYLA
RB0
Buboid
1.0
2.0
0.2
6.4
6.6
6.3
1-3
0.2
0.4
0.6
6.8
1.5
0.0
02
3.6
3.0
20
2000
2.0
Avtraga Katze
1500
200
1000
200
440
0.6
Figure 7: Results for tasks on NetHack. BeBold achieves the SoTA results comparing to RND and IMPALA.
the amulet, then escape the dungeon and finally unlock five challenging levels (the four Elemental Planes and the Astral Plane). We test BeBold on a set of tasks with tractable subgoals in the game: Staircase: navigating to staircase the next level, Pet: reaching staircase and keeping the pet alive, Guld: collecting gold, Score: maximizing the score in the game, Scout: scouting to explore unseen areas in the environment, and Oracle: finding the oracle (an -aga character at level 5-9).
Results in Fig. 7 show that BeBold surpasses RND and IMPALA on all tasks' Especially on Pet, BeBold outperforms the other two with a huge margin. This again illustrates the strong performance of BeBold in an environment with huge action spaces and long-horizon reward (several magnituees longer than StarCraft and Dota2). Oracle is the hardest task and no approaches are able to find the oracle and obtain a reward of 1000. BeBold still manages to find policy with less negative rewards (i.e.. penalty of taking actions that do not lead to game advancement, like moving towards a wall). For RIDE, we contacted the authors, who confirmed their method is not functional on NetHack. We further attempted to tune RIDE but to no avail. So we do not report RIDE performance on NetHack.
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 to explore areas where the prediction of the next state from the current learned dynamical model is wrong. Dynamic- AE (Stadie al., 2015) computes the distance between the predicted and the real state on the output of an autoencoder, ICM (Pathak et al., 2017) learns the state representation through a forward and inverse model and EMI (Kim al., 2018) computes the representation through maximizng mutual information Z[[s, s') and ())))
Another line of research is using information gain to reward the agent. VIME (Houthooft et al., 2016) uses a Bayesian network to measure the uncertainty of the learned model. Later, to reduce computation, a deterministic approach has been adopted (Achiam and Sastry, 2017). Other works also propose to use ensemble of networks for measuring uncertainty (Pathak et al., 2019; Shyam et al., 2019). We can also reward the agent by Empowerment (Klyubin et al., 2005; Gregor et al., 2016; Salge et al., 2014; Mohamed and Rezende, 2015), prioritizing the states that agent can take control through its actions. It is different from state-diff: if S differs from s, but nor due to agent's choice of actions, then the empowerment at S; is zero Other criteria exist, e.g., diversity (Eysenbach et al., 2018), feature control (Jaderberg et al., 2016; Dilokthanakul et al., 2019) or the KL divergence between current distribution over states and a target distribution of states (Lee et al., 2019).
Outside of intrinsic reward, researchers have proposed to use randomized value functions to encour- age exploration (Osband et al., 2016; Hessel et al., 2017; Osband et al., 2019). Adding noise to the network is also shown be effective (Fortunato et al., 2017: Plappert et al., 2017). There has also been effort putting to either explicitly or implicitly separate exploration and exploitation (Colas et al., 2018; Forestier et al., 2017; Levine et al., 2016). The recently proposed Go-Explore series (Ecoffet et al., 2019; 2020) also fall in this category. We might also set up different goals for exploration (Guo and Brunskill, 2019; Oh et al., 2018; Andrychowicz et al., 2017).
Curriculum learning (Bengio et al., 2009) has also been used to solve hard exploration environments. The curriculum can be explicitly generated by: searching the space (Schmidhuber, 2013), teacher-
'For Gold task, there is small fix introduced to the environment recently. We benchmark all methods hefore the fix and will update the results.
8

---

Under review as a conference paper at ICLR 2021
Revense
Reccoge
13000
Keerygo Aotum
AND
6000
4000
2005-
2000
Fnvirommett
100
Figure 8: Results for CNN-based and model on MonteZuma's Revenge. BeBold achieves good performance.
student setting (Matiisen et al., 2019), increasing distance between the starting point and goal (Jabri et al., 2019) using density model to generate task distribution for the meta learner (Florensa et al., 2017). Our work can also viewed as an implicit curriculum learning as gradually encourages the agent to expand the area of exploration. However, it never explicitly generates curriculum.
MONTEZUMA" REVENGE
We also provide initial result of BeBold on MonteZuma's Revenge. We same paradigm as RND and the same of hyperparameters except using CNN-based model, BeBold achieves approximately 10000 external reward after two Billion frames while the performance reported in RND (Burda et al., 2018b) is around 6700. When using RNN-baed model, BeBold reached around 13000 external reward 100K updates while RND only achieves 4400. Please note that these are only initial result and we'l 'lll provide the comparison with RND and average return across multiple seeds in the future.
128 parallel environments. In Fig. 8, we can see that
8 LIMITATIONS AND FUTURE WORK
Noisy TV Problem. One of the limitations on BeBold the well-known Noisy TV problem. The problem was raised by (Pathak et al., 2017): the agent trained using a count-based IR will get attracted local sources of entropy in the environment. Thus, will get high IR due to the random- ness in the environment even without making any movements. BeBold suffers from this problem well since the difference between consecutive states be caused by the stochasity in the envi- ronment. That could the reason that BeBold doesn't get a good performance on stochastic tasks (e.g., Dynami cattamic-obstee Obs-talesees 5x5). We will leave this problem to future research.
Hash Table for ERIR. The ERIR BeBold adopts hash table for episodic visitation count. This could potentially have hard time when applying BeBold in a continuous space environment (e.g., some robotics tasks). One simple solution to discretilize the space and still use hash table for counting. We also leave the more general and elegant fix to this problem to future work.
CONCLUSION
In this work, we propose a new criterion for intrinsic reward (IR) that encourages exploration be- yond the boundary of explored regions using regulated difference of inverse visitation count along a trajectory. Based on this criterion, the proposed algorithm BeBold successfully solves 12 of the most challenging tasks in procedurally-generaa provement over the previous SoTA, overcoming short-sightedness issues that plague count-based exploration. We also evaluate BeBold on NetHack, a much more challenging environment. BeBold outperforms all the baselines by significant margin. summary, this simple criterion and the en- suing algorithm demonstrates effectiveness in solving the sparse reward problem in reinforcement learning (RL), opening up opportunities to many real-world applications.
MiniGrid environment. This is a significant im-

---

Under review as a conference paper at ICLR 2021
REFERENCES
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-555 2015.
Adria Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. arXiv preprint ar arXiv: 13330000000 2020a.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-3344 2019,
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, 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-355 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140- 1144, 2018.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: 01.66.01555 540, 2016.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-511 2017.
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.
Jürgen Schmidhuber. Formal theory of creativity. fun, and intrinsic motivation (1990-2010). IEEE
Transactions on Autonomous Mental Development, 2(3):230-247, 2010.
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.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexci A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv: 04355, 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey and Oleg Klimov. Exploration by random network distillation. arXiv preprint 1xXiv:8100.18880 2018b.
Georg Ostrovski, Mare G Bellemare, Aaron van den Oord, and Rémi Munos. Count- based explo- ration with neural density models. arXiv preprint 17X3v:1703.0133 2017.
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, 2020b.
Jingwei Zhang, Niklas Wetzel, Nicolai Dorka, Joschka Boedecker, and Wolfram Burgard. Sched- uled intrinsic drive: A hierarchical take on intrinsically motivated exploration. arXiv preprint arXiv:/903.0740 /903007400 2019.
Kenneth Marino, Abhinav Gupta, Rob Fergus, and Arthur Szlam. Hierarchical RL using an ensem- ble of proprioceptive periodic policies. In International Conference on Learning Representations, 2019. URL https: wpwpreeewweeeeeee//// net d
10

---

Under review as a conference paper at ICLR 2021
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: new approach for hard-exploration problems. urXiv preprint /0t:::990..1000 2019.
Maxime thevalier-Boisvent Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: githt...hb....o.eg com/
cwm/max max http://wmmembbaaaamnnnr...... 2018.
Heinrich Küttler. Nantas Nardelli, Alexander H Miller, Roberta Raileanu, Marco Selvatici, Ed- ward Grefenstette, and Tim Rocktäschel. The nethack learning environment. arXiv preprint arXiv:2006. 13760, 2020.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally-generete environments. arXiv preprint 2rX1v:2002.12292, 2020.
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 arXiv:2006. 12122, 2020.
Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle. Yoshua Bengio, and Sergey Levine. Infobot: Transfer and exploration via the formation bottleneck. arXiv preprint arXiv:1901. 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return then explore. arXiv preprint arXiv:2004. 12919, 2020.
Brian Yamauchi. A frontier-based approach for autonomous exploration. In Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA 197. 'Towards New Computational Principles for Robotics and Automation's pages 146-151. IEEE, 1997.
Brian Yamauchi. Frontier-based exploration using multiple robots. Proceedings of the second international conference on Autonomous agents, pages 47-53, 1998.
Anirudh Topiwala, Pranav Inani, and Abhishek Kathpal. Frontier based exploration for autonomous robot. arXiv preprini arXiv:1806. 03581, 2018.
Bradly Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint 15070005 2015.
Hyoungseok Kim, Jaekyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Ex- ploration with mutual information. arXiv preprint a1X.v:1810.01176. 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, pages 1109-111 2016
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning, arXiv preprint wrXiv:1703.0173: 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. arXiv preprint arXiv: 1rXiv:190.004161 2019.
Pranav Shyam, Wojciech Jaskowski, and Faustino Gomez. Model-based active exploration. In International Conference Machine Learning, pages 5779-5788, 2019.
Alexander S Klyubin, Daniel Polani, and Chrystopher L Nehaniv. All clse being equal be empow- cred. European Conference on Artificial Life, pages 744-753. Springer, 2005.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:161 1.07507, 2016.
Christoph Salge, Cornelius Glackin, and Daniel Polani. Empowerment-an introduction. In Guided Self-Organd Organizaaaz Inception, pages 67-114. Springer, 2014.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. In Advances in neural information processing systems, pages 2125-2133, 2015.
11

---

Under review as a conference paper at ICLR 2021
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint urXiv: 180200607, 2018.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint (tt:://11.00999 2016.
Nat Dilokthanakul, Christos Kaplanis, Nick Pawlowski, and Murray Shanahan. Feature control as intrinsic motivation for hierarchical reinforeement learning. IEEE transactions on neural net- works and learning systems, (M(11):349--444 2019.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdi- nov. Efficient exploration via state marginal matching. arXiv preprint arXiv:1906 05274, 2019,
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pages 4026-4034, 2016.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. arXiv preprint arXiv:1710.02298. 2017.
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20( 1-2, 2019.
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 preprini arXiv: 1706. 10295, 2017.
Matthias Plappert. Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marein Andrychowicz. Parameter space noise for exploration. arXiv preprint arXiv: 7766009055. 2017.
Cédric Colas, Olivier Sigaud, and Pierre-Y Yves Oudeyer. Gep-pg: Decoupling exploration and ex- ploitation in deep reinforcement learning algorithmss. arXiv preprint arXiv:1802.05053. 2018.
Sébastien Forestier, Yoan Mollard, and Pierre-Yves Oudeyer. Intrinsically motivated goal explo- ration processes with automatic curriculum learning. arXiv preprint arXiv:1708.00 021900 2017.
Sergey Levine. Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. The Journal of Machine Leurning Research, 17(1):1334-133, 2016.
Zhaohan Daniel Guo and Emma Brunskill. Directed exploration for reinforcement learning. arXiv preprint arXiv:1906.07800 2019.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. arXiv preprint 1rXi::/806.05635.. 2018
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience play. In Advances in neural information processing systems, pages 5048-5058, 2017.
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.
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.
Tambet Matisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learn- ing. IEEE transactions on neural networks and learning systems. 2019.
Allan Jabri, Kyle Hsu, Abhishek Gupta, Ben Eysenbach, Sergey Levine, and Chelsea Finn. Un- supervised curricula for visual meta-reinforcement learning. In Advances in Neural Information Processing Systems, pages 10519-10531, 2019.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse cur- 2017.
riculum generation for reinforcement learning. arXiv preprint
12

---

Under review as a conference paper at ICLR 2021
A SOME ANALYSIS BETWEEN COUNT-BASED APPROACHES AND OUR APPROACH
Consider two corridors. left and right. The left corridor has length Ti while the right corridor has length T,. Both starts with an initial state 8n- When the game starts, the agent was always placed 80-
For simplicity, we just assume there is only binary action (left or right) to be chosen at the starting point 8p. after that the agent just moves all the way to the end of the corridor and the game restarts. And we set the discount factor = 1.
Using count-based approach, the accumulated intrinsic reward received by the agent if moving to the left corridor for the i-th time is R; :- Ti/i. This is because for each state, the first time the agent visit it, it gets reward of and the second time it gets reward of 1/2, etc. And this is true for every state in this corridor. Similarly, for i-th time moving right, it is R, == T//i.
Now let's think how the policy of the agent is trained. In general, the probability to take action left or right is proportional of the past reward due to the update rule ((s, a) < (1 (1-10)00 (Q)(( 0.01). If we think about Q learning starting with (s0, left) ( right) 0, and consider the situation when the agent has already done ny left and ny right actions, then we have:
the accumulated reward. In Q learning it is an exponential moving average
+ aRR for typically small (e.g.,
Q(50, = Tia
(4)
Similarly, we have
(1 - a))
(S0, right) T,a
(5)
t=1
= We could define <(n) := a >i (1-a)=-1 and thus (ss,, left) = Tiő(n,) and (so,, right) (n,(
If we treat ((-) as function in the real domain, and assign visiting probability m(a)s)) x Q(80; a), then the visitation counts, now is denoted as xy and Hr since they are continuous, for left and right satisfies the following differential equations:
Ti((s))
TイΦ(xr) 4, = TiO(I;) T,
1 Tiő(II) +T,OE,,)
(6)
In the following, we will show that if Ti # T,, long corridor will dominate the exploration since has lot of rewards until very late. Suppose (0) = (0) has longer corridor than right side. Then from the equations, very quickly x >> Zy. For a close to O, we could check that o(r) is monotonously increasing function when is small positive number, since the more an agent visits a corridor, the more reward it obtains. So this creates a positive feedback and the growth of zz dominates, which means that the policy will almost always visit left. This happens until after z4 is large enough and ((x1) starts to decay because of diminishing new rewards and the training discount a. The decay is on the order of like 1 then the agent will 2,
and Ti T,, that is. left side
finally start to visit the right side. Indeed, (right(/s)) > 50% if T,a > Ti/21, or > comparison, if we pick sides in uniform random manner, when zj is this big, I, should also be comparable (while here H, can be as small or 2).
T: 1 In T,
If an agent have K corridors to pick with Tı > T2 >... Tk. things will be similar.
When Ti = T,,, the dynamics is perfectly symmetric and the agent visits both left and right with 1/2 probability. Since this symmetry quite rare, count-hased exploration is often biased towards one or two corridors (See Thl. 2), BeBold uses difference of inverse visitation counts as intrinsic rewards, and thus balance the exploration.
B HYPERPARAMETERS FOR MINIGRID
Following (Campero et al., 2020), we use the same hyperparameters for all the baselines. For ICM, RND, IMPALA, RIDE and BeBold, we the learning rate 10-1, batch size 32, unroll
13

---

Under review as a conference paper at ICLR 2021
1.M
3.34
5.2M
3.M
Debold
Figure 9: On policy state density heatmaps Pa (s:). BeBold continuously pushes the frontier of exploration from Rooml to Room7.
length 100, RMSProp optimizer with 0.01 and momentum O.
We also sweep the hyperpa- rameters for BeBold: entropy coefficient (0.0001, 0.0005, 0.001 and intrinsic reward coefficient {0.01, 0.05, 0.13. We list the best hyperparameters for each method below.
BeBold. For all the Obstructed Maze series environments, and the intrinsic reward coefficient of 0.05. For all the other environments, we use the entropy coefficient of 0.0005 and the intrinsic reward coefficient of 1. For the hash table used in ERIR, take the raw inputs and directly use that as the key for visitation counts.
the entropy coefficient of 0.0005
AMIGo. As mentioned in (Campero et al., 2020), we use batch size of 8 for student agent and batch size of 150 for teacher agent. For learning rate, we use learning rate of 0.001 for student agent and learning rate of 0.001 for teacher agent. We use an unroll length of 100, entropy cost of 0.0005 for student agent and entropy of 0.01 for teacher agent. Lastly we use 0.7 and 0.3 for defining IRs in AMIGo.
RIDE. Following (Raileanu and Rocktäschel, 2020), we use entropy coefficient of 0.0005 and intrinsic reward coefficient for key corridor series of environments. For all other environments, we use entropy coefficient of 0.001 and intrinsic reward coefficient of 0.5.
RND. Following (Campero et al., 2020), we use entropy coefficient of 0.0005 and intrinsic reward coefficient of 0.1 for all the environments.
ICM. Following (Campero al., 2020), use entropy coefficient of 0.0005 and intrinsic reward coefficient of 0.1 for all the environments.
IMPALA. We use the hyperparameters introduced in first paragraph of this section for the baseline.
C ANALYSIS FOR MINIGRID
In addition to the analysis provided before, we also conduct some other analysis of BeBold in Min- iGrid.
On Policy State Density in MiniGrid We also plot the on policy state density P* (*(s) for different checkpoint of BeBold. We ran the policy for 2K steps and plot the BeBold IR based on the con- secutive states in the trajectory. In Fig. we can clearly see that the boundary of explored region is moving forward from Rooml 1 to Room7. It is also worth noting that although the policy focuses on exploring one room (one major direction to the boundary.) at time, also put a reasonable amount of effort visiting the previous room (other directions of to the boundary). Thus, BeBold greatly alleviate the sigrt-sighted problem aforementioned.
D RESULTS FOR ALL STATIC ENVIRONMENTS IN MINIGRID
In addition the results shown above, we also test BeBold on all the static producedurally-genee generrted environments in MiniGrid. There are other categories of static environment. Results for BeBold and all other baselines shown in Fig. 10 and Fig. 11.
14

---

Under review as a conference paper at ICLR 2021
Empry (E) These the simple ones in MiniGrid. The agent needs search in the and find the goal position. The initial position
agent and goal can random.
Four Rooms (FR) In the environment, the agent need to navigate in maze composed of four rooms. The position of the agent and goal is randomized.
Door Key (DK) The agent needs to pick up the key, open the door and get to the goal. The reward is sparse in such environment.
Red and Blue Doors (RBD) this environment, the agent randomly placed in a room. There are one red and one blue door facing opposite directions and the agent has to open the red door then the blue door in order. The agent cannot see the door behind him it needs to remember whether or not he has previously opened the other door in order to reliably succeed at completing the task.
Lava Gap (LG) The agent has to reach the goal (green square) at the corner of the room. It must pass through a narrow gap in a vertical strip of deadly lava. Touching the lava terminate the episode with zero reward.
Lava Crossing (LC) The agent has to reach the goal (green square) at the corner of the room. must pass through some narrow gap in a vertical/horizontal strip of deadly lava. Touching the lava terminate the episode with a zero reward.
Simple CrOssing (SC) The agent has to reach the goal (green square) on the other corner of the room, there are several walls placed in the environment.
E HYPERPARAMETER FOR NETHACK
For general hyperparameters, we use optimizer RMSProp with a learning rate of 0.0002. No mo- mentum is used and we scale the the forward distillation loss by a factor of 0.01 to slow down training. We adopt the intrinsic reward coefficient of 100. For the hash table used in ERIR, take several related infor- mation (e.g., the position the agent and the level the agent is in) provided by (Küttler al., 2020) and use that as the key for visitation counts.
e 0.000001. The entropy cost set 0.0001. For RND and BeBold,
15

---

Under review as a conference paper at ICLR 2021
MiniGrid Empoy-5X3 vo
MinGGris Empty RXn vo
Miniörid Empty vo
MinGGnd Empty Random exs
1.0
10
1.0
1.0
Novenge Bartin
Nurenge Return
0.6
0.6
0.5
0.6
0.0
0.0
0.0
0.0
Enstronment 107
Enxtroment Steas
Envtronmett
167
Enstronment Steps
1.0
1.0
0.8
0.8
0.8
0.8
Novegge Reetmm
Noenpe Return
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
2
Enutrnnmmnn Steps
Endrroment Steps
Invtremment Steps
Endrroment Steps
MiniGrid--eee Door Ney-456--0
Ni-iür Deor
NisGrisuukk Minori-Aukllooom422---2 (2000
1.0
1.0
Koeege Berumr
Noenge Beturn
0.6
0.6
0.5
0.6
Mecrage
Mecrage
0.4
0.4
0.0
0.
0.0
0.0
Enstronment Staps 167
Endtromment Sleak
107
Environmment Steps
1c7
Endtronment Stwpps
307
MinGridRReD
0.8
0.8
0.8
0.8
Avverge Ramum
Aueenge Return
04-
0.1
04
0.4
0.2
0.2
0.2
0.2
3
Environmentt
Environment Staps
Envirenment Slegs
Environment Staps
WiniGrid KayCar MorS33
Minkörid Unioc--v
MinG-i UnlockHcckpp v0
Miniörid BicckednnccPPPuuee. yo
1.0
1.0
1.0
1.0
Auvenge Bartin
Jueenge Retum
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.0
0.
0.0
0.0
Environment Staps 167
Envirenment Stads
167
Environment Staps
167
Endrronment Staps 167
IMPALA
AND
RIDE
AMIGO
Belold
Figure 10: Results for BeBold Part and all baselines on all static tasks.
16

---

Under review as a conference paper at ICLR 2021
MrC-i-Gatttre-eeee 10
MinkGri- Oww.raattttttreeeeeeeee 10hob
MrvGridchhencteekeeer 201vv0
1.0
1.0
1.0
1.0
0.8
9.5
lvergge
Burerge
0.4
0.4
0.4
0.4
0.0
0.0
0.0
0.0
Environment Staps 167
Ensironmentttpp Stops
167
Enviooment Stups
1c7
Environment Staps 167
MiniGrid
MinGdd Dis5kit22
MinGddd Lava6ae55
MinlGrdd LavoGap55
0.8
0.5
0.8
0.8
Averige Sentum
Areraga Return
0.6
0.4
0.2
0.2
0.2
0.2
Enstronmmett Steps
Enstronment Steps
Enwionment Steps
Environment Steps
Minitr Sa
MiriGrid Menicii-LanraCCoo LaraalraCCCCaaa mg
Nintür wlw.aeantttiiiiiiiiiii.....
1.3
1.0
Koenge Barurn
Nourage Rotum
0.6
0.5
6.66
2.6
0.4
0.4
0.2
0.0
0.3
0.0
0.0
Environment Steps 167
Enstronment
167
Envionment
1:7
Envifooment
167
0.8
0.8
0.8
0.8
Avvenge Renurm
Auczgg Return
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
Enufronmmntt Steps
EntronmentStepp Stops
Eniionmeent Steps
Etvironment Stops
0.5
Average
0.0
Ensfronment Steps 167
IMPALA
KM
AND
RIDE
AMIGO
BcBoid
Figure 11: Results for BeBold Part 2 and all baselines on all static tasks.
17


Reviews:
[{"review_id": "pQkE-Uw2aIn", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "------------------------------------        \n**Summary:**\n\nThis paper proposes BeBold, a new definition of intrinsic reward to guide exploration in sparse reward problems. This intrinsic reward combines the ideas behind count-based approaches and state-diff approaches. They demonstrate the success of BeBold by comparing their algorithm to a set of state-of-the-art exploration methods using intrinsic rewards on a set of tasks from the MiniGrid and NetHack environments.\n\n------------------------------------        \n**Strong points:**\n\nOverall, I believe this is a very good paper. The idea is simple, the motivations and intuitions are well explained. The empirical study is carefully designed, involves relevant baselines and environments. The paper is also well written. I will list the main strong points:\n* The problem of exploration in sparse environments is an important problem in the field of RL. Many exploration problems have been defined (detachment, short-sightedness, etc.). This paper presents these problems and proposes to improve on some of them.\n* The paper is clearly written and well organized.\n* The related work is relevant and seems complete.\n* The experiments are overall well designed. MiniGrid and Nethack are two types of benchmarks adapted to the study of exploration algorithms and the baselines are relevant. I like that the authors conducted ablations studies and additional experiments to study specific aspects of their strategy (visitation counts analysis and the study of the short-sighted problem).\n* The new methods seem to significantly outperform previous ones without being overly complicated. The empirical evidence supports the claim (although I have a problem with the use of “solve” here, see below).\n\n------------------------------------        \n**Weak points:**\n\nI will now list a few weak points of the paper.\n* The paper lists various exploration problems (noisy TV problem, detachment, derailment, short-sightedness and asymptotically inconsistent). BeBold is said to solve detachment, short-sightedness and asymptotical inconsistency. Derailment and the noisy TV problem are neither defined nor discussed. I believe BeBold does not solve the noisy TV problem, it should be discussed.\n* I am not sure I get the intuition behind the clipping of the reward function. The authors write: “we do not want to give a negative IR to the agent if it transits back from a novel state to a familiar state”, but do not really explain why. Can you make this explicit?\n* Episodic restriction seems to restrict the use of BeBold to environments with discrete countable states (use of hash table). Do you see a way around that problem? \n* I think the main problem is the total absence of discussion w.r.t. the potential limits of BeBold (there is no discussion section). In particular, the authors could discuss the aspects mentioned above: the limitation to discrete states, the noisy TV and derailment problems. \n* Comparison to Go-Explore: Talking about BeBold, the paper says: “without using domain knowledge (e.g., image downsampling like in Go-Explore (Ecoffet et al., 2019)). It is true that BeBold does not use image downsampling, but it does not use images at all, which is probably the explanation. Go-Explore and RND can be applied to image-based environments like Montezuma’s revenge. To do so, Go-Explore indeed requires downsampling. However, I believe that if BeBold were to be applied to such environments, it would also need the downsampling trick (or equivalent) to be able to apply episodic restriction.\n* 4 seeds is a very small number. I know that very few works present much more than this, but I think it is bad practice. Please consider adding more (>=10). I admit that in your case, the trend is quite clear as competing algorithms show null performance most of the time.\n* I think the repeated use of the term “solved” is quite misleading. The traditional definition of “to solve” is probably “to reach maximum performance”. This is definitely not the case in several environments. Please consider either defining precisely what you mean by “solved”, or not using that term.\n* There is no codebase in the supplementary material. Do you plan on releasing it? Please consider doing so.\n\nI believe most of these weak points can be solved during the rebuttal. \n\n------------------------------------        \n**Recommendation and justification:**\n\nI think this paper should be accepted for the reasons listed in the Strong Points section. I'm giving a score of 7. I'd be happy to raise this score to an 8 provided that the authors add a discussion section to discuss the points mentioned above.\n\n------------------------------------        \n**Feedback to improve the paper (not part of assessment):**\n\n* “in which the agent gets trapped into one (long) corridor and fails to try other choices.” →  not very clear at this point, although it’s explained later.\n* The episodic restriction seems to require a policy that has memory. Otherwise the reward would not be Markovian anymore. Maybe this should be said somewhere?\n* Short-sightedness paragraph: “but it is often far less than enough in a complex environment”: vague and not argumented.\n* What do the environment code stands for? S, R, Dl-h, Dl-hb, Q?\n* Results could be a little bit bigger, maybe switch the colors so that the two leading algorithms do not have almost identical colors (pink and red)?\n* In tables, what does bold indicate? Is it only the best value? does it assert statistical significance (if yes, which test at which confidence level?)\n* I believe the paper does not mention which RL algorithm is used. This seems like an important detail to provide. \n\n**Typos:**\n* “In contrast, (Campero et al. 2020) solves 50% of the tasks…” →  remove parentheses. Same in the last paragraph before Sec. 5 “For this, (Zhang et al, 2019) ...  (Raileanu)...”. Other examples throughout.\n* Reward definition in Sec2. Not well defined, we don’t know what are t, k or what the =1 refers to. \n* Do not use contractions “does’nt”, “don’t”, “won’t”, “let’s” etc.\n* Sec. 3, Episodic Restric. paragraph: “back and force” → “back and forth”\n* “the observation to the agent” → “the observation of the agent” ?\n* Table 2 caption: “th” → “the”.\n* Second to the last paragraph before the Intrinsic Reward Heatmap paragraph: “discover” → “discovers”.\n* “BeBold doesn’t suffer from short-sighted problem” → “BeBold does not suffer from short-sightedness” or “the short-sighted problem”.\n* “We only give RND intrinsics” → is “intrinsics” a word ? \n\n\n**Post-rebuttal update**\nThe authors addressed most of my concerns during the rebuttal, added relevant discussions, experiments on Montezuma and clarified the reported evaluation metrics. I raise the score from 7 to 8.", "extra_scores": {}, "extra_text": {}}, {"review_id": "m2MaqW_3B_C", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "BeBold: Exploration Beyond the boundaries of Explored Regions\n\nThe authors address the problem of exploring efficiently for a reinforcement learning agent when the reward function is sparse. They propose to compute an intrinsic reward based on the inverse visitation count to reduce the visit imbalance generated by optimizing for the extrinsinc reward.\n\nThis work present an interesting approach to progressively explore at the boundaries of the most visited states (a phenomenon that occurs when the agent focus on maximizing known rewards). They address the key problem of short-sightedness in this domain. The contribution is clearly stated by the authors. The results support the claim that their method achieved state-of-the-art performance of the Minigrid environments and Nethack. They also provide an analysis of the necessity of clipping and having an episodic restriction on the intrinsic reward (ERIR).\n\nA couple of remarks however: \n- the context should be clarified: you mention a quite classical RL setting, which assumes is done by interacting with the environment. In that case, one can explore via action selection and potentially discover new states (by trying new actions or experiencing an unexpected outcome). On the other side, you method tackle the problem of visiting properly a known space (as the effect of the method \"marks\" actions that transition from well-visited to poorly visited parts of the state space for the next episode). This should be made explicit.\n- How is this augmented reward information used? I didn't see a clear mention of the learning algorithm implemented in the agent, please make that explicit.\n\nAs a main criticism, I's day that the underlying assumption of this work is that the environment is somewhat known and that \"exploration\" only happens within this known environement. It is critical to the method that the action selection process itself moves the agent towards fully-unknown parts of the state space.\n\nSection 6 should be clarified on how your methods and the related work actually relate ; it is only done for the last paragraph but should be clarified for the other approaches you cite.\n\nTypos:\np4: \"from MiniGird: ...\"\np6: \"... heatmap of normalizd visitation counts...\"\np8: \"... maximizng mutual information\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "FJdzhbR4yOE", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper focuses on exploration with intrinsic rewards and proposes to use the difference of inverse visitation count as the intrinsic rewards. The method outperforms some existing baselines with intrinsic rewards in the procedurally-generated tasks (MiniGrid and NetHack). \n\nClarity: This paper introduces the method and discusses its advantage over the previous work clearly, but some small points are vague and need more clarification (please see the section 'Cons' for the details.)\n\nOriginality: As far as I know, the proposed formulation of intrinsic reward is novel, though it is closely related to prior works. For example, in \"NEVER GIVE UP: LEARNING DIRECTED EXPLORATION STRATEGIES\", the intrinsic reward is also a combination of visitation count in the current episode and lifelong prediction error. \n\nSignificance: The proposed idea itself is interesting, and it has shown SoTA results in some challenging tasks. This work will be more significant if there are positive results on other hard exploration tasks (not only procedurally generated tasks), e.g. Montezuma's Revenge.\n\nPros:\n* The proposed method is simple and effective in some challenging procedurally-generated tasks. \n* This paper discusses the weakness of the previous work and explains why the proposed method helps address these issues.\n* This paper visualizes the change of visitation count during training and thus explicitly demonstrates the behavior of the learning policy. \n* This paper conducts an ablative study to investigate the role of different components in the proposed intrinsic reward. \n\nCons:\n* In section 3, \"inverse visitation counts as prediction difference\". Could you please clarify why the prediction error in RND method can approximate the inverse visitation count? This unclear point seemingly weakens the ground of the proposed method. \n* In Figure 3, are some baselines methods missing in some tasks. For example, on \"Medium: KeyCorridorS5R3\", are there curves for the baselines?\n* In section 4, the authors discuss the weakness of the count-based exploration method: detachment. Go-explore tries to solve the detachment problem and shows super good performance on Atari hard-exploration tasks. It will be quite interesting if the proposed method could also significantly outperform the count-based exploration of the Atari games. Currently, the experiments are all conducted on procedurally-generated tasks. Does the proposed method could also work well on other types of domains?\n* In section 1, it is mentioned that the curiosity-driven intrinsic reward suffers from the noisy TV problem. The proposed method will also suffer from this problem or not? In other words, is there any failure case that the proposed method will not work?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CCDpWO2mVv", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThis paper is a presentation of BeBold, a new method using an intrinsic reward for exploration, meant for procedurally generated, episodic environments. The method includes two major components: the first being intrinsically rewarding the agent for entering states that are less visited than the current state and the second being only intrinsically rewarding the agent for the first time it enters a state during an episode. The agent's intrinsic reward is larger if the difference in visit counts is larger. The paper includes some discussion of the conceptual advantages of BeBold over prior work as well as empirical demonstrations in MiniGrid and NetHack.\n\n**Strengths and Weaknesses**\nThe primary strength of this paper is the BeBold reward as an idea. The most noteworthy weaknesses, from my point of view, are the discussion of \"short-sightedness\" and the narrative used to describe BeBold, both frequently seeming misleading or missing important clarifying points. However, the paper is supported by other strengths including an appropriate discussion of related work.\n\nThe authors have made short-sightedness a core support for their proposed method. Unfortunately, they have not provided sufficient evidence to convince me that short-sightedness is necessarily a problem. The intuition with the corridor example makes sense, and some of the experiments seem to support the idea. However, it’s not clear to what extent this is a serious issue and how much it affects exploration. Furthermore, the other experiments seem to contradict the authors’ reasoning and cast doubt on their analysis. The pseudo-mathematical analysis seems seriously oversimplified and flawed, since it makes several incorrect assumptions and still doesn’t prove the authors’ point more than the intuitive explanation. The experiments also have issues that prevent them from providing appropriate support. \n\n**Recommendation**\nI am recommending that the paper be rejected primarily because, as stated, insufficient evidence is provided for the core support for the paper.\n\n**Specific Examples of Issues**\n\n1. Conceptual Issues:\n\n1.1 It is implied that the second-longest corridor will receive the second-largest amount of exploration, but this is not true in the results shown in Table 1, where the second-longest corridor (length 30) is never the corridor with the second-largest amount of exploration. This disagreement is concerning and brings doubt into the entire discussion.\n\n1.2 It is not generally true that \"the probability to take action left or right is proportional to the accumulated reward\" (p. 12) This assumption is not the case for epsilon-greedy Q-learning nor softmax/Boltzmann exploration (at least for most temperature settings), which are two very common strategies.\n\n1.3 The description of short-sightedness in the introduction (\"the agent often settles in local minima, sometimes oscillating between two states that alternately feature lower visitation counts\" (p. 1) does not clearly match the problem of short-sightedness described in Section 4, where it appears to refer to the problem where longer trajectories (corridors) provide more accumulated intrinsic reward.\n\n1.4 The method is designed for procedurally generated environments, and there is no discussion of and no experimental work dealing with stochastic environments. While it is completely acceptable to design a method that works for one type of environment and not another, the reason I see this omission as slightly problematic is that all of the primary comparisons are with count-based intrinsic rewards. One of the explicit strengths of count-based rewards is that they encourage the agent to return to states multiple times to acquire enough data to account for high variance. Do you know if it is possible that such environments might give count-based methods the edge over BeBold? While testing this hypothesis is beyond the scope of this paper, I think a comment about such a possibility would be appropriate to include in this paper.\n\n1.5 It appears that the example 1/N count-based bonus that is used (Section 3 and Appendix A) to demonstrate a conceptual disadvantage of count-based methods over BeBold is not used in the works you cite. Bellemare et al (2016), Ostrovski et al. (2017), and Puigdomènech Badia et al. (2020) all use 1/$\\sqrt{N)}$-esque bonuses and the exact decay rate of RND (Burda et al., 2018b) is difficult to put one's finger on, but it isn't designed to mimic 1/N. In this way, using a 1/N bonus seems inappropriate for demonstrating a conceptual shortcoming in existing work. This is an important concern for me, because it comes across as misinforming the reader.\nNote: I believe the citation to Burda et al. (2018a) should be with the citation to Pathak et al. (2017), rather than with the count-based methods. \n\n2. Weaknesses in the experiments:\n\n2.1 Why use a Q-network for the tabular setting at all? To provide an empirical demonstration of the discussion in Appendix A, initializing all Q-values to zero and updating them as discussed in the Appendix would likely be more instructive for the reader.\n\n2.2 Because there is randomness involved (for example, in the Q-network as mentioned on page 6) I expect there to be variance in the numbers reported, but Tables 1 and 2 do not appear to include any measure of uncertainty. How many runs were done? Further, I can't find an explanation of how the Q-network was initialized, including what kind of random initialization was used.\n\n2.3 Did BeBold solve all of the environments or only the 12 \"most challenging ones\"? \"We test BeBold on all environments from MiniGrid. BeBold manages to solve the 12 most challenging environments\" (p. 5). I found the way this was expressed a touch unclear. I'm hoping that you could instead write, \"BeBold manages to solve all environments, including the 12 most challenging environments.\"\n\n2.4 In Table 2 (p. 6) there is no mention of what 0.2M, 0.5M, etc. mean. Are they episodes?\n\n2.5 While the introduction asserts that there are quantitative results showing that BeBold mitigates the detachment problem (p. 2), I could not find any discussion of detachment in the discussion of the quantitative results in the paper. I'm also a bit doubtful that the included experiments are appropriate for demonstrating this mitigation quantitatively.\n\n2.6 Can you provide a little more explanation about why clipping needs to be done to allow for a fair comparison? Does clipping mean the same thing in this context as it did in Section 3, that is, to only allow positive rewards? \"We remove clipping from BeBold for a fair comparison\" (p. 6). \n\n2.7 I'm concerned about the choice to measure the quantity of training data based on the number of episodes rather than the number of time steps. As Machado et al. (2018, Section 3.1.3, pp. 528-529) suggest in their discussion of benchmarking reinforcement learning agents, when episode lengths differ from episode to episode, the policy affects the amount of training data. Do you have a conceptual reason to think that this won't pose a problem in your experiments?\nMachado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M., & Bowling, M. (2018). Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61, 523-562.\n\n3. Inaccurate references to the literature:\n\n3.1 It is not obvious how the overall goal of Brockman et al. (2016), which I read to be a presentation of OpenAI Gym, supports the point you are making: \"most work requires either a manually-designed dense reward\" (p.1) I can see it supporting the point that much work makes use of manually-designed dense rewards, but not that not having it causes most algorithms to fail. It may be helpful to provide a page number so the interested reader can more easily follow your thinking. I was expecting some kind of survey or argument about how the type of reward affects performance in Deep RL, so this citation was surprising for me.\n\n3.2 Detachment and derailment are written as though they are a single concept (p. 1) and the example doesn't really give a very accurate sense of the definitions of either. What does this example have to do with derailment?\n\n3.3 The explanation of detachment on page 4 does not seem to accurately capture the meaning as it was defined by Ecoffet et al. (2019). In particular, an important property of a detachment situation is that the intrinsic reward in an area between two unexplored areas is exhausted, meaning that the exploration of one of those areas is not only delayed, as in your example, but is never induced through intrinsic reward because there isn't enough intrinsic reward left to shape behaviour towards that area.\n\n4. Incorrect or missing logic:\n\n4.1 The paper claims that another method relies on good-quality generalization because it uses two stages. This is not necessarily true.\n\n4.2 How can you be sure that reliance on quality generalization is the reason that BeBold performs better than RIDE? (\"As a result, BeBold shows …\")\n\n4.3 Why are you comparing your method with Campero et al. (2020) rather than any of the other examples that use MiniGrid? \"In contrast, (Campero et al., 2020) solves 50% of the tasks, which were categorized as “easy” and “medium”, by training a separate goal-generating teacher network in 500M steps\" (p. 2) I suspect it is the present state-of-the-art at the time of writing, but would appreciate the narrative in the paper confirming that.\n\n5. Failure to communicate the connection between other sources and this paper:\n\nThe paragraphs on Go-Explore, Frontier-based exploration, and BeBold comment separately on each approach without relating them. This part is especially difficult to understand since the reader hasn't been told very much about how BeBold works at this point in the paper.\n\nFor example, it may be useful to clarify that because the Frontier-based methods described are designed for robots, they take advantage of properties of the physical spaces that those robots are designed for, like being structured such that exploring a 2D map is a reasonable goal.\n\n6. References to ideas and existing literature that haven't been introduced:\n\n6.1 At the point in the text where the reader is pointed to Figure 1, (the end of page 1) RND has been introduced as a module of the proposed method used to approximate the inverse visitation count, not as a competing method, and no explanation of how RND is designed has been provided, with the same going for any clues as to why RND gets \"trapped.\" The function c is not defined.\n\n6.2 The term trajectory should be defined for your context. In some papers, a trajectory is any sequence of state-action-rewards in the environments, while in others it only includes those corresponding with a complete episode. It would probably be best to try to include a definition around its first use on page 1: \"Finally, state-diff approaches offer rewards if, for each trajectory, representations of consecutive states differ significantly.\" Some kind of explanation of why trajectories get so much focus in the early part of the paper would also be helpful.\n\n**Additional Feedback (Here to help, not necessarily part of decision assessment)**\n\nOne way to make this paper easier to follow, and perhaps more impactful on the reader, would be to order the paper differently. Because the algorithm is so much inspired by the gaps in the literature, I think explaining the shortcomings of different existing algorithms before explaining BeBold might work really well. You could leave it in the current order, but the story needs to be told quite differently to avoid the many references to existing literature without explanation.\n\nThe phrase \"criterion for IR\" (in the Abstract) made me think it meant some kind of requirement for something to be defined as IR, and from context, I think you're not trying to define IR, you're trying to define a new type of IR, so I would consider rephrasing. You used \"exploration criterion\" later and it is a bit less confusing. Matching the wording of other papers who are creating new types of IR would improve understanding within the group of researchers focused on IR.\n\n\"The statement \"Random exploration (e.g., $\\epsilon$-greedy) in these environments is often insufficient and leads to poor performance (Bellemare et al., 2016)\" (p. 1) leaves room for misunderstanding from the reader, so I recommend something like \"Random exploration (e.g., $\\epsilon$-greedy) __alone__ is often insufficient.\"\n\n\"have proposed to use intrinsic rewards\" (p. 1) → \"have proposed using intrinsic rewards\"?\n\n\"This addresses asymptotic inconsistency in the state-diff, since the inverse visitation count vanishes with sufficient explorations.\" I expected the word \"exploration\" rather than \"explorations\" here because the word \"exploration\" is more commonly used as an uncountable noun (meaning the plural form is still \"exploration\") but if you mean exploration in a sense that is countable, a definition would be really helpful. (p. 1)\n\n\"transition function T : S × A → P(S) where P(S) is the probability of next state given the current state and action.\" This is kind of strange notation since P(S) doesn't seem to be a set of anything. Also, it doesn't seem like T appears anywhere else in the paper, so you probably don't need this definition at all. (p. 2)\n\nTo help clarify this reward, it would be useful to discuss when the counts, $N(s)$, are updated, which I'm guessing is at the end of the episode? The definition in (1) doesn't result in the properties described if the counts are updated online after each transition (in which case, if we imagine a corridor, then $N(s_{t+1}) = N(s_t) - 1$, so you get the same properties of \"short-sightedness\" as offered by count-based methods.\n\n\"We clip the IR here because we don’t want to give a negative IR to the agent if it transits back from a novel state to a familiar state.\" (p. 3) Can you explain briefly why this would be problematic? I think it is natural to ask why we shouldn't just keep pushing the agent forward into the frontier by giving it a negative reward if it takes a step back? An example of a situation where such a choice would cause a problem would be helpful here. \n\n\"As a result, the agent will continue pushing the frontier of exploration in a much more uniform manner than RND and won’t suffer from short-sightedness.\" RND hasn't actually been mentioned in the text prior to this point, so I think this would be quite confusing for someone who does not know RND very well.\n\n\"partial observation o_t are used\" This looks like a typo. (p. 3)\n\n\"RIDE (Raileanu and Rocktäschel, 2020) avoids this by scaling the intrinsic reward r(s) by the inverse of the state visitation counts.\" I don't think you use the notation r(s) ever again.\n\n\"The corridor $\\tau_j$ has a length of $T_j$.\" Since you never use $T_j$ again, as far as I can tell, I recommend just telling the reader that the lengths of the corridors vary to avoid adding notation that isn't used. (p. 3)\n\n\"preference on exploring\" should probably be \"preference for exploring\" (p. 3)\n\n\"Automatic curriculum approaches (Campero et al., 2020)) have similar issues due to an ever-present IR.\" Extra parenthesis. (p. 4)\n\n\"For this, (Zhang et al., 2019) proposes to learn a separate scheduler to switch between intrinsic and extrinsic rewards, and (Raileanu and Rocktäschel, 2020) divides the state representation difference by the square root of visitation counts.\" (1) Accidental citep instead of citet, (2) should probably be \"proposes learning\" rather than \"proposes to learn\" since it is the agent that will be learning, rather than the authors, and (3) should be divide rather than divides since Raileanu and Rocktäschel are two people. (p. 4)\n\n\"We only evaluate AMIGo for 120M steps in our experiments, the algorithm obtains better results when trained for 500M steps\" There's a comma splice there; it would be helpful to have some kind of transition to help the reader leap between the two ideas and why they are shared here. (p. 4)\n\n\"where each tile contains an object\" Should this actually be \"where each tile may contain an object\"? (p. 4)\n\n\"MR consists of a series of rooms connected by doors and the agent must open the door to get to the next room.\" I assume they have to open more than one door in a single environment? I was expecting, \"the agent must open each door to get to the subsequent room\" or something along those lines. (p. 4)\n\nIn Figure 3, I think some kind of indicator of the maximum possible return would be helpful. (p. 5)\n\n\"Multi Room environments are relatively easy in MiniGrid.\" I don't understand what this means. Do you mean that they are relatively easy for BeBold, and if so, how are you measuring \"easiness\"? (p. 5) \n\n\"RND, AMIGo, RIDE, IMPALA and BeBold successfully solves KCS3R3\" should probably be \"RND, AMIGo, RIDE, IMPALA and BeBold successfully solve KCS3R3\" (noun-verb agreement, p. 5)\n\n\"We analyze how BeBold mitigates the short-sightedness issue by only using IR to guide exploration\" (p. 5) From context, I'm guessing that you mean that you are no longer including the extrinsic reward, so in this section ($r_t = r_t^i$)? The phrase \"to guide exploration\" is a little ambiguous, so you might do better to be more specific, like \"only using IR in the computation of the value function\" or something along those lines. \n\n\"Entropy of th visitation counts\" (p. 6) Typo in the caption for Table 2.\n\n\"give all states equal amount\" (p. 6) Missing article on equal amount (probably should by \"an equal amount\") \n\n\"normalizd visitation counts\" (p. 6) Typo.\n\n\"discover all the rooms\" (p. 6) should probably be \"discovers all the rooms\"\n\nI was a bit uncomfortable with the definition of curiosity-based intrinsic reward, though it is appropriate for all of the intrinsic reward methods that use the word curiosity that I am aware of, because the term curiosity has been used quite differently for other methods that don't use an intrinsic reward, like the method published by Still and Precup (2012).\nStill, S., & Precup, D. (2012). An information-theoretic approach to curiosity-driven reinforcement learning. Theory in Biosciences, 131(3), 139-148.\n\nYour bibliography has some capitalization errors. For example, Vinyals et al. 2019 has lost the capital S, C, and II for StarCraft II, Silver et al. 2016 and 2017 have lost the capital N in Nature, and Brockman et al. 2016 has lost the capital AI in OpenAI Gym.\n\n\"Both starts with\" probably should be \"Both start with\" (noun-verb disagreement, p. 12)\n\"If an agent have\" probably should be \"If an agent has\" (noun-verb disagreement, p. 12)\n\"Using count-based approach\" probably should be \"Using a count-based approach\" (missing article, p. 12)\n\n-------------------------------------------------------------------------------\n**UPDATE from responses**\n\nThank you for your detailed response to my comments.\n\nThe majority of my comments describing the weaknesses of this paper are related to both the conceptual and experimental components of the corridor example, so I want to recommend not including the example at all. It does not add clarity or provide any conceptual insights. This is in agreement with your stated primary focus, which is on demonstrating the empirical performance of a novel intrinsic reward design. Further, if you removed nearly all of the parts of the paper referring to the corridor example, you might have space to explain the detachment and derailment and the relationship of your method to these problems, as well as the other terminology that is currently not defined. It may be appropriate to include the idea briefly as motivation.\n\n**It is not clear to what extent short-sightedness is a serious issue and how much it affects exploration.**\n\nNone of the papers have the term \"short-sighted\" in them, so at the very least, you are using a new name for a problem and then not defining it clearly. To the best of my reading, the problem you describe as short-sightedness is not described in these papers. Ecoffet et al. focus on derailment and detachment (which are different from the short-sightedness problem described in this paper) and while Guo et al. do describe myopia, their paper is not about intrinsic reward, so the type of local optima that they get stuck in are quite distinct from the optima created by the intrinsic reward design that the short-sightedness problem refers to.\n\nI am a strong proponent of using tabular simplifications to better understand problems, but in this case, the tabular simplification has not allowed for a sufficiently detailed understanding of short-sightedness. For this reason, I think it is important to look to the function approximation setting. In the function approximation setting, shortsightedness isn't clearly a problem. Your results in Table 2 suggest that RND doesn't suffer from short-sightedness in the same way that the tabular count-based method does—it does not spread out between the corridors evenly, which seems to be the behaviour you are looking for, but it doesn't get the short-sightedness effect either.\n\n**The pseudo-mathematical analysis in the appendix seems seriously oversimplified and flawed.**\nWhen I said that it was over-simplified, I meant that the assumptions that were made are inappropriate. I am not looking for more complex analysis; I am looking for analysis of an equally simple problem but one that is correct. The primary problem with the analysis is that it sort of stops in the middle. There is a great deal of set-up, and then the final point is simply a qualitative statement that if the growth of a quantity is proportional to how big it is, then the quantity that starts out larger will continue to get larger. The differential equations are not needed and not even used to make this point.\n\n1. While it is true that you do not state that the second-longest corridor will obtain the second-most exploration, I would like to understand what makes the choice of the second corridor to explore different from the choice of the first corridor to explore. From what you've written, it sounds like the agent is going to become obsessed with the longest corridor, and continue exploring it until it is \"exhausted.\" If the first corridor is never exhausted, why are the remaining three corridors not explored roughly the same amount? If the first corridor is exhausted, why isn't the next corridor that the agent becomes obsessed with the second longest, since it is now the longest corridor that is not exhausted, making it a similar choice to the initial one. In this case, wouldn't the second-longest corridor receive the second-most exploration? While I understand that because the action is sampled from the distribution output by the policy network instead of taking max, the \"exhausting\" would not necessarily happen neatly, but it still seems that the Q-value of the second-longest corridor should become the second-largest, again resulting the second corridor being sampled the second most.\n\n1.3 I am not disputing that this could be thought of as getting stuck in local minima, but I believe that the idea that \"alternately feature lower visitation counts\" is a completely different problem from the long corridor preference (which may actually have higher visitation counts, but is more preferable due to accumulation).\n\n2.5 Since you do not know why your method outperforms the baselines, it is inappropriate to say that BeBold mitigates the detachment problem. \n\n2.6 I'm sorry that I don't understand this response. Can you explain the relationship between reward clipping and dedication?\n\n3.3 The response does not address my concern. The primary problem is that the way detachment and derailment are described does not seem to be accurate. The example, \"in which the agent gets trapped into one (long) corridor and fails to try other choices,\" partially addresses the problem of detachment, but does not appear to have any relevance to derailment. However, I am also of the opinion that for the authors to adequately support claims about these concepts, they must be described in enough detail for the reader to understand.\n\n4.2 I understand that a difference between RIDE and BeBold is this use of an embedding network, and I can see why you might hypothesize that it might affect performance, but again, I don't think there is any evidence given to show that this is the reason that BeBold outperforms RIDE, so it should be stated appropriately.\n\n6.1 While I am familiar with RND, the problem I am trying to point out here is that the terms appear in the paper prior to any explanation of what they are, which severely hinders readability.\n\n**Additional Feedback (Here to help, not necessarily part of decision assessment)**\n\nI recommend using the terms _target_ network and _predictor_ network for the two networks involved in RND, rather than teacher and student. Since target and predictor are used in the majority of the paper by Burda et al., they're more memorable for readers of the paper, so I think it will be less confusing.\n\nNew Typos: \n\"The results is averaged\" → The results are averaged (p. 5)", "extra_scores": {}, "extra_text": {}}, {"review_id": "7Sq9efum4J", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary \n\nThe authors propose a novel intrinsic reward based on the difference of inverse visitation counts for consecutive states. This reward encourages the agent to explore beyond the boundary of already explored regions. Using a few simple examples, they show that the proposed intrinsic reward mitigates the problems of detachment and short-sightedness which are common for count-based methods. The method shows superior performance on a number of tasks from two procedurally-generated benchmarks, MiniGrid and NetHack. The paper also contains comparisons with a few strong baselines (including SOTA on these benchmarks), analysis of the learned behavior and intrinsic reward, as well as ablations of the proposed approach. \n\n\nStrengths \n\nOverall, I really liked this paper. The proposed method is simple, well motivated, clearly explained, significantly outperforms the SOTA, and solves hard exploration tasks that were previously out of reach. I found the empirical evaluation to be very thorough and comprehensive, including multiple baselines and ablations. I particularly liked the careful motivation of this approach together with the quantitative analysis in Section 5.2 (which compares the visitation counts and intrinsic rewards of different methods). In addition, the authors support their claims regarding the short-sightedness and detachment issues with well designed experiments and metrics. \n\n\nWeaknesses\n\nOne thing that wasn’t clear to me after reading the paper was what are the teacher and student networks used to approximate the visitation counts. Are these equivalent to the predictor and random network used by RND? This is an important detail so please clarify. \n\nCould the network phi (used to estimate visitation counts) “forget” previously visited states and thus lead to short-sighted behavior in a similar way as count-based methods do (i.e. oscillate between two state regions / corridors)? Have you ever observed this behavior in practice and if not, do you have any intuition why?\n\nHave you tried scaling the IR reward by the inverse of the episodic state counts (like RIDE does) instead of only using the episodic restriction? It might be interesting to add it as an ablation and give some intuition on which (when) one is preferable.  \n\nI think it would be valuable to include all the baselines in the analysis section i.e. Tables 1, 2, and Figures 4, 5 (they can be in the appendix if there isn’t enough space).\n\nCan you specify how many seeds you used for computing the mean and std in the plots? I could not find information and it is important in order to understand the significance of the results.\n\n\nMinor Points\n\nIs there any reason for which in Figure 4 you don’t show the visitation counts for both models for the same number of environment steps? I think that would be a more clear way of presenting those results. \n\nThere is some inconsistency in the notation used. In Figure 1, you use c(s) to denote visitation counts, while in Section 3, you use N(s). \n\nTypos:\nTable 2: “entropy of the” \nFigure 2: “MRN6” → MRN6-SX?\nCitations in various places contain parentheses where they should not (i.e. in the middle of a sentence).\n\n\nRecommendation\n\nThis paper presents a novel and effective method for an important problem, and it also provides insightful analysis to better understand the limitations of different approaches. Thus, I think it would be a valuable contribution and I recommend it for acceptance. \n\n\n\n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have mixed views about this paper. 

However, it seems to me that the paper is missing some important related work on near-optimal exploration and it is only picking a couple of superficially similar approaches to look at. In particular, the standard benchmarks of Rmax, UCRL and Posterior Sampling do are not mentioned. I encourage the authors to look at such methods closely. They perform exploration byplanning over a sample or set of possible MDPs. 

I also want to raise another issue mentioned by the reviewers. The paper focuses extensively on neural networks, however a count-based metric is inherently for the tabular case. Why would a neural network be appropriate in such a setting? (The authors use a hash table because they are using a large discrete space. However, does it makes sense to essentially uniformly randomly cluster states together? Could there be another, better method? How about continuous spaces?)

The algorithm idea is interesting, and the core is given already in (1) as:  'give reward in newly visited states'. However, the algorithm as described is incomplete.  It is OK as a high-level description, but normally we'd require sufficient detail to reimplement the method from scratch.
You should for example specify how this intrinsic reward value is going to be used. Most of the reviewers, including me, could not understand how a student/teacher network would be  combined with (1) to produce the intended exploration. Please try to explain in as much detail as possible your algorithm in order for the reviewers to be able to make an informed decision.

Decision: Reject