Title: DEEP EXPLORATION BY NOVELTY-PURSUIT WITH MAXIMUM STATE ENTROPY

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.

1. INTRODUCTION:

Efficient exploration is important to learn a (near-) optimal policy for reinforcement learning (RL) in huge state space (Sutton & Barto, 1998) . Dithering strategies like epsilon-greedy, Gaussian action noise, and Boltzmann exploration are inefficient and require exponential interactions to explore the whole state space. In contrast, deep exploration (Osband et al., 2016) overcomes this dilemma via temporally extended behaviors with a long-term vision. Recently, proposed methods include the intrinsically motivated goal exploration process (IMGEP) (Forestier et al., 2017) , and maximum state entropy exploration (MSEE) (Hazan et al., 2019) . In particular, IMGEP selects interesting states from the experience buffer as goals for a goal-conditioned exploration policy. In this way, exploration behaviors are naturally temporally-extended via accomplishing self-generated goals. On the other hand, MSEE aims to search for a policy such that it 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 a visited state with the least visitation counts as the goal to reach the boundary of the explored region; then, it takes random actions to explore the non-explored region. An illustration can be seen in Figure 1 . 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. A 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 storage when selecting the least visited states, we approximate the visitation counts via prediction errors given by Random Network Distillation (Burda et al., 2019b) . Besides, we observe that previous methods used in IMGEP (Forestier et al., 2017) are inefficient to train the goal-conditioned exploration policy. We employ training techniques based on reward shaping (Ng et al., 1999) and HER (Andrychowicz et al., 2017) to accelerate training the goal-conditioned policy. Finally, we additionally train an unconditioned exploitation policy to utilize samples collected by the goal-conditioned Figure 1 : Illustration for the proposed method. A goal-conditioned policy firstly reaches the exploration boundary, then perform random actions to discover new states. exploration policy with environment-specific rewards. Thus, the exploration and exploitation is decoupled 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 a 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 SuperMarioBros.

2. BACKGROUND:

Reinforcement Learning. In the standard reinforcement learning framework (Sutton & Barto, 1998) a learning agent interacts with a Markov Decision Process (MDP). The sequential decision process is characterized as follows: at each time t, the agent receives a state s t from the environment and selects an action a t from its policy π(s, a) = Pr{a = a t |s = s t }; that decision is sent back to the environment, and the environment gives a reward signal r(s t , a t ) and transits to the next state s t+1 based on the state transition probability p a ss ′ = Pr{s ′ = s t+1 |s = s t , a = a t }. This process repeats until the agent encounters a terminal state after which the process restarts. The main target of reinforcement learning is to maximize the expected discounted return E π [ ∑ ∞ t=0 γ t r t ] in an unknown environment, where γ ∈ (0, 1] is a factor that balances the importance of future reward. Without information about environment dynamics and task-specific rewards in advance, the agent needs exploration to 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 process (IMGEP) (Baranes & Oudeyer, 2009; Forestier et al., 2017) relies on a goal-conditioned (or goal-parameterized) policy π g for unsupervised exploration. It involves the following steps: 1) selecting an intrinsic or interesting state from the experience buffer as the desired goal; 2) exploring with a goal-conditioned policy π g (s, a, g) = Pr{a t = a|s t = s, g t = g}; 3) reusing experience for an exploitaion policy π e (s, a) = Pr{a t = a|s t = s} to maximize the external reward. Note that the performance of exploitation policy π e relies on samples collected by the goal-exploration policy π g . Thus, the criterion of goal selection is crucial for IMGEP.

Maximum State Entropy Exploration. Maximum state entropy exploration (Hazan et al., 2019) aims to search an exploration policy π * such that it maximizes the entropy of induced state distribution (or minimizes the KL-divergence between the uniform distribution and induced state distribution) among the class of stationary policies (i.e., π * ∈ arg max π H[d π ], 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.

In practice, an exact density estimator for high-dimension state space is intractable, and the state space is unknown, which leads to an empirical state distribution over visited states. The differences are important. For example, directly optimizing the entropy of empirical state distribution over visited states is not what we want, because it ignores the non-visited states outside of the empirical state distribution (see the top row in Fig 2 ). Instead, we need to first maximize the support of induced state distribution (i.e., discovering new states), then we maximize the entropy of induced state distribution with full support (see the bottom row in Fig 2 ). 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. The theoretical analysis starts with the situation that each iteration the goal-conditioned exploration policy can only select a state to 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 is closely related to the goal generation in IMGEP. To facilitate the analysis, let the unit vector e = [0, • • • , 1, . . . ] ∈ R |S| denotes a choice (i.e., e(i) = 1 indicates that the policy selects i-th state to visit). Note that x t+1 = x t + e t with this assumption.

Proposition (Max Counting Measure of Support) For any state i ∈ {1, • • • , |S|} with x i t ≥ 0, unless the unvisited state sets K = {i|x i t = 0}

is an empty set, for any choice e t such that e t (i) = 1 with x i t = 0, we have µ t+1 = µ t + 1. 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 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 1 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 are small. In conclusion, the goal-conditioned exploration policy is asked to reach the exploration boundary, then it performs random actions to discover new states to maximize the counting measure. We provide the proof in the appendix A.1. Theorem 1 characterizes the behavior of visiting the 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 1 still suggests selecting states with the least visitation counts as goals, the above method can also be applied to maximize the entropy of induced state distribution. Actually, it is easy to unify the two stages via a smoothed entropy (Hazan et al., 2019) . For our problem, the definition of entropy is proper by assigning non-visited states with a "dummy" visitation counts between 0 and 1. In that case, Theorem 1 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.

H σ (d π ) = -E dπ [log(d π ) + σ]

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. In fact, the goal-conditioned policy should be trained to reach the exploration boundary quickly and pays more efforts to discover new states around the exploration boundary, as our experiment results in Section 5.1 indicate.

4. 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 4.1. We describe the training technique of goal-conditioned policy in Section 4.2. Finally, we introduce an exploitation policy to learn the experience collected by the goal-conditioned exploration policy in Section 4.3. We outline the proposed exploration method in Algorithm 1.

4.1. APPROXIMATING EXPLORATION BOUNDARY IN HIGH-DIMENSION 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 et al. (2019b) show that prediction errors given by two randomly initialized network have a strong relationship to the number of training samples on the MNIST dataset. Thus, we can use the prediction errors to sort visited states. Other approaches like pseudo-counts (Bellemare et al., 2016; Ostrovski et al., 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 f (x; ω t ), and a trainable network called predictor network f (x; ω p ). 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 to minimize the difference between the predictor network and the target network concerning the predictor network's parameters, shown in Equation 1.

min ωp 1 K K ∑ i=1 ||f (s i ; ω t ) -f (s i ; ω p )|| 2 (1)

In practice, we employ an online learning setting to train RND and maintain a priority queue to store states with the highest prediction errors. In particular, after a 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 as a goal for the goal-conditioned 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 a distribution based on their prediction errors (e.g., softmax distribution). Before we describe the training techniques for the goal-conditioned policy, we emphasize that training this policy doesn't require the external reward signal from the environment. But we additionally use the external reward for the goal-conditioned policy to reduce the mismatch behaviors between the goal-conditioned policy π g and the exploitation policy π e .

Following multi-goal reinforcement learning (Andrychowicz et al., 2017; Plappert et al., 2018a) , we 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 π g (s, a, g; θ)1 is asked to accomplish a desired goal g. For our settings, the achieved goal is coordinate information.

EQUATION

A proper reward function for the goal-conditioned policy is an indicator function with some tolerance, shown in Equation 2. With a little abuse of notations, between the achieved goal ag and the desired goal g we use d(ag, g) to denote some "distance" (e.g., L 1 or L 2 norm) between the achieved goal ag and the desired goal g. If the distance is less than some threshold ϵ, the goalconditioned 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.

EQUATION

Reward shaping introduces additional training rewards to guide the agent. Reward shaping is invariant to the optimal policy if shaping reward function is a potential function (Ng et al., 1999) . pursuit: the proposed method. We also consider three variants of our method: 4) novelty-pursuitplanning oracle: the proposed method with a perfect goal-conditioned policy; 5) novelty-pursuitcounts-oracle: the proposed method with selecting goals based on true visitation counts; 6) noveltypursuit-oracles: the proposed method with both two oracles. The results are summarized in Table 1 .

Note that the maximum state distribution entropy for this environment is 5.666. First, we can see that novelty-pursuit achieves a higher entropy than the random and bonus method. Though exploration bonus via prediction errors of RND may help makes an exploration-exploitation trade-off (Burda et al., 2019b) , but is inefficient to a maximum state entropy exploration. We attribute this to delayed and indirect feedbacks of the exploration bonus. Second, when the planning oracle and visitation counts oracle are available, the entropy of our method roughly improves by 0.228 and 0.124, respectively. We notice that the planning-oracle avoids exploration towards the exploration boundary and spends more meaningful steps to explore around the exploration boundary, thus greatly improves the entropy. Based on this observation, we think accelerating goal-conditioned policy training is more important for our method. Actually, we find the proposed method can satisfy our need to approximate the exploration boundary via prediction errors of RND (See Appendix A.4 for more results). Third, the combination of two oracles gives a near-perfect performance (the gap between the maximum state entropy is only 0.039). This result demonstrates that goal-condition exploration behaviors presented by novelty-pursuit can maximize the state entropy and validates the analysis in Section 3.

5.2. ABLATION STUDY OF GOAL-SELECTION AND TRAINING TECHNIQUES:

In this section, we study the factors that contribute to our method by ablation experiments. Firstly, we focus on the criterion of goal-section in IMGEP. We compare novelty-pursuit with two other goalselection methods: 1) random-selection: selecting states randomly from the experience buffer; 2) learning-progress: selecting a feasible state (goal success rate is between 0.3 and 0.7) with probability of 0.8 and an arbitrary visited state with the probability of 0.2, which is adopted from (Forestier et al., 2017) . Results on the Empty Room are shown in Figure 4 . Secondly, we study how goalconditioned policy learning affects performance. We compare HER and the reward-shaping with distance reward (i.e., reward based on L 1 norm in our problem) used in (Forestier et al., 2017) .

Results on the Empty Room are shown in Figure 5 .

From Figure 4 , we see that IMGEP doesn't work when randomly selecting goals, but novelty-pursuit 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 an explicit exploration objective.

From Figure 5 , we find that the IMGEP with HER or reward shaping outperforms than the IMGEP with distance reward. As discussed in Ng et al. (1999) , reward based on distance may change the optimal behavior of goal-condition exploration policy, thus hurts the performance for IMGEP. 

5.3. EVALUATION ON COMPLEX ENVIRONMENTS:

In this section, we compare different methods in 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 al., 2016) with Gaussian action noise on Fetch Reach and ACER (Wang et al., 2017) with policy entropy regularization on others; 2) bonus: an off-policy version of (Burda et al., 2019b ) that combines the external reward and intrinsic reward based on the vanilla policy. Note reported results of novelty-pursuit are the performances of the exploitation policy π e rather than the goal-conditioned exploration policy π g . 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 in Figure 6 . 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 is somewhat misled by the intrinsic reward though we have tried many weights to balance the external reward and intrinsic reward.

Secondly, we consider the FetchReach environment and results are shown in Figure 6 . We see that novelty-pursuit can consistently grip 4 spheres while other methods sometimes fail to efficiently explore the whole state space to grip 4 spheres.

Finally, we consider the SuperMarioBros 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 7 and the final performance is listed in Table 2 . We find the vanilla method gets stuck into the local optimum on SuperMarioBros-1-1 while the bonus method and ours can find a near-optimal policy. All methods perform well on SuperMarioBros-1-2 thanks to dense rewards. On SuperMarioBros-1-3, reward is sparse and the task is very challenging. We plot trajectories of SuperMarioBros-1-3 in Figure 8 , and 

6. RELATED WORK:

Exploration. 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 (Mnih et al., 2015; Lillicrap et al., 2016) or parameter space (Plappert et al., 2018b; Fortunato et al., 2018) , and adding the policy's entropy regularization (Schulman et al., 2017; Mnih et al., 2016) .

For tabular Markov Decision Process, there are lots of work utilizing confidence based reward to balance exploration and exploitation (Kearns & Singh, 2002; Strehl & Littman, 2008; Kolter & Ng, 2009; Lattimore & Hutter, 2014) . Several exploration strategies for deep RL based approximation visitation counts have been proposed in high-dimension space (Bellemare et al., 2016; Ostrovski et al., 2017) . Another type of exploration is curiosity-driven exploration. These methods track the uncertainty of dynamic (Stadie et al., 2015; Pathak et al., 2017; Burda et al., 2019a; b) to explore intrinsic states. Deep (temporally extended) exploration via tracking the uncertainty of value function is studied in (Osband et al., 2016) . Besides, maximum (policy) entropy reinforcement learning encourages exploration by maximizing the cumulative sum of external reward and policy entropy (Ziebart et al., 2008; Haarnoja et al., 2017; O'Donoghue et al., 2016; Haarnoja et al., 2018) .

Recently, Hazan et al. (2019) introduce a new exploration objective: maximum state entropy. They provide an efficient algorithm when restricted to a known tabular MDP (a density estimator oracle is 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 on the framework of intrinsically motivated goal exploration processes (IMGEP) (Baranes & Oudeyer, 2009; Forestier et al., 2017; Péré et al., 2018) . Go-Explore (Ecoffet et al., 2019) is reminiscent of IMGEP and achieves dramatic improvement on the hard exploration problem of Montezumas Revenge. But with the assumption that the environments are resettable or deterministic and many hand-engineering 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 to stochastic environments. Importantly, we aim to answer the core question: why such defined goal-conditioned exploration is efficient?

Goal-conditioned Policy. By taking environment observation and desired goal as inputs, the goalconditioned policy is expected to accomplish a series of tasks. Schaul et al. (2015) propose the universal value function approximator (UVFA) and train it by bootstrapping from the Bellman equation. However, training goal-condtioned policy is also still a challenging problem due to goal-condition reward is sparse (e.g. 1 for success, 0 for failure). Andrychowicz et al. (2017) propose hindsight experience replay (HER) by replacing each episode with an achieved goal rather than one that the agent was trying to achieve. This operation introduces more reward signals and serves as an implicit curriculum. Florensa et al. (2018) use a generator network to adaptively produce artificial feasible goals. We also use a 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 et al., 1999) to accelerate training.

Learning from experience. Off-policy reinforcement learning algorithms such as DQN (Mnih et al., 2015) , DDPG (Lillicrap et al., 2016), and ACER (Wang et al., 2017) , reuse experience to improve data efficiency. Besides, how to additionally utilize (good) experience to overcome exploration dilemma is studied in (Oh et al., 2018; Goyal et al., 2019) . These works are perpendicular to ours since we focus on how to discover these valuable states.

7. CONCLUSION:

This paper bridges the intrinsically motivated goal exploration process (IMGEP) and the maximum state entropy exploration (MSEE). We propose a 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 to 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. 

EQUATION

By looking at the derivative of f (x), we know that f (x) is a monotonically increasing function. Thus, for any x i t < x j t , we have that g(i, j) > 0.

EQUATION

In conclusion, unless state i has the least visitation counts, we can always another state j with x j t < x i t 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 al., 1999) . Here we verify that reward shaping introduced by our method doesn't change the optimal policy for goalconditioned policy. Adding up shaping rewards gives: 

:

IMGEP WITH MAXIMUM STATE ENTROPY EXPLORATIONIn this section, we 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.

With the respect of input to a goal-conditioned policy, s contains ag to keep notations simple.

Figures and Tables:

Figure 2: Histograms for normalized state visitation counts, where the x-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 {1, 2, • • • , |S|} denotes the state space S, π 1:t denotes the set of policies {π 1 , π 2 , • • • , π t } over previous iterations, π t+1 denotes the policy of next iteration, x i t denotes the cumulative visitation counts of state i induced by history policies π 1:t , and N t = ∑ |S| i=1 x i t denotes the sum of all state visitation counts. Hence, the entropy of empirical state distribution induced by policies π 1:t is defined as H[d π1:t (s)] = ∑ |S|

Figure 3: Illustration of four environments considered in this paper.

Figure 4: Comparison of goal-selection.

Figure 6: Average episode returns over 5 seeds on the Empty Room, Four Rooms and FetchReach environments. Shadows indicate the standard deviation.

Figure 7: Average episode returns over 3 seeds on SuperMarioBros. Shadows indicate the standard deviation.

Figure 8: Trajectory visualization on SuperMarioBros-1-3. Trajectories are plotted in green cycles with the same number samples (18M). The agent starts from the most left part and needs to fetch the flag on the most right part. Top row: vanilla; middle row: bonus; bottom row: novelty-pursuit.

d(ag t , g) + d(ag t+1 , g) = -d(ag 1 , g) + d(ag 2 , g) -d(ag 2 , g) + d(ag 3 , g) + • • • -d(ag T , g) + d(ag T +1 , g) = -d(ag 1 , g) + d(ag T +1 , g) (7)

, • • • , π t } over previous iterations, π t+1 denotes the policy of next iteration, x i t denotes the cumulative visitation counts of state i induced by history policies π 1:t , and N t =

Table content: <table><tr><td>∑ |S| i=1 x i t denotes the sum of all state visitation counts. Hence, the entropy of empirical state distribution induced by policies π 1:t is defined as H[d π1:t (s)] = ∑ |S| i=1 x i t Nt log x i t Nt (H t for short), and the counting measure of empirical state distribution support induced by policies π 1:t is defined as µ[d π1:t (s)] = ∑ |S| t ≥ 1) (µ t i=1 I(x i for short), where I is the indicator function.</td></tr></table>

Theorem 1 (Max Entropy) For any state i ∈ {1, • • • , |S|} with x i

Table content: <table/>

Algorithm 1 Exploration by novelty-pursuit Input: predictor network update interval K; goal-conditioned policy update interval M ; minibatch size of samples for goal-conditioned policy N ; Initialize parameter θ for goal-conditioned exploration policy π g (s, g, a; θ). Initialize parameter ω t for target network f (x; ω t ), and ω p for predictor network f (x; ω p ). Initialize a buffer D g for π g , and a priority queue Q to store states with least visitation counts. for each iteration do Reset the environment and get the observation o 0 ; Choose a goal g from priority queue Q, and set goal success = F alse; for each timestep t do if goal success == T rue then Choose an random action a t ; # Explore around the exploration boundary else Choose an action a t from π g (s t , g, a t ; θ); # Go to the exploration boundary end if Send a t to the environment and get r e t , s t+1 ; Update goal success(s t+1 , g); # Store new states and update the predictor network if t % K == 0 then Store transitions {s k , g, a k , r e k } t k=t-K into replay buffer D g ; Calculate prediction errors for {s k } t k=t-K and store them into priority queue Q; Update predictor network f (x; ω p ) using {s k } t k=t-K ; end if # Update π g with reward shaping if t % M == 0 then Update π g with {s k , g k , a k , r i

Table content: <table><tr><td>k } K k=1 sampled from D g ;</td></tr><tr><td>end if</td></tr><tr><td>end for</td></tr><tr><td>end for</td></tr><tr><td>4.2 TRAINING GOAL-CONDITIONED POLICY EFFICIENTLY</td></tr></table>

Average entropy of visited state distribution at timesteps 200k over 5 seeds on Empty Room.

Table content: <table><tr><td/><td>Entropy</td></tr><tr><td>random</td><td>5.129 ± 0.021</td></tr><tr><td>bonus</td><td>5.138 ± 0.085</td></tr><tr><td>novelty-pursuit</td><td>5.285 ± 0.073</td></tr><tr><td colspan="2">novelty-pursuit-planning-oracle 5.513 ± 0.077</td></tr><tr><td>novelty-pursuit-counts-oracle</td><td>5.409 ± 0.059</td></tr><tr><td>novelty-pursuit-oracles</td><td>5.627 ± 0.001</td></tr><tr><td>maximum</td><td>5.666</td></tr></table>

Final Performance over 3 seeds on SuperMarioBros.

Table content: <table><tr><td/><td>novelty-pursuit</td><td>bonus</td><td>vanilla</td></tr><tr><td>SuperMarioBros-1-1</td><td>36.02 ± 8.19</td><td colspan="2">17.74 ± 7.84 8.43 ± 0.14</td></tr><tr><td>SuperMarioBros-1-2</td><td>33.30 ± 6.13</td><td colspan="2">33.19 ± 1.53 29.64 ± 2.02</td></tr><tr><td>SuperMarioBros-1-3</td><td>8.14 ± 0.55</td><td>0.20 ± 0.14</td><td>-0.07 ± 0.01</td></tr></table>

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-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 a 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 5th International Conference on 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. Suppose we have two choices among state i and state j, we want to compare the difference g(i, j) between the entropy H i [d π1:t+1 ] by visiting state i and the entropy H j [d π1:t+1 ] by visiting state j. Let N t = ∑ i x i t denotes visitation counts over all states. Note that the entropy difference of two choices can be attributed to changes in x i t+1 and x j t+1 : g(i, j) = H i [d π1:t+1 ] -H j [d π1:t+1 ]

Table content: <table><tr><td colspan="2">A APPENDIX</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="4">A.1 PROOF OF THEOREM 1</td><td/><td/><td/><td/><td/><td/></tr><tr><td>= (-</td><td colspan="2">x i t +1 N t +1 log</td><td colspan="2">x i t +1 N t +1 -</td><td>x j t N t +1 log</td><td colspan="2">x j t N t +1 ) -(-</td><td colspan="2">x j t +1 N t +1 log</td><td>x j t +1 N t +1 -</td><td>x i t N t +1 log</td><td>x i t N t +1 )</td><td>(4)</td></tr><tr><td colspan="2">x j t +1 N t +1 log</td><td colspan="2">x j t +1 N t +1 -</td><td colspan="2">x j t N t +1 log</td><td>x j t N t +1 ) -(</td><td colspan="2">x i t +1 N t +1 log</td><td colspan="2">x i t +1 N t +1 -</td><td>x i t N t +1 log</td><td>x i t N t +1 )</td></tr><tr><td colspan="9">Let f (x) = x+1 Nt+1 log x+1 Nt+1 -x Nt+1 log x Nt+1 , which yields</td><td/></tr><tr><td/><td/><td/><td/><td/><td>g</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
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). 1. 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. 2. 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. 2a) 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. In 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)? 2b) 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. 3. 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. 4. 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. Overall, 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.