Year: 2021

Abstract:
Learning meaningful behaviors in the absence of reward is a difficult problem in reinforcement learning. A desirable and challenging unsupervised objective is to learn a set of diverse skills that provide a thorough coverage of the state space while being directed, i.e., reliably reaching distinct regions of the environment. In this paper, we build on the mutual information framework for skill discovery and introduce UPSIDE, which addresses the coverage-directedness trade-off in the following ways: 1) We design policies with a decoupled structure of a directed skill, trained to reach a specific region, followed by a diffusing part that induces a local coverage. 2) We optimize policies by maximizing their number under the constraint that each of them reaches distinct regions of the environment (i.e., they are sufficiently discriminable) and prove that this serves as a lower bound to the original mutual information objective. 3) Finally, we compose the learned directed skills into a growing tree that adaptively covers the environment. We illustrate in several navigation and control environments how the skills learned by UPSIDE solve sparse-reward downstream tasks better than existing baselines.

heading: 1 INTRODUCTION
text: Deep reinforcement learning (RL) algorithms have been shown to effectively solve a wide variety of complex problems (e.g., Mnih et al., 2015; Bellemare et al., 2013). However, they are often designed to solve one single task at a time and they need to restart the learning process from scratch for any new problem, even when it is defined on the very same environment (e.g., a robot navigating to different locations in the same apartment). Recently, Unsupervised RL (URL) has been proposed as an approach to address this limitation. In URL, the agent first interacts with the environment without any extrinsic reward signal. Afterward, the agent leverages the experience accumulated during the unsupervised learning phase to efficiently solve a variety of downstream tasks defined on the same environment. This approach is particularly effective in problems such as navigation (see e.g., Bagaria et al., 2021) and robotics (see e.g., Pong et al., 2020) where the agent is often required to readily solve a wide range of tasks while the dynamics of environment remains fixed.
In this paper, we focus on the unsupervised objective of discovering a set of skills that can be used to efficiently solve sparse-reward downstream tasks. In particular, we build on the insight that mutual information (MI) between the skills’ latent variables and the states reached by them effectively formalizes the dual objective of learning policies that both cover and navigate the environment efficiently (e.g., Gregor et al., 2016). Indeed, maximizing MI has been shown to be a powerful approach for encouraging exploration in RL (Houthooft et al., 2016; Mohamed & Rezende, 2015) and for unsupervised skill discovery (e.g., Gregor et al., 2016; Eysenbach et al., 2019; Achiam et al., 2018; Sharma et al., 2020; Campos et al., 2020). Nonetheless, learning policies that maximize MI is a challenging optimization problem. Several approximations have been proposed to simplify it at the cost of possibly deviating from the original objective of coverage and directedness (see Sect. 4 for a review of related work).
In this paper, we propose UPSIDE (UnsuPervised Skills that dIrect then DiffusE) to learn a set of policies that can be effectively used to cover the environment and solve goal-reaching downstream tasks. Our solution builds on the following components (Fig. 1):
• Policy structure (Sect. 3.1, see Fig. 1 (A)). We consider policies composed of two parts: 1) a directed part, referred to as the skill, that is trained to reach a specific region of the environment, and 2) a diffusing part that induces a local coverage around the region attained by the first part. This structure favors coverage and directedness at the level of a single policy.
• New constrained objective (Sect. 3.2, see Fig. 1 (B) & (C)). We then introduce a constrained optimization problem designed to maximize the number of policies under the constraint that the states reached by each of the diffusing parts are distinct enough (i.e., they satisfy a minimum level of discriminability). We prove that this problem can be cast as a lower bound to the original MI objective, thus preserving its coverage-directedness trade-off. UPSIDE solves it by adaptively adding or removing policies to a given initial set, without requiring any prior knowledge on a sensible number of policies.
• Tree structure (Sect. 3.3, see Fig. 1 (D) & (E)). Leveraging the directed nature of the skills, UPSIDE effectively composes them to build longer and longer policies organized in a tree structure. This overcomes the need of defining a suitable policy length in advance. Thus in UPSIDE we can consider short policies to make the optimization easier, while composing their skills along a growing tree structure to ensure an adaptive and thorough coverage of the environment.
The combination of these components allows UPSIDE to effectively adapt the number and the length of policies to the specific structure of the environment, while learning policies that ensure coverage and directedness. We study the effectiveness of UPSIDE and the impact of its components in hardto-explore continuous navigation and control environments, where UPSIDE improves over existing baselines both in terms of exploration and learning performance.

heading: 2 SETTING
text: We consider the URL setting where the agent interacts with a Markov decision process (MDP) M with state space S, action space A, dynamics p(s′|s, a), and no reward. The agent starts each episode from a designated initial state s0 ∈ S.1 Upon termination of the chosen policy, the agent is then reset to s0. This setting is particularly challenging from an exploration point of view since the agent cannot rely on the initial distribution to cover the state space.
We recall the MI-based unsupervised skill discovery approach (see e.g., Gregor et al., 2016). Denote by Z some (latent) variables on which the policies of length T are conditioned2 (we assume that Z is categorical for simplicity and because it is the most common case in practice). There are three optimization variables: (i) the cardinality of Z denoted by NZ , i.e., the number of policies (we write Z = {1, . . . , NZ} = [NZ ]), (ii) the parameters π(z) of the policy indexed by z ∈ Z, and (iii) the
1More generally, s0 could be drawn from any distribution supported over a compact region. 2In URL, there is no terminal state and the agent has to define a criterion to terminate the episode and restart.
In practice, most of unsupervised skill discovery methods set a fixed number of steps.
policy sampling distribution ρ (i.e., ρ(z) is the probability of sampling policy z at the beginning of the episode). Denote policy z’s action distribution in state s by π(·|z, s) and the entropy function by H. Let the variable ST be the random (final) state induced by sampling a policy z from ρ and executing π(z) from s0 for an episode. Denote by pπ(z)(sT ) the distribution over (final) states induced by executing policy z, by p(z|sT ) the probability of z being the policy to induce state sT , and let p(sT ) = ∑ z∈Z ρ(z)pπ(z)(sT ). Maximizing the MI between Z and ST can be written as
max NZ , ρ, π I(ST ;Z) = H(ST )−H(ST |Z) = − ∑ sT p(sT ) log p(sT ) + ∑ z∈Z ρ(z)EsT |z [ log pπ(z)(sT ) ] = H(Z)−H(Z|ST ) = −
∑ z∈Z ρ(z) log ρ(z) + ∑ z∈Z ρ(z)EsT |z [log p(z|sT )] , (1)
where in the expectations sT |z ∼ pπ(z)(sT ). In the first formulation, the entropy term over states captures the requirement that policies thoroughly cover the state space, while the second term measures the entropy over the states reached by each policy and thus promotes policies that have a directed behavior. Learning the optimal NZ , ρ, and π is a challenging problem and several approximations have been proposed (see e.g., Gregor et al., 2016; Eysenbach et al., 2019; Achiam et al., 2018; Campos et al., 2020). Many approaches focus on the so-called reverse formulation of the MI (second line of Equation 1). In this case, the conditional distribution p(z|sT ) is usually replaced with a parametric model qφ(z|sT ) called the discriminator that is trained via a negative log likelihood loss simultaneously with all other variables. Then one can maximize the lower bound (Barber & Agakov, 2004): I(ST ;Z) ≥ Ez∼ρ(z),τ∼π(z) [log qφ(z|sT )− log ρ(z)], where we denote by τ ∼ π(z) trajectories sampled from the policy indexed by z. As a result, each policy π(z) can be trained with RL to maximize the intrinsic reward rz(sT ) := log qφ(z|sT )− log ρ(z).
3 THE UPSIDE ALGORITHM
In this section we detail the three main components of UPSIDE, which is summarized in Sect. 3.4.

heading: 3.1 DECOUPLED POLICY STRUCTURE OF DIRECT-THEN-DIFFUSE
text: While the trade-off between coverage and directedness is determined by the MI objective, the amount of stochasticity of each policy (e.g., injected via a regularization on the entropy over the actions) has also a major impact on the effectiveness of the overall algorithm (Eysenbach et al., 2019). In fact, while randomness can promote broader coverage, a highly stochastic policy tends to induce a distribution pπ(z)(sT ) over final states with high entropy, thus decreasing −H(ST |Z) and losing in directedness. In UPSIDE, we define policies with a decoupled structure (see Fig. 1 (A)) composed of a) a directed part (of length T ) that we refer to as skill, with low stochasticity and trained to reach a specific region of the environment and b) a diffusing part (of length H) with high stochasticity to promote local coverage of the states around the region reached by the skill.
Coherently with this structure, the state variable in the conditional entropy in Equation 1 becomes any state reached during the diffusing part (denote by Sdiff the random variable) and not just the skill’s terminal state. Following Sect. 2 we define an intrinsic reward rz(s) = log qφ(z|s)− log ρ(z) and the skill of policy z maximizes the cumulative reward over the states traversed by the diffusing part. Formally, we can conveniently define the objective function:
max π(z) Eτ∼π(z) [∑ t∈J α · rz(st) + β · H(π(·|z, st)) ] , (2)
where J = {T, . . . , T + H} and α = 1, β = 0 (resp.α = 0, β = 1) when optimizing for the skill (resp. diffusing part). In words, the skill is incentivized to bring the diffusing part to a discriminable region of the state space, while the diffusing part is optimized by a simple random walk policy (i.e., a stochastic policy with uniform distribution over actions) to promote local coverage around sT .
Table 1 illustrates how UPSIDE’s policies compare to other methods. Unlike VIC and similar to DIAYN, the diffusing parts of the policies tend to “push” the skills away so as to reach diverse
regions of the environment. The combination of the directedness of the skills and local coverage of the diffusing parts thus ensures that the whole environment can be properly visited with NZ |S| policies.3 Furthermore, the diffusing part can be seen as defining a cluster of states that represents the goal region of the directed skill. This is in contrast with DIAYN policies whose stochasticity may be spread over the whole trajectory. This allows us to “ground” the latent variable representations of the policies Z to specific regions of the environment (i.e., the clusters). As a result, maximizing the MI I(Sdiff;Z) can be seen as learning a set of “cluster-conditioned” policies.

heading: 3.2 A CONSTRAINED OPTIMIZATION PROBLEM
text: In this section we consider π as fixed and we focus on how to optimize the number of policies NZ and the policy sampling distribution ρ(z). The standard practice for Equation 1 is to preset a fixed number of policies NZ and to fix the distribution ρ to be uniform (see e.g., Eysenbach et al., 2019; Baumli et al., 2021; Strouse et al., 2021). However, using a uniform ρ over a fixed number of policies may be highly suboptimal, in particular when NZ is not carefully tuned. In App. A.2 we give a simple example and a theoretical argument how the MI can be increased by removing skills with low discriminability when ρ is uniform. Motivated by this observation, in UPSIDEwe focus on maximizing the number of policies that are discriminable enough. We fix the sampling distribution ρ to be uniform over N policies and define the following constrained optimization problem
max N≥1 N s.t. min z∈[N ] Esdiff [log qφ(z|sdiff)] ≥ log η, (Pη)
where qφ(z|sdiff) denotes the probability of z being the policy traversing sdiff during its diffusing part according to the discriminator and η ∈ (0, 1) defines a minimum discriminability threshold. By optimizing for (Pη), UPSIDE automatically adapts the number of policies to promote coverage, while still guaranteeing that each policy reaches a distinct region of the environment. Alternatively, we can interpret (Pη) under the lens of clustering: the aim is to find the largest number of clusters (i.e., the region reached by the directed skill and covered by its associated diffusing part) with a sufficient level of inter-cluster distance (i.e., discriminability) (see Fig. 1). The following lemma (proof in App. A) formally links the constrained problem (Pη) back to the original MI objective. Lemma 1. There exists a value η† ∈ (0, 1) such that solving (Pη†) is equivalent to maximizing a lower bound on the mutual information objective maxNZ , ρ I(Sdiff;Z). Since (Pη†) is a lower bound to the MI, optimizing it ensures that the algorithm does not deviate too much from the dual covering and directed behavior targeted by MI maximization. Interestingly, Lem. 1 provides a rigorous justification for using a uniform sampling distribution restricted to the η-discriminable policies, which is in striking contrast with most of MI-based literature, where a uniform sampling distribution ρ is defined over the predefined number of policies.

heading: 3.3 COMPOSING SKILLS IN A GROWING TREE STRUCTURE
text: Both the original MI objective and our constrained formulation (Pη) depend on the initial state s0 and on the length of each policy. Although these quantities are usually predefined and only appear implicitly in the equations, they have a crucial impact on the obtained behavior. In fact, resetting after each policy execution unavoidably restricts the coverage to a radius of at most T + H steps around s0. This may suggest to set T and H to large values. However, increasing T makes training the skills more challenging, while increasing H may not be sufficient to improve coverage.
Instead, we propose to “extend” the length of the policies through composition. We rely on the key insight that the constraint in (Pη) guarantees that the directed skill of each η-discriminable policy reliably reaches a specific (and distinct) region of the environment and it is thus re-usable and amenable to composition. We thus propose to chain the skills so as to reach further and further parts of the state space. Specifically, we build a growing tree, where the root node is a diffusing part around s0, the edges represent the skills, and the nodes represent the diffusing parts. When a policy z is selected, the directed skills of its predecessor policies in the tree are executed first (see Fig. 9 in App. B for an illustration). Interestingly, this growing tree structure builds a curriculum on the episode lengths which grow as the sequence (iT + H)i≥1, thus avoiding the need of prior
3Equation 1 is maximized by setting NZ = |S| (i.e., maxY I(X,Y ) = I(X,X) = H(X)), where each z represents a goal-conditioned policy reaching a different state, which implies having as many policies as states, thus making the learning particularly challenging.
knowledge on an adequate horizon of the downstream tasks.4 Here this knowledge is replaced by T and H which are more environment-agnostic and task-agnostic choices as they rather have an impact on the size and shape of the learned tree (e.g., the smaller T and H the bigger the tree).

heading: 3.4 IMPLEMENTATION
text: We are now ready to introduce the UPSIDE algorithm, which provides a specific implementation of the components described before (see Fig. 1 for a qualitative illustration, Alg. 1 for a short pseudo-code and Alg. 2 in App. B for the detailed version). We first make approximations so that the constraint in (Pη) is easier to estimate. We remove the logarithm from the constraint to have an estimation range of [0, 1] and thus lower variance.5 We also replace the expectation over swith an empirical estimate q̂(B)φ (z) = 1 |Bz| ∑ s∈Bz qφ(z|s), where Bz denotes the set of the lastB states observed while executing the diffusing part of z. Integrating this in (Pη) leads to
max N≥1,π N s.t. min z∈[N ] q̂(B)φ (z) ≥ η, (3) where η is an hyper-parameter.6 Interestingly, the optimization over N can be solved by a simple greedy strategy. Since the function g(N) := minz∈[N ] maxπ(z) Esdiff [log qφ(z|sdiff)] is non-increasing in N with g(1) = 0 (i.e., the more policies the harder it is to meet the constraint), the incremental policy addition or removal in Alg. 1 (lines 5 & 9) is guaranteed to terminate with the optimal number of policies independently from the number of initial policies N .
Algorithm 1: UPSIDE Parameters: Discriminability threshold η ∈ (0, 1), branching factor N start, Nmax. Initialize: Tree T initialized as a root node, policies-to-expand candidatesQ = {0}.
while Q 6= ∅ do // tree expansion 1 Dequeue a policy z ∈ Q and create N = N start nodes C(z) rooted at z. 2 POLICYLEARNING(T , C(z)). 3 if minz′∈C(z) q̂(B)φ (z
′) > η then // Node addition
4 while minz′∈C(z) q̂(B)φ (z ′) > η and N < Nmax do 5 Increment N = N + 1 and add one policy to C(z). 6 POLICYLEARNING(T , C(z)). 7 else // Node removal 8 while minz′∈C(z) q̂(B)φ (z ′) < η and N > 1 do 9 Reduce N = N − 1 and
remove least discriminable policy from C(z).
10 POLICYLEARNING(T , C(z)). 11 Enqueue η-discriminable nodes C(z)
inQ.
We then integrate the optimization of Equation 3 into an adaptive tree expansion strategy that incrementally composes skills (Sect. 3.3). The tree is initialized with a root node corresponding to a policy only composed of the diffusing part around s0. Then UPSIDE iteratively proceeds through the following phases: (Expansion) While policies/nodes can be expanded according to different ordering rules (e.g., a FIFO strategy), we rank them in descending order by their discriminability (i.e., q̂(B)φ (z)), thus favoring the expansion of policies that reach regions of the state space that are not too saturated. Given a candidate leaf z to expand from the tree, we introduce new policies by adding a set C(z) of N = N start nodes rooted at node z (line 2, see also steps (A) and (D) in Fig. 1). (Policy learning) The new policies are optimized in three steps (see App. B for details on the POLICYLEARNING subroutine): i) sample states from the diffusing parts of the new policies sampled uniformly from C(z), ii) update the discriminator and compute the discriminability q̂(B)φ (z′) of new policies z′ ∈ C(z), iii) update the skills to optimize the reward (Sect. 3.1) computed using the discriminator (see step (B) in Fig. 1). For faster convergence and stability, already consolidated policies are kept fixed, and the states sampled from their associated diffusing parts are kept in memory in small replay buffers Bz which we call state buffers of size B (in our experiments, we use B = 10H). (Node adaptation) Once the policies are trained, UPSIDE proceeds with optimizing N in a greedy fashion. If all the policies in C(z) have an (estimated) discriminability larger than η
4See e.g., the discussion in Mutti et al. (2021) on the “importance of properly choosing the training horizon in accordance with the downstream-task horizon the policy will eventually face.”
5While Gregor et al. (2016); Eysenbach et al. (2019) employ rewards in the log domain, we find that mapping rewards into [0, 1] works better in practice, as observed in Warde-Farley et al. (2019); Baumli et al. (2021).
6Ideally, we would set η = η† from Lem. 1, however η† is non-trivial to compute. A strategy may be to solve (Pη′) for different values of η′ and select the one that maximizes the MI lower bound E [log qφ(z|sdiff)− log ρ(z)]. In our experiments we rather use the same predefined parameter of η = 0.8 which avoids computational overhead and performs well across all environments.
(lines 3-5), a new policy is tentatively added to C(z), the policy counterN is incremented, the policy learning step is restarted, and the algorithm keeps adding policies until the constrained is not met anymore or a maximum number of policies is attained. Conversely, if every policy in C(z) does not meet the discriminability constraint (lines 7-9), the one with lowest discriminability is removed from C(z), the policy learning step is restarted, and the algorithm keeps removing policies until all policies satisfy the constraint or no policy is left (see step (C) in Fig. 1). The resulting C(z) is added to the set of consolidated policies (line 11) and UPSIDE iteratively proceeds by selecting another node to expand until no node can be expanded (i.e., the node adaptation step terminates with N = 0 for all nodes) or a maximum number of environment iterations is met.

heading: 4 RELATED WORK
text: URL methods can be broadly categorized depending on how the experience of the unsupervised phase is summarized to solve downstream tasks in a zero- or few-shot manner. This includes modelfree (e.g., Pong et al., 2020), model-based (e.g., Sekar et al., 2020) and representation learning (e.g., Yarats et al., 2021) methods that build a representative replay buffer to learn accurate estimates or low-dimensional representations. An alternative line of work focuses on discovering a set of skills in an unsupervised way. Our approach falls in this category, on which we now focus this section.
Skill discovery based on MI maximization was first proposed in VIC (Gregor et al., 2016), where the trajectories’ final states are considered in the reverse form of Equation 1 and the policy parameters π(z) and sampling distribution ρ are simultaneously learned (with a fixed number of skills NZ). DIAYN (Eysenbach et al., 2019) fixes a uniform ρ and weighs skills with an action-entropy coefficient (i.e., it additionally minimizes the MI between actions and skills given the state) to push the skills away from each other. DADS (Sharma et al., 2020) learns skills that are not only diverse but also predictable by learned dynamics models, using a generative model over observations (rather than over skills) and optimizing a forward form of MI I(s′; z|s) between the next state s′ and current skill z (with continuous latent) conditioned on the current state s. EDL (Campos et al., 2020) shows that existing skill discovery approaches can provide insufficient coverage and relies on a fixed distribution over states that is either provided by an oracle or learned. SMM (Lee et al., 2019) uses the MI formalism to learn a policy whose state marginal distribution matches a target state distribution (e.g., uniform). Other MI-based skill discovery methods include Florensa et al. (2017); Hansen et al. (2019); Modhe et al. (2020); Baumli et al. (2021); Xie et al. (2021); Liu & Abbeel (2021); Strouse et al. (2021), and extensions in non-episodic settings (Xu et al., 2020; Lu et al., 2020).
While most skill discovery approaches consider a fixed number of policies, a curriculum with increasing NZ is studied in Achiam et al. (2018); Aubret et al. (2020). We consider a similar discriminability criterion in the constraint in (Pη) and show that it enables to maintain skills that can be readily composed along a tree structure, which can either increase or decrease the support of available skills depending on the region of the state space. Recently, Zhang et al. (2021) propose a hierarchical RL method that discovers abstract skills while jointly learning a higher-level policy to maximize extrinsic reward. Our approach builds on a similar promise of composing skills instead of resetting to s0 after each execution, yet we articulate the composition differently, by exploiting the direct-then-diffuse structure to ground skills to the state space instead of being abstract. Approaches such as DISCERN (Warde-Farley et al., 2019) and Skew-Fit (Pong et al., 2020) learn a goalconditioned policy in an unsupervised way with an MI objective. As explained by Campos et al. (2020), this can be interpreted as a skill discovery approach with latent Z = S, i.e., where each goal state can define a different skill. Conditioning on either goal states or abstract latent skills forms two extremes of the spectrum of unsupervised RL. As argued in Sect. 3.1, we target an intermediate approach of learning “cluster-conditioned” policies. Finally, an alternative approach to skill discovery builds on “spectral” properties of the dynamics of the MDP. This includes eigenoptions (Machado et al., 2017; 2018) and covering options (Jinnai et al., 2019; 2020), and the algorithm of Bagaria et al. (2021) that builds a discrete graph representation which learns and composes spectral skills.

heading: 5 EXPERIMENTS
text: Our experiments investigate the following questions: i) Can UPSIDE incrementally cover an unknown environment while preserving the directedness of its skills? ii) Following the unsupervised phase, how can UPSIDE be leveraged to solve sparse-reward goal-reaching downstream tasks? iii) What is the impact of the different components of UPSIDE on its performance?
We report results on navigation problems in continuous 2D mazes7 and on continuous control problems (Brockman et al., 2016; Todorov et al., 2012): Ant, Half-Cheetah and Walker2d. We evaluate performance with the following tasks: 1) “coverage” which evaluates the extent to which the state space has been covered during the unsupervised phase, and 2) “unknown goal-reaching” whose objective is to find and reliably reach an unknown goal location through fine-tuning of the policy.
We compare UPSIDE to different baselines. First we consider DIAYN-NZ (Eysenbach et al., 2019), where NZ denotes a fixed number of skills. We introduce two new baselines derived from DIAYN: a) DIAYN-curr is a curriculum variant where the number of skills is automatically tuned following the same procedure as in UPSIDE, similar to Achiam et al. (2018), to ensure sufficient discriminability, and b) DIAYN-hier is a hierarchical extension of DIAYN where the skills are composed in a tree as in UPSIDE but without the diffusing part. We also compare to SMM (Lee et al., 2019), which is similar to DIAYN but includes an exploration bonus encouraging the policies to visit rarely encountered states. In addition, we consider EDL (Campos et al., 2020) with the assumption of the available state distribution oracle (since replacing it by SMM does not lead to satisfying results in presence of bottleneck states as shown in Campos et al., 2020). Finally, we consider the RANDOM policy, which samples actions uniformly in the action space. We use TD3 as the policy optimizer (Fujimoto et al., 2018) though we also tried SAC (Haarnoja et al., 2018) which showed equivalent results than TD3 with harder tuning. Similar to e.g., Eysenbach et al. (2019); Bagaria & Konidaris (2020), we restrict the observation space of the discriminator to the cartesian coordinates (x, y) for Ant and x for Half-Cheetah and Walker2d. All algorithms were ran on Tmax = 1e7 unsupervised environment interactions in episodes of size Hmax = 200 (resp. 250) for mazes (resp. for control). For
7The agent observes its current position and its actions (in [−1,+1]) control its shift in x and y coordinates. We consider two topologies of mazes illustrated in Fig. 2 with size 50× 50 such that exploration is non-trivial. The Bottleneck maze is a harder version of the one in Campos et al. (2020, Fig. 1) whose size is only 10× 10.
UPSIDE DIAYN-5 DIAYN-10 DIAYN-20 RANDOM
baselines, models are selected according to the cumulated intrinsic reward (as done in e.g., Strouse et al., 2021), while UPSIDE, DIAYN-hier and DIAYN-curr are selected according to the highest number of η-discriminable policies. On the downstream tasks, we consider ICM (Pathak et al., 2017) as an additional baseline. See App. C for the full experimental details.
Coverage. We analyze the coverage achieved by the various methods following an unsupervised phase of at most Tmax = 1e7 environment interactions. For UPSIDE, we report coverage for the skill and diffusing part lengths T = H = 10 in the continuous mazes (see App. D.4 for an ablation on the values of T,H) and T = H = 50 in control environments. Fig. 2 shows that UPSIDE manages to cover the near-entirety of the state space of the bottleneck maze (including the top-left room) by creating a tree of directed skills, while the other methods struggle to escape from the bottleneck region. This translates quantitatively in the coverage measure of Table 2 where UPSIDE achieves the best results. As shown in Fig. 3 and 4, UPSIDE clearly outperforms DIAYN and RANDOM in state-coverage of control environments, for the same number of environment interactions. In the Ant domain, traces from DIAYN (Fig. 4b) and discriminator curves in App. D.3 demonstrate that even though DIAYN successfully fits 20 policies by learning to take a few steps then hover, it fails to explore the environment. In Half-Cheetah and Walker2d, while DIAYN policies learn to fall on the agent’s back, UPSIDE learns to move forward/backward on its back through skill composition.
Unknown goal-reaching downstream tasks. We investigate how the tree of policies learned by UPSIDE in the unsupervised phase can be used to tackle goal-reaching downstream tasks. All unsupervised methods follow the same protocol: given an unknown8 goal g, a) (exploration) first we sample rollouts over the different policies, b) then we select the best policy based on the maximum discounted cumulative reward collected and c) we fine-tune this policy to maximize the sparse reward r(s) = I[‖s − g‖2 ≤ 1]. Fig. 5 reports the
8Notice that if the goal was known, the learned discriminator could be directly used to identify the most promising skill to fine-tune.
discounted cumulative reward on various unknown goals after the fine-tuning phase. We see that UPSIDE accumulates more reward than the other methods, in particular in regions far from s0, where performing fine-tuning over the entire skill path is especially challenging. In Fig. 6 we focus on a specific unknown goal region that baselines fail to reach: we see that UPSIDE’s fine-tuning can slightly deviate from the original tree structure to improve the goalreaching behavior of its candidate policy. We also perform finetuning on the Ant domain under the same setting (unknown goals and sparse rewards). In Fig. 4c, we show that UPSIDE clearly outperforms DIAYN-20 and TD3 when we evaluate the average success rate of reaching 48 goals sampled uniformly in [−8, 8]2. Note that DIAYN particularly fails as its policies learned during the unsupervised phase all stay close to the origin s0.
Ablative study of the UPSIDE components. The main components of UPSIDE that differ from existing skill discovery approaches such as DIAYN are: the decoupled policy structure, the constrained optimization problem and the skill chaining via the growing tree. We perform ablations to show that all components are simultaneously required for good performance. First, we compare UPSIDE to flat UPSIDE, i.e., UPSIDE with the tree depth of 1 (T = 150, H = 50). Table 2 reveals that the tree structuring is key to improve exploration and escape bottlenecks; it makes the agent learn on smaller and easier problems (i.e., short-horizon MDPs) and mitigates the optimization issues (e.g., non-stationary rewards). However, the diffusing part of flat UPSIDE largely improves the coverage performance over the DIAYN baseline, suggesting that the diffusing part is an interesting structural bias on the entropy regularization that pushes the policies away from each other. This is particularly useful on the Ant environment as shown in Fig. 4. A challenging aspect is to make the skill composition work. As shown in Table 1, DIAYN-hier (a hierarchical version of DIAYN) does not perform as well as UPSIDE by a clear margin. In fact, UPSIDE’s direct-then-diffuse decoupling enables both policy re-usability for the chaining (via the directed skills) and local coverage (via the diffusing part). Moreover, as shown by the results of DIAYN-hier on the bottleneck maze, the constrained optimization problem (Pη) combined with the diffusing part is crucial to prevent consolidating too many policies, thus allowing a sample efficient growth of the tree structure.

heading: 6 CONCLUSION AND LIMITATIONS
text: We introduced UPSIDE, a novel algorithm for unsupervised skill discovery designed to trade off between coverage and directedness and develop a tree of skills that can be used to perform efficient exploration and solve sparse-reward goal-reaching downstream tasks. Limitations of our approach that constitute natural venues for future investigation are: 1) The diffusing part of each policy could be explicitly trained to maximize local coverage around the skill’s terminal state; 2) UPSIDE assumes a good state representation is provided as input to the discriminator, it would be interesting to pair UPSIDEwith effective representation learning techniques to tackle problems with high-dimensional input; 3) As UPSIDE relies on the ability to reset to establish a root node for its growing tree, it could be relevant to extend the approach in non-episodic environments.
Ethics Statement. We do not foresee any obvious negative societal impacts from our work, which focuses on the fundamentals of reinforcement learning and proposes a new algorithm for unsupervised skill discovery.
Reproducibility Statement. We have made several efforts to ensure that the results provided in the paper are fully reproducible. We provide a detailed algorithm in App. B.3, explanations on the implementation of baselines (App. C.1), an exhaustive list of all hyper-parameters (App. C.2) and a detailed experimental protocol that considers robustness in the evaluation of methods (App. C.3). We plan to release our code upon acceptance of this work.

heading: Appendix

heading: A Theoretical Details on Section 3 13
text: B UPSIDE Algorithm 16

heading: C Experimental Details 18

heading: D Additional Experiments 22

heading: A THEORETICAL DETAILS ON SECTION 3

heading: A.1 PROOF OF LEMMA 1
text: Restatement of Lemma 1. There exists a value η† ∈ (0, 1) such that solving (Pη†) is equivalent to maximizing a lower bound on the mutual information objective maxNZ , ρ I(Sdiff;Z).
Proof. Recall that we consider that π is fixed for convenience (the optimization process of the policies is studied in Sect. 3.1). Furthermore, we assume that the number of available skills is upper bounded, i.e., 1 ≤ NZ ≤ Nmax. We begin by lower bounding the negative conditional entropy by using the well known lower bound of Barber & Agakov (2004) on the mutual information
−H(Z|Sdiff) = ∑ z∈Z ρ(z)Esdiff [log p(z|sdiff)]
≥ ∑ z∈Z ρ(z)Esdiff [log qφ(z|sdiff)] .
We now use that any weighted average is lower bounded by its minimum component, which yields −H(Z|Sdiff) ≥ min
z∈Z Esdiff [log qφ(z|sdiff)] .
Thus the following objective is a lower bound on the original objective of maximizing I(Sdiff;Z) max
NZ=N,ρ
{ H(Z) + min
z∈[N ] Esdiff [log qφ(z|sdiff)]
} . (4)
Interestingly, the second term in Equation 4 no longer depends on the skill distribution ρ, while the first entropy term H(Z) is maximized by setting ρ to the uniform distribution over N skills (i.e., maxρH(Z) = log(N)). This enables to simplify the optimization which now only depends on N . Indeed, Equation 4 is equivalent to
max NZ=N
{ log(N) + min
z∈[N ] Esdiff [log qφ(z|sdiff)]
} . (5)
We define the functions f(N) := log(N), g(N) := min
z∈[N ] Esdiff [log qφ(z|sdiff)] .
Let N† ∈ arg maxN f(N) + g(N) and η† := exp g(N†) ∈ (0, 1). We now show that any solution of (Pη†) is a solution of Equation 5. Indeed, denote by N? the value that optimizes (Pη†). First, by validity of the constraint, it holds that g(N?) ≥ log η† = g(N†). Second, since N† meets the constraint, by optimality we have that N? ≥ N† and therefore f(N?) ≥ f(N†) since f is non-decreasing. We thus have{
g(N?) ≥ g(N†) f(N?) ≥ f(N†) =⇒ f(N ?) + g(N?) ≥ f(N†) + g(N†).
Putting everything together, an optimal solution for (Pη†) is an optimal solution for Equation 5, which is equivalent to Equation 4, which is a lower bound of the MI objective, thus concluding the proof.
A.2 SIMPLE ILLUSTRATION OF THE ISSUE WITH UNIFORM-ρ MI MAXIMIZATION
This section complements Sect. 3.2: we show a simple scenario where 1) considering both a uniform ρ prior and a fixed skill number NZ provably leads to suboptimal MI maximization, and where 2) the UPSIDE strategy of considering a uniform ρ restricted to the η-discriminable skills can provably increase the MI for small enough η.
Consider the simple scenario (illustrated on Fig. 7) where the agent has N skills indexed by n and must assign them to M states indexed by m. We assume that the execution of each skill deterministically brings it to the assigned state, yet the agent may assign stochastically (i.e., more than one state per skill). (A non-RL way to interpret this is that we
want to allocate N balls into M boxes.) Denote by pn,m ∈ [0, 1] the probability that skill n is assigned to state m. It must hold that ∀n ∈ [N ],∑m pn,m = 1. Denote by I the MI between the skill variable and the assigned state variable, and by I the MI under the prior that the skill sampling distribution ρ is uniform, i.e., ρ(n) = 1/N . It holds that
I(N,M) = logN + 1 N ∑ n,m pn,m log pn,m∑ n pn,m .
Let I?(N,M) := max{pn,m} I(N,M) and {p?n,m} ∈ arg max{pn,m} I(N,M). We also define the discriminability of skill n in state m as
qn,m := pn,m∑ n pn,m ,
as well as the minimum discriminability of the optimal assignment as
η := min n max m
q?n,m.
Lemma 2. There exist values of N and M such that the uniform-ρ MI be improved by removing a skill (i.e., by decreasing N ).
Proof. The following example shows that with M = 2 states, it is beneficial for the uniform-ρ MI maximization to go from N = 3 to N = 2 skills. Indeed, we can numerically compute the optimal solutions and we obtain for N = 3 and M = 2 that
I?(N = 3,M = 2) ≈ 0.918, p?n,m = (
0 1 0 1 1 0
) , q?n,m = ( 0 0.5 0 0.5 1 0 ) , η = 0.5,
whereas for N = 2 and M = 2, I?(N = 2,M = 2) = 1, p?n,m = ( 0 1 1 0 ) , q?n,m = ( 0 1 1 0 ) , η = 1.
As a result, I?(N = 2,M = 2) > I?(N = 3,M = 2), which concludes the proof. The intuition why I? is increased by decreasing N is that for N = 2 there is one skill per state whereas for N = 3 the skills must necessarily overlap. Note that this contrasts with the original MI (that also optimizes ρ) where decreasing N cannot improve the optimal MI.
The previous simple example hints to the fact that the value of the minimum discriminability of the optimal assignment η may be a good indicator to determine whether to remove a skill. The following more general lemma indeed shows that a sufficient condition is that η is small enough.
Lemma 3. Assume w.l.o.g. that the skill indexed by N has the minimum discriminability η, i.e., N ∈ arg minn maxm q?n,m. Define
∆(N, η) := logN − N − 1 N log(N − 1) + 1 N log η.

heading: If ∆(N, η) ≤ 0 — which holds for small enough η — then removing skill N results in a larger
text: uniform-ρ optimal MI, i.e., I?(N,M) < I?(N − 1,M).
Proof. It holds that
I?(N,M) ≤ logN + 1 N  ∑ n∈[N−1] ∑ m∈[M ] p?n,m log q ? n,m + ∑ m∈[M ] p?n,m log η  ≤ logN − N − 1
N log(N − 1)
+ N − 1 N log(N − 1) + 1 N − 1 ∑ n∈[N−1] ∑ m∈[M ] p?n,m log q ? n,m + 1 N log η
≤ ∆(N, η) + N − 1 N I?(N − 1,M).
As a result, if ∆(N, η) ≤ 0 then I?(N,M) < I?(N − 1,M).
B UPSIDE ALGORITHM
B.1 VISUAL ILLUSTRATIONS OF UPSIDE’S DESIGN MENTIONED IN SECTION 3
B.2 HIGH-LEVEL APPROACH OF UPSIDE

heading: B.3 DETAILS OF ALGORITHM 1
text: We give in Alg. 2 a more detailed version of Alg. 1 and we list some additional explanations below.
• When optimizing the discriminator, rather than sampling (state, policy) pairs with equal probability for all nodes from the tree T , we put more weight (e.g. 3×) on already consolidated policies, which seeks to avoid the new policies from invading the territory of the older policies that were previously correctly learned.
• A replay buffer is instantiated at every new expansion (line 2), thus avoiding the need to start collecting data from scratch with the new policies at every POLICYLEARNING call.
• J (line 22) corresponds to the number of policy updates ratio w.r.t. discriminator updates, i.e. for how long the discriminator reward is kept fixed, in order to add stationarity to the reward signal.
• Instead of using a number of iterationK to stop the training loop of the POLICYLEARNING function (line 16), we use a maximum number of environment interactions Ksteps for node expansion. Note that this is the same for DIAYN-hier and DIAYN-curr.
Algorithm 2: Detailed UPSIDE Parameters: Discriminability threshold η ∈ (0, 1), branching factor N start, Nmax Initialize: Tree T initialized as a root node index by 0, policy candidatesQ = {0}, state buffers BZ = {0 : [ ]}
while Q 6= ∅ do // tree expansion 1 Dequeue a policy z ∈ Q and create N = N start nodes C(z) rooted at z and add memory for states in the state buffers BZ 2 Instantiate new replay buffer BRL 3 POLICYLEARNING(BRL, BZ , T , C(z)) 4 if minz′∈C(z) d(z′) > η then // Node addition 5 while minz′∈C(z) d(z′) > η and N < Nmax do 6 Increment N = N + 1 and add one policy to C(z) 7 POLICYLEARNING(BRL, BZ , T , C(z)) 8 else // Node removal 9 while minz′∈C(z) d(z′) < η and N > 1 do
10 Reduce N = N − 1 and remove least discriminable policy from C(z) 11 POLICYLEARNING(BRL, BZ , T , C(z)) 12 Enqueue inQ the η-discriminable nodes C(z)
13 POLICYLEARNING(Replay buffer BRL, State buffers BZ , Tree T , policies to update ZU ) 14 Optimization parameters: patience K, policy-to-discriminator update ratio J , Kdiscr discriminator
update epochs, Kpol policy update epochs 15 Initialize: Discriminator qφ with |T | classes 16 for K iterations do // Training loop 17 For all z′ ∈ ZU , clear BZ [z′] then collect and add B states from the diffusing part of π(z′) to it 18 Train the discriminator qφ for Kdiscr steps with dataset ⋃ z′∈T BZ [z
′]. 19 Compute discriminability d(z′) = q̂(B)φ (z ′) = 1|Bz′ | ∑ s∈Bz′ qφ(z ′|s) for all z′ ∈ ZU 20 if minz′∈ZU d(z ′) > η then // Early stopping 21 Break 22 for J iterations do 23 For all z′ ∈ ZU , sample a trajectory from π(z′) and add to replay buffer BRL 24 For all z′ ∈ ZU , update policy π′z for Kpol steps to optimize the discriminator reward as in Sect. 3.1 keeping skills from parent policies fixed 25 Compute discriminability d(z′) for all z′ ∈ ZU
• The state buffer size B needs to be sufficiently large compared to H so that the state buffers of each policy represent well the distribution of the states generated by the policy’s diffusing part. In practice we set B = 10H .
• In POLICYLEARNING, we add Kinitial random (uniform) transitions to the replay buffer for each newly instantiated policies.
• Moreover, in POLICYLEARNING, instead of sampling uniformly the new policies we sample them in a round robin fashion (i.e., one after the other), which can be simply seen as a variance-reduced version of uniform sampling.
B.4 ILLUSTRATION OF THE EVOLUTION OF UPSIDE’S TREE ON A WALL-FREE MAZE
See Fig. 11.
B.5 ILLUSTRATION OF EVOLUTION OF UPSIDE’S TREE ON THE BOTTLENECK MAZE
See Fig. 12.

heading: C EXPERIMENTAL DETAILS

heading: C.1 BASELINES
text: DIAYN-NZ . This corresponds to the original DIAYN algorithm (Eysenbach et al., 2019) where NZ is the number of skills to be learned. In order to make the architecture more similar to UPSIDE, we use distinct policies for each skill, i.e. they do not share weights as opposed to Eysenbach et al. (2019). While this may come at the price of sample efficiency, it may also help put lesser constraint on the model (e.g. gradient interference).
DIAYN-curr. We augment DIAYN with a curriculum that enables to be less dependant on an adequate tuning of the hyperparameter of the number of skills of DIAYN. We consider the curriculum of UPSIDE where we start learning with N start policies during a period of time/number of interactions. If the configuration satisfies the discriminablity threshold η, a skill is added, otherwise a skill is removed or learning stopped (as in Alg. 2, lines 5-12). Note that the increasing version of
this curriculum is similar to the one proposed in VALOR (Achiam et al., 2018, Sect. 3.3). In our experiments, we use N start = 1.
DIAYN-hier. We extend DIAYN through the use of a hierarchy of directed skills, built following the UPSIDE principles. The difference between DIAYN-hier and UPSIDE is that the discriminator reward is computed over the entire directed skill trajectory, while it is guided by the diffusing part for UPSIDE. This introduced baseline can be interpreted as an ablation of UPSIDE without the decoupled structure of policies.
SMM. We consider SMM (Lee et al., 2019) as it is state-of-art in terms of coverage, at least on long-horizon control problems, although Campos et al. (2020) reported its poor performance in hard-to-explore bottleneck mazes. We tested the regular SMM version, i.e. learning a state density model with a VAE, yet we failed to make it work on the maze domains that we consider. As we use the cartesian (x, y) positions in maze domains, learning the identity function on two-dimensional input data is too easy with a VAE, thus preventing the benefits of using a density model to drive exploration. In our implementation, the exploration bonus is obtained by maintaining a multinomial distribution over “buckets of states” obtained by discretization (as in our coverage computation), resulting in a computation-efficient implementation that is more stable than the original VAE-based method. Note that the state distribution is computed using states from past-but-recent policies as suggested in the original paper.
EDL. We consider EDL (Campos et al., 2020) with the strong assumption of an available state distribution oracle (since replacing it by SMM does not lead to satisfying results in presence of bottleneck states as shown in Campos et al., 2020, page 7: “We were unable to explore this type of maze effectively with SMM”). In our implementation, the oracle samples states uniformly in the mazes avoiding the need to handle a complex exploration, but this setting is not realistic when facing unknown environments.

heading: C.2 ARCHITECTURE AND HYPERPARAMETERS
text: The architecture of the different methods remains the same in all our experiments, except that the number of hidden units changes across considered environments. For UPSIDE, flat UPSIDE (i.e., UPSIDE with a tree depth of 1), DIAYN, DIAYN-curr, DIAYN-hier and SMM the multiple policies do not share weights, however EDL policies all share the same network because of the constraint that the policy embedding z is learnt in a supervised fashion with the VQ-VAE rather than the unsupervised RL objective. We consider decoupled actor and critic optimized with the TD3 algorithm (Fujimoto et al., 2018) though we also tried SAC (Haarnoja et al., 2018) which showed equivalent results than TD3 with harder tuning. The actor and the critic have the same architecture that processes observations with a two-hidden layers (of size 64 for maze environments and 256 for control environments) neural networks. The discriminator is a two-hidden (of size 64) layer model with output size the number of skills in the tree.
Common (for all methods and environments) optimization hyper-parameters: • Discount factor: γ = 0.99 • σTD3 = {0.1, 0.15, 0.2} • Q-functions soft updates temperature τ = 0.005 • Policy Adam optimizer with learning rate lrpol = {1e−3, 1e−4} • policy inner epochs Kpol = {10, 100} • policy batch size Bpol = {64} • Discriminator delay: J = {1, 10} • Replay buffer maximum size: 1e6 • Kinitial = 1e3
We consider the same range of hyper-parameters in the downstream tasks.
UPSIDE, DIAYN and SMM variants (common for all environments) optimization hyperparameters:
• Discriminator batch size Bdiscr = 64 • Discriminator Adam optimizer with learning rate lrdiscr = {1e−3, 1e−4} • discriminator inner epochs Kdiscr = {10, 100} • Discriminator delay: J = {1, 10} • State buffer size B = 10H where the diffusing part length H is environment-specific.
EDL optimization hyper-parameters: We kept the same as Campos et al. (2020). The VQ-VAE’s architecture consists of an encoder that takes states as an input and maps them to a code with 2 hidden layers with 128 hidden units and a final linear layer, and the decoder takes the code and maps it back to states also with 2 hidden layers with 128 hidden units. It is trained on the oracle state distribution, then kept fixed during policy learning. Contrary to UPSIDE, DIAYN and SMM variants, the reward is stationary.
• βcommitment = {0.25, 0.5} • VQ-VAE’s code size 16 • VQ-VAE batch size Bvq-vae = {64, 256} • total number of epochs: 5000 (trained until convergence) • VQ-VAE Adam optimizer with learning rate lrvq-vae = {1e−3, 1e−4}

heading: Maze specific hyper-parameters:
text: • Ksteps = 5e4 (and in time 10 minutes) • T = H = 10 • Max episode length Hmax = 200 • Max number of interactions Tmax = 1e7 during unsupervised pre-training and downstream tasks.
Control specific optimization hyper-parameters: • Ksteps = 1e5 (and in time 1 hour) • T = H = 50 • Max episode length Hmax = 250 • Max number of interactions Tmax = 1e7 during unsupervised pre-training and downstream tasks.
Note that hyperparameters are kept fixed for the downstream tasks too.

heading: C.3 EXPERIMENTAL PROTOCOL
text: We now detail the experimental protocol that we followed, which is common for both UPSIDE and baselines, on all environments. It consists in the following three stages:
Unsupervised pre-training phase. Given an environment, each algorithm is trained without any extrinsic reward on Nunsup = 3 seeds which we call unsupervised seeds (to account for the randomness in the model weights’ initialization and environment stochasticity if present). Each training lasts for a maximum number of Tmax environment steps (split in episodes of length Hmax). This protocol actually favors the baselines since by its design, UPSIDE may decide to have fewer environment interactions than Tmax thanks to its termination criterion (triggered if it cannot fit any more policies); for instance, all baselines where allowed Tmax = 1e7 on the maze environments, but UPSIDE finished at most in 1e6 environment steps fitting in average 57 and 51 policies respectively for the Bottleneck Maze and U-Maze.
Model selection. For each unsupervised seed, we tune the hyper-parameters of each algorithm according to a certain performance metric. For the baselines, we consider the cumulated intrinsic reward (as done in e.g., Strouse et al., 2021) averaged over stochastic roll-outs. For UPSIDE, DIAYN-hier and DIAYN-curr, the model selection criterion is the number of consolidated policies, i.e., how many policies were η-discriminated during their training stage. For each method, we thus have as many models as seeds, i.e. Nunsup.
Downstream tasks. For each algorithm, we evaluate the Nunsup selected models on a set of tasks. All results on downstream tasks will show a performance averaged over the Nunsup seeds.
• Coverage. We evaluate to which extent the state space has been covered by discretizing the state space into buckets (10 per axis on the continuous maze domains) and counting how many buckets have been reached. To compare the global coverage of methods (and also to be fair w.r.t. the amount of injected noise that may vary across methods), we roll-out for each model its associated deterministic policies.
• Fine-tuning on goal-reaching task. We consider goal-oriented tasks in the discounted episodic setting where the agent needs to reach some unknown goal position within a certain radius (i.e., the goal location is unknown until it is reached once) and with sparse reward signal (i.e., reward of 1 in the goal location, 0 otherwise). The environment terminates when goal is reached or if the number of timesteps is larger than Hmax. The combination of unknown goal location and sparse reward makes the exploration problem very challenging, and calls upon the ability to first cover (for goal finding) and then navigate (for reliable goal reaching) the environment efficiently. To evaluate performance in an exhaustive manner, we discretize the state space into Bgoal = 14 buckets and we randomly sampleNgoal = 3 from each of these buckets according to what we call goal seeds (thus there are Bgoal × Ngoal = 10 different goals in total). For every goal seed, we initialize each algorithm with the set of policies learned during the unsupervised pre-training. We then roll-out each policy during Nexplo episodes to compute the cumulative reward of the policy, and select the best one to fine-tune. On UPSIDE, we complete the selected policy (of length denoted by L) by replacing the diffusing skill with a skill whose length is the remaining number of interactions left, i.e. Hmax − L. The ability of selecting a good policy is intrinsically linked to the coverage performance of the model, but also to few-shot adaptation. Learning curves and performance are averaged over unsupervised seeds, goal seeds, and over roll-outs of the stochastic policy. Since we are in the discounted episodic setting, fine-tuning makes sense, to reach as fast as possible the goal. This is particularly important as UPSIDE, because of its tree policy structure, can reach the goal sub-optimally w.r.t the discount. On the maze environments, we consider all unsupervised pre-training baselines as well as “vanilla” baselines trained from scratch during the downstream tasks: TD3 (Fujimoto et al., 2018) and ICM (Pathak et al., 2017). In the Ant environment, we also consider Ngoal = 3 and Bgoal = 14 in the [−8, 8]2 square.

heading: D ADDITIONAL EXPERIMENTS

heading: D.1 ADDITIONAL RESULTS ON BOTTLENECK MAZE
text: Here we include 1) Fig. 13 for an analysis of the predictions of the discriminator (see caption for details); 2) Fig. 14 for the policy visualizations for the remaining methods (i.e., those not reported in Fig. 2; 3) Fig. 15 for the downstream task performance for the remaining methods (i.e., those not reported in Fig. 5.

heading: D.2 ADDITIONAL RESULTS ON U-MAZE
text: Fig. 16 visualizes the policies learned during the unsupervised phase (i.e., the equivalent of Fig. 2 for the U-Maze), and Fig. 17 reports the heatmaps of downstream task performance (i.e., the equivalent of Fig. 5 for the U-Maze). The conclusion is the same as on the Bottleneck Maze described in Sect. 5: UPSIDE clearly outperforms all the baselines, both in coverage (Fig. 16) and in unknown goal-reaching performance (Fig. 17) in the downstream task phase.

heading: D.3 ANALYSIS OF THE DISCRIMINABILITY
text: In Fig. 18 (see caption) we investigate the average discriminability of DIAYN depending on the number of policies NZ .
UPSIDE Bottleneck Maze U-Maze T = H = 10 85.67 (±1.93) 71.33 (±0.42)
T = H = 20 87.33 (±0.42) 67.67 (±1.50)
T = H = 30 77.33 (±3.06) 68.33 (±0.83)
T = H = 40 59.67 (±1.81) 57.33 (±0.96)
T = H = 50 51.67 (±0.63) 58.67 (±1.26)
D.4 ABLATION ON THE LENGTHS T AND H OF THE UPSIDE POLICIES
Our ablation on the mazes in Fig. 19 investigates the sensitiveness of UPSIDE w.r.t.T and H , the lengths of the directed skills and diffusing parts of the policies. For the sake of simplicity, we kept T = H . It shows that the method is quite robust to reasonable choices of T and H , i.e., equal to 10 (as done in all other experiments) but also 20 or 30. Naturally, the performance degrades if T,H are chosen too large w.r.t. the environment size, in particular in the bottleneck maze which requires “narrow” exploration, thus composing disproportionately long skills hinders the coverage. For T = H = 50, we recover the performance of flat UPSIDE.

Review summaries:
The paper proposes a novel algorithm for learning unsupervised skills based on empowerment. Specifically, direct-and-diffuse policies are proposed that first optimize empowerment and then after a fixed number of episode steps optimize action entropy. This yields policies that go to a certain point in a directed manner and then move around that point at random. Further, the UPSIDE algorithm is based on tracking the policies with high discriminability (i.e. low H(z|x)). The algorithm keeps a set of policies that are currently above a threshold and attempts to add new policies incrementally. Finally, each new policy can be assigned a parent policy, wherein the parent policy is executed to produce the starting state for the new policy. This allows the proposed algorithm to stack policies sequentially and reach goals further away. Empirically, the algorithm achieves good performance on pointmass, cheetah, walker, and ant tasks.

To increase the state space coverage with unsupervised skill discovery, the authors propose UPSIDE. They tackle reaching distant states (direct) and covering neighbor states (diffuse) at different stages. Also, they discover skills by forming a tree, which enables chaining of smaller skills to form far-reaching skills. Also, instead of fixing the number of skills to learn, they maximize the number of skills with a constraint on the output of the discriminator $q_\phi(z|s_{diff})$ and show that it is a lower bound of the mutual information objective. Empirical results on Maze and MuJoCo environments and further analyses are presented.

The paper proposes an unsupervised exploration method for reinforcement learning, called UPSIDE, that combines learning of directed skills that enable covering distant states, and a diffusive part that explores locally and helps expand the explored region further. The main contributions are both the topology of the policy (division to tree-structured skills and diffusive parts), a theory for training such policies, and a practical implementation that simplifies some of the technicalities induced by the theory. The experiments illustrate well the assumed benefits and include both toy tasks (a point mass in a maze) as well as more complex tasks such as HalfCheetah and Ant from OpenAI Gym. The experiments also compare to prior methods such as DIYAN and provide ablations of the importance of the different components. 

The idea of this work is to maximize coverage while ensuring learned skills are distinguishable. The learning framework is based on maximizing mutual information (MI) between latent random variables and states.  This paper proposes a decoupled objective for local coverage and directness, on top of it, a tree structure based exploration method is proposed to incrementally compose learned skills for maximum coverage.

The authors propose a novel skill discovery method that combines standard mutual information maximization with notable changes. The first is that skill now enter a diffusion stage (random actions) before being predicted by a reverse predictor. The second is that environmental resets are exploited in order to construct a skill tree, wherein new skills are executed only after their parent skills. The final change is a pruning/growth strategy similar to VALOR, which is critical for constructing the skill tree.  The authors evaluate their method by comparing it to traditional skill discovery methods in terms of state coverage and performance on downstream tasks. 

This method learns a space of intrinsic goals to maximize coverage of the state space. This work utilizes mutual information between skills and states, where the entropy of states and negative entropy of states given options describe the diffusing and directing objectives respectively. This is done by learning skills with two separate parts, a long scale directed component and a short scale diffusing component. These skills have state distributions that differ by at least a specified factor. It then separates these skills along a hierarchical tree structure, where temporal abstraction occurs by calling lower level options, which have a limited range, controlling the shape of the tree by pruning skills with low difference, and adding new skills when all the skills satisfy the condition. 

The paper presents a framework for an unsupervised learning of robotic skills that balances directness of exploration and coverage of state space. The theory of the method builds on the notion of mutual information between states and skills, where the conditional entropy between states and skill definitions corresponds to the directed part of the learned policy, and entropy of the states to the diffusing part of the policy. The directed part is optimized to increase discriminability of the skills given the states using a discriminator network. The diffusing part performs a random walk policy with uniform distribution over actions.The paper further proposes to optimize the number of skills by requiring the minimum discriminability of skills and discarding skills that fall below the discriminability threshold. Finally, in order to be able to reach states that are farther away, the paper proposes to combine skills in a tree structure and gradually expand the tree by adding new skill nodes to the tree. The approach is shown to outperform other unsupervised skill discovery methods on such tasks as continuous maze, CartPole and Reacher in OpenAI Gym during both, unsupervised skill discovery phase and training of downstream tasks.