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

Abstract: Learning meaningful behaviors in the absence of a task-specific reward function is a challenging problem in reinforcement learning. A desirable 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. At test time, an agent could then leverage these skills to solve sparse reward problems by performing efficient exploration and finding an effective goal-directed policy with little-to-no additional learning.  Unfortunately, it is challenging to learn skills with such properties, as diffusing (e.g., stochastic policies performing good coverage) skills are not reliable in targeting specific states, whereas directed (e.g., goal-based policies) skills provide limited coverage. In this paper, inspired by the mutual information framework, we propose a novel algorithm designed to maximize coverage while ensuring a constraint on the directedness of each skill. In particular, we design skills with a decoupled policy structure, with a first part trained to be directed and a second diffusing part that ensures local coverage. Furthermore, we leverage the directedness constraint to adaptively add or remove skills as well as incrementally compose them along a tree that is grown to achieve a thorough coverage of the environment. We illustrate how our learned skills enables to efficiently solve sparse-reward downstream tasks in navigation and continuous control environments, where it compares favorably with existing baselines.

Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reaching
Anonymous Author(s)
Affiliation Address email
Abstract
Learning meaningful behaviors in the absence of task-specific reward function is a challenging problem in reinforcement learning. A desirable unsupervised objective is learn a set of diverse skills that provide thorough coverage of the state space while being directed, i.e., reliably reaching distinct regions of the environment. At test time, an agent could then leverage these skills solve sparse reward problems by performing efficient exploration and finding an effective goal- directed policy with little-to-no additional learning. Unfortunately, is challenging to learn skills with such properties, as diffusing (e.g.. stochastic policies performing good coverage) skills are not reliable targeting specific states, whereas directed (e.g., goal-based policies) skills provide limited coverage. In this paper, inspired by the mutual information framework, we propose a novel algorithm designed maximize coverage while ensuring constraint skill. In particular, we design skills with decoupled policy structure, with a first part trained to be directed and second diffusing part that ensures local coverage. Furthermore, we leverage the directedness constraint to adaptively add or remove skills well incrementally compose them along a tree that is grown to achieve thorough coverage of the environment. We illustrate how our learned skills enables efficiently solve sparse-reward downstream tasks in navigation and continuous control environments, where it compares favorably with existing baselines.
11
the directedness of each
13
15
17
19
Introduction
20
Deep reinforcement learning (RL) algorithms have been shown to effectively solve wide variety of complex problems [c.g.. 23, 6, 31, 12, 2, 28]. However, they are often designed solve one single task at time and they need to restart the learning process from scratch for any new problem, even 23
21
22
24 when it is defined on the very same environment (e.g., navigating to different locations in the same apartment). Recently, unsupervised RL (URL) has been proposed as an approach to address this limitation. In URL, the agent first interacts with the environment without any extrinsic reward signal. 27 Afterward, the agent leverages the experience accumulated during the unsupervised learning phase to
25
26
28 efficiently solve variety of downstream tasks defined on the same environment.
29 In this paper, we consider the URL setting where the agent starts from an initial state so and resets
30 to it every time the policy terminates. We focus sparse-reward downstream tasks, which require
31 effective exploration (i.c.. via thorough coverage of the state space) to find the goal well as
32 learning policy reliably reaching the goal (i.c., a directed policy).
39 We build on the insight that mutual information (MI) effectively formalizes the dual objective of learning skills that both cover and navigate the environment efficiently [e.g.. 11]. Specifically, given
35 the state variable S and some variables Z on which the skill policies are conditioned, MI is defined as H(S)
I(S;
H(SIZ)
H(Z) H((Z(S),
(1)
coverage
directedaess
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Figure I: Overview of UPSIDE. The black dot corresponds to the initial state so. (A) A set of random skills initialized, each skill being composed a directed part (illustrated as a black arrow) and diffussig part (red arrows), which induces local coverage (colored circles). (B) The policies associated to the directed part of each skill are then updated to maximize discriminability of the states reached by their diffusing part (Sect. 3.1). (C) The least discriminable skills are iteratively removed while the policies of the remaining skills are re-optimized. This is executed until the discriminability of each skill satisfies a given constraint (see Sect. 3.2). In this example three skills are kept. (D) One of these learned skill is then used basis to add new skills, which are then optimized following the same procedure. For the "red" and "purple" skills, UPSIDE is not able to find sub-skills of sufficient quality and thus they not expanded any further. (E) At the end of the process, UPSIDE has created a tree of directed skills covering the state space (Sect. 3.3). These covering skills can then be used to solve downstream tasks. Moreover, the discriminator learned together with the skills can be used select the skill to reach any specific goal region, where the directed parts get close to the goal, while the diffusing part provides the local coverage to attain the goal. The complete algorithm detailed in Sect. 3.4 and Appendix.
36
where I denotes the MI and H the entropy function. The first expression, known as the forward form of MI, explicitly balances the two sought-after properties of coverage captured by the entropy over the state space H(S)) - and directedness, i.e., the ability to reach specific states S depending on Z captured by the negative conditional entropy - (S Z). The second expression of (l), often easier to optimize and referred to as the reverse form, stipulates that the skills should be sampled as diversely as possible while being discriminable.
37
38
39
40
41
42
Maximizing (1) has been shown to be a powerful approach for encouraging exploration in RL [16, 25] and for unsupervised skill discovery [e.g.. 11. 9, 1, 30, 8]. Nonetheless, learning skills that maximize the MI is a challenging optimization problem. Several approximations have been proposed to simplify the problem at the cost of possibly deviating from the original objective of coverage and directedness (see Sect. 4 for review of related work). In this paper, we propose UPSIDE (UnsuPervised Skills that direct then DiffusE) to learn skills that can effectively used to solve goal- downstream tasks. Our solution builds on the following components (see Fig. for an illustration of UPSIDE):
43
44
45
46
47
49
Skill structure. In order to balance coverage and directedness, we design skills composed of two parts: 1) a directed part that is trained reach distinct region of the environment, and diffusing part that covers the states around the region attained by the first part.
50
51
52
Optimization. We further strengthen the coverage and directedness properties of the skills by turning the MI objective into constrained optimization problem designed maximize coverage under the constraint that each skill achieves a minimum level of discriminability. This in turn enables UPSIDE to adaptively add skills improve coverage, when all the initial skills meet the constraint, or remove those that violate the constraint to guarantee that each skill is directed and reaches a distinct region of the environment.
53
54
55
56
57
Tree structure. When the agent starts from fixed initial state, the skills' length is crucial parameter, where short skills do not allow for proper coverage, and long skills are difficult to train. In UPSIDE we consider short skills to make the optimization easier, while composing them along tree structure that ensures an adaptive and deep coverage of the environment.
59
80
61
82 We study how our learned skill structure enables to both perform efficient exploration and learn effective geal-reaching policies in variety of navigation and continuous control environments (including MuJoCo's 's reacher) and we compare its performance to relevant baselines.
84
2
Setting
85
86
We consider the URL setting where the agent interacts with a Markov decision process (MDP) M with state space S. action space A, dynamics p(s')k ss a), and reward. The agent starts each
2

---

68 episode from a designated initial state So E S. Upon termination of the chosen policy, the agent is then reset to Sg. This setting is particularly challenging from an exploration point of view since the agent cannot rely on the initial distribution to cover the state space.
69
70
71 We recall the MI-based unsupervised skill discovery approach [see e.g.. 11]. Denote by Z some
72 (latent) variables on which the skills of length T' are conditioned. There are three optimization
73 variables: (i) the support of the skills denoted by |Z] (we consider it be discrete so |2| is the
74 number of skills), (ii) the policy π(z) associated to skill 2, and (iii) the sampling rule (i.e., p(=)
75 the probability of sampling skill 2 at the beginning of the episode). Let the variable Sy be the
78 random (final) state induced by sampling a skill from p and executing the associated policy T(2)
77 from so for an episode. We denote by ((T) the distribution over (final) states induced by executing the policy of skill 2, by ()))) the probability of z being the skill to induce state sy, and
79 let ((T)) = =Eve ((=))=(=)(5))) (ST). Then maximizing the MI between Z and ST can be written as
max Z)= = =((s)) - H(ST) = -- ((T) logp(sr) + Σ (er [lgg
ZEZ
= =((Z) - H((I/T)= = E(2)) - log p(z) + 3 (()) [[gg(t|<T]], (1)
=EZ
ZEZ
~ (x)()) (ST). As discussed in Sect. 1, learning the optimal Z), P. and m 81 is a challenging problem [see e.g., 11, 9, 8].
80 where in the expectations ~
82 3 Algorithm Structure
UPSIDE is based on three main components: a) the skill learning corresponding to stage A and B of Fig. I and described in Sect. 3.1, b) a constrained optimization problem used to optimize the number of skills (stage C' and Sect. 3.2) and c) tree-building procedure (stage D and Sect. 3.3). Together,
84
86 these components allow UPSIDE to discover skills that combine coverage and directedness.
87
3.1 Skill Structure and Optimization
As shown in e.g., [9, 30, 37], the level of stochasticity of each skill (e.g., induced via regularization 89 on the entropy over the actions) plays key role in trading off coverage and directedness. In fact,
88
90 while randomness promotes broader coverage, it may compromise the directedness of the skills,
91 In fact, a highly stochastic skill tends to induce a distribution P=(=) (ST) over final states with high
92 entropy (thus decreasing - -))S which prevents the skill to be reusable in solving sparse-reward
93 downstream tasks where the objective is reliably reach specific goal state of the environment. Determining how much stochasticity to inject to adequately balance both objectives and optimize (1)
34
95
a difficult problem.
diffusing part lov tnd
96 We propose to design skills with a decoupled policy structure:
A directed part (of length T) with low stochasticity and trained to reach a specific region of the environment. It is responsible for increasing the - (H(S) term in (1).
directed part ofe
97 A diffussing part (of length H) with high stochasticity to promote local coverage of the states around the region reached by the directed part. It responsible for increasing the H(S) term (1).
Figure 2: Directed and diffus- ing parts of the skill.
98
Similar to prior work [e.g., 11, 9], the policy associated to the directed part of skill 2 is trained to max- imize an intrinsic reward (s) x p(2[s),² where p(z(s) measures the "discriminability" of the skill
given the state s. More formally, T(2) maximizes the cumulative reward En(s) ET rz (s:) over the states traversed by the policy during the diffusing part. In practice, we also add small entropy regularization (- st)) to the directed policy in order to ensure a minimum level of exploration and make the learning more robust. For the diffusing part, we rely on simple random
100
101
102
103
104
walk policy (i.e., a stochastic policy with uniform distribution over actions).
In RL, stochasticity is injected at "train time" to boost exploration or improve robustness, while the policy executed "test time" is deterministic. Here we refer stochasticity introduced to better optimize (1). 2 'Although [11, 9] employ rewards in the log domain, we find that using a reward that is a non-linear transformation into [0, 1] works better in practice, as also observed in [33, 5J. Furthermore, in practice we replace p(z[s) by the predictions of a learned discriminator go (2(2)) as explained in Sect. 3.4.
3

---

105
Intuitively, the diffusing part defines a cluster of states that is used as goal for the directed part. This allows us to "ground" the latent variable representations of the skills Z to specific regions of the environment (i.e., the clusters). As a result, maximizing the MI over such skills can be seen as learning a set of "cluster-conditione"" and thus directed, policies.
106
107
108
109
3.2
Skill Support and Sampling Rule
The MI objective (1) crucially depends on the number of skills ((Z) and the distribution p(z). Unfortunately, it is been shown [e.g., 8] that solving (1) is particularly challenging. In order to simplify the optimization and the associated learning problem, we modify (1) in two ways.
110
111
112
113
First, coherently with the skill optimization detailed in Sect. 3.1, the random variable in the conditional entropy is any state reached during the diffusing part of the skill and not just the terminal state. More formally, we denote by San the random variable and its distribution for a specific skill e is (Sun) = H Ei=44 (s))) i.e., the distribution over states obtained by averaging the distributions at any of the steps in the diffuuing part. Similarly, p(z[sait) now denotes the probability of being the skill to traverse Saif during its diffusing part. As result, training the skills to maximize MI naturally leads the diffusing parts to "push" the directed parts away so as to reach diverse regions of the environment. The combination of "global" coverage of the directed parts and "local" coverage
115
118
117
118
119
120
121
of the diffusing part ensures that the whole environment is properly visited with |Z| < S skills."
122
Second, we introduce an alternative problem that simplifies the optimization while preserving the coverage and directedness properties of MI. This is achieved by introducing a stronger requirement on the discriminability. While the conditional entropy term S() in (1) promotes the discrim- inability of skills on average, we argue that a more suitable objective is to constrain each skill to
123
124
125
128
achieve a minimum level of discriminability. First, we move from the average the minimum over skills by lower bounding the conditional entropy as
127
HH(ZSSar) = Σ p(2) [log [ogp(>|san)) 2 min
Exar [log p (a))s)
(2)
=E7
ZEZ
128
which leads to the following optimization (assuming w is fixed for convenience)
{ (H(Z)) + min Exg [log p( p(2/)))))]] =E[M]
max N,
(3)
129
where with an abuse of notation we use = E [N] to denote all skills in a set with cardinality N. Since (3) is lower bound to MI, it tends to promote the same type of covering and directed skills. Furthermore, (2) no longer depends on the distribution over skills and the entropy term H(Z) is
131
132
maximized by setting o to the uniform distribution over N skills (i.c., max, H(2) = log(NN), thus simplifying the optimization, which now only depends on N.
133
134
While optimizing (3) promotes a cardinality N such that all skills have good discriminability, more convenient formulation is to explicitly set a minimum level of discriminability for all skills through the following constrained optimization problem:
135
136
max log(N) N21
S.L.
min Exgu [log [logp(=|ssaa (=][sarr) 2 log 1)-
NE(N]
137
where 7 is a parameter that defines the discriminability threshold. A skill 2 is said to be 1/-consolidated if it satisfies the constraint. Crucially, let PN == minze(N] Esc.n [log p(2|sa(r)) then the sequence PN)) N21 is non-increasing with P1 = O (i.e., the more skills the harder it is to meet the constraint). As result, (4) can be optimized following simple greedy strategy incrementally adding skills until the constraint is violated. The optimal N thus defines the effective number of n--consolidated skills and it corresponds to the largest number of skills that is guaranteed to display sufficient discriminability. Alternativly, we can interpret (4) finding the largest number of clusters (i.e., the region reached by the directed part of a skill and covered by its associated diffusing part) with a minimum level of cluster distance. This effect is qualitatively illustrated in Fig. where the states attained by the directed part of the skills attain different regions that are locally covered by their diffusing parts.
139
140
142
144
145
146
'Notice that (1) is maximized by setting |Z| = ||S| (since maxy I(X, Y)= = x(x,x) = H(X) (), i.c.
where each skills is a goal-conditiones policy reaching different state. This implies having many policies as states, which makes the learning particularly challenging as the complexity of the environment increases.

---

Algorithm 1: UPSIDE
Initialize: Discriminability threshold y E (0, 1). branching factor No 2 1, patience K Initialize: Tree T initialized as a root node indexed by O, queue parent nodes = {0).
while W * do // tree expansion
Dequeue a node/skill w' E W and expand 'T at w by adding a set C(w) of No nodes/skills
Create random policies иT,, Vz E C(w)
Initialize discriminator Yo with [7] classes
Continue = true; Saturated false
while Continue do
for K iterations do
Sample skill from T at random
Extract the sequence of nodes 2(1): ...) in T leading to 2
Execute the composed (directed part) policy (T ms) followed by the diffusing part Add states observed during diffusion part to state buffer Update discriminator qa with SGD on B. to predict label x
10
11
if E ((w) then // Update only new policies, other polices kept fixed
Update policy и. using SAC optimize the discriminator reward in Sect. 3.1. Compute the if mil):gc(w) d(=)) yy then // Node removal
14
d(z) = do (z) = [8_1 E,es, (x(2|s) for all x E C(w)
15
Remove the node/skill arg min d(2) from C(wc) and T
Set Saturate true else if not Saturated then Add one new node/skill to C(w) and T
18
20
21
Set Continue false
22
Enqueue in W the consolidated nodes C(w)
147
3.3
Composing Skills in a Tree Structure
The MI optimization problem as well our constrained variant (4) depend the initial state so and on the length of each skill. Although these quantities are usually predefined and only appear implicitly in the equations, they have crucial impact the obtained behavior. In fact, resetting after each skill execution unavoidably restricts the coverage to a radius of at most T H steps around so- This may suggest set T and H to large value. However, increasing the horizon makes the training of the skills more challenging, as learning π would require solving a difficult RL problem itself.
149
151
152
153
Instead, we propose to "extend" the length of the skills through composition. Indeed, the decoupled skill structure and the constraint in (4) entail that the directed part of cach of the 7-consolidated skills reliably reach specific (and distinct) region of the environment and it is thus re-usable and amenable to composition. We propose to chain the directed part of the skills in order to reach further and further parts of the state space. Specifically, we build growing tree, where the root is the initial state so, the edges represent the directed part of the skills, and the nodes represent the diffusing part of skills. As such, whenever skill is selected, the directed part of all the policies associated to its predecessor skills in the tree are executed first (see Fig. 1 for an illustration of the tree structure).
155
157
159
161
As result, the agent naturally builds curriculum the episode lengths, which grow as the sequence (iT + H) As such, it does not require prior knowledge on an adequate horizon of the downstream goal- based task.* 4 Here this knowledge is replaced by and which are more environment-agnostie and task-agnostic quantities, as their choice rather has impact on the size and shape of the learned tree (e.g., the smaller and the bigger the tree).
163
164
186
167
3.4
The UPSIDE Algorithm
188
We are now ready to introduce UPSIDE, which provides specific implementation of the components described before (see Fig. for a qualitative illustration and Algorithm for the detailed pseudo-code).
189
170
We perform standard approximations to make the constraint in (4) casier to estimate. We approximate the unknown posterior p(2(s) with learned discriminator (2 is) with parameters ó. We also
'See e.g., the discussion in [26] on the "importance of properly choosing the training horizon in accordance with the downstream task horizon the policy will eventually face."
5

---

172 remove the logarithm from the constraint to have an estimation range of [0. 1] and thus lower
173 variance". Finally, we replace the expectation over s with an empirical estimate gxx (2) averaging the
174 value of the discriminator evaluated on the last B states observed while executing the diffusing part
175 of 2. Integrating these approximations in (4) leads to
N N21.
S.L.
min 4e [E
(2) 2 7/-
(5)
176
As discussed in Sect. 3.2, this problem can be conveniently optimized using a greedy strategy. We then integrate the optimization of (5) into an adaptive tree expansion strategy: (Generating new skills) Given a tree structure as described in Sect. 3.3, we expand the tree at a leaf w by adding No new nodes/skills following breadth-first-see first-searchh approach (lines 1, 2). Then (Skill Learning) the
178
179
180
new skills are optimized by: i) sampling random skills in the tree to update the discriminator (lines 7-11), and ii) by updating the policies to optimize the discriminability reward (Sect. 3.1) computed
182
using the discriminator (lines 13). To speed-up convergence, we only update the policies that have be added to the tree structure, keeping all the previous policies fixed (line 12). Note that in the update of the discriminator we leverage the states observed in previous phases of the algorithm by maintaining (small) replay buffer of states for each skill. (Node Consolidation) After a patience period (line 6), if all skills are p-consolidated, we tentatively add more skills to the leaf w (line 18). On the other hand, if any skill does not meet the discriminability threshold, we remove it and consolidate the remaining skills into the tree (lines 16, 17) and we repeat the process.
183
184
185
186
187
188
Model selection. A core aspect of any RL algorithm is model selection, i.e., finding the best configuration of hyperparameters. In URL with no prior knowledge of the downstream task(s), it non-trivial to devise an adequate criterion for model selection and this aspect is rarely addressed, despite being crucial in practice. For instance, while the coverage of the state space may be a good proxy for the performance of URL algorithm [see e.g., 8], it may be difficult to measure in continuous problems, Interestingly, our optimization problem directly provides a single, task-agnostic and environment-agnostin criterion for model selection, which is the number N of n-consolidattd skills discovered by the agent. Indeed in all of our experiments we simply select the model (i.c., set of hyperparameters) that maximizes N. This is significant advantage w.r.t. existing methods, such as VIC and DIAYN, for which no principled approach to model selection is provided.
190
181
192
193
194
195
196
197
198
4
Related work
199
Unsupervised Reinforcement Learning methods can be broadly decomposed according to the way they summarize the experience accumulated during the unsupervised phase into reusable knowledge to solve downstream tasks. This includes both off-policy model-free [e.g., 27] and model-basee [e.g., 29] methods that seek to populate a representative replay buffer and build accurate value or
201
202
203
204
model estimates, that are used solve given downstream task in zero- few-shot manner.
205
The accumulated experience during train time can also be compressed into low-dimensional representation for value functions as well as policies and to improve exploration [c.g., 36]. An alternative line of work focuses on the discovery of a set of skills in an unsupervised manner. Our approach falls in this category, on which we now focus our related work review.
208
207
208
Skill discovery based on MI maximization was first proposed in VIC [11], where only the final states of each trajectory are considered in the reverse form of (1) and where both the skills and their sampling rules are simultaneously learned (with a fixed support [Z]. i.e., fixed number of
210
211
212
skills). DIAYN [9] fixes the sampling rule to be uniform, and weighs the skills with an action-entropy
213
coefficient (i.e., it additionally minimizes the MI between actions and skills given the state), so as
214
to push the skills away from each other and enhance coverage. DADS [30] learns skills that are not only diverse but also predictable by learned dynamics models, by using a generative model over observations (rather than over s skills) and optimizing a forward form of MI, namely 2(s)) between
215
216
217
the next state s' and current skill z (with continuous latent) conditioned on the current state s. EDL [8] shows that existing skill discovery approaches can provide insufficient coverage, and instead proposes
218
219
to rely on a fixed distribution over states p(s) which is either provided by an oracle or learned. In
220
SMM [19], the MI formalism is used to learn policy for which the state marginal distribution matches
221
a given target state distribution (e.g., uniform), which can be seen as a more scalable way of tackling
the problem of maximum entropy over the state space [15], and as way to encourage skills to go
223
through unknown state regions. Other MI-based skill discovery methods include [10, 14, 24, 5, 34],
as well as [35, 20] which investigate skill discovery in non-episodic settings.

---

UPSIDE
DIAYN
SMM
Figure 3: UPSIDE, DIAYN-curriculum and SMM-10 10 skills learned in a bottleneck maze (Top) and U-maze (Bottom). For both DIAYN and SMM report the stochastic execution of the learned skills and for UPSIDE we report the deterministic directed parts (that are composed) followed by the (stochastic) diffusing part, which is the same protocol used to evaluate coverage.
225 Our approach shares a similar motivation to prior MI-based works of targeting skills that are both directed and state-covering In particular, the decoupled structure introduced in Sect. 3.1 can be as a more suitable way to achieve the objective of improving the coverage of VIC as done in DIAYN and SMM, without compromising the directedness of the skills.
227
While most skill discovery approaches consider fixed number of skills, a curriculum with increasing number of skills studied in [1, 3]. Our discrininability constraint what enables skills to be composed along tree structure, which allows increases decreases the support of available skills depending on the region of the state space.
230
232
233
Recently, [37] proposed hierarchical RL method that discovers abstract and task-agnosti skills while jointly learning a higher-level policy which is trained to maximize environment reward. Our approach builds on similar promise of composing skills instead of resetting to 8g after each execution,
235
yet we articulate the composition differently, by exploiting the direct-then-diffuse structure to ground learned skills to the state space instead of being abstract.
237
238
In addition, approaches such as DISCERN [33] and Skew-Fit [27] learn goal-conditioned policy in an unsupervised way with an MI objective. As explained in [8, Sect. 5], this can be interpreted as skill discovery approach with latent Conditioning on either goal states or abstract latent skills forms two extremes of the spectrum of unsupervised RL. We target an intermediate approach, seeking benefit from the groundedness of the latent skill Z and the states S (and thus amenability to composition) of goal-conditioned RI., and from the reduced search space and sampling ease of skill-based RI.
240
S, i.e., where each goal state can define a different skill.
242
244
245
An alternative approach skill discovery builds on "spectral" properties of the dynamics of the environment. This includes cigenoptions [21, 22] and covering options [17, 18]. as well as the algorithm of [4] that builds discrete graph representation which learns and composes spectral skills.
246
247
Experiments
248
In this section, investigate the following questions: i) Can the adaptive tree structure of UPSIDE in- crementally cover an unknown environment while preserving directedness of the skills? ii) Following
250
the unsupervised phase, how UPSIDE be leveraged to solve goal-based downstream tasks?
252
report results on: a) Navigation problems continuous mazes, where actions represent the desired shift in x and y coordinates; b) A difficult instance of CartPole, where the cart starts with zero speed and the pole is oriented downside; e) The Reacher [32] problem using the MuloCo implementation
254
in Gym [7]. In all environments, the per-dimension action space is in [1].

---

Bottimeek Mare
U-Mare
0.8
0.8
UPSIDE
SMM-55
Corrrago
0.6
Conerage
0.0
SMM-110
DIAYN-50
0.4
0.4
DIAYN-10
DIAYN-curriculom
Random policy
0-
0.2
0.4
0.6
0.5
1.2
0
0.2
0.4
0.6
0.5
12
Ear ctoctins
-100
Eur cutetactions
109
Figure 4: Normalized coverage in U-maze and bottleneck.
We compare to different baselines. DIAYN-K, where K is fixed number of skills, is the original algorithm proposed in [9]. DIAYN-Curriculum is a variant where the number of skills is automatically tuned following the same procedure as in UPSIDE ensuring good discriminability. We also compare
257
259
to SMM [19], which is similar to DIAYN, but it includes an exploration bonus encouraging the policies
260
to visit rarely encountered states. In our implementation, the exploration bonus obtained by
261
maintaining multinomial distribution over "buckets of states" obtained by discretization, resulting in an computation-effciien and stable implementation that is more stable than the original VAE-based
262
283
method. UPSIDE and all baselines are implemented with Soft-Actor Critic (SAC) [13].
Unsupervised Phase. We run all methods until convergence. We then do model selection according to the criterion of either the final number of skills for UPSIDE and DurYN-curriculmm and the final average discriminability for DIAYN-K and SMM. To compute the coverage, we perform rollouts by first sampling a skill uniformly at random and executing its associated policy until termination. We discretize states into buckets (50 interval per dimension for mazes and 10 for control environments)
265
267
268
269
and report the proportion of buckets reached by each method as a function of the total number of
270
steps executed in the environment over multiple rollouts. Since only small portion of the discretized states can be reached, we normalize the coverage such that the best method obtains 1.
271
We consider two topologies of mazes with size (height and width) 50 such that exploration is non- trivial (i.e., a random policy is only able to cover a small part of the state space): a U-shaped maze and Bottleneck maze (which is harder version of the one in [8, Fig. 1] which is only of size 10 for the same action space). In Fig. 3 we show that UPSIDE succeeds in covering the near-entirety of the state space by creating tree of directed skills. Moreover, UPSIDE created directed skills with a low entropy, while the two baselines tend to create skills that are more stochastic. This is
273
275
277
278
particularly evident for SMM, due the state-entropy exploration bonus, that while it encourages broader coverage makes skills less directed.
279
In Fig. 4 report the coverage on the Bottleneck maze and U-Maze. For UPSIDE, executing skill corresponds to executing the directed part of all the "parent" skills in the tree and concluding with the diffusion part of the skill. SMM achieves better coverage than DIAYN thanks to the increased level of stochasticity (diffusion) of its skills. UPSIDE outperforms both by reaching regions of the environment that are not be achieved by other methods. Here, we plot UPSIDE with T = 10 and
281
283
285
H 10, but we found UPSIDE to be robust to these parameters as shown in the supplementary.
Results are similar in the CartPole problem (see Fig. 5) where UPSIDE (with T 20 and H = 20) obtains better coverage than baselines. On the other hand, in Reacher (see Fig. 5), DIAYN-50 outperforms UPSIDE in terms of coverage. This can be explained by the fact that, in this environment, highly stochastic skills provide a good coverage. Nonetheless, this comes at the cost of very low discriminability (rightmost plot), which suggests DIAYN-50 skills have poor directedness. On the other hand, UPSIDE (and DIAYI-curriculum) achieves much larger discriminability by removing redundant skills and favoring more directed policies.
287
289
291
293
Downstream Tasks, Following the unsupervised phase, UPSIDE has learned tree of skills. We now investigate how these skills are used to tackle downstream task. In that setting, we propose to use -bill-based approaches (i.e UPSIDE, DIAYN and SMM) in the following way: a) (exploration) first 295
294
we sample rollouts over the different skills. b) We then select the best skill based on the maximum cumulative reward collected and e) we fine-tune this skill to maximize the reward. We report results
297
on mazes (additional results are provided in the supplementary). We consider a sparse positive reward
8

---

Cartyde
Bondar
Boacker
UPSIDE
0.
C
1..0
DLAYS-40
DLAYX-10
DIAVN-earnnolo
5KJM
022
0.2
Randors policy
0.5
LG5
Tee
Earr
Eun
Figure 5: Normalized coverage in Cartpole (Left) and Reacher (Middle). (Right) Average discrim- inability of the skills during training in Reacher.
299
when reaching a particular defined goal." We consider goals at different distances from the initial sp, the further, the harder. Fig. 6 shows the learning curves obtained when fine-tuning the best skill for the different models and compare to a classical SAC algorithm where single policy is learned from scratch. DIAYN/SMM means we use the best state-covering policies between DIAYN and
300
302
303
SMM. For the "close" goal setting, both UPSIDE and DIAYN/SMM are able to learn to reach this goal
304
efficiently while SAC solves the task only for some of the training runs. Note that we do not show
305
DIAYN performance since it is lower than the SMM one. For the "far" goal setting, only UPSIDE learns
306
reach this goal. Obtained trajectories are illustrated Fig. 6.
U-Maae:: Vnkucwa
Goal
0.5-
Spoose rate
0.5
0.6
0.4
0.4
105
Borthoneck Miaee Uniturnm Clows Gool
Rotrbmeck Maon Unimoere Par Goal
0.5-
0.5
Sartoe nit
0.5
0..0
Sueeoo
0.1-
Inticraciioss
Euc
300
(Left): Learning curves for "short" distance and (Middle) Figure 6: "medium" distance goals. (Right): Learned policies after fine-tuning (Top) U-maze. (Bottom): Bottleneck maze.
UPSIDE DIAYN/SMM
SAC
Conclusion
307
308
We introduced UPSIDE, a novel algorithm for unsupervised skill discovery designed to trade off between coverage and directedness and develop tree of skills that be used to both perform efficient exploration of the environment and learn effective goal-directed policies. Natural venues for future investigation are: 1) The diffusing part of each skill could be explicitly trained maximize local coverage; 2) UPSIDE assumes good representation of the state is provided as input, it would be interesting pair UPSIDE with effective representation learning techniques tackle problems with high-dimensional input (e.g., image-based RL); 3) While UPSIDE is grounded on the solid principle of MI maximization, a more thorough theoretical investigation is needed explicitly link the optimization problem and its approximations to the downstream performance.
310
312
313
314
315
316
'Nticee that if the goal was known, the learned discriminator could be directly used to identify the most promising skill to fine-tune.

---

References
317
318
[1] J. Achiam, H. Edwards, D. Amodei, and P. Abbeel. Variational option discovery algorithms. arXiv preprint arXiv: Jl0.. 2018.
320
[2] M. Andrychowicz. D. Crow, A. Ray, Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin,
P. Abbeel, and W. Zaremba. Hindsight experience replay. In NIPS, 2017.
[] A. Aubret, L. Matignon, and S. Hassas. Elsim: End-to-end learning of reusable skills through intrinsic motivation. arXiv preprint arXiv:2006. /2903, 2020.
323
324
[4] A. Bagaria, J. Crowley, J. W. N. Lim, and G. Konidaris. Skill discovery for exploration and planning using deep skill graphs. 2021.
325
326
[5] K. Baumli, D. Warde-Farley, S. Hansen, and V. Mnih. Relative variational intrinsic control. arXiv preprini arXiv:2012.07822 2020.
327
328
[6] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An
evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
330
331
[7] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym, 2016.
332
333
[8] V. Campos, A. Trott, C. Xiong, R. Socher, X. Giro-i Nieto, and J. Torres. Explore, discover and learn: Unsupervised discovery of state-covering skills. In International Conference on Machine Learning, 2020.
335
336
[9] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2019.
337
338
[10] C. Florensa, Y. Duan, and P. Abbeel. Stochastic neural networks for hierarchical reinforcement learning. arXiv preprint
2017.
340
[11] K. Gregor, D. Rezende, and D. Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.0743 2016.
[12] S. Gu, E. Holly, T. Lillicrap, and S. Levine. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA), pages 3389-3396.. IEEE, 2017.
343
345
[13] Haarnoja, A. Zhou, P. Abbeel, and Levine. Soft actor-critic: Off- Off-policy maximum entropy deep reinforcement learning with a stochastic actor. CoRR, ftss/1801.01200 2018.
348
[14] S. Hansen, W. Dabney, A. Barreto, D. Warde-Farley, T. Van de Wiele, and V. Mnih. Fast task inference with variational intrinsic successor features. In International Conference on Learning Representations, 2019.
348
350
[15] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681 2681-2691, 2019.
351
[16] R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. De Turck, and P. Abbeel. Vime: variational information maximizing exploration. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1 1117-1125, 2016.
353
355
[17] Y. Jinnai, J. W. Park, D. Abel, and G. Konidaris. Discovering options for exploration by minimizing cover time. In International Conference on Machine Learning, pages 3130-3139. PMLR, 2019.
356
357
358
[18] Y. Jinnai, J. W. Park, M. C. Machado, and G. Konidaris. Exploration in reinforcement learning with deep covering options. In International Conference on Learning Representations, 2020.
359
360
[19] I. Lee, B. Eysenbach, E. Parisotto, E. Xing, S. Levine, and R. Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint 1rX 2019.
10

---

382
[20] K. Lu, A. Grover. P. Abbeel, and I. Mordatch. Reset-free lifelong learning with skill-space planning, arXiv preprint wrXiv:2012.035544 2020.
363
364
[21] M. C. Machado, M. G. Bellemare, and M. Bowling. A laplacian framework for option discovery in reinforcement learning. In International Conference on Machine Learning, pages 2295-2304. PMLR, 2017.
386
367
[22] M. C. Machado, C. Rosenbaum, X. Guo, M. Liu, G. Tesauro, and M. Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Representations, 2018.
389
370
[23] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):529 533, 2015.
371
372
373
[24] N. Modhe, P. Chattopadhyay, M. Sharma, A. Das, D. Parikh, D. Batra, and R. Vedantam. Ir-vic: Unsupervised discovery of sub-goals for transfer in rl. In Proceedings the Twenry- Ninth International Joint Conference Artificial Intelligence, IJCAI-20, International Joint Conferences on Artificial Intelligence Organization, 2020.
374
376
377
[25] S. Mohamed and D. J. Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. In Advances in neural information processing systems, pages 2125- 2133, 2015.
379
380
[26] M. Mutti, I.. Pratissoli, and M. Restelli. A policy gradient method for task-agnostic exploration. arXiv preprint arXiv:2007.000 0406000 2020.
381
382
[27] V. H. Pong, M. Dalal, S. Lin, A. Nair, S. Bahl, and S. Levine. Skew-fit: State-covering self-supervised reinforcement learning. In International Conference on Machine Learning, 2020.
384
385
[28] Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint 1tfi::1777.03444 2017.
[29] R. Sekar, O. Rybkin, K. Danillidis, P. Abbeel, D. Hafner, and D. Pathak. Planning explore via self-supervised world models. In International Conference on Machine Learning, pages 8583-8592. PMLR, 2020.
388
389
390
[30] A. Sharma, S. Gu, Levine, V. Kumar, and K. Hausman. Dynamics-aware unsupervised
381
discovery of skills. In International Conference on Learning Representations, 2020.
[31] D. Silver, J. Schrittwisser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, I.. Baker, M. Lai, A. Bolton, et Mastering the game of go without human knowledge. nature, 550(7676):354-3555
383
394
2017.
[32] E. Toooooov T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 50pou26-500 5033, 2012.
396
398
[33] D. Warde-Farles T. Van de Wiele, T. Kulkarni, C. Ionescu, S. Hansen, and V. Mnih. Unsuper- vised control through non-parametric discriminative rewards. In International Conference on Learning Representations, 2019.
389
400
401
[34] K. Xie, H. Bharadhwaj.
D. Hafner, A. Garg, and F. Shkurti. Skill transfer via partially amortized hierarchical planning. In International Conference on Learning Representations, 2021.
402
[35] K. Xu, S. Verma, C. Finn, and S. Levine. Continual learning of control primitives: Skill
404
discovery via reset-games. arXiv preprint arXiv:2011.05288 2020.
405
[36] D. Yarats, R. Fergus, A. Lazaric, and L. Pinto. Reinforcement learning with prototypical representations. arXiv preprint 2002. /2771 2021.
406
[37] Zhang, H. Yu, and W. Xu. Hierarchical reinforcement learning by discovering intrinsic options. In International Conference on Learning Representations, 2021.
408
11

---

Checklist
409
410
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
412
413
(b) Did you describe the limitations of your work? [Yes] We discuss the limitations and
414
directions of further investigation in the conclusion.
415
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not foresee any obvious negative societal impacts from our work, which focuses on the fundamentals of reinforcement learning and proposes a new algorithm for unsupervised skill discovery.
417
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
420
421
2. If you are including theoretical results...
422
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
425
(b) Did you include complete proofs of all theoretical results? [N/A]
424
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [No] We plan to release our code upon acceptance of this work.
426
428
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
429
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Yes when possible.
431
432
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
433
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new asstts...
435
(a) If your work uses existing assets, did you cite the creators? [Yes] See Sect.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
438
439
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
440
441
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
443
5. If you used crowdsourcing or conducted research with human subjects...
444
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
445
446
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
447
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
449
450
12


Reviews:
[{"review_id": "d-0SBLiVelP", "reviewer": "Reviewer_HknL", "summary": "The idea of this work is to maximize coverage while ensuring learned skills are distinguishable. The learning framework is based on maximizing mutual information (MI) between latent random variables and states. \nThis paper proposes a decoupled objective for local coverage and directness, on top of it, a tree structure based exploration method is proposed to incrementally compose learned skills for maximum coverage.", "questions": "", "limitations": "", "rating": 5, "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": "While the problem studied in this work is important, there are several issues with clarity and novelty.\n\nThe authors need to define what is the length of “skill” before referring it.\n\nThe motivation of using the constrained optimization formulation for H(z) - H(z|s) (eq 3 and eq 4) should be elaborated more.\n\nIn introduction the objective seems to maximize H(s) - H(s|z) which aligns with its maximizing coverage motivation, but then in the method section, the objective becomes H(z) - H(z|s) which does not encourage explicit exploration, see EDL[Campos et al] and APS [Liu & Abbeel].\n\nAlso, EDL is a very related baseline, and should be discussed and compared in terms of methodology and experiments. EDL firstly optimize H(s) then use the data to optimize -H(s|z), which is closely related to this work. In fact, this work conducted experiments in 2D maze with the same topology as in EDL. I suggest the authors to compare their method against EDL.\n\n------------------------ \n\nAfter reading the response from the authors, I am rising my score from 4 to 5.\nAs mentioned in the reply to the author response, while I tend to reject it, my score merely reflects the current status of the paper, with additional experiments in more convincing environments and downstream task fine-tuning, I think this work can be a strong paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "F-2aiKH_PxC", "reviewer": "Reviewer_1Gri", "summary": "This method learns a space of intrinsic goals to maximize coverage of the state space. This work utilizes mutual information between skills and states, where the entropy of states and negative entropy of states given options describe the diffusing and directing objectives respectively. This is done by learning skills with two separate parts, a long scale directed component and a short scale diffusing component. These skills have state distributions that differ by at least a specified factor. It then separates these skills along a hierarchical tree structure, where temporal abstraction occurs by calling lower level options, which have a limited range, controlling the shape of the tree by pruning skills with low difference, and adding new skills when all the skills satisfy the condition. ", "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": "Abstract: the abstract is somewhat confusing in that it is not clear whether the skills learns are diffusing or directed, or how that separation is made, since it is difficult for them to be both at once. \n\nIntroduction:\n25 Unsupervised RL seems like an unusual phrase. Intrinsic rewards, exploration or unsupervised policy learning seem more descriptive. Reinforcement learning is defined by a reward function, distinct from supervised learning.\n\nFigure 1 is fairly useful, but the description is somewhat verbose and between pictures it is not clear whether skills are being pruned or added, especially between image B and C / D and E.\n\n42 Maximizing 1 does not encourage exploration in RL, though learning options which maximize 1 does tend to produce options which cover the space more fully. \n\n58 From the introduction, it is still not clear how the tree structure is used and how it differs from the skill structure. \n\nSetting:\nIt is not clear that a MDP is still an MDP without reward. This would just be an environment that exhibits Markovian dynamics. This is just a semantic issue, though.\n\nEquation 1: While both forward and backward MI are mathematically equivalent, it is not clear from this section which one is more relevant for an intuition of this task. It seems like the first would be, however, since it better describes the diffuse and directed properties.\n\nAlgorithm Structure:\n96,97,99 Note that the use of H(S), -H(S|Z) describe the forward form of mutual information, however p(z|s) is then used to describe the discriminability of a skill, but is from the reverse description of mutual information. This switching can be confusing. \n\nEquation 2: While it makes mathematical sense that the minimum skill is less than the average, it is not entirely clear what a minimum level of discriminability is. In this case, it seems like intention of this lower bounding is to say that the loss is based on how discriminable the least distinct skills is.\n\nEquation 3: It is also not clear how Equation 2 leads to Equation 3. While it makes sense to optimize over the number of skills, and complete the mutual information term, this is a consequence only after combining with Equation 1. It would be useful then to specify this. \n\n135 This use of \"convenient formulation\" is unclear. This is used because maximizing over a cardinality of skills is an integer program, and thus using a greedy algorithm is the classic solution to such a problem.\n\nIn the final case, the skills are simply learned such that they exhibit better than \\log \\eta entropy over the states that they cover. It seems appropriate to relate this to clustering because this seems to have parallels to a kind of minimum distance coverage metric that might be used in that case. \n\n3.3 It seems like the tree structure and how the composition works is integral to this work, but is only discussed in a limited manner. How nodes are chosen to be expanded upon and how an agent would navigate the tree seems like immediate questions.\n\n3.4 While prior work has described how the discriminator q_\\phi(z|s) is optimized, it is not entirely clear when reading this section what feedback is used to train the discriminator. This makes the description of the different steps confusing, since they simply assume that the discriminator reward performs well. \n\nThe pruning and growth method for skills in the tree is mentioned only briefly, and seems as though it requires a good number of hyperparameters to manage. \n\nRelated work: \nFrom a formatting perspective, it would be best to separate the related work by category, especially since this work is primarily only interested in comparison with the line of work doing skill discovery based on mutual information. This is because this work tests only on the navigation domain used to visualize coverage, and uses the same language as these related methods.\n\nExperiments:\nWhile this method appears to perform substantially better than the existing methods, one weakness is that is does not compare with other methods which tend to escape some of the bottlenecks. In particular, though Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills is mentioned, and shown to get much better coverage by greater directedness, it is not compared against.\n\nWhile the illustrations in Figure 3 are promising, it is worth noting that the performance of such exploration on high dimensional tasks has a much different characteristic. In particular, high dimensional states will take much longer to perform the dense coverage exhibited by the UPSIDE algorithm. This seems to limit the scope of results given (though most methods in this domain appear to struggle with this as well).\n\nThe diffusing component is not always tested in this method. For example, in the case where there would be a narrow bottleneck, it seems like the diffusing criteria could cause a skill that enters the bottleneck to fail because it cannot diffuse due to constraints in the environment. None of the experimental cases appear to test this possibility, but in many practical applications there are situations where this property is at play.\n\nOne ablative that seems important based on the results is to observe the level of effect of composing options. Since it seems like many of the other methods fail to escape the bottlenecks near the start, it seems like this difference is actually the primary advantage by comparison. \n\nOverall, this work proposes a new and interesting way to define a set of skills that maximizes coverage over a space while keeping the skills distinct. The work build a novel framework of option composition and provides an alternative way to choose options---based on the worst differentiable option, which is interesting. Though it compares against methods which do not perform as well as other in the same domain, it does demonstrate encouraging results. However, the domain limits the scope of these results from many practical applications. Some missing components in the description and the equations does obfuscate exactly what the algorithm is doing.\n\nOriginality: decent\n\nQuality: good\n\nClarity: marginal\n\nSignificance: marginal", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work does not discuss limitations or societal impact. A discussion of how exploration could affect modern navigation methods, whether in maps, robot movement, etc, could have occurred. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "CXucrDSGct1", "reviewer": "Reviewer_tU7w", "summary": "The authors propose a novel skill discovery method that combines standard mutual information maximization with notable changes. The first is that skill now enter a diffusion stage (random actions) before being predicted by a reverse predictor. The second is that environmental resets are exploited in order to construct a skill tree, wherein new skills are executed only after their parent skills. The final change is a pruning/growth strategy similar to VALOR, which is critical for constructing the skill tree.\n\nThe authors evaluate their method by comparing it to traditional skill discovery methods in terms of state coverage and performance on downstream tasks. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Overall, I really like this idea as well as its execution. The tree structure and separate diffusion process tie together nicely (i.e. no diffusion until leaf node), and the qualitative results are very strong. But there are a few things stopping me from a stronger acceptance recommendation.\n\nThere are two critical ablations that are missing. The first is to run UPSIDE without the diffusion stage (likely requiring retuning the action entropy bonus) to see how necessary it truly is. The second is to run UPSIDE without the tree structuring. My hypothesis is that the diffusion stage is only necessary with the tree structure, as it prevents stochasticity from hurting the ability to reach leaf nodes, though perhaps just executing the deterministic policy with otherwise high action entropy bonus would be sufficient. In particular, I don't buy the claim on line 121 that direct-then-diffuse is qualitatively different from direct-with-action-entropy, since e.g. the policy could just be super stochastic after becoming predictable -- effectively replicating the direct-then-diffuse behavior while maintaining the ability to utilize other strategies (e.g. don't randomly take an action that kills you).\n\nIn addition, your baselines would be a lot more impactful if you swept over skill duration. UPSIDE can chain together skills, which allows for its impressive performance on e.g. unknown far goal, but perhaps DIAYN could also achieve this with sufficient skill duration.\n\nOne final point is that the claim on line 198 that VIC/DIAYN don't have an unsupervised model selection criteria is simply untrue. Its just the value of the lower-bound e.g. E[ log p(z) - log q(z | s) ]. Indeed exponentiating this even gives a value for the effective number of skills, which is more readily interpretable than UPSIDE's actual number of skills, since those won't all be perfectly interpretable. Of course, this criteria could easily be used by UPSIDE as well, and UPSIDE has enough other advantages to offset the loss of this contribution.\n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Environmental resets are mentioned, but should also be addressed as a limitation. Other skill discovery methods can easily be extended non-episodic environments (e.g. compare DIAYN to VISR), but UPSIDE relies heavily on this ability in order to establish a root node for its tree. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0hgyKTujEKK", "reviewer": "Reviewer_guNm", "summary": "The paper presents a framework for an unsupervised learning of robotic skills that balances directness of exploration and coverage of state space. The theory of the method builds on the notion of mutual information between states and skills, where the conditional entropy between states and skill definitions corresponds to the directed part of the learned policy, and entropy of the states to the diffusing part of the policy. The directed part is optimized to increase discriminability of the skills given the states using a discriminator network. The diffusing part performs a random walk policy with uniform distribution over actions.The paper further proposes to optimize the number of skills by requiring the minimum discriminability of skills and discarding skills that fall below the discriminability threshold. Finally, in order to be able to reach states that are farther away, the paper proposes to combine skills in a tree structure and gradually expand the tree by adding new skill nodes to the tree. The approach is shown to outperform other unsupervised skill discovery methods on such tasks as continuous maze, CartPole and Reacher in OpenAI Gym during both, unsupervised skill discovery phase and training of downstream tasks.", "questions": "", "limitations": "", "rating": 6, "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- Exploration and skill discovery is crucial for scaling up robot learning. Optimizing for both directness and exploration through mutual information between states and skills is an elegant way to acquire a wide variety of skills.\n- The paper is well-written, and straightforward to understand and follow.\n- The method is shown to discover a wider variety of skills and provide a better coverage of the state space than previous methods.\n\nCriticism\n- As discussed in the paper, and also visible in Fig. 3, the proposed method pushes the trajectories of different skills apart to increase their discriminability. Using a pre-defined minimum discriminability threshold might result in gaps in the state coverage, which can lead to low performance on tasks that require varying granularity of control, e.g. some manipulation tasks in robotics. It would be interesting to see a discussion how the method could deal with such tasks and ensure an appropriate state coverage.\n- It would be useful to see more details about the skill latent variable z, in particular how it is constructed and its dimensionality.\n- Experiments on downstream tasks assume that there is already a skill that is close to the new task and can be fine-tuned. It would be interesting to see a discussion how the method would deal with problems where combination of multiple skills is required.\n- As also indicated in the paper, it would be interesting to see experiments on higher-dimensional problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed limitations of their work. The proposed approach does not lead to any obvious negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers found the proposed method interesting and early results promising, but ultimately the current set of experiments feel unfinished and fall short of acceptance. First, only a few relatively simple environments are currently considered. Reviewers felt that it is important to see UPSIDE succeed in more challenging environments that have been used for skill learning, e.g. Hopper, Ant, or Walker in Mujoco. Second, two important ablations are missing - the removal of the diffusion stage, and the remove of the tree structuring of skills. While the authors claim both are important for their method, it is important to demonstrate this to readers. With these two (relatively simple) issues addressed, I expect UPSIDE will be a worthy contribution to the community.
Decision: Reject