PROVABLY BENEFITS OF DEEP HIERARCHICAL RL
Authors: Zeyu Jia
Simon S. Du
Ruosong Wang
Mengdi Wang
Lin F. Yang
Venue:  (2020)
Keywords: hierarchical model
reinforcement learning
low regret
online learning
tabular reinforcement learning

Abstract: Modern complex sequential decision-making problem often both low-level 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 model-based 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.

Under review as a conference paper at ICLR 2020
PROVABLE BENEFITS OF DEEP HIERARCHICAL RL
Anonymous authors
Paper under double-blind review
ABSTRACT
Modern complex sequential decision-making problem often requires both low- level policy and high-level planning. Deep hicrarchical reinforcement learning (Deep HRL) admits multi-layer abstractions which naturally model the policy in hierarchical manner, and it is believed that deep HRL reduce the sam- ple complexity compared to the standard RL frameworks. We initiate the study of rigorously characterizing the complexity of Deep HRL. We present model- based optimistic algorithm which demonstrates that the complexity of learning near-optimal policy for deep HRL scales with the sum of number of states 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.
INTRODUCTION
Reinforcement learning (RL) is a powerful tool to solve sequential decision making problems in vari- ous domains, including computer games (Mnih et 2013). Go (Silver et al. 2016), robotics (Schul- man et 2013). A particular feature in these successful applications of RL is that these tasks are concrete enough to be solved by primitive actions and do not require high-level planning. Indeed, when the problem complex and requires high-level planning, directly applying RL algorithms cannot solve the problem. An example is the Atari game Montezuma's Revenge, in which the agent needs to find keys, kills monsters, move correct rooms, etc. This is notoriously difficulty problem that requires more sophisticated high-level planning.
Hicrarchical reinforcement learning (HRL) is powerful framework that explicitly incorporate high- level planning. Roughly speaking, HRL divides the decision problem into multiple layers and each layer has its own state space. States in higher layers represent more abstraction and thus higher layer states some time named meta-states, When number of layers of abstraction is large, call this framework, deep hierarchical reinforcement learning (deep HRL). In deep HRL, the agent makes decisions by looking at states from all layers. The dependency high-level planning. HRL has been successfully applied to many domains that require high-level planning, including autonomous driving (Chen al., 2018). recommendation system (Zhao al., 2019), robotics (Morimoto & Doya 2001). Recently, extension to imitation learning has also been studied (Le al.,)
higher layer states represents
While being practically powerful framework, theoretical understanding on HRL is still limited. Can we provably show the benefit of using HRL instead of naive RL? In particular, what can we gain from multi-layer abstraction of deep HRL.? Existing theories mostly focus on option RL setting, which transits from the upper layer to lower layer when some stopping criterion met (Fruit al.) 2017). This is different from setting requiring horizons in each layer to be the same, which is common in computer games and autonomous driving Morcover, the number of samples needed in Fruit et al. (2017) is proportional to the total number of states and total number of actions. In our setting, both the total number of states and number actions can be exponentially large and hence their algorithm becomes impractical.
We initiate the study of rigorously characterizing the complexity of deep HRL and explaining its benefits compared to classical RI.. We study the most basic form, tabular deep HRL in which there

---

Under review as a conference paper at ICLR 2020
total L-layers and each layer has its own state space St for & E [L]. One can simply apply classical RL algorithm on the enlarged state space S S₁ x S2 x x St. The sample complexity will however depend the size of the enlarged states space |S] 11 [ In this paper, show because of the hierarchical structure, we can reduce the sample complexity exponentially, from x p (ee)) to & El= S) We achieve this via model- based algorithm which carefully constructs confidence of the model in a hierarchical manner. We fully exploit the structure that lower-level MDPs of different high-level states share the same transition probability, which allows us to combine the information collected at different high-level states and use to give an accurate estimator of the model for all low-level MDPs. Due to this information aggregation, able to improve the sample complexity bound. To our knowledge, this is the first theoretical result quantifying the complexity of deep HRL and explain its benefit comparing to classical RL.
Organization, This paper is organized as follows. In Section 2 we discuss related work. In Sec- tion 3 we review basic RL concepts and formalize deep HRL. In Section 4 we present our main algorithm and present its theoretical guarantees. In Section 5 we give a proof sketch of our main theorem. We conclude in Section o and defer some technical lemmas appendix.
2 RELATED WORK
We are going to provide several related literatures on tabular MDP and hicrarchical reinforcement learning in this section.
As for tabular MDP, many works focus on solving MDP with simulator which can provide samples of the next state and reward given the current stte-acction pair. These work includes Lattimore & Hutter (2012); Azar et al.] (2013); Sidffrr et al. (2018b)ar a): Agarwal et al.] (2019). Since we do not need to consider the balance between exploration and exploitation, this setting is easier than the setting of minimizing the regret.
There are also a line of work on analysis of the regret bound in RL setting. Jaksch et al. (2010) and Agrawal & Jia (2017) propose model-based reinforcement learning algorithm, which esti- mates the transition model using past samples and add a bonus to the estimation. Their algorithms achieve regret bound Ó HHASAAAA AT) and O(VH3S SH AT) respectively. Later, the UCBVI algo- rithm in Azar al. 2017) adds bonus term to the Q function directly, and achieves the regret bound Ö O(VH2SAT), which matches the lower bound when the number of episode is sufficiently large. Adopting the technique of variance reduction, the vUCQ algorithm in Kakade et al. (2018) im- proves the lower order term in the regret bound. [ et al. (2018) proposed a model-free Q-learning algorithm is proved to achieve regret bound (VV (AT)
Hierarchical reinforcement learning Barto & Mahadevan (2003) are also broadly studied in Dayan & Hinton| [193): Parr & Russell 1998); |Sutton et al. ( (199)): Dietterich| (2000): [Stolle & Precup (2002); [acon et al. (2017) Florensa al. (2017): Frans et al. (017). The option framework, which is studied in Sutton et al. (1999); Precup (2001). is another popular formulation used in hierarchical option reinforcement learning, but their analysis only applics to the setting of option RL. To our current knowledge, there is no such work
RL. In Fruit et al. (2017), the regret analysis yis is carried
analyzing the regret bound of multi-level hierarchical RL.
3 PRELIMINARIES
3.1 EPISODIC MARKOV DECISION PROCESS
In this paper, we consider finite horizon Markov decision process (MDP). An MDP is specified by tuple (S,A, A, H, r)) where S is the (possibly uncountable) state space, A is a finite action space, H E E4 is a planning horizon, P S A + A (S) is the transition function, and r : Sx A + [0, 1] is the reward function. At each state E S, an agent is able to interact with the MDP by playing an action a E A. Once an action a is played on state s, the agent receives an immediate reward r(s.a) a) E [0. and the state transitions to next state s' with probability a)) Starting
'erre we only consider cases where rewards are in [0. 1], but it is easy to know that this result can generalize rewards in different range using standard reduction Sidford al. (018a). We can also generalize our
2

---

Under review as a conference paper at ICLR 2020
from some initial state $1 S (draw from some distribution), the agent is able to play H steps (an episode) and then the system resets to another initial state $1 sampled from the initial distribution.
For MDP, goal is to obtain optimal (will be precise shortly) policy, is a function that maps each state to an action. an agent always follows the action given by a policy я, then it induces random trajectory for episode: $1,01, r1, 82, 02, P2......... ,8H an PH where 71 = r($1. a1); $2 ~ P(-1s1,a1); Q2 ~ (882), etc. The value function and Q-function at step h of a given policy is defined as (s) = E | 55 = =| and (7 a) =
S + A, which
E E sn = s, on = a) where the expectation over all sample trajectories. Then the op- timal policy, x=, defined to be the policy with largest (si ) for all 81 S. For any optimal policy, its value and Q Q-function satisfy the following Bellman equation
Vs E S, E [M):
Q%(s, a) = r(ss a) + Eess (itz(''), (i( max (7 a)
and (s) =
We consider the MDP problem in the online learning setting, where the probability transition is unknown. However, our goal is still to collect the maximum amount reward, i.e., play a policy that comparable the optimal one. Therefore, the agent needs to learn to play through trial and error, i.e. improving the policy by learning from experiences. Suppose we allow the agent to play in total K 2 episodes. For each episode, the agent is following a policy n² which computed based on her experiences collected from episodes 1,2,.... ... k 1. To measure the performance of the agent, we use the following standard regret formulation, which compares the reward collected by the agent to the performance of optimal policy.
K Σ k=1
R(K)
Note that, if the agent learns nothing, we then expect R(K) x K. But if the agent is able to learn, then the average regret, R(K) K, which measures the average error per step, goes when K becomes large. In the online MDP literature, model based algorithms (e.g. [Jaksch et al. (2010))
achieves regret R(K) s (OHHHSPPAAAH
3.2 DEEP HIERARCHICAL MDP
In this section we introduce a special type of episodic MDPs, the hierarchical MDP (hMDP). If we view them as just normal MDPs, then their state space size can be exponentially large. Formally, each hMDP consists of T, levels of episodic MDPs with the L-th level having planning horizon He- One can view the ê-th level MDP as subtask of the (f+ 1)-th level MDP. To transition between two state in (& 1)-th level, the agent needs to play episode in é-th level MDP (the state transition will be defined formally shortly). Therefore, the total planning horizon of the hierarchical MDP is H = - Hg-
For each step h in the hMDP, we can represent it by tuple (hn.... h2), where hę [He] is the step of f-th level MDP for 1 < é < L. We use H, - H; to denote the effective horizon of level f, which represents the total number of actions in A J- ... U Ar needed to be played in an episode of the full hMDP. Note that, for each the immediate next lexicographical tuple of (hı, ,h)).
(h,, .ht) E [1, H], we have + 1 (h/. ... h22 is
We now describe how the agent can interact with the full hMDP. In fact, in each step h, only an
action in one level can be played. This level is given by the function [H] - [L], formally defined as
o(h) = arg max = Hz) +
[E[L]
It characterizes the lowest level of MPDs which does not reach the last step in its horizon.
result to the setting where the reward is stochastic, since estimating the reward accurately requires much fewer samples than estimating the transition.
3

---

Under review as a conference paper at ICLR 2020
Figure I: Demonstration of Hierarchical MDP: 3 levels MDP, level (lowest level) has states, level 2 has 3 states, level 3 (highest level) has states, the total number of states is 36.
To make it formal for the state-transition, use S₁ to denote the set of states at level L, Ar to denote the set of actions at level To be convenient, we assume for every length trajectory in the f-th level MDP, the last state always falls in St C Si, which the endstates level f. At step of the full hMDP, the full state described as a length- tuple: (s1,-.., .t)) For any 5 l < (h), we immediately have 8, S is endstate of level e. Note that the total number of states the full MDP is I (Se), which is exponentially larger than the average size of a level's state space.
[L]. for any He
call as
Now we define the transition. step h of the full hMDP, the agent plays an action 0j (1)) Ao(A) for the a level MDP. The state of this MDP triggers a transition level (h):
(1) h41
(()) (hh) P (- 11 Oh Sh o(h)-1)
Note that the probability transition is determined by the state-action-ending--tee tuple (h)) (b0(h) ag 88 (h))-1), instead of single state-action pair. Moreover, all the MDPs with level lower than (h) will reset their state based on some initial distribution Pj:
Pd ())
v1 $ i (h)
and all the MDPs with level higher than (h) will keep their states unmoved.
For any given E E [L], we use Eg to denote the state-action wwwpaactiioonnnnn-stteee tuple at level E: E, = ((s((aa s01)
1-1)|s s' E St, a' E Ars f-1 E Sh-1)-
As for the reward, we use r(s ... S (h)) E [0, 1] to denote the immediate reward obtained after executing the action a <(h), We illustrate the hierarchical MDP model in Figure
An Example: Autonomous Driving. We here give our vehicle to reach the destination, while not hitting obstacles or crashing into another vehicles or pedestrians. We use the following hierarchical MDP structure to formulate this problem.
concrete example. Suppose want
4

---

Under review as a conference paper at ICLR 2020
Level represents the status (e.g. position the road, whether has obstacle in the front) of the vehicle, and the ending state represents whether the vehicle avoids all the obstacles, other vehicles, pedestrians and arrives at the end of the road. Level 2 represents the road map, and the ending state represents whether the vehicle reaches the desired position.
At each time step, if the vehicle does reach the end state of level 1, that is, it still the road and not at a crossing, then the vehicle needs to decide whether speeding up, slowing down or dodging the obstacle in the front. If the vehicle reaches the end state of level that is, arrives at the end of a road, then it needs to decide whether going straight forward, turning left or turnnng right. This process ends if and only the vehicle reaches the desired position.
3.3 DEEP HIERARCHICAL REINFORCEMENT LEARNING OBJECTIVE
Suppose the environment is an hMDP. The hierarchical structure and the reward is known but the transition models are not known. Similar to the classic RL setting, our agent needs to interact with the unknown hMDP while being able to accumulate the amount of rewards comparable to optimal policy. Our goal is design an algorithm that minimizes the regret defined in Equation (2).
Since an hMDP is very special compared to normal MDP, we redefine its related quantities here. The policy æ is a mapping from S x x St x [H] to A₁ U... AA, where क ('...... ,", h)) E A if and only if (h) = f, s "', 8f E S and s² E St, , SL. Given a policy n, and step h, the value function and Q function are again defined in Equation (T). but can be rewritten as,
Q7(s' .... ... """;"""aaa))) = =r(s', "1s""...,,;;a0
+ EgAwp! - ze p((ee) (3') 2 @h ..... ; ... , h))
3 s4, st..ttt...,,s
V/ V#+ (s)
8 = As E 1
Our objective is to find a policy nt such that the value function V is maximized for all states and steps in a horizon. We use V/ and Q7 to denote the optimal value function and optimal Q-function, which is the value function and the Q-function when applying the optimal policy T².
4 ALGORITHM
In this section, we will present model-based hierarchical reinforcement learning algorithm, to- gether with its regret bound analysis.
4.1 MODEL-BASED HIERARCHICAL REINFORCEMENT LEARNING ALGORITHM
To formally present algorithm, we first explain the high-level ideas. Note that the full model size is O (II |St| [Se]) where |Sy] is the number of states in level and |&,] is the number of state- action-endstanl tuples level f. However, we notice that there are rich structures for the algorithm to exploit: low-level MDPs corresponding to different high-level states share the same transition model. Recall that, our eventual goal to learn the hierarchical model with number of samples much less than [ Ee] To achieve this goal, we group our samples obtained from transition models by vate-action-endstaie tuple, and samples obtained from initial distributions by levels: even if the samples are collected at different high-level state-action pair, they are grouped to same set as long they come from a same Late-acttoo-eeddsttee pair. We then use the samples from a level to estimate the MDP initial distribution corresponding to that level. In effect, to estimate all the MDPs corresponding to a level accurately, we only need visit this level number of times proportional to the size of a single MDP in this level, which is far smaller than the model of all MDPs in this level combined.
Next, we explain how we can deploy the algorithm in the online setting, where we can only visit a state by following the trajectory some policy. Initially, we have no knowledge of the MDPs corresponding to each level, we just initialize each of them to arbitrary MDP. Suppose we play the whole game for K episodes, and for each episode, we play H l He steps, where Hę
5

---

Under review as a conference paper at ICLR 2020
the horizon of MDP in level L. Suppose at episode & E [K] and step [H], the transition happens at level (which means (h) E). We denote the full state we observed as (s),k)" h
and the action we take as " Then collect data samples of the form (eh (,1))) where c = (sh oh & mm.))) E & is state-action-endstate tuple at level é, and also data samples of the form (i, (1.441,.))) for every $ i s e- 1. 1. We add them to buffer, 1 Nes, corresponding to late-action-endstan tuple ei,k; and $/1,, k M, corresponding level Here M, and Ne., multisets, i.e., their elements can be repeated. We use Nen, to estimate probability transition P(.(c%,)) and Mj to estimate (-) respectively.
When new episode & starts, we first do model estimation based on all the samples collected and partitioned. Using this estimated model, value function and Q-function is computed. However, the estimation error always exists the estimated model due to insufficient samples from certain itae-aation-endstaae tuples. To account for this, we estimate the model uncertainty based on con- centration inequalities. Specifically, we add the uncertainties to our value function estimator, and use the modified value function play for the new episode. Note that doing encourages explo- ration on unexperienced state-action pairs. In fact, as we will show shortly, by using appropriate uncertainty estimation, the model becomes more accurate if the algorithm makes mistake (e.g., by playing a less-optimal action). With a pigeon hole principle argument, we can show that our algorithm achieves low regret bound.
Our model-based algorithm formally presented in Algorithm initial distribution level l as
We denote our estimator of the
#18 # Mr)
(s)
[Mrl
where #(s E Me} and MM are the number of appearance of state s in buffer Mr and the total number of states in buffer Me, respectively. We also denote our estimator of transition distribution at state-action-endstae tuple e as
Pa(sec) = #(8 E N.)
(4)
[Nvl
where # Ne} and Nel are the number of appearance of state buffer Ne and the total number of states in buffer Ne, respectively. With this these estimators, we use dynamic programming to solve for the Q-function and value functions as follows,
Qhi (t::a))))tt))))) = r(ss st:a) h,
+ E Bg P 30 - Pette (5 ,88 st,ttt....,, (5)
(s ,5 min 11,ma max
[Qh(s) ... s.....,taa)) st:aa]]
aES,
where for 1 < h < H, t o(h), E & and V #++1
(s (st.... rb) 0. Here the bonus function
b(k, e) is used to estimate the uncertainty of the Q, V estimator, which are defined as follows:
8(|Sa + log 4L2 (21266))))
((k,,lle) = H min 1,
n(k 1,e)
(6)
8(S.)) + (og(4L?|S:|le) k2
+ H min
(k 1)H,
where ô is a constant between [0, 1] to be specified before, and nikk - 1, e) is the number of times encountered iate--ctioonenndsee tuple before k--horizon These bonus functions bound the dif- ference between the estimated Q- Q-functions to the exact value (per-step) with high probability. For episode k; exploratory policy is then
T (s) 8" (,)) = arg max (0%(s',... ( ,8";;);)))))
(7)
dE

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Model-based Algorithm for Hierarchical RL
1: Input: An MDP with hierarchical structure,
2: Initialize: M2 = N₂ = 2 (elements repeatable) for every 1 S L, E. E
3: Initialize: b(k, h, l, e) as in formula (6)
4: for = do
5: Calculate Vi5 2% TH with uses formula 5
7
6: for = do
a(h)
Qh sheiaa)
7: Play action Ai.k = arg (ax.E
8:
Get next state (, s/111,155
9:
for i =1 (h) do
Put 8 s/1,, into Mg;
Put +1 into (oh
12:
Update
Pr. Pk,((s) = #1sE Mr}
VI S 1,88 E St:
MM
#(s E No}
(s(e))
LA v L, 8 Sp.
[Nve
4.2 REGRET BOUND FOR ALGORITHM
In this subsection we provide a formal guarantee for Algorithm T We present proof sketch in the next section, and the full proof is deferred to appendix.
Theorem 4.1. Suppose we run Algorithm for K 2 1 episodes on an hMDP. For k E [K]. let Th be policy played by the algorithu in episode k. Then we have, with probability at least 6,
1. R(K) = Σo [Hndla + Hy KHk 1 (1S)) + log 8-1)
E=1
where 8 E (0, 1) and R(K) is defined in Equation 2
From this theorem, observe that the regret bound only depends on Σ f-1 v Ee] where [&e] [S.||Ael|S)_. (here 18/_11 is the number of endstates at level & 1). Usually, the number of actions and the number endstates at level are much smaller than the number of states and can be viewed as constant. In this way our regret bound only depends on Σ [Sp). It means
after K = 5 R(K)/K = 0(1) (this when the agent learns a meaningful amount of information). Let us consider the full hMDP, whose state space size is I |St]. With a model based or model free algorithm like Jaksch et al. (2010); Jin et al.) (2019), the number of episodes needed would be 2 I [Se] to achieve constant average regret. Note that IT |Sy] can be exponentially larger than poly (Oly( [Se)), therefore our algorithm achieves exponential saving in the sample complexity for RL.
episodes, the algorithms achieves a constant average regret H H
PROOF SKETCH
The proof Theorem
divided into two parts. the first part, we prove that with high probability, the difference between empirical expectation and true expectation of the value function can be bounded by the bonus b. The proof of this property involves estimation the total variation (TV) distance between distribution the state space St of level é and its empirical estimation using samples. This TV distance can be bounded by O (\S/l/n) with high probability.
The second part of proof tells that if the difference between empirical expectation and true expec- tation of the value function be bounded by the bonus b then the estimator Q of function
7

---

Under review as a conference paper at ICLR 2020
is always an optimistic estimation to the true Q-function with high probability. That is, for every s' E St, we have (s'...... .'. 2 (s's'... s²). Then we can show that the regret can be upper bounded by the sum of all bonuses along the sample path. Hence bound by summing over all bonuses in each step and horizon. We notice that at level there are
obtain the regret
only |& distributions need to estimate, and each one is distribution on Sg. Therefore applying Hölder inequality we obtain the regret bound Σí E O(viS, |& (K,, where we put the dependence on H and into O.
CONCLUSION
In this paper we prove the benefit of hierarchical reinforcement learning theoretically. We propose a model-based hierarchical RL algorithm which achieves a regret bound that is exponentially better than the naive RL algrorithm. To our knowledge, this the first theoretical result demonstrating the benefit of using deep hierarchical reinforcement learning. Below we list two future directions.
Deep Hierarchical Reenforcement Learning with Function Approximation The current work focuses the most basic formulation, tabular RL: When state space large, function approximation is required for generalization across states. Recently, a line of work gave provably polynomial sample complexity upper bound for RL with function approximation under various assumptions (Wen & Van Roy, 2013) Du et al., 2019) Jiang et al.] [017)] Yang & Wang, 2019) Jin et al.) 2019). An interesting direction is to combine our analysis with these results and obtain guarantees on deep HRL with function approximation.
Deep Hierarchical Reenforcement Imitation Learning Imitation learning is another paradigm where expert's trajectories are available to the agent. Le et al. (2018) presented framework to com- bine hierarchical learning and imitation learning. However, there no formal statistical guarantee. We believe our analysis can be leveraged to understand deep hierarchical imitation learning too.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. On the optimality of sparse model-basee planning for markov decision processes. arXiv preprint arXiv: 1906-03804 2019.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In NIPS, 2017.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91()): 325-349, 2013.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. arXiv preprint 1eXivv1703.0544 2017.
Pierre-Lue Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hicrarchical reinforcement learning. Discrete event dynamic systems, 13(1-2)441-77,2000 2003.
Jianyu Chen, Zining Wang, and Masayoshi Tomizuka. Deep hierarchical reinforcement learning for autonomous driving with distinct behaviors. In 2018 IEEE Intelligent Vehicles Symposium (IV), pp. 1244. IEEE, 2018.
Peter Dayan and Geoffrey Hinton. Feudal reinforcement learning. In Advances neural infor- mation processing systems, pp. 271-278, 1993.
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of artificial intelligence research, 13:227-303, 2000.
8

---

Under review as a conference paper at ICLR 2020
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Lang- ford. Provably efficient RL with rich observations via latent state decoding. arXiv preprint arXiv:1901.09018. 2019.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical rein- forcement learning. arXiv preprint arXiv:/704.03012 2017.
Kevin Frans, Jonathan Ho, Xi Chen, Picter Abbeel, and John Schulman. Meta learning shared hierarchies. arXiv preprint wtX.v://100099700 2017.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. In Advances in Neural Information Processing Systems, pp. 316--1666 2017.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-1160 2010.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire, Con- textual decision processes with low bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1704-1711 1713. JMLR. org. 2017.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi- cient? In Advances in Neural Information Processing Systems, pp. 4863-4873, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388 2019.
Sham Kakade, Mengdi Wang, and Lin Yang. Variance reduction methods for sublinear reinforce- ment learning. 02 2018.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference Algorithmic Learning Theory, pp. 320-334. Springer, 2012.
Hoang Minh Le, Nan Jiang, Alekh Agarwal, Miroslav Dudík, Yisong Yue, and Hal Daumé, Hierar- chical imitation and reinforeement learning. ArXiv, abs/1803.00590, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Jun Morimoto and Kenji Doya. Acquisition of stand-up behavior by real robot using hierarchical reinforcement learning. Robotics and Autonomous Systems, 36(1):37-5,, 2001.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pp. 1043-1049, 1998.
Doina Precup. Temporal abstraction in reinforcement learning. 2001.
John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, and Pieter Abbeel. Trust region policy optimization. 02 2015.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pp. 5186-5196, 2018a.
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770-787. Society for Industrial and Applied Mathematics, 2018b.
David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game go with deep neural networks and tree search. Nature, 529:484 489, 01 2016. doi: f0.1038//ature16666

---

Under review as a conference paper at ICLR 2020
Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, pp. 212-223. Springer, 2002.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the I1 deviation of the empirical distribution. Hewlett-Paese Packkrd Labs, Tech. Rep, 2003.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deter- ministic systems. In Advances in Neural Information Processing Systems, pp. 3021-3029, 2013.
Lin F Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv: 10389, 2019.
Dongyang Zhao, Liang Zhang, Bo Zhang, Lizhou Zheng, Yongjun Bao, and Weipeng Yan. Deep hierarchical reinforcement learning based recommendations via multi-goals abstraction. arXiv preprint arXiv:1903.099: 09374, 2019.
10

---

Under review as a conference paper at ICLR 2020
A PROOF OF THEOREM 4.1
A. NOTATIONS FOR THE PROOF
We will specify some useful notations in the proof first.
To be convenient, we use [K Qu(K, a]
to denote Ví. (1
sk,r and
Qn(sk "kk ak) We [M] denote the |81| whose (r), , -ele-memmnnt is (a Te, "hht1'' =k,4))) Given probability distribution Pi(.) (1 S is E) over the state space S₁, use Pi denote the operator over tensors:
|S dimmenssnil tensor
L+1
P' [V [ = Σ
[k]
55. ... Tti 1
Rk,)+
(8)
S.ES
which can be understood as taking the expectation on the i-th element. We can also define the tensor product operator p @ p'2, ... @ P for different ".. ,āg as the composite operator, where each pi is operator of dimension |
A.2 PROOF OF THEOREM
We present the proof of Theorem in this subsection. In the next we use Ck,b to denote the state-action-endstae pair (s k 0g k.
We first present a lemma indicating that with high probability, the difference between the empirical expectation of the value function is bounded by the bonus.
Lemma A.1. With probability at least
8, we have
[
P @ P-(e)e) Ph.o PE-- @ Pa(-le) V 77411194 s b(k,h,e,e)
for every 2,111 - < 1 < < L and e E &c.
Proof. Given any k N 1,15 h < H, 15 E L and = (s', a', s'1 &c, we have the following estimation of error between estimated transition model and true transition model.
Pk. @ ... & Pkol & PA(le) Pk. 8 ... Pho- @ Pa((1e) V44111100
[Pkoo @
p k.o
p-11 & Pa(-le) - ... Pk.o .. Pko
... Pa(les] MM
Pk, o Pa(le) Ph. - Pa((le) V (
|| Ph.o]
8 PP. 8 pi-1 & Pit
& p @ pa((le) V [4]
(x(-le) - -Pa(lle
1 & P/.0 8 ... Pk. - Pl.0 3 ... 1 Vo+ 1k]
Ph.o - Pko/111
Ph. @ ... P Ø p
8 Pku Ø Pa(lee) V [1)00
+ Pa(-le) -Pa(1e)
P2. @ ... ph-1
Pko 8 ... Ph.o v 1x)
Σ PK. Pk.o || H Pa(tle) P&(He)) H
According to Theorem 2.1 in Weissman et al. (2003), for any 1 s 1 8- 1, with probability at least we have
8(SS, + log 8 8-1)
| - Ph:o <
(9)
(k: 1)H,

---

Under review as a conference paper at ICLR 2020
where we use the fact that till k horizons, we have KH, samples for the initial distribution of level i. Similarly, with probability at least 1 we have
8([Se) + log 8-1) n(k 1,e)
Pu((le) - Pa((e)) -
where we use nkk - 1, e) denote the number of appearance of state- aaatee-ction-endstta tuple till k - horizons (including on all 1 S i S E, we obtain
horizon). Replacing å with [41_|),||EE)])) and applying union bound
Pk.o- - Pko || H + -l-(aatte)) Pa(-)e) H
H (V 8([S5] + log( 442
H Σ min 8(|S.) log 1og(4L2|5) | k-2 /0))
<H(1
(k: e,
(A: - --
with probability at least - 5 (k Therefore, noticing that
[Pho 8 ... ... Pk.0' @ P-(e)) -Pho0 8 ... ... Pa(tle) V/+ 1k)8c S H
we choose
8(1Sg) + loloog(1 (21(12)))/55)
b(k,h, e,, = H min {1,
n(k e,
(10)
1, 8(SS.) + 1og(41.2 k2/())
+ H
min
(k: - 1)
1=1
then we have
[Ph.o & Pk. @ Px(-le) - Pl.o 3 ... Pkoot @ Pa(lle)) V V S bbk,,
((ki,,,e,))
with probability at least - (2
Finally, apply the union bound on all 1: 2 1,1 5 L and E Ec.
[Pho @ ... @ Pho1 @ Pa(-le) Pk,o @ ... Pko @ Pa((le) 14 S b(k, h,e,) holds for every 1, s < L, & with probability least 1 5.
Next we present lemma indicating that if the event in Lemma A.1 holds, then Va is always an optimistic estimation to the true value function Vi- Lemma A.2. Suppose the event in Lemma A. holds, then
holds for every S h S H and 1 S.
Proof. We will prove stronger version of this lemma. That is, for every (8t, ,t) E Si x...x Sr, we have
(s ......s)) 2 Vs'(s" s²).
We will prove this result by induction. When h = H, since V. V = 0, the inequality V >
Vī [k] already holds. Next we assume that this inequality holds for h + 1, and we consider the case
h. For any (s) s²)) E S1 x... St, af Ae, we let e = (st, a s Suppose o(h) L. and for every < E, s st are all end-state of level i. According to the events in Lemma A.1 we have
O , r(s", ... 84 s4, + [Pho .... s Pko s Pa((
V V
,84)
b(k,h,e,e)
2 rrss 54 anw + Pho 1h.0...ppf.. @ PA(-le)
( :... ,s4)
2 r(s) ah) + Ph.o 8 ... 2 P 0 Pa(.(e)
Via Vitil... ,s4)
= (kikkahfl
12

---

Under review as a conference paper at ICLR 2020
where the first inequality uses the event in Lemma A.1 and last inequality uses the fact that V A++ nonnegative operator. Therefore, have
1+11 and
[P Pk.0
Pa(tle)
.." s4) = min
max (h .... , , a'EAA
min
max Qi(s", y : H Vi (s",,... (aEEA,
,
This indicates that this lemma holds for h, which completes the induction. Hence for every 1 S h S H, this lemma holds.
Equipped with these two lemma, are ready to prove Theorem 4.1
Proof. Suppose the event in Lemma A. always holds (which will happen with probability at least - 5), then we can calculate the value function.
* [k]
V [K]
li, afi,1 - Q7 1, af,1]
[hho @ ... 8..... Pk. 8 Pa((lex.)) V 18)00 + b(k,,, e, ex,A)
[Phoo @ ... .....7 P @ Pa(-lemi)) |
(Plu & ... 2 Pko 2 Pa((lex.1) 1k)0 W 14111/000 + b(k, h, e, ek.h)
[PL,O ② ... @ P k.0 @ (.(l) - Pk.o @ Pk. @ Pa((-eex.)) 1x
(Vi++ [k] V [k]) 1h+1A b(k, C,,,,)
V Vh+ (2)00 [Ph 6 ... p & (P(()e).1) - p/,00 @ Pkoo 60 Pa(-les,))
$ (Vi++ [k] Vi (k) + E1+1,* + 2b(k h1 e (x,R),
where the last inequality uses Lemma A.2 and we define En+1, as follows:
S+I1. = [Phoo 60 ... & Pk. s Pat(lex.))
V4 With 1 (V [k]]
V ,
V O. we get Sum up this inequality for all < S H, and noticing that V
"
"
[ - -1F [R] $ Σ
Ektik + 2
bkk, h, (h), ck,));
#=1
1=1
which indicates that
K
K H
V
VITH [
VT'
En+ +
b(k h, (h)) (11)
k=1k=1
As for the first term in the above it is easy that E1+1, is martingale difference sequence with respect to h, k. Since every Én, is bounded by H = H ... Hr, according to Azuma-Hoeffding inequality we have
K
H
ch
S S4H HK log 5-1
(12)
A=
1=1
with probability at least 8.
13

---

Under review as a conference paper at ICLR 2020
Next, we will analyze the second term in equation 11
According formula equation
10
we have
K H
bki, h o (1i), ex,,))
8(1So()))
H
min
(13)
nlk - 1, (b,A)
(b)-1
8(S) + 1og((42)S,,| (k2/6))
min 1
(A: - H)
In the first summation of the above equation, the one involved with / I/nn(k 1, Ex,A) appears (k, Ck.A) n(k 1, ek,,) times. And given S S L, there exists H H, choices of such that a (h) f. For given E, there are [Ez] choices of n(k,e) where &c. Therefore, have
8([Sc) + (oL( (
min 1,
n(k: 1, ek,h)
1=1 [k]]
K
8(1Sel + log(4L2 Se E (8))
Σ
Σ
(n(k;e) e) n(k e)) min \
n(k e,
kmleEE
Σ
Σ
(n(ki, e) - nolk - 1,)))
e9Er k=1,n( LH
K Σ
8([Se) + log 1og(4L2|S
(n(k, - nlk -1,e))
n(k 1,e)
cEE; Am bmlln(k--1e)))
8([Se] + log 1og(442((S]|E) n (k; e)
18
Σ
(m(kk))) -n(k 1)
k=1,n(k-1.e)) 1.))> Hr eEE
K
n(k.e)
8(1Sa) log (4I (1812/1)))))))
Σ
j
k= j=n(k 1ee)+1
-2H + Σ n(Ke)
4L2 |12 8(SSe log((12
j
eEEt /=1
21111E + Σ
2/ 8(SS:
log
en(Kee)
e
<2f1,| 2. 8(S8
log 412 (1
Exl Σ n( EEE,
= - + 1og
Eel K(H, He41)
- (firle + KH; [ log log
where the third inequality uses the fact that for any e E Eg we have nikk e) -n(k 1,,e) < He, and the second last equation uses the fact that Eees, n(K, e) is the number of all possible action- endstate pair appears up K horizons, which is K times the number of such that (hh) l.
14

---

Under review as a conference paper at ICLR 2020
Therefore, the first term in equation B has the following estimation
S([Sau)) + 1og(4L2 1 Sa(h) Eo(k) kk2))))
H
min 1,
n(k, C2,h)
k=1h=1
Σ
H + H KHt, | + log 1og
t=1
As for the second term in equation 13
we have
K
H1
(hh)1
8([S)) + log (LL (n)) (h- - H)
H
min
1.
1=
i=1
H
8(|8:) log (ogg(4T.2) (4T.2 (8))
11
min
(k 1)H1
8(1S. + (4
Σ
Σ
min 1,
(A: - (1-1)
fmi+t (h)
L
8(1S:) + log (1..1115..11 18/122//5)
min 1,
(h: - 1)H,
im Emitl (h)
K
8(15,) log (4.(41115,.((E)) 18,1)210))))
H
H
min
1,1
11-1)
1=1 t=
K
8(18:) log 1og(411)5:1(()) (4200))))
<
Hi
(1-1)
i=1
A=
> i=1
Hil, H KH, (IS log 1)g
where the last inequality we apply the Hölder inequality. Combined previous two estimations together, we obtain that
K
H
b(ks h, ex,))
HHireeel + Hy Kile ((Sa + log d 8-1)
Σ δ (H,, + HY KH.(( + 8-1
L
0
Hy KH, |& + log 6-1)
E=1
This equation, together with equation and equation 12 indicates the regret bound
K
R(K)=
[
ViT
k=1
Hileed + H v KHr (oogo)))
log 4H HK log 8-1
E=1
Σ
HHe + Hy K KH. [1 + log 8 8-1)
E=1
15

---

Under review as a conference paper at ICLR 2020
holds with probability at least 1 - 23. This completes the proof of Theorem 4.1
16


Reviews:
[{"review_id": "rkg7VVswKB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper performs a regret analysis for a new hierarchical reinforcement learning (HRL) algorithm that claims an exponential improvement over applying a naive RL approach to the same problem. The proposed algorithm and the regret analysis performed seem rigorous and well-thought out.\n\nHowever, I think that this paper should be rejected because (1) the algorithm does not appear to be a substantial improvement over existing algorithms, (2) the paper makes strong claims about an exponential improvement over standard RL, but doesn't provide a strong benchmark to compare to, and (3) the paper is imprecise and unpolished, with many grammatical errors.\n\nI would be open to reconsidering my score if a) the authors submit a revised version with significantly cleaned up text, and b) if the authors could provide more information about how their contribution compares to the existing literature.\n\nMain argument \n\nThe paper would benefit from establishing stronger context for the central contributions of their paper. For instance, the paper begins by contrasting HRL approaches with a number of standard RL algorithms, saying that approaches such as AlphaGo do not require high-level planning. This seems surprising; many RL researchers would describe MCTS (the base of the AlphaGo algorithm) as performing planning. It would be great if the authors could go into more detail as to what they view as planning, and why AlphaGo does not do so.\n\nAdditionally, the main comparison the authors seem to make is between HRL and naive RL, which does not provide sufficient context to properly analyse their algorithm. Many algorithms are better than applying a classical RL algorithm naively. As such, it is not sufficient to show that the algorithm proposed by the authors is stronger than a naive approach; it would be better to compare the algorithm to either a) the state of the art (SOTA) approach, or b) a more credible approach than the naive one. Experimental evidence would help.\n\nOne point of comparison is Fruit et al. (2017), which is mentioned as another paper which carries out a regret analysis in a HRL setting. Fruit et al. (2017) contains a number of simple numerical simulations; a similar effort here would help.\n\nAnother issue is that the paper is confusing, with systematic grammar errors and typos. The paper would benefit significantly with some copy-editing/proofreading by a native English speaker. For instance, the title should (presumably) read \"Provable Benefits of Deep Hierarchical RL.\" Such errors appear throughout the paper. Fixing them would make the paper much easier to understand.\n\nFinally, although this did not factor into the score I awarded the paper, the terminology used by the authors is confusing, referring to their setting as \"Deep Hierarchical Reinforcement Learning.\" \"Deep Reinforcement Learning\" is a widely used term in industry, referring to algorithms that apply Deep Learning to RL problems, such as AlphaGo or DeepStack. I would encourage the authors to use a different term to describe the setting.\n\nQuestions to the authors: \n\n1) In what way is AlphaGo not doing planning? What is an example of an algorithm that does planning in a standard RL setting? e.g. what would planning look like in Go?\n2) Did you run any experiments/simulations of your work? If not, why not? \n3) Can you elaborate on what a classical RL algorithm would look like that would serve as a proper benchmark to this algorithm?\n4) In your mind, what is the SOTA algorithm for your setting?\n5) What are some simple domains that your algorithm would apply to?\n\n[0]: Moravčík, Matej & Schmid, Martin & Burch, Neil & Lisý, Viliam & Morrill, Dustin & Bard, Nolan & Davis, Trevor & Waugh, Kevin & Johanson, Michael & Bowling, Michael. (2017). DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker. Science. 356. 10.1126/science.aam6960. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SJgUpKLeqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the theoretical aspects of HRL. It provides theoretical analysis for the complexity of Deep HRL. The idea is to exploit a given action hierarchy, and known state decomposition, the fact that the high-level state space shares similar low-level structures. The final result is an exponential improvement of HRL to flat RL. \n\nOverall, the paper pursues an ambitious goal that analyses the complexity of Deep HRL. The writing is not easy to follow. I some questions and concerns as follows\n\n- I wonder why the state space must be defined in a product form? If a standard RL is used, then it could be applied directly to the state space ($S_L$) on that primitive actions operate. Hence L-1 state spaces will be discarded? I don't see why a flat RL must estimate policies for states at all levels. It looks like many later derivations based on the assumption of factored state spaces and factored transitions on different levels. In the case of factored representation, the authors should make clear assumptions and find a better way to describe the overall algorithm.\n\n- Section 3.2: the authors use time index for Q and V, does that mean all analysis is for non-stationary MDPs? This is not the assumption in Jaksch et al. (2010) and this paper. The description in this section is very confusing and contains a lot of imprecise definitions\ne.g. should H = \\prod {i=1} H_i?? is h =(h_1,...h_L) not in [1,H]? what is the definition of the immediate next lexicographical tuple? etc. The definition of \\sigma is also unclear and hard to understand.\n\n- The analysis in Section 4. and Algorithm 1 are not for Deep HRL as said in Abstract and Introduction. The analysis is based on PAC-MDP learning for models at each action level. This paper's contributions might be clearer if the authors made clearer assumptions, e.g. on action hierarchy, abstract state space structures etc..\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxd6v70YS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPros:\n\n1. 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).\n\nCons (in descending order of their weights in my decisions):\n\n1. 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.\n\n2. There are many (typographical) errors in both the text and mathematical expressions. Some of them are more severe than others hindering understanding. \n\n3. 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.\n\n4. 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.\"\n\nA non-exhaustive list of obvious mistakes/typos:\n1. In the title, \"Provably\" -> Provable.\n2. In the abstract, \"often both\" -> often requires both.\n3. In Organization, \"theoremm\" -> theorems.\n4. In Section 2, “between exploration” -> between exploration and exploitation.\n5. Above Section 3, \"carried\" -> carried out.\n6. Below (1), \"amount reward\" -> amount of reward.\n7. 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.\n8. Section 3.3, \"able accumulate\" -> able to accumulate.\n9. Section 3.3, the definition of V_h^\\pi, there should be not \\max.\n10. (5), \"H\" -> H - h.\n11. Section 6, \"tabular R\" -> tabular RL.\n12. In References, \"Posterior sampling for reinforcement learning: worst-case regret bounds\" -> Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.\n13. In References, \"Temporal abstraction in reinforcement learning\" should be cited as a PhD thesis.\n\nSome other possible errors/inconsistencies:\n1. 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.\n2. Indexing seems inconsistent near the top of page 3. The initial state is s_0 but the trajectory starts with s_1. \n3. 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).\n4. Section 3.3, what are the k's in the equations? \n5. (6), what is n(k-1, e)?\n\nMinor (factored little to none in my decision):\n1. 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).\n2. 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).\n3. 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. \n4. 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.\n\nSome suggestions\n\nI 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 \n\n1. better articulating the motivations for hMDPs (concrete examples would help)\n\n2. contextualizing hMDPs with respect to other well-known models such as semi-MDPs (technical and precise comparison would help).\n\nTo 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.\n\nIn conclusion, I cannot recommend accepting the current article. \n\n(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.\n\n\nPost-rebuttal update:\n\nThank 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper pursues an ambitious goal to provide a theoretical analysis HRL in terms of regret bounds. However, the exposition of the ideas has severe clarity issues and the assumptions about HMDPs used are overly simplistic to have an impact in RL research.
Finally, there is agreement between the reviewers and AC that the novelty of the proposed ideas is a weak factor and that the paper needs substantial revision.
Decision: Reject