SKEW-EXPLORE: LEARN FASTER IN CONTINUOUS SPACES WITH SPARSE REWARDS
Year: 2019

Abstract:
In many reinforcement learning settings, rewards which are extrinsically available to the learning agent are too sparse to train a suitable policy. Beside reward shaping which requires human expertise, utilizing better exploration strategies helps to circumvent the problem of policy training with sparse rewards. In this work, we introduce an exploration approach based on maximizing the entropy of the visited states while learning a goal-conditioned policy. The main contribution of this work is to introduce a novel reward function which combined with a goal proposing scheme, increases the entropy of the visited states faster compared to the prior work. This improves the exploration capability of the agent, and therefore enhances the agent’s chance to solve sparse reward problems more efficiently. Our empirical studies demonstrate the superiority of the proposed method to solve different sparse reward problems in comparison to the prior work.

text: 1 INTRODUCTION
Reinforcement Learning (RL) is based on performing exploratory actions in a trial-and-error manner and reinforcing those actions that result in superior reward outcomes. Exploration plays an important role in solving a given sequential decision-making problem. A RL agent cannot improve its behaviour without receiving rewards exceeding the expectation of the agent, and this happens only as the consequence of properly exploring the environment.
In this paper, we propose a method to train a policy which efficiently explores a continuous state space. Our method is particularly well-suited to solve sequential decisionmaking tasks with sparse terminal rewards, i.e., rewards received at the end of a successful interaction with the environment. We propose to directly maximize the entropy of the history states by exploiting the mutual information between the history states and a number of reference states. To achieve this, we introduce a novel reward function which, given the references, shapes the distribution of the history states. This reward function, combined with goal proposing learning frameworks, maximizes the entropy of the history states. We demonstrate that this way of directly maximizing the state entropy, compared to indirectly maximizing the mutual information (WardeFarley et al., 2018; Pong et al., 2019) improves the ex-
ploration of the state space as well as the convergence speed at solving tasks with sparse terminal rewards.
Maximizing the mutual information between the visited states and the goal states, I(S;G), results in a natural exploration of the environment while learning to reach to different goal states (Warde-Farley et al., 2018; Pong et al., 2019). The mutual information can be written as I(S;G) = h(G)− h(G|S); therefore maximizing the mutual information is equivalent to maximizing the en-
tropy of the goal state while reducing the conditional entropy (conditioned on the goal state). The first term, encourages the agent to choose its own goal states as diverse as possible, therefore improving the exploration, and the second term forces the agent to reach the different goals it has specified for itself, i.e., training a goal-conditioned policy, π(.|s, g). Instead of maximizing the mutual information, we propose to maximize the entropy of the visited states directly, i.e., maximizing h(S) = h(Z) +h(S|Z)−h(Z|S), where Z is a random variable that represents the reference points of promising areas for exploration. Therefore, in our formulation, we have an extra term, h(S|Z), which encourages maximizing the entropy of the state conditioned on the reference points. This extra term, implemented by the proposed reward function, helps the agent to explore better at the vicinity of the references. We call our method Skew-Explore, since similar to Skew-Fit introduced by Pong et al. (2019), it skews the distribution of the references toward the less visited states, but instead of directly reaching the goals, it explores the surrounding areas of them.
We experimentally demonstrate that the new reward function enables an agent to explore the state space more efficiently in terms of covering larger areas in less time compared to the earlier methods. Furthermore, we demonstrate that our RL agent is capable of solving long-term sequential decision-making problems with sparse rewards faster. We apply the method to three simulated tasks, including a problem to find a trajectory of a YuMi robot end-effector, to open a door of a box, pressing a button inside the box and closing the door. In this case, the sparse reward is given only when the button is pressed and the door is closed, i.e., at the end of about one minute of continuous interaction with the environment. To validate appropriateness of the trajectory found in simulation, we deployed it on a real YuMi robot, as shown in Figure 1. The main contributions of this paper can be summarized as (1) introducing a novel reward function which increases the entropy of the history states much faster compared to the prior work, and (2) experimentally demonstrating the superiority of the proposed algorithm to solve three different sparse reward sequential decision-making problems.

heading: 2 RELATED WORK
text: Prior works have studied different algorithms for addressing the exploration problem. In this section, we summarize related works in the domain where rewards from the environment are sparse or absent.
Intrinsic Reward: One way to encourage exploration is to define an intrinsically-motivated reward, including methods that assimilate the definition of curiosity in psychology (Oudeyer et al., 2007; Pathak et al., 2017). These methods have found success in domains like video games (Ostrovski et al., 2017; Burda et al., 2018). In these approaches, the ”novelty”, ”curiosity” or ”surprise” of a state is computed as an intrinsic reward using mechanisms such as state-visiting count and prediction error (Schmidhuber, 1991; Stadie et al., 2015; Achiam & Sastry, 2017; Pathak et al., 2017). By considering this information, the agent is encouraged to search for areas that are less visited or have complex dynamics. However, as pointed out by Ecoffet et al. (2019), an agent driven by intrinsic reward may suffer from the problem of detaching from the frontiers of high intrinsic reward area. Due to catastrophic forgetting, it may not be able to go back to previous areas that have not yet been fully explored (Kirkpatrick et al., 2017; Ellefsen et al., 2015). Our method is able to keep tracking the novelty frontier and train policy to explore different areas in the frontier.
Diverse Skill/Option Discovery: Methods that aim to learn a set of behaviours which are distinct from each other, allow the agent to interact with the environment without rewards for a particular task. Gregor et al. (2016) introduced an option discovery technique based on maximizing the mutual information between the options and the final states of the trajectories. Eysenbach et al. (2018); Florensa et al. (2017a); Savinov et al. (2018) proposed to learn a fixed set of skills by maximizing the mutual information through an internal objective computed using a discriminator. Achiam et al. (2018) extended the prior works by considering the whole trajectories and introduced a curriculum learning approach that gradually increases the number of skills to be learned. In these works, the exploration is encouraged implicitly through learning diverse skills. However, it is difficult to control the direction of exploration. In our method, we maintain a proposing module which tracks the global information of the states we have visited so far, and keep proposing reference points that guide the agent to the more promising areas for exploration.
Self-Goal Proposing: Self-goal proposing methods are often combined with a goal-conditioned policy (Kaelbling, 1993; Andrychowicz et al., 2017), where a goal (or task) generation model is
trained jointly with a goal reaching policy. The agent receives rewards in terms of completing the internal tasks which makes it possible to explore the state space without any supervision from the environment. Sukhbaatar et al. (2017) described a scheme with two agents. The first one proposes tasks by performing a sequence of actions and the other repeats the actions in reverse order. Held et al. (2018) introduced a method that automatically label and propose goals at the appropriate level of difficulty using adversarial training. Similar works are proposed by Colas et al. (2018); Veeriah et al. (2018); Florensa et al. (2017b), where goals are selected based on the learning progress. WardeFarley et al. (2018) trained a goal-conditioned policy by maximizing the mutual information between the goal states and the achieved states. The goals are selected from the agent’s recent experience with strategies. Later, Pong et al. (2019) applied a similar idea of using mutual information. They maximize the entropy of a goal sampling distribution. The focus of these methods is on learning a policy that can reach diverse goals. Although gradually increasing the scale of the goal proposing network, the agent may eventually cover the entire state space, exploration itself is not efficient. In our work, we adopt the same idea of maximizing the entropy of the goal sampling distribution by Pong et al. (2019). However, instead of using the goal-conditioned policy, we introduce a reference point-conditioned policy which greatly increases the efficiency of exploration.

heading: 3 SKEW-EXPLORE: SEARCHING FOR THE SPARSE REWARD
text: We discuss the policy learning problem in continuous state and action spaces, which we model as an infinite-horizon Markov decision process (MDP). The MDP is fully characterized by a tuple (S,A, pa(s, s′), R′a(s, s′)), where S, the state space, and A, the action space, are subsets of Rn, the unknown transition probability p : S × A × S → [0, inf) indicates the probability density function of the next state s′ given the current state s ∈ S and the action a ∈ A. For each transition, the space associated environment E emits an extrinsic reward according to function R′ : S × A → R. The objective of the agent is to maximize the discounted return, i.e. return R = ∑∞ ts=0
γtsrts , where γ is a discounted factor and rts is the reward received at each step ts. In this study, we consider an agent interacting in an environment E with sparse reward. The sparse reward r is modelled as a truncated Gaussian function with a narrow range. From previous interactions, the agent holds an interaction set It, in which transaction triples (sj ,aj , sj+1),∀j ∈ {1, · · · , T − 1} are contained. We also extract the states sj from It to form a history state set St, which contains all visited states by the agent until iteration t. The objective of our method is to find an arbitrary external goal in a continuous state space and converge to a policy that maximizes the R as fast as possible. This involves two processes 1) Find the external reward through efficient exploration. 2) Converge to a policy that maximizes R once the external reward is found.
We can use the entropy of the history state set as a neutral objective to encourage exploration, since an agent that maximizes this objective should have visited all valid states uniformly. To describe it mathematically, we define a random variable S to represent the history states that the agent has visited. The distribution of S is estimated from the history state set St. Our goal is to encourage exploration by maximizing the entropy h(S) of the history states. However, using the entropy as the intrinsic reward directly may suffer from problems similar to other intrinsic motivated methods (Schmidhuber, 1991; Stadie et al., 2015; Achiam & Sastry, 2017; Pathak et al., 2017). As the reward of the same state is changing, the agent has the risk of detaching from the frontiers of high intrinsic reward area.
We introduce a concept called novelty frontier reference point, which can be sampled from a distribution that represents the novelty frontier (Ecoffet et al., 2019). The novelty frontier defined in our work represents the areas near the states with lower density in distribution p(s). The frontier reference points are sampled after the distribution of the novelty frontier is updated. We define a Z to represent all the history frontier reference points with probability density p(z) estimated from a set Zt that contains all novelty frontier reference points until iteration t. The conditional probability p(s|z) defines the behaviour of the agent with respect to each reference point. In this work, we model this behaviour using a state distribution function Kz(s − z) parameterized by the displacement between the state and the reference point. The function Kz needs to be chosen carefully as it should satisfy our expectation of the policy behaviour and also, provides an informative reward signal to train the policy. Mathematically, we can rewrite p(s) as p(s) = ∫ f(s|z)p(z)dz = ∫ Kz(s − z)p(z)dz. Generally, Kz(·) can be different for different z.
However, to reduce the complexity of learning, we constrain Kz(·) to be consistent for any z, meaningKz(s−z) = K(s−z). The definition ofK(·) satisfies the definition of a kernel function. Using K(s− z), p(s) can then be further represented as
p(s) = ∫ K(s− z)p(z)dz
= (K ∗ p)(s). By considering the law of convolution of probability distributions, we obtain S = Z + N, where N is a random variable characterized by a density function K(·). Now with this setup, we are able to to analyze our method’s performance using information theory. By considering the entropy’s relationship with mutual information h(S) = h(S|Z) +I(S;Z), we receive the final decomposition of our objective under the novelty frontier reference point-conditioned policy framework
h(S) = h(Z) + h(S|Z)− h(Z|S). (1) Eq. 1 indicates that in order to maximize the h(S), we can individually maximize/minimize each term while making other terms fixed. In the following section, we will explain the optimization process in detail.
3.1 MAXIMIZING h(Z): OBTAINING AN EXPANDING SET OF NOVELTY FRONTIER REFERENCE POINTS
As introduced above, h(Z) is the entropy estimated from the novelty frontier reference points setZt. To increase h(Z), we need to add a new reference point to Zt such that, the entropy estimated form Zt+1 is larger than the entropy estimated from Zt. In our method, the frontier reference points are sampled from the novelty frontier distribution which represents less history areas according to the current history states. Pong et al. (2019) proposed a method to skew the distribution of the history states using importance sampling, such that states with lower density can be proposed more often. In our work, we use a similar way to estimate the novelty frontier distribution. There are three steps in our process. In the first step, we estimate the p(s) from St using a density estimator e.g. Kernel Density Estimation (KDE). In the second step, we sample Q states {s0, · · · , sQ} from p(s), and compute the normalized weight for each state using Eq. 2
wi = 1
Yα p(si)p(si) α α ∈ [− inf, 0), Yα = N∑ n=1 p(s = sQ)p(s = sQ) α, (2)
where Yα is a normalizing constant. The state with lower p(s) has higher weight and vice versa. Finally, we utilize a generative model training scheme Tg(·, ·) (e.g. weighted KDE), together with sampled states and weights to get a skewed distribution pskewed(s) = Tg({s0, · · · , sn}, {w0, · · · , wn}) to represent the novelty frontier distribution.
If Q is big enough, by choosing a α appropriately, we are able to expand our frontiers after each iteration. As a consequence, the distribution estimated from Zt will become more and more uniform and its range will become larger and larger, just like annual ring of the tree. The entropy of a continuous uniform function U(p, q) is ln(p − q) and if the distribution has a larger range, the entropy is larger as well. Fig 2 illustrates the estimated frontier distribution skewed from p(s).
3.2 MAXIMIZING h(S|Z)− h(Z|S): INCREASING THE EXPLORATION RANGE AROUND REFERENCE POINTS
The conditional entropy of h(S|Z) and h(Z|S) are highly correlated, maximizing/minimizing them individually are difficult. Therefore, in this section, we consider to maximize h(S|Z) - h(Z|S)
as a whole. Using the relation S = Z + N, we rewrite the expression as h(S|Z) − h(Z|S) = h(Z + N|Z)− h(Z|Z + N), which can be further simplified (see Appendix D) as
h(Z|S)− h(S|Z) ≥ h(N)− h(Z). This implies that there is a lower bound for the expression h(S|Z)− h(Z|S). For a fixed h(Z), we can maximize the lower bound h(N)− h(Z) by increasing h(N). h(N) is related to the shape and variance of the exploration distribution near the reference point. In our method, we model N as a Gaussian distribution with zero mean. In an ideal case, we would like to have as large variance as possible. However, increasing the variance also results in learning difficulty, as we need a longer trajectory to evaluate the performance and more samples to update the network. Therefore, we use the variance to control the trade-off between exploration efficiency and learning efficiency.

heading: 3.3 DESIGNING THE REWARD FUNCTION
text: Our algorithm requires the policy to move around a given reference point, and the distribution of the states in the trajectory should follow a Gaussian distribution centered at the reference point. In this section, we introduce an intrinsic reward function to train such policy by minimizing the the Kullback-Leibler (KL) divergence between the trajectory distribution and the desired Gaussian distribution. For each given reference point zi, we collect a trajectory τi by running the policy with the given reference point, indicated as π(zi), for M steps. Then, we estimate the probability density of each state s in τi, referred to as pτi(s), using a density estimator. Finally, we check the probability density of s in the Gaussian distribution centered at zi, referred to as pzi(s). The KL-divergence between the trajectory distribution pτi and the desired distribution pzi is formulated as follows
DKL(pτi(·) | pzi(·)) = Ezi∼(Zt),τi∼π(zi),s∼τipτi(s) log pτi(s)
pzi(s) . (3)
To minimize the KL-divergence, the intrinsic reward of s with respect to zi is computed as rint(s, zi) = log(pzi(s))− log(pτi(s))). (4)
The intrinsic reward function measures the difference between the desired density of s in the trajectory and the actual density achieved. The reward is positive when the actual density is smaller than the desired one, when states in the trajectory are too far from the reference point, and the reward is negative when the actual density is larger than the desired one, when the agent stays too long at the reference point. An extrinsic reward rext(s) is provided by the environment and the total reward of a time step is defined as the weighted sum of the intrinsic and the extrinsic reward. The extrinsic reward should be much greater than the intrinsic reward. The reward of each time step r(s, zi) is defined as
r(s, zi) = wint · rint(s, zi) + wext · rext(s), (5) where, wint and wext are respective weights for internal and external rewards. The performance of the policy is closely related to the set Zt, as it records the reference points we used to train the policy until iteration t. As described in section 3.1, while we increase the entropy h(Z) by proposing new reference points form the novelty frontier to train the policy, the policy gradually gain skills to explore different areas. When a state with a large extrinsic reward is discovered, the policy eventually ignores all given reference points and converge to reach the state with the extrinsic reward. Algorithm 1 shows the whole Skew-Explore algorithm using pseudo code and our implementation of the algorithm is available online 1.
1https://anonymous.4open.science/r/b4596073-4cbc-4ac6-b85b-e9a786909058/
Algorithm 1 Skew-Explore 1: procedure SKEW-EXPLORE 2: History state set S0 = {} 3: History novelty frontier reference points set Z0 = {} 4: Randomly sample L novelty frontier points zi 5: Z0 = Z0 ∪ {z1, ..., zL}. 6: for t = 1, 2, 3... do 7: Collect a set of states sq by running policy giving different frontier reference point zi. 8: Compute reward for each state using Eq. 5. 9: Update history state set St = St−1 ∪ {s1, ..., sQ} and estimate p(s) from St 10: Estimate the novelty frontier distribution pskewed(s) by skewing p(s). 11: Sample L new novelty frontier points zl ∼ pskewed(s). 12: Update history novelty frontier reference points set Zt = Zt−1 ∪ {z1, ..., zL}. 13: Update policy according to the rewards
3.4 SCALING TO HIGHER DIMENSIONAL STATES
4 EXPERIMENT
In this section, we evaluate our algorithm from three perspectives. 1) How efficient is our algorithm in terms of exploring the entire state space, and how different choice of variance affects the efficiency? 2) Is our algorithm able to converge to a stable solution for tasks with sparse reward? 3) Is our algorithm able to solve a complicated sparse reward task with long horizon? The implementation details of the experiments can be found in Appendix E. Two metrics are considered to evaluate the performance. They are the state distribution entropy h(S) and the coverage, which are estimated from history state set St. We describe how we estimate the two metrics and their difference in Appendix A and B. A short video regarding the experiments can be found online 2.

heading: 4.1 POWER OF EXPLORATION
text: In the first experiment, we evaluate our algorithm in term of the efficiency of exploring the state space. We test our algorithm in two simulated environments, the PointMaze and the DoorOpen environments (Fig. 4). In the PointMaze environment, a point agent is controlled to move inside a maze with narrow passages. In the DoorOpen environment, a YuMi robot can open a door by grabbing the door handle. The PointMaze environment was previously used by Florensa et al. (2017a); Eysenbach et al. (2018); Pong et al. (2019), whilst environments similar to the DoorOpen environment were used by Kalakrishnan et al. (2011); Chebotar et al. (2017); Pong et al. (2019). The objective of the tasks is to explore the entire state space in a minimum amount of time. In order to evaluate the performance, we measure the efficiency as the overall coverage and the entropy of the density estimated from all history states. We compare our algorithm with two baseline algorithms: the random network distillation (RND) proposed by Burda et al. (2018) which is an approach using prediction error as the intrinsic reward, and Skew-Fit proposed by Pong et al. (2019) which combines a goal proposing network with a goal-conditioned policy.
We consider two configurations. The first one is the proximal policy optimization (PPO) Schulman et al. (2017) together with a Long Short-Term Memory network (LSTM) Hochreiter & Schmidhuber (1997). The second configuration is soft actor-critic (SAC) Haarnoja et al. (2018) and hindsight experience replay (HER) Andrychowicz et al. (2017). We note here that RND is only tested with PPO and LSTM as it was not designed for off-policy methods. For each configuration, we run
2https://www.dropbox.com/s/xxw7ug3lnud3h0j/video_submission.mp4
12 times and compare the mean and variance. Fig. 5 shows the results for all 5 configurations. We can see that our method, SAC+HER+Skew-Explore, makes both coverage and entropy increase faster than the other methods. It also increases with relatively small variances. Fig 6 illustrates
how coverage changes for both our method Skew-Explore and Skew-Fit. In this figure, we see how our method is able to cover the state space (area in this case) faster than Skew-Fit. To further analyze how different choices of the variance of N affects the exploration efficiency, several values of variances 02, 12, 22, 32, 42 and 62 are tested in the PointMaze environment. After 80 iterations, estimated entropy 40.2±1.2, 49.3±0.7, 51.4±0.8, 51.4±0.7, 51.4±0.7 and 48.9±3.3 are received. We observe that while the variance increases, the performance first increases and then decreases.

heading: 4.2 POWER OF SOLVING A SINGLE SPARSE REWARD TASK
text: The power of exploration is an important aspect, but we also want our algorithm to converge to a stable policy that maximizes the extrinsic reward for different sparse reward tasks. To this end, we use the same environments (Fig. 4) as in the previous experiment. In each environment, we select five uniformly distributed target points from the area of interest and assign extrinsic rewards when the agent reaches these points. For each target point, we train an individual policy to reach it. Hypothetically, influenced by the extrinsic reward, the agent eventually ignores the internal
goals generated by the goal proposing module and reaches the target points consistently. In order to evaluate the performance of our algorithm, we measure how reliably the agent is able to reach each target point. To this end, we collect the final 10 states from the 10 most recent trajectories and define criteria for convergence as the percentage of receiving the extrinsic rewards. If more than 90% of the states receive the extrinsic reward with a standard deviation of less then 3%, we say the agent solved the task successfully. In this experiment, we use the configuration SAC+HER+SkewExplore which achieves the best performance in the previous experiment. Table 1 shows how many trajectories the algorithm needs to reach the criteria of convergence. This experiment thus shows that our algorithm is able to solve a sparse reward task, by obtaining a policy with a limited number of trajectories. Additional results can be found in Appendix F.

heading: 4.3 TASK WITH A LONG HORIZON AND REAL WORLD DEMONSTRATION
text: In the third experiment, we evaluate the ability of our algorithm in terms of solving a sparse reward task with a long horizon and test the performance of the converged policy using a real world YuMi robot. We increase the complexity of the environment by adding a box and a button to the DoorOpen environment used in the previous two experiments. We design a task called OpenPressClose which needs a long sequence of procedures to be solved. The sequence includes 1) open the box, 2) press the button inside the box and 3) close the box. The extrinsic sparse reward is only given to the agent after all procedures in the sequence are done. This task is exceptionally challenging as each intermediate procedure requires a set of continuous actions in correct order to be achieved and no intermediate reward is provided to guide the search. Therefore this task requires the power of efficient exploration to discover the state that provides an extrinsic reward. If the algorithm fails to explore efficiently, the rewarding state would never be found and no policy will be learned. The results show that the algorithm is able to discover the extrinsic reward and converge to a stable solution. Fig 7a shows the change of average extrinsic reward per step over iterations and Fig 7b shows the converged policy in sequential order. The resulting policy is deployed to a real world YuMi robot as shown in Fig 1. A demonstration of the real robot solving the task can be found in the video.

heading: 5 CONCLUSION
text: In this work, we propose an algorithm named Skew-Explore, a general framework for continuous state exploration. Inspired by Skew-Fit Pong et al. (2019), the main idea of Skew-Explore is to encourage exploration around the novelty frontier reference points proposed by a latent variable proposing network. The algorithm is able to track the global information of entropy of density distribution estimated by the states stored in a history state set, which helps to maximize a corresponded metrics, namely entropy and coverage. Two experiments are conducted to test the power of SkewExplore on the exploration problem and the single sparse reward problem. In the first experiment, we found that our algorithm Skew-Explore, using SAC and HER together, has the fastest exploration rate. In the second experiment, we found that our algorithm is also able to converge to a stable policy when a single sparse reward is given. As a demonstrator, we used an environment where a robotic manipulator needs to 1) open a door, 2) press a button inside and 3) close the door in a sequence but only with a sparse reward given at the end. We implemented the fully converged policy on a real YuMi robot using policy transfer. Future work will include investigating if we can improve the efficiency of policy convergence by adjusting the proposing network’s distribution. Additionally, we will examine whether clustering can increase the efficiency for exploration. Moreover, we will look for a better reward function than KL divergence between Gaussian-based goal distribution and the trajectory distribution.

heading: Appendices
text: A DIFFERENCE BETWEEN COVERAGE AND h(S)
Since the reward is given to an arbitrary state in the whole space, two metrics could be considered to evaluate the performance of the agent, namely the state distribution entropy h(S) and the coverage fc(St). The distribution of S can be estimated using any density estimator trained using St.
The coverage of St is defined as a mapping fc : Sn → R, K(St) :=
∫
S maxi(φ(si)) ds, where φ : [0, inf) → R is a radial basis function with a Gaussian kernel centred at si ∈ St, and n equals |St|. Intuitively, these two measures describe similar characteristics of the data distribution. However, they also have significant differences. One major difference is that when a new data point is presented in the state space, the coverage can only increase whilst the entropy can decrease if the new data point is given in an often visited area. Figure 8 illustrates the difference between coverage and density estimation when two and three points are given. Coverage gives a better intuition about where the agent should search for the sparse reward.
To find the sparse reward, we maximize the history states entropy to increase the coverage. A proof for one-dimensional state space is given in Appendix C. Proof of high dimensional cases is related to Kepler theorem Hales (2005) and is beyond the scope of this paper. We aim to maximize the entropy of the state density in the St, which isH(S).

heading: B ESTIMATING STATE ENTROPY AND COVERAGE
text: In practice, we uniformly discretize the entire state space along each dimension and use the center of the discretized grids to estimate the entropy and the coverage. We do not check the validity of each grid. Therefore, there are grids that are not reachable from the initial state, and the maximum possible coverage is less than 1. The PointMaze environment is discretized to 50 · 50 grids. The DoorOpen environment is discretized to 10 · 10 · 10 · 2 · 10 grids. The entropy and coverage are summed over the discretized states.
C PROOF OF RELATION BETWEEN COVERAGE AND h(S)
In this section, we prove Lemma C.1. Lemma C.1. Given N movable points P = {p1, p2, · · · , pN} distributed in R with boundary Bl ≤ pi ≤ Bh. Maximizing the coverage estimated from these points using a Gaussian kernel will make the points to be uniformly distributed within the boundary, thus maximizing the entropy of the points’ distribution.
Proof. According to the definition of coverage, the area under all Gaussian kernels could be written as :
fc(P) = ∫ R max i (φ(pi)) dx (6)
We rewrite the equation as subtraction of all the areas and the overlapping areas. Fig 9 illustrates these concepts. The area from negative infinity to x under Gaussian distribution is defined as.
Φ(x) = ∫ x −∞ φ(x)dx = 1 2 ( 1 + erf ( x√ 2 )) , (7)
fc(P) = NΦ(∞)− N−1∑ i=1 2Φ( −ti 2 ) (8)
= 1− N−1∑ i=1 erf ( −ti 2 √ 2 ) (9)
(10)
As maximizing 1− ∑N−1 i=1 erf ( −ti 2 √ 2 ) is equivalent to minimizing ∑N−1 i=1 erf ( −ti 2 √ 2 ) . We formulate an optimization problem as follows:
minimize t1,t2,··· ,ti N−1∑ i=1 erf ( −ti 2 √ 2 ) subject to ti ≥ 0,∀ti
N−1∑ i=1 ti ≤ Bh −Bl,
Solving this problem using the KKT conditions will give us that when ti = Bh−BlN−1 ,∀ti, the expression is minimized. This result shows that when the coverage estimated from these points is maximized, the points need to be distributed evenly within the boundary. As a consequence, the entropy of the distribution of these points is also maximized.
D PROOF OF h(S|Z)− h(Z|S) ≥ h(N)− h(Z)
In this section, we show our analysis and proof of the expression
h(S|Z)− h(Z|S) ≥ h(N)− h(Z).
Let Z and S be jointly distributed continuous random variables, where S is related to Z through a conditional PDF f(s|z) defined for all z. The conditional PDF f(s|z) follows a Gaussian distribution centred at different z with standard deviation σ > 0.
Lemma D.1. S can be represented as the sum of Z and N, where N is a r.v. with Gaussian PDF of 0 mean and standard deviation σ, independent from Z.
S = Z + N (11)
Proof
Using the law of total probability, the density of f(s) can be written as:
f(s) = ∫ f(s|z)f(z)dz
=
∫ 1
σ √ 2π e−(s−z) 2/2σ2f(z)dz
= ∫ K(s− z)f(z)dz
= (K ∗ f)(s), (12)
where K is the density function of N. According to Theorem 7.1 in Grinstead & Snell (2012), when the density function f(s) is the convolution of the density function of G and N, S = G + N holds.

heading: Q.E.D.
text: Lemma D.2. When S = Z + N holds, the following expression
h(S|Z)− h(Z|S) ≥ h(N)− h(Z) (13)
holds.

heading: Proof.
text: Remark. Here we note that we will use following equations in later proof,
h(Z) = h(Z|N) = h(Z + N|N) (14) h(N) = h(N|Z) = h(Z + N|Z). (15)
In Eq. 14 and Eq. 15, h(Z) = h(Z|N) and h(N) = h(N|Z) are true because Z and N are independent. Moreover, h(Z|N) = h(Z + N|N) and h(N|Z) = h(Z + N|Z) are true because there is no gain of information by adding what is given already.
We expand the Eq. 13 by replacing the S with Z + N and get
h(S|Z)− h(Z|S) = h(Z + N|Z)− h(Z|Z + N) = h(N)− h(Z|Z + N) (16)
Now we proceed to prove that h(Z|Z + N) = h(N|Z + N),
h(Z|Z + N) = h(G + N|Z) + h(Z)− h(Z + N) = h(N) + h(Z)− h(Z + N) = h(N) + h(Z + N|N)− h(Z + N) = h(N,Z + N)− h(Z + N) = h(N|Z + N). (17)
We replace h(Z|Z + N) with h(N|Z + N) in Eq. 16 to have
h(S|Z)− h(Z|S) = h(N)− h(N|Z + N) = I(Z + N;N)
= I(S;N). (18)
According to the property of mutual information, I(S;N) ≥ 0, with equality if and only if S and N are independent. As S = Z + N, I(S;N) = 0 is true only when the PDF of N is a Dirac delta function. In our case, PDF of N is a Gaussian function and σ > 0, as a consequence, the expression h(S|Z)− h(Z|S) > 0 holds. Additionally, since h(Z|Z + N) is the same as h(N|Z + N), by law of conditioning reduces entropy, we has an inequality as follows
h(S|Z)− h(Z|S) = h(N)− h(N|Z + N) h(S|Z)− h(Z|S) = h(N)− h(Z|Z + N) h(S|Z)− h(Z|S) ≥ h(N)− h(Z). (19)

heading: Q.E.D
text: If we link it back to the paper, Z is the novelty frontier reference points proposing distribution and S represents the achieved state distribution by executing goals sampled form Z. N defines the behaviour of the policy according to a given reference point. When N has a Dirac delta distribution, the policy is a goal-conditioned policy (as in Skew-Fit). When N is a Gaussian distribution, the policy moves around the reference point following a Gaussian distribution. Compared to the goal conditioned policy, the reference point-conditioned policy achieves higher state entropy. The extra amount of entropy equals to the mutual information I(Z + N;N).
E IMPLEMENTATION DETAILS

heading: E.1 ENVIRONMENT DETAILS
text: The three environments used in the experiments are implemented using Mujoco Todorov et al. (2012).
PointMaze: In this environment, an agent travels in a maze contains narrow passages. The observation is the x, y position of the agent and the action is the velocity along the x, y axis. The maximum velocity for each dimension is 0.12. In the sparse reward experiment, the agent receives an extrinsic reward when the distance to the goal is less than 0.15.
DoorOpen: In this environment, we use a single arm Yumi robot with 7 degrees of freedoms (DOFs). The robot is controlled in Cartesian space and the orientation of the end-effector is fixed. The robot can grab a door handle and open the door on a table. The maximum opening of the door is 90 degrees. The observation space is 5 dimensional, including the x, y, z position of the end-effector, the open/close status of the gripper and the opening angle of the door. The action is the velocity along x, y, z axis. The valid action space of the robot is 10cm×11cm×10cm. In the sparse reward experiment, the agent receives an extrinsic reward when the angle difference to the goal is less than 2 degrees.
OpenPressClose: This environment contains a single arm Yumi robot, a box with a door and a button inside the box. The robot configuration is the same as the DoorOpen environment. The maximum opening of the door is 143 degrees. The observation space of the robot is 6 dimensional, including the x, y, z position of the end-effector, the open/close status of the gripper, the opening angle of the door and the status of the button. The action is the velocity along x, y, z axis. The valid action space of the robot is 2cm× 28.5cm× 16cm. In the sparse reward experiment, the agent needs to press the button down for more than 1cm and close the door completely.
E.2 HYPERPARAMETER
We use the same network structure for all experiments. The policy network contains 5 fully-connected layers with the number of units in all layers 32, 64, 128, 64, 32. We use ReLU as the activation function and there is no activation for the output layer and for all experiments, the length of the trajectory is 200.
The RND contains 3 fully-connected layers with the number of units 32, 64, 64 in the random target network and contains 4 fully-connected layers with the number of units
32, 64, 64, 128 in the prediction network.
For PPO, we use the batch of 5, 000 and 15 epochs per iteration. We update the state distribution and the goal distribution at every 5, 000 step.

heading: F ADDITIONAL RESULTS
text: The second experiment test whether the algorithm is able to converge to a given sparse reward after exploration. As mentioned in the section 4.2, five points are selected to test the convergence of the algorithm given a sparse reward. Fig 10 shows the exact points in the PointMaze and DoorOpen environments. The points are selected uniformly from the area of interests. For each point, twelve experiments have been executed to receive information about mean and the variance of the algorithm’s performance. Fig 11 and Fig 12 show the relationship between the convergence criteria and the number of iteration for PointMazz environment and DoorOpen environment respectively.

Review summaries:
This paper studies the problem of exploration in reinforcement learning. The key idea is to learn a goal-conditioned agent and do exploration by selecting goals at the frontier of previously visited states.  This frontier is estimated using an extension of prior work (Pong 2019). The method is evaluated on two continuous control environments (2D navigation, manipulation), where it seems to outperform baselines.

This paper proposes a new exploration algorithm by proposing a new way of generating intrinsic rewards. Specifically, the authors propose to maintain a "novelty frontier" which consists of states that have low-likelihood under some likelihood model trained on their replay buffer. The authors propose to sample from the novelty frontier using a scheme similar to a prior method called Skew-Fit, but replace the VAE with a kernel-based density model. To construct an exploration reward, the authors estimate the KL divergence between the resulting policy state distribution and the desired `state distribution, where the desire state distribution is a Gaussian centered around a point sampled from the novelty frontier.