A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process
Authors: Jiayu Chen
Vaneet Aggarwal
Tian Lan
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Unsupervised Skill Discovery
Determinantal Point Process
Options

Abstract: Learning rich skills under the option framework without supervision of external rewards is at the frontier of reinforcement learning research. Existing works mainly fall into two distinctive categories: variational option discovery that maximizes the diversity of the options through a mutual information loss (while ignoring coverage) and Laplacian-based methods that focus on improving the coverage of options by increasing connectivity of the state space (while ignoring diversity). In this paper, we show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. To be specific, we explicitly quantify the diversity and coverage of the learned options through a novel use of Determinantal Point Process (DPP) and optimize these objectives to discover options with both superior diversity and coverage. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari. The results demonstrate that our algorithm outperforms state-of-the-art baselines in both diversity- and coverage-driven categories.

A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process
Jiayu Chen Purdue University West Lafayette, IN 47907 chen3686@purdue edu
Vaneet Aggarwal Purdue University West Lafayette, IN 47907 vaneet@purdue edu
Tian Lan
The George Washington University Washington, DC 20052 tl 1lan@gwu.edd edu
Abstract
Learning rich skills under the option framework without supervision of external rewards is at the frontier of reinforcement learning research. Existing works mainly fall into two distinctive categories: variational option discovery that maximizes the diversity of the options through a mutual information loss (while ignoring coverage) and Laplacian-bies based methods that focus on improving the coverage of options by increasing connectivity of the state space (while ignoring diversity). In this paper, show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. To be specific, we explicitly quantify the diversity and coverage of the learned options through novel use of Determinantal Point Process (DPP) and optimize these objectives to discover options with both superior diversity and coverage. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari. The results demonstrate that our algorithm outperforms state-of-the th- baselines in both diversity- and coverage-drivee driven categories.
Introduction
Reinforcement Learning (RL) has achieved impressive performance in a variety of scenarios, such rely on in real-life scenarios often with sparse or no rewards. To this end, utilizing unsupervised option discovery acquiring rich skills without supervision of environmental rewards by building temporal action-sequence abstractions (denoted as options), to support efficient learning can be essential. The acquired skills not specific to a single task and thus be utilized to solve multiple downstream tasks by implementing a corresponding meta-controller that operates hierarchically on these skills.
as games [ 22 robotic control [ 4), and transportation [5] 6). However, most its applications
task-specific rewards to drive exploration and learning, limiting its use
Existing unsupervised option discovery approaches broadly fall into two categories: (1) Variational option discovery, e.g., 778 9 which aims to improve diversity of discovered options by maximizing
the mutual information 10 between the options and trajectories they generate. It tends to reinforce already discovered behaviors for improved diversity rather than exploring (e.g., visiting poorly- connected states) to discover new ones, so the learned options may have limited coverage of the state space. (2) Laplacian-
option discovery, e.g., [II 12], which clusters the state space using a Laplacian spectrum embedding of the state transition graph, and then learns options to connect different clusters. This approach is shown to improve the algebraic connectivity of the state space 13 and reduce expected covering time during exploration. However, the discovered options focus on improving connectivity between certain clusters and thus could homogeneous and lack diversity. Note that coverage in this paper is defined as property with respect single option, which can be measured as the number of state clusters traversed by an option trajectory. By maximizing coverage
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

2626e
(b)
Dharsd
GG
(0)
90
Figure 1: Illustrative example. (a) Options from variational methods have good diversity but poor (single-option) coverage of the corridors, (b) Each option from Laplacian-based methods aims to improve its coverage by visiting poorly-connected corner states but tends be homogeneous the others. (c) Options from our proposed method have both superior diversity and coverage. (d) The coverage and diversity measure of the options (a)-(c) defined with DPP (i.e., Eq.(7 and
of each single option and diversity among different options in the meanwhile, the overall span of all options can be maximized. However, diversity and coverage may not go hand-in-hand in option discovery, visualized in Figure (b)). Attempts such as [14 15 have been made to address this gap, but they rely on expert datasets that contain diverse trajectories spanning the whole state spaces and lack an analytical framework for diversity and coverage of the discovered options.
This paper introduces novel framework for unsupervised option discovery by utilizing Determinantal Point Process (DPP) to quantify and optimize both diversity and (single-option) coverage of the learned options. A DPP establishes a probability measure for subsets of set of items. The expected cardinality, representing the average size of random subsets drawn according to the DPP, serves as diversity measure, as reflects the likelihood of sampling diverse items and the number of distinct items in the set. First, to enhance option diversity, we apply DPP to the set of trajectories for different options. Maximizing the expected cardinality under this DPP encourages agents to explore diverse trajectories under various options. Second, we create another DPP for the set of visited states in trajectory and maximize its expected cardinality. This prompts the agent visit distant states from distinct state clusters through each trajectory, leading to higher single-option coverage. As shown Figure dd), these objectives effectively measure diversity and coverage the options. Lastly, to establish the option-policy mapping and so learn multiple options simultaneously. we maximize the mutual information between the option choice and related trajectories, as in variational option discovery. Rather than using the whole trajectory [16] or only the goal state [7]. our solution extract critical landmark states from a trajectory via a maximum a posteriori (MAP) inference of DPP, allowing noise mitigation while retaining vital information. In conclusion, our proposed framework unifies diversity and coverage in option discovery using a mathematical modeling tool-DPP. Our key contributions
follows. (1) To the best of our knowledge, this is the first work to adopt DPP for option discovery.
(2) The proposed unified framework enables explicit maximization of option diversity and coverage, capturing advantages of both variational and Laplacian-based based methods. (3) Empirical results on a series of challenging RL tasks demonstrates the superiority of our algorithm over state-of-the-art (SOTA) baselines.
Background and Related Works
2.1 Unsupervised Option Discovery
As proposed in [77, the option framework consists of three components: an intra-option policy :: T A [0, 1]. termination condition / : + {0, 1}, and an initiation set / S S. An option < 1, 3 > is available in state s if and only if E I. If the option is taken, actions are selected according to ı until it terminates according to 3 (i.e.. 3 1). The option framework enables learning and planning at multiple temporal levels and has been widely adopted in RL. Multiple research areas centered on this framework have been developed. Unsupervised Option Discovery aims at discovering skills that are diverse and efficient for downstream task learning without supervision from rewards, for which algorithms have been proposed for both single-agent and multi-agent scenarios 20 21. Hierarchical Reinforcement Learning [22 23 and Hierarchical Imitation Learning 25 26 on the other hand, aim directly learning a hierarchical policy incorporated with skills, either from interactions with the environment or expert demonstrations.
18
19
24

---

We focus on single-agent unsupervised option discovery. One primary research direction in this field is variational option discovery, which aims learn latent--onditioned option policy ([aas c). where e. represents the option latent. Diverse options can be learned by maximizing the mutual information between the option choice e and the trajectory generated by the policy conditioned on c. As shown in (271, this objective is equivalent to Variational Autoencoder (VAE) [2]. Variational option discovery can be categorized into two groups based on the structure of the VAE used: (1)
Trajectory-first methods, such EDL 14 and OPAL [3), follow the structure _ c D,
Here, represents the agent's 's trajectory, while D and E denote the VAE's decoder and encoder, respectively. In this case, the policy network x <aass, c) serves as the decoder D. The effectiveness of these methods rely on the quality of the expert trajectory set used as the encoder's ss input. For instance, OPAL employed for Offline RL [29] assumes access to a trajectory dataset generated by a mix of diverse policies starting from various initial states. Similarly, in EDL., highly-efficient exploration strategies such as State Marginal Matching [16] are utilized to simulate perfect exploration and obtain a set of trajectories (7) with good state space coverage for option learning. (2) Option-fine -frstt methods,
such as VIC 77.. DIAYN B. VALOR (27), and DADS 19). follow the structure c _ T D. c and learn TTal s.c) as the encoder E. Unlike EDL and OPAL learning from "exploration experts", these methods start from a random policy to discover diverse options. However, due to challenges in exploration, they fail to expand the set of states visited by the random policy, leading poor state space coverage. For instance, in Figure Ta), though trajectories of different options are diverse, none of them explore the corridor. There have been more notable advancements in variational option discovery methods, as cited in [30 31 32
35). A detailed comparison between these methods 33 34 and our algorithm, highlighting our contributions, can be found in Appendix
In this paper, we tackle a more challenging scenario where the agent must learn to identify diverse options and thoroughly explore the environment, starting from a random policy. This approach supports self-driven learning and exploration, rather than relying on expert policy/trajectories like trajectory-firy methods. We achieve this by integrating the variational method with another key branch in unsupervised option Laalovvrr--aallaiaaan---a is based on the Laplacian spectrum of the state transition graph, which can be estimated using state transitions in the replay buffer. The state transition graph and its Laplacian matrix are formally defined in Appendix I. Specifically, the approach presented in [12] first estimates the Fiedler vector - the eigenvector associated with the second smallest eigenvalue of the Laplacian. Options are then trained connect states with high and low values in the Fiedler vector. These states are loosely connected by "bottleneck" states. By connecting them with options, the algebraic connectivity of the state space enhanced, and thus the exploration can be accelerated [13] However, these options may be homogeneous. For instance, in Figure (b), multiple options are found to explore the right corridor. but they all follow the same direction given by the Fiedler vector. Inspired by variational and Laplacian-basee methods, we propose a new option discovery framework that unifies the optimization of diversity and coverage, through a novel use of DPP. As shown in Figure Ic), multiple diverse options are discovered, most of which traverse the "bottleneck" states to enhance coverage.
option discovery [1] 12 This approach
[igure[[b),
2.2 Determinantal Point Process
According to [36, given a set of items W (wi,... ",,,,, measure on the set of all the subsets of W. P is called a Determinantal Point Process (DPP) if a random subset W drawn according to P has probability:
). a point process P on W is probability
det(Lw)
det(Lw) del +
PL(W) = W) = Ew'ew (Lw.)
(I)
I E N is the identity matrix. L= L(W) E NNN is the DPP kernel matrix, which should be symmetric and positive semidefinite. Lw E | is the sub-matrix of L indexed by elements in W. Specifically, (W (w:)) x Li and PL(W = {w,, w/}) x LuLii L3 where Lif measures the similarity between item i and j. Since the inclusion of one item reduces the probability of including similar items, sets consisting of diverse items are more likely to be sampled by a DPP.
The DPP kernel matrix L can be constructed as a Gram Matrix 37 L = B Diag(
B
Diag( )) q' lg....., ,Nvl E RN with q. 2 0 denotes the quality measure. B
b
D is the stacked feature matrix where by RR is the feature vector corresponding to w. The
3

---

inner product of feature vectors, e.g., b, b is used the similarity measure between items in W. From Eq. ① we can see that PL(W= = w) is propotional to the squared [W| --dimensionn volume of the parallelepiped spanned by the columns of B corresponding to the elements in W. Diverse sets have feature vectors that are more orthogonal and span larger volumes, making them more probable.
b,
The expected cardinality of samples from a DPP is an effective measure of the diversity of W and reflects the number of modes in W (38). We provide detailed reasons why we choose the expected cardinality instead of the likelihood in Eq. ①I as the diversity measure in Appendix C.T According to (36), the expected cardinality of set sampled from a DPP can be calculated with Eq. (2). where A is the i-th eigenvalue of L(W). DPPs have found applications across a wide array of domains to promote diversity due to their unique ability model diverse subsets, such information retrieval
39 40 computer vision (88. natural language processing [4] 42], and reinforcement learning This motivates us to employ DPPs skill discovery for diversity enhancement.
N
E W-PLIW)
[W]
Σ
(2)
+1
3 Proposed Approach
In this section, we propose a DPP-based framework that unifies the variational and Laplacian- option discovery get options with both superior diversity and coverage. As discussed in Section 2.1 defining an option requires relating it to its initial states 8p, specifying its termination condition, and learning the intra-option policy. Our algorithm learns prior network (c(so) to determine the option choice c E C at an initial state, and an intra-option policy network aa(a) 88, c) to interact with the environment using a certain option for a fixed number of steps (i.e., the termination condition). With Pw and Te, we can collect trajectories 7 = (so, 4o 8T) corresponding to different options.
In Section 3.1, we propose C lower bound for the mutual information between the option and the landmark states in its trajectory, inspired by variational option discovery. By introducing the conditional variable and maximizing L we establish the option aption-policy mapping and learn multiple options simultaneously. Each option can generate specific trajectories. However, the mutual information objective only implicitly measures option diversity the difficulty of distinguishing them via the variational decoder, and does not model the coverage. Thus, in Section (..2] we additionally introduce explicit coverage and diversity measures based DPP as objectives. In particular, LPP/ measures single-agent coverage as the number of landmark states traversed by an option trajectory. Maximizing this metric encourages each option cover broader area in the state space. Notably, CPPP generalizes the popllciia--baede option discovery objectives by employing the Laplacian spectrum as the feature vector construct the DPP kernel matrix. CPPP measures the diversity among trajectories of the same option. By minimizing it, the consistency these trajectories can be enhanced. CPPP measures the diversity among trajectories corresponding to different options. which should be maximized to improve the diversity among various options. The rationale behind introducing CPPP is to maximize both the coverage of each individual option and the diversity among various options. By doing so, we can maximize the overall span of all options, thereby fostering the formation of diverse skills that fully explore the state space.
3.1 Landmark-based Mutual Information Maximization
Previous works tried to improve the diversity of learned options by maximizing the mutual information between the option choice and trajectory - 227 or goal state sT (46] generated by the corresponding intra-option policy. However, the whole trajectory contains noise and the goal state only cannot sufficiently represent the option policy. In this paper, we propose to maximize the mutual information between e and landmark states G in T instead. G is a set of distinct, representative states. Specifically, after clustering all states according to their features, diverse set of landmarks with varied feature embeddings is identified to represent each different cluster. Notably, G can be extracted from t through the maximum a posteriori (MAP) inference of a DPP (36), shown as Eq. {3) where X' denotes the set of states in т. The intuition is that these landmarks should constitute the most diverse subset of X' and thus should be the most probable under this DPP.
G = arg max PLAX (X X)= = arg max P(X X I(2)) arg max del(Lx) XCX
(3)
XCX
XCx det(L L + IT)
4

---

In order to maximize the mutual information between G and while filtering out the redundant information for option discovery in 7. According to the Information Bottleneck framework [47] this
can be realized through Eq. {4. where su(-) is the initial state distribution, T(.) denotes the mutual information, and Ta is the intormation constraint.
max E [cc, G|so; w)), s.t., [c,, T(s0: 0,w) S let 0ww
somp(()
Equivalently, with the introduction of a Lagrange multiplier 3 2 0, we can optimize:
max 8,w
E
[I G|so; 0, - So; 8 w)]
(5)
spm=p(-))
is infeasible to directly compute and optimize Eq.
5
so we have the following proposition.
Proposition 1. The optimization problem as Eq. 5 can be solved by maximizing L (w. 0, o):
H(C(s) + E 40.077
[ (GI7) log Palclso. G) B B
e) [Unis(r|so))
(6)
#0.0
Here, 8o p(()),~~ Pu((1so), Po(-|so: c). H(C represents the entropy associated with the option choice distribution at a given state. PDPP(GIT) = dct dct(La)/ det(L [ T) is the probability of extracting G from t, under a DPP the set of states in Po(c) so, G) serves as variational estimation of the posterior term P(c|so, G) in [c, G) (T(so) denotes the probability of sampling trajectory given so under a uniformly random walk policy.
The derivation can be found in Appendix A.2 (1) The first two terms of Eq. (6) constitute a lower bound of the first term in Eq. ( H(CTS) and Pa(ciso, G) can be estimated using the output from the prior network and variational posterior network, respectively. (2) The third term in Eq. (6) corresponds
lower bound of the second term in Eq. (5). Instead of directly calculating 31 T ( which is implausible, we introduce f (o)) to convert it to regularization term as which the KL Divergence 10 between the distribution of trajectories under our policy and random walk policy, exploration of the trained policy Te can be improved. Note that Po (T c) IIroo To (o az), where P( az) is the transition function in the MDP.
in Eq. 66. Specifically, by minimizing DK (Po
Another challenge in calculating " is to infer the landmarks G with Eq. (3.. (L is the kernel matrix of the DPP, of which the construction further introduced in the next section.) The MAP inference problem related to DPP is NP-hard 48. and greedy algorithms have shown to be promising as a solution. this work, we adopt the fast greedy method proposed in (39 for the MAP inference, which is further introduced in Appendix C.2 with its pseudo code and complexity analysis.
3.2 Quantifying Diversity and Coverage via DPP
In this section, we propose three optimization terms defined with DPP explicitly model the coverage and diversity of the learned options. Jointly optimizing these terms with Eq. (6). the discovered options are expected to exhibit improved state space coverage and enhanced diversity.
The first term relates to improving the coverage of each option by maximizing:
T+1
x +
CP CPPP (w, 0) = E Σ
Pulcss))
f(F) = E X-PL(X)
|X| = Σ
(7)
C.T
where X' is the set of states in L(x') is the kernel matrix built with feature vectors of states in X, f(r) is the expected number of modes (landmark states) covered in trajectory т. Thus, CPPP measures single-option coverage, by maximizing which we can enhance exploration of each option.
As for the kernel matrix, according to Section 2.2 can construct L(X') by defining the quality measure o and normalized feature vector for each state in X. States with higher expected returns should be visited more frequently and thus be assigned with higher quality values. However, given that there is no prior knowledge on the reward function, we assign equal quality measure to each state as 1. As for the features of each state, we define them using the Laplacian spectrum, i.c. eigenvectors corresponding to the D-smallest eigenvalues of the Laplacian matrix of the state transition graph, denoted as [ .... TD). To be specific, for each state s, its normalized feature is defined as:
b. (s) = (s). ())) (1) As shown in Spectral Clustering (49. states with high similarity in this feature embedding fall in
(s)) The reasons for this feature design are as follows:
5

---

Algorithm 1 Unsupervised Option Discovery based on DPP (ODPP)
1: Initialize the prior network Pw, policy network Te, variational decoder Pa. and trajectory set 7
2: for each training episode do
3: i 1, ..... do
4: Sample si sa(-) and e ~ (-(())))) or use the ones from the previous episode to collect
trajectories subject to the same option and starting point
5: Collect trajectory T; (s), ag. sT-1 11 sty), where af ~ aee c)
6: 7
7: end for
8: Update Pa,, Ta with PPO and P. with SGD, based 7 and Eq.
13
7 0
9:
end for
the same cluster. Under a DPP with this feature embedding, the sampled states with distinct features should belong to different clusters, i... the landmarks. Then, by maximizing CPPP (i.e., the expected number of landmarks covered in 2²,, the agent is encouraged to traverse multiple clusters within the option discovery 122 In [12), they set a threshold to partition the state space into two parts the set of states with higher values in the Fiedler vector (i.e., 02) than the threshold is used as the initiation set and the other states are used as the termination set, then the option policy is trained to connect states within these two areas. We note that, as a special case our algorithm, when setting the feature dimension D 2, we can get similar options with the Laplacian-based methods through maximizing CPPP. Given that the eigenvector corresponding to the smallest eigenvalue a Laplacian matrix is Ui = itstee with diverse feature embeddings encoded by [ T5) (i.e., D = 2) tend to differ in 2z2 distinct in 75 as possible
state space. (2) With this feature design, our algorithm generalizes of the Laplacian-
By maximizing LPPP, the options trained to visit the states that in a trajectory, which is similar with the ones learned in [2]. We empirically demonstrate this in Section 4 Note that the Laplacian spectrum /v/... TDl for infinite-scall state space can be learned
as neural network through representation learning (50) which is introduced in Appendix C.3 Thus,
our algorithm can be applied tasks with large-scale state spaces.
Next, we expect the set of sampled trajectories related to the same option e and starting from the same state so, i.e., 7 c)) to be consistent and thus hard to be distinguished by DPP, which is important given the stochasticity of the policy output. This is realized by minimizing the expected
mode number in each 7 (so:e); (5p ~ u(.), Pa(-(8o), 7 (so.c) Po Po(-1so,0) c))
M
N
C2 CDPP (w,
[o( ((F()))))) g( (en.))
E Y~PPTO)
|
(8)
+1
#0,0, (*0)n)
where J' is the set of M trajectories related starting so (i.e., [TI,... TM
()) L())
the kernel matrix built with the feature vectors of each trajectory, i.e., b(T,). The feature vector of a trajectory can be obtained based on the ones of its landmark states G; through the Structured DPP framework [5I]: b(T.) = =EEEG, b(s). (b(s) is defined above.) Alternatively, we can use the hidden layer output of the decoder Po so). which embeds the information contained in G. This design is commonly adopted in DPP-related works [52 (33. We will compare these two choices in Section 4 Notably, our kernel matrix design, i.e, L(X') and L()), is task-irrelevant and domain www.iingewweedeeee-e free.
Last, the set of sampled trajectories subject to different options should be diverse. This is achieved by maximizing its expected mode number (i.e., Eq. (.) Here, Z is the union set of y related to different options, i.e., Ue 7 (ea,e'), and T.(2) is the kernel matrix corresponding to trajectories in E.
K
C3 DDPP (w:
MY (00000))) My7 (o0.)))
E Z~Pu(Z)
|
(9)
2
S0.0, (ag.e)
3.3 Overall Algorithm Framework
The overall objective is to maximize Eq. 10 The hyperparameters a1 2 0 (provided in Appendix C.6 are the weights for each DPP term and can be fine-tuned to enable a tradeoff between coverage and diversity of the learned options.
C(w,0, L (w, + c.pP (w, CPPPPP(ws (w, 0) + az C (w, (p)P(w
(10)

---

we can calculate the gradients with respect to w. 6, 6, i.e. the parameters of the prior network, policy network and variational decoder, and then apply corresponding algorithms for optimization. First, V L = V C so Pa can be optimized as a standard likelihood maximization problem with SGD [54]. Next, regarding w and f. we have Proposition 2 which is proved in Appendix
Based on Eq. 10,
A.3, Notably, we select PPO (55] to update w and O. The overall algorithm (ODPP) is summarized as Algorithm [] where the main learning outcome is the intra-option policy Te. When applied to downstream tasks, Ta(a|s, c) can be fixed and we only need to learn high-level policy Pø(cls) to select among options. We note that our algorithm is highly salable and only slightly increases the time complexity compared with previous algorithms in this field. Detailed discussion the complexity and scalability are provided in Appendix C.4 and C.5
The gradients of the overall objective L(w, (ww,0,c) の) with respect w and 0 can be unbiasedly estimated using Eq. (17). Here, Q and Qm are the Q-functions for the prior and policy networks, respectively. Consequently, both networks can be trained using reinforcement learning.
Proposition 2.
T-1
VwC = E V log Pu(ls)))) VoC= $0,0,
E
V e log To (a 1t c)Q
(11)
F0.0
T
m=
t=
QTv -loo Par (c) +
E
TH
7 80, c)
(12)
pDPP (Gml [i)) log so. Gm)
T
QTh s0))
log no (a th (a,"ls"" .c)
M
M
1=0
(13)
01 f(mm) - 02g 7 (so.e)) + aggly? 7 (s0.eo)
4 Evaluation and Main Results
In this section, we compare ODPP with SOTA baselines on a series of RL tasks. (1) For intuitive visualization, we test these algorithms on maze tasks built with Mujoco [56). In particular. we select the Point and Ant as training agents, and put them in complex 3D Mujoco Maze environments (Figure 44aa)aann and 4(d)). We evaluate the diversity and coverage of the options learned with different algorithms, through visualizing corresponding trajectories. Then, we provide a quantitative study to see if these options can aid learning in downstream tasks goal-achieving or exploration tasks in the maze environments. Both tasks are long-horizon with episode length of 500. (2) To show the applicability of our algorithm on a wide range of tasks, we test it on 3D Ant locomotion tasks (Figure ((a)) and Atari video games. In this part, we focus on evaluating if the agent can learn effective skills without supervision of task- specific rewards.
As mentioned in Section 2. our algorithm follows the option-first variational option discovery. which starts from random policy rather than an efficient exploration policy like the trajectory- methods. To keep it fair, we compare our algorithm with several SOTA option-first methods: VIC (7), DIAYN g VALOR (7). DADS 99, and APS (57]. Further, our algorithm integrates the variational and Laplacian-basee option discovery, so we compare it with a SOTA aaalaciin--aseee method as well: DCO [1]] The codes are available at
4.1 Ablation Study
In Figure 2 we visualize trajectories of options learned with different algorithms in the Point Room task, which start from the same initial state and have the same horizon (i.e., 50 steps). Note that the visualizations in Figure I 3 are aerial views of the 3D Mujoco Room/Corridor. As mentioned in Section 3.2, the objective of DCO is to train options that can connect states with high and low values in the Fielder vector of the state transition graph. Due to its algorithm design [12), we can only learn one option with DCO simultaneously. (1) From (a)-(c), we can see that variational option discovery methods can discover diverse options, but these options can hardly approach the "bottleneck" states in the environment which restricts their coverage of the state space. On the contrary, in (d), options trained with DCO can go through two "bottleneck" states but lack diversity, since they stick to the direction given by the Fiedler vector. While, shown in (h), options learnt with our algorithm have both superior diversity
time. While, with the others, we can learn multiple options
7

---

(d)
Figure 2: (a) VIC, (b) DIAYN, (c) VALOR, (d) DCO, (e) ODPP (C (f) ODPP (C CPPPP, (g) ODPP using trajectory features defined by hidden layer output, (h) ODPP using trajectory features defined with the Structured DPP framework.
and coverage. (2) (e), we can already get significant better options than the baselines by only using C as the objective. From (e) (f), it can be observed that additionally introducing the objective term CDPP can encourage options to cover more landmark states. From (f) to (h), we further add L2 CPPP and LPPP, which makes the option trajectories more distinguishable from the view of DPP. Also, in (g) and (h). we adopt different designs of the trajectory feature. It shows that using trajectory features defined with the Structured DPP framework (introduced in Section 3.2) is better than using the hidden layer output of the decoder Pa. These results show the effectiveness each component in algorithm design and demonstrate that algorithm can construct options with higher diversity and coverage than baselines. In Appendix D.3] we provide quantitative results to further show the improvement brought by each objective term of ODPP.
Next, as claimed in Section 3.2 if set- ting the feature dimension D 2, ODPP is expected to learn similar op- tions with DCO, thus ODPP generalizes the Laplacian-based method. In Figure visualize the value of each state in the Fiedler vector as the background color (the darker the higher), and the op- tions learned with DCO and ODPP in the Point Corridor task starting from dif- ferent locations. We can observe from (a) and (b) that most of the learned op- tions are similar both in direction and length. Further, if adopt the normal setting, where D 30 and the number options to learn at time is 10, we can get diverse options shown as (c), which can be beneficial for various downstream tasks. In this case, ODPP can viewed as generalization and extension of DCO through variational tools (e.g., BB)) to learn multiple diverse options at time.
23 2
28
(a) DCO
(b) ODPP (D 2)
(c) ODPP
Figure 3: Options leamed with DCO; (b) Options
learned with ODPP, when setting the feature dimension as (c) Options learned with ODPP in the normal setting.
4.2 Evaluation in Downstream Tasks
In Figure 4. we evaluate the options learned with diffferent algorithms on series of downstream tasks. These options are trained without task-specific rewards, and thus potentially applicable to different downstream tasks in the environment. Firstly, we test the options in Point Room/Corride goal-achieving tasks where point agent is trained achieve certain goal (i.e., red points in Figure 4(a) and 4(d). This task is quite challenging since: (1) The location of the goal is not included in the observation. (2) The agent will get a positive reward only when reaches the goal area; otherwise, will receive penalty. Hence, the reward setting is highly sparse and delayed, and the agent needs
fully explore the environment for the goal state. In Figure 4(b) (c) we compare the mean and
standard deviation of the performance (i.e., mean return of decision step) of different algorithms

---

0.00
Coleode
(a) Mujoco Room
(b) Point Room Task
(c) Point Corridor Task
23
VALLM
5.0
Rueer
(d) Mujoco Corridor
(e) Ant Room Task
(I) Ant Corridor Task
Figure 4: (a)(d) Mujoco Maze tasks. (b)(c) Applying the options to goal-achieving tasks in the Point Room/Corridor where the agent needs to achieve one of the four goals (red points). (e)(f) Applying options to exploration tasks in the Ant Room/Corridor where the agent needs to explore as far as possible to get higher reward.
in the training process, which is repeated four times (each time with a different goal). It can be observed that, with options learned by ODPP, the convergence speed and return value can be much higher. Note that the pretrained options are fixed for downstream tasks and we only need to learn an option selector Ps (c)s) which gives out option choice at state s. In this way. we can simplify a continuous control task to discrete task, and the advantage can be shown through the comparison with using PPO (i.e.. "Base RI.") directly on the task. To keep fair, the PPO agent is pretrained for the same number of episodes as the option learning. Moreover, we evaluate these algorithms in Ant Room/Corridor exploration tasks where an Ant agent trained explore the areas as far from the start point (center) as possible. The reward for trajectory is defined with the largest distance that the agent has ever reached during this training episode. In Figure (()) we present the change of the trajectory return during the training process of these algorithms (repeated five times with different random seeds). The options trained with ODPP provide a good initialization of the policy for this exploration task. With this policy, the Ant agent can explore much larger area in the state space.
As mentioned in Section 3
we learn prior network P.. together with the option policy network To. This design is different from previous algorithms which choose to fix the prior distribution. In Appendix [D.I] we provide a detailed discussion on this and empirically show that we can get further performance improvement in the downstream task by initializing the option selector Ps. with Pw.
4.3 Performance of Unsupervised Skill Discovery Across Various Benchmarks
In the 3D Locomotion task, an Ant agent needs coordinate its four legs to move. In Figure S(a), we visualize two of the controlling behaviors, learned by ODPP without supervision of any extrinsic rewards. Please refer Appendix D.2 for more visualizations. The picture above shows that the Ant rolls to the right by running on Leg first and then Leg 4, which is a more speedy way to move ahead. While, the picture below shows that it learns how to walk to the right by stepping on its front legs (2&3) and back legs (1 (1&4) by turn. These complex behaviors are learned with only intrinsic objectives on diversity and coverage, which is quite meaningful. Further, we show numeric results to evaluate the learned behaviors. We use the reward defined in (58) as the metric, which is designed to encourage the Ant agent to move as fast possible the least control cost. In Figure (b)), we take the average of five different random seeds, and the result shows that options trained by ODPP outperform the baselines. The reward drops during training for some baselines, which is reasonable since this is not the reward function used for option learning. Finally, to see whether we can learn a large number of options in the meantime with ODPP, we test the performance of the discovered options when setting the number of options to learn as 10, 20, 40, 60. From Figure 5(c), it can be observed that even when learning a large number of options at the same time, we can still get options with high quality (mean) and diversity (standard deviation) which increase during the training.

---

1100
40 1420
3000 2000 2000 AEAA S000 CICO 2006 500) 3300 2000 3000 5000 5500 7000
Figure 5: (a) Visualization of the controlling behaviors learned by ODPP. (b) The change of the mean and standard deviation of the trajectory rewards subject to different options in the training process. (c) The performance change as the number of options learn at the same time goes up.
240
du dlip
OCPP
2000
00:00
19003
2003 W002 1200
20
2030
4000
X010
10:30
(a) CartPole
(b) RiverRaid
(c) AirRaid
Figure Evaluation results on OpenAl Gym and Atari games to show the superiority of our algorithm on more general tasks. Our algorithm performs the best in all the three tasks, and the performance improvement becomes more significant as the task difficulty increases.
To further demonstrate the applicability of ODPP, we compare it with SOTA baselines on more general OpenAl Gym and Atari tasks [59]. Notably, we adopt two more advanced skill discovery algorithms as baselines: DADS and APS. Comparisons among these two and previous baselines are in Appendix D.4 Skills discovered with different algorithms are evaluated with reward functions carefully-crafue for each task, provided by OpenAl Gym. For each algorithm, which the average cumulative rewards (i.c., sum of rewards within a skill duration) in the training process shown in Figure 6 The skill duration is set as 100 for CartPole and 50 for the other two. Note that the complete episode horizon is 200 for CartPole and 10000 for AirRaid and RiverRaid. Thus, it would be unfair to compare the cumulative reward of skill with the one of whole episode. Our algorithm performs the best in all the three tasks, and the improvement becomes more significant the task difficulty increases. When relying solely on MI-based objectives, the agent tends to reinforce already discovered behaviors for improved diversity rather than exploration. The explicit incorporation of coverage and diversity objectives in our algorithm proves beneficial in this case.
learn 10 skills, of
Conclusion and Discussion
ODPP is a novel unsupervised option discovery framework based on DPP, which unifies variational and Laplacian-basee option discovery methods. Building upon the information-theott prior variational research, propose three DPP-related measures to explicitly quantify and optimize diversity and coverage of the discovered options. Through a novel design the DPP kernel matrix based the Laplacian spectrum of the state transition graph, ODPP generalizes SOTA Laplacian- based option discovery algorithms. We demonstrate the superior performance of ODPP over SOTA baselines using variational and Laplacian-basee
objectives in
series of challenging benchmarks. Regarding limitations of ODPP, the primary one is to assign suitable weights for each objective term: crucial, yet conducting grid search for their joint selection would be exhaustive. Instead, we employ a sequential, greedy method to select hyperparameters in accordance with our ablation study's procedure, further detailed in Appendix C.6
methods
01:3 in Eq. (T)) and 3 in Eq. (6). These hyperparameters
Acknowledgments and Disclosure of Funding
This project is supported by ONR award N00014-23- 1-2850 and CISCO research award 76934189,
10

---

References
[1] Brown, N., T. Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456)::833 -90- 2019.
[2] Silver, D., Huang, C. Maddison, et Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484449) 2016.
[3] Ebert, F., C. Finn, S. Dasari, A. Xie, A. Lee, S. Levine. Visual foresight: Model-based deep reinforcement learning for vision-based robotic control. arXiv preprint arXiv: 180o:008820008 2018.
[4] Lillicrap. T. P., J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver. D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 150900997,, 2015.
[5] Chen, J., A. K. Umrawal, Lan, Aggarwal. Deepfreight: A model-free deep-reiinfrrcement learning-based algorithm for multi-transfer freight delivery. In Proceedings of the 3 Inter- national Conference on Automated Planning and Scheduling, pages 510-518. AAAI Press, 2021.
[6] Al-Abbasi, A. O., A. Ghosh, V. Aggarwal. Deeppool: Distributed model-free algorithm for ride- sharing using deep reinforcement learning. IEEE Transactions on Intelligent Trunsportation Systems, 20( 20(12):47144777
2019.
[7] Gregor, K., D. Rezende, D. Wierstra. Variational intrinsic control. Proceedings of the 5th International Conference Learning Representutions, ICLR 2017. OpenReview.net, 2017.
[8] Eysenbach, B., A. Gupta, J. Ibarz, S. Levine. Diversity is all you need: Learning skills without a reward function. In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, OpenReview.net, 2019.
[9] Sharma, A., S. Gu, S. Levine, V. Kumar, K. Hausman. Dynamics-aware unsupervised discovery of skills. In Proceedings of the 8th International Conference Learning Representations, ICLR 2020. OpenReview.net, 2020.
[10] Cover, T. M. Elements of information theory. John Wiley Sons, 1999.
[11] Jinnai, Y., J. W. Park, D. Abel, G. D. Konidaris. Discovering options for exploration by minimizing cover time. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, vol. 97 of Proceedings of Machine Learning Research, pages 3130-3139. PMLR, 2019.
[12] Jinnai, Y., J. W. Park, M. C. Machado, G. D. Konidaris. Exploration in reinforcement learning with deep covering options. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
[13] Ghosh, A., S. P. Boyd. Growing well-comnected graphs. In Proceedings of the 45th IEEE Conference on Decision and Control, CDC 2006, pages 6605-6611. IEEE, 2006.
[14] Campos, V., A. Trott, C. Xiong, R. Socher, X. Giró-i-Nicto, J. Torres. Explore, discover and learn: Unsupervised discovery of state-covering skills. In Proceedings of the 37th International Conference on Machine Learning, ICMI.2020 vol. 119 of Proceedings of Machine Learning Research, pages 1317-1327. PMLR, 2020.
[15) Ajay, A., A. Kumar, P. Agrawal, S. Levine, O. Nachum. OPAL: offline primitive discovery for accelerating offline reinforcement learning. In Proceedings of the 9th International Conference
on Learning Representations, ICLR 2021. OpenReview.net, 2021.
[16] Lee, L., B. Eysenbach, E. Parisotto, P. Xing, S. Levine, R. Salakhutdinov. Efficient exploration via state marginal matching. CoRR, htts/1906.052744 2019.
[17] Sutton, R. S., D. Precup, S. P. Singh. Between mdps and semi-mdps: A framework for temporal abstraction reinforcement learning. Artificial Intelligence,
1999.
[18] Chen, J., Chen, T. Lan, V. Aggarwal. Multi-agent covering option discovery based on kronecker product of factor graphs. IEEE Transactions on Artificial Intelligence, 2022.
[19] Learning multi-agent options for tabular reinforcement learning using factor graphs. IEEE
Transactions Artificial Intelligence, pages 1-13, 2022.
[20] Zhang, F., C. Jia, Y.C.. Li, L. Yuan, Y. Yu, Z. Zhang. Discovering generalizable multi-agent coordination skills from multi-task offline data. In Proceedings of the I 11th International Conference Learning Representations. 2022.

---

[21] Chen, J., M. Haliem, T. Lan, V. Aggarwal. Multi-agent deep covering option discovery. arXiv preprint arXIv:2210.03266, 2022.
[22] Zhang, S., S. Whiteson. DAC: the double actor-critic architecture for learning options. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pages 2010-2020. 2019.
[23] Li, C., D. Song, D. Tao. The skill-action architecture: Learning abstract action embeddings for reinforcement learning. In Submissions of the 9th International Conference on Learning Representations. 2021.
[24] Jing, M., W. Huang, F. Sun, X. Ma, T. Kong, C. Gan, L. Li. Adversarial option-aware hierarchical imitation learning. In Proceedings of the 38th International Conference on Machine Learning, pages 5097-5106. PMLR, 2021.
[25] Chen, T. Lan, V. Aggarwal. Option-aware adversarial inverse reinforcement learning for robotic control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 5902-5908. IEEE, 2023.
[26] Chen, J., D. Tamboli, T. Lan, V. Aggarwal. Multi-task hicrarchical adversarial inverse reinforce- ment learning. In Proceedings of the 40th International Conference Machine Learning, vol. 202 of Proceedings of Machine Learning Research, pages 4895-4920. PMLR, 2023.
[27] Achiam, J., H. Edwards, D. Amodei, P. Abbeel. Variational option discovery algorithms. CoRR, Abs/1807. 807.10299, 2018.
[28] Kingma, D. P., M. Welling. Auto-encoding variational bayes. In Proceedings of the 2nd International Conference on Learning Representations, ICLR 2014. 2014.
[29] Levine, S., A. Kumar, G. Tucker, J. Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. CoRR, abs/2005.01643, 2020.
[30] Hansen, S., W. Dabney, A. Barreto, D. Warde-Farley, T. V. de Wiele, V. Mnih. Fast task inference with variational intrinsic successor features. Proceedings of the 8th International Conference on Learning Representations. OpenReview.net, 2020.
[31] Baumli, K., D. Warde-Farley, S. Hansen, V. Mnih. Relative variational intrinsic control. In Thirty- AAAI Conference on Artificial Intelligence, pages 6732 6740. AAAI Press, 2021.
[32] Hansen, S., G. Desjardins, K. Baumli, D. Warde-Farley, N. Heess, S. Osindero, V. Mnih. Entropic desired dynamics for intrinsic control. In Advances in Neural Information Processing Systems 34, pages 1 11436-11444 1448. 2021.
[33] Kamienny, P., J. Tarbouriech, S. Lamprier, A. Lazaric, L. Denoyer. Direct then diffuse: Incremental unsupervised skill discovery for state covering and goal reaching. In Proceedings the 10th International Conference on Learning Representations. OpenReview.net, 2022.
[34] Strouse, D., K. Baumli, D. Warde-Farley, V. Mnih, S. Hansen. Learning more skills through optimistic exploration. In Proceedings of the 10th International Conference on Learning Representations. OpenReview.net, 2022.
[35] Liu, H., P. Abbeel. APS: active pretraining with successor features. In Proceedings of the 38th International Conference Machine Learning, vol. 139, pages 6736-6747. PMLR, 2021.
[36] Kulesza, A., B. Taskar. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 5(2-3):123-288) 2012.
[37] Elfeki, M., C. Couprie, M. Rivière, M. Elhoseiny. GDPP: learning diverse generations using determinantal point processes. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, vol. 97 of Proceedings of Machine Learning Research, pages 1774-1783 PMLR, 2019.
[38] Gong, B., W. Chao, K. Grauman, F. Sha. Diverse sequential subset selection for supervised video summarization. In Advances in Neural Information Processing Systems 27, NeurIPS 2014, pages 2069-2077. 2014.
[39] Chen, L., G. Zhang, E. Zhou. Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In Advances Neural Information Processing Systems 31, NeurIPS 2018, pages 5627-5638. 2018.
12

---

[40] Wilhelm, M., A. Ramanathan, A. Bonomo, S. Jain, H. Chi, J. Gillenwater. Practical diversified recommendations on youtube with determinantal point processes. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 2165-2173. ACM, 2018.
[41]
Serez-Beltrachini. L., M. Lapata. Multi-docume summarization with determinantal point process attention. Journal of Artificial Intelligence Research, 71:371-399, 2021.
[42] Song, Y.. R. Yan, Y. Feng, Y. Zhang, D. Zhao, M. Zhang. Towards neural conversation model with diversity net using determinantal point processes. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 5932-5939. AAAT Press, 2018.
[43] Holder, J., A. Pacchiano, K. M. Choromanski, S. J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing
Systems 33. 2020.
[44] Nieves, N. P., Y. Yang, O. Slumbers, D. H. Mguni, Y. Wen, J. Wang. Modelling behavioural diversity for learning in open-ended games. In Proceedings of the 38th International Conference on Machine Learning, vol. 139, pages 8514-8524. PMLR, 2021.
[45] Wu, S., J. Yao, H. Fu, Y. Tian, C. Qian, Y. Yang. Q. Fu, W. Yang. Quality- diversity via population based reinforcement learning. In Proceedings the 11th International Conference on Learning Representations. OeenRevie,.net, 2023.
[46] Kwon, T. Variational intrinsic control revisited. In Proceedings of the 9th International Conference on Leurning Representations, ICLR 2021. OpenReview.net, 2021.
[47] Alemi, A. A., I. Fischer, J. V. Dillon, K. Murphy. Deep variational information bottleneck. In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017. OpenReview.nee 2017. [48] Ko, C., J. Lee, M. Queyranne. An exact algorithm for maximum entropy sampling. Operation Research, 43(4):684-691, 1995.
[49] Ng. A. Y., M. I. Jordan, Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14, NewrlPS 2001, pages 849- 9566. MIT Press, 2001.
[50] Wang, K., K. Zhou, Q. Zhang, J. Shao, B. Hooi, J. Feng. Towards better laplacian representation in reinforcement learning with generalized graph drawing. In Proceedings of the 38th Inter- national Conference on Machine Learning. ICML 2021, vol. 139 of Proceedings of Machine Learning Research, pages 11003-11012. PMLR, 2021.
[51] Kulesza, A., B. Taskar. Structured determinantal point processes. Advances in Neural Information Processing Systems 23, NeurlPS 2010, pages 1171-1179, Curran Associates, Inc., 2010.
[52] Yuan, K. M. Kitani. Diverse trajectory forecasting with determinantal point processes. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
K.
[53] Yang, Y., Y. Wen, Wang, L. Chen, K. Shao, D. Mguni, W, Zhang. Multi-agent determinantal g-learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, vol. 119 of Proceedings of Machine Learning Research, pages 10757-10766. PMLR, 2020.
[54] Amari, S. Backpropagation and stochastic gradient descent method. Neurocomputing, 5(3):185- 196, 1993.
[55] Schulman, J., F. Wolski, P. Dhariwal, A. Radford, O. Klimov. Proximal policy optimization algorithms. CoRR, fass/7777.06347 2017.
[56] Todorov, E., T. Erez, Y. Tassa. Mujoco: A physics engine for model-based control. In 2012
JEFE/RSJ International Conference on Intelligent Robots and Systems, pages 0036-5033. IEEF, 2012.
[57] Liu, H., P. Abbeel. APS: active pretraining with successor features. In Proceedings of the 38th International Conference on Machine Learning, vol. 139, pages 6736-6747. PMLR, 2021.
[58] Schulman, J., P. Moritz, S. Levine, M. Jordan, P. Abbeel. dime-siiea continuous control using generalized advantage estimation. In Proceedings of the 4th International Conference on Learning Representations, ICLR 2016. 2016.
13

---

[59] Hosu, I. T. Rebedea. Playing atari games with deep reinforcement learning and human checkpoint replay. CoRR, ttss/667.00007, 2016.
[60] Fiedler, M. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2)2998- 305, 1973.
14

---

A Notations and Proof
A.1 Basic Concepts and Notations
Markov Decision Process (MDP); The reinforcement learning problem can be described with an MDP, denoted by M (S,A,P, R, 7). where S is the state space, A is the action space, P SS x A x S + [0, 1] is the state transition function, R S x A + R is the reward function, and y 1), is the discount factor.
State transition graph in an MDP: The state transitions in M can be modelled as state transition graph G = (Va, Eg), where Va is set of vertices representing the states in S, and Eg is set of undirected edges representing state adjacency in M. We note that:
Remark. There is an edge between state 8 and s' (i.e., 8 and s' are adjacent) if and only if 3a A, s.t. P(s, a, 8') V PPs'', a, 8) > 0.
The adjacency matrix A of G is an |S] [S] matrix whose (i.j) entry is 1 when 8; and sj adjacent, and otherwise. The degree matrix D is a diagonal matrix whose entry (i. equals the number of edges incident to s;. The Laplacian matrix of G is defined smallest eigenvalue A2 (L) is called the algebraic connectivity of the graph G. and the corresponding normalized eigenvector is called the Fiedler vector [60] Last, the normalized Laplacian matrix defined as D- LD-
L D A. Its second
A.2 Proof of Proposition I
To start with, we can find lower bound of the second term in Eq. 5 as follows:
-B
E (pmpp())
[Tc, T|80]]
-3 E somp(()
Σ P(r]su) P(g))s)))
1 + Σ
P(c,)(so)log Po(t|so,
3 E
Σ P(g7)s)) Σ
log log
s)m
C,t
P)( P(T(sp)
-33 E
Σ Po((e)))
sp))(
C,7
1og Po(T|so:
log P(T(su)
= =-3 E
Σ Po((ls)
Unif(r|su) su)
Unif(r]so)
pp)p())
G5T
Po(T|so.c) c) Σ Pc((cso))P(((ee,ss) log Unif(r(so)
3 E
Dx((P(rss)l(umiffttl)
s0~
Po (0. Σ Pa((cso) log (TTs)( 6,5
2 - E
p()
= -
E
()))(() (-
(14)
where (-I(-)) denotes the Kullback-Leibler (KL) Divergence which is non-negative, Po(T[so. c) ITT-0 Ta (e)sss,)PP(ss....
ax) is the probability of the trajectory given so and under the option policy ny, and Unii(()))) (50) is the probability of the same trajectory given 5g under the random walk policy. Instead of explicitly calculating P(r(so) which is impractical, we introduce Uni 'nif(rr (r(ss) to convert the second term in Eq. (5) into a regularization term to encourage exploration and diversity.
As for the first term in Eq. (5). we can deal with it as Eq. 15 where we introduce (o(c) G) as the variational estimation P(c|so, G) which hard to acquire. The first inequality Eq. 15) is based on the fact that KI. Divergence is non-negative. While, the second inequality holds because we only keep the trajectory J from which sampled, so the trajectory and corresponding landmark states form a bijection.
15

---

E [0mp(()
[Tc, Glsu)]
= E
Σ Pu(c[so) Pu((ssu)) + Σ 30 s)ma()
log P(c|su, G)
c.G
P(Cls c) log Po(c|so, G) P(c|so. G) Pa(c|so. G)
Σ Pu(((ss)) log Pu(c(s)) +
Σ
E somu(+)
c,G
H(([S)+
+
E (pmpp())
Σ (o Polcsoo G)
P(Glss)Dxx.PccbboCllll (lIl G))
H(C[S)+ +
Pol(os)) log Po(c|so, G)
(om-)(-)
H((CS)) +
E somp(()
Σ Pu(c(so) Σ Pol''sso, so, ()PDPP(((TT) (G(r)) log Pa(clss, G)
H(C[S)+ +
E (p)pp()
Σ Po(cls c)PDPP (occ
Po(Cc))) Po(e|so G)
(15)
A.3 Proof of Proposition 2
First, we take the gradient with respect and get the following result:
VwC=
E )amu(()
Σ V log Pa
P.Peccca Palcsa, G)
(16)
01
02
Pu
Σ
Po Po(7)ss,c)g((((000))
+ Σ
(uPasc))))
Σ (1000)
Po s0,
ch) c'))
Given that Pulss))) = (a(c(ss)V V. log Pa (clso) and the definition of KL Divergence, i.e..
DEL (Po(T]so, <) (nn((((((s)))) = Σ, PO(T 80, c) TT-1 [log mo(a (t, e) - log Tumif (at {8)]] we simplify Eq. [16
V
Ve log (c.
8g s)))))) (-1so))
(17)
where the related Q-function QN (c, 50) is defined as:
Pa (c, s0) = llog (u(c((s)) (ro Pott
E
Laag( 7 (eo.0) + agally 7 (eane)
(18)
T-1
E TouPot- 8p.c)
PDPP log Po(c(00, G)
log (arlo( + a()
16

---

Next, we calculate the gradient with respect to 0 as follows:
VoL= E (amp(())
Σ
PulccoolVoPo(tlbu c) PDPP (G]T) Po(cloo: G) Polleoo
RST
Σ Pu(ccso)VoPPo(Tle c)
log To (a(al log Tunis ( [s)]]
B Σ
Pu(choo c)
Vo log To (a)lss))
6,7
Σ
Σ Pa(c(so)
Σ
VoPo(7 10. c) [ (s0. c)) azh(l 7(00, d))
((aa.e)
(19)
With VaPo(T|so, Po(T]so, c) V log (o( Pa
c) Et= Vo log To (8,, c). and mE Er- To 1s c) where s (a.t) is the state (ac-
(oPo Ss. c) Po Po(7|su: ssu c)
tion) at step t in trajectory m. Eq. can be written as follows:
VoL=
Ve log (s
PDPP log Po(ciso, G) G)) 3
Σ 1=
log me anf(T)
$p.0,T
Σ
Ve log To (a,""sss .c) [ ( (m)))) + azh(y 7 (sor)))
80.0,
M
E
Σ
Vo log To |s" c))m0 (
80,0,T
(20)
where the advantage term is as Eq. 21 7 {TI, ... TMr) Tm = (s8
-88- a sT)):
PDPP (G,n m (m log Pa Pa(ciso: Gm)
B T-1
Q (7, c)
log
log c)
M
(21)
(Tm) 02g( 7 (s) aahly 7 (s0.et)
M
Then, it's not hard to see the relationship between QPw and Q as:
(c, -- -log Pa (c(ss)) +
Σ Thh ( 80, c)
(22)
17

---

B Comparisons with Recent Variational Option Discovery Algorithms
Here, we provide comparisons of our algorithm with more recent variational option discovery methods 30
31
32
33
35
In 300, the authors focus on alternative approaches to leverage options learned during the unsuper- vised phase, rather than new option discovery algorithms. They still adopt objectives based on Mutual Information (MI) as previous works without solving the exploration issue.
The authors of propose siightl-modified version of VIC improve usefulness of the discovered options by introducing an extra posterior. Still, their options are not explicitly trained for better coverage/exploration like ours.
The authors of [32 propose to replace the fixed prior distribution P(c) with a fixed dynamics model over the option latent codes P(cxle--1). Each latent code corresponds to sub-trajectory By concatenating sub-trajectories, the agent can reach much further states. They only rely on MI-based objectives, so they cannot model the coverage of each option (like ours) and instead choose chain options for better overall coverage. The fixed P(c (t-1) can result in inflexibility when applying options in downstream tasks.
In (33], they employ a multi-step protocol to generate options organized in a tree-like structure. Heuristics and structural limits are involved in each step. which may hinder its generality. Also, they propose to optimize the local coverage around the final state rather than the overall trajectory coverage like ours.
The authors of 34 note that, with variational objectives proposed in VIC and DIAYN, the agent can be discouraged from seeking out new states, since the variational posterior Pa(c))) is likely to make poor predictions when presented with trajectories containing previously unseen states, resulting in low rewards for the policy. Thus, exploration bonus should be introduced as extra reward term. In 34,, they choose to train ensembles of discriminators and adopt their disagreement as a measure of state uncertainty. States of higher uncertainty are assigned with higher exploration bonus. Similar to theirs, our algorithm introduces additional bonus as a reimbursement of the unnecessary pessimistic exploration. The difference lies that they adopt an implicit exploration measure (i.c., the disagreement among ensembles) while we use explicit ones based on DPP.
In 35 they optimize the MI [(s, c) H(s) - M(ssc), where H(s) is for improving exploration of the learned options. They adopt a variational posterior (s|c) to estimate H(slc). Learning Pø(s|c) can be challenging when the state space is high-dimensional, compared with (c(c)s) used in our paper, which can hinder the optimization. Further, in DADS, they categorize algorithms utilizing [(s.c) c) H() H(s|c) as the forward form of MI-based option discovery, and they empirically and theoretically show the limited capability of these algorithms for exploration even with H(s) in the objective.
C Implementation Details and Analysis of ODPP
C.1 The Choice of Diversity Measure
The expected cardinality is a better choice for the diversity measure than the likelihood shown as Eq. ( Using the log-likelihne likelihood based on the Determinant of the DPP kernel matrix directly would heavily penalize repeated items in the sampled set W in Eq. [.. For example, if there are very similar points in W. the corresponding rows in the kernel matrix will be almost identical and lead to zero determinant, which will cause numerical issues for the logarithm function. Take our work as an example: at the beginning of the training stage, the moving range of the Mujoco agent is very limited, then we always include very close states in a trajectory, which will always lead to a zero determinant and thus cannot provide training signals. However, the expected cardinality only counts the number of diverse states in trajectory that will not be heavily influenced by the repeated items. Therefore, we select the expected cardinality as the diversity measure in this paper.
C.2 Fast Greedy MAP Inference for DPP
The maximum posteriori (MAP) inference of DPP aims at finding the subset of items with the highest possibility under the DPP measure, which is NP-hard [48). The log-probability function in
18

---

DPP, i.e., I(W) = degdetLw]) is submodular, which means:
ViE W, Wi S W2 S WAfO) u ((W)) 2 IW2 (i)) ((0))-((()) ((W))
(23)
Thus, the MAP inference for DPP be converted to submodular maximization problem, where greedy algorithms have shown promising empirical success, Recently, the authors of [39] propose a fast greedy method for MAP inference in DPP with time complexity O(S*N) to return S items of sample space of size N. The key step of their algorithm is that for each iteration, the item which maximizes the marginal gain:
arg max 1(Wmap U (ot) I(W map)
(24)
iEWAW Wmap
is added to Wm mapp starting from an initial set 0, until the maximal marginal gain becomes negative or the target sample number is reached (i.e., stopping criteria). This part is not contribution. We provide its detailed pseudo code as Algorithm 2 For the derivation, please refer to the original paper We also provide its implementation code part of the complete code of ODPP.
39
Algorithm 2 Fast Greedy MAP Inference for DPP
1: Input: The set of items W and its kernel matrix L, stopping criteria
2: Initialize: For i W, C, D. df La; W Wmap (i), where arg maxiew log(d?)
3: while stopping criteria not satisfied do
4: for E WWWWnme. do
5:
= (L Cj. >)/d; log(d?), Wmop- = Wmap U [
6: C2 = ca @:). d? = df - c.
7:
end for
8: j arg
9:
end while
10: Return W Wmap
C.3
Computation of the Laplacian Spectrum for the Infinite-scale State Spaces
As mentioned in Section 3.2 the feature vector of each state b, is defined with the eigenvectors corresponding to the D-smallest eigenvalues the Laplacian matrix of the state transition graph. However, for the infinite-scale state spaces, cannot obtain this Laplacian spectrum through matrix- based methods, so we adopt the NN-based method proposed in (50) for estimating the Laplacian spectrum, which has been proved to be scalable for infinite-scale state spaces and sufficiently accurate compared with the groundtruth. Since this algorithm is not our contribution, we only provide the take-away messages here for implementation.
According to [50], the & smallest eigenvalues dLse and corresponding eigenvectors Visk of the Laplacian L can be estimated by: (k: D for our case)
min Σ (k - i 1)07 Lui, s.t. of 03 6ij. V i,j = 1,..., M1...
(25)
For the large-scale state space, the eigenvectors can be represented as neural network that takes state 8 as input and outputs a k-dimension vector (s), ... Sx (s)) as an estimation of (r) (s). ... (s))))
Accordingly, the objective in Equation (25) can be expressed as: (please refer to (50) for details)
G(I,,... .R) (T
ΣΣ ((,()))())))))
(26)
where T is a set of state-tran tate-trrasstions collected by interacting with the environment through a random policy. Further, the orthonormal constraints in Equation (25) are implemented as penalty term:
P(f..... fx) aEsup.stap
ΣΣΣ - & - 6.)
(27)
where a is the weight term and is the distribution of states in T. To sum up, the eigenfunctions f can be trained an NN by minimizing the loss function:
T.fi...., ffk) G(fi, fak) +
(28)
19

---

C.4 Analysis on Computation Complexity
The learning target of ODPP is intra-option policy to(a,s, c) conditioned on the option choice As in Section 3.3] this policy is learned with an Actor-Critic algorithm for which the Q-function is defined as Eq. (13) This Q-function contains variational and DPP-based objectives. Compared with previous variational option discovery algorithms (e.g., DIAYN, VIC, VALOR), we additionally need to (a) sample landmark states from each trajectory and (b) calculate the DPP-related terms:
f()), g(-), h(().
For (a), adopt fast greedy MAP inference algorithm for DPP. As mentioned in Appendix C22 it takes ((5 N) to sample S landmark states from an option trajectory of length N. In our setting, N 50, 5 10, so the process be done in real-time.
For (b), we need to build DPP kernel matrices, and then compute f(-): g(-), h(()) based on eigenvalues of the corresponding kemeel matrix in Eq. -7) 9 The time complexity for eigen decomposition is ( where N is the size of the matrix. For the state kernel matrix, is the number of states in an option trajectory (i.e., the option horizon) which we set as 50. For the trajectory kernel matrix, N corresponds to the number of trajectories collected in each training iteration, which set as 100. Thus, f(-), 9(), h(-) can be computed in real-time.
To build the kernel matrix, we need feature vectors for each state. As introduced in Appendix C. the feature vector is the output of a pre-trained neural network which takes the state as input. The training of this feature function based on state transitions in the replay buffer and only needs to be done for once or twice in the whole option discovery process, of which the time cost is within 30 minutes.
To sum up, compared with previous variational methods, we additionally introduce three DPP items to explicitly model the option diversity and coverage, of which the involvement only slightly increases the time complexity.
C.5 Analysis on Scalability
ODPP can be adapted to more intricate setups encompassing longer option horizons, a greater number of skills, or visual domains. We elaborate on the scalability of ODPP as follows.
(a) The skill horizon is constrained by the MAP inference and eigen decomposition operations previously described. Given their time complexity, the skill horizon could readily be expanded from 50 to 100 or even 500. This augmentation would necessitate an additional time of O(10 or O(10~3) 2) seconds per training iteration, compared with previous variational methods. These estimations are based on computations on a machine with a single Intel i7 CPU and four GeForce RTX 2060 GPUs. Note that skill horizon longer than 100 is rarely necessary. Employing skill with an excessively long horizon may compromise flexibility in decision-making.
(b) Compared with variational methods, our algorithm does not introduce extra limitations on the number of learned skills. Moreover, in Figure Stc), we show that even when learning a large number of options at the same time (as much as 60), we can still get options with high quality (mean) and diversity (standard deviation) which increase during the training process.
(c) ODPP needs to learn the Laplacian feature embeddings. For visual domains, this process can incorporate a pretrained CNN model as feature extractor, which serves to convert visual input into feature vectors. Subsequently, the original algorithm can be applied. Applications in visual domains could pose a common challenge for all option discovery algorithms and present an exciting avenue for future research.
C.6 Important Hyperparameters
First, we introduce the structure of the networks used our algorithm and the baselines as follows. We use s_ s_dim, a_dim to represent the dimension of the state space and action space respectively. and use e_nuum to represent the number of options to learn at time, which can be 10, 20, 40 or 60 in our experiments. Also, we use lanh and relu to denote the hyperbolic tangent function and rectified linear unit used as the activation functions, FC(X, Y), BiLSTM(X Y) to denote the fully-comnected and bidirectional LSTM layer with the input size X and output size Y.
20

---

The prior network Pw is used in all the algorithms other than DCO and its structure is [FC dim, 64), tanh, FC(64, 64), tanh, FC 64), tanh, FC c num)]. The value network corresponding to Pw has the same structure as Pu. except that the output is of size 1.
The policy network To is used in all the algorithms, with the structure [FC(s dim e e_num, 64), tanh, FC 64), tanh, FC, 64), tanh, FC a_ o_dim), tanh]. Its corresponding value network has the same structure except that the output is of size 1 and there is not tanh at the end.
The decoder P used in ODPP and VALOR takes a sequence of states in the trajectory as input, so it uses bidirectional LSTM as part of the network, i.e., (B sdmm,, 64), (2 64, c_num)].
While, the decoder of VIC and DIAYN takes one state input rather than sequential data, so it uses the fully-connected layer instead, i... IFC(s_dimn 180), tanh, FC8000, 180), tanh, FC(180, 180), tanh, FC((80, c_num)]]
The option selector Pe has the same structure as Pa and used in all the algorithms.
The eigenfunction network introduced in Section C.3 is used in ODPP and DCO to estimate the Laplacian spectrum. Its structure is [FC(s dem, 256), relu, FC(556, 256), relu, (2(556, 256), relu, (256 256), relu, (C 30)]. where 30 denotes the dimension
of the feature vector b; mentioned Section 3.2
As noted in the paper, the crucial hyperparameters are 3, 01:3 in Eq. and (T0) which control the importance of each objective term, relating to diversity and coverage. Conducting a grid search on the set of parameters
be exhaustive. Therefore, we follow the process of the ablation study shown in Figure 2 add objective terms and adjust their corresponding weights one by one. In particular,
in Figure 2 e), we retain only the L objective and select its weight / 10-3 from five possible choices: 1, 10011 10-2 10-3 10-4, guided by the visualization results. Next, for Figure (1),, we introduce CPPP and fine-tune the corresponding weight on while keeping / fixed 10 Last, we incorporate CDPP and LDPP and adjust 02 and (3 accordingly, while keeping 3 and oi fixed. Note that the final two terms must work in tandem ensure that the discovered options exhibit diversity across different options and consistency for a specific option choice.
After fine-tuning, we set 3 10-3 a1 10 02 10 2 ag 1002. It is worthy noting that our evaluations across various challenging RL. tasks utilize the same hyperparameter set, highlighting the robustness of our algorithm. This is because our proposed (DPP- (DPP-based) coverage and diversity measures are task-agnostic and universally applicable to RL tasks.
D
Additional Evaluation Results
D.1 Complementary Results on the Effect of the Prior Network
As discussed in Section we learn a prior network Pa concurrently with the option policy network me- Figure 77 demonstrates how initializing the option selector P.. with P. can lead to further performance improvement in the downstream task, using the Point Corridor goal-achieving task as an example. This is based the fact that both networks share the same structure.
First, in (a), we sample 10,000 trajectories for each option and visualize the agent orientation distribution corresponding to different options. In (b), we present the coordinate system setup along with the four turning points for evaluation. The option choices at these turning points provided by the prior network are displayed in (c). It can be observed that P., favors the most significant options at given state. For instance, at Location #1, Option #5, which tends to go left or down as shown in (a), preferred, while at Location #3, Option #3 is favored, guiding the agent to go up or right. Lastly, in (d), we demonstrate that initializing the option selector with the prior network can further enhance the agent's performance in the downstream goal-achieving task.
Previous variational methods choose to fix the prior distribution to avoid a collapse for the prior network to sample only a handful of skills. Our algorithm pretends that because our algorithm additionally introduces three DPP-based terms to explicitly maximize the coverage and diversity of the learned options. With CPPP, each option is expected to cover multiple state clusters with long range and different options tend to visit different regions in the state space. In this case, the prior network would tend to select multiple diverse skills to improve its learning objective (i.c., Eq.
21

---

Option
0.005
110
90
140
1180
180
-180
-10
80
190
-180
190
-1.00
-80
190
0.010
0.005
-100
-80
90
100
110
-80
50
100
-00
-00
0
90
150
-150
-00
90
100
-100
-00
50
150
Orientatin
Location
Location
(d)
Mopoethm
0.50
0.00
Location 83
Location M
Option Choloe
Figure 7: (a) Agent orientation distribution corresponding to different options. (b) Setup of the coordinate system and start points. (c) The output distribution the prior network at different start points. (d) Performance improvement in the downstream task when applying the prior initialization. The trained prior gives preference to more useful options at corresponding states. At Location #1. Option #5, which tends to go left or down, is preferred: at Location #3, Option #3 is preferred which can lead the agent to go up or right. Moreover, Option #8 preferred Location #2 to lead the agent to go down, while Option #6 is preferred at Location #4 to lead the agent to go up.
(22) rather than sampling only few of them. The collapse happens because the mutual information objective only implicitly measures option diversity as the difficulty of distinguishing them via the variational decoder and does not model the coverage, as noted in Section 3 This motivates to introduce explicit diversity and coverage measures regularizers and enhancement.
D.2 More Visualization of the Learned Ant Locomotion Behaviors
we show more visualization results of the learned Ant locomotion behaviors without the supervision of task-specific rewards.
In Figure 8
(a) Flip
(b) Rotation
Figure 8: (a) The Ant agent learns flip over first, then tries to flip back, and finally stands on its Leg 1. (b) The Ant agent walks to the right while rotating. It uses Leg 2&3 as the front legs at first
and Leg 1&2 the front leags at last.
22

---

D.3 Quantitative Ablation Study Results
Algorithm
Distance
Standard deviation in
Standard deviation in
ODPP (C!B)
9.600 + 0.724
5.342 + 0.521
9.239 + 0.689
ODPP (LTB, 4
11.037 +: 0.627
7.067 +: 0.565
9.313 + 0.731
ODPP (C CT3""
14.241 = 0.653
7.493 0.547
10.077 + 0.799
Table 1: Numerical results on Mujoco Corridor. We compare our algorithm (the third row) with its ablated versions. ODPP (C! represents version using only the variational objective _ whereas ODPP BL cPPP) includes the additional coverage objective LPPP. For each algorithm, we collect ten different option trajectories and compute the mean distance (i.e., vz² + y²) of the final states as the (single-option) coverage measure, and the standard deviation on æ and y (of the final states) as the diversity measure. For goal-achieving tasks, these are reasonable metrics, as adopted VALOR. The table displays the 95% confidence intervals these metrics from ten repeated experiments. It can be observed that the performance in coverage and diversity improves with the introduction DPP-based objectives, supporting our algorithm design.
Algorithm
Distance
Standard deviation æ Standard deviation in
ODPP (L ODPP (C CDPP)
11.737 + 0.581
7.424
0.450
9.637 + 0.766
13.008 + 0.786
8.649
0.887
9.768 0.633
ODPP (C "
15.349 = 0.629
10.551 + 0.558
11.356 + 0.515
Table 2: Numerical results on Mujoco Room. These results gathered in the same way described above, and the same conclusion can be derived from this table.
D.4 Baseline Performance on OpenAl Gym and Atari Games
30
20
80
2000
4003
60C0
8200
10000
2005
4000
GO00
8000
20000
Step
S0ep
(a) CartPole
(b) RiverRaid
wuch
DAY
D00
DADS
2000
4000
3000
10000
(c) AirRaid
Figure Each algorithm is employed to learn skills various tasks in an unsupervised manner. The 95% confidence intervals of the option trajectory rewards from repeated experiments with different random seeds are depicted. Comparisons between DADS (brown) and APS (purple) with other baselines illustrate their enhanced performance.
23


Reviews:
[{"review_id": "leHeLqrRqy", "reviewer": "Reviewer_4NNK", "summary": "This paper proposes and evaluates an approach to option discovery in reinforcement learning. The aim is to autonomously identify a set of options that are diverse and that give good coverage of the state space. This aim is achieved by using the Determinantal Point Process (DPP). The proposed approach is evaluated in a range of domains. ", "questions": "No questions.", "limitations": "Adequate.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed approach is intuitive and principled. \n\nWhile the underlying notions of diversity and coverage have been used earlier in the literature for option discovery, their combined optimization through the Determinantal Point Process is novel and returns better results than related existing methods.\n\nThe experimental evaluation is extensive and varied, showing not only learning curves but also option trajectories. \n", "weaknesses": "Only minor comments: \n\nAn analysis of computational complexity is provided in the supplementary material. It would be useful to see a short summary of that in the main paper. \n\nIn the learning curves, it would be useful to plot ceiling performance. \n\nText in Figure 1d is too small. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation. We will fix the issues that you mentioned during the final submission stage, including moving analysis of the computational complexity to the main text, highlighting the ceiling performance in the learning curves, and adjusting the text size in Figure 1(d)."}, {"review_id": "5ZbQeyMzOQ", "reviewer": "Reviewer_7oxb", "summary": "This paper addresses reward-free options discovery for RL. First, it notes that prior work would prioritize either state coverage or diversity into the options discovery procedure. Hence, it proposes a new loss function that fosters coverage and diversity simultaneously by exploiting DPPs on both the trajectories generated by the options and the states within a trajectory. Finally, it presents an algorithm to optimize this objective, which is evaluated in continuous control domains against standard baselines, such as VIC, VALOR, DIAYN, and Laplacian methods.", "questions": "The paper is an interesting contribution to a problem that is somehow far from being solved despite receiving a considerable attention recently. While the main contribution of this paper is algorithmic, it is hard to assess its value without a stronger empirical study (or more theoretical corroboration). Thus, I am currently providing a slightly negative score, even if a case for acceptance could be made and I am open to change my score after the authors' response. As is, the paper looks like a nice engineering feat to me, but lacks some convincing intuition and experiments on why all those tricks would work in general.\n\n**Algorithm**\n\n- There is one aspect that is not completely clear to me on how the loss is presented. The authors motivates the work as going beyond previous variational or Laplacian approaches with a new framework that comprises both, but then the main ingredient of the loss, i.e., $\\mathcal{L}_{IB}$, looks a standard variational loss with some variation (landmark states). Moreover, the components $\\mathcal{L}_1, \\mathcal{L}_2, \\mathcal{L}_3$ already provide incentives for coverage and diversity, so why one should also add the information bottleneck on top of them? Overall, I think that presenting this work as an evolution of variational option discovery would help its presentation.\n- From my understanding, to define the relevant DPPs a proper kernel on trajectories and states is needed. Can the authors discuss how this would be designed in the absence of any domain knowledge?\n- I am wondering whether the presented loss function induces a (hidden) RL problem or not, i.e., whether the loss function could be incorporated into a standard reward function in hindsight. Is the approach producing a set of deterministic options or the discovered options may be stochastic?\n\n**Experiments**\n\n- The presented approach is fairly complicated and I think the ablation study in Section 4.1 is not enough to state that all of the introduced ingredients would benefit the option discovery in general. It is somehow underwhelming that the paper only presents one result, a single domain and a single seed, through an illustration instead of some quantitative analysis and learning curves. I believe this does not meet the bar to motivate the added complexity of the loss function, especially on top of the $\\mathcal{L}_{IB}$ that seems to lead to a good options discovery already.\n- All of the approach is predicated on the need for coverage and diversity simultaneously, but it is hard to evaluate them beyond qualitative assessments. However, I think the paper could put more effort in designing quantitative measures to evaluate diversity and coverage.\n- I would suggest to report the learning curves with average and confidence intervals instead of one standard error, which is hardly meaningful.\n\n**Minor**\n\n- I would suggest to report the pseudocode of Algorithm 1 in the main text.\n- The overall notation, in particular the one needed to define the loss function, is sometimes convoluted.\n- Where is the DIAYN learning curve in Fig. 4b, 4c?\n- Why are the Atari results relegated to the appendix? CartPole is not an Atari game, but a continuous control task.\n- In the downstream task setting only the option selecting policy is learned? Do the authors considered also fine-tuning of the learned options?", "limitations": "The paper explicitly addresses the limitations of the presented approach in the final paragraph.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Exploiting tools from DPPs for the options discovery is interesting and, to the best of my knowledge, novel and original;\n- The experimental results are at least promising;\n- The paper includes a neat presentation of the previous works and approaches for unsupervised options discovery.", "weaknesses": "- The learning objective and the corresponding algorithm are quite convoluted. They requires several layers of approximation to make the learning tractable, as well as a handful of hyper-parameters to be tuned and the definition of a suitable kernel over trajectories and states;\n- The experimental evaluation is not thorough. Most of all, the ablation study is limited to a single run in a single domain, and leaves the reader wondering whether all of the introduced ingredients would be needed in general;\n- The intuition behind the loss function is not always pristine. It is easy to lose focus going through Section 3 of the paper;\n- The visualization of the experimental results could be further polished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Regarding loss terms (Question #1):\n\nAs noted in the first paragraph of Section 3, we need to learn an intra-option policy $\\pi_{\\theta}(a|s,c)$ conditioned on the option choice $c$. Each option choice should correspond to a specific policy. As a common practice in variational methods, this type of option-policy mapping is established by maximizing the mutual information between them, i.e., $\\mathcal{L}^{IB}$ in our case. The DPP-based loss terms, i.e., $\\mathcal{L}^{DPP}_{1:3}$, cannot be harnessed directly to obtain such a mapping.\n\nPresenting our algorithm as an evolution of variational methods would be a good idea. We provide such a view in the second paragraph of Section 3 as an algorithm overview. The variational loss term, $\\mathcal{L}^{IB}$, is used to establish the option-policy mapping, so we can learn multiple options simultaneously by introducing a conditional variable $c$. However, the mutual information objective only implicitly measures diversity of options as the difficulty of distinguishing them via a variational decoder (i.e., $P_{\\phi}$ in our paper), and does not model the coverage. As a novel extension, we propose to explicitly model and optimize the coverage and diversity of options based on DPP.\n\n## Regarding the DPP kernel (Question #2):\n\nTo make our algorithm general, we do not rely on domain knowledge when designing the DPP kernel. \n\nFor the kernel matrix on the set of states, as described in the second paragraph of Section 3.2, we need to specify the quality measure and feature vector for each state. Since this is a reward-free setting, all states are assigned with the same quality. As for feature vectors, we use Laplacian spectrum (i.e., eigenvectors corresponding to the $D$ smallest eigenvalues) of the state-transition graph, which intuitively captures connectivity among states. The same feature design has been used for spectral clustering [1], and we have shown analytically and empirically that we can generalize Laplacian option discovery with this feature embedding. This feature design is task-irrelevant. In any RL task, we can compile state transitions in replay buffers, upon which we can estimate these features, as detailed in Appendix C.3. \n\nAs for the kernel matrix on trajectories, we still assign equal quality measure to each trajectory. As in the first paragraph of Page 6, the feature of each trajectory is acquired as a sum over feature vectors of states within the trajectory. This follows the structural DPP framework [2] used for modeling sequential data. Still, the kernel matrix design does not require domain knowledge.\n\n## Regarding the option learning (Question #3):\n\nThe learning outcome is the intra-option policy $\\pi_{\\theta}(a|s,c)$. $c$ is a one-hot vector representing a discrete set of options. For each $c$, its policy is a mapping from the current state to the action, which is stochastic in continuous control tasks. \n\n$\\pi_{\\theta}(a|s,c)$ is modeled as a neural network and trained through applying the gradient $\\nabla_{\\theta}\\mathcal{L}$ (i.e., Eq. (10)). The gradient form inspires us to update the policy with Actor-Critic methods, where $A^{\\pi_{\\theta}}_m$ defines the Q-function.\n\nWhen being applied to downstream tasks, $\\pi_{\\theta}(a|s,c)$ is fixed and we only need to learn a high-level policy $P_{\\psi}(c|s)$ to select among options. For each selected option, we execute its intra-option policy for a fixed number of steps (i.e., the option horizon) before sampling a new one.\n\n## Regarding the experiments:\n\nFor quantitative results, we have provided comparisons among multiple option discovery algorithms, including the learning performance on downstream Mujoco tasks (Figure 4), effectiveness of the discovered skills in 3D Mujoco Locomotion (Figure 5) and OpenAI Gym tasks (Figure 8 in Appendix D.3). Besides, we provide detailed analysis on the learned prior network (Figure 6 in Appendix D.1).\n\nThe introduction of each objective term is intuitive. $\\mathcal{L}^{IB}$ is for establishing the option-policy mapping and implicitly encouraging the diversity, $\\mathcal{L}^{DPP}_{1}$ is for improving the coverage of each option trajectory, while the other DPP terms work together to explicitly model and optimize the option diversity. \n\nFor more convincing ablation study, we provide new quantitative results in the global response as a PDF. We propose using the distribution of final locations within option trajectories to measure the diversity and coverage, as in [3]. \n\n## Regarding the minor issues:\n\nWe will move the pseudocode to the main text since we get an extra page in the final version.\n\nThe learning curves of DIAYN in Figure 4(b)(c) are blocked by the ones of other algorithms. The options learned with these algorithms can hardly lead the agent out of the inner room in Figure 4(a) to reach the goal area and get any reward signal.\n\nCartPole is not an Atari game like the other two in Figure 8. We will fix the benchmark name as OpenAI Gym and move Figure 8 to the main text.\n\nIn the downstream task setting, only the option selecting policy is learned. We do not fine-tune the options in this stage, because this is for evaluating the discovered options in the previous stage and we need to keep them fixed in downstream tasks to keep comparisons fair.\n\n## Regarding the complexity of the proposed algorithm (Weakness #1):\n\nWe have provided a discussion on this in the global response.\n\n## References:\n\n[1] Ng, Andrew, Michael Jordan, and Yair Weiss. \"On spectral clustering: Analysis and an algorithm.\" Advances in neural information processing systems 14 (2001).\n\n[2] Kulesza, Alex, and Ben Taskar. \"Structured determinantal point processes.\" Advances in neural information processing systems 23 (2010).\n\n[3] Achiam, Joshua, Harrison Edwards, Dario Amodei, and Pieter Abbeel. \"Variational option discovery algorithms.\" arXiv preprint arXiv:1807.10299 (2018).\n\n"}, {"review_id": "F6qjsRmACG", "reviewer": "Reviewer_iqV6", "summary": "The paper introduces an unsupervised option discovery framework based on a combination of Determinantal Point Process and Laplacian spectral features. The main idea is to combine variational methods and  Laplacian methods in order to control for coverage and diversity of the options. The proposed method has been validated experimentally on Mujoco 3D navigation environments where it shows superior performance to other approaches. Further experiments have been done on Atari environments as well.", "questions": "line 112: the explanation of this Gram matrix seems lacking, for instance the quality measure is just introduced in the text here and used once more later, without any explanation how it related to reward and the DPP probability of a subset.\n\neq.3: it is not clear to me from this equation that you are doing MAP inference,  can you specify in clear terms what is the posterior here and what is the prior (also in the paper)? \n\neq. 4: what is being maximized over here? And a follow-up, in which sense is beta a Lagrange multiplier? What is the constrained optimization problem that is being solved here, can you actually write it this way? Please clarify this in your response and ideally in the main text.\n\nline 219: the notation here is confusing, is this to define a conditional random variable given s_0 and c? (the trajectory). Wouldn’t it be better to just define this as sampled from a conditional distribution, then take the expectation in eq.7 over it. (might be less confusing)\n\neq.8: same comment as for line 219. \n\neq.9: perhaps you should consider putting the minus sign into the second loss, so that it remains a proper loss (something that you want to minimize) and adjust the explanation.\n\nfigure 3 caption - “in the normal setting”\n\nthe legends in figure 4 are not well visible and the fonts are off. I suggest you place the legends outside of the figure.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed combination of DPP and Laplacian features is reasonable and shows promising results. The novelty stems mainly from the modified DPP kernel similarity matrix which makes use of the Laplacian spectrum. I also think that maximizing the cardinality of the the landmark set as a diversity signal is a nice idea.\n\nAll components that were introduced in the method are well argued. Especially the overarching motivation of maximizing coverage and diversity in the same time (reaping the benefits of variational and Laplacian methods)\n\nExperiments are convincing.", "weaknesses": "At some points the paper lacks clarity, for example in the exposition of the DPP, terms were introduced that were not properly explained and that I would not consider common knowledge.\n\nSome probabilistic framing that was used in the paper was off, but we can clarify this in the rebuttal phase hopefully.\n\nThe Atari experiments should appear in the main paper in some form, since they are already announced in the abstract.\n\nAs the authors have already noted in the paper, the method needs balancing of 3 terms in the objective which might make it impractical, however the hyperparameters are stable across different environments (shows robustness).\n\nNo significant theoretical insights, rather a combination of existing works in order to devise and option discovery algorithm.\n\nThe writing in general could be improved, I found it a bit hard to keep track of all the introduced terms and the connection to the main idea of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Regarding the Gram Matrix (Question #1): \n\nAs introduced in Section 2.2, the Gram Matrix includes the quality measures $q$ and normalized vectors $\\vec{b}$ for each element in the set. From Eq. (1), we can see that the sampling probability is proportional to the squared volume of the parallelepiped spanned by the columns $q_i\\vec{b}_{i}$, for $i$ in the sampled subset. Thus, elements with more orthogonal feature vectors and higher quality values are more probable to be sampled as a subset.\n\nIn RL tasks, we need to assign quality measures and features for each state. States with higher expected returns should be visited more frequently and thus be assigned with higher quality values. However, in our reward-free setting, we do not have prior knowledge on the quality of states, so we define equal quality measures to each state as 1, as mentioned in Section 3.2.\n\n## Regarding Eq. (3) (Question #2):\n\n$P_{L(\\mathcal{W})}(\\mathbb{W}=W)=P(\\mathbb{W}=W|\\mathbb{L}=L(\\mathcal{W}))$ denotes the probability of sampling the subset $W$ out of the universal set $\\mathcal{W}$ given the definition of the kernel matrix $L(\\mathcal{W})$. With such a conditional model, the problem to find the set $W \\subseteq \\mathcal{W}$ with the highest probability, i.e., Eq (3), is referred to as maximum a posteriori (or MAP) inference, as defined in the first paragraph of Section 2.4.5 in [1]. We will clarify this in the main text during the final submission stage.\n\n## Regarding Eq. (4) (Question #3):\n\nOur goal is to learn a policy $\\pi_{\\theta}$ and a prior $P_{\\omega}$ which condition on the option choice $c$. $c$ should be maximally expressive about the landmark states $G$ induced by $\\pi_{\\theta}$ and $P_{\\omega}$, while being compressive about the whole trajectory $\\tau$ to eliminate redundant information. According to the Information Bottleneck framework [2], this can be realized through: \n\n$\\max_{\\theta, \\omega} \\mathbb{E}_{s_0 \\sim \\mu(\\cdot)} I(c, G|s_0;\\theta, \\omega)$ \n\n$I(c, \\tau|s_0;\\theta, \\omega) \\leq I_{ct}$\n\nwhere $I_{ct}$ is the information constraint. Equivalently, with the introduction of a Lagrange multiplier $\\beta \\geq 0$, we can optimize: $\\max_{\\theta, \\omega} \\mathbb{E}_{s_0 \\sim \\mu(\\cdot)} \\left[ I(c, G|s_0;\\theta, \\omega) - \\beta I(c, \\tau|s_0;\\theta, \\omega) \\right]$. Thanks for the advice. We will add this to the main text during the final submission stage.\n\n## Regarding Eq. (7)-(9):\n\n$\\vec{\\tau}_{(s_0, c)}$ denotes a set of $M$ sampled trajectories subject to the option choice $c$ and starting from $s_0$. We will adopt your suggested modifications to Eq. (7) - (9) for better explanation.\n\n## Regarding Figure 3 and 4:\n\nThank you for your careful check. We will fix them during the final submission stage.\n\n## References:\n\n[1] Kulesza, Alex, and Ben Taskar. \"Determinantal point processes for machine learning.\" Foundations and Trends® in Machine Learning 5, no. 2–3 (2012): 123-286.\n\n[2] Alemi, Alexander A., Ian Fischer, Joshua V. Dillon, and Kevin Murphy. \"Deep Variational Information Bottleneck.\" In International Conference on Learning Representations, 2017.\n\n"}, {"review_id": "4wWmTy7XXl", "reviewer": "Reviewer_vq5Y", "summary": "This paper introduces a novel framework for unsupervised option discovery by utilizing Determinantal Point Process (DPP) to quantify and optimize both the diversity and the coverage of the learned options. The proposed unified option discovery framework captures the advantages of both variational and Laplacian-based methods, which is the major tools for existing unsupervised option discovery approaches. The experiment results in both MuJoCo and Atari demonstrate the superiority of the proposed algorithm.", "questions": " ", "limitations": " ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation to propose the unified algorithm framework is convincing and the paper is well-written and easy to follow. The author well illustrates the main idea of this paper using a toy example. \n2. The proposed option discovery framework unifies both variational and Laplacian-based methods and enables explicit maximization of diversity and coverage of the options.\n3. Though DPP is widely used in methods to promote diversity, it is the first work to adopt it into option diversity.\n4. Both the theoretical and experimental results show the superiority of the algorithms.", "weaknesses": "1. The major concern to me is the application of the proposed framework. In Equ 9. there are three hyper-parameters in the loss function. How to tune these hyper-parameters?  In L586 you say fine-tune important hyperparameters using a sequential, greedy method based on options’ visualization, such as in Fig2. Could you provide more details? \n2. DPP is widely used in the work to promote diversity. It would be better to discuss them in related work, e.g., in promoting diverse policies in population-based RL[1, 2], diverse policies in games [3], recommendation diversity [4], etc. \n3. Some theoretical results can be highlighted (such as using a Proposition station) in the main text. \n4. In Sec4, instead of some visualization results, are there some diversity metrics that could be proposed to measure the diversity? It would be better to see these numerical results in the main text. \n\n[1] Jack Parker-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems, 33:18050–18062, 2020.\n\n[2] Wu S, Yao J, Fu H, et al. Quality-Similar Diversity via Population Based Reinforcement Learning. In The Eleventh International Conference on Learning Representations, (2023).\n\n[3] Perez-Nieves, Nicolas, et al. \"Modelling behavioural diversity for learning in open-ended games.\" International conference on machine learning. PMLR, 2021.\n\n[4]. Chen, L., G. Zhang, E. Zhou. Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In Advances in Neural Information Processing Systems 31, NeurIPS 2018, pages 5627–5638. 2018.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Regarding fine-tuning the hyperparameters:\n\nAs noted in the paper, the crucial hyperparameters are $\\beta,\\ \\alpha_{1:3}$ in Eq. (4) and (9) which control the importance of each objective term, relating to diversity and coverage. Conducting a grid search on the set of parameters can be exhaustive. Therefore, we follow the process of the ablation study shown in Figure 2, add objective terms and adjust their corresponding weights one by one. In particular, in Figure 2(e), we retain only the $\\mathcal{L}^{IB}$ objective and select its weight $\\beta=10^{-3}$ from five possible choices: $1, 10^{-1}, 10^{-2}, 10^{-3}, 10^{-4}$, guided by the visualization results. Next, for Figure 2(f), we introduce $\\mathcal{L}^{DPP}_1$ and fine-tune the corresponding weight $\\alpha_1$ while keeping $\\beta$ fixed at $10^{-3}$. Last, we incorporate $\\mathcal{L}^{DPP}_2$ and $\\mathcal{L}^{DPP}_3$ and adjust $\\alpha_2$ and $\\alpha_3$ accordingly, while keeping $\\beta,\\ \\alpha_1$ fixed. Note that the final two terms must work in tandem to ensure that the discovered options exhibit diversity across different options and consistency for a specific option choice. \n\nAfter the fine-tuning, we set $\\beta=10^{-3}, \\alpha_1=10^{-4}, \\alpha_2=10^{-2}, \\alpha_3=10^{-2}$. It is worthy noting that our evaluations across various challenging RL tasks utilize the same hyperparameter set, highlighting its robustness. This is because our proposed (DPP-based) coverage and diversity measures are task-agnostic and universally applicable to RL tasks.\n\n## Regarding related works on DPP:\n\nWe will add the following literature review on applying DPP to diversity enhancement:\n\nDeterminantal Point Processes (DPPs) have found applications across a wide array of domains to promote diversity due to their unique ability to model diverse subsets. Originating from quantum physics, DPPs were introduced to the machine learning community by Kulesza and Taskar [2], whose tutorial highlighted the potential of DPPs for promoting diversity. In information retrieval tasks, Wilhelm et al. [10] and Chen et al. [11] have demonstrated the utility of DPPs in diversifying the output of recommendation systems.  In Computer Vision, Gong et al. [3] and Kim et al. [4] utilized DPPs in video summarization and object detection, respectively, to reduce outcome redundancy. In Natural Language Processing, Perez-Beltrachini et al. [5] exploited DPPs to select relevant and diverse content for neural abstractive summarisation, and Song et al. [6] applied them to model the query-level and system-level diversity in neural conversation systems. Expanding on this theme of diversity, DPPs have been extensively applied in reinforcement learning, particularly in promoting diverse policies in population-based RL [7, 8], and diverse policies in games [9].\n\n## Regarding the theoretical results:\n\nThanks for your advice. We will highlight the variational lower bound of the Information Bottleneck objective (i.e., Eq. (5)) and the unbiased gradient estimators for the prior network and intra-option policy (i.e., Eq. (10)-(12)), and formalize them as propositions in the final version.\n\n## Regarding the diversity metrics:\n\nIn Figure 5(b), we utilize the standard deviation of trajectory rewards corresponding to different options as quantitative measures for the option diversity. This measure has been used in previous works, such as [1].\n\nFor more convincing ablation study, we provide new quantitative results in the global response as a PDF. We propose using the distribution of final locations within option trajectories to measure the diversity and coverage, as in [12].\n\n## References:\n\n[1] Eysenbach, Benjamin, Abhishek Gupta, Julian Ibarz, and Sergey Levine. \"Diversity is All You Need: Learning Skills without a Reward Function.\" In International Conference on Learning Representations. 2018.\n\n[2] Kulesza, Alex, and Ben Taskar. \"Determinantal point processes for machine learning.\" Foundations and Trends® in Machine Learning 5, no. 2–3 (2012): 123-286.\n\n[3] Gong, Boqing, Wei-Lun Chao, Kristen Grauman, and Fei Sha. \"Diverse sequential subset selection for supervised video summarization.\" NeurIPS, 2014.\n\n[4] Kim, Nuri, Donghoon Lee, and Songhwai Oh. \"Learning instance-aware object detection using determinantal point processes.\" Computer Vision and Image Understanding 201 (2020): 103061.\n\n[5] Perez-Beltrachini, Laura, and Mirella Lapata. \"Multi-document summarization with determinantal point process attention.\" JAIR 71 (2021): 371-399.\n\n[6] Song, Yiping, Rui Yan, Yansong Feng, Yaoyuan Zhang, Dongyan Zhao, and Ming Zhang. \"Towards a neural conversation model with diversity net using determinantal point processes.\" AAAI, 2018.\n\n[7] Parker-Holder, Jack, Aldo Pacchiano, Krzysztof M. Choromanski, and Stephen J. Roberts. \"Effective diversity in population based reinforcement learning.\" NeurIPS, 2020.\n\n[8] Wu, Shuang, Jian Yao, Haobo Fu, Ye Tian, Chao Qian, Yaodong Yang, Qiang Fu, and Yang Wei. \"Quality-Similar Diversity via Population Based Reinforcement Learning.\" ICLR, 2022.\n\n[9] Perez-Nieves, Nicolas, Yaodong Yang, Oliver Slumbers, David H. Mguni, Ying Wen, and Jun Wang. \"Modelling behavioural diversity for learning in open-ended games.\" ICML, 2021.\n\n[10] Wilhelm, Mark, Ajith Ramanathan, Alexander Bonomo, Sagar Jain, Ed H. Chi, and Jennifer Gillenwater. \"Practical diversified recommendations on youtube with determinantal point processes.\" CIKM, 2018.\n\n[11] Chen, Laming, Guoxin Zhang, and Eric Zhou. \"Fast greedy map inference for determinantal point process to improve recommendation diversity.\" NeurIPS, 2018.\n\n[12] Achiam, Joshua, Harrison Edwards, Dario Amodei, and Pieter Abbeel. \"Variational option discovery algorithms.\" arXiv:1807.10299 (2018).\n\n\n"}, {"review_id": "SO8UFpaZcj", "reviewer": "Reviewer_6F6e", "summary": "This paper focuses on unsupervised option discovery. It uses the framework of Determinantal Point Processes (DPP) with the aim of combining the advantages of variational and Laplacian-based methods, and unify the desiderata of coverage and diversity of the learned options. Empirical validation shows the benefits of the approach over baselines in continuous control tasks. ", "questions": "- Could the authors provide a rigorous/mathematical definition of what they mean by 'coverage' throughout the paper. Is it in terms of entropy of states visited by the options H(S)? If so, then it's a term explicitly optimized by diversity I(S,Z) = H(S) - H(S|Z), which would make confusing the statement that \"variational option discovery maximizes the diversity of the options through a mutual information loss (while ignoring coverage)\" (or maybe the authors mean that optimizing MI exactly is difficult and the approximations performed in the literature tend to have poor coverage, which is different from arguing that the targeted objective ignores coverage in the first place). Also, using a Laplacian-based idea that reduces the cover time of the graph induced by the random policy may be a poor proxy of state space coverage in the entropic sense, while some diversity-based works like [6-8] explicitly target this component with good empirical results. As for the coverage visualizations, Figure 1) b) is said to improve coverage but the options are all going to the same corridor, which does not look desirable in terms of state space coverage. Meanwhile on Figure 3, the paper implies that options learned by (c) are more \"diverse\" and \"beneficial for various downstream tasks\" than (a) or (b), although one may argue otherwise, as the latter show less clutter around the initial state and attain more distant regions of the state space. Thanks for the clarifications.\n- Isn't the evaluation on Appendix D.3 on OpenAI Gym rather than Atari? (Is Cartpole an Atari game?)\n- Although there is a computational complexity discussion in Appendix C.4, could you elaborate more on the scalability of the approach and for example provide numbers on its computational requirements compared to VIC/DIAYN given the same number of environment interactions?\n- As first observed in the DIAYN paper, fixing the prior distribution (over option choice at the initial state) rather than learning it prevents a collapse to sampling only a handful of skills (as it can occur for VIC), and this has become standard practice in most subsequent works (although it is a loose lower bound on the original MI objective that should also optimize for the prior distribution). Here you explicitly learn the prior distribution, which is an interesting but undiscussed choice, could you explain more if, and why, you can overcome the aforementioned collapse? ", "limitations": "A limitation is discussed in Section 5. Not applicable regarding potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The idea of adopting DPP for option discovery is novel and quite interesting. Ensuring coverage and diversity has been a challenging open question in the unsupervised RL community and the use of DDP is a mathematically clever way to tackle it. The fact that the proposed approach seeks to capture advantages of both variational and Laplacian-based methods, usually part of distinct streams of research, also has a unifying value.\n- The paper is quite clear, well motivated and well written.\n- Experiments show improvements over baselines like DIAYN.", "weaknesses": "- Some related work is missing, including more recent and improved variational methods, such as [1-6]. It would in particular be valuable to discuss the connections with option-discovery approaches like [6-8] that build on the idea of Maximum Entropy Exploration and explicitly seek to optimize coverage, since the latter is a key feature targeted in the paper; see also my first question below. \n- The proposed method is quite complicated, with somewhat ad hoc design. While I appreciate the effort to isolate each desiderata (coverage/diversity, intra/inter-option), the final objective function in Eq.(9) is rather involved. In particular, the choice of hyperparameters to trade-off each term looks non-trivial, as acknowledged in the last section of the paper. The method seems quite computationally involved compared to standard variational approaches, and it is unclear how it would scale to more complex setups (e.g, longer horizon, more skills, visual domains).\n- The empirical part of the paper could be improved. There have been numerous option-discovery works that clearly outperform VIC/DIAYN and it would be relevant to compare to such stronger baselines. For example: DISDAIN [5], EDL [7] (with SMM [6] instead of the oracle version, despite the fact that it is a 'trajectory-first' method as categorized in the paper), DADS (despite the author's argument of distinction between model-free / model-based). As a small side note, it's also nice to add the random policy as a 'free' baseline (as it sometimes outperforms VIC/DIAYN in coverage objectives).\n- Very minor typos: 'extracts' (l.51), 'generalizes the\" (l.202), 'long-horizon' (l.251)).\n\n[1] Fast task inference with variational intrinsic successor features, Hansen et al., ICLR 2020\n\n[2] Relative variational intrinsic control, Baumli et al., AAAI 2021\n\n[3] Entropic desired dynamics for intrinsic control, Hansen et al., NeurIPS 2021\n\n[4] Direct then diffuse: Incremental unsupervised skill discovery for state covering and goal reaching, Kamienny et al., ICLR 2022\n\n[5] Learning more skills through optimistic exploration, Strouse et al., ICLR 2022\n\n[6] Active Pretraining with Successor Features, Liu and Abbeel, ICML 2021\n\n[7] Efficient Exploration via State Marginal Matching, Lee et al., arXiv 2019\n\n[8] Explore, discover and learn: Unsupervised discovery of state-covering skills, Campos et al., ICML 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Regarding the definition of option coverage (Question #1):\n\nIn our paper, coverage is a property defined w.r.t. a single option. It refers to the expected number of landmark states (i.e., clusters of states) traversed by an option trajectory. It is defined as $f(\\tau)$ in Eq. (6). We view states in a trajectory as the universal set $\\mathcal{X}$. The expected cardinality of a set sampled from $\\mathcal{X}$ under a DPP, i.e., $f(\\tau)$, reflects the number of modes (i.e., landmark states) contained in the trajectory.\n\nBy (a) maximizing coverage of each single option and (b) maximizing diversity among different options in the meanwhile, the overall span of all options in the state space can be maximized. The \"coverage\" in our paper does not refer to the span of all options and so we do not use entropy of states as the coverage measure.\n\nIn Figure 1(b), options optimized for (single-option) coverage all enter the right corridor, allowing each one’s trajectory to visit more landmark states and thus achieving better (single-option) coverage compared with the ones in Figure 1(a). In Figure 3(a)(b), we show the learned option trajectories starting from different locations (i.e., yellow points), while in 3(c), we only show trajectories starting from the center point. Options learned in (c) can lead the agent to multiple directions from a starting point, showing more diversity.\n\n## Regarding complexity and scalability of ODPP (Weakness #2, Question #3):\n\nPlease refer to the global response at the top.\n\n## Regarding the prior network (Question #4):\n\nLearning a prior network provides a tighter lower bound on the original MI objective. In Figure 6 of Appendix D.1, we show that the learned prior network can be used as initializations to aid downstream tasks.\n\nPrevious variational methods choose to fix the prior distribution to avoid a collapse for the prior network to sample only a handful of skills. Our algorithm pretends that because our algorithm additionally introduces three DPP-based terms to explicitly maximize the coverage and diversity of the learned options. With $\\mathcal{L}^{DPP}_{1:3}$, each option is expected to cover multiple state clusters with a long range and different options tend to visit different regions in the state space. In this case, the prior network would tend to select multiple diverse skills to improve the learning objective (i.e., Eq. (11)) rather than sampling only few of them.\n\nThe collapse happens because the mutual information objective only implicitly measures option diversity as the difficulty of distinguishing them via the variational decoder and does not model the coverage, as noted in Section 3. This motivates us to introduce explicit diversity and coverage measures as regularizers and enhancement.\n\n## Regarding related works (Weakness #1):\n\nHere, we provide comparisons of our algorithm with more recent variational option discovery methods. (This is a simplified version due to the word count limit. We can provide the detailed version in the discussion stage (if asked) and the final submission. [1-8] refers to papers listed by the reviewer.)\n\nIn  [1], the authors focus on alternative approaches to leverage options learned during the unsupervised phase, rather than new option discovery algorithms. They still adopt objectives based on Mutual Information (MI) as previous works without solving the exploration issue.\n\nThe authors of [2] propose a slightly-modified version of VIC to improve usefulness of the discovered options by introducing an extra posterior. Still, their options are not explicitly trained for better coverage/exploration.\n\nThe authors of [3] propose to replace the fixed prior distribution $P(c)$ with a fixed dynamics model over the option latent codes $P(c_{t}|c_{t-1})$. Each latent code corresponds to a sub-trajectory. By concatenating sub-trajectories, the agent can reach much further states. They only rely on MI-based objectives, so they cannot model the coverage of each option (like ours) and instead choose to chain options for better overall coverage.  The fixed $P(c_{t}|c_{t-1})$ can result in inflexibility when applying options in downstream tasks.\n\nIn [4], they employ a multi-step protocol to generate options organized in a tree-like structure. Heuristics and structural limits are involved in each step, which may hinder its generality. Also, they propose to optimize the local coverage around the final state rather than the overall trajectory coverage like ours. \n\nIn [6], they optimize the MI $I(s, c) = H(s) - H(s|c)$, where $H(s)$ is for improving exploration of the learned options. They adopt a variational posterior $P_{\\phi}(s|c)$ to estimate $H(s|c)$. Learning $P_{\\phi}(s|c)$ can be challenging when the state space is high-dimensional, compare with $P_{\\phi}(c|s)$ used in our paper, which can hinder the optimization.  Further, in DADS, they categorize algorithms utilizing $I(s, c) = H(s) - H(s|c)$ as the forward form of MI-based option discovery, and they empirically and theoretically show the limited capability of these algorithms for exploration even with $H(s)$ in the objective. \n\nEDL [8] disentangles exploration and skill discovery into two phases. They first train an exploration policy that induces a uniform distribution over states and can cover the state space. Then, they discover diverse skills contained in thorough samples from the pre-learned exploration policy, based on MI-based objectives. Training such an exploration policy can be challenging. In [8], they adopt SMM [7] as a solution, which requires solving a demanding max-min problem. In our paper, we tackle a more challenging scenario where the agent must learn to identify diverse options and thoroughly explore the environment at the same time, starting from a random policy, without access to expert trajectories or exploration policies.\n\n## Regarding Weakness #3:\n\nWe have offered comparisons with more advanced baselines: DADS and APS [6], in the global response as a PDF."}]

Author rebuttal:
## Regarding complexity of ODPP :

The learning target of ODPP is an intra-option policy $\pi_{\theta}(a|s,c)$ conditioned on the option choice $c$. As in Section 3.3, this policy is learned with an Actor-Critic algorithm for which the Q-function is defined as Eq. (12). This Q-function contains variational and DPP-based objectives. Compared with previous variational option discovery algorithms (e.g., DIAYN, VIC, VALOR), we additionally need to (a) sample landmark states from each trajectory and (b) calculate the DPP-related terms: $f(\cdot),\ g(\cdot),\  h(\cdot)$.

For (a), we adopt a fast greedy MAP inference algorithm for DPP [1]. As mentioned in Appendix C.2, it takes $\mathcal{O}(S^2N)$ to sample $S$ landmark states from an option trajectory of length $N$. In our setting, $N=50,\ S=10$, so the process can be done in real-time.

For (b), we need to build DPP kernel matrices, and then compute $f(\cdot),\ g(\cdot),\  h(\cdot)$ based on eigenvalues of the corresponding kernel matrix as in Eq. (6)-(8). The time complexity for eigen decomposition is $\mathcal{O}(N^3)$, where $N$ is the size of the matrix. For the state kernel matrix, $N$ is the number of states in an option trajectory (i.e., the option horizon) which we set as 50. For the trajectory matrix, $N$ corresponds to the number of trajectories collected in each training iteration, which is set as 100. Thus, $f(\cdot),\ g(\cdot),\  h(\cdot)$ can be computed in real-time.

To build the kernel matrix, we need feature vectors for each state. As introduced in Appendix C.3, the feature vector is the output of a pre-trained neural network which takes the state as input. The training of this feature function is based on state transitions in the replay buffer and only needs to be done for once or twice in the whole option discovery process, of which the time cost is within 30 minutes.

To sum up, compared with previous variational methods, we additionally introduce three DPP items to explicitly model the option diversity and coverage, of which the involvement only slightly increases the time complexity. 

## Regarding scalability of ODPP:

ODPP can indeed be adapted to more intricate setups encompassing longer option horizons, a greater number of skills, or visual domains. We elaborate on scalability of ODPP as follows and will include these discussions and numerical examples in the revised paper.

(a) The skill horizon is constrained by the MAP inference and eigen decomposition operations previously described. Given their time complexity, the skill horizon could readily be expanded from 50 to 100 or even 500. This augmentation would necessitate an additional time of $\mathcal{O}(10^{-3})$ or $\mathcal{O}(10^{-1})$ seconds per training iteration, compared with previous variational methods. These estimations are based on computations on a machine with a single Intel i7 CPU and four GeForce RTX 2060 GPUs. Note that a skill horizon larger than 100 is rarely necessary. Employing a skill with an excessively long horizon may compromise flexibility in decision-making.

(b) Compared with variational methods, our algorithm does not introduce extra limitations on the number of learned skills. Moreover, in Figure 5(c), we show that even when learning a large number of options at the same time (as much as 60), we can still get options with high quality (mean) and diversity (standard deviation) which increase during the training process.

(c) ODPP needs to learn the Laplacian feature embeddings. For visual domains, this process can incorporate a pretrained CNN model as a feature extractor, which serves to convert visual input into feature vectors. Subsequently, the original algorithm can be applied. Applications in visual domains could pose a common challenge for all option discovery algorithms and present an exciting avenue for future research.

## Regarding new results:

As required by reviewers, new empirical results are provided in the uploaded PDF, including quantitative ablation study results and comparisons with more advanced baselines on OpenAI Gym.

## References:

[1] Chen, Laming, Guoxin Zhang, and Eric Zhou. "Fast greedy map inference for determinantal point process to improve recommendation diversity." Advances in Neural Information Processing Systems 31 (2018).


Meta-review: The paper focuses on the problem of unsupervised option discovery. The authors proposes a novel and effective mathematical formulation based on DPPs to achieve diversity and coverage at the same time. The resulting algorithm successfully improves existing baselines in standard benchmarks.

After the discussion, there is general consensus that the paper investigates an important problem and it introduces a novel formulation that combines existing but often orthogonal approaches to unsupervised skill discovery such as Laplacian and mutual-information-based approaches. The empirical evaluation is overall satisfactory.

I strongly encourage the authors to fully integrate their rebuttal into the final version to properly address concerns related to the method formulation, its complexity, and the experiments.
Decision: Accept (poster)