Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper the authors prove specific regret bounds for an RL agent utilizing a particular hierarchy when solving (some) novel tasks in the domain. The authors further demonstrate that the particular hierarchy considered is recoverable, and present a method for doing so. 
main_review: As the authors themselves point out, while there has been much work in HRL and many methods proposed for how hierarchical structure might be recovered by an agent - there remain little to no formal guarantees (either for the discovery of the hierarchy, or for the performance on novel tasks using the hierarchy). The current paper might therefore constitute an important contribution to an at-present poorly understood area.

I found the paper to be generally well written, albeit perhaps not so well presented. In particular, it seems that in order to get any traction with the problem the authors had to build up a large number of loosely justified assumptions building up to a result which is difficult to reason about given the afore mentioned setup. A clearer presentation might've been to _assume_ the existence of the latent hierarchy (or better yet a comparable structure more closely related to the existing literature) and then prove the regret bounds. And then separately (in a follow on paper or in the appendix) note that the assumed hierarchy is in fact recoverable.

I have some concerns with the specific assumptions / constructions that the paper builds up en-route to it's final result:
- the authors first introduce the notion of a 'latent hierarchy' defined, loosely speaking, in terms of entrance and exit states. While this definition is appealing in the rooms domain I am not convinced about its generality. I did however appreciate the author's attempts to at least somewhat address this question in their consideration of the Alchemy benchmark. Nevertheless this setup feels particularly geared towards domains with obvious bottle-neck states (and there are a number of other papers whose methods would recover the bottle necks at least in this domain). It's worth noting that this sort of condition doesn't lend itself naturally to a description of hierarchy in trivial open domains (like a 1d chain or empty room).
- while some notion of 'coverage' is a typical requirement, I found the proposed 'optimistic imagining' largely unprincipled. The authors first defined the notion of /alpha-importance (ok), then noted that it doesn't work in the simple rooms domain and so propose an alternative definition that does work in the rooms domain... but it's generality remains completely unclear (my intuition is, again, that is probably unique to domains with single bottleneck states).
- the authors propose an algorithm by which the latent hierarchy is recoverable, but it seems that in order to implement it (phase 2) requires that the agent explore in a reward-free way in order to determine the full transition dynamics. That is to say that the proposed algorithm indeed demonstrates that the latent hierarchy is recoverable, but not practically so. Given the paper's earlier assertion that the latent hierarchy they define suggests a natural set of options policies, I wonder whether the whole first part of the paper might be done away with, and the key result demonstrated under the assumption that the option policies are already provided? (in line with my earlier suggestion)
- the key results establish regret bounds for an agent utilizing the latent hierarchy when performing novel tasks... but critically these tasks must themselves satisfy a number of additional conditions - in particular the tasks must be 'hierarchically compatible'. This would seem to exclude the vast majority of tasks (to see this in the rooms domain it seems it would suffice for one to just consider the set of tasks with |S|-choose-k terminal states with equal reward).

And so, in summary, it seems that the key result is established only for a new definition of what constitutes a hierarchy, where the meta-RL tasks satisfy a bespoke definition of coverage, and is then applicable only to a small percentage of tasks (even in the single motivating domain).

With all that said, I think we desperately need more stable theoretical footing in HRL. I would encourage the authors to consider a reframing of their work addressing the separate contributions separately, and hopefully in more generally applicable ways.
summary_of_the_review: An interesting paper proving regret bounds in a meta-learning HRL setting. However, in order to get any traction on the problem, the authors seem to need to make a large number of unprincipled assumptions (and introduce many novel definitions) such that the general interest / applicability of results is in questions.

A reframing of the results in which the authors present the key contributions separately would likely result in a much more impactful contribution.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel formulation  to analyze the provable benefits of hierarchical RL algorithms. Based on this new formulation of hierarchical structures, they propose new algorithms to learn the latent hierarchy and apply the extracted hierarchy on the downstream tasks. Under several assumptions, they prove that their algorithms enjoy better regret or sample complexity bounds than brute-force methods.
main_review: The formulation of hierarchical structures (Definition 4.1) is quite interesting and covers many real situations in HRL. From the discussion on the related work, I understand that this formulation is novel enough, and the understanding of HRL is still limited. I believe that this paper can serve as a good start to the theoretical understanding of HRL. 

However, I feel disappointed that there are so many assumptions in both the main text and the appendix. Since most of these assumptions are proposed for the first time and not commonly used in the previous literature, I believe the authors should discuss more on the necessity of each assumptions. Also, there should be more discussion on whether combining these assumptions may exclude common situations in HRL. I state several problems that I am mostly concerned:
 - Assumption 5.2 seems to be made to ensure that optimistic imagination works for the latent hierarchy formulation. However, it looks artificial and I doubt whether this assumption is commonly satisfied in the HRL tasks. 
- In Assumption 6.1 you assume that only one cluster has the positive reward. Why this assumption is necessary? This is not the common case in HRL tasks, and can we remove this assumption?
- There are many parameters in these assumptions such as $\alpha$, $\zeta$,$\rho$, $\tilde{H}$, $T^*_{\tilde{H}}$, $T^{min}$ ... If possible, I wonder the magnitude of these parameters in common HRL tasks, e.g. the gated four-room environment used in this paper as an example.

In section 5, the authors propose a novel algorithm to learn the transition dynamics and detect exits. Compared with the query complexity of the brute-force approach, is the complexity in Theorem 5.1 strictly better in all parameter regimes? Can you briefly explain the main difference between your algorithm and the brute-force approach?

Another minor issue is about Theorem 6.2. The regret bound in Theorem 6.2 ignores the sample complexity to learn the hierarchy oracle. If I understand correctly, the total complexity to learn both the hierarchy and the sampled task can still be exponential in $W$ in the hard instance construction. Therefore, there is actually no exponential separation between HRL methods and brute-force methods.

The paper can be further polished by fixing the typos and clarify several statements:

- The definition of Regret in Section 3: $V^*, V^{\pi}$ -> $V_1^*, V_1^{\pi}$
- Section 5.2.3, line 2: What do you mean by optimistically choosing dynamics estimates?
- Section 5.2.3, line 4: $M_t$ in Assumption 5.2, not Assumption 5.1?
- Definition 5.2: What is successful and failed termination? Are they two newly-constructed states in the definition of the new MDP? What is the definition of the distribution $\delta$? Is the input of the oracle the four-tuple $(x,f,r,\tilde{H})$? If so, how can we know $P_t$ used in the definition of $P_f$?
- Theorem 5.1: By saying query complexity, do you mean the total samples needed in all three phases (sample complexity)?
 
summary_of_the_review: Overall, I believe that the formulation and algorithms are quite novel, and the hierarchy formulation covers many real situations in HRL. The paper can be further improved by adding more explanation about assumptions and main theorems.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a theoretical analysis of hierarchical reinforcement learning in a meta-RL setting. This work is focused on a tabular  case. To quantify the importance of the state-action pair, $\alpha$-importance is introduced. Subsequently, for exit coverage, optimistic imagination is introduced. The proposed algorithm discovers exits that characterize the hierarchical structure by leveraging these concepts. It is theoretically proved that the hierarchy oracle that reduces the complexity of exploration is implementable using the proposed algorithm. In addition, the regret bound of a hierarchical oracle is theoretically proved. 
main_review: Strong points
- paper provides several interesting theoretical results

Weak points
- the study is limited to a tabular setting
- discussion on the relation to the existing methods can be improved

While theoretical analysis is limited to the tabular setting, the paper presents interesting theoretical results for HRL in a meta-RL setting. 
Although I'm not the expert in the field of the theoretical analysis of HRL, the regret -guarantee for the meta-test setting seems novel.
Similarly, it is interesting to see that it is provable that the hierarchical oracle is implementable using the proposed algorithm. 

On the other hand, I would like to see clearer connection to the existing methods. The methods for discovering the bottleneck states have been investigated for decades, and there are many ways to define the bottleneck states. I would like to encourage authors to discuss the connection between the exits found by the proposed algorithm and the bottleneck states found by the existing methods. For example, I would like to see the connection between the proto-value function and the exits found by the proposed algorithm or $\alpha$-importance used in this study.

Minor comments
- Regarding the work by Wei et al. (2020), I think that it is not very appropriate to state like "they focus on the reduction in regret when the learner already knows the decomposition." In my understanding, their work revealed the sample efficiency of HRL based on some quantities that characterize HRL and suggested what kind of structure should be used in HRL. Although this is just my opinion, please consider better way to phrase the position of the work.   
summary_of_the_review: While theoretical analysis is limited to the tabular setting, the paper presents interesting theoretical results for HRL in a meta-RL setting. To further clarify the contribution of the work, I would like to encourage the authors to deepen the discussion on the relation to the previous studies.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors develop a theoretical framework to discover the latent hierarchical structures shared across meta-training RL tasks, and propose a tractable hierarchy-learning algorithm with provable guarantees. The paper seems to be theoretically solid, and is well organized. I appreciate the proposed notions, such as latent hierarchy, $\beta$-dynamics separation, $\alpha$-importance, and so on. I believe they can provide researchers with a novel perspective for studying hierarchical RL.
main_review: However, the current version does not convince me to recommend acceptance due to the following concerns:

Q1. The authors assume that the agent has access to transition models (including transition probabilities and reward functions), but transition models are difficult to obtain especially for complex real-life environments. I, therefore, suspect whether the theory is valid for MDPs with high-dimensional state spaces and complex transition models?

Q2. The authors assume that the latent hierarchy partitions MDPs into clusters such that the non-exit dynamics is unchanged. Does that latent hierarchy exist in general meta-learning RL problems? Additionally, in many meta-learning settings, meta-training tasks do not necessarily share a common state space. I suspect whether the proposed theory and algorithms can be used in general meta-learning RL problems.

Q3. The authors make many assumptions, but never explain whether they are reasonable for realistic RL problems.

Q4. The main text does not introduce how to partition the state space into clusters, and how to optimize the high-level and low-level hierarchical policies. 

summary_of_the_review: Although the paper seems to be theoretically solid and presents many interesting notions, the current version does not convince me to recommend acceptance.
review_title: null

Meta-review: This paper studies meta-learning in hierarchical RL, where the unknown hierarchy is learned during meta-training and then applied to a test task. The authors propose an optimistic algorithm for solving this problem and analyze it. The main contribution of the paper is in the first end-to-end analysis.

This paper has three borderline reviews and one reject. Despite the differences in the scores, all reviewers share the same opinion. The idea is novel and very interesting. However, the algorithm and its analysis rely on many assumptions, many of which are introduced in this work and not properly discussed. Because of this, the paper needs a major revision and is rejected for now.
Decision: Reject