Deep exploration by novelty-pursuit with maximum state entropy
Authors: Zi-Niu Li
Xiong-Hui Chen
Yang Yu
Venue:  (2020)
Keywords: Exploration
Reinforcement Learning

Abstract: Efficient exploration is essential to reinforcement learning in huge state space. Recent approaches to address this issue include the intrinsically motivated goal exploration process (IMGEP) and the maximum state entropy exploration (MSEE). In this paper, we disclose that goal-conditioned exploration behaviors in IMGEP can also maximize the state entropy, which bridges the IMGEP and the MSEE. From this connection, we propose a maximum entropy criterion for goal selection in goal-conditioned exploration, which results in the new exploration method novelty-pursuit. Novelty-pursuit performs the exploration in two stages: first, it selects a goal for the goal-conditioned exploration policy to reach the boundary of the explored region; then, it takes random actions to explore the non-explored region. We demonstrate the effectiveness of the proposed method in environments from simple maze environments, Mujoco tasks, to the long-horizon video game of SuperMarioBros. Experiment results show that the proposed method outperforms the state-of-the-art approaches that use curiosity-driven exploration.

Under review as a conference paper at ICLR 2020
DEEP EXPLORATION BY NOVBLTY-PURSUIT WITH MAXIMUM STATE ENTROPY
Anonymous authors Paper under double-blind review
ABSTRACT
Efficient exploration is essential to reinforcement learning in huge state space. Re- cent approaches to address this issue include the intrinsically motivated goal ex- ploration process (IMGEP) and the maximum state entropy exploration (MSEE). this paper, we disclose that goal-conditioned exploration behaviors IMGEP can also maximize the state entropy, which bridges the IMGEP and the MSEE From this connection, we propose a maximum entropy criterion for goal selec- tion in goal-conditioned exploration, which results in the new exploration method novelty-pursuit. Novelty-pursut performs the exploration in two stages: first, it selects goal for the coal-conditioned exploration policy reach the boundary of the explored region; then, it takes random actions to explore the non-explored region. We demonstrate the effectiveness of the proposed method in environments from simple maze environments, Mujoco tasks, to the long-horizon video game of SuperMarioBros. Experiment results show that the proposed method outperforms the state-of- oate--of-the-at approaches that use curiosity-driven exploration.
INTRODUCTION
Efficient exploration is important to learn (near-) optimal policy for reinforcement learning (RL) in huge state space (Sutton & Barro, (198). Dithering strategies like ppsilon-greedy, Gaussian action noise, and Boltzmann exploration are inefficient and require exponential interactions to explore the whole state space. In contrast, deep exploration (Osband al. 2016) overcomes this dilemma temporally extended behaviors with a long-term vision. Recently, proposed methods include the in- trinsically motivated goal exploration process (IMGEP) (Forestier et all, 2017), and maximum state entropy exploration (MSEE) (Hazan et all 2UD). In particular, IMGEP selects interesting states from the experience buffer as goals for a goal-conditioeed exploration policy. In this way, explo- via accomplishing self- celf-generated goals. On the
ration behaviors are naturally temporally-extennde other hand, MSEE aims to search for a policy such that maximizes the entropy of state distribution. In this way, the agent can escape from the local optimum caused by insufficient state exploration.
In this paper, we show that the target of maximizing the support of state distribution (discovering new states) and maximizing the entropy of state distribution (unifying visited state distribution) can be both achieved by the goal-conditioned policy. From this connection, we propose an exploration method called novelty-pursuit. Abstractly, our method performs in two stages: first, it selects visited state with the least visitation counts as the goal to reach the boundary of the explored region; then, it takes random actions explore the non-explored region. An illustration can be seen in Figure M. Intuitively. this process is efficient since the agent avoids exploring within the explored region. Besides, the exploration boundary will be expanded further as more and more new states are discovered. Finally, the agent will probably explore the whole state space to find the optimal policy.
naive implementation of the above strategies can lead to inefficient exploration and exploitation on complex environments. First, to tackle the problem of the curse of dimension and exhaustive stor- age when selecting the least visited states, we approximate the visitation counts via prediction errors given by Random Network Distillation (Burda et all MMDNN. Besides, we observe that previous methods used in IMGEP (Eoresther et all 2012Z) are inefficient to train the goal-come condalioni explo- ration policy. We employ training techniques based reward shaping (Ng et ali, (1999) and HER (Andrychowıcz et al, 2012) to accelerate training the goal-conditioned policy. Finally, we addition- ally train unconditioned exploitation policy utilize samples collected by the goal-conditioned

---

Under review as a conference paper at ICLR 2020
Goal-condition Action
Random Action
Non-explored Region
Explored Region
Origin
Figure I: Illustration for the proposed method. A goal-conditioned policy firstly reaches the explo- ration boundary, then perform random actions discover new states.
exploration policy with environment-specific rewards. Thus, the exploration and exploitation is de- coupled in our method.
Our contributions are summarized as follows: (1) We disclose that goal-conditioned behaviors can also maximize the state entropy, which bridges the intrinsically motivated goal exploration process and the maximum state entropy explore. (2) We propose method called novelty-pursuit from this connection and give practical implementations.
(3) We demonstrate the exploration efficiency of the proposed method and achieve better performance on environments from the maze, Mujoco tasks, to long-horizon video games of Surerraaioorrs.
2 BACKGROUND
Reinforcement Learning. In the standard reinforcement learning framework (Suiton & Barto, 1998) learning agent interacts with Markov Decision Process (MDP). The sequential decision process is characterized as follows: at each time I, the agent receives state from the environment and selects an action o, from policy T(s, a) = Pr(a az|s s = se): that decision is sent back to the environment, and the environment gives reward signal r(st, a.) and transits to the next state $141 based on the state transition probability p". = Pr(s' = $1+1|s = St, a = a.}- This process repeats until the agent encounters terminal state after which the process restarts. The main target of reinforcement learning is to maximize the expected discounted return E- +>> t=o rrr in an unknown environment, where 7 (0, 1] is factor that balances the importance of future reward. Without information about environment dynamics and task-specific rewards in advance, the agent needs ex- ploration discover potential valuable states. Apparently, the learned policy may be sub-optimal if the exploration strategy cannot lead to explore the whole state space.
Intrinsically Motivated Goal Exploration Process. Intrinsically motivated goal exploration pro- cess (IMGEP) (Baranes & Oudeyer, 2019 Forester et all (01Z) relies on a goal-conditioned (or ggal-parameterizze) policy Tg for unsupervised exploration. It involves the following steps: 1) se- lecting an intrinsic or interesting state from the experience buffer as the desired goal; 2) exploring with goal-conditioned policy Hy (s. a. g) Pr(a; = als; s, 9: = g}: 3) reusing experience for a st 3} to maximize the external reward. Note that the
an exploitaion policy (s a) = Pr(a. performance of exploitation policy मe relies on samples collected by the goal-exploration policy Tg. Thus, the criterion of goal selection is crucial for IMGEP.
Maximum State Entropy Exploration. Maximum state entropy exploration Hazan cf al (ALS) aims to search exploration policy x² such that it maximizes the entropy of induced state distri- bution (or minimizes the KL-divergence between the uniform distribution and induced state distri- bution) among the class of stationary policies (i.e., x² arg max, H[dz], where d, is the state distribution induced by π). Without any information about tasks given by the environment, we think maximum state entropy exploration is safe for exploitation.
IMGEP WITH MAXIMUM STATE ENTROPY EXPLORATION
In this section, bridge the intrinsically motivated goal exploration process and maximum state entropy exploration. We begin with practical considerations when maximizing state entropy, then analyze the exploration characteristics of the proposed goal-selection method for IMGEP
2

---

Under review as a conference paper at ICLR 2020
In practice, exact density estimator for high-dimension state space is intractable, and the state space unknown, which leads to an empirical state distribution over visited states. The differences important. For example, directly optimizing the entropy of empirical state distribution over visited states is not what we want, because ignores the non-visited states outside of the empirical state distribution (see the top row in Fig (). Instead, induced state distribution (i.c., discovering new states), then we maximize the entropy of induced state distribution with full support (see the bottom row in Fig (). In the following, we demonstrate that selecting the states with the least visitation counts among visited states as goals can achieve the above functions under some assumptions.
need to first maximize the support of
0.20
0.20
0.15
0.35
derstry
Max Entropy
0.05
0.05
0.00
state index
dersity
0.15
Max Support
cersity
0.15
Max Entropy
0.15
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0
100
0.00
25
50
300
0.00
255
50
300
state index
state index
State Index
Figure 2: Histograms for normalized state visitation counts, where the z-axis represents the index of state. Top row: directly maximizing the entropy of empirical state distribution over visited states; Bottom row: firstly maximizing the counting measure of induced state distribution support, then maximizing the entropy of state distribution with full support.
; Let the set 21,2..-. [S]] denotes the state space S, I denotes the set of policies { "", over previous iterations, T++1 denotes the policy of next iteration, x denotes the cumulative visi- tation counts state i induced by history policies TI:ts and N, = = st denotes the sum of all state visitation counts. Hence, the entropy of empirical state distribution induced by policies th zi defined as H d.. (s) = 18| N. log N.
(H, for short), and the counting measure of empirical
state distribution support induced by policies mia is defined as pldda.. (x)
T(x 2 1) (fr
for short), where is the indicator function.
The theoretical analysis starts with the situation that each iteration the goal-conditioned exploration policy can only select a state visit without consideration of trajectories towards the goal. Our question is which state to visit gives the most benefits in terms of maximum state entropy. This question closely related to the goal generation IMGEP. To facilitate the analysis, let the unit
vector [0,... 1, 1,...] RRIS denotes choice (i.e., e(i) 1 indicates that the policy selects i-th state to visit). Note that 2:+1 24 e, with this assumption.
Proposition (Max Counting Measure of Support) For any state (L,....,1ST with æt 2 0. unless the unvisited state sets K = { 0} is an empty set, any choice e, such that ex with x = 0, we have μe+1 = Pr +
This Proposition states visiting the non-visited states is to maximize the counting measure of induced state distribution support. The agent improves its policy by discovering new valuable states. In practical applications, we don't 't have access to non-visited states in advance. In other words, we can't select these non-visited states as goals since they are not contained in the experience buffer. To deal with this problem, we assume that the chance of discovering non-visited states is high when the agent perform random actions to explore around the exploration boundary. The exploration boundary can be understood as the set of visited states with the least visitation counts (See Figure II for the illustration). Our assumption is based on the fact that the total visitations counts of the visited region are large and the total visitation counts of the non-visited region small. In conclusion, the coal-conditioned exploration policy is asked to reach the exploration boundary, then it performs random actions to discover states maximize the counting measure.
3

---

Under review as a conference paper at ICLR 2020
Theorem (Max Entropy) For any state i E {1,... |8|] with at 2 1; for any choice ej such that ej with i arg minj dy we have ef E arg m H441-
We provide the proof in the appendix states with the least visitations when the whole state space has been explored (i.e., the stage after maximizing the counting measure of induced state distribution support). Since Theorem still suggests selecting states with the least visitation counts as goals, the above method
Theorem characterizes the behavior of visiting the
also be applied to maximize the entropy of induced state distribution. Actually, it is easy to unify the two stages via smoothed entropy H. (dx) = -E,, [loy(dz) +o] (Hazan et all, 2019). For our problem, the definition of entropy is proper by assigning non-visited states with a "dummy" visitation counts between 0 and In that case, Theorem M still holds and suggests firstly selecting these non-visited states and subsequently selecting the states with least visitation counts to maximize the smoothed state entropy.
The proposed exploration method is called novelty-pursuit. We notice that the above analysis neglects the influences of trajectories towards the exploration boundary. However, the fluctuation of state distribution entropy by the trajectories towards the exploration boundary is less significant from practical considerations. exploration boundary quickly and pays more efforts to discover new states around the exploration boundary, as our experiment results in Section 5 indicate.
fact, the goal-conditioned policy should be trained to reach the
METHOD
In this section, we present practical implementations for the proposed method. How to approximate visitation counts in high-dimension space and how to estimate the exploration boundary is given in Section 8.1 We describe the training technique of goal-conditioned policy in Section H.21 Fi- nally, we introduce exploitation policy to learn the experience collected by the goal-conditioned exploration policy in Section
We outline the proposed exploration method Algorithm II.
4.1 APPROXIMATING EXPLORATION BOUNDARY
SPACE
Generally, computing the visitation counts in high-dimension space is intractable. However, it is possible to build some variables related to the visitation counts. For example, Burda (201M)) show that prediction errors given by two randomly initialized network have strong relationship to the number of training samples on the MNIST dataset. Thus, we can use the prediction errors sort visited states. Other approaches like pseudo-counts (Bellemare et all, 2016; Ostrovski.et et all, 2017) can be also applied, but we find that RND is easy to scale up.
RND is consist of two randomly initialized neural networks: a fixed network called target network (x),,, and trainable network called predictor networkf(2;wp)) Both two networks take a state s as input and output a vector with the same dimension. Each time a batch of data feeds into the predictor network minimize the difference between the predictor network and the target network concerning the predictor network's parameters, shown in Equation II.
min up
Σ (f - (ss
In practice, we employ an online learning setting to train RND and maintain priority queue to store states with the highest prediction errors. In particular, after goal-conditioned policy collects a mini-batch of transitions, this data feed to train the predictor network. Also, a state with high prediction error will be stored into the priority queue and the state with the least prediction error will be removed out of the priority queue if full. This process repeats and no historical data will be reused to train the predictor network. Besides, each iteration a state will be selected from the priority queue a goal for the condiiondd policy. After achieving the goal, the exploration policy will perform random actions to discover new states. Consider the bias due to approximation, we sample goals from distribution based their prediction errors (e.g., softmax distribution).
4

---

Under review as a conference paper at ICLR 2020
Algorithm Exploration by novelty-pursuit
predictor network update interval K; goal-conditioned policy update interval M; mini- batch size of samples for goal-conditioned policy N;
Input:
Initialize parameter for goal-conditioned exploration policy Ty(5, g, a: a)
Initialize parameter wi for target network f(;; wi), and wpp for predictor network (a;; wp).
Initialize buffer Dy for Tg. and priority queue Q store states with least visitation counts. for each iteration do
Reset the environment and get the observation oo: Choose a goal g from priority queue Q, and set gool success = False; for each timestep do
if gool suuccss = True then
Choose an random action a,; # Explore around the exploration boundary else
Choose an action a, from (st, 9, ax; 0): # Go to the exploration boundary end if
Send Ge to the environment and get rf; 8t+1;
Update sual_success((( (usccess($(11.000 9);;
# Store new states and update the predictor network if % K = then
Store transitions (*k. 9, Ok Filk=ee into replay buffer Dg:
Calculate prediction errors for {&x {s and store them into priority queue Q;
Update predictor network f (a; using {8 end if
# Update Ty with reward shaping
if % M = 0 then
Update Tg with {sk, Ik. ag2 K sampled from Dy: end if end for end for
4.2 TRAINING GOAL-CONDITIONED POLICY EFFICIENTLY
Before deseribe the training techniques for the goal-conditioned policy, we emphasize that train- ing this policy doesn't require the external reward signal from the environment. But we additionally the external reward for the goal-conditioned policy to reduce the mismatch behaviors between the goal-conditioned policy Ty and the exploitation policy Ne-
Following multi-goal reinforcement learning (Andrychowicz al, 2012: Plappert al. (и
manually extract goal information from state space. Specifically, each state s is associated with an achieved goal of ag, and the desired goal is denoted as g. To avoid ambiguity, a goal-conditioned policy xy (s, a, g: 8 is asked to accomplish a desired goal g. For our settings, the achieved goal is coordinate information.
ragt-- 9.) = {{
1 if d(agt, 9r) <e
(2)
otherwise
A proper reward function for the goal-conditioned policy is an indicator function with some tol- erance, shown in Equation 2 With little abuse of notations, between the achieved goal ag and the desired goal we use d(ag.g) to denote some "distance" (c.g.. L1 or L2 norm) between the achieved goal ag and the desired goal g. If the distance less than some threshold e, the goal- conditioned policy receives a positive reward otherwise zero. Note that this function is also be used to judge whether agents reach the exploration boundary. However, the training of goal-conditioned policy is slow with this sparse reward function. Next, we introduce some techniques to deal with this problem.
r(agt: 9t) d(agt-1.9:) d(agt,9:)
Reward shaping introduces additional training rewards guide the agent. Reward shaping is in- variant to the optimal policy if shaping reward function is a potential function (g et al. (999).
With the respect of input goal-conditioned policy, contains ag keep notations simple.
5

---

Under review as a conference paper at ICLR 2020
Specifically, we define the difference of two consecutive distances (between the achieved goal and the desired goal) as shaping reward function, shown in Equation BL Since shaping reward function is dense, it lead substantial reductions in learning time. Verification of the optimal goal- conditioned policy is invariant between this function and the indicator reward function is given in Appendix A. Alternatively, one
also Hindsight Experience Replay (HER) (Andrychowicz atal ))) to train the goal-conditioned policy via replacing each episode with an achieved goal rather than one that the agent was trying to achieve. But one should be careful since HER changes the goal distribution for learning. Besides, one can also utilize past trajectories to accelerate training, which we discuss in Appendix
4.3 EXPLOITING EXPERIENCE FROM EXPLORATION POLICY
Parallel to the goal-conditioned exploration, we additionally train an unconditioned exploitation policy Te, which only takes the state input. This policy learn from experience collected by the exploration policy Ty in an pollcc learning fashion. At the same time, the exploitation policy also interacts with the environment to mitigate the side effect of exploration error (Fujimoto all, 2019), a phenomenon that off-policy learning degenerates when data from the exploration policy is not correlated the experience generated by the exploitation policy. Note that exploitation policy is trained with an RL objective to maximize expected discounted external return. Therefore, the exploration and exploitation are naturally decoupled, which turns out to help escape the local opti- mum on SuperMariooros environments. From this perspective, our method is distinguished from Go Go-Explore Ecottet et (2019), which employs exploration followed by exploitation.
5 EXPERIMENT
In this section, we aim to answer the following research questions: 1) Does novelty-pune pursuit effec- tively maximize the state entropy? 2) Do the proposed goal-selection criterion and training tech- niques improve performance for IMGEP? 3) How does the performance of novelty-puree pursuit compare with the state-of-the-ard approaches in complex environments? We conduct experiments from the simple maze environments, Mujoco tasks, to long-horizon video games of SuperMarioBros to eval- uate the proposed method. Detailed policy network architecture and hyperparameters are given in Appendix A.A and A.A respectively.
Here we briefly describe the environment settings (see Figure K for illustrations). Detailed settings given in the Appendix A.5l
An agent navigates in the maze of 17 x 17 to find the exit Chevalieez Boisert et all 20I8). The agent receives time penalty until it finds the exit and receives a positive reward. The maximum return for both two environments is +1, and the minimum total reward is -1. Note that the observation is partial image of shape (7, 3).
Empty Room & Four Rooms.
FetchReach. A 7-DOF Fetch Robotics arm (simulated in the Mujaco (Lodorov et all, 201 2)) is
asked to grip spheres above table. There are spheres on the table, and the robot receives positive reward of +1 when its gripper catches a sphere (the sphere will disappear after being caught) otherwise receives time penalty. The maximum total reward is +4, and the minimum total reward is -1
SuperMarioBros. Mario agent with raw image observation explores to discover the flag. The reward is based on the score given by the NES simulator (Kauten, 2018) and is clipped into - and +1 except +50 when getting flag. There are 24 stages in the game, but we only focus on the 1-1, 1-2, and 1-3.
5.1 COMPARISON EXPLORATION EFFICIENCY
In this section, we study the exploration efficiency in terms of the state distribution entropy. We focus on the Empty Room environment because it is tractable to calculate the state distribution entropy. Note that don't use any external reward the observation for RND is a local-view image.
We consider the following baselines: 1) random: uniformly selecting actions; 2) bonus: a policy receiving exploration bonus based the prediction errors of RND (Burda 20195); 3) novelty-

---

Under review as a conference paper at ICLR 2020
(a) Empty Room
(b) Four Rooms
(c) FetchReach
(d) SuperMarioBros
Figure 3: Illustration of four environments considered in this paper.
pursuit: the proposed method. We also consider three variants of our method: 4) novelty-pursuit
planning oracle: the proposed method with perfect goal-conditioned policy: 5) novelty-pursuit- counts-oracle: the proposed method with selecting goals based on true visitation counts; 6) novelty- pursuit-oracles; the proposed method with both two oracles. The results summarized in Table M Note that the maximum state distribution entropy for this environment 5.666.
Table I: Average entropy of visited state distribution at timesteps 200k over 5 seeds on Empty Room.
Entropy
random
5.129 + 0.021
bonus novelty-pursee pursuit
5.138 = 0.085
5.285 = 0.073
govelty-pursuic planning- oracle
5.513 = 0.077
novelty- www.uuttcounts-onn
5.409 = 0.059
novelty-pune pecelty-pusuut-oraclee maximum
5.627 + 0.001
5.666
First, we can see that movelty-purssigg achieves higher entropy than the random and bonus method. Though exploration bonus via prediction eπrоrs of RND may help makes an peploratioo-exploiatttt trade-off (Eurda et all 20195), but is inefficient to a maximum state entropy exploration. We at- tribute this to delayed and indirect feedbacks of the exploration bonus. Second, when the planning oracle and visitation counts oracle are available, the entropy our method roughly improves by 0.228 and 0.124, respectively. We notice that the planning-oracle avoids exploration towards the ex- ploration boundary and spends more meaningful steps to explore around the exploration boundary, thus greatly improves the entropy. Based this observation, think accelerating goal-conditioned policy training is more important for our method. Actually, we find the proposed method can satisfy need approximate the exploration boundary via prediction errors of RND (See Appendix [.4 for more results). Third, the combination of two oracles gives a near-perfect performance (the gap between the maximum state entropy only 0.039). This result demonstrates that goal-condition exploration behaviors presented by novelty-pursut can maximize the state entropy and validates the analysis in Section [
5.2 ABLATION STUDY OF GOAL-SELECTION AND TRAINING TECHNIQUES
In this section, study the factors that contribute our method by ablation experiments. Firstly, focus on the criterion of goal-section in IMGEP. We compare novelty selection methods:
novelty-pursuit pursuit with two other goal- selecting states randomly from the experience buffer: 2) Saaming--roggesss selecting feasible state (goal success rate is between 0.3 and 0.7) with probabil- ity of 0.8 and an arbitrary visited state with the probability of 0.2, which is adopted from (Forestier study how goal-
aL 2012). Results on the Empty Room are shown in Figure Secondly, conditioned policy learning affects performance. We compare HER and the reward- -hauudd---ainggggg with distance reward (i.e., reward based L₃ norm in problem) used in (Forestier all 2017). Results on the Empty Room are shown Figure H
From Figure g gives a greater boost compared to the learning-progress. We think the reason is that this heuristic method is brittle to the estimation of goal success rate and lacks explicit exploration objective.
that IMGEP doesn't work when randomly selecting goals, but

---

Under review as a conference paper at ICLR 2020
From Figure E. find that the IMGEP with HER or reward shaping outperforms than the IMGEP with distance reward. As discussed in Ng et all (1999), reward based on distance may change the optimal behavior of goal-condition exploration policy, thus hurts the performance for IMGEP.
1.0
1,0
hoveltypursut
reward shaping distance reward
0.0
learning progress
0.0
random selection
-0.
-0.5
-1.00
steps
stops
Figure 4: Comparison of goal selectionn...
Figure 5: Comparison of training techniques.
5.3 EVALUATION ON COMPLEX ENVIRONMENTS
In this section, we compare different methods terms of external reward. We will see that without sufficient and efficient exploration, the policy may be stuck into the local optimum. Two baseline methods using reinforcement learning are considered: 1) vanilla: DDPG (Lillicrap et all, 2016) with Gaussian action noise on Fetch Reach and ACER (Wang al, 20L) with policy entropy regular- ization on others; 2) bonus: an off-policy version of (Burda et all 2019E) that combines the external reward and intrinsic reward based on the vanilla policy. Note reported results of novelty purittyttuuuutttt are the performances of the exploitation policy Ne rather than the coal-conditioned exploration policy Tg. We keep the number of samples and training iterations same for all methods.
First, we consider the previously used Empty Room and the Four Room environments. The results are shown Figure We see that the vanilla policy hardly finds the exit. Novelty-pursuit is comparative to bonus and outperforms bonus on the Four Rooms environment, where we observe that bonus somewhat misled by the intrinsic reward though we have tried many weights to balance the external reward and intrinsic reward.
Secondly, we consider the RetchReach environment and results are shown in Figure H We see that govelty-pursutt
consistently grip spheres while other methods sometimes fail to efficiently explore the whole state space to grip 4 spheres.
Finally, we consider the SuperMariooros environments, in which it is very hard to discover the flag due to the huge space state and the long horizon. Learning curves are plotted in Figure / and the final performance is listed in Table Q We find the vanilla method gets stuck into the local optimum SuperMarioBros- 1-1 while the bonus method and ours can find a near-optimal policy. All methods perform well SuperMarioBros-112 thanks dense rewards. On SuperMarioBros-113 reward is sparse and the task is very challenging. We plot trajectories of SuperMarioBros-113 in Figure & and
novelty-pursuit
bonus
vanilla
Empty Room
Four Rooms
Fetch Reach
1.0
episode return
opisade return
0.5
oplsode return
12
0.0
0.0
-0.5
100k steps
500k steps
steps
Figure 6: Average episode returns over 5 seeds on the Empty Room, Four Rooms and FetchReach environments. Shadows indicate the standard deviation.
8

---

Under review as a conference paper at ICLR 2020
novelty-pursuit
bonus
vanilla
SuperMarioBros-111
SuperMarioBros-1-2
SuperMarioBros-11
40-
apicode return
episodle return
opis return
30-
30
20
10-
0-
4.3M
13.5M
18M
4.5M
9M steps
13.5M
18M
9M steps
13.5M
18M
steps
Figure 7: Average episode returns over seeds on SuperMarioBros. Shadows indicate the standard deviation.
Trajectory visualization SuperMarioBros-I13 Trajectories are plotted in green cycles with the same number samples (18M). The agent starts from the most left part and needs to fetch flag the most right part. Top row: vanilla; middle row: bonus; bottom novelty-pursuit.
Figure 8:
more results can be found in Appendix A It turns out only our method can get positive rewards via a deep exploration presented by the goal-conditioned policy on SuperMarioBros-
Table 2: Final Performance over 3 seeds on SuperMarioBros.
novelty-pursui
bonus
vanilla
SuperMarioBros- 1-1
36.02 8.19
17.74 7.84
8.43 - 5 0.14
SuperMarioBros-I 1-2
33.30 = 6.13
33.19 = 1.53
29.64 2.02
SuperMarioBros-114 1-3
8.14 + 0.55
0.20 + 0.14
-0.07 0.01
RELATED WORK
Traditionally, the exploration strategy is based on the exploitation policy that receives an external reward from the environment. Traditional exploration methods include injecting noise on action space (Mmih et all, 2015 Lillicrap et all, 2016) or parameter space (Plappert et al, 2018h; Fortunato et all 2018), and adding the policy's 's entropy regularization (Schulman all, 2017 Mmih al. 2016).
Exploration.
For tabular Markov Decision Process, there are lots of work utilizing confidence based reward to balance exploration and exploitation (Kearns & Singh, 2002 Strrhl & Littman, 2008 Kolter & Ng. 2009; Lathmore Hutter. M)TE).. Several exploration strategies for deep RL based approximation
visitation counts have been proposed in high-dimension space (Bellemare et all 2016; Ostrovski al 2017). Another type exploration curiosity-drie driven exploration. These methods track the uncertainty of dynamic (Stadie all 2015: Parhak et all 2017: Burda all 2019)1 to explore intrinsic states. Deep (temporally extended) exploration via tracking the uncertainty value func- tion is studied in (Osband et all 2016). Besides, maximum (policy) entropy reinforcement learning

---

Under review as a conference paper at ICLR 2020
encourages exploration by maximizing the cumulative sum of external reward and policy entropy (Zicbart et all 2008; Haarnoja et al. 20177 O'Donoghue et all, 2016: Haarnoja et all 20T3).
Recently, Hazan ef all (2019) introduce new exploration objective: maximum state entropy. They
provide an efficient algorithm when restricted to a known tabular MDP (a density estimator oracle required for an unknown tabular MDP) and gives the theoretical analysis. We derive the criterion of goal generation based on the principle of maximum state entropy.
Our method is based the framework of intrinsically motivated goal exploration processes (IMGEP) (Baranes & Oudeyei, 2019; Forestier all 2017; Pêré et all, 2018). Go-Explore (Ecofiri
the hard exploration problem of Montezumas Revenge. But with the assumption that the environments are resettable or deterministic and many aandeenginn designs, Go-Explore is restricted to specific environments. Our method shares a similar exploration strategy like Go-Explore, but our method is implemented practically and can be applied stochastic environments. Importantly, we aim answer the core question: why such defined goal-conditioned exploration is efficient?
atall 2019) is reminiscent of IMGEP and achieves dramatic improvement
By taking environment observation and desired goal as inputs, the goal- conditioned policy is expected to accomplish a series of tasks. Schaul el (20155) propose the uni- versal value function approximator (UVFA) and train by bootstrapping from the Bellman equation. However, training goal-condtioned policy is also still challenging problem due to goal-condition reward is sparse (e.g. 1 for success, for failure). Andrychowicz el all (2017)) propose hindsight experience replay (HER) by replacing each episode with an achieved goal rather than that the agent was trying to achieve. This operation introduces more reward signals and serves as an implicit curriculum. Florensa et all (201)) use generator network to adaptively produce artificial feasible goals. We also use goal-conditioned policy, but goals are selected from the experience buffer rather than being specified in advance. What's more, we utilize the technique of reward shaping (Ng all, 1999) to accelcrate training.
Goal-conditioned Policy.
Learning from experience. Off-policy reinforcement learning algorithms such as DQN clal 2013), DDPG (Lillerap et alJ (201)), and ACER (Wang et all 2017), reuse experience to improve data efficiency. Besides, how additionally utilize (good) experience overcome exploration dilemma is studied in (Oh et all 2018; Goyal et all, 2019). These works are perpendicular to ours since we focus on how to discover these valuable states.
CONCLUSION
This paper bridges the intrinsically motivated goal exploration process (IMGEP) and the maximum state entropy exploration (MSEE). We propose method called novelty-pursuit from the connection. We demonstrate the proposed method is efficient towards exploring the whole state space. Therefore, the proposed method can escape from the local optimum and heads the (near-) optimal policy. We notice that current training techniques of the exploitation policy are based on an RL objective, which may not be efficient utilize experience collected by the exploration policy. Theoretically, the influence of trajectories towards the exploration bound should be considered. We leave these for future works.
REFERENCES
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Proceedings of the 30th Advances in Neural Information Processing Systems, pp. 5048-500 5058, 2017.
Adrien Baranes and Fierre-Yyer Oudeyer. R-IAC: robust intrinsically motivated exploration and active learning. IEEE Transactions on Autonomous Mental Development, 1(3):155-169, 2009.
Mare 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 29th Advances in Neural Information Processing Systems 29, pp. 1471-1479, 2016.
10

---

Under review as a conference paper at ICLR 2020
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/1606.01540, 2016.
Yuri Burda, Harrison Edwards, Deepak Pathak, Amos J. Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. In Proceedings of the 7th International Conference on Learning Representations, 2019a.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. Proceedings of 7th International Conference on Learning Representations, 2019b.
Maxime Chevalier- Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. pttps: / wwt.ttttt...g/ggo com
2018.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. nttps:
//qithub. cwm/ opena /basell
nes. 2017.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go-explore: new approach for hard-expe exploortlonii problems. CoRR, abs/1901 10995, 2019.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In Proceedings of the 35th International Conference on Machine Learning, pp. 1514-1523, 2018.
Sébastien Forestier, Yoan Mollard, and Pierre-Y Yves Oudeyer. Intrinsically motivated goal explo- ration processes with automatic curriculum learning. CoRR, abs/1708 020990,, 2017.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Os- band, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In Proceedings of the 6th Interna- tional Conference on Learning Representations, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In Proceedings the 36th International Conference on Machine Learning, pp. 2052- 2062, 2019.
Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal. Timothy P. Lillicrap. Sergey Levine, Hugo Larochelle, and Yoshua Bengio. Recall traces: Backtracking models for efficient reinforcement learning. In Proceedings of the 7th International Conference on Learning Repre- sentations, 2019.
Tuomas Haarnoja. Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep encrgy-based policies. In Proceedings of the 34th International Conference on Machine Learning. pp. 1352-1361, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, pp. 1856-1865, 2018.
Elad Hazan, Sham M. Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In Proceedings of the 36th International Conference Machine Learning, pp. 2681-2691, 2019.
Christian Kauten. Super Mario Bros for OpenAl Gym. GitHub, 2018. URL
com/ http//aaannaaayammaaaaaaaaaaaaaa
Michael J. Kearns and Satinder P. Singh. Near-optimal reinforcement learning in polynomial time.
Machine Learning, 49(2-3):209-22 232, 2002.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
Zico Kolter and Andrew Ng. Bear-bayesian exploration in polynomial time. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 513-520, 2009.

---

Under review as a conference paper at ICLR 2020
Tor Lattimore and Marcus Hutter. Near-optimal PAC bounds for discounted mdps. Theoretical Computer Science, 558:125- 123,-113,2200 2014.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforeement learning. In Pro- ceedings of the 4th International Conference Learning Representations, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. 2015.
Nature, (18(7550):522-553555
Volodymyr Mnih, Adria Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of the 33nd International Conference Machine Learning, pp. 1928- 1937, 2016.
Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 16th International Conference on Machine Learning, 1999.
Brendan O' D'Dnooguee, Rémi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. PGQ: combining policy gradient and q-learning. CoRR, abs/1611.01623 1.066666666 2016
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In Proceedings of the 35th International Conference on Machine Learning, pp. 3875-3884, 2018.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via boot- strapped DQN. In Proceedings of the 29th Advances in Neural Information Processing Systems, pp. 4026 4034, 2016.
Georg Ostrovski, Marc G. Bellemare, Aäron van den Oord, and Rémi Munos. Count-based ploration with neural density models. In Proceedings of the 34th International Conference on Machine Learming, pp.
2017.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- exploration by self-supervised prediction. In Proceedings of the 34th International Conference Machine Learning, pp. 2778-2787, 2017.
Alexandre Péré, Sébastien Forestier, Olivier Sigaud, and Pierre-Yves Oudeyer. Unsupervised leamn ing of goal spaces for intrinsically motivated goal exploration. In Proceedings of the 6th Interna- fional Conference on Learning Representations, 2018.
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, Vikash Kumar, and Wojeiech Zaremba. Multi-goal reinforcement learning: Challenging robotics environments and request for research. CoRR, Ab049442. 2018a.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y. Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marein Andrychowicz. Parameter space noise for exploration. In Proceedings of the 6th International Conference on Learning Representations, 2018b
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In Proceedings of the 32nd International Conference on Machine Learning, pp. 1312-1320, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.063477, 2017.
Bradly C. Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. CoRR, abs/1507.00814 2015.
12

---

Under review as a conference paper at ICLR 2020
Alexander L. Strehl and Michael L. Littman. An analysis of model-basee interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309- 1331, 2008.
Richard S. Sutton and Andrew G. Barto. Introduction to reinforcement learning. MIT Press, 1998.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running
average of its recent magnitude, 2012.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Rémi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay, In Proceedings of the Sth International Conference Learning Representations, 2017.
Brian D. Ziebart, Andrew L.. Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 33nd AAAI Conference on Artificial Intelligence, pp. 1433-1438, 2008.
A APPENDIX
A.1 PROOF OF THEOREM
Suppose we have two choices among state i and state j. we want to compare the difference gii,j) between the entropy H, [d by visiting state and the entropy Hj (d by visiting state j. Let N; = Σ; 2 denotes visitation counts over all states. Note that the entropy difference of two choices can be attributed to changes in 21+1 and x/41i
g(i.j) H, [d - H1(dT..11)
ai+1 =i+1 of log N.+1 N.+1
log N.+1 - (- #/+1 a++1 of N.+1
(-
log No+1
log N.+1) (4)
Not1
N.t1
+1/+1 a/t1 af Not1
o7 log Not1 N.11 log Not1 N.t1
#1+1 z1+1
of log N.+1
xf
N.t1 (N+tl log N.11
Let f(x) = N.+1
log #+1
N log N,II, which yields
N.+1
g(i.5) = f(x() - f(x))
(5)
By looking the derivative of (I:), know that f(x) is monotonically increasing function. Thus, for any xf xQ have that gi, j) O.
(((x) N +1 log(1 + x
>
In conclusion, unless state has the least visitation counts, we can always another state with of < xf to increase the entropy. Hence, visiting the states with the smallest visitation counts is optimal.
A.2 REWARD SHAPING FOR MULTI-GOAL REINFORCEMENT POLICY
Reward shaping is invariant to the optimal policy under some conditions (Ng et all, 1999). Here we verify that reward shaping introduced by method doesn't 't change the optimal policy for goal- conditioned policy. Adding up shaping rewards gives:
d(agrs g) d(ag++1.9)
d(agi,g) d(ag2,0)) g) d(ag2.9) + d(aga, g) +... d(agr, g) d(agT+1.g)
d(agi,g) g) + d(agr++.g)
13

---

Under review as a conference paper at ICLR 2020
For the optimal policy Tg. d(agr+1.9) g) 0, while d(ag1.9) is constant. Thus, for the fixed g, the optimal policy Ty induced by the reward shaping is invariant to the one induced by sparse-reward in Equation 21
A.3 TRAINING GOAL-CONDITIONE)) POLICY WITH PAST TRAJECTORIES
In fact, training the goal-conditioned policy for our problem is different from the settings of multi- goal reinforcement learning (Andrychowicz all 2014: Plappert et all 20 The goal is selected from visited states rather than the non-v non-visited states. Thus, we can utilize past trajectories to accel- training with supervised learning- The optimization problem is defined in Equation & Note that we cannot rely on this information on stochastic environments like SuperMarioBros.
min
Σ
- log n. (g(aclos.g: 9:
(8)
where T(g) is the trajectory that covers the goal in the previous exploration process.
Steps
Exploration Boundary
120k
-04
200k
C4
Figure 9: Visualization for the exploration boundary given by visitation counts and the estimated via prediction errors of RND.
A.4 ADDITIONAL RESULTS
Empty Room. We depict the exploration boundary by visitation counts and the estimated one by method in Figure g The agent starts from the left top corner and performs random policy. The exploration boundary shown black top 10% states with least visitation counts or the largest prediction errors among all visited states.
MariorMa In Figure [IC we make additional trajectories visualization on SuperMarioBros 1-1 and SuperMarioBros- 1-2. Trajectories method gets into the local optimum even with policy entropy regularization on SuperMarioBros-II 1- 1. In addition, only method get the flag SuperMarioBros-1122
plotted with same number samples (18M). Vanilla
14

---

Under review as a conference paper at ICLR 2020
(a) SuperMarioBroo- 1-1. Agent starts from the most left part and needs to find the flag on the most right part.
BEEB
ma in (b) SuperMarioBros-I 1-2. The agent walks in the underworld shown in black and needs get the tlag through the water pipe on the right part (see arrows).
Figure 10: Trajectory visualization. For each figure, top row: vanilla (ACER); middle row: bonus; bottom role: novelty-pursuit (ours). The vanilla method gets stuck into the local optimum even with policy entropy regularization on SuperMarioBros 1-1. Only our method can get the flag on SuperMariiBros
A.5 ENVIRONMENT PREPOSSESSING
2018), we only use the image and coordination information as inputs. We only consider four actions: turn left, turn right, move forward and move backward. The maximum episode length is 190 for Empty Room, and 500 for Four Rooms. Each time the agent receives time penalty of 1/max exit.
Maze. Different from Cheeallie-Booiseee
and receives +1 when finding the
FetchReach. We implement this environment based FetchReach-v0 in Gym (Brockman et all 2016). The maximum episode length is 50. The locations of four spheres are (1.20, 0.90, 0.65), (1.10, 0.72, 0.45), (1.20, 0.50, 0.60), and (1.45, 0.50, 0.55). When sampling goals, remove spheres outside of the table i.e., the valid x range: (1.0, 1.5), the valid range is (0.45, 1.05), and valid range is (0.45, 0.65).
Marioraas.
We implement this environment based on (Kauten, 2018) with Gym wrappers. Prepossessing includes grey-scaling, observation downsampling, external reward clipping (except that 50 for getting flag), stacked frames of 4, and sticky actions with a probability of 0.25, The maximum episode length is 800. The environment restarts when the agent dies.
A.6 NETWORK ARCHITECTURE
We the convolutional neural network (CNN) for Empty Room, Four Rooms, and video games of SuperMarioBros, and multi-layer perceptron (MLP) for FetchReach environment. Network archi- tecture design and parameters based on baselines (Dhariwal all 2017). For each environment,
15

---

Under review as a conference paper at ICLR 2020
RND uses a similar network architecture. The predictor network has additional MLP layers than the predictor network.
A.7 HYPERPARAMETERS
Table gives hyperparameters for ACER (Wang al, 2017) on the maze and SuperMarioBros (the learning algorithm is RMSProp (Iheleman & Hintnn 2012)) DDPG (Lillicrap et all, 2016) used in Fetch Reach environments based on the HER algorithm implemented in baselines (Dharwal etall 2017) expect that the actor learning rate is 0.0005. We run 4 parallel environments for DDPG and the size of the priority queue is also 100. As for the predictor network, the learning rate of the predictor network is 0.0005 and the optimization algorithm is Adam (Kingma & Ba 2UE) for all experiments, and the batch size training data is equal to the product of rollout length and the number of parallel environments.
The goal-conditioned policy is trained with shaping rewards defined in Equation B and external rewards, which helps reduce mismatch behaviors between its and the exploitation policy's The weight is 1 for all enviromments except for SuperMarioBros. For bonus method used Section S. the weight to balance the exploration bonus and the external reward (i.e., r' Text + Brint) 0.1 for Empty Room and Four Rooms, 0.01 for FetchReach, 1.0 for SuperMarioBros-I1 and SuperMarioBros- 1-3, and 0.1 for SuperMarioBros- We also do normalization for the intrinsic reward by dividing the intrinsic rewards via a running estimate of the standard deviation of the sum of discounted intrinsic rewards.
Table 3: Hyperparameters of our method based on ACER on the maze and MurirMass
Hyperparameters
Empty Room
Four Rooms
SuperMarioBros
Rollout length
20
20
20
Number of parallel environments
4
8
Learning rate Learning rate schedule
0.0007
0.0007
0.00025
linear
linear
constant
0.95
0.95
0.95
Entropy coefficient
0.10
0.10
0.10
Size of priority queue
100
100
20
Total training steps
200K
500K
20M
16


Reviews:
[{"review_id": "S1xkntLaFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of exploration in deep reinforcement learning. The authors borrow the ideas developed in the intrinsically motivated goal exploration process, and entropy maximization and propose a method on Noverly-Pursuit. The authors then empirically study the proposed method. \n\n1) The authors investigate an important problem and I would appreciate the authors if they could motivate its importance more in their work.\n\n2) In the second paragraph, the author mentioned that goal-conditioned exploration behaviours can maximize entropy. Later in the same paragraph, they claim that \"The exploration policy leads\nto maximize the state entropy on the whole state distribution considering tabular MDP\". I guess the authors' point was this approach might increase the entropy rather than maximizing it. If the claim is, in fact, maximization, a reference would be helpful. If the authors prove it in this paper, implying it in this paragraph is also helpful. \n\n3) In the background section, the authors did not specify whether they provide background on tabular MDP or beyond that. By calling the transition kernel the state transition probabilities, it seems they introduced a tabular MDP, but a more concrete introduction and preliminaries would help to follow the paper.\n\n3) The first paragraph of section 2, the author mentioned that\n\"The target of reinforcement learning is to maximize the expected discounted return\". I hope the authors mean\"one of the targets in the study of reinforcement learning ...\"\n\n4) in the same paragraph, why the \\gamma = 0 is excluded? is there any specific reason? Also, when the authors include the gamma = 1, do they make sure the maximization in line 9 of the same paragraph is well defined in regular cases?\n\n5) Regarding the experiment in figure 2. It would be useful to the readers if the authors provide more details about this experimental study.\n\n6) In the few paragraphs below Figure 2, it would be nicer if the authors provide a clear definition of each term. In order to follow the paper, I relied on my imperfect inference to infer the definitions. Also, I find it probably useful to distinguish the random variables and their realizations in the notation.\n\n6) Regarding the theorem1. I would recommend making the statement more transparent and more clear. I also recommend to even not calling it a theorem since it, as mentioned, is as clear as the definitions. Also, arent x_t(i)s non-negative by definition? \n\n7) In this sentence:\n\"However, we don’t know what non-visited states are and\nwhere non-visited states locate in practice since we can’t access ...\"\nI think the authors' point was that \"we might not have access to it in general\".\n\n8) It would be helpful to me to evaluate this paper if the authors explain more how the following statements go through:\n\"To deal with this problem, we assume that state density over the whole state space is continuous, thus visited states and non-visited states are close\". I am not sure how \"thus visited states and non-visited states are close\" follows from continuity of density and what is the notion of closeness. \n\n9-1) Theorem 2: while H seems to be a function of d_\\pi1:t(s), I am not sure how to interpret the argmax_{e_t}. A bit of help from the authors would be appreciated. \n\n9-2) Theorem 2: In the proof, I was not able to justify to my self the transition form g(xi; xj) = Hxi [d1:t+1] 􀀀 Hxj [d1:t+1] to the second line. Also, what is the definition of H_x_i?\n\n10) In equation 2, the authors use a notation d, I guess as distance. It would not only be helpful to define it but also would be helpful to use a different notation for distance and the d used on page 3, presumably for \"empirical state distribution\". \n\n11) At the beginning of the paper, the authors motivated the maximum entropy but the final algorithm is based on other approaches. \n\n12) Despite the fact that I could not find this paper ready enough and well-posed, I also have a concern about the novelty of the approach. I think it is not novel enough for publication at ICLR, but I am open to reading other reviewers', as well as commenters', and more especially the authors' rebuttal response.\n\n13) I also encourage the authors to provide a discussion on the cases where the novelty (whatever that could mean) does not matter, rather the  novelty of state-action pair matters. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HygSxD3hYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\nThe paper addresses the challenge of intrinsically-driven exploration in tasks with sparse or delayed rewards. First, the authors try to bridge the gap between the objectives of intrinsically-motivated goal generation and maximum state entropy exploration. Then, they propose a new exploration method, called novelty-pursuit, that prescribes the following receipt: first, reach the exploration boundary through a goal-conditioned policy, then take random actions to explore novel states. Finally, the authors compare their approach to a curiosity-driven method based on Random Network Distillation in a wide range of experiments: from toy domains to continuous control, to hard-exploration video games.\n\nI think that the paper displays some appealing empirical and methodological contributions, but it is not sufficiently theoretically grounded. For this reason, I would vote for rejection. I would advise the authors to rephrase their work as a primarily empirical contribution, in order to emphasize the merits of their method over a lacking theoretical analysis.\n\n*Detailed Comments*\n\n*Major Concern*\nMy major concern is about the claim that goal-conditioned exploration towards the least visited state would, at the same time, maximize the entropy of the state distribution. The derivations seem technically sound, but I think that the underlying assumption is unreasonable in this context: it neglects the influence of the trajectory to reach the target state, which is rather crucial in reinforcement learning instead. It is quite easy to design a counter-example in which the (optimal) goal-conditioned policy towards the least visited state actually decreases the overall entropy of the state distribution. One could avoid the issue by assuming to have access to a generative model over the states, but that would fairly limit the applicability of the approach.\n\n*Other Concerns and Typos*\n- I think that the authors minimize the relation between their methodology and the one proposed in (Ecoffet et al., 2019). It is true that the applicability of Go-Explore is quite limited. However, the idea behind their approach, which is based on first reaching an already visited state and then exploring randomly from that state, is not all dissimilar from the two-phase exploration scheme of novelty-pursuit.\n- It is not completely clear to me how the disentanglement between exploration and exploitation works in the novelty-pursuit algorithm.\n- What is the vanilla policy considered in the experiments?\n- Section 4.2, after equation 3: rewarding shaping -> reward shaping\n- section 5.4: we consider the SuperMarioBros environments, which is very hard ecc. -> we consider the SuperMarioBros environments, in which it is very hard ecc.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxjEFuqqr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes novelty-pursuit for exploration in large state space. In theory, novelty-pursuit is motivated by connecting intrinsically motivated goal exploration process (IMGEP) and the maximum state entropy exploration (MSEE), showing that exploring least visited state can increase state distribution entropy most. In practice, novelty-pursuit works in two stages: First, it selects a goal (with largest value prediction error) to train a goal reaching policy to reach the boundary of explored and unexplored states. Second, after reaching goal states, it uses a randomly policy to explore, hopefully can get to unexplored states. Experiments on Empty Room show that the novelty-pursuit with perfect goal reaching policy and visit count information can maximize state distribution entropy. Experiments on Empty Room, Four Rooms, FetchReach and SuperMarioBros show that the proposed method can achieve better performance than vanilla (policy gradient?) and bonus (exploration bonus using Random Network Distillation).\n\n1. The authors claim that the proposed method connects IMGEP and MSEE. However, the theory actually shows that a connection of visit count and MSEE (Thm. 2, choosing least visited state increases the state distribution entropy most.) Table 1 of Empty Room experiments shows the same, with visit count oracle the state entropy is nearly maximized. With goal exploration (entropy 5.35 and 5.47 in Table 1), the state entropy is not \"maximized\". I consider the theory part and Table 1 more a connection between visit count (including zero visit count, and least visited count) and MSEE, rather than IMGEP and MSEE.\n\n2. The argument of first choose non-visited state, then choose least visited state (Fig. 1) makes sense. However, the experiment design is just one way of approximately achieving this. I did not see why doing this approximation is good from both theoretical and empirical perspectives.\n\n2a) Random Network Distillation (RND) prediction error is used to select goals. After reaching these goals, it is claimed that the boundary of explored and unexplored states has been reached. However, RND just uses visit count as a high-level motivation, and there is no justification that high RND prediction error corresponds to low visit count. \n\nIn Table 1, it is surprising even in this simple environment, the entropy still looks not good with approximation. Maybe use larger networks. And why does bonus have the same entropy as random (does not make sense to me since RND should be a much stronger baseline than random policy)?\n\n2b) There exist other methods to approximate this boundary of visited/non-visited states (like pseudo-count as mentioned). Comparisons with other choices are needed (on simple tasks if others cannot be scaled up to SuperMarioBros) to claim that this approximation is a good choice.\n\n3. The experiments are lack of comparison with other exploration methods. There are only comparisons with vanilla (is it policy gradient?) and bonus (I suppose it is exactly the same method as in RND paper?), which is not enough to show the proposed method is on a good level. Also, experiments on more tasks (such as Atari) are needed to evaluate the performance of the purposed method.\n\n4. The reward shaping r(a g_t, g_t) in Eq. (2) is for a changing g_t. In Eq. (7), it seems to show cancelation of fixed g. I did not see why cancelation of fixed g in Eq. (7) can lead to the conclusion that Eq. (2) does not change optimal policies.\n\nOverall, I found this paper: 1) main idea (Fig. 1) makes sense; 2) the theoretical contribution is weak (the connection between visit count and entropy is not difficult to see). It does not connect IMGEP and MSEE, but connects visit count and entropy; 3) The experiments choose one way to approximately reaching boundary of visited and non-visited states, which is lack of comparison with other choices; 4) The experiments look promising, especially on SuperMarioBros, but more experiments on other tasks and comparisons with other exploration methods are needed to evaluate the proposed method thoroughly.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is insufficient support to recommend accepting this paper.  The reviewers unanimously recommended rejection, and did not change their recommendation after the author response period.  The technical depth of the paper was criticized, as was the experimental evaluation.  The review comments should help the authors strenghen this work.
Decision: Reject