A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process

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.

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. - The paper is quite clear, well motivated and well written. - 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.  - 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). - 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). - Very minor typos: 'extracts' (l.51), 'generalizes the" (l.202), 'long-horizon' (l.251)). [1] Fast task inference with variational intrinsic successor features, Hansen et al., ICLR 2020 [2] Relative variational intrinsic control, Baumli et al., AAAI 2021 [3] Entropic desired dynamics for intrinsic control, Hansen et al., NeurIPS 2021 [4] Direct then diffuse: Incremental unsupervised skill discovery for state covering and goal reaching, Kamienny et al., ICLR 2022 [5] Learning more skills through optimistic exploration, Strouse et al., ICLR 2022 [6] Active Pretraining with Successor Features, Liu and Abbeel, ICML 2021 [7] Efficient Exploration via State Marginal Matching, Lee et al., arXiv 2019 [8] Explore, discover and learn: Unsupervised discovery of state-covering skills, Campos et al., ICML 2020

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. - Isn't the evaluation on Appendix D.3 on OpenAI Gym rather than Atari? (Is Cartpole an Atari game?) - 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? - 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

A limitation is discussed in Section 5. Not applicable regarding potential negative societal impact.

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.

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. 2. The proposed option discovery framework unifies both variational and Laplacian-based methods and enables explicit maximization of diversity and coverage of the options. 3. Though DPP is widely used in methods to promote diversity, it is the first work to adopt it into option diversity. 4. 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? 2. 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. 3. Some theoretical results can be highlighted (such as using a Proposition station) in the main text. 4. 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. [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. [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). [3] Perez-Nieves, Nicolas, et al. "Modelling behavioural diversity for learning in open-ended games." International conference on machine learning. PMLR, 2021. [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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

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.

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. All 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) Experiments 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. Some probabilistic framing that was used in the paper was off, but we can clarify this in the rebuttal phase hopefully. The Atari experiments should appear in the main paper in some form, since they are already announced in the abstract. As 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). No significant theoretical insights, rather a combination of existing works in order to devise and option discovery algorithm. The 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.

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. eq.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)? eq. 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. line 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) eq.8: same comment as for line 219. eq.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. figure 3 caption - “in the normal setting” the legends in figure 4 are not well visible and the fonts are off. I suggest you place the legends outside of the figure.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

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.

Strengths

- Exploiting tools from DPPs for the options discovery is interesting and, to the best of my knowledge, novel and original; - The experimental results are at least promising; - 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; - 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; - The intuition behind the loss function is not always pristine. It is easy to lose focus going through Section 3 of the paper; - The visualization of the experimental results could be further polished.

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. **Algorithm** - 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. - 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? - 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? **Experiments** - 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. - 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. - I would suggest to report the learning curves with average and confidence intervals instead of one standard error, which is hardly meaningful. **Minor** - I would suggest to report the pseudocode of Algorithm 1 in the main text. - The overall notation, in particular the one needed to define the loss function, is sometimes convoluted. - Where is the DIAYN learning curve in Fig. 4b, 4c? - Why are the Atari results relegated to the appendix? CartPole is not an Atari game, but a continuous control task. - In the downstream task setting only the option selecting policy is learned? Do the authors considered also fine-tuning of the learned options?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The paper explicitly addresses the limitations of the presented approach in the final paragraph.

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.

Strengths

The proposed approach is intuitive and principled. While 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. The experimental evaluation is extensive and varied, showing not only learning curves but also option trajectories.

Weaknesses

Only minor comments: An 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. In the learning curves, it would be useful to plot ceiling performance. Text in Figure 1d is too small.

Questions

No questions.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Adequate.

After response

I am very sorry for the late reply. First, I want to thank the authors for their detailed clarifications, which make me feel now more confident in evaluating this paper. My feeling is that the empirical analysis could be further strengthen, but the overall contribution of this paper is original and interesting. I am raising my score accordingly.