Exploration via Elliptical Episodic Bonuses
Authors: Mikael Henaff
Roberta Raileanu
Minqi Jiang
Tim Rocktäschel
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
exploration
generalization
contextual MDP

Abstract: In recent years, a number of reinforcement learning (RL) methods have been pro- posed to explore complex environments which differ across episodes. In this work, we show that the effectiveness of these methods critically relies on a count-based episodic term in their exploration bonus. As a result, despite their success in relatively simple, noise-free settings, these methods fall short in more realistic scenarios where the state space is vast and prone to noise. To address this limitation, we introduce Exploration via Elliptical Episodic Bonuses (E3B), a new method which extends count-based episodic bonuses to continuous state spaces and encourages an agent to explore states that are diverse under a learned embed- ding within each episode. The embedding is learned using an inverse dynamics model in order to capture controllable aspects of the environment. Our method sets a new state-of-the-art across 16 challenging tasks from the MiniHack suite, without requiring task-specific inductive biases. E3B also outperforms existing methods in reward-free exploration on Habitat, demonstrating that it can scale to high-dimensional pixel-based observations and realistic environments.

Exploration via Elliptical Episodic Bonuses
Mikael Henaff
Roberta Raileanu
Meta AI Research mikael Maeaflhhenfff ceeffffmetaccmm com com
Meta Al Research Faileanu@mett com
Minqi Jiang
Tim Rocktäschel
University College London Meta AI Research meta@fb.. com
University College London w.rocktaschee@ess ucl ac uk
Abstract
In recent years, number of reinforcement learning (RL.) methods have been pro- posed to explore complex environments which differ across episodes. In this work, we show that the effectiveness these methods critically relies on count-based episodic term in their exploration bonus. As result, despite their success in relatively simple, noise-frec settings, these methods fall short in more realistic scenarios where the state space is vast and prone to noise. To address this lim- itation, we introduce Exploration via Elliptical Episodic Bonuses (E3B), a new method which extends count- based episodic bonuses to continuous state spaces and encourages an agent to explore states that are diverse under learned embedding within each episode. The embedding is learned using an inverse dynamics model in order to capture controllable aspects of the environment. Our method sets a new tate-offthhe-art across 16 challenging tasks from the MiniHack suite, with- out requiring task-specific inductive biases. E3B also matches existing methods sparse reward, pixel-basee Vizdoom environments, and outperforms existing methods in reward-fres exploration on Habitat, demonstrating that it can scale high-dimensional pixel-based observations and realistic environments.
Introduction
Exploration in environments with sparse rewards is a fundamental challenge in reinforcement learning (RL). the tabular setting, provably optimal algorithms have existed since the early 2000s [36, 10]. More recently, exploration has been studied in the context of deep RL, and a number of empirically successful methods have been proposed, such as pseudocounts [9], intrinsic curiosity modules (ICM) [52], and random network distillation (RND) [13]. These methods rely intrinsically generated exploration bonuses that reward the agent for visiting states that are novel according to some measure. Different measures of novelty have been proposed, such as the likelihood of a state under learned density model, the error of forward dynamics model, or the loss on random prediction task. These approaches have proven effective on hard exploration problems, exemplified by the Atari games Montezuma's 's Revenge and PitFall [22).
The approaches above are, however, designed for singleton RL tasks, where the agent is spawned in the same environment every episode. Recently, several studies have drawn attention to the fact that RL agents exhibit poor generalization across environments, and that even minor changes the environment can lead substantial degradation in performance [75, 35, 74, 18. 38]. This has motivated the creation of benchmarks in the Contextual Markov Decision Process (CMDP) framework, where different episodes correspond to different environments that nevertheless share certain characteristics. Examples of CMDPs include procedurally generated (PCG) environments
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

[15, 58, 41, 34, 17, 7, 29, 53] or embodied Al tasks where the agent must generalize its behavior to unseen physical spaces test time [59, 61, 28, 72]. A number of methods have been proposed which have shown promising performance in PCG environments with sparse rewards, such as RIDE [56], AGAC [25] and NovelD [76]. These methods propose different intrinsic reward functions, such as the change in representation in a latent space, the divergence between the predictions of policy and an adversary, or the difference between random network prediction errors at two consecutive states. Although not presented as central algorithmic feature, these methods also include a count-based bonus which is computed at the episode level.
In this work, we take closer look at exploration in CMDPs, where each episode corresponds to a different environment context. We first show that, surprisingly, the count-based episodic bonus that is often included as a heuristic is in fact essential for good performance, and current methods fail if it is omitted. Furthermore, due to this dependence on a count-based term, existing methods fail on more complex tasks with irrelevant features or dynamic entities, where each observation is rarely seen more than once. We find that performance can be improved by counting certain features extracted from the observations, rather than the observations themselves. However, different features are useful for different tasks, making it difficult to design a feature extractor that performs well across all tasks.
To address this fundamental limitation, we propose a new method, E3B, which uses an elliptical bonus [6, 20, 42] at the episode level that can be seen as a natural generalization of a count-based episodic bonus to continuous state spaces, and that is paired with a self-supervised feature learning method using an inverse dynamics model. Our algorithm is simple to implement, scalable large or infinite state spaces, and achieves state-of-the-art performance across 16 challenging tasks from the MiniHack suite [58], without the need for task-specific prior knowledge. also matches existing methods on hard exploration tasks from the VizDoom environment [37], and significantly outperforms existing methods in reward-free exploration on the Habitat embodied AI environment [59, 69]. This demonstrates that E3B scales to rich, high dimensional pixel-based observations and real-world scenarios. Our code is available at https:/ ///gtttttbbb/////////// com wwom/facee httm//faceoookreerccceeeee
Background
2.1 Contextual MDPs
We consider a Contextual Markov Decision Process (CMDP [30]) given by M (S,AA,, P.r. ps) where S is the state space, A is the action space, C is the context space, P is the transition function, r the reward function, Nlc the distribution over contexts and μs is the conditional initial state distribution. At each episode, we sample a context 80 ~ ~1((-cc), and subsequent states in the episode are sampled according to 81+1 ~ P(-[st, at c). Let de denote the distribution over states induced by following policy in context The goal is to learn a policy π which maximizes the expected return over all contexts, i.c. R = -e--pe.ddd as) [r(s, a)]. environments, such ProcGen [17]. MiniGrid [15], NetHack [41], or MiniHack [58], where each context e corresponds to the random seed used to generate the environment; in this case, the number of contexts CI is effectively infinite. Other examples include embodied AI environments [59, 69, 28, 61, 72), where the agent is placed in different simulated houses and must navigate
JCC, an initial state
Examples of CMDPs include
location or find an object. In this setting, each context c E C represents a house identifier and the number of houses [C] is typically between 20 and 1000. For an in-depth review of the literature on CMDPs and generalization in RL. see [39].
2.2 Exploration Bonuses
If the environment rewards are sparse, learning policy using simple e-greedy exploration may require intractably many samples. We therefore consider methods that augment the external reward function r with an intrinsic reward bonus b. A number of intrinsic bonuses that encourage exploration in singleton con-coonttt MDPs have been proposed, including pseudocounts [9], intrinsic curiosity modules (ICM) [52] and random network distillation (RND) error [13]. At a high level, these methods
Technically, some of the environments we consider are Contextual Partially Observed MDPs (CPOMDPs), but we follow the convention in [39] and adopt the CMDP framework for simplicity. For CPOMDPs, we use recurrent networks or frame stacking to convert to CMDPs, as done in prior work [46].

---

define an intrinsic reward bonus that is high if the current state is different from the previous states visited by the agent, and low if similar (according to some measure).
Method
Exploration bonus
RIDE [56]
(0((++1) ((8))l22 1/ (c(+(+1)
NovelD [76]
(BRND(FL11) -a bRNN( [[Nc((++1==]] =
AGAC [25]
+ 3 1/ (N(41)1)
Table 1: Summary of recent exploration methods for ppoceduralll-ggneraale environments. Each
exploration bonus has a count-based episodic term, marked in blue.
More recently, several methods have been proposed for and evaluated on procedurally-generee MDPs. All use different exploration bonuses, which summarized in Table 1. RIDE [56] defines a bonus based on the distance between the embeddings two consecutive observations, NovelD [76] uses bonus based on the difference between two consecutive RND bonuses, and AGAC [25] uses the KL divergence between the predictions of the agent's policy and those of an adversarial policy trained mimic it (see the original works for details). In addition, all three methods have term in their bonus (marked blue) which depends on (*(+++) the number of times $1+1 has been encountered during the current episode. Although presented as a heuristic, below will show that without this count-based episodic term, all three methods fail to learn. This in turn limits their effectiveness in more complex, dynamic, and noisy environments.
Importance and Limitations of Count-Based Episodic Bonuses
We now discuss in more detail the importance and limitations of the count-based episodic bonuses used in RIDE, AGAC and NovelD, which depend on Na()s). Figure shows results for the three methods with and without their respective count-based episodic terms, on one of the MiniGrid environments used in prior work. When the count-based terms are removed, all three methods fail to learn. Similar trends apply for other MiniGrid environments (see Appendix D.1). This shows that the episodic bonus is in fact essential for good performance.
MiniGrid-N10-95 S10-v0
07
07
67
0.6
RIDE episodic
AGAC
episodic counts)
0.4-
0.4
0.4
NovelD
episode
0.3
NovelD
(no episodic counts)
0.24
0.1
0.1
0.-
0.0-
0.0
0.0
0.5
1.0
2.5
2.0
2.5
steps
steps
steps
107
Figure 1: Results for RIDE, AGAC and NovelD with and without the count-based episodic bonus, over random seeds (solid line indicates the mean, shaded region indicates one standard deviation). All three algorithms fail if the count-based episodic bonus is removed.
However, the count-based episodic bonus suffers from a fundamental limitation, which is similar to that faced by count-based approaches in general: if each state is unique, then Ne will always be 1 and the episodic bonus is no longer meaningful. This is the case for many real-world applications. For example, a household robot's 's state as recorded by its camera might include moving trees outside the window, clocks showing the time images television screen which are not relevant for its tasks, but nevertheless make each state unique.
Previous works [56, 25, 76] have used the MiniGrid test suite [15] for evaluation, where observations are less noisy and do not typically contain irrelevant information. Thus, methods relying on episodic counts have been effective in these scenarios. However, in more complex environments such as

---

MiniHack [58] or with high- high-dimensional pixel- pixel-based observations, episodic count- based approaches can cease to be viable.
possible alternative could be to design a function to extract relevant features from each state and feed them the count-based episodic bonus. Specifically, instead of defining bonus using Ne (s)), , we could define the bonus using Ne(o(s:)), where @ is a hand-designed feature extractor. For example, in the paper introducing the MiniHack suite [58], the RIDE implementation uses ((sx) = (Iz, Wt), where (xe, Vt.) is the spatial location of the agent at time t. However, this approach relies heavily on sask-specific knowledge.
Figure shows results on two tasks from the MiniHack suite for three NovelD variants (we decided to focus our study variants of NovelD. since it previously shown to outperform competing methods on MiniGrid [76]). The first, NOVELD, denotes the standard formulation which uses uses the positional feature encoding
the bonus (*+) = 1]. The second, described above, i.e. the episodic bonus is defined as (())()()))) = 1] with ((x)) = (nt, ye). The third, NOVELD-MESSAGE, uses a feature encoding where ((t)) extracts the message por- tion of the state 8, similarly to [47] (both encodings are explained in more detail in Section 5). In contrast to the MiniGrid environments, here standard NOVELD fails completely due to the presence of a time counter feature in the Mini-
Minimack-O--ttihamm-- Www.------ae---errroooe
Hack observations, which makes each observa- tion in the episode unique. Using the positional encoding enables NOVEL.D-POSITION to solve the MultiRoom task, but this method fails on the Freeze task. On the other hand, using the message encoding enables NOVELD-MESSAGE to succeed on the Freeze task, but it fails on the MultiRoom one. This illustrates that different feature extractors are effective different tasks, and that designing one which is broadly effective is challenging. Therefore, robust new methods which do not require task-specific engineering are needed.
opicodi reward
65-
-14
steps
Stegs
NovelD
Nove D-position
Nove D D-message
Figure 2: Performance of NovelD with differ- ent feature extractors: entire observation, agent location, or environment message. Results are averaged over 5 seeds and the shaded region rep- resents one standard deviation.
4 Elliptical Episodic Bonuses
In this section we describe Exploration via Elliptical Episodic Bonuses, (E3B), our algorithm for exploration in contextual MDPs. It is designed to address the shortcomings of count-based episodic bonuses deseribed above, with two aims mind. First, we would like an episodic bonus that can be used with continuous state representations, unlike the count-based bonus which requires discrete states. Second, we would like a representation learning method that only captures information about the environment that is relevant for the task at hand. The first requirement is met by using an elliptical bonus [6. 20, 42], which provides a continuous analog to the count-based bonus, while the second requirement is met by using a representation learned with an inverse dynamics model [52, 56].
summary of the method is shown in Figure We define an intrinsic reward based on the position of the current state's embedding with respect to an ellipse fit on the embeddings of previous states encountered within the same episode. This bonus is then combined with the environment reward and used to update the agent's policy. The next two sections describe the elliptical bonus and embedding method in detail.
4.1 Elliptical Episodic Bonus
Given a feature encoding é, at each time step in the episode the elliptical bonus is defined as follows:
= ((;))
-- C-1=
[os))((s)) +
(I)
Here A/ is regularization term to ensure that the matrix Ct-1 non-singular, where À is sealar coefficient and I is the identity matrix. The reward optimized by the algorithm is then defined as

---

Policy rallout (single episode)
Agent Policy
π
enbedding
Ellipses fit on previous enbeddings wi thin episode
Low reward
low reward
low reward
high reward
Intrinsic rewards
b
b2
by
b4
Policy update
Environment
T1 T2
T4
rewards
Figure 3: Overview of E3B. At each step in episode, ellipse fit the embeddings of previous states encountered within the episode. Intrinsic rewards are computed based on the position of the current state's embedding with respect to the ellipse: the further outside the ellipse, the higher the reward. These are combined with environment rewards, the policy is updated, and the process repeated. The state embeddings are learned using an inverse dynamies model.
F(se, ar) r(r,, ae) 3 b(se), where r(st, de) is the extrinsic reward provided by the environment and [8 is scalar term balancing the tradeoff between exploration and exploitation.
Intuition. One perspective is that the elliptical bonus is natural generalization of count- based episodic bonus [2]. To see this, observe that the problem is tabular and ø is a one-hot encoding of the state, then C--1 will be diagonal matrix whose entries contain the counts corresponding to each state encountered in the episode. Its inverse C_ will also be diagonal matrix whose entries are inverse state visitation counts, and the bilinear form ((st) (7))(s)) reads off the entry corresponding to the current state St. yielding bonus of (sN)
For more general geometric interpretation, (850), ..., (1)-1) are roughly centered at zero, then Ct-1 can be viewed as their unnormalized covariance matrix. Now consider the eigendecomposition the diagonal matrix whose entries are the eigenvalues Ai,... An (these C.-1 UT AU, where
real since C is symmetric). Letting Uő(s,) ) (21, .... 2n, be the set of coordinates of ((st) in the eigenspace of Ct-1, we can rewrite the elliptical bonus as:
2
X
The bonus increases the more ((x)) is aligned with the eigenvectors corresponding to smaller eigenvalues of C.-1 (directions of low data density), and decreases the more it is aligned with eigenvectors corresponding to larger eigenvalues (directions of high data density). An illustration for n 2 shown in Figure 10 of Appendix In our experiments, typically between 256 and 1024.
Efficient Computation. The matrix Ct-1 needs be inverted each step & in the episode, operation which is cubic in the dimension of & and may thus expensive. To address this, we use the
matrix identity [62] to perform fast rank-1 updates in quadratic time:
1
ift
0-1
0 1- dee
ift 2
5

---

This results in an approximately 3x speedup over naive matrix inversion (details in Appendix D.2).
4.2 Learned Feature Encoder
Any feature learning method could in principle be used learn Φ. Here we use the inverse dynamics model approach proposed in [52], which trains model g along with to map each pair of consecutive embeddings ((*+), ((*++1) to distribution over actions a, linking them. our setup, á is separate from the policy network. The y model is trained jointly with ø using the following per-sample loss:
(st, Oes S141: 9) log pppppa((((s))) o(s(+1)))
The motivation is that the mapping 6 will discard information about the environment which is not useful for predicting the agent's 's actions. Previous work [52] has shown that this can make learning more robust to random noise or other parts of the state which are not controllable by the agent.
4.3 Full Algorithm
Putting all of these together, the full algorithm is given below.
Algorithm 1 Exploration via Episodic Elliptical Bonuses (E3B)
Initialize policy т,, feature encoder ó and inverse dynamics model while not converged do Sample context ~ μcc and initial state so ps((lc)
Initialize inverse covariance matrix: C / for t = O,..., T..,Ton do
ag ~ (-1ss)
// Sample action
St+1, P:41 ~ a(-(s,,ai)
// Step through environment
b = 0($+1) Cr @(s++1)
// Compute bonus
u CT ((14()
C = - I+b-11 uu
// Update inverse covariance matrix
Fe+1 T++1 + Bbb+1
end for Perform policy gradient update using rewards fi, Fr-
Update o and g using {(Se, dt, )== T- to minimize the loss:
È = log(p(ee)((((s)) (()++))))
end while
Experiments
5.1
MiniHack Suite
In order probe the capabilities of existing methods and evaluate E3B, we seek CMDP environments which exhibit challenges associated with realistic scenarios, such as sparse rewards, noisy or irrelevant features, and large state spaces. For our first experimental testbed, we opted for the procedurally generated tasks from the MiniHack suite [58], which is itself based on the NetHack Learning Environment [41]. NetHack is notoriously challenging roguelike video game where the agent must navigate through procedurally generated dungeons to recover a magical amulet. The MiniHack tasks contain numerous challenges such finding and using magical objects, navigating through levels while avoiding lava, and fighting monsters. Furthermore, rewards are sparse and as detailed below, the state representation contains a large amount of information, only some of which is relevant for given task.
For all our experiments we use the Torchbeast [40] implementation of IMPALA [23] as our base RL algorithm. For certain skill-based tasks, we restricted the action space to the necessary actions for solving the task at hand, since we found that none of the methods were able to make progress with

---

the full action space (see Appendix C.1.4). See Appendix C.1.3 for environment details and C.1 for other experiment details.
5.1.1 Modalities for Episodic Bonus
The MiniHack environments provide an observation at each step that includes three different modali- ties: i) symbolic image, which indicates the location of the agent, monsters other entities, objects and different types of terrain (such as walls, lava, water); ii) statistics vector which indicates the agent's current (æ, v) location, hit points, time step I, and other features such as strength, dexterity and constitution, and iii) textual message which gives different types of feedback about the environment ("you see key of master thievery", "the wall is solid rock"). These are illustrated in Figure 4.
observation St
We now draw attention to some important subtleties re- garding how existing methods implement count-based episodic bonuses as we will see, these can have a large impact on performance. The works of [56, 25, 76], which use the MiniGrid suite [15] for evaluation, use hash table whose keys are the full observations (in this case symbolic images) encountered by the agent. The occurrences these observations are then counted to compute the episodic bonus. The baselines run in the MiniHack tasks [58], on the other hand, use a hash table whose keys are the (ar, y) positions of the agent, which are extracted from the observation and are then similarly counted to compute the episodic bonus.
message
The door resists!
}30000+
................................
symbolic image
1...))).......
303333>
.
In order to understand the effect of these different in- put modalities count-based episodic bonuses, we consider three variants of the NovelD algorithm, in addition to the original formulation. These methods all have a count-based episodic bonus of the form (oss)) 1]. with different choices of & detailed below.
}333}3
stats vector
34, 1, 14, -. 2, 7, []]
(x, y) position
time step
Figure 4: Observation for MiniHack
NOVELD: in the original version of the algorithm, the identity. Here the input to the count-based episodic bonus is the full state, namely the concatenation of the symbol image, the message and the stats vector. This makes no assumptions about which part of the state is most useful.
NOVELD-POSITION in this variant, é extracts the (æ, y) position of the agent from the statistics vector, which reflects strong inductive bias that the task navigation-based
NOVELD-IMAGE: in this variant, o extracts the symbol image only. This reflects an inductive bias that the message and the stats vector are not useful since they are discarded.
GOVELD-MESSAGE in this variant, é extracts the message only. This reflects an inductive bias that the messages are important but the stats and symbolic images are not.
For E3B, we feed the full state the algorithm and do not make any assumptions about which part is useful for the task at hand. Despite the lack of task-specific inductive biases, our method is still able extract the relevant features for each task, thus outperforming the other exploration approaches (or matching their performance when prior knowledge of the task is used).
5.1.2 Results on MiniHack
Aggregate results for IMPALA, RND, RIDE, ICM, NovelD (with the three variants described above) and E3B over 16 sparse reward tasks from the MiniHack suite are shown in Figure 5. Out of 16 environments, 8 are based on the MiniGrid suite, but use the MiniHack interface and observation space (environment details are included in Appendix 1.3).. We used the performance metrics and bootstrapping protocol from [4] to compute confidence intervals, which are more informative than simple point estimates. We see that over all tasks (top row), E3B outperforms all other methods by significant margin across all three performance metrics.
7

---

Median
IQM
Mean
E3B (ours)
NovelD-message
NovelD-image"
NovelD
All tasks
RIDE
RND
ICM
IMPALA
0.00
0.25
0.50
0.75
0.00
0.25
0.50
0.75
0.0
0.2
0.4
0.6
E3B (ours)
NovelD-message*
NovelD-posittin
NovelD-image"
Navigation-bal tasks only
NovelD RIDE
RND
IMPALA
0.3
0.6
E38 (ours)
NovelD message*
NovelD-
NovelD-Image*
Skill-based tasks only
RIDE
RND
ICM
IMPALA
0.4
0.8
0.0
0.8
0.0
Episode Return
Figure 5: Aggregate results 16 tasks from the MiniHack environment. Bars represent 95% confidence intervals computed using stratified bootstrapping with 5 random seeds. Methods marked with use task-specific prior knowledge.
Standard NOVELD performs poorly due to the fact that the MiniHack observations contain a time counter in the statistics vector (see Figure 4), which makes each observation in the episode unique and hence renders the count-based episodic bonus meaningless. The three NovelD variants which use different features extracted from the state for the count-based bonus perform better. Figure shows aggregate performance across subset of 9 navigation braegattioo-bbsedd tasks (middle row) and killl-basd tasks (bottom row) (see Appendix C.1.3 for the task breakdown). On the navigation based tasks, NOVELD PELD--POSTTON has excellent performance, since visiting large number of different (æ, y) locations is closely aligned with the true task reward. However, NOVELD D-PESTIIO fails on all the skill-based tasks, resulting in poor performance overall. We observe opposite trend for the NOVELDD-ESSAAGE variant, which performs very well on the saiel-based tasks, but poorly on the navigation- ones.
This highlights that although certain inductive biases can help for certain tasks, it is difficult to find one which performs well across all of them. Our method, E3B, performs well on both the navigation-ban based tasks and the skill-based tasks, resulting in superior performance overall. is worth noting that E3B does not require any task-specific engineering: the exact same algorithm is run for all tasks, and it uses the unprocessed states. Results for individual tasks, along with more analysis and discussion, can be found in Appendix D.4.
IQM
E38 (non-episodic)
5.1.3 Ablation Experiments
E3B (random enc.)
E3B (policy enc.)
We next report results for ablation experiments measuring the effects of different algorithmic components of E3B, namely the feature encod- ing and the episodic nature the bonus. Re- sults are shown in Figure 6. E3B (random enc.) indicates E3B where a randomly initialized network which is kept fixed throughout training. E3B (policy enc.) indicates E3B where the weights of & are tied to those of the policy network (with the last layer producing action probabilities removed). E3B (non-episodic) indicates E3B where the
E3B
0.00
0.25
0.50
0.75
Episode Return
Figure 6: MiniHack ablations, bars represent 95% confidence intervals using stratified bootstrapping.

---

elliptical bonus is computed using observations across all timesteps in the lifetime of the agent, and not just the current episode. All three variants perform significantly worse than E3B, which uses an inverse dynamics model encoding for & and an episodic bonus. This highlights that both the inverse dynamics model and episodic bonus are important for success.
5.2 Pixel-Based VizDoom
As our second evaluation testbed, we used the sparse reward, pixel-based VizDoom [37] environments used in prior work [52, 56]. Although these are singleton MDPs, they still constitute challenging exploration problems and probe whether our method scales to continuous high-dimensional pixel- based observations. Results comparing E3B to RIDE, ICM and IMPALA on three versions of the task are shown Figure (hyperparameters can be found in Appendix C.2). IMPALA succeeds on the dense reward task but fails on the two sparse reward ones. E3B is able to solve both versions of the sparse reward task, similar RIDE and ICM.
We emphasize that these are singleton MDPs, where the environment does not change from one episode the next. Therefore, is unsurprising that ICM, which was designed for singleton MDPs, succeeds in this task. RIDE is also able to solve the task, consistent with results from prior work [56]. The fact that E3B also succeeds provides evidence of its robustmess and its applicability settings with pixel-based observations.
WiddemmllyWesttoooeDDeeee
WiddommMyyWaatttoneepaan
episode return
0.4
0.4
0.
0.2
6.-
0.0
-02
-0.2
-02
0.0
0.2
0,4
0.6
1.0
0.2
0.2
0.4
0.5
0.8
1.0
0.4
D2
0.5
0.8
1,5
sleps
Steps
167
steps
IMPALA
RIDE
ICM
E38
Figure 7: Results on pixel-based Vizdoom tasks with dense and sparse rewards. Results are averaged over 5 random seeds, shaded region indicates one standard deviation.
5.3 Reward-free Exploration on Habitat
As our third experimental setting, we investigate reward-free exploration Habitat [59, 69]. Habitat is a platform for embodied research which provides an interface for agents to navigate and act in photorcalistic sim- ulations of real indoor environments. At each episode during training, the agent is initialized a different environment, and it is tested on set of held-out environments not used during training. These experiments are designed to evaluate explo- ration of realistic CMDPs with visually rich observations.
Reward-free exploration
% Map Revealed
We use the HM3D dataset [57], which contains high-quality renditions of 1000 different indoor spaces. As our base RI. algorithu we use DD-PPO [71] and train ICM, RND, NovelD and E3B agents using the intrinsic reward alone. We then eval- uate each agent (as well as two random agents) on unseen test environments by measuring how much of each environment has been revealed by the agent's line of sight over the course of the episode. Full details on the experimental setup can be found in Appendix C.3.
20>
RND E3B
Figure 8: Reward-free exploration on Habitat. Error bars represent std. deviations over seeds.
Quantitative results are shown in Figure 8. The E3B agent reveals significantly more of the test maps than any of the other agents. Trajectories for E3B, ICM, RND and NovelD on one of the test maps shown in Figure 9, which illustrate how E3B explores large portion of the space whereas the

---

others do not. These results provide evidence for E3B's scalability to high-dimensional pixel-base observations, and reinforce its broad applicability.
(a) E3B
(b) ICM
(c) NovelD
(d) RND
Figure 9: Trajectories of policies trained with different exploration algorithms, on Habitat environ- ment unseen during training. E3B reveals larger portion of the map than other methods.
Related Work
Exploration in RL. Exploration remains a long- soan--ttnding problem in RL. Common approaches include e-greedy [68], count- based exploration [66, 8, 48, 45, 70, 43], curiosity- exploration [60, 64, 65, 11]. and other types of intrinsic motivation [49, 50, 63, 1. 12]. These methods were largely designed for singleton MDPs, where the environment remains the same across episodes. As result, they measure novelty over the agent's lifetime static environment rather than on an episodic basis under a distribution of diverse contexts, as necessary in CMDPs. Other intrinsic motivation methods have recently been developed for exploration CMDPs [56, 73, 25, 76). As our experiments show, they critically rely episodic count-based bonuses, which E3B generalizes.
Another class of methods automatically generate curricula over variations of the CMDP encourage efficient learning, effectively performing a form of curiosity- exploration in the context space. These include goal-conditioned [27, 26, 24, 55, 19, 14. 22] and goal-free variants [67. 54, 33, 21]. Unlike our method, these methods assume the ability to actively configure the environment context. In principle, E3B can be combined with these approaches, whereby E3B explores at an episodic level, while the automatic curriculum method explores at context level, making the two complementary.
Elliptical Bonuses. The of elliptical bonuses has long history in the contextual bandit literature [6. 20, 42], which corresponds to the RL setting with single time step. More recently, several works have begun to explore the use of elliptical bonuses the context of multi-step RL. The PC-PG algorithm [2] considers MDPs with linear dynamics and uses an elliptical bonus based on a policy cover explore in provably efficient manner. The ACB algorithm [5] also uses an elliptical bonus, approximated using linear regressors trained on random noise, while FLAMBE [3] uses an elliptical bonus inside a learned dynamics model. All of these algorithms operate on singleton MDPs, whereas ours is designed for contextual MDPs and constructs elliptical bonuses at the episode level rather than across episodes. We also use different feature learning methods, namely inverse dynamics models, instead of the policy encoders, random networks or kernel methods used in the aforementioned works.
7 Conclusion
In this work, we identified a fundamental limitation of existing methods for exploration in CMDPs: their performance relies heavily on episodic count-based term, which is not meaningful when each state is unique. This a common scenario in realistic applications, and it is difficult to alleviate through feature engineering. To remedy this limitation, introduce extends episodic count-based methods to continuous state spaces using an elliptical episodic bonus, as well as inverse dynamics model automatically extract useful features from states. E3B achieves a new state-of-the-art on a wide range of complex tasks from the MiniHack suite, without the need for feature engineering. Our approach also scales to high-dimensional pixel-based environments, demonstrated by the fact that it matches top exploration methods on VizDoom and outperforms them in reward-free exploration on Habitat. Future research directions include experimenting with more advanced feature learning methods, and investigating ways to integrate within-episode and across-ee episode novelty bonuses.
method, E3B, which
10

---

References
[1] Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv:/703.011 2017.
[2] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, (33).
[3] Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: structural complexity and representation learning of low rank mdps. CoRR, abs/2006. 10814, 14, 2020.
[4] Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G Belle- mare. Deep reinforcement learning at the edge of the statistical precipice. Advances in Neural Information Processing Systems, 2021.
[5] Jordan T. Ash, Cyril Zhang, Surbhi Goel, Akshay Krishnamurthy, and Sham M. Kakade. Anti-concentrated confidence bonuses for scalable exploration. CoRR, abs/21 1202, 2021.
[6] Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Jouraall of Machine Learning Research, 3:397-422 March 2002.
[7] Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Victor Valdés, Amir Sadik, et al. Deepmind lab. arXiv preprint arXiv:1612.033801 2016.
[8] Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
[9] 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 P Processing Systems, NIPS' 16, page 1479-144 1487, Red Hook, NY, USA, 2016. Curran Associates Inc.
[10] Ronen Brafman and Moshe Tennenholtz. R-MAX- A general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213-231 2002.
[11] Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. In ICLR, 2019.
[12] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv:1810.12890 2018
[13] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
[14] 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. 12/22, 2020.
[15] Maxime Chevalier-Boisver, Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. https:// hgtggttttuu..... wwwpmaximecc///////c.coo..tttctt hetp///gggmmmiiiiiiieeeeeee 2018.
[16] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[17] Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages
PMLR, 13-18 Jul 2020.
[18] Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1282-1289. PMLR, 09-15 Jun 2019.
[19] Cédric Colas, Tristan Karch, Olivier Sigaud, and Pierre-Y Oudeyer. Intrinsically motivated goal-conditioned reinforcement learning: a short survey. ArXiv, abs/20 099300 2020.
11

---

[20] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In COLT, 2008.
[21] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances in Neural Information Processing Systems, 33:1 3049-13061, 2020.
[22] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXivv:901. 2019.
[23] 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. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Jennifer G. Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässaan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1406-1415. PMLR, 2018.
[24] Meng Fang. Tianyi Zhou. Yali Du, Lei Han, and Zhengyou Zhang. Curriculum-guuin guided hindsight experience replay. In NeurlPS, 2019.
[25] Yannis Flet-Berliae, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adver- sarially guided actor-critic. CoRR, abs/2102.04376. 2021.
[26] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In Conference on robot learning, pages 482-495. PMLR, 2017.
[27] Séhastien Forestier, Rémy Portelas, Yoan Mollard, and Pierre- Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. arXiv preprint 17X1v: 2017.
[28] 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 arXiv:2007.04954 2020.
[29] Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint arXiv:2109.06780 2021.
[30] Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv:1502.022555 022.999, 2015.
[31] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image 2015.
recognition. arXiv preprint
[32] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation. 9()):1735-1780, 1997.
[33] Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized level replay. In Interna- tional Conference on Machine Learning, pages 4940-4950. PMLR, 2021.
[34] Arthur Juliani, Ahmed Khalifa, Vincent-Pierre Berges, Jonathan Harper, Hunter Henry, Adam Crespi, Julian Togelius, and Danny Lange. Obstacle tower: A generalization challenge in vision, control, and planning. CORR, abs/1902.01377. 2019.
[35] 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//806. 0e////86.11772 10729, 2018.
[36] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. In Machine Learning, pages 209-232. Morgan Kaufmann, 2002.
[37] Michat Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaškowski. ViZDoom: A Doom-based Al research platform for visual reinforcement learning. In IEEE Conference on Computational Intelligence and Games, pages 341-348 Santorini, Greece, Sep 2016. IEFE. The best paper award.
[38] Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of generalisation in deep reinforcement learning. CoRR, abs/2111.0979. 2021.
12

---

[39]
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of generalisation deep reinforcement learning. CoRR, abs/21 11 1..09794, 2021.
[40] Heinrich Küttler, Nantas Nardelli, Thibaut Lavril, Marco Selvatici, Viswanath Sivakumar, Tim Rocktäschel. and Edward Grefenstette. Torchbeast: A pytorch platform for distributed RL. CoRR, abs/1910.03552, 2019.
[41] 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.
[42] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual- approach to personalized news article recommendation. In Michael Rappa, Paul Jones, Juliana Freire, and Soumen Chakrabarti, editors, WWW. pages 661-670. ACM, 2010.
[43] Marlos C Machado, Marc G Bellemare, and Michael Bowling. Count-based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5125-5133, 2020.
[44]
Prasanta Chandra Mahalanobis. On the generalized distance in statistics. Proceedings of the National Institute of Sciences (Calculta), 2:49-55, 1936.
[45] Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, and Marcus Hutter. Count-bass exploration in feature space for reinforcement learning. arXiv preprint arXiv:1706.080 080900 2017.
[46] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-levee control through deep reinforcement learning. Nature, (177540):559-55333 February 2015.
[47] Jesse Mu, Victor Zhong, Roberta Raileanu, Minqi Jiang, Noah D. Goodman, Tim Rocktäschel, and Edward Grefenstette. Improving intrinsic exploration with language abstractions. CoRR, abs/2202.08933 2022.
[48] Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference on machine learning, pages 2721-2730.
PMLR, 2017.
[49] Pierre-Y Yves Oudeyer, Frdric Kaplan, and Verena Hafner. Intrinsic motivation systems for autonomous mental development. IEEE transactions evolutionary computation, 11(2):265- 286, 2007.
[50] Pierre Yves Oudeyer and Frederic Kaplan. What is intrinsic motivation? typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
[51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[52] Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven explo- ration by self-supervised prediction. CORR, abs/1705.0525 003633 2017.
[53] Aleksei Petrenko, Erik Wijmans, Brennan Shacklett, and Vladlen Koltun. Megaverse: Simulat- ing embodied agents at one million experiences per second. In International Conference on Machine Learning, pages 8556-8566. PMLR, 2021.
[54] Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In CoRL, 2019.
[55] Sébastien Racanière, Andrew Kyle Lampinen, Adam Santoro, David P. Reichert, Vlad Firoiu, and Timothy P. Lillicrap. Automated curricula through setter-solver interactions. ArXiv, abs/1909. 12892. 2019.
[56) Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally-genere environments. In International Conference on Learning Representations, 2020.
13

---

[57] 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-matterport 3d dataset (HM3d): 1000 large-scale 3d environments for embodied AI. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[58] Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, 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.
[59] 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 on Computer Vision (ICCV), 2019.
[60] Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neural controllers. In Proc. of the international conference on simulation of adaptive behavior: From animals to animats, pages 222-227, 1991.
[61] Bokui Shen, Fei Xia, Chengshu Li, Roberto Martín-Martin, Linxi Fan, Guanzhi Wang, Claudia Pérez-D' Arpino, Shyamal Buch, Sanjana Srivastava, Lyne Tchapmi, et al. igibson 1.0: A simulation environment for interactive tasks in large realistic scenes. In 2021 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 7520-7527. IEEE, 2020.
[62] Sherman and W. J. Morrison. Adjustment of an inverse matrix corresponding to change in one element of a given matrix. Ann. Math. Stat., 21(1):124-127, 1950.
[63] Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint 0rxiv:1507.008/1 2015.
[64] Christopher Stanton and Jeff Clune. Curiosity search: Producing generalists by encouraging individuals to continually explore and acquire skills throughout their lifetime. PLOS ONE, 1 199:11220, 09 2016.
[65] Christopher Stanton and Jeff Clune. Deep curiosity search: Intra-life exploration improves performance on challenging deep reinforcement learning problems. CoRR, wws/1800..eao 005503 2018.
[66] Alexander L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-133 -131,, 2008.
[67] Sainbayar Sukhbaatar, Ilya Kostrikov, Arthur D. Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. ArXiv, abs/1703.05440 2018.
[68] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[69] Andrew Szot, Alex Clegg, Eric Undersander, Erik Wijmans, Yili Zhao, John Turner, Noah Maestre, Mustafa Mukadam, Devendra Chaplot, Oleksandr Maksymets. Aaron Gokaslan, Vladimir Vondrus, Sameer Dharur, Franziska Meier, Wojeiech 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 (NeurlPS), 2021.
[70] Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
[71] Erik Wijmans, Abhishek Kadian, Ari S. Morcos, Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. Dd-ppo: Learning near pear-perfect pointgoal navigators from 2.5 billion frames. In ICLR, 2020.
[72] Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanxiao Jiang, Yifu Yuan, He Wang, et al. Sapien: A simulated past-based interactive en- vironment. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 11097-11107, 2020.
14

---

[73] Daochen Zha, Wenye Ma, Lei Yuan, Xia Hu, and Ji Liu. Rank the episodes: A simple approach
for exploration sereeduurlly-generttee environments. arXiv preprint arXiv:2101.08152. 2021.
[74] Amy Zhang, Nicolas Ballas, and Joelle Pineau. A dissection of overfitting and generalization in continuous reinforcement learning. arXiv preprint arXiv: /t06:08800.9955 2018.
[75] Chiyuan Zhang, Oriol Vinyals, Rémi Munos, and Samy Bengio. A study overfitting in deep reinforcement learning. CoRR, boss/1844006833, 2018.
[76] Tianjun Zhang, Huazhe Xu, Xiaolong Wang. Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuandong Tian. Noveld: A simple yet effective exploration criterion. In A. Beygelzimer, Dauphin, Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss how our method (as
well as existing methods) are not able to solve MiniHack tasks with large action spaces in Section 5 as well as Appendix C.1.4.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix A.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yess] We included the code with instructions in the supplement, and will release the code on GitHub upon acceptance.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We use the rliable library to compute error bars using stratified bootstrapping in Figure 5.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C.1.5.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cited all the codebases we built upon, see Section C.4.
(b) Did you mention the license of the assets? [Yes] We mentioned all licenses associated with the codebases we used, see Section C.4.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] All of our code is included in our code release.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "iy3rlnYOSV", "reviewer": "Reviewer_rjcQ", "summary": "The paper proposes a method that alternates between learning the feature mapping via the inverse dynamics model and using the learned feature to construct the elliptical bonus for exploration. The paper also analyzes several heuristic exploration bonus method by removing the count-based component in them and shows that they fail under such modification. The paper claims that the proposed algorithm contributes the most to the contextual markov decision processes (CMDP) setting, and shows its empirical competitiveness in the MiniHack benchmark. ", "questions": "1. In figure 1, why are the baselines not performing well even with their original constructions (with counts)?\n\n2. The motivation against using counting based method seems not very fair? \"if each state is unique\" (line 102) almost implies that the state space is continuous, then one obviously should never use naive count-based bonus, since count-based bonus only works for tabular MDP. \n\n3. In the feature learning part, it is known that the inverse dynamics model is valid only if it is conditioned on some conditional distributions of actions (for example, policies). In the proposed algorithm, is the conditioned policy being a mixture of all previous policies? Would it providing conflicting information, for example, at some state policy a goes left and policy b goes right? Since the algorithm aims to perform exploration.\n\n4. In result shown in Fig.6, is there any hypothesis why RND completely fails on all tasks?\n\n5. The ablation shown in section 5.1.3 is not using very strong baselines. For example, in [1,2,4], those method are using RFF kernels and random networks like RND as feature mappings, which show convincing empirical performance. \n\n6. In Fig.8, is there any possible explanation for why E3B is worse than the baselines in some task? ", "limitations": "1. As mentioned in the previous section, resetting the covariance matrix seems a limitation of the proposed work. \n\n2. The results shown in Section 5.2 shows that the proposed algorithm achieves very limited improvement or even no improvement than previous algorithms on regular MDPs with large state space.  ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n\n1. The proposed method, E3B, when evaluated in the MiniHack benchmark, which is a reasonable benchmark for CMDP, shows better performance than the previous empirical methods with heuristic exploration bonuses. The evaluation also contains some variants of the baselines to provide more insights into the results. \n\n2. The paper is easy to follow with several informative visualizations. \n\n## Weakness\n\n1. It is very surprising to see that the proposed algorithm, which resets the empirical covariance matrix at the beginning of the episode (according to Algorithm.1), can actually work. First, this should not work in theory, where your covariance matrix $C$ is constructed using the policy cover defined on all previous iterations. Intuitively, it is also not very clear why this can work effectively. Resetting $C$ at the beginning of the episode means the bonus construction has no memory of what states have already been visited before. Combined with that the algorithm performs policy optimization based on reward + bonus, consider the setting if we have sparse reward and short horizon: for example, if one wants to escape a maze in small time budget, the algorithm could first visit some dead end, but receives high bonuses due to resetting $C$, and update to visit the dead end with higher probability after the PG update, and visit the dead end again but still receives high bonus, and thus eventually stuck?\n\n2. The contribution of this work does not seem obvious, either. Using elliptical bonus in Deep RL or with neural network function approximation has already studied by some previous work. For example, PC-PG [1] (which this paper also mentions) actually uses PPO+elliptical bonus in their experiment. [2] even has a specific Deep RL version that uses deep RL + elliptical bonus and is evaluated in the deep RL benchmarks. If we also consider the representation learning part, [3] provides both theoretical and empirical results with neural network function approximation. In addition, [4] also justifies that a variant of [2] is actually performing feature learning in a noisy system. There seems no comparison against any of these works in this paper, given that the approaches are similar and the above baselines actually also show strong performance in practice.\n\n### references\n\n[1] Agarwal, Alekh, et al. \"Pc-pg: Policy cover directed exploration for provable policy gradient learning.\" Advances in neural information processing systems 33 (2020): 13399-13412.\n\n[2] Song, Yuda, and Wen Sun. \"Pc-mlp: Model-based reinforcement learning with policy cover guided exploration.\" International Conference on Machine Learning. PMLR, 2021.\n\n[3] Xu, Pan, et al. \"Neural contextual bandits with deep representation and shallow exploration.\" arXiv preprint arXiv:2012.01780 (2020).\n\n[4] Ren, Tongzheng, et al. \"A free lunch from the noise: Provable and practical exploration for representation learning.\" arXiv preprint arXiv:2111.11485 (2021).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Cmjqk5R2P6U", "reviewer": "Reviewer_TeH7", "summary": "This work highlights an important weakness for existing exploration methods relying on intrinsic motivation in CMDPS, namely their over reliance on a count-based episodic term. Since this count-based term is computed on hand-engineered features, or on the entire observation, such methods underperform in noisy or more realistic environments. The authors propose to replace this term with an elliptical episodic bonus, computed on learned features extracted by inverse dynamic modeling. This simple modification significantly improves the performance of intrinsically motivated agents in complex environment which differ across episodes. This is shown through experiments on the MiniHack suite, and potential for scaling to image-based tasks is presented on VizDoom. The authors also report some interesting nuances in environments, and clarify the importance of heuristic choices in existing methods.", "questions": "**Main comments**\n* The method's clarity can be improved. While the computation of the elliptical bonus is clear, its integration in the reward signal is not. This should be clearly discussed in the main body of the paper. Furthermore, to the best of my undestanding, E3B's reward only includes an episodic term, while RIDE, AGAC and NovelD also include a global term. While the lack of robustness in the episodic term is understandable, it is not clear why E3B also removes the global term.\n* I would suggest author to ablate the method by replacing the elliptical terms with a hash-based count term [1], which can be computed over the representations learned through inverse modeling.\n* The choice of MiniHack tasks is not well motivated. I am not fully informed on common evaluation protocols on MiniHack, but to my understanding the authors performed a selection of tasks. The reasoning behind this selection should be motivated, particularly in relation to prior works.\n* Figure 6 shows how RIDE does not achieve any reward signal in any of the tasks considered. Can the authors provide an intuitive explaination for this result?\n\n**Minor comments**\n* line 50: Prior works on elliptical bonuses should be cited before the Related Works section on the last page. I would suggest to add them here, in order to clarify that this idea is not novel.\n* lines 83-85: I would recommend adding references to NovelD and AGAC to better assist the reader.\n* Figure 1: What is the behavior of each agent when disabling the count-based episodic bonus? Is their explorative behavior less extended, or do they fail to move at all?\n* line 123: This experiment is only reported for NovelD, but the reasoning for this choice is only provided on line 243. I would recommend to move this explanation here.\n* line 176: Why is $n$ not fixed across all experiments? How is its value selected?\n\n**References**\n\n[1] Haoran et al. \"#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning.\", 2017", "limitations": "The authors do not overstate their contribution, and the limitations of their work are properly presented.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n* The claims made through the paper are modest, but well argued and sufficiently supported by experimental results.\n* The paper is well written and easy to follow. The motivating weakness of existing methods is outlined well, and the idea of elliptical bonuses is clearly presented, and motivated from different point of views.\n* The experimental section is convincing: the metrics reported follow a statistically principled evaluation approach, baselines are satisfactory and their behavior is well explained.\n\n**Weaknesses**\n* While the motivation and the intuition of the method are clear, the main body of the paper does not explicitly describe the algorithm itself, which is relegated to the Appendix. As a result, this part of the paper is lacking in clarity.\n* The method is not particularly original, as it can be seen as an incremental generalization of count-based exploration bonuses to continuous settings.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9Hzh34aJrNh", "reviewer": "Reviewer_yKuH", "summary": "The paper gives evidence of the importance of the pseudo count quantity used in existing exploration algorithms in RL, and proposes a new algorithm to extend the pseudo count idea to continuous state spaces by also proposing a method to learn a feature encoder. They give this evidence through various empirical experiments.\n\nThanks to the authors for putting in the effort in doing this work!", "questions": "Questions/Suggestions:\n- How are differences between contexts defined? I see that there is a distribution over contexts but how extreme can differences between two contexts be? It doesn't appear to be the case here, but generally does the reward function change between contexts too?\nHow many samples are actually needed for fitting in the ellipse? \n- The paper also notes that “any feature learning method” could be used, but it proposes to use the inverse dynamics model. I am curious how off-the-shelf feature extractors perform with the elliptical exploration algorithm? It seems like this problem is an independent problem itself, and it would make sense to leverage existing works instead of re-inventing something new.\n- How sensitive are results to the regularization term in Equation (1)? In my experience, I have found this term to be sensitive.\n- I know the goal isn't explicitly lifelong learning, but I am curious what the authors think about getting E3B (non-episodic) from Figure 7 to work in that setting? In a lifelong setting where the agent is constantly interacting with no clear start and end to different contexts, I wonder how the proposed method would work then and how it compares to existing methods?\n- So we can see a clear performance improvement in Figure 6. But I am curious why ICM performs similarly to E3B on the high-dimensional Vizdoom domain, especially given that the motivation was current methods don’t fare well in high dimensional/continuous state spaces?\n- How will the count-based methods in Table 1 improve or change if you use the proposed feature encoder (inverse dynamics model) as input into these existing exploration methods instead of using the proposed elliptical count-based algorithm?\n", "limitations": "Yes, they have.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- I appreciate works that take a hard look at existing methods in the manner that is done in this paper and try to understand the fundamental flaws.\n- I like table 1 of distilling the exploration methods to their essence, and also I like figure 3.\n- The time-counter example of how states can appear unique is a nice one for intuition.\n- The paper is generally well-written and easy to follow.\n\nWeaknesses:\n- I view the paper as trying to solve two independent problems, but the paper makes it seem they are intrinsically tied together. The two problems are: 1) learning a feature encoder and 2) exploration. While the paper does include an ablation study showing how important both these parts are, it would be nice to get a better understanding of these two independent components. For example, how does using the learned encoder improve other existing count-based methods, or how does using off-the-shelf feature encoders affect the performance of the elliptical exploration algorithm?\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept