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

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.

1. INTRODUCTION:

Figure 1 : A sparse-reward task trained by a YuMi robot in simulation and deployed to the real hardware. The task consists of (1) opening a door, (2) pressing a button, and (3) closing the door. The reward is given only at the end of a successful trial.

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 (Warde-Farley et al., 2018; Pong et al., 2019) improves the exploration 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.

2. RELATED WORK:

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. Warde-Farley 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.

3. SKEW-EXPLORE: SEARCHING FOR THE SPARSE REWARD:

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, p a (s, s ), R a (s, s )), where S, the state space, and A, the action space, are subsets of R n , 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 γ ts r ts , where γ is a discounted factor and r ts is the reward received at each step t s . 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 I t , in which transaction triples (s j , a j , s j+1 ), ∀j ∈ {1, • • • , T -1} are contained. We also extract the states s j from I t to form a history state set S t , 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 S t . 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 Z t 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 K z (s -z) parameterized by the displacement between the state and the reference point. The function K z 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 = K z (s -z)p(z)dz. Generally, K z (•) can be different for different z.

However, to reduce the complexity of learning, we constrain K z (•) to be consistent for any z, meaning K z (s -z) = K(s -z). The definition of K(•) 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 set Z t .

To increase h(Z), we need to add a new reference point to Z t such that, the entropy estimated form Z t+1 is larger than the entropy estimated from Z t . 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 S t using a density estimator e.g. Kernel Density Estimation (KDE). In the second step, we sample Q states {s 0 , • • • , s Q } from p(s), and compute the normalized weight for each state using Eq. 2

EQUATION

)

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 T g (•, •) (e.g. weighted KDE), together with sampled states and weights to get a skewed distribution p skewed (s

) = T g ({s 0 , • • • , s n }, {w 0 , • • • , w n })

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 Z t 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. 

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.

Figure 3 : Our method, Skew-Explore, aims to obtain uniform state visitation distribution estimated from the history state set. We start by sampling from our history state set, and weighting the states such that less-visited states are assigned with higher weights. We then train a skewed distribution p skewed (s) using the weighted samples as the novelty frontier distribution. Next we sample reference points on the novelty frontier distribution and run our policy to explore around the points.

3.3. DESIGNING THE REWARD FUNCTION:

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 z i , we collect a trajectory τ i by running the policy with the given reference point, indicated as π(z i ), 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 z i , referred to as p zi (s). The KL-divergence between the trajectory distribution p τi and the desired distribution p zi is formulated as follows

EQUATION

To minimize the KL-divergence, the intrinsic reward of s with respect to z i is computed as

EQUATION

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 r ext (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,

EQUATION

where, w int and w ext are respective weights for internal and external rewards. The performance of the policy is closely related to the set Z t , 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 online1 .

Algorithm 1 Skew-Explore 1: procedure SKEW-EXPLORE 2:

History state set S 0 = {} 3:

History novelty frontier reference points set Z 0 = {} 4:

Randomly sample L novelty frontier points z i 5:

Z 0 = Z 0 ∪ {z 1 , ..., z L }.

6::

for t = 1, 2, 3... do 7:

Collect a set of states s q by running policy giving different frontier reference point z i .

8::

Compute reward for each state using Eq. 5.

9:

Update history state set S t = S t-1 ∪ {s 1 , ..., s Q } and estimate p(s) from S t 10:

Estimate the novelty frontier distribution p skewed (s) by skewing p(s).

11::

Sample L new novelty frontier points z l ∼ p skewed (s).

12:

Update history novelty frontier reference points set Z t = Z t-1 ∪ {z 1 , ..., z L }. 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 S t .

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 online2 .

4.1. POWER OF EXPLORATION:

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. 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 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 We observe that while the variance increases, the performance first increases and then decreases.

4.2. POWER OF SOLVING A SINGLE SPARSE REWARD TASK:

Table 1 : This shows the number of trajectories needed for the algorithm to converge to five uniformly sampled target states in each environment. A successful convergence is measured as 90% of the states receive the extrinsic reward with a standard deviation of less then 3%. The two other methods Skew-Fit and RND cannot solve the problem below upper limit 3000 trajectories.

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+Skew-Explore 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.

4.3. TASK WITH A LONG HORIZON AND REAL WORLD DEMONSTRATION:

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. 

5. CONCLUSION:

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 Skew-Explore 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.

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.

EQUATION

EQUATION

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 -t i 2 √ 2 subject to t i ≥ 0, ∀t i N -1 i=1 t i ≤ B h -B l ,

Solving this problem using the KKT conditions will give us that when t i = B h -B l N -1 , ∀t i , 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:

EQUATION

)

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.

Q.E.D. Lemma D.2. When S = Z + N holds, the following expression

EQUATION

holds.

Proof.:

Remark. Here we note that we will use following equations in later proof,

EQUATION

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

EQUATION

Now we proceed to prove that h(Z|Z + N) = h(N|Z + N),

EQUATION

We replace h(Z|Z + N) with h(N|Z + N) in Eq. 16 to have

EQUATION

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

EQUATION

Q.E.D

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 E.1 ENVIRONMENT DETAILS:

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. 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.

:

https://anonymous.4open.science/r/b4596073-4cbc-4ac6-b85b-e9a786909058/

https://www.dropbox.com/s/xxw7ug3lnud3h0j/video_submission.mp4

Figures and Tables:

Figure 2: This figure shows a comparison between the state distribution p(s) (dashed blue) and a corresponding novelty frontier distribution skewed from p(s) (red).

Fig 2 illustrates the estimated frontier distribution skewed from p(s).

Figure 4: The PointMaze environment and the DoorOpen environment.

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).

Figure 5: Results of how coverage and entropy changes over iterations in PointMaze (left) and the DoorOpen (right) environments.

Figure 6: Results of how coverage changes over iterations in the PointMaze environment.

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.

Figure 7: (a) Relation between average extrinsic reward per iterations. (b) From up to down, left to right, this figure shows a sequence of the converged policy for the OpenPressClose task, which is a long horizon task with a sparse reward given only at the end.

Figure 9: This figure demonstrates the relationship between overall coverage and overlapping area.

Figure 10: Five uniformly distributed points in PointMaze environment and the DoorOpen environment.

Peer review (iclr2020):
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. Overall, the paper tackles an important questions of exploration, and while the concept of a frontier set is not novel, the authors propose a concrete instantiation that has promising results on continuous state spaces. I*m skeptical that this exact algorithm would work on domains with complex state spaces (e.g. images), where adding Gaussian noise to your state won*t produce reasonable nearby states. That said, the general idea of fitting a new model to the latest trajectory and using KL as reward seems like a promising principle that could on its own scale. However, the theory seems a bit off and there are a few experimental details that make me hesitant to increase my score. In details: Theory: I found the proof surprisingly long given that it amounts to saying that if (1) S = Z + N and (2) Z and N are independent, then H(S) >= H(N) and so H(S | Z) - H(Z | S) = H(S) - H(Z) >= H(N) - H(Z) Perhaps more worrisome is the statement, *we consider to maximize h(S|Z) - h(Z|S)*. Unless I misread the paper, the authors do not maximize this quantity. Instead, they *fix* this quantity by choosing a fixed entropy of N. Worse yet, this quantity is actually minimizes since, while h(N) is fixed for the duration of the experiment, h(Z) is maximized (*To increase h(Z), we need to add...*). It would be good for the authors to address this concern, given that the claim of the paper is that they are *maximizing the entropy of the visited states.* It seems like a simple answer is the following: given that S = Z + N, if N is fixed to some Gaussian distribution, then the authors simply need to maximize H(Z), which they are already doing. I*m not sure why the authors need to reason about H(S | Z) - H(Z | S). Experiments: Can Table 1 be replaced with the learning curves? The numbers 90% success and standard deviation of 3% seem like arbitrary numbers. It doesn*t preclude the possibility that (e.g.) Skew-Fit or RND receives a 99% success rate with standard deviation of 3.1%. Figure 11 and 12 of the Appendix don*t convince me that threshold at 90% and 3% is a particularly good choice. Can the authors summarize the difference between coverage and entropy in the main paper? It seems like an important distinction. Given that the authors did not use all 8 pages, it would be good to explain it there rather than in the Appendix. How sensitive is the method to the hyperparameter alpha? How was it chosen? Is it the same alpha chosen for Skew-Fit? How was N chosen for the door environment? Is Figure 7 (left) showing the performance on the simulated or real-world robot? If it was done on the real-world robot, were there any important details in getting sim-to-real-world to work? In Figure 5, why does there seem to be discrete jumps in the learning curves for *DoorOpen Coverage*? I would be inclined to raise my score if: 1. The authors clarify why studying the quantity H(S | Z) - H(Z | S) is particularly important. 2. Address the concerns raised over the experiments. 3. Discuss more explicitly under what assumption they expect for this method (with a Gaussian KDE) to work well