Modern complex sequential decision-making problem often requires both lowlevel policy and high-level planning. Deep hierarchical reinforcement learning (Deep HRL) admits multi-layer abstractions which naturally model the policy in a hierarchical manner, and it is believed that deep HRL can reduce the sample complexity compared to the standard RL frameworks. We initiate the study of rigorously characterizing the complexity of Deep HRL. We present a modelbased optimistic algorithm which demonstrates that the complexity of learning a near-optimal policy for deep HRL scales with the sum of number of states at each abstraction layer whereas standard RL scales with the product of number of states at each abstraction layer. Our algorithm achieves this goal by using the fact that distinct high-level states have similar low-level structures, which allows an efficient information exploitation and thus experiences from different high-level state-action pairs can be generalized to unseen state-actions. Overall, our result shows an exponential improvement using Deep HRL comparing to standard RL framework.
This paper proposes a new kind of episodic finite MDPs called "deep hierarchical MDP" (hMDP). An L-layer hMDP can be *roughly* thought of as L episodic finite MDPs stacked together. A variant of UCRL2 [JOA10] is proposed to solve these hMDPs and some results from its regret analysis are provided. 
Pros:
1. The essential result (Theorem 4.1) on the regret bound of the proposed algorithm seems correct. I have not checked the proofs in detail but in part because it does not seem surprising and that a precise assessment is hindered by many typos (see Min2 and Con2).
Cons (in descending order of their weights in my decisions):
1. The proposed hMDPs do _not_ seem to capture important features or challenges in hierarchical RL. My understanding is that the transitions in hMDPs work _like_ a clockwork (more on this in Mis6), the algorithm interacts with the sub-MDPs at each layer in turns according to their fixed horizons H_l's. This structure is very rigid temporally and seems to exclude the mentioned example of autonomous driving: the number of decision steps between intersections would be fixed.
2. There are many (typographical) errors in both the text and mathematical expressions. Some of them are more severe than others hindering understanding. 
3. Possible as a consequence of Con2, some quantities defined seem unclear or incorrect at worst. For example, the "standard regret" defined in (2) is an expectation, not a random variable as in convention.
4. There are some notable deviations from similar settings in prior works. They might be worthwhile innovations but their significance or motivations is omitted. For example, the rewards in hMDPs are defined as a function of the full state, i.e. in general not decomposable to rewards on the states of each layer, yet the analogy for hMDP is "L levels of episodic MDPs."
A non-exhaustive list of obvious mistakes/typos:
1. In the title, "Provably" -> Provable.
2. In the abstract, "often both" -> often requires both.
3. In Organization, "theoremm" -> theorems.
4. In Section 2, “between exploration” -> between exploration and exploitation.
5. Above Section 3, "carried" -> carried out.
6. Below (1), "amount reward" -> amount of reward.
7. The definition of horizon H is incorrect. Consider H_1 = 2 and H_2 = 3, the algorithm will interact with the sub-MDPs in the following order within one episode: 1, 1, 2, 1, 1, 2, 1, 1, 2. There are 9 steps not 6 = 2 * 3 as defined.
8. Section 3.3, "able accumulate" -> able to accumulate.
9. Section 3.3, the definition of V_h^\pi, there should be not \max.
10. (5), "H" -> H - h.
11. Section 6, "tabular R" -> tabular RL.
12. In References, "Posterior sampling for reinforcement learning: worst-case regret bounds" -> Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.
13. In References, "Temporal abstraction in reinforcement learning" should be cited as a PhD thesis.
Some other possible errors/inconsistencies:
1. Related work listed regret bounds from prior works (the presentation closely mirrors that of [JABJ18]) assume an episodic MDP with non-stationary transitions, i.e. P_t ≠ P_{t'} in general. However, in 3.1 the transitions are stationary. Relatedly, regardless of the stationarity of the transitions, there may not be an optimal _stationary_ policy in an episodic MDP contrary to the claim in the paper.
2. Indexing seems inconsistent near the top of page 3. The initial state is s_0 but the trajectory starts with s_1. 
3. Near the top of page 3, V_h^\pi and Q_h^\pi should sum from h'=h, not h'=1. I assume that the authors intend to define h-step values (to appear in the Bellman equations).
4. Section 3.3, what are the k's in the equations? 
5. (6), what is n(k-1, e)?
Minor (factored little to none in my decision):
1. The claim in Introduction that some games "do not require high-level planning" while others do is highly speculative and vague. Note that any policy can be written a function with codomain in the primitive actions. In fact, many people thought to solve a game like chess or Go requires some temporal hierarchy (opening, mid-game, and end-game).
2. The comparison to running UCRL2 on hMDP ignoring the given structure seems weak. Given the knowledge of the particular clockwork-like structure of hMDP at each layer (horizons, states, actions), the natural attempt would be run O(L) copies of UCRL2, one for each sub-MDP (under different terminating states of the immediately lower sub-MDP). Frankly, in my understanding, that seems to be roughly what the authors propose as the solution (thus the results unsurprising). Moreover, it is not immediately clear that UCRL2 can apply to the proposed setting of hMDP without checking regular conditions like communicating (diameter being finite).
3. The claim that RL with options “can be viewed as a two-layer HRL” needs much elaboration if not correction. Note that in the former, primitive actions are always taken in the original MDP at consecutive steps. 
4. There is a limited relevance to deep learning or deep RL central to the themes at ICLR, i.e. the general issue of representation. This work may be more suitable for other general ML venues.
Some suggestions
I agree with the authors' sentiment that our theoretical understanding of hierarchical RL is relatively limited. I applaud the authors' effort to address this limitation. But judging from this aim of advancing our theoretical understanding, I think the paper may be improved by 
1. better articulating the motivations for hMDPs (concrete examples would help)
2. contextualizing hMDPs with respect to other well-known models such as semi-MDPs (technical and precise comparison would help).
To put it in a different way, it is unclear to the readers why we want to solve this special class of hMDPs and what does hMDPs have to do with the general issues in hierarchical RL. Technically, I feel that assuming episodicity seems against the spirit of hierarchical RL where subtasks are often delimited by their subgoals instead of durations.
In conclusion, I cannot recommend accepting the current article. 
(To authors and other reviewers) Please do not hesitate to directly point out my misunderstandings if there is any. I am open to acknowledging mistakes and revising my assessment accordingly.
Post-rebuttal update:
Thank you for replying to my review and incorporating some of my suggestions into your revision. However, I found many concerns (and mistakes) unaddressed, such as Mis7. The use of driving in Manhattan as an example troubles me because even stopping for a traffic light seems to disrupt the fixed temporal hierarchy of decisions. In conclusion, I will maintain my recommendation.