Venue: ICLR 2022 Conference

Reviews:

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

* This is an interesting approach to improve unsupervised skill discovery in multiple ways: state space coverage, avoiding prespecifying the number of skills to learn, and dynamically extending episode horizons.

  Most skill discovery methods that use the mutual information decomposition of a form of $\mathcal{I}(S; Z) = \mathcal{H}(Z) - \mathcal{H}(Z|S)$ fix the distribution of $z$ and do not encourage exploration. This work suggests a workaround to explore local regions with a decoupled policy structure (direct and diffuse), which I find a meaningful contribution.

  The approach of maximizing the number of skills via the constrained objective and learning new skills on top of existing ones in the tree-structured manner is also an intriguing direction for skill discovery with less predetermined components.

* In comparison with the baseline skill discovery methods, this method shows improved state space coverage and performance empirically (see my comment about the issue with MuJoCo experiments below, though).

* The visualization and analyses provide meaningful insights. They show that the proposed method is effective for learning a set of skills covering the state space on the toy (Maze) environments (Table 2 and Fig.2). They also present how well their method can reach different goals on Bottleneck Maze before and after fine-tuning (Fig.5).

**Weaknesses**

* The diffusing with the simple random walk policy (performing uniform random actions) is one of the most basic strategy for exploration and wouldn't be very effective on many environments, as it does not necessarily lead to good (local) state space coverage. Fig.4 (a) is an example of such case. This is also mentioned by the authors in Sec.6.

* Only a few baseline methods are used for the comparison on the MuJoCo environments (Ant, Half-Cheetah, and Walker2d), considering that those environments are much more complex and closer to real-world scenarios than the Maze environments.

  More importantly, DIAYN (Eysenbach et al., 2019) and RANDOM are not a good choice of baselines for comparing state space coverages in MuJoCo control environments. The authors can check out/consider other works, such as DADS (Sharma et al., 2020) or IBOL (Kim et al., 2021).
summary_of_the_review: The authors propose an interesting approach to unsupervised skill discovery tackling multiple issues with some existing prior methods. They also provide meaningful empirical results and analyses.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a new framework for unsupervised skill discovery termed UPSIDE which aims to learn a fix set of state space covering skills that have a directed and diffusing (noisy) component, are constrained to be sufficiently discriminable and are chained together in a tree structure to enable composition. The paper shows results on grid world and continuous control environments demonstrating the effectiveness of their method. 
main_review: **Strengths**: 
This work takes a novel approach to the skill discovery problem. Instead of directly finding maximal entropy policies that act as skills, this work splits skills into directed and diffusing (exploratory) components. The paper also includes a technique for limiting the number of skills by ensuring they satisfy some minimal discriminability threshold. Finally, the method also includes a method for generating compositions of directed skills via a tree structure and then diffusing from the leaf to explore. Overall the method is novel and is appears to be supported by experimental results. 

**Weaknesses**: 
I think there are several weaknesses in the presentation and experimentation that would need to be addressed.
1. For the continuous control environments, why are there no finetuning results on the downstream tasks besides Ant? For some reason the authors report coverage and discriminator accuracy for three gym tasks: Ant, Half-Cheetah and Walker but only downstream RL results on Ant. Please report downstream results on the other two tasks as well. 
2. Why is DADS not included as a baseline? DADs has been shown to outperform DIAYN on the continuous control tasks and should certainly be compared against. 
3. I am slightly confused by the discussion regarding a fixed number of skills N - DIAYN at least doesn’t have this - it just has a skill conditioned policy with z sampled from the uniform distribution. 
   
-   Using DIAYN-Nz doesn’t seem particularly valid to me - you should compare against the original method as well for proper comparison
    
-   The authors then introduce modified variants of DIAYN (DIAYN-curr) to deal with the fact that it has a limited set of policies - which was not how the algorithm was designed to begin with. Additionally they then switch to TD3 claiming it doesn’t work well. Instead as mentioned above, please comparison against the original DIAYN codebase. 

Minor Nitpicks:
- Add some sort of visualizations of the learned skills for the continuous control environments. 
- “We optimize policies by maximizing their number under the constraint that each of them reaches distinct regions of the environment” - this sentence needs a wording fix - its a bit unclear in the abstract itself what maximizing their number means.
- Figure 5: what does UPSIDE before/after mean?
- Figure 10 or something like it should go in the main paper (it is very helpful in understanding the main idea of the work)

Overall, I recommend rejection but I am open to updating my score if my concerns are addressed. 
summary_of_the_review: Overall, the method proposed in this work is novel but the experiments, while showing performance improvements for the proposed method, do have several flaws which I point out in my review. If these issues can be addressed, I would be open to updating my score from rejection. 

=====================================UPDATE=========================================================
After discussion with the authors, I have raised my score as my experimental concerns have been addressed.
review_title: null

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

main_review: The submission has all components that make up a good paper: it reads well, describes and motivates the problem, positions itself with respect to the prior literature, covers the theory and implementation with necessary details, and compares the prior methods. I don’t have any critical concerns, and only mostly minor comments and suggestions.

I cannot fully parse the objective in Equation 2. Especially the sentence “In words, the skill is incentivized to bring the diffusing part to a discriminable region of the state space.” seems to be incorrect. The reward does incentivize the skills to stay in a discriminable region, but only the discriminability of the end of the episode should matter (not how we got there). In fact, I would expect this objective to lead to skills that try to avoid unvisited states (as those regions are indiscriminable) and the skills should be biased in already visited direction rather than being symmetrically distributed, as is the case for example in Figure 4(a). Can you elaborate on why the chosen reward works?

Regarding the experiments and comparison to DIYAN, I find it strange that the coverage of RANDOM is practically as good as DYIANs, and in the case of Ant, RANDOM actually surpasses DYIAN. The text clarifies that in the Half-Cheetah and Walker2d environments, “DIAYN policies learn to fall on the agent’s back”. This does not seem to be the case in the original DIAYN paper (https://sites.google.com/view/diayn), where the agent especially in the HalfCheetah environment is able to acquire proper gaits. Can you comment on this discrepancy?

What are the axes in Figure 4(a) and (b)? I suppose they are the xy-coordinates, in which case UPSIDE covers the space really well. Just to confirm, the discriminator gets to see the full state, not just these two coordinates?

The sparse reward tasks do not bring much new to the paper because the result is obvious from the coverage plots showing UPSIDE explores well. I would suggest using one of more standard sparse exploration tasks (e.g., SparseHalfCheetah) to better show the benefits and make the result comparable to existing literature. 

There is a missing related paper [1], which also learns unsupervised skills by fitting a distance function. They learn only a single directed policy and do not try to cover the entire state space, but their policy also includes a directed part and a diffusive part for exploration.

Equation 1 has a missing maximization operator on the right hand side of the equation.

[1] Hartikainen et al., Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery, ICLR 2020

summary_of_the_review: Good paper that has all required components. The proposed algorithm is novel, the paper provides both theoretical analysis as well as a practical version of the algorithm, and the experiments indicate substantial improvement over prior works.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a novel algorithm for learning unsupervised skills based on empowerment. Specifically, direct-and-diffuse policies are proposed that first optimize empowerment and then after a fixed number of episode steps optimize action entropy. This yields policies that go to a certain point in a directed manner and then move around that point at random. Further, the UPSIDE algorithm is based on tracking the policies with high discriminability (i.e. low H(z|x)). The algorithm keeps a set of policies that are currently above a threshold and attempts to add new policies incrementally. Finally, each new policy can be assigned a parent policy, wherein the parent policy is executed to produce the starting state for the new policy. This allows the proposed algorithm to stack policies sequentially and reach goals further away. Empirically, the algorithm achieves good performance on pointmass, cheetah, walker, and ant tasks.
main_review: 
Cons:
- The proposed method is overly complex and contains many ad hoc decisions. For instance, the iteration in Algorithm 1 seems entirely ad hoc to me.
- It is unclear how to adapt the method to a larger or a continuous space of skills, which is important for more realistic applications.
- The theoretical justification for the proposed method is weak. For instance, Lemma 1 shows that the proposed objective is a lower bound on empowerment, but the paper entirely ignores the question of whether the bound is tight (in contrast to all previous work in the area which uses tight bounds). Further, in Sec 3.4, the paper claims that the algorithm is “guaranteed to terminate with the optimal number of policies”, however, the proof ignores the fact that q(z|s) depends on the number of policies. As far as I can tell the algorithm is only guaranteed to find a “locally” optimal solution (i.e. optimal for the corresponding q), not the optimal solution.
- The empirical evaluation unfortunately suffers due to non-standard evaluation metrics. As far as I can tell, the paper does not follow any existing evaluation protocol. 

Separately from the cons, I am not convinced that the idea of performing constrained optimization (Eq P_eta) is important for the proposed algorithm. It seems that a very similar algorithm can be obtained by jointly optimizing I(x;z) and N for maximum empowerment.

Pros:
- The paper focuses on the relevant problem of improving coverage in unsupervised skill discovery
- The proposed method significantly outperforms prior work and provides important insights into what properties are important for a successful skill discovery algorithm, such as using discriminability of the final state in the trajectory and stacking skills sequentially for better exploration.
- The paper presents extensive experiments and visualizations which detail the failure points of prior work
- The paper is clearly written and technically relatively strong

summary_of_the_review: The paper has many issues and in my opinion the proposed algorithm is not viable in more complex domains. However, it is possible that some of the limitations can be lifted, such as using discrete skill variables only. Further, the paper empirically presents good performance on the challenging ant domain and contains several important insights that might be useful for the future researchers. Therefore I am leaning towards accept.
review_title: null

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

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

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