Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reaching
Authors: Pierre-Alexandre Kamienny
Jean Tarbouriech
sylvain lamprier
Alessandro Lazaric
Ludovic Denoyer
Venue: ICLR 2022 Poster (2022)
Keywords: unsupervised reinforcement learning
skill discovery
mutual information

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.

Published as a conference paper at ICLR 2022
DIRECT THEN DIFFUSE:
INCREMENTAL UNSUPERVISED SKILL DISCOVERY FOR STATE COVERING AND GOAL REACHING
Pierre-Alexandre Kamienny*1., Jean Tarbouriech
Sylvain Lamprier", Alessandro Lazaric Ludovic Denoyer Meta AI "Soroonne University, LIP6/ISIR
3 Inria Scool
ABSTRACT
Learning meaningful behaviors in the absence of reward is difficult problem in reinforcement learning. A desirable and challenging unsupervised objective is to learn set of diverse skills that provide 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 evvrage-diirectdness directedness trade-off in the following ways: 1) We design policies with decoupled structure of a directed skill, trained to reach specific region, followed by a diffusing part that induces 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 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 several navigation and control environments how the skills learned by UPSIDE solve sparse-reward downstream tasks better than existing baselines.
INTRODUCTION
Deep reinforcement learning (RL) algorithms have been shown effectively solve 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 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 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 variety of downstream tasks defined on the same environment. This approach is particularly effective in problems such as navigation (see e.g., Bagaria al., 2021) and roboties (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, focus the unsupervised objective of discovering 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 can formalize the dual objective of learning policies that both cover and navigate the environment efficiently. Indeed, maximizing MI has been shown 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 al., 2018: Sharma 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 dircetedness (see Sect. 4 for a review of related work).
of skills that can be
"quull contribution
Now at Ubisoft La Forge
(pakamt enny, It starborriest (azarie]rrb.com .ay nn. ermprerriiee r.upoo..rr Iudevie denggga 1.com

---

Published as a conference paper at ICLR 2022
difuusing part
directed skill
Structure UPSIDE
policy
Figure 1: Overview of UPSIDE. The black dot corresponds to the initial state. (A) A of random policies initialized, cach policy being composed of a directed part called skill (illustrated as a black arrow) and a dif- fusing part (red arrows) which induces a local coverage (colored circles). (B) The skills are then updated to maximize the discriminability of the states reached by their corresponding diffusing part (Sect. 3.1). (C) The least discriminable policies are iteratively removed while the remaining policies re-optimized. This is ecuted until the discriminahility policies are consolidated. (D) One of these policies is used as basis to add new policies, which are then opti- mized following the same procedure. For the "red" and "purple" policy, UP s IDE is not able to find sub col-policies of sufficient quality and thus they are expanded any further. (E) At the end of the process, UP SIDIDE has created a tree of policies covering the state space, with skills as edges and diffusing parts as nodes (Sect. 3.3).
each policy satisfies a given constraint (Sect. 3.2). this example two
In this paper, we propose UPSIDE (UnsuPervised Skills that dIrect then DiffusE) to learn 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. I (A)). We consider policies composed of two parts: 1) directed part, referred to as the skill, that trained 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. (B) & (C)). We then introduce a constrained opti- mization 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 minimum level of discriminability). We prove that this problem can be cast as lower bound to the original MI objective, thus preserving its coverage-directednes adding or removing policies to given initial set, without requiring any prior knowledge on sensible number of policies.
trade-off. UPSIDE solves it by adaptively
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 struc- ture. This overcomes the need defining a suitable policy length advance. Thus UP SIDE 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 SPSIDE and the impact of its components hard- to-explore continuous navigation and control environments, where UP SIDE improves over existing baselines both in terms of exploration and learning performance.
2 SETTING
We consider the URL setting where the agent interacts with a Markov decision process (MDP) with state space S, action space A, dynamics p(s'ls, silss,a). and no reward. The agent starts each episode from a designated initial state Sy E S.! Upon termination of the chosen policy, the agent is then reset to su- This setting is particularly challenging from 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 al., 2016). Denote by Z some (latent) variables on which the policies length T are conditioned (we assume that Z categorical for simplicity and because it is the most common case practice). There are three
More generally, so could be drawn from any distribution supported over compact region.
2

---

Published as a conference paper at ICLR 2022
optimization variables: (i) the cardinality of Z denoted by Nz, i.e., the number of policies (we write 2 = (1...., N2) = [Nz]) (ii) the parameters T(2) of the policy indexed by & E Z, and (iii) the policy sampling distribution (i.e., p(2) is the probability of sampling policy at the beginning of the episode). Denote policy z's action distribution in state by (-|2,, 8) and the entropy function by H. Let the variable ST be the random (final) state induced by sampling policy z from p and executing π²)) from so for an episode. Denote by (*T=)(ST) the distribution over (final) states induced by executing policy 2, by p(2)sT) the probability of 2 being the policy to induce (final) state 8T, and let ((TT) Ezez (()))(())(TT) Maximizing the MI between Z and Sr can be written maXN P. I(S:: 2), where
I(Sr: Z) H(Sr) HZ()IZ)
>E(EE Σ p(st) {(ss))ooFP(s) logp(st) Σ ((2) Sy [Ig))(ss($T)]
8y
2E%
H(Z) H(((ST) Σ p(z) log .EZ
Σ
((2) Dogp(=)sr)) zEZ
where in the expectations sr|2 ~ (8()) In the first formulation, the entropy term over states captures the requirement that policies thoroughly cover the state space, while the second term mea- sures the entropy over the states reached by each policy and thus promotes policies that have a directed behavior. Learning the optimal N2, P. and ıT to maximize Equation is a challenging prob- lem 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 pl p(2(sr) is usually replaced with a parametric model 4a (2(ST) called the discriminator that trained via a neg- ative log likelihood loss simultaneously with all other variables. Then one maximize the lower bound (Barber & Agakov, 2004): I(S:: 2) 2 [==o(=))r=x(() [log qs (2(sT) - log p(z)]. where we denote by ~ (2)) trajectories sampled from the policy indexed by z. As a result, each policy x(2) can be trained with RL to maximize the intrinsic reward (s())) == log q (2(ST) log p(z).
3 THE UPSIDE ALGORITHM
In this section we detail the three main components of UPSIDE, which is summarized in Sect. 3.4.
3.1 DECOUPLED POLICY STRUCTURE OF DIRECT-THEN-DIESS -IFFUSE
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 major impact 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 (r(a) over final states with high entropy, thus increasing H(Sz [Z) and losing in directedness. In UP UPSI,E, we define policies with a decoupled structure (see Fig. 1 (A)) composed of a) a directed part (of length T) that we refer as skill, with low stochasticity and trained to reach a specific region of the environment and b) diffusing part (of length H) with high stochasticity promote local coverage of the states around the region reached by the skill.
Coherently with this structure, the state variable in the con- ditional entropy in Equation 1 becomes any state reached during the diffusing part (denote by Sai the random vari- able) and not just the skill's terminal state. Following Sect. 2 we define an intrinsic reward r=()) log go (2 log p(2) and the skill of policy z maximizes the cunulative reward over the states traversed by the diffusing part. For- mally, we can conveniently define the objective function:
UFSIDE directed skill
CPSIDE diflisiig part
vic policy
DIAYN policy
state variable
San
Sam
Sr
s
J
(T
T + H}
(T.
T
H)
(T)
(l.... T)
(a.8)
(1,0)
(0.
(1,0) (1.1)
Table 1: Instantiation of Equation for each part of an UPSIDE policy, and for VIC (Gregor et al.. 2016) and DIAYN (Eysenbach al., 2019) policies.
Σe a a.rr( (8t) + 3 H([T(- (((T(-12, st)]. (2)
max (T))(= xx)
TEJ
where -T T + H} and a = 1, = (resp. a = 0, B = 1) when optimizing for the skill (resp. diffusing part). In words, the skill is incentivized to bring the diffusing part to discriminable region of the state space, while the diffusing part is optimized by a simple random walk policy (i.c., stochastic policy with uniform distribution over actions) to promote local coverage around 87.
3

---

Published as a conference paper at ICLR 2022
Table illustrates how UPSIDE's policies compare to other methods. Unlike VIC and similar to DIAYN, the diffuusing 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 N₂ < [S] policies.? 2 Furthermore, the diffusing part can be seen as defining cluster of states that represents the goal region of the directed skill. This is in contrast with D DIAYN policies whose stochasticity may be spread over the whole trajectory. This allows us "ground" the latent variable representations of the policies Z to specific regions of the environment (i.e., the clusters). As result, maximizing the MI (S Z) can be seen as learning a set of "cluster-conditioned" policies.
3.2 A CONSTRAINED OPTIMIZATION PROBLEM
In this section, we focus on how to optimize the number of policies Nz and the policy sampling distribution p(z). The standard practice for Equation I is to preset fixed number of policies Nz and to fix the distribution p to be uniform (see e.g., Eysenbach al., 2019; Baumli et al.. 2021; Strouse et al., 2021). However, using a uniform P over a fixed number of policies may be highly suboptimal, in particular when N2 is not carefully tuned. In App. A.2 we give a simple example and theoretical argument on how the MI can be ensured to increase by removing skills with low discriminability when p is uniform. Motivated by this observation, in UP IDE we focus on maximizing the number of policies that are sufficiently discriminable. We fix the sampling distribution p to be uniform over N policies and define the following constrained optimization problem
max N N21
(NN 2 log y): where g(N)= == max min Esaz [log go (=(((()ar)) n. ZE(N]
(Pa))
where (=)2sam)) denotes the probability of being the policy traversing Sair during its diffusing part according to the discriminator and 17 (0, defines a minimum discriminability threshold. By optimizing for (P,). UPSTDE 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 sufficient level of inter-cluster distance (i.e., discriminability) (see Fig. 1). The following lemma (proof in App. A.1) formally links the constrained problem (P,) back to the original MI objective.
Lemma 1.
There exists a value n/ E (0, 1) such that solving (Pnt) is equivalent to maximizing a lower bound on the mutual information objective max N2. I(San; 2).
Since (Prt) 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. provides a rigorous justification for using a uniform sampling distribution restricted to the 1) g-diseriminable policies, which is in striking contrast with most of MI-based literature, where a uniform sampling distribution p is defined over the predefined number of policies.
In addition, our alternative objective (Pr,) has the benefit of providing a simple greedy strategy to optimize the number of policies N. Indeed, the following lemma (proof in App. A. ensures that starting with N (where g = 0) and increasing it until the constraint g(N) Z log v is violated is guaranteed to terminate with the optimal number of policies.
Lemma 2. The function y is non-increasing in N.
3.3 COMPOSING SKILLS IN GROWING TREE STRUCTURE
Both the original MI objective and our constrained formulation (Pr,) depend on the initial state so 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 around so. 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.
radius of at most T' + H steps
Equation is maximized by setting N2- = SS| (i.e.. maxy I(X, Y) I(X,X) = H((X), )). where each represents goal-conditioned policy reaching different state, which implies having many policies as states, thus making the learning particularly challenging.
4

---

Published as a conference paper at ICLR 2022
Instead, we propose to "extend" the length of the policies through composition. We rely the key insight that the constraint in (Pa) guarantees that the directed skill of each n-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 growing tree, where the root node is diffusing part around so, the edges represent the skills, and the nodes represent the diffitsing 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 curriculum on the episode lengths which grow as the sequence (iT + 121, thus avoiding the need of prior knowledge on an adequate horizon of the downstream tasks. 3 Here this knowledge is replaced by T' and H which are more environment-agnosie 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).
3.4 IMPLEMENTATION
Algorithm 1: UPSTDE
We are now ready to introduce the UPSIDE al- gorithm, which provides specific implementation of the components described before (see Fig. 1 for an illustration, Alg. for short pseudo-code and Alg. 2 in App. B for the detailed version). We first make approximations so that the constraint in (P,) is casier to estimate. We remove the logarithm from the constraint have an estimation range of [0. 1] and thus lower variance. 4 We also replace the expectation over Sair with an empirical estimate
Parameters:
Discriminability threshold
E (0, 1). branching factor N _ Initialize: Tree T initialized as root node 0. policies candidates Q = =0) while 2 J 0 do // tree expansion
1
Dequeue policy 2 E Q and create
N = N policies C(z).
POLICYLEARNING(T.C C(2)). if min (=')) > 7) then
2
// Node addition
while min,'ec(=) 05 (x') > 1)
(=) = B.. ExeB, (=(ss)), where B_ denotes small replay buffer, which we call state buffer, that contains states collected during a few rollouts by the diffusing part of TT. In our experiments, we
and < N ymx do
Increment N = N + 1 and add one policy to C(z).
POLICYLEARNING(T..C C()))
take B- = =B. = 10H. Integrating this in (P₂)
7
else/ // Node removal while min,'ec(s) 05 (2') < " and > 1
leads to
max N N21
s.t. max min 98 (x) 2 77.
(3)
Reduce N = N - 1 and remove least discriminable policy from C(z).
a, zE(N)
where 1) is an hyper-paramert optimization problem in N can be solved using the 10 incremental policy addition or removal in Alg. I (lines 5 & 9), independently from the number of initial policies N.
From Lem. 2, this
POI.ICYLEARNINGC" C())).
Add n-discriminable policies C(=) to Q, and T as nodes rooted 2.
We then integrate the optimization of Equation 3 into an adaptive tree expansion strategy that in- crementally composes skills (Sect. 3.3). The tree is initialized with a root node corresponding to a policy only composed of the diffusing part around 8p- Then UPSIDE iteratively proceeds through the following phases: (Expansion) While policies/nodes can be expanded according to different ordering rules (c.g., a FIFO strategy). we rank them in descending order by their discriminability (i.e., Tg (2)), 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 Nstart 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) (state buffers of consolidated policies in T are kept in memory), ii) update the discriminator and compute the discriminability 2 (=') of new policies z' E C(=), iii)
"See e.g.. the discussion in Mutti al. (2021) the "importance of properly choosing the training horizon accordance with the downstream-Bn task horizon the policy will eventually face."
'While Gregor et al. (2016); Eysenbach et al. (2019) employ rewards in the log domain, we find that map- ping rewards into [0, 1] works better in practice, as observed in Warde-Farley et al. (2019); Baumli et al. (2021). "Ideally, we would set 1) = n' from Lem. 1, however n' is non con-trivial to compute. A strategy may be to solve (P,r) for different values of n and select the one that maximizes the MI lower bound F. [log to (san)) - lolgg((()) p(=)]. In our experiments we rather use the same predefined parameter of n = 0.8 which avoids computational overhead and performs well across all environments.
5

---

Published as a conference paper at ICLR 2022
update the skills to optimize the reward (Sect. 3.1) computed using the discriminator (see step (B) in Fig. 1). (Node adaptation) Once the policies are trained, UPSIDE proceeds with optimizing N in greedy fashion. If all the policies in C(2) have an (estimated) discriminability larger than n (lines 3-5), a new policy is tentatively added to C(=), the policy counter N is incremented, the policy learning step is restarted, and the algorithm keeps adding policies until the constraint 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(2), 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 ((2) 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 uduptation step terminates with N = for all nodes) or maximum number of environment iterations is met.
4 RELATED WORK
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 model- free (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 I and the policy parame- ters x (2) and sampling distribution p are simultaneously learned (with a fixed number of skills Nz). DIAYN (Eysenbach et al., 2019) fixes uniform P and weights skills with an action-entropy co- efficient (i.c., 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 and optimizing a forward form of MI I(s'; 2|s) between the next state s' and current skill (with con- tinuous 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. 12;17); 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 in- creasing Nz is studied in Achiam et al. (2018); Aubret et al. (2020). We consider a similar dis- criminability criterion in the constraint in (Pr,) 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 hicrarchical 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 Su after each execution, yet articulate the composition differently, by exploiting the direct-then-diffusee structure to ground skills to the state space instead of being abstract. Har- tikainen et al. (2020) perform unsupervised skill discovery by fitting distance function; while their approach also includes a directed part and a diffusive part for exploration, it learns only a single directed policy and does not aim to cover the entire state space. Approaches such as DISCERN (Warde-Fatt Farley et al., 2019) and Skew-Fit (Pong et al.. 2020) learn a goal-conditioned policy in an unsupervised way with an MI objective. As explained by Campos et al. (2020), this can be in- terpreted as 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 policies. Finally, an alternative approach to skill discovery builds on
learning celuster-conditiones "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 discrete graph representation which learns and composes spectral skills.
6

---

Published as a conference paper at ICLR 2022
UP IPSIDE
Bottleneck Maze
U-Maze
RANDOM
29.17
(40.37)
23.33
(#0.57)
DIAYN-10
17.67
(1.0.77)
14.67
(1:0.42)
DIAYN-20
23.00
(41109)
16.67
(#1.10)
DIAYN-50
30.00
(40.72)
25.33
(#1.03)
DIAYN 50
DIAYN- -curr
18.00
(+0.82)
15.67
(#0.87)
DIAYN-hier
38.33
(4:0.68)
49.67
(#:0.7))
EDL-10
27.00
(11.41)
32.00
(11.11)
EDL-20
31.00
(#v.47)
46.00
(2)..2)
EDL.500
33.33
(#:042)
52.33
2.3
SMM-10
19.00
(#00.4)
14.00
(40.54)
SMM-20
23.67
(#1.299
14.00
(#0.27)
SMM-50
28.00
(1.0.82)
25.00
(11.52)
Flat UPSIDE 10
40.67
(+1150)
43.33
(#2.57)
ED -0
Flat UPSIDE EPSIDE-200
47.67
(1:0.31)
55.67
(d11.03)
Flat UP UPSIDS SPSIDE-23 50
51.33
(+: (..4)
57.33
(10.31)
UPSIDE
85.67
(211933
71.33
(1:0442)
Table 2: Coverage Bottleneck Maze and U-Maze: UPSIDE ers significantly more regions of the discretized state space than the other methods. The values represent the number of buckets that are reached, where the 50 x 50 space is discretized into 10 buckets per axis. To compare the global coverage of methods (and to be fair the amount of injected noise that may vary across methods), we roll-out for each model associated deterministic policies.
Figure 2: Policies Iearned the Bot- tleneck Maze (see Fig. 14 in App. other methods): contrary the baselines, UPSIDE successfully escapes the bottleneck region.
EXPERIMENTS
Our experiments investigate the following questions: i) Can UPSIDE incrementally cover an un- known 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 mazes and on continuous control prob- lems (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 ob- jective is to find and reliably reach an unknown goal location through fine-tuning of the policy, We perform our experiments based on the SaLinA framework (Denoyer et al., 2021))
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- is curriculum variant where the number of skills is automatically tuned following the same procedure as UPSIDE similar to Achiam et al. (2018) to ensure sufficient discriminabil- ity, and b) DIAYN- -eii-N-heerrrrree hier is hierarchical extension of D DIAYN where the skills are composed in tree as in UP S SIDE 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 en- countered states. In addition, we consider EDL (Campos et al., 2020) with the assumption of the available state distribution oracle (since replacing by SMM does not lead satisfying results in presence of bottleneck states as shown in Campos et al., 2020). Finally, we consider the RANDOM
'The agent observes its current position and its actions (in [-1, +1]) control its shift in 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 harder version of the one in Campos al. (2020, Fig. whose size only 10 10.

---

Published as a conference paper at ICLR 2022
100
20
400
20-
15
15-
200
10-
100
6-
15
10
infermctions
10
(a) Ant
(b) Half-Cheetah
Walker2d
Figure 3: Coverage on control environments: UPSIDE covers the state space signif-
UPSIDE
icantly more than DIAYN and RANDOM. The curve represents the number of buckets reached the policies extracted from the unsupervised phase of UPSIDE and DIAYN function of the number environment interactions. DIAYN UPSIDE the same amount of injected noise. Each axis discretized into 50 buckets.
DIAYN-6
DIAYN-10
DIAYN-20
RANDOM
TDS
DIAYN
-4
-4
0.1
-8
-8 -4 0
8
4 0
8
Eare Interactions
(a) JPSIDE policies on Ant
(b) DIAYN policies on Ant
(c) Fine-tuning on
Figure 4: (a) & (b) Unsupervised phase on Ant: visualization of the policies learned by UPS IDE and
DIAYN-20. We display only the final skill and the diffusing part of the IDE policies. (c) Downstream tasks on Ant: we plot the average success rate over unknown goals (with sparse reward) that are sampled uniformly in the -88,8 8]2 square (using stochastic roll-outs) during the fine-tuning phase. UP SIDIIE achieves higher success rate than DIAYN-20 C and TD3.
policy, which samples actions uniformly in the action space. We use TD3 as the policy optimizer (Fujimoto al., 2018) though also tried SAC (Haarnoja et al., 2018) which showed equivalent results than TD33 with harder tuning. Similar to e.g., Bysenbach et al. (2019); Bagaria & Konidaris (2020), we restrict the observation space of the discriminator the cartesian coordinates (xx, y) for Ant and æ for Half-Cheetah and Walker2d. All algorithms were ran on T'ax = 1e7 unsupervised en- vironment interactions episodes of size Hmax 200 (resp. 250) for mazes (resp. for control). For baselines, models are selected according to the cumulated intrinsic reward (as done in e.g.. Strouse al., 2021), while UPS IDE, DIAYN-hier and DIAYN-curt are selected according to the high- est number of y-discriminable policies. On the downstream tasks, we consider ICM (Pathak et al., 2017) as an additional baseline. See App. for the full experimental details.
Coverage. We analyze the coverage achieved by the various methods following unsupervised phase of at most Tmax = 1e7 environment interactions. For UPSIDE, we report coverage for the skill and difffusing part lengths T H 10 in the continuous mazes (see App. D.4 for ablation on the values of T, H) and T H = 50 in control environments. Fig. 2 shows that UP S IDD man- ages to cover the near-entirety of the state space of the bottleneck maze (including the top-left room) by creating 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. and 4, UPSTDE clearly outperforms DIAYN and RANDOM in state-coverage 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 few steps then hover, it fails to explore the environment. In Half-Cheerd and Walker2d, while DIAYN policies learn to fall on the agent's back, UPSIDE learns to move forward/backwwrrd on its back through skill composition.
Unknown goal-reaching tasks. We investigate how the tree of policies learned by UPSIDE in the unsupervised phase can used to tackle goal-reaching downstream tasks. All unsuper- vised methods follow the same protocol: given an unknown" goal g. i) we sample rollouts over
Notice that if the goal was known, the learned discriminator could be directly used to identify the most promising skill fine-tune.
8

---

Published as a conference paper at ICLR 2022
0.33
0.32
0.33
0.15
0.33
0.33
0.33
0.54
0.0
0.0
0.P
0.0
0.0
0.0
0.9
0.0
0.0
0.0
0.
0.0
0.25
0.28
0.41
0.64
0.0
0.0
0
0.0
0.85
0.49
0.67
0.89
0.85
0.71
0.45
0.85
0.79
0.51
0.22
0.96
0.89
0.76
0.61
0.95
0.85
0.76
0.0
0.96
0.08
0.75
0.32
0.96
0.85
0.75
0.64
UPSTDE: before and after fine-tuning
(b) DIAAN
F.D..
(d) TCM
Figure Downstream task performance on Bottleneck Maze: UPSIDE achieves higher discounted cumulative reward on various unknown goals (See Fig. 15 App. for SVV and TD3 performance). From each the 16 discretized regions, we randomly sample 3 unknown goals. For every method and goal seed, we roll-out each policy (learned in the unsupervised phase) during 10 episodes and select the one with largest cumulative reward fine-tune (with sparse reward r(s) = I[[|s g|la v 1J). Formally, for given goal y the reported
value 7 "I[T S Hnas] with r == [t 2 1 || glla I 1]. 7 0.99 and horizon Hmas 200.
the different learned policies, ii) then we select the best policy based on the maximum discounted cumulative reward collected, and iii) we fine-tune this policy (i.e., its sequence of directed skills and its final diffusing part) to maximize the sparse reward r(s) = =I[[|s [[[ls-gli glle I I]. Fig. 5 reports the discounted cumulative reward on various goals af- ter the fine-tuning phase. We see that UP S IDE accumulates more reward than the other methods, in particular in regions far from Su, where performing fine-tuning over the entire skill path is especially challenging. In Fig. deviate from the original tree structure to improve the goal-reaching behavior of its candidate policy. We also perform fine-tuning on the Ant domain under the same setting. In Fig. 4c, we show that UPS SIDE clearly outperforms D DTAYN-20 and TD3 when we evaluate the aver- age 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 80.
Unknown goal with sperse reward
Post-finetuning
Pre-finetuning
see that UPSIDE'S fine-tuning can slightly
Figure 6; For an unknown goal location, UPSIDE identifies promising policy in its tree and fine-tunes it.
Ablative study of the UPSIDE components. The main components of UPSIDE that differ from ex- isting 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 compare UPSIDE to
all components are simultaneously required for good performance. First, flat UPSIDE, i.e., UPSIDE with the tree depth of (7 = 150, H = 50). Table 2 reveals that the tree structuring is key improve exploration and escape bottlenecks; it makes the agent learn 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 composi- tion work. as well as UPSTDE by clear margin. In fact, UPSIDE's direct-then-diffus 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-hie optimization problem (P,, combined with the diffusing part is crucial to prevent consolidating too many policies, thus allowing sample efficient growth of the tree structure.
shown in Table 1, DTAYN-hi er r hierarchical version of DTAYN does not perform
decoupling enables
the bottleneck maze, the constrained
CONCLUSION AND LIMITATIONS
We introduced UP SPSIDE, a novel algorithm for unsupervised skill discovery designed to trade off between coverage and directedness and develop a tree of skills that can used to perform ef- ficient 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, would be interesting to pair IPSIDE with effective representation learning techniques to tackle problems with high-dimensions 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.

---

Published as a conference paper at ICLR 2022
Acknowledgements
We thank both Evrard Garcelon and Jonas Gehring for helpful discussion.
REFERENCES
Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms. arXiv preprint arXiv: 1807. 10299, 2018.
Arthur Aubret, Laëtitia Matignon, and Salima Hassas. Elsim: End-to-end learning of reusable skills through intrinsic motivation. In European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2020.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In International Conference Learning Representations, 2020.
Akhil Bagaria, Jason K Senthil, and George Konidaris. Skill discovery for exploration and planning using deep skill graphs. In International Conference on Machine Learning, pp. 521-531. PMLR, 2021.
David Barber and Felix Agakov. The im algorithm: variational approach to information maxi- mization. Advances in neural information processing systems, 16(320):201, 2004.
Kate Baumli, David Farde-Farley, Steven Hansen, and Volodymyr Mnih. Relative variational in- trinsic control. In Proceedings the AAAI Conference Artificial Intelligence, volume 35, pp- 6732-6740, 2021.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Víctor Campos, Alexander Trou, Caiming Xiong, Richard Socher, Xavier Giro-i Nieto, and Jordi Torres. Explore, discover and learn: Unsupervised discovery of state-covering skills. In Interna- tional Conference on Machine Learning, 2020.
Ludovic Denoyer, Alfredo de la Fuente, Song Duong, Jean-Baptiste Gaya, Pierre-Alexandre Kamienny, and Daniel H Thompson. Salina: Sequential learning of agents. arXiv preprint arXiv:21 2021.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In International Conference on Learning Representa- tions, 2019.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical rein- forcement learning. arXiv preprint arXiv: /7Xiv:/704.03012 2017.
Scott
Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.07500 2016.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1861-1870. PMLR, 2018.
Steven Hansen, Will Dabney, Andre Barreto, David Warde-Farley, Tom Van de Wiele, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. Interna- tional Conference on Learning Representations, 2019.
Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, and Sergey Levine. Dynamical distance learning for sumi-super and unsupervised skill discovery. In International Conference on Learning Representations, 2020.
10

---

Published as a conference paper at ICLR 2022
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: variational information maximizing exploration. Proceedings of the 30th International Con- ference Neural Information Processing Systems, pp. 1117-1125, 2016.
Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris. Discovering options for exploration by minimizing cover time. In International Conference Machine Learning, pp. 3130-3139. PMLR, 2019.
Yuu Jinnai, Jee Won Park, Marlos C Machado, and George Konidaris. Exploration in reinforcement learning with deep covering options. In International Conference Learning Representations, 2020.
Lisa Lee. Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdi- nov. Efficient exploration via state marginal matching. arXiv preprint N0KEv:9906.0522. 2019.
Hao Liu and Pieter Abbeel. Aps: Active pretraining with successor features. In International Conference on Machine Learning, pp. 6736 6747. PMLR, 2021.
Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Reset-free lifelong learning with skill- space planning. arXiv preprint arXiv:2012.03558, 2020.
Marlos C Machado, Mare Bellemare, and Michael Bowling. laplacian framework for op- tion discovery in reinforcement learning. In International Conference on Machine Learning, pp- 2295-2304. PMLR, 2017.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Representations, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 (777540) 533, 2015.
Nirbhay Modhe, Prithvijit Chatoopadhyay, Mohit Sharma. Abhishek Das, Devi Parikh, Dhruv Batra, and Ramakrishna Vedantam. Ir-vic: Unsupervised discovery of sub-goals for transfer in rl. In Proceedings the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI- 20, 2020.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. In Advances in neural information processing systems, pp. 2125-2133, 2015.
Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task-agnostic exploration via policy gra- dient of a non-parametric state entropy estimate. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp.
2021.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16 16-17,20 2017.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering self-supervised reinforcement learning. In International Conference on Ma- chine Learning, 2020.
Ramanan Sekar, Olch Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervieed world models. In International Conference Machine Learning, pp. 8592. PMLR, 2020.
Archit Sharma, Shixiang Gu, Sergey Levine. Vikash Kumar, and Karol Hausman. Dynamics-awe aware unsupervised discovery of skills. International Conference on Learning Representations, 2020.
DJ Strouse, Kate Baumli, David Warde-Farley, Vlad Mnih, and Steven Hansen. Learning more skills through optimistic exploration. arXiv preprint arXiv:2107. 14226, 2021.
11

---

Published as a conference paper at ICLR 2022
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. In In- ternational Conference on Learning Representattinss 2019.
Kevin Xie, Homanga Bharadhwaj, Danijar Hafner, Animesh Garg, and Florian Shkurti. Skill transfer via partially amortized hierarchical planning. In International Conference Learning Represen- tations, 2021.
Kelvin Xu, Siddharth Verma, Chelsea Finn, and Sergey Levine. Continual learning of control prim- itives: Skill discovery via reset-games. Advances in Neural Information Processing Systems, 33, 2020.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Reinforcement learning with proto- typical representations. In Proceedings of the 38th International Conference on Machine Learn- ing. pp. 11920-11991 11931. PMLR, 2021.
Jesse Zhang, Haonan Yu, and Wei Xu. Hierarchical reinforcement learning by discovering intrinsic options. International Conference on Learning Representations, 2021.
12

---

Published as a conference paper at ICLR 2022
Appendix
Theoretical Details on Section 3
13
B UPSIDE Algorithm
16
C Experimental Details
18
Additional Experiments
A THEORETICAL DETAILS ON SECTION 3
A.1 PROOFS OF LEMMAS 1 AND
Restatement of Lemma 1.
There exists value 17 E 10 such that solving (Pyt) is equivalent to maximizing a lower bound on the mutual information objective max n, I(Sair; 7).
Proof. We assume that the number of available skills is upper bounded, i.e., N2 N Nuax 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 (air)
= -E
((2)BBurr (log p(z[san)
#EZ
> Σ ((z) [log go (=][sair))
#EZ
We now use that any weighted average is lower bounded by its minimum component, which yields
- San) 2 min
Exun [log 2o (=(saur)
=E2
Thus the following objective is lower bound on the original objective of maximizing I(Sai: 2)
max F.
[((Z)
min Esar [log (a(2)sam))) }
(4)
=E[N]
Interestingly, the second term in Equation 4 no longer depends on the skill distribution p. while the first entropy term H(Z) is maximized by setting p the uniform distribution over N skills (i.e., maxp H(Z) log( N)). This enables to simplify the optimization which now only depends on N.
Thus Equation 4 equivalent to
max { N==N
log((V) max min Esgn [log g0(2) [=](sarrr]
(5)
a ZE[N]
We define the functions
f(N) log(N), g(N) = max min Esya [log go (z((sai)))) 5 =E[N]
Let NO E arg max f(N) g(N) and n² exp (NN)) E (0, 1). We now show that any solution of (P,t) 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*) 2 logn' = g(V.). Second, since N meets the constraint and N is the maximal number of skills that satisfies the constraint of (P,tt, by optimality we have that N 2 Nt and therefore S(N*) 2 s(Nt) since f is non-decreasing. We thus have
(N(N*) 2 g(Nt) ((N+) 2 S(NT)
= f(N*) + +(N*) 2 f(Nt) + g(Nt).
Putting everything together, optimal solution for (P,t) is optimal solution for Equation 5, which is equivalent to Equation 4, which is a lower bound of the MI objective, thus concluding the proof.
13

---

Published as a conference paper at ICLR 2022
Restatement of Lemma 2. The function g is non-increasing in N.
Proof. We have that g(N) == max=,q min (s [og((()))) where throughout the proof we write s instead of Sai for ease of notation. Here the optimization variables are т E (IT) (i.e., set of N policies) and q S ((V), i.e. a classifier of states N possible classes, where A(N) denotes the N-simplex. For E [N]. let
hN 9, q,2) == B (=)
fN( 9) == min hy (TT, q.
SE[N]
Let (x',4) E arg mag. ( g). We define मे := (x((1), ( (NN) such that ((ils) == g (ils) for any IN - and ((N]s) = (((Vss) + q + 1/s).
(N)) E (IT) and q S -
Intuitively, we are "discarding" policy N + 1 and "merging" class N + with class N.
Then it holds that
gN + 1) IN+I(T'
min hN+1 (x',2'2)) min hN+1 (4', ,') =E[N+1]
=E[M]
Now, by construction of म. have for any i [N - 1] that h I , i) (, 7). As for class N, since 7( (NN = x (N), by definition of (-N and from monotonicity of the log function, holds that h (T', q' N) (N) (N [s] satisfies
IN+1 o N) s E Re [log(
hN (n,
Hence, we get that
min (n', .'= v =E[N]
min h hn q. fx - g(N).
=E[N]
Putting everything together gives gNN + 1) S ((V), which yields the desired result.
A.2 SIMPLE ILLUSTRATION OF THE ISSUE WITH UNIFORM-P MI MAXIMIZATION
This section complements Sect. 3.2: we show sim- ple scenario where 1) considering both a uniform p prior and fixed skill number Nz provably leads to suboptimal MI maximization, and where 2) the
skill
state
state
UPSIDE strategy of considering a uniform p re- stricted to the n-discriminable skills can provably in- crease the MI for small enough 17.
skill
M
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 sume that the execution of each skill deterministi- cally 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 E 10 the probability that skill n. is assigned state m. It must hold that Vn E [N], Em, Po.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 p is uniform, i.e., p(n) = 1/N. It holds that
skill
state
We as-
The agent must assign (possibly stochastically) N skills to M states: under the prior of uniform skill distribution, can the MI with be increased by varying the number of skills N?
Figure
I(N, Σ
log Σ N Pn.m log En Pmnm
P
log N +
1 Σ pm log En Pn.m
Pn.m
N
n.m
L' max Pm m I(N, M) and {ptmm E arg eaggma//poo pm.m. I(N, We also define the
discriminability of skill state as
Pn.m
mn En Po.m
as well as the minimum discriminability of the optimal assignment as
7 min max Tr.m
n
m
14

---

Published as a conference paper at ICLR 2022
Lemma 3. There exist values of N and M such that the uniform-p MI be improved by removing skill (i.e., by decreasing N).
Proof. The following example shows that with M 2 states, it beneficial for the uniform-p MI maximization to go from N = 3 to N = 2 skills. Indeed, we can numerically compute the optimal solutions and we obtain for N and M 2 that
0
0
0.5
I' 3, M 2) 0.918,
Pa,m
0
Irim
0
0.5
7 0.5,
0/
1
whereas for N and M
IN = M 2) = Ph,m (1 1),
( 1)=
1= 1.
= As result, (N = 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 skill per state whereas for N= = 3 the skills must necessarily overlap. Note that this contrasts with the original MI (that also optimizes p) where decreasing N cannot improve the optimal MI.
I'
The previous simple example hints to the fact that the value of the minimum discriminability of the optimal assignment 17 may be a good indicator to determine whether remove skill. The following more general lemma indeed shows that a sufficient condition for the uniform-p MI to be increased by removing skill is that v is small enough.
Lemma 4. Assume without loss of generality that the skill indexed by N has the minimum discrim- inability q) ie.. N E arg min, maxm In Define
N --1 log(N + logn.
1
A(N,n) == log
N
N
If n), S which holds for small enough 17 then removing skill N results in larger uniform-p optimal MI, ie., I' (N,M) I (N - M).
Proof. It holds that
I' (N, log N +
1
Σ
Pr.m log Iu +
Σ
Pr.m log 1)
N
nEIN mc[M]
mc(M]]
N
= llog N
log(NV N - 1)
N
log(N 11) + N
Σ
Σ
Pi.m log Iim
+
log !
N
N
REIN 1 mE(Ad]
A(N + N 1 I' I'N 1,
As result, if A(N, n) < then I' (N, <I -N
15

---

Published as a conference paper at ICLR 2022
B UPSIDE ALGORITHM
B.1 VISUAL ILLUSTRATIONS UPSIDE'S DESIGN MENTIONED SECTION 3
diffusing part the polac
2=1
2=2
directed polcy
z=3
Z=4
a.k.a. skill
2=6
2=5
Figure 8: UPSIDE policy: a directed skill fol- lowed by diffusing part.
Decoupled structure of
zm7
2=8
Figure 9: the above UFSIDE tree example, executing policy 2 means sequentially composing the skills policies 2 {2, 2, 7) and then deploying the diffusing part of policy = 7.
B.2 HIGH-LEVEL APPROACH OF UPS IDE
Learned
Fixed
Filled
NODE/POLICY a ~ Ryla 25,2
Sample node/ policy per episade tree
from discriminator train noda/pollcy
"Tree incrementally grown by tentatively adding new policies/nodes
already consolidated policies. sampling distribution p uniform the new policies ((2).
ENVIRONMENT
DISCRIMINATOR l
t' Uni(((())
Sus pl (,
Feed (policy, state) samples train discriminator
Compute discriminability for each new policy and consolidate ddz)) 2 n. otherwise discriminable policy
POLICY BUFFER f gdt (.), s,1)
Figure 10: High-level approach of UPSIDE.
B.3 DETAILS OF ALGORITHM 1
We give in Alg. 2 a more detailed version of Alg. I and we list some additional explanations below.
When optimizing the discriminator, rather than sampling (state, policy) pairs with equal probabil- ity for all nodes from the tree T, we put more weight (e.g. 3x) 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 BRL 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, order add stationarity the reward signal. Instead of using number of iterations K to stop the training loop of the POlICYLEARNING func- tion (line 16), we use a maximum number of environment interactions Kaeps for node expansion. Note that this is the same for DTA OTAYN-hier and DIAYN-curr.
16

---

Compute discriminahility d(z') ) for all z' E Zu Published as a conference paper at ICLR 2022
Algorithm 2: Detailed UPSIDE
Parameters:
Discriminability threshold 1) E (0, 1), branching factor Nskutt N
Initialize: Tree T initialized as a root node index by 0, policy candidates Q = (0), state buffers
By = []
while Q + 0
expansion
Dequeue a policy 2 Q and create = N nodes C(2) rooted at & and add new key to Bz Instantiate new replay buffer BRI.
POLICYLEARNING(BN)) Bz. T.C(=))
mins/ d(=') > 17 then // Node addition while min./eco d(=') > and N < Nmm do
Inerement N N + and add one policy to C(2)
POLICYLEARNING(BAL. Bz, T, (=))
else // Node removal
while mins/ec(=) d(z') and N > 1 do Reduce N N and remove least discriminable policy from C(2)
11
POLICYLEARNING((BL. Bz. T. C()))
Enqueue in the r-discriminable nodes C(2)
POLICYLEARNING buffer BRL, State buffers 82, Tree T, policies to update Zu) Optimization paramefers: patience K, pollcc--o-ooooo tolicy-to-iisermminato update ratio Kaisce discriminator update epochs. K policy update epochs
15 Initialize: Discriminator de with [T] classes
16 for K iterations do // Training Loop
For all z' E Zu. clear [= then collect and add states from the diffusing part of <T=') to Train the discriminator for Kasa steps with datasct User B2 [2
18
19
Compute discriminability d(=') = q3 (=') = 1r. Exes, (z (2)(8) for all z' E Zu
20
if min d(z') > then // Early stopping
Break for iterations do
22
23
For all z' E Zu. sample a trajectory from r22)) and add to replay buffer BRL. For a'l E Zu, update policy ní. for Kpd steps replay buffer BRI optimize the discriminator reward as in Sect. 3.1 keeping skills from parent policies fixed
25
The state buffer size B needs be sufficiently large compared H that the state buffers of each policy represent well the distribution of the states generated by the policy's 's diffusing part. In practice set B 10H.
In POLICYLEARNING, newly instantiated policies.
add Kinitial random (uniform) transitions to the replay buffer for each
Moreover, in POLICYLEARNING instead of sampling uniformly the new policies we sample them in 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 UPSIDE'S TREE THE BOTTLENECK MAZE
See Fig. 12.
17

---

Published as a conference paper at ICLR 2022
Fbor trbersation
Sunder of scive palioo
B
0.5 Eor Interections
1.5
Figure 11: Fine-grained evolution of the tree structure on a wall-free maze with N 4 and A 8, The environment is a wall-free continuous maze with initial state located at the center of the maze. Image A represents the diffusing part around So. In image B. N 4 policies trained, yellow) is sufficiently discriminable, thus it pruned, resulting image small number of interactions enough to ensure that three policies are ry-disrrminable (image C). image D, a fourth policy (in green) able to become ry- y-discriminable. New policies are added, trained and p-discriminated from 5 policies (image E) N 8 policies (image F). Then policy (in yellow) is expanded with A 4 policies (image G). additional policies
of them (in lime
They are all v-discriminable convergence until time-out (as done here). On the left, we plot number active policies (which represents the number of policies that are being trained at the current level of the tree) as well as the average discriminator accuracy over the active policies.
added (images H. ...). The process continues until
Figure 12: Incremental expansion of the tree learned by UPSIDE towards unexplored regions of the state space in the Bottleneck Maze.
C EXPERIMENTAL DETAILS
C.I BASELINES
DIAYN-NZ- This corresponds to the original DIAYN algorithm (Eysenbach et al., 2019) where Nz is the number of skills to be learned. order make the architecture more similar to SIDD,, 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 the price sample efficiency, may also help put lesser constraint on the model (e.g. gradient interference).
DIAYN-CUrT. We augment DIAYN with curriculum that enables to be less dependent on an adequate tuning of the number of skills of DIAYN. We consider the curriculum of UP SIDE where start learning with sstartt policies during period of time/number of interactions. If the configuration satisfies the discriminablity threshold 77, skill is added, otherwise skill is removed learning stopped (as Alg. 2, lines 5-12). Note that the increasing version of this curriculum is similar to the proposed in VALOR (Achiam al., 2018, Sect. 3.3). In experiments,
Astart 1.
18

---

Published as a conference paper at ICLR 2022
DIAYN-hier. extend DIAYN through the use of hierarchy of directed skills, built following the UPSIDE principles. The difference between DIAYN-hier and UPSIDE is that the discrimi- nator reward is computed over the entire directed skill trajectory, while it is guided by the diffusing part for UPS STD. This introduced baseline can be interpreted as an ablation UPS UPSIDE IDE, 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 state density model with VAE, yet we failed to make work on the maze domains that we consider. As we use the cartesian (2, 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 multinomial distribution over "buckets of states" obtained by discretization (as in our coverage computation), resulting in 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 by SMM does not lead to satisfying results in presence of bot- tleneck states as shown in Campos et al., 2020, page 7: "We were unable to explore this type of maze effectively with SMM"). our implementation, the oracle samples states uniformly in the mazes avoiding the need to handle complex exploration, but this setting is not realistic when facing unknown environments.
C.2 ARCHITECTURE AND HYPERPARAMETERS
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), DTAYN, DTAYN-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 is learnt in 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 two-hidden layers (of size 64 for maze environments and 256 for control environments) neural networks. The discriminator 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 byper-parameters:
Discount factor: = 0.99
TTD: (0.1, 0.150,15..,0. 0.2)
Q-functions soft updates temperature 0.005
Policy Adam optimizer with learning rate Irpal = (1c 11-
policy inner epochs Kpol {10, 100}
policy batch size Bpoi = {64}
Discriminator delay: J = 10)
Replay buffer maximum size: 1e6
Kinttall le3
We consider the same range of hyper-parameters in the downstream tasks.
Forr completeness, we report here the performance of DIAYN-SAC in continuous mazes: DIAYN-SAC with N₂ 2 10 on Bottleneck maze: 21.0 (# 0.50); on U-maze: 17.5 (# 0.75), to compare with DIAYN-TD3
with Nz = 10 on Bottleneck maze: 17.67 (# 0.57); on U-maze: 14.67 (# 0.42). We thus see that DIAYN-SAC
fails to cover the state space, performing similarly to A YN-TD3 (albeit over larger range of hyperparameter search, possibly explaining the slight improvement..
19

---

Published as a conference paper at ICLR 2022
UPSIDE, DIAYN and SMM variants (common for all environments) optimization hyper- parameters:
Discriminator batch size Buiser = 64
Discriminator Adam optimizer with learning rate Wraiser = (le (1e-3, 1e-1)
discriminator inner epochs Kdiser {10, 100}
Discriminator delay: {1, 103
State buffer size B 10H where the diffusing part length H is environment--peciffc.
EDL optimization hyper- apper-parameter:: We kept the same Campos al. (2020). The VQ-VAE's architecture consists an encoder that takes states as an input and maps them to a code with 2 hidden layers with 128 hidden units and final linear layer, and the decoder takes the code and maps 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.
Peommitment {0.25, 0.5}
VQ-VAE's code size 16
VQ- VAE batch size Baq = (64, 256}
total number epochs: 5000 (trained until convergence)
VQ- VAE Adam optimizer with learning rate Irve-vee {le 33, 1e 1e=
Maze specific hyper-parannn typer-parameters:
steps 5e4 (and in time 10 minutes)
T H 10
Max episode length Hmax 200
Max number of interactions T 1e" during unsupervised pre-training and downstream tasks.
Control specific optimization byper-parameterss
K steps 1e5 (and in time hour)
T H 50
Max episode length Hmax = 250
Max number of interactions T'ux = 1ea during unsupervised pre-training and downstream tasks.
Note that hyperparameters are kept fixed for the downstream tasks too.
C.3 EXPERIMENTAL PROTOCOL
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 environment, each algorithm is trained without any extrinsic reward on Nunsup 3 seeds which we call unsupervised seeds (to account for the random- ness 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 have fewer vironment interactions than Tmax thanks to its termination criterion (triggered more policies); for instance, all baselines where allowed T max 1e7 on the maze environments, but UPSIDE finished at most in le6 environment steps fitting in average 57 and 51 policies respectively for the Bottleneck Maze and U-Maze.
cannot fit any
Model selection. For each unsupervised seed, we tune the hyper-paramette according certain performance metric. For the baselines, consider the cumulated intrin- sic 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 poli- cies. i.c., how many policies were d-discriminated during their training stage. For each method, we thus have many models seeds, i.e. Nunsup-
each algorithm
20

---

Published as a conference paper at ICLR 2022
Downstream tasks. For each algorithm, evaluate the Nunsup selected models 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 certain radius (i.e., the goal location unknown until is reached once) and with sparse reward signal (i.e., reward of 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 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 exhaustive manner,
discretize the state space into B 14 buckets and we randomly sample Vgual = 3 from each of these buckets according to what we call goal seeds (thus there Bgoal goal 10 different goals in total). For every goal seed, initialize each algorithm with the set of policies learned during the unsupervised pre-training. We then roll-out each policy during Nesplo episodes 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 skill whose length the remaining number of interactions left, i.e. Hmax L. The ability of selecting good policy is intrinsically linked to the coverage performance of the model, but also 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 possible the goal. This is particularly important 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 well "vanilla" baselines trained from scratch during the downstream tasks: TD3 (Fujimoto et al., 2018) and ICM (Pathak et al., 2017). In the Ant environment, also consider Ngaal 3 and B Bgout
14 in the [-8, 8)2 square.
21

---

Published as a conference paper at ICLR 2022
(a) UPSIDE discriminator
(b) DIAYN discriminator
(c) EDL VQ-VAE
Figure 13: Environment divided in colors according the most likely latent variable Z, according to (from left right) the discriminator learned by UPSIDE, the discriminator learned by DIAYN and the VQ-Vi VAE Icarned by EDL. Contrary to DIAYN, UFS IDD's optimization enables the discriminator training and the policy training to catch up to each other, thus nicely clustering the discriminator predictions across the state space. EDL 's VQ-VAE also manages to output good predictions (recall that consider the EDI version with the strong assumption of the available state distribution oracle, see Campos al., 2020), yet the skill learning is unable cover the entire state space due exploration and sparse rewards.
(a) 3MM
(b) DIAYN-CUFE CUUr
DIAYN-hier
(d) Flat UPSIDE
Figure 14: Complement to Fig. 2: Visualization the policies learned on the Bottleneck Maze for the remain- ing methods.
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.96
0.88
0.49
0.0
0.96
0.61
0.75
0.68
(a) SMM
(b) TD3
Figure 15: Complement Fig.5. Heatmaps of downstream task performance after fine-tuning the remain-
ing methods.
D ADDITIONAL EXPERIMENTS
D.1 ADDITIONAL RESULTS BOTTLENECK MAZE
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.c., those not reported in Fig. 5).
22

---

Published as a conference paper at ICLR 2022
(a) UPSIDE
(b) DIAYN
(c) EDL
(d) SMM
(e)
DIAYN-CUFT
DIAYN-hier
(g) Flat UPSIDE
Figure 16: Visualization the policies learned on U-Maze. This is the equivalent of Fig. for U-Maze.
0.0
0.0
0.0
0.11
0.06
0.36
0.17
0.11
0.16
0.39
0.63
0.0
0.0
0
0.0
0.0
0.0
0.6
0.59
0.43
0.34
0.87
0.61
0.91
0.86
0.72
0.67
0.85
0.52
0.5
0.43
0.97
0.89
0.76
0.67
0.96
0.88
0.76
0.21
0.96
0.88
0.75
0.44
(a) UPSIDE before fine-
(b) UPSIDE
(c) DIAYN
(d) EDL
tuning
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.09
02
0.03
0.0
0.31
0.91
0.87
0.52
0.67
0.91
0.87
0.35
0.34
0.91
0.87
0.71
0.33
0.96
0.88
(c)
1CM
SMM
(g)
TD3
Figure 17: Heat maps of downstream task performance U-Maze. This is the equivalent of Fig. for U-Maze.
D.2 ADDITIONAL RESULTS ON U-MAZE
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.c., the equivalent of Fig. 5 for the U-Maze). The conclusion is the same 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.
23

---

Published as a conference paper at ICLR 2022
Average discrinnnntoo accuracy
0.8
Average discriniaatos
0.6
DIAYN- 10
DIAYN-5
DIAYN-20
DIAYN-10
0.4
0.2
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Ear Interactions
-10*
Eaw inteructions
-107
(a) Bottleneck Maze
(b) Ant
Averago disoriiinstor sccuracy
0.8
10.8
Average dacriminator
0.6
0.6
0.4
DIAYN-S
D-AYN-5
DIAYN-20
0.2
D-2Y
0.2
0-4
0.6
0.8
0.2
0.4
0.6
0.8
Ear Internatiioss
1007
Ear interactions
-207
(c) Half-Cheetah
(d) Walker2d
Figure 18: Average discriminability of the DIAYN-N2 policies. The smaller Nz is, the casier it is to obtain close-to-periie to-eeffect discriminability. However, even for quite large Nz (50 for mazes and 20 in control envi- ronments), DIAYN is able achieve good discriminator accuracy, often because policies learn how "stop" some state.
D.3 ANALYSIS OF THE DISCRIMINABILITY
In Fig. 18 (see caption) we investigate the average discriminability of DIAYN depending on the number of policies Nz.
24

---

Published as a conference paper at ICLR 2022
( 11 = 10
(b) T = 20
T H 30
(d) T = H = 40
(e) T = H = 50
-T= 10
T- 20
(h) H 30
(i) T H 40
( H 50
Figure 19: Ablation on the length of UPSIDE policies (I' H): Visualization of the policies learned on Bottleneck Maze (top) Maze (bottom) for different values T, H. (Right table) Coverage values (according to the same procedure as in Table 2). Recall that T and H de- note respectively the lengths of the directed skill and the diffusing part UPSIDE policy.
UPSIDE
Bottleneck Maze
U-Maze
the
T == 20
10
85.67
(=1.3)
71.33
(4:0.42)
87.33
(=0.42)
67.67
(+1150)
T=H=0 30
77.33
(13.06)
68.33
(10088)
T= 40
59.67
(=1.81)
57.33
(#0.96)
T= 50
51.67
(10.63)
58.67
(1:1.26)
D.4 ABLATION 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 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 (as done all other experiments) but also 20 or 30. Naturally, the performance degrades 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, recover the performance of flat UPSIDE
D.5 FINE-TUNING RESULTS ON HALF-CHEETAH AND WALKER2D
In Sect. 5, we reported the fine-tuning results on Ant. We now focus on Half-Cheetah and Walker2d, and similarly observe that UPS IDE largely outperforms the baselines:
UPSIDE
TD3
D DIAYN
Half-Cheetah
174.93
(#:1.45
108.67
(=25.61)
0.0
(:0.00
Walker2d
46.29
(43.00)
14.33
(+1.00)
2.13
(#0.74)
We note that the fine-tuning experiment on Half-Cheere exactly corresponds to the standard Sparse- Half Chefthh task, by rewarding states where the x-coordinate larger than 15. Meanwhile, Sparse- Walker2d provides reward long as the x-coordinate is larger than 1 and the agent is standing up. Our fine-tuning task on Walker2d more challenging as we require the x-coordinate to be larger than 4. Yet the agent be rewarded even if it is not standing up, since downstream task is purely goal-reaching goal location yet not be standing up (e.g., by crawling), which may occur as there no incentive in UPS IPSIDE to remain standing up, only to be discriminable.
We indeed interestingly noticed that UPSIDE may reach the desired
25


Reviews:
[{"review_id": "wwEos5Si69h", "reviewer": "Reviewer_wdBX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nCons:\n- The proposed method is overly complex and contains many ad hoc decisions. For instance, the iteration in Algorithm 1 seems entirely ad hoc to me.\n- It is unclear how to adapt the method to a larger or a continuous space of skills, which is important for more realistic applications.\n- The theoretical justification for the proposed method is weak. For instance, Lemma 1 shows that the proposed objective is a lower bound on empowerment, but the paper entirely ignores the question of whether the bound is tight (in contrast to all previous work in the area which uses tight bounds). Further, in Sec 3.4, the paper claims that the algorithm is “guaranteed to terminate with the optimal number of policies”, however, the proof ignores the fact that q(z|s) depends on the number of policies. As far as I can tell the algorithm is only guaranteed to find a “locally” optimal solution (i.e. optimal for the corresponding q), not the optimal solution.\n- The empirical evaluation unfortunately suffers due to non-standard evaluation metrics. As far as I can tell, the paper does not follow any existing evaluation protocol. \n\nSeparately from the cons, I am not convinced that the idea of performing constrained optimization (Eq P_eta) is important for the proposed algorithm. It seems that a very similar algorithm can be obtained by jointly optimizing I(x;z) and N for maximum empowerment.\n\nPros:\n- The paper focuses on the relevant problem of improving coverage in unsupervised skill discovery\n- The proposed method significantly outperforms prior work and provides important insights into what properties are important for a successful skill discovery algorithm, such as using discriminability of the final state in the trajectory and stacking skills sequentially for better exploration.\n- The paper presents extensive experiments and visualizations which detail the failure points of prior work\n- The paper is clearly written and technically relatively strong\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper has many issues and in my opinion the proposed algorithm is not viable in more complex domains. However, it is possible that some of the limitations can be lifted, such as using discrete skill variables only. Further, the paper empirically presents good performance on the challenging ant domain and contains several important insights that might be useful for the future researchers. Therefore I am leaning towards accept.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rUd6E5USpLA", "reviewer": "Reviewer_H3Jm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The submission has all components that make up a good paper: it reads well, describes and motivates the problem, positions itself with respect to the prior literature, covers the theory and implementation with necessary details, and compares the prior methods. I don’t have any critical concerns, and only mostly minor comments and suggestions.\n\nI cannot fully parse the objective in Equation 2. Especially the sentence “In words, the skill is incentivized to bring the diffusing part to a discriminable region of the state space.” seems to be incorrect. The reward does incentivize the skills to stay in a discriminable region, but only the discriminability of the end of the episode should matter (not how we got there). In fact, I would expect this objective to lead to skills that try to avoid unvisited states (as those regions are indiscriminable) and the skills should be biased in already visited direction rather than being symmetrically distributed, as is the case for example in Figure 4(a). Can you elaborate on why the chosen reward works?\n\nRegarding the experiments and comparison to DIYAN, I find it strange that the coverage of RANDOM is practically as good as DYIANs, and in the case of Ant, RANDOM actually surpasses DYIAN. The text clarifies that in the Half-Cheetah and Walker2d environments, “DIAYN policies learn to fall on the agent’s back”. This does not seem to be the case in the original DIAYN paper (https://sites.google.com/view/diayn), where the agent especially in the HalfCheetah environment is able to acquire proper gaits. Can you comment on this discrepancy?\n\nWhat are the axes in Figure 4(a) and (b)? I suppose they are the xy-coordinates, in which case UPSIDE covers the space really well. Just to confirm, the discriminator gets to see the full state, not just these two coordinates?\n\nThe sparse reward tasks do not bring much new to the paper because the result is obvious from the coverage plots showing UPSIDE explores well. I would suggest using one of more standard sparse exploration tasks (e.g., SparseHalfCheetah) to better show the benefits and make the result comparable to existing literature. \n\nThere is a missing related paper [1], which also learns unsupervised skills by fitting a distance function. They learn only a single directed policy and do not try to cover the entire state space, but their policy also includes a directed part and a diffusive part for exploration.\n\nEquation 1 has a missing maximization operator on the right hand side of the equation.\n\n[1] Hartikainen et al., Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery, ICLR 2020\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Good paper that has all required components. The proposed algorithm is novel, the paper provides both theoretical analysis as well as a practical version of the algorithm, and the experiments indicate substantial improvement over prior works. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xg-mmjSlxTF", "reviewer": "Reviewer_zwRd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**: \nThis work takes a novel approach to the skill discovery problem. Instead of directly finding maximal entropy policies that act as skills, this work splits skills into directed and diffusing (exploratory) components. The paper also includes a technique for limiting the number of skills by ensuring they satisfy some minimal discriminability threshold. Finally, the method also includes a method for generating compositions of directed skills via a tree structure and then diffusing from the leaf to explore. Overall the method is novel and is appears to be supported by experimental results. \n\n**Weaknesses**: \nI think there are several weaknesses in the presentation and experimentation that would need to be addressed.\n1. For the continuous control environments, why are there no finetuning results on the downstream tasks besides Ant? For some reason the authors report coverage and discriminator accuracy for three gym tasks: Ant, Half-Cheetah and Walker but only downstream RL results on Ant. Please report downstream results on the other two tasks as well. \n2. Why is DADS not included as a baseline? DADs has been shown to outperform DIAYN on the continuous control tasks and should certainly be compared against. \n3. I am slightly confused by the discussion regarding a fixed number of skills N - DIAYN at least doesn’t have this - it just has a skill conditioned policy with z sampled from the uniform distribution. \n   \n-   Using DIAYN-Nz doesn’t seem particularly valid to me - you should compare against the original method as well for proper comparison\n    \n-   The authors then introduce modified variants of DIAYN (DIAYN-curr) to deal with the fact that it has a limited set of policies - which was not how the algorithm was designed to begin with. Additionally they then switch to TD3 claiming it doesn’t work well. Instead as mentioned above, please comparison against the original DIAYN codebase. \n\nMinor Nitpicks:\n- Add some sort of visualizations of the learned skills for the continuous control environments. \n- “We optimize policies by maximizing their number under the constraint that each of them reaches distinct regions of the environment” - this sentence needs a wording fix - its a bit unclear in the abstract itself what maximizing their number means.\n- Figure 5: what does UPSIDE before/after mean?\n- Figure 10 or something like it should go in the main paper (it is very helpful in understanding the main idea of the work)\n\nOverall, I recommend rejection but I am open to updating my score if my concerns are addressed. ", "summary_of_the_paper": "This work proposes a new framework for unsupervised skill discovery termed UPSIDE which aims to learn a fix set of state space covering skills that have a directed and diffusing (noisy) component, are constrained to be sufficiently discriminable and are chained together in a tree structure to enable composition. The paper shows results on grid world and continuous control environments demonstrating the effectiveness of their method. ", "summary_of_the_review": "Overall, the method proposed in this work is novel but the experiments, while showing performance improvements for the proposed method, do have several flaws which I point out in my review. If these issues can be addressed, I would be open to updating my score from rejection. \n\n=====================================UPDATE=========================================================\nAfter discussion with the authors, I have raised my score as my experimental concerns have been addressed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TRYafnqef1F", "reviewer": "Reviewer_d1m1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n* This is an interesting approach to improve unsupervised skill discovery in multiple ways: state space coverage, avoiding prespecifying the number of skills to learn, and dynamically extending episode horizons.\n\n  Most skill discovery methods that use the mutual information decomposition of a form of $\\mathcal{I}(S; Z) = \\mathcal{H}(Z) - \\mathcal{H}(Z|S)$ fix the distribution of $z$ and do not encourage exploration. This work suggests a workaround to explore local regions with a decoupled policy structure (direct and diffuse), which I find a meaningful contribution.\n\n  The approach of maximizing the number of skills via the constrained objective and learning new skills on top of existing ones in the tree-structured manner is also an intriguing direction for skill discovery with less predetermined components.\n\n* In comparison with the baseline skill discovery methods, this method shows improved state space coverage and performance empirically (see my comment about the issue with MuJoCo experiments below, though).\n\n* The visualization and analyses provide meaningful insights. They show that the proposed method is effective for learning a set of skills covering the state space on the toy (Maze) environments (Table 2 and Fig.2). They also present how well their method can reach different goals on Bottleneck Maze before and after fine-tuning (Fig.5).\n\n**Weaknesses**\n\n* The diffusing with the simple random walk policy (performing uniform random actions) is one of the most basic strategy for exploration and wouldn't be very effective on many environments, as it does not necessarily lead to good (local) state space coverage. Fig.4 (a) is an example of such case. This is also mentioned by the authors in Sec.6.\n\n* Only a few baseline methods are used for the comparison on the MuJoCo environments (Ant, Half-Cheetah, and Walker2d), considering that those environments are much more complex and closer to real-world scenarios than the Maze environments.\n\n  More importantly, DIAYN (Eysenbach et al., 2019) and RANDOM are not a good choice of baselines for comparing state space coverages in MuJoCo control environments. The authors can check out/consider other works, such as DADS (Sharma et al., 2020) or IBOL (Kim et al., 2021).", "summary_of_the_paper": "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.", "summary_of_the_review": "The authors propose an interesting approach to unsupervised skill discovery tackling multiple issues with some existing prior methods. They also provide meaningful empirical results and analyses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose UPSIDE, a method for improving state coverage in unsupervised skill learning. "Direct-and-diffuse" policies concatenate phases of directed behaviour followed by dithering to improve neighbourhood coverage in the region of state space visited, trained with a discriminability objective to ensure diversity in region coverage, and composing these skills into a tree structure to further improve coverage.

Reviewers generally found the submission highly novel and well written, were encouraged by the experimental results, and were unanimous on the importance of the problem addressed. Reviewers d1m1 and wdBX praised the visualizations as adding considerable insight. d1m1 raised the concern that a random walk in the second stage would not work in some environments (which the authors pointed out can be overcome by the tree method) and suggested DADS was a better baseline than DIAYN (also mentioned by zwRd, with which the authors agreed, and proceeded to implement). zwRd expressed concerns about gaps in the finetuning results (addressed by the authors in follow-up) as well as details of the DIAYN setup (also addressed to zwRd's satisfaction). H3Jm's minor concerns around the text and equations, figures and DIAYN experimental results were fully addressed in discussion. wdBX was the reviewer with the most substantive concerns around the apparent complexity, ad hoc design, scalability and lack of theoretical grounding. After discussion (which resulted in the authors drafting a proof in the comments, an ICLR first for this AC) wdBX believed that the paper would be improved by additions proposed, but remained "borderline" in their evaluation.

The work presents a compelling, if somewhat complicated (and therefore perhaps unsatisfying, to some), method improving state coverage in unsupervised skill learning. Research in contemporary machine learning often takes the form of one piece of work pushing the boundaries significantly with a complex algorithm with further work dissecting and refining the ideas therein, reducing them to their essence. Viewed through this lens, the paper in question presents several ideas that all form parts of the overall method which appear likely to serve to inspire and motivate future work. With all reviewers leaning accept either strongly or weakly, there is little doubt in the AC's mind that this paper should be accepted, and widely read by researchers interested in unsupervised skill acquisition.
Decision: Accept (Poster)