Integrating Episodic and Global Novelty Bonuses for Efficient Exploration
Authors: Mikael Henaff
Minqi Jiang
Roberta Raileanu
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
exploration
generalization

Abstract: Exploration in environments which differ across episodes has received increasing attention in recent years. Current methods use some combination of global novelty bonuses, computed using the agent's entire training experience, and episodic novelty bonuses, computed using only experience from the current episode. However, the use of these two types of bonuses has been ad-hoc and poorly understood. In this work, we first shed light on the behavior these two kinds of bonuses on hard exploration tasks through easily interpretable examples. We find that the two types of bonuses succeed in different settings, with episodic bonuses being most effective when there is little shared structure between environments and global bonuses being effective when more structure is shared. We also find that combining the two bonuses leads to more robust behavior across both of these settings. Motivated by these findings, we then investigate different algorithmic choices for defining and combining function approximation-based global and episodic bonuses. This results in a new algorithm which sets a new state of the art across 18 tasks from the MiniHack suite used in prior work. Our code is public at \url{web-link}. 

Under review as a conference paper at ICLR 2023
INTEGRATING EPISODIC AND GLOBAL NOVELTY BONUSES FOR EFFICIENT EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
Exploration in environments which differ across episodes has received increasing attention in recent years. Current methods use some combination of global novelty bonuses, computed using the agent's 's entire training experience, and episodic nov- elty bonuses, computed using only experience from the current episode. However, the use of these two types of bonuses has been ad-hoc and poorly understood. In this work, we first shed light on the behavior these two kinds bonuses on hard exploration tasks through easily interpretable examples. We find that the two types of bonuses succeed in different settings, with episodic bonuses being most effec- tive when there is little shared structure between environments and global bonuses being effective when more structure is shared. We also find that combining the two bonuses leads to more robust behavior across both of these settings. Motivated by these findings, we then investigate different algorithmic choices for defining and combining function approximation-baie based global and episodic bonuses. This re- sults in a new algorithm which sets new state of the art across 18 tasks from the MiniHack suite used in prior work. Our code is public at web-link.
INTRODUCTION
Balancing exploration and exploitation is long-standing challenge in reinforcement learning (RL). A large body of research has studied this problem within the Markov Decision Processes (MDP) framework (Sutton & Barto, 2018), both from theoretical standpoint (Kearns Singh. 2002; Braf- man & Tennenholtz, 2002; Agarwal et al., 2020) and an empirical one. This has led to practical exploration algorithms such as pseudocounts (Bellemare et al., 2016b), intrinsic curiosity modules (Pathak et al., 2017) and random network distillation (Burda et al., 2019), yielding impressive results on hard exploration problems like Montezuma's Revenge and PitFall (Bellemare et al., 2012).
More recently, there has been increasing interest in algorithms which move beyond the MDP frame- work. The standard MDP framework assumes that the agent is initialized in the same environment at each episode (we will refer to these MDPs singleton MDPs). However, several studies have found that agents trained in singleton MDPs exhibit poor generalization, and that even minor changes to the environment cause substantial degradation in agent performance (Zhang et al., 201 8b; Justesen et al,, 2018; Zhang et al., 201 8a; Cobbe et al., 2019; Kirk et al., 2021a). This has motivated the use of contextual MDPs (CMDPs, (Hallak al., 2015)), where different episodes correspond different environments which nevertheless share some structure. Examples of CMDPs include procedurally- generated environments (Chevalier-Boisvee) et al., 2018; Samvelyan al., 2021; Küttler al., 2020; Juliani et al., 2019; Cobbe et al., 2020; Beattie et al., 2016; Hafner, 2021; Petrenko et al., 2021) or embodied AI tasks where the agent must generalize across different physical spaces (Savva al., 2019; Shen et al., 2020; Gan et al., 2020; Xiang et al., 2020).
While exploration is well-studied in the singleton MDP case, it becomes more nuanced when deal- ing with CMDPs. For singleton MDPs, a common and successful strategy consists of defining an exploration bonus which added to the reward function being optimized. This exploration bonus typically represents how novel the current state is, where novelty is computed with respect to the entirety of the agent's ' experience across all episodes. However, it is unclear to what extent this strat- egy is applicable in the CMDP setting-ii if two environments corresponding to different episodes are very different, we might not want the experience gathered in one to affect the novelty of a state observed in the other.

---

Under review as a conference paper at ICLR 2023
An alternative using global bonuses is to use episodic ones. Episodic bonuses define novelty with respect to the experience gathered in the current episode alone, rather than across all episodes. Recently, several works (Stanton & Clune, 2018; Raileanu & Rocktäschel, 2020; Flet- et al., 2021; Zhang et al., 2021b; Henaff et al., 2022) have used episodic bonuses, with Henaff et al. (2022) will
showing that this is an essential ingredient for solving sparse reward CMDPs. However, show, an episodic bonus alone may not be optimal if there is considerable shared structure across different episodes in the CMDP.
In this work, we study how to best define and integrate episodic and global novelty bonuses for exploration in CMDPs. First, through series of easily interpretable examples using episodic and global count-based bonuses, we shed light on the strengths and weaknesses of both types of bonuses. In particular, we show that global bonuses, which are commonly used singleton MDPs, can be poorly suited for CMDPs that share little structure across episodes; however, episodic bonuses, which are commonly used contextual MDPs, can also fail certain classes of singleton MDPs where knowledge transfer across episodes is crucial. Second, we show that by multiplicatively combining episodic and global bonuses, we are able to get robust performance on both contex- tual MDPs that share little structure across episodes and singleton MDPs that are identical across episodes. Third, motivated by these observations, we comprchensively evaluate different combina- tions of episodic and global bonuses which do not rely on counts, well as strategies for integrating them, on a wide array of tasks from the MiniHack suite (Samvelyan et al., 2021). Our investigations yield new algorithm which combines the elliptical episodic bonus of Henaff al. (2022) and the NovelD global bonus of Zhang et al. (2021b) which sets a new state of the art across 18 tasks from the MiniHack environment, solving the majority of them. Our code is available web- 1 link.
BACKGROUND
2.1 CONTEXTUAL MDPs
Pc: We consider a contextual Markov Decision Process (CMDP) defined by (S, P.r.l. Ps) where S is the state space, is the action space, C is the context space, P is the transition function, Mss is the initial state distribution conditioned on context and pc is the context distribution. At each episode, we first sample a context episode, the next state is then sampled according to st+1 P(-sst, ae, c) and the reward is given by rt = r(8t, az e). Let de represent the distribution over states induced by following policy æ with context The goal is to learn policy which maximizes the expected return, averaged across contexts:
NC and an initial state sg ps(-]c). At each step in the
R = Eespe (1)(()))
Examples of CMDPs include procedurally- generated environments, such as ProcGen (Cobbe et al., 2020), MiniGrid (Chevalier-Bal Boisvert et al., 2018), NetHack (Küttler et al., 2020), or Mini- Hack (Samvelyan al., 2021), where each context corresponds the random seed used to gener- ate the environment; in this case, the number of contexts [C] is effectively infinite (we will slightly abuse notation and denote this case by [C| 30). Other examples include embodied AI environ- ments (Savva et al., 2019; Szot et al., 2021; Gan et al., 2020; Shen et al., 2020; Xiang et al., 2020), where the agent is placed in different simulated houses and must navigate
srreedurallyyggeeratteeddd
location or find an object. In this setting, each context c E C represents a house identifier and the number of houses |C] typically between 20 and 1000. More recently, CARL (Benjamins et al., 2021) was introduced as benchmark for testing generalization in contextual MDPs. However, their focus is on using privi- leged information about the context c to improve generalization, which we do not assume access to here. For an in-depth review of the literature CMDPs and generalization in RL, see Kirk et al. (2021b). Singleton MDPs are a special case of contextual MDPs with [C]
2.2 EXPLORATION BONUSES
At a high level, exploration bonuses operate by estimating the novelty of a given state, and assigning high bonus if the state is novel according to some measure. The exploration bonus is then combined with the extrinsic reward provided by the environment, and the result is optimized using RL. More precisely, the reward function optimized by the agent is given by:
2

---

Under review as a conference paper at ICLR 2023
F(s,a) = r(ss a b(s,a)
(I)
where r(s, a) the extrinsic reward, b(s, a) is the exploration bonus, and is parameter governing the balance between exploration and exploitation. Some bonuses do not depend on a or additionally depend the next state s', which will be clear from the context. To account for the sometimes wide variation in the scale of exploration bonuses across different environments and different points in time during training, the exploration bonus sometimes divided by a running estimate of its standard deviation, is done in Burda et al. (2019).
In tabular domains with small number of discrete states, a common choice is to use the inverse counts: b(s) (s) (Strehl & Littman, 2006), where ((s) is the number of times state has been encountered by the agent. However, in many settings interest the number possible states is large or infinite, and many states will not be seen more than once, rendering this bonus ineffective since all states will be rewarded by the same amount. This has motivated alternative approaches using function approximation. The methods below have proven successful on sparse reward singleton MDPs (RND) and/or sparse reward CMDPs (RIDE, AGAC, NovelD and E3B).
Random Network Distillation (RND) (Burda et al., 2019) randomly initializes a neural network f : S - R and then trains second neural network ff with the same architecture to predict the outputs of f on states encountered by the agent. The exploration bonus associated with a given state is given by the MSE:
(*)) = 1l5( - f(x))112
The intuition is that for states similar ones previously encountered by the agent, the error will be low, whereas it will be high for very different states. RND has performed well on hard singleton MDPs and is commonly used component of other exploration algorithms.
Novelty Difference (NovelD) (Zhang et al., 2021b) uses the difference between RND bonuses at two consecutive time steps, regulated by an episodic count-based bonus. Specifically, its bonus is:
bNoelID (St, a, 8t-1) (RND(( c bRND(st) [[ =1]
(3)
Here bAND represents the RND bonus defined above, and Ne(s) represents the number of times has been encountered within the current episode. The first term global novelty bonus, which measures novelty with respect to cross-episode experience, whereas the second term is an episodic novelty bonus, which measures novelty with respect to experience within the current episode only.
Adversarially Guided Actor-Critic (AGAC) (Flet-Berliac et al., 2021) also combines global and episodic novelty bonuses. Its bonus is defined by:
bAGAC(s)) = DKL (( + B
V (8e)
where Tadv is policy trained to mimic the behavior policy æ (usually with smaller learning rate). The motivation is that this will encourage the policy to adopt different behaviors as it tries remain different from the adversary. The second term is an episodic bonus based on (s).. the number of times the state has been encountered within the current episode.
Rewarding Sopact-Driven Exploration (RIDE) (Raileanu & Rocktäschel, 2020) uses an episodic novelty bonus which is the product of two terms: baset reward and the difference between two consecutive state embeddings:
(RIDE(S))
[((((+1) ((8x)ll2
(5)
(N.(s.
Here the & embedding is learned using a combination of inverse and forward dynamics models. The motivation for the second term in the bonus is reward the agent for taking actions which cause significant changes in the environment. RIDE does not use global novelty bonus.
Exploration via Elliptical Episodic Bonuses (E3B) (Henaff et al., 2022) also uses an episodic novelty bonus only, and is motivated by the following observation: while the count-based episodic bonuses used in NovelD,, RIDE and AGAC are essential for good performance, they do not scale to
3

---

Under review as a conference paper at ICLR 2023
complex enviromments where given state is unlikely to be than once within episode. E3B uses a feature extractor & learned using an inverse dynamics model, and defines the episodic bonus follows:
(s))( = ( C-1 E ((s))(ss)) + A
(6)
==
Here to denotes the start of the current episode. This can be seen generalization of episodic count-based bonus to continuous state spaces.
3 WHEN ARE EPISODIC AND GLOBAL NOVELTY BONUSES USEFUL?
Although RIDE, NovelD, AGAC and E3B all use different combinations of episodic and global novelty bonuses, their use in CMDPs has been largely heuristic. The RIDE and NovelD papers simply state that the episodic bonus included between a sequence of states within the same episode. Furthermore, the global novelty bonuses are justified using the singleton MDP case, but it is unclear to what extent these justifications carry over to the CMDP case. Therefore, a closer investigation of when episodic and global novelty bonuses are useful in CMDPs required. Details for all experiments in this section are Appendix
prevent the agent from going back and forth
3.1 ADVANTAGES OF EPISODIC BONUSES
We begin by providing an example of CMDPs where global novelty bonuses fail and episodic bonuses succeed. Consider the procedurally- generated MiniHack environment shown in Figure 1. Here, each episode corresponds to a different map where the agent must navigate from the start- ing location to the goal. The agent only receives reward if it reaches the goal, and the episode ter- minates if it touches the walls which are made of lava. Because of this, random exploration has a very small chance of reaching the goal before the episode ends, and exploration bonuses are needed.
.......)).)......))
)..)
..........334)3333
h.)
|111111))......
I........33).....
.....................
................................
We ask the question: are global or episodic nov- elty bonuses more appropriate here? For simplic- ity, consider bonuses based counts of (z, locations, which are commonly used in prior work (Flet-Berliac et al., 2021; Samvelyan et al., 2021; Zhang et al., 2021b) to avoid the issue of each state being unique:
Figure 1: Two different contexts of the Mult t MaltiRRoomNN-LLaV environment. Leg- end:
agent, start, goal. lava
1
(s)
Depisodic (s) = I[Ne((((s) = 1]'
(7)
(s))
Here N represents counts over all the agent's experience, and N. represents counts only within the current episode, while vú is a feature extractor which extracts the (z, y) coordinates of the agent from the state, In general, methods which do not require handcrafted features are preferable, and we focus on them in Section 4. However, this simple bonus facilitates interpretability, which is the focus of this section.
Using the global novelty bonus encourages the agent to learn sequence of policies which, together, cover all the (x, 3) locations. This is appropriate when the map is the same across all episodes: eventually, of the policies will cover the (x. v/) location corresponding to the goal and the agent will receive reward. However, this is not appropriate in this CMDP setting where the environment
We also tried
for the episodic bonus, but it didn't work as well.
V (N)
4

---

Under review as a conference paper at ICLR 2023
changes each episode. To this, note since the goal location changes along with the rest of the map each episode, it can find itself in a region whose global bonus has already been depleted. The more uniform the goal sampling is, the less likely it is the global bonus will be useful.
In contrast, the episodic bonus encourages the agent to visit as many (z, y) locations as possible within each episode. Since each episode corresponds to its map, well-optimized policy will thus have a high chance of visiting region close to the goal, which turn will increase the chance of reaching the goal and receiving reward.
MintHbcckMuutRRRom---WLaawww
To verify this argument, we train agents us- ing the global and episodic bonuses equa- tion 7 over different numbers of contexts [C] on
Episode Return
the MiniHack-Mull Mooolttiooo-NN--eee vironment shown in Figure 1. The number of contexts represents the number of distinct maps, and one of them is chosen at random at start of each episode. Results are shown
en-
06-
in Figure 2. The agent using the global bonus obtains perfect performance for the singleton MDP setting where |C] 1, but performance steadily degrades as the number of contexts in- creases. In contrast, when using the episodic bonus, performance remains high as the num- ber of contexts increases. We found that per- formance remains high (0.86 + 0.1) even when [C] 2o (no two maps are repeated during training).
00-
Episodic
Gobal Bonus
Number of contexts |C]
Mean performance for global and episodic count-based exploration bonuses with different numbers of contexts (i.e. maps). Shaded region indicates standard deviation over 5 seeds.
Figure 2:
Reward-free exploration Habilat HM3D
Episodic bonus
We provide further evidence for this ar- gument with experiments on Habitat, photorealistic simulator of indoor environ- ments. Habitat is conceptually similar to MiniHack MamiiHack-MMaaaaa RRom environment in
% Map Revealed
Global bonuses
the sense that at each episode, the agent finds itself in different indoor space con-
20
sisting of connected rooms. However, the maps in Habitat are considerably more com- plex and the observations
Random (no stop)
RND
pixel-based. Here we compare global and episodic bonuses based on function approximation, since counts are not meaningful with high- dinhnssimnsi im- ages. We use the reward-free exploration setup described (Henaff al., 2022). Results are shown in Figure 3. We see that, similarly to Mi n Hack -Mac- Room, the global bonuses (ICM and RND) perform poorly whereas the episodic bonus (E3B) performs well. See Appendix for details.
Figure 3: Habitat exploration with |C]
1000.
corrtdors
3.2 ADVANTAGES GLOBAL BONUSES
Does this mean that should always prefer an episodic bonus global one? Unfortunately, the answer is not so clear-cut. We now provide an example where the episodic bonus fails but the global bonus succeeds. Consider a singleton MDP with M corridors which can be crossed in 7 steps, with a single one containing reward at the end (shown in Figure 4). If the episode length is T. then any policy which goes to the end any the M corridors will get equivalent episodic bonus, and hence the chance of success will be 1/M. On the other hand, a global bonus will solve the task: after visiting one of the corridors, the global bonus there will eventually become de- pleted and the agent will move on to another one, eventually visiting the corridor with the reward.
steps
Simple example where episodic bonus fails.
Figure/
5

---

Under review as a conference paper at ICLR 2023
We illustrate this argument using a singleton version of the Cr envi- ronment (shown in Figure 5a), where the agent must explore different corridors to find its way to the exit. This is similar to the example in Figure 4 in the sense that the agent will likely need to explore multiple dead ends before finding the goal. Figure 5b shows results for agents trained with the episodic and global bonus. In contrast the previous example, but consistent with a requmeettt above, the global bonus succeeds across all seeds whereas the episodic bonus produces inconsistent performance across seeds, leading poor performance overall.
MiniHack- Corriioo--oorioo----ee R5, |c| =
Episode Return
oball Bonus
Episodic Bonus
No Banus
(b)
Figure 5: a) Example map for MiniHacke 
enviromett
é indicates agent,
corridors connecting rooms, start location and goal. b) Performance agents trained with the global bonus and the episodic bonus on singleton version of the environment, Error bars represent the standard deviation across random seeds.
Are global bonuses only useful in the special case of singleton MDPs? We next show that this is not the case, and that global bonuses can also be useful in general CMDPs with large [C], provided they exhibit certain shared structures across contexts. We consider the Mi ni Hack - KeyRoom-S) SSnnms10 environment illustrated in Figure 6a. this environment, the agent must pick up key and use to open door to small room and reach the exit. Here different contexts correspond to different placements of the agent, key, room, door and exit. A property of this environment is that when the agent visits certain states along the optimal trajectory, it receives messages which are common across all contexts. For example, whenever the agent moves to the key location in any context, it receives the same message "You see here a key named The Master Key of Thievery".. Similarly, when picking up the key, it receives the same message, "g key named The Master Key of Thievery." Here, we extract the message rather than the (r. y) coordinates.
define the 1 feature extractor in equation Results in Figure 6b show that both the global and episodic bonuses work well for [C] = co. This explained by the fact that regardless of the context, a policy which activates both of these can explaanee
messages aligns with the optimal policy. A global bonus will encourage the agent to explore diverse messages throughout training, eventually activating the two messages above which bring it close to the optimal policy, An episodic bonus will encourage the agent to activate diverse messages within each episode, which in this case similarly brings close to the optimal policy.
3.3 COMBINING GLOBAL AND EPISODIC BONUSES
Taken together, the above examples suggest that global and episodic bonuses have complementary strengths and weaknesses, and that their effectiveness depends the amount of shared structure among different contexts the CMDP. one end of the spectrum, singleton MDPs have complete sharing of structure among contexts (since they all identical), and global episodic bonuses best suited. At the other end the spectrum, CMDPs such as the MultiRoom environment share little structure between contexts and episodic bonuses are preferred. The KeyRoom environment sits somewhere in between, where contexts are different but there is nevertheless shared structure between them, and both types of bonus effective.
This raises the question: is there a bonus which works well across all of these different settings? We hypothesize that multiplying the episodic and global bonuses together would be more effective than

---

Under review as a conference paper at ICLR 2023
KeyRoom-S10, [C]
0.8
Episode Return
0.0
Global Bonus Episodic Bonus
No Bonus
(b)
Figure 6: a) Two example maps for MiniHack Beeeccc--eeooo----- S10 enviroment. indicates agent, key, door, start location and goal. b) Performance of agents trained with the global bonus and the episodic bonus. Error bars represent the standard deviation across random seeds.
either of them alone, and would work well across a wide range of CMDPs with differing amounts of common structure across episodes. The resulting combined bonus is given by:
Drombined (82) T[Na(1((s))) =] ((.((s))
(8)
This is motivated by the following observations. First, let us consider the MDP in Fig- ure 4: note that following any of the corridors will maximize the episodic bonus by pro- viding an episodic bonus of at each step. The total combined bonus in equation is then equal to the global bonus, and optimizing the global bonus causes the agent to visit each
the corridors until reaches one with the reward, solving the MDP. environ-
Now let us consider the ment. If the agent is initialized roughly uniformly throughout the map, the global bonus will de- cay roughly uniformly across regions over time. This means that the bonus in equation 8 will be roughly equal to the episodic bonus (scaled by a constant), which we know is effective. Finally, as noted previously, in KeyRoom SS0 both the episodic and global bonuses will assign high nov-
Combined Bonus Performance
1.3
Episode Retum
0.4
elty to messages associated with picking up the key, which aligns with the optimal policy, sug- gesting that their product will also be effective.
Cordors 14-1
MultRcom Lava
4 -1=x
Figure 7: Performance of combined bonus. Er- ror bars indicate standard deviation over 5 seeds.
Empirical results for all three environments are shown in Figure 7 (we use the same v feature ex- tractor as in previous experiments for each envi- ronment). We see that the combined bonus obtains good performance all three environments, which suggests that retains the advantages both the global and episodic bonus.
DESIGN CHOICES FOR EPISODIC AND GLOBAL NOVELTY BONUSES
The previous section has shown that global and episodic bonuses succeed different types of CMDPs, and that combining them via multiplication can yield bonus which is more robustly effective. However, in order to facilitate interpretability we used count-based bonuses, which do not scale to complex, high-dimensional environments unless task-specific prior knowledge is used (e.g. knowing to extract (z, y) positions or messages). this section, we investigate whether our insights still hold when using more general bonuses which do not assume such prior knowledge. We

---

Under review as a conference paper at ICLR 2023
do this through study of global and episodic bonuses based function approximation across wide range of tasks from the MiniHack suite (Samvelyan et al., 2021).
4.1 EXPERIMENTAL SETUP
As our experimental testbed, we use 18 sereddurally-eeneratee tasks from the MiniHack suite (Samvelyan et al., 2021) used in prior work (Henaff et al., 2022). The MiniHack tasks are de- signed to precisely evaluate different capabilities of a given agent, such as navigation, planning or the ability use objects. Furthermore, many of the MiniHack tasks involve sparse rewards (which are only given on completion the task) and complex observations which include irrelevant infor- mation. For evaluation, we follow the protocol suggested by Agarwal et al. (2021) and report the mean, median and interquartile mean (IQM) together with 95% confidence intervals using stratified bootstrapping. We use 5 random seeds for each of the 18 tasks. Our full experimental details can be found in Appendix D.
4.2 RESULTS
We now investigate combining different global novelty bonuses from AGAC, RND and NovelD with the elliptical episodic bonus. We use E3B's elliptical bonus as our episodic bonus instead of a count-base based one, since prior work has shown that count-based bonuses either fail in complex environments, or are highly dependent on task-specific feature extractors (Henaff' et al., 2022). In contrast, the elliptical bonus has been shown to work well across wide range of environments without requiring task-specific prior knowledge.
Two questions we aim to answer are: i) which global bonus (if any) gives the most improvements when combined with E3B's elliptical bonus, and ii) which strategy best for combining the two bonuses. To answer these, consider the following algorithms:
bE3RXAGAC(SE)
((x) C (8x))
DRI((T( (-)e) Tadv
DE3BXRND(#)) ((s)) T cT(
ll((s)) f(s))11
DE3exNovelD (8t)
(()) (7))
[1((541) - f(sH+1)l12 clf((s)) f(s:)113
(E3B+AGACC5L) = ((s,) T oz)))()))
+ (Dkaa
DE3B+RND(SL) = ((x)) T cT1
+ *1s(ss)) - f(xe)112
(B3B+NovelD(st) = [Z) + [[1f((e+1)) f(sc+1)l -cllf((ss)) - f(s))1
Here & learned online using inverse dynamics model. The algorithms above include all possible combinations of global bonuses (second term) with the elliptical bonus (first term), and combining the two by multiplication or by taking a weighted sum. For the algorithms which take a weighted sum, we tuned the 3 term on subset of tasks, and report the best value on all 18 tasks. We compare E3B as baseline since it was previously shown outperform other methods such as IMPALA, RND, ICM, RIDE and NovelD (Henaff et al., 2022).
Results are shown Figure First, we see that additively combining any of the global bonuses with the elliptical episodic bonus does not provide meaningful improvement over E3B for any metric. However, multiplicatively combining E3B with either RND or NovelD bonuses produces a large and statistically significant improvement in both median and IQM performance over E3B (the more robust metrics according to Agarwal et al. (2021)), )), as well as modest improvement in mean performance. This establishes new tfate-of-the-ar art MiniHack.
One explanation for the superior performance of the multiplicative combination over the additive one is that the scale of the global bonus decreases significantly throughout training whereas the scale of the episodic bonus does not, since it is reset each episode. Because of this, if we combine the two bonuses via addition, the combined bonus will become increasingly dominated by the episodic
8

---

Under review as a conference paper at ICLR 2023
Median
IQM
Mean
E3B
E3B AGAC
E3B + NovelD
E3B + RND
E3B x AGAC
E3B NovelD
E3B RND
0.84
0.87
0.90
0.93
0.850
0.875
0,900
0.925
0.56
0.64
0.72
Episode Return
Figure 8: Aggregate performance on MiniHack tasks, Bars indicate 95% confidence intervals computed using stratified bootstrapping.
bonus. However, if we are combining the two multiplicatively, the global bonus will still have an effect regardless of its scale. See Appendix E for additional results and discussion.
5 RELATED WORK
Exploration in singleton MDPs is well-studied problem in RL, give more detailed overview of existing methods Appendix C. However, these methods are designed for the singleton MDP setting and some form of global bonus which,
show in Section is not always appropriate to the more general CMDP setting we consider here. More recently, RIDE (Raileanu & Rocktäschel, 2020), AGAC (Flet-Berliae al., 2021) and NovelD (Zhang al., 2021b) have begun tackle MDPs, a type of CMDP commonly used in empirical research. These methods use combinations of global bonuses designed for singleton MDPs and count-based episodic bonuses. The recent work of Henaff et al. (2022) highlighted the practical importance of these episodic bonuses, as well the weaknesses of count-based episodic bonuses, and proposed the elliptical episodic bonus solution, but did not include a global bonus. Compared to these prior works, our work makes two contributions. First, whereas previous works justified using global bonuses by appealing to intuitions from singleton MDPs, and provided little justification for using episodic bonuses aside from their empirical performance, we provide deeper justifications for of each bonus in CMDPs. In particular, examine in detail the behavior of global and episodic count-based bonuses across different representative settings, and shed light on how each bonus can drive exploration depending the amount of shared structure across episodes. Second, whereas previous works have investigated different combinations bonuses in isolation, there has not been systematic comparison of bonuses and combination strategies, which we do in Section investigation results in a new algorithm which outperforms the previously proposed ones. Further- more, our algorithm's 's multiplicative combination of global and episodic bonuses is well justified based on our previous investigations in Section
ploration in serteddrrallyggneertte
This
CONCLUSION
In this work, we have taken steps towards better understanding the roles of global and episodic exploration bonuses in CMDPs. First, we study illustrative examples in which count-based versions of each bonus succeed and fail, showing that the two bonuses have complementary strengths and weaknesses. In particular, our experiments suggest that the effectiveness of each bonus depends on the amount of structure which is shared across episodes in the CMDP, and that episodic bonuses are more effective when there little shared structure, while global bonuses benefit from more shared structure. We also show that combining global and episodic bonuses multiplicatively leads to increased robustness across different settings. Motivated by these observations, we perform an in-depth empirical study of approaches which combine global and episodic bonuses in the function approximation setting. This results a new algorithm that sets a new state-of-the-art across 18 tasks from the MiniHack suite. Future research directions include more precisely understanding and characterizing the settings where each bonus will succeed, which may lead to improved algorithms which adapt automatically to the setting at hand.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv:1703.01722 2017.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed explo- ration for provable policy gradient learning. Advances in neural information processing systems, (33), 2020.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in Neural Informa- fion Processing Systems, 2021.
Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, et al. Deepmind lab. arXiv preprint arXiv:1612.03881, 2016.
Mare Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47, 07 2012. doi: 10.1613/jains 3/jairr.::39..
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information pro- cessing systems, 29, 2016a.
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp. 1479-1487, Red Hook, NY, USA, 2016b. Curran Associates Inc. ISBN 9781510838819.
Carolin Benjamins, Theresa Eimer, Frederik Schubert, André Biedenkapp. Bodo Rosenhahn, Frank Hutter, and Marius Lindauer. Carl: A benchmark for contextual and adaptive reinforcement learning. arXiv preprint arXiv:2 orXiv:2/10.02100) 10.02 2021.
Ronen I. Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213 231, 2002. URL http://
jmlr. http://pppps////////////
html.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network
distillation. In International Conference on Learning Representations, 2019, URL https: ///////////// //operreview ew net./ fo rum? d=H1 JJnRRYm..
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Con- ference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pp. 1283-1294. PMLR, 13-18 Jul 2020. URL https:/ httpp/ppooccn....e/ee/p mlr. prwss/v119// cai20d. html.
Maxime Chevalier-Boiswer Lueas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. hitps: /ttpps:///ittee /ttpttttth/b///// com http///aaiimmmmeeeeem http://gmmmmiiiiii.. 2018.
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (clus). Yoshua Bengio and Yann LeCun (eds.), 4th Inter- national Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http: arxiv. org. http//ls..111....... 07289....9.
Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. Quantifying gener- alization in reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 1282-1289. PMLR, 09-15 Jun 2019.
10

---

Under review as a conference paper at ICLR 2023
Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforeement learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2056-2056. PMLR, 13-18 Jul 2020. https:::: htt.httts::/ppoceeeeeee pwwpeediingg.....
mlr www..pres//vee v 9 cobbe20a.a.occccccc html.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IM- PALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Jen- nifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, vol- ume 80 of Proceedings of Machine Learning Research, pp. 1406-1415, PMLR, 2018. URL http:/ ppwpeediiggs...ccooo mmlm wwwpppeesssveeeee 1ee00//speho..e wspeholttaa..... html.
Yannis Flet-Berliac, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adversar- abs/
ially guided actor-critic. CoRR, abs/2102.04376, 2021. URL
2102.04 04376.
Ronan Fruit and Alessandro Lazaric. Exploration-exploittiie in mdps with options. In Artificial intelligence and statistics, pp. 576-584. PMLR, 2017.
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near optimal exploration-exploitaton non- communicating markov decision processes. Advances in Neural Information Processing Systems, 31, 2018a.
Ronan Fruit, Mattco Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient blas-span-constraile Learning, pp. 1578-1588 PMLR, 2018b.
in reinforcement learning. In International Conference Machine
Chuang Gan, Jeremy Schwartz, Seth Alter, Martin Schrimpf, James Traer, Julian De Freitas, Jonas Kubilius, Abhishek Bhandwaldar, Nick Haber, Megumi Sano, et al. Threedworld: A platform for interactive multi-modal physical simulation. arXiv preprint w:Xiv:200..0495. 2020.
Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint arXiv:2109.06780, 2021.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint 150.002202222 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. arXiv preprint 11x1v:1512.033385, 2015.
Mikael Henaff.
Explicit explore-exploit algorithms in continuous state spaces. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett
(eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso-
ciates, Inc., 2019. URL https: htttps:///pooceedingg wwwpsa/ss...uiiisseooom wwweurps..cpppper///eeeeeee wttpc//pppp//21///1iea... pdf.
Mikael Henaff, Roberta Raileanu, Minqi Jiang, and Tim Rocktäschel. Exploration via elliptical episodic bonuses. In NeurIPS, 2022.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1785-1780, 1997.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforce- ment learning with linear function approximation. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceed- ings of Machine Learning Research, pp. 2137-2143. PMIR, 09-12 Jul 2020. URL https: //proceeding
jin20a html.
Arthur Juliani, Ahmed Khalifa, Vincent-Pierre Berges, Jonathan Harper, Hunter Henry, Adam Crespi, Julian Togelius, and Danny Lange. Obstacle tower: A generalization challenge in vi- sion, control, and planning. CoRR, abs/1992.011388 2019. URL http: /arxivv...././////////a////avavv .org/ abs/ 1902. 01378.

---

Under review as a conference paper at ICLR 2023
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Procedural level generation improves generality of deep reinforcement learning. CoRR, abs/1806. 10729, 2018. URL http:: org abs 100.6.806..0 10729.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. In Machine Learning. pp. 209-232. Morgan Kaufmann, 2002.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of generalisation in deep reinforcement learning. CoRR, abs/2111.09794, 2021a. URL
abs/2111. 09794.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of generalisation in deep reinforcement learning. CoRR, 1.0929111,9994, 2021b. URL https: httpp::://axii.rrgpp./ abs/ 2111. 09794.
J Zico Kolter and Andrew Y Ng. Near-bayesian exploration in polynomial time, In Proceedings of the 26th annual international conference machine learning, pp. 513-520, 2009.
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The nethack learning environment. CoRR, abs/2006.13760, 2020. URL https:t////. aaaaaiivvvrro abs/ 20000006... 13760.
Marlos C Machado, Mare Bellemare, and Michael Bowling. Count-based exploration with the successor representation. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 34, pp. 5125-5133, 2020.
Gaurav Manek and J Zico Kolter. Model-based reinforcement learning with ensembled model-value expansion. 2021.
Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, and Mareus Hutter. Count-based explo- ration in feature space for reinforcement learning. arXiv preprint arXiv: 170.00800, 2017.
Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference machine learning, pp. 2721-2730. PMLR, 2017.
Pierre-Yves Oudeyer and Frederic Kaplan. What is intrinsic motivation? typology of computa- tional approaches. Frontiers in neurorobotics, 1:6, 2009.
Pierre Yves Oudeyer, Frdric Kaplan, and Verena Hafner. Intrinsic motivation systems for au- tonomous mental development. IEEE transactions evolutionary computation, 11(2):265-288) 2007.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. CoRR, abs/1705.053633 2017. URL 7705.05361
org/ abs/
Aleksei Petrenko, Erik Wijmans, Brennan Shacklett, and Vladlen Koltun. Megaverse: Simulating embodied agents at one million experiences per second. In International Conference on Machine Learning. pp. 8556-8566 PMLR, 2021.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally-geeeeateed environments. In International Conference on Learning Representattons, 2020. URL https: htttp:://ppeeeeeeeeee http///ppppteeeeeee/e/ee net http://eee/fuutmme///ee
TJBFPE.
Santhosh Kumar Ramakrishnan, Aaron Gokaslan, Erik Wijmans, Oleksandr Maksymets, Alexan- der Clegg, John M Turner, Eric Undersander, Wojeiech Galuba, Andrew Westbury, Angel X Chang, Manolis Savva, Yili Zhao, and Dhruv Batra. Habitat- Sabitat-matterporr 3d dataset (HM3d): 1000 -cage-scale 3d environments for embodied AI. In Thirty-fifth Conference Neural In- formation Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL https: / //openrevi ew. net.ff forum? dimmiid===uuussS..
12

---

Under review as a conference paper at ICLR 2023
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holde Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Küttler, Edward Grefenstette, and Tim Rocktäschel, Minihack the planet: A sandbox for open-ended reinforcement learning research. CoRR, abs/2109.13202, 2021. URL
https:: rx rivivv..vvv org/ alos 13202.
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied Al Research. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), 2019.
Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neu- ral controllers. In Proc. of the international conference on simulation of adaptive behavior: From animals to animats, pp. 222-222 1991.
Ramanan Sekar. Olch Rybkin, Kostas Danillidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supe world models. ICML, 2020.
Bokui Shen, Fei Xia, Chengshu Li, Roberto Martín-Martín, Linxi Fan, Guanzhi Wang, Claudia Pérez-D' Arpino, Shyamal Buch, Sanjana Srivastava, Lyne Tchapmi, al. igibson 1.0: A simu- lation environment for interactive tasks in large realistic scenes. In 2021 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 7520 7520-752.2.2 IEEE, 2020.
Pranav Shyam, Wojciech Jaškowski. and Faustino Gomez. Model-based active exploration. In Ka- malika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Con- ference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5779-5788. PMLR, 09-15 Jun 2019. URL https: htttp:://ppooeeedngaa. htt.:///...........psssss///// shyam1 9a html.
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint 1 00814, 2015.
Christopher Stanton and Jeff Clune. Deep curiosity search: Intra-life exploration improves perfor-
mance challenging deep reinforcement learning problems. CoRR, ab6//800.,0053, 2018. URL http: / aaaaiiiiiiiv.//..//.aaaaaaaaaava www.rwwwww...ae.ooooooeeeooeeeee abs/ / 806 00553.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 1309):130--133,, 2008.
Er L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 2006.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Andrew Szot, Alex Clegg, Eric Undersander, Erik Wijmans, Yili Zhao, John Turner, Noah Maestre, Mustafa Mukadam, Devendra Chaplot, Oleksandr Maksymets, Aaron Gokaslan, Vladimir Von- drus, Sameer Dharur, Franziska Meier, Wojciech Galuba, Angel Chang, Zsolt Kira, Vladlen Koltun, Jitendra Malik, Manolis Savva, and Dhruv Batra. Habitat 2.0: Training home assistants to rearrange their habitat. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schul- man, Filip DeTurck, and Pieter Abbeel. exploration: study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No- regret exploration in goal-oriented reinforcement learning. In International Conference on Ma- chine Learning, pp. 9428-9437. PMLR, 2020.
Erik Wijmans, Abhishek Kadian, Ari S. Morcos, Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. Dd-ppo: Learning near- cear-perfect pointgoal navigators from 2.5 billion frames. In ICLR, 2020.
13

---

Under review as a conference paper at ICLR 2023
Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanx- iao Jiang, Yifu Yuan, He Wang, et al. Sapien: A simulated part-based interactive environment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 11097-11107, 2020.
Amy Zhang, Nicolas Ballas, and Joelle Pineau. A dissection of overfitingg and generalization in continuous reinforcement learning. arXiv preprint arXiv:1806.07937 2018a.
Chiyuan Zhang, Oriol Vinyals, Rémi Munos, and Samy Bengio. study on overfitting in deep reinforcement learning. CoRR, abs/1804.06893, 2018b. URL http://arxiv.. org.ab/// 1804. 06833.
Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph E Gonzalez, and Stuart Russell. Made: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 34:9663-9680, 2021a.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuan- dong Tian. Noveld: A simple yet effective exploration criterion. In Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021b. URL wttpt:tt//// https:://peerreveew net forum?
14


Reviews:
[{"review_id": "qAX-74nV46", "reviewer": "Reviewer_2WV4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigated the benefits of global vs episodic exploration bonuses, and provided interesting intuition as to when each would help learning and when it would not. Moreover, this paper studies setting of contextual MDPs, which is relatively understudied compared to single MDPs. It proposes a simple way of combining global and episodic bonuses that work nicely in the tasks that they investigate. ", "summary_of_the_review": "This paper was an interesting and easy read and contains useful and novel results and intuitions for the community concerning the use of exploration bonuses, especially their combination. However, as it stands, there is not yet a hint of how their study would behave in slightly more scaled up tasks, and their analysis on combining exploration bonuses is a little too scant. If these factors can be rectified, I would definitely move my score up on what I think is an interesting paper. ", "strength_and_weaknesses": "Strengths: this study provided nice toy tasks that gave good intuition about when global vs episodic exploration bonuses would be beneficial and when they would not. Their multiplicative combination solution at the end of the paper (combining the 2) was a simple solution that can be easily implemented. They hypothesized why it works (the relative scaling of gobal vs episodic bonuses over  episodes). Finally, the fact that they tried it both for count-based bonuses as well as the more scalable E3B bonus was commendable. \n\nWeaknesses: The tasks tried remain toyish and are limited in scope (confined to the minihack suite). While I really liked the demonstrations they provided, and think that minihack is a good start, it would have been nice to see at least a hint of either 1) how global vs episodic exploration bonuses behave in a slightly more scaled up task (e.g. procgen or anything with nontrivial pixels), or 2) how their multiplicative solution behaves in such a scaled up task and whether it still works. \n\nFinally, their investigation of their multiplicative solution ends on a hypothesis: that it works because of the relative scaling of global vs episodic bonuses over  episodes. It would have been great if they could provide some more comprehensive empirical evidence for this hypothesis. The question of how to combine global & episodic exploration bonuses is a good question (and more generally, understanding  the effects of exploration durign learning/generalization is a very important question in RL). The authors did a cool experiment investigating multiplicative vs additive combination.  It is a very simple manipulation, but simple manipulations often have great merit. They should have dissected this experiment  for a more comprehensive understanding of this result. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZDSS5JMK3jr", "reviewer": "Reviewer_b6oF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper tackles the problem of exploration in RL. This has long been a challenging problem in RL, the paper talks about the episodic novelty and global novelty in the exploration. The paper studies the two novelty and draws the conclusion that they are effective in different settings. Episodic novelty is most effective when there are structures shared while global novelty is most effective when there are fewer structures shared. The paper conducts experiments on 18 MiniHack tasks. ", "summary_of_the_review": "Overall I appreciate the authors' effort in tackling the exploration problem. However, it is a little hard for me to judge whether the conclusion can be drawn only from the MiniHack experiments. Please see the strengths and weaknesses above. ", "strength_and_weaknesses": "Strength: \n1. The paper tackles the problem of episodic and global novelty, which is a very interesting setting. \n2. The paper is well written. \n3. The baselines are compared thoroughly. \n4. The experiments is conducted over 18 tasks.\n\nWeakness: \n1. I feel the paper may dismiss some baselines like Never Give Up, MADE. \n2. I feel like the experiments conducted are toy and it is hard for me to judge whether this is a valuable contribution in general. I would suggest conducting more experiments in different domains to support the conclusion. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MaGyeOw8c6", "reviewer": "Reviewer_xEHz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work aims to analyze the use of two exploration novelty bonuses - global bonuses and episodic bonuses - in the problem of exploration in environments. Previous works show that global novelty is computed using agent’s entire training experience while episodic novelty is constrained within the specific episode the agent is in. This paper delves into the different behaviors of these two bonuses. When there is little shared structure between environments, episodic bonuses are useful; when there is more structure shared between environments, global bonuses are useful. This leads to the combination of global and episodic bonuses, and evaluation on various settings. ", "summary_of_the_review": "The idea is straightforward and convincing, but I think theoretical contributions / novelty / experimental evaluations are limited. I give the marginally below the threshold score, but I'm happy to raise the scores after the discussion with other reviewers. ", "strength_and_weaknesses": "Strengths \n- This work is based on the contextual MDP (CMDP) setting, where C is the context space in addition to the MDP setting. Per each episode, the context c is sampled from the context distribution. \n- Nice and detailed explanations on background on exploration bonuses (RND, novelD, AGAC, RIDE) in section 2.2. \n- I think the main part of this paper is the section 3, raising the questions of when are episodic bonuses and global novelty bonuses are useful, respectively. \n- There are some example of CMDPs where global novelty bonuses fail, and advantage of the episodic bonuses succeed.(MiniHack, for example). Where the environment changes each episode, global bonuses fail (Figure 2). \n- There are other cases of CMDPs where global novelty bonuses are preferred. This is useful (1) singleton MDP case (2) although with large |C|, the structures are shared across contexts. \n- I think the arguments made by the authors are compelling so far. \n- The experiments in the section 3 are valid\n- Evaluations are valid. \n\nWeakness\n- Although the authors showed the insights on when to prefer global bonuses, and when to prefer episodic bonuses, and its relationship with level of structures being shared across the context. I think the contribution is not largely significant. This paper does not introduce a new algorithm,  although it shows some design choices for episodic and global novelty bonuses. \n- Although the authors argue that general CMDPs with large |C| with shared structures across contexts are good fit for global bonuses, they didn’t add theoretical insights in it; only tried to prove it via one example. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7sQGrJnkB0", "reviewer": "Reviewer_f9fK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors evaluate the relation between episodic and global novelty bonus with regard to contextual MDPs. They show two simplified examples for demonstrating the different advantages of the two novelty bonus types. Additionally, they explore 6 different combinations of the episodic E3B bonus with global novelty bonus definitions, proposed in the literature. The methods are evaluated on 18 MiniHack domains.", "summary_of_the_review": "The paper is well written, but lacks a crucial detail and contains some questionable argumentations. Namely, the effect of the feature space is not sufficiently evaluated and it is not clear if a global-only bonus would be sufficient, given a context independent state feature space. In conclusion, the quality of the proposed method is not substantiated. The authors should clarify the mentioned feature space issues and add additional experiments with a global-only baseline and evaluate different feature spaces, if possible.", "strength_and_weaknesses": "The authors try to tackle an interesting problem in a clear to understand way. The evaluation is reasonable diverse, but could be improvement by adding different domains (not just variants of MiniHack). However, the paper suffers from flaws in the reasoning, combined with a lack of a crucial detail (the used feature space, see next section). The claims from Sections 3.1 do only hold under the used state feature spaces, because it does not generalize due to the context dependent value of the feature space. It is likely, that a context independent feature space - like the message features from Section 3.2 - will not be affected by the mentioned issue. This is also supported by Figure 5b, showing competitive results for the episodic variant. Furthermore, the results from Sec. 3.3 and 4 are not clearly showing the assumed benefit, as explained in the next Section.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject