Title: PROVABLE BENEFITS OF DEEP HIERARCHICAL RL

Abstract: 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.

1. INTRODUCTION:

Reinforcement learning (RL) is a powerful tool to solve sequential decision making problems in various domains, including computer games (Mnih et al., 2013) , Go (Silver et al., 2016) , robotics (Schulman et al., 2015) . 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 is 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 to correct rooms, etc. This is notoriously difficulty problem that requires more sophisticated high-level planning.

Hierarchical reinforcement learning (HRL) is powerful framework that explicitly incorporate highlevel 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 are some time named meta-states. When number of layers of abstraction is large, we 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 on higher layer states represents high-level planning. HRL has been successfully applied to many domains that require high-level planning, including autonomous driving (Chen et al., 2018) , recommendation system (Zhao et al., 2019) , robotics (Morimoto & Doya, 2001) . Recently, extension to imitation learning has also been studied (Le et al., 2018) .

While being a practically powerful framework, theoretical understanding on HRL is still limited. Can we provably show the benefit of using HRL instead of naïve 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 is met (Fruit et al., 2017) . This is different from our setting requiring horizons in each layer to be the same, which is common in computer games and autonomous driving Moreover, 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 of 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 RL. We study the most basic form, tabular deep HRL in which there are total L-layers and each layer has its own state space S for ∈ [L] . One can simply apply classical RL algorithm on the enlarged state space S = S 1 × S 2 × • × S L . The sample complexity will however depend on the size of the enlarged states space |S| = Π L =1 |S |. In this paper, we show because of the hierarchical structure, we can reduce the sample complexity exponentially, from ∝ poly(Π L |S |) to ∝ L =1 poly(|S |). We achieve this via a 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 it to give an accurate estimator of the model for all low-level MDPs. Due to this information aggregation, we are 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 Section 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 6 and defer some technical lemmas to appendix.

2. RELATED WORK:

We are going to provide several related literatures on tabular MDP and hierarchical reinforcement learning in this section.

As for tabular MDP, many works focus on solving MDP with a simulator which can provide samples of the next state and reward given the current state-action pair. These work includes Lattimore & Hutter (2012) ; Azar et al. (2013) ; Sidford et al. (2018b; 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 a model-based reinforcement learning algorithm, which estimates the transition model using past samples and add a bonus to the estimation. Their algorithms achieve regret bound Õ( √ H 4 S 2 AT ) and Õ( √ H 3 S 2 AT ) respectively. Later, the UCBVI algorithm in Azar et al. (2017) adds bonus term to the Q function directly, and achieves the regret bound Õ( √ H 2 SAT ), 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) improves the lower order term in the regret bound. Jin et al. (2018) proposed a model-free Q-learning algorithm is proved to achieve regret bound Õ(

√ H 3 SAT ).

Hierarchical reinforcement learning Barto & Mahadevan (2003) are also broadly studied in Dayan & Hinton (1993) ; Parr & Russell (1998); Sutton et al. (1999); Dietterich (2000) ; Stolle & Precup (2002) ; Bacon et al. (2017) ; Florensa et al. (2017) ; Frans et al. (2017) . The option framework, which is studied in Sutton et al. (1999) ; Precup (2001) , is another popular formulation used in hierarchical RL. In Fruit et al. (2017) , the regret analysis is carried on option reinforcement learning, but their analysis only applies to the setting of option RL. To our current knowledge, there is no such work 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 a tuple (S, A, H, P, r), where S is the (possibly uncountable) state space, A is a finite action space, H ∈ Z + is a planning horizon, P : S ×A → (S) is the transition function, and r : S ×A → [0, 1] is the reward function. At each state s ∈ S, an agent is able to interact with the MDP by playing an action a ∈ A. Once an action a is played on state s, the agent receives an immediate reward r(s, a) ∈ [0, 1] 1 , and the state transitions to next state s with probability P (s |s, a). Starting from some initial state s 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 s 1 sampled from the initial distribution.

For an MDP, our goal is to obtain an optimal (will be precise shortly) policy, π : S → A, which is a function that maps each state to an action. If an agent always follows the action given by a policy π, then it induces a random trajectory for an episode: s 1 , a 1 , r 1 , s 2 , a 2 , r 2 , . . . , s H , a H , r H where r 1 = r(s 1 , a 1 ), s 2 ∼ P (•|s 1 , a 1 ), a 2 ∼ π(s 2 ), etc. The value function and Q-function at step h of a given policy is defined as

V π h (s) = E π H h =h r h s h = s and Q π h (s, a) = E π H h =h s h = s, a h = a

, where the expectation is over all sample trajectories. Then the optimal policy, π * , is defined to be the policy with largest V π 1 (s 1 ) for all s 1 ∈ S. For any optimal policy, its value and Q-function satisfy the following Bellman equation

∀s ∈ S, a ∈ A, h ∈ [H] : Q * h (s, a) = r(s, a) + E s ∼P (•|s,a) V * h+1 (s ), V * h (s) = max a∈A Q * h (s, a)

and V * H+1 (s) = 0.

(1)

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 is comparable to 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 ≥ 1 episodes. For each episode, the agent is following a policy π k , which is 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 an optimal policy.

EQUATION

Note that, if the agent learns nothing, we then expect R(K) ∝ K. But if the agent is able to learn, then the average regret, R(K)/K, which measures the average error per step, goes to 0 when K becomes large. In the online MDP literature, model based algorithms (e.g. Jaksch et al. (2010) )

achieves regret R(K) ≤ Õ H 2 |S| 2 |A|HK .

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 L levels of episodic MDPs with the -th level having planning horizon H . One can view the -th level MDP as a subtask of the ( + 1)-th level MDP. To transition between two state in ( + 1)-th level, the agent needs to play an episode in -th level MDP (the state transition will be defined formally shortly). Therefore, the total planning horizon of the hierarchical MDP is

H = L i=1 H . For each step h in the hMDP, we can represent it by a tuple (h 1 , • • • , h L ), where h ∈ [H ] is the step of -th level MDP for 1 ≤ ≤ L. We use H = L i= H i to

denote the effective horizon of level , which represents the total number of actions in A ∪ • • • ∪ A L needed to be played in an episode of the full hMDP. Note that, for each h

= (h 1 , • • • , h L ) ∈ [1, H], we have h + 1 = (h 1 , • • • , h L ) is the immediate next lexicographical tuple of (h 1 , • • • , h L ).

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 σ(h) = arg max ∈[L] {h = H } + 1.

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.

Figure 1 : Demonstration of Hierarchical MDP: 3 levels of MDP, level 1 (lowest level) has 3 states, level 2 has 3 states, level 3 (highest level) has 4 states, the total number of states is 36.

To make it formal for the state-transition, we use S to denote the set of states at level , A to denote the set of actions at level . To be convenient, we assume for every ∈ [L], for any Hlength trajectory in the -th level MDP, the last state always falls in S ⊂ S l , which we call as the endstates in level . At step h of the full hMDP, the full state is described as a length-L tuple:

(s 1 , • • • , s L ).

For any 1 ≤ < σ(h), we immediately have s ∈ S is an endstate of level . Note that the total number of states of the full MDP is L =1 |S |, which is exponentially larger than the average size of a level's state space. Now we define the transition. At step h of the full hMDP, the agent plays an action a

σ(h) h ∈ A σ(h)

for the σ(h)-level MDP. The state of this MDP triggers a transition at level σ(h):

s σ(h) h+1 ∼P • | s σ(h) h , a σ(h) h , s σ(h)-1 h

Note that the probability transition is determined by the state-action-ending-state tuple (s

σ(h) h , a σ(h) h , s σ(h)-1 h

), instead of single state-action pair. Moreover, all the MDPs with level lower than σ(h) will reset their state based on some initial distribution P i 0 :

s i h+1 ∼P i 0 (•) , ∀1 ≤ i ≤ σ(h) -1

, and all the MDPs with level higher than σ(h) will keep their states unmoved.

For any given ∈ [L], we use E to denote the state-action-ending-state tuple at level :

E = {(s , a , s -1 ) | s ∈ S , a ∈ A , s -1 ∈ S -1 }.

As for the reward, we use r(s

1 h , • • • , s L h , a σ(h) h

) ∈ [0, 1] to denote the immediate reward obtained after executing the action a σ(h) h

. We illustrate the hierarchical MDP model in Figure 1 .

An Example: Autonomous Driving. We here give a more concrete example. Suppose we want 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.

Level 1 represents the status (e.g. position on the road, whether has an 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 not reach the end state of level 1, that is, it still on 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 1, that is, it arrives at the end of a road, then it needs to decide whether going straight forward, turning left or turning right. This process ends if and only if 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 an optimal policy. Our goal is design an algorithm that minimizes the regret defined in Equation (2).

Since an hMDP is very special compared to a normal MDP, we redefine its related quantities here. The policy π is a mapping from

S 1 × • • • × S L × [H] to A 1 ∪ • • • A L , where π(s 1 , • • • , s L , h) ∈ A if and only if σ(h) = , s 1 ∈ S 1 , • • • , s -1 ∈ S -1 and s ∈ S , • • • , s L ∈ S L .

Given a policy π, and step h, the value function and Q function are again defined in Equation ( 1), but can be rewritten as,

Q π h (s 1 , • • • , s L ; a) = r(s 1 , • • • , s ; a) + E s1 ∼P 1 0 ,••• ,s -1 ∼P -1 ,s ∼P (•|e) V π h+1 (s 1 , • • • , s , s +1 • • • , s L ), V π h (s 1 , • • • , s L ) = Q k h (s 1 , • • • , s L ; π(s 1 , • • • , s L , h)) V π H+1 (s 1 , • • • , s L ) = 0, ∀s ∈ S , 1 ≤ ≤ L.

Our objective is to find a policy π * such that the value function V π h is maximized for all states and steps in a horizon. We use V * h and Q * h to denote the optimal value function and optimal Q-function, which is the value function and the Q-function when applying the optimal policy π * .

4. ALGORITHM:

In this section, we will present a model-based hierarchical reinforcement learning algorithm, together with its regret bound analysis.

4.1. MODEL-BASED HIERARCHICAL REINFORCEMENT LEARNING ALGORITHM:

To formally present our algorithm, we first explain the high-level ideas. Note that the full model size is

O L =1 |S ||E |

, where |S | is the number of states in level and |E | is the number of stateaction-endstate tuples in level . 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

L =1 |S ||E |.

To achieve this goal, we group our samples obtained from transition models by state-action-endstate tuple, and samples obtained from initial distributions by levels: even if the samples are collected at a different high-level state-action pair, they are grouped to a same set as long as they come from a same state-action-endstate 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 to visit this level a 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 of some policy. Initially, we have no knowledge of the MDPs corresponding to each level, we just initialize each of them to an arbitrary MDP. Suppose we play the whole game for K episodes, and for each episode, we play H = L =1 H steps, where H is the horizon of an MDP in level . Suppose at episode k ∈ [K] and step h ∈ [H], the transition happens at level (which means σ(h) = ). We denote the full state we observed as

(s 1 h,k , • • • , s L h,k

) and the action we take as a h,k . Then we collect data samples of the form (e h,k , s h+1,k ), where e h,k = (s h,k , a h,k , s -1 m,k ) ∈ E is a state-action-endstate tuple at level , and also data samples of the form (i, s i h+1,k ) for every 1 ≤ i ≤ -1. We add them to a buffer, s h+1,k to N e h,k corresponding to state-action-endstate tuple e h,k , and s i h+1,k to M i corresponding to level i. Here M i and N e h,k are multisets, i.e., their elements can be repeated. We use N e h,k to estimate probability transition P (•|e h,k ), and M i to estimate P i 0 (•) respectively. When a new episode k starts, we first do a model estimation based on all the samples collected and partitioned. Using this estimated model, a value function and a Q-function is computed. However, the estimation error always exists in the estimated model due to insufficient samples from certain state-action-endstate tuples. To account for this, we estimate the model uncertainty based on concentration inequalities. Specifically, we add the uncertainties to our value function estimator, and use the modified value function to play for the new episode. Note that doing so encourages exploration 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 a mistake (e.g., by playing a less-optimal action). With a pigeon hole principle argument, we can show that our algorithm achieves a low regret bound.

Our model-based algorithm is formally presented in Algorithm 1. We denote our estimator of the initial distribution at level as

EQUATION

where #{s ∈ M } and |M | are the number of appearance of state s in buffer M and the total number of states in buffer M , respectively. We also denote our estimator of transition distribution at state-action-endstate tuple e as

EQUATION

where #{s ∈ N e } and |N e | are the number of appearance of state s in buffer N e and the total number of states in buffer N e , respectively. With this these estimators, we use dynamic programming to solve for the Q-function and value functions as follows,

EQUATION

where for

1 ≤ h ≤ H, = σ(h), e ∈ E and V k H+1 (s 1 , • • • , s L ) = 0.

Here the bonus function b(k, h, , e) is used to estimate the uncertainty of the Q, V estimator, which are defined as follows:

EQUATION

)

where δ is a constant between [0, 1] to be specified before, and n(k -1, e) is the number of times we encountered state-action-endstate tuple before k-horizon. These bonus functions bound the difference between the estimated Q-functions to the exact value (per-step) with high probability. For episode k, our exploratory policy is then

EQUATION

Algorithm 1 Model-based Algorithm for Hierarchical RL 1: Input: An MDP with hierarchical structure, δ 2: Initialize: M = N e = ∅ (elements repeatable) for every 1 ≤ ≤ L, e ∈ E ; 3: Initialize: b(k, h, , e) as in formula (6) 4: for k = 1 : K do 5:

Calculate V k h , Q k h , π k with uses formula ( 5), (7).

6:

for h = 1 : H do 7:

Play action a

σ(h) h,k = arg max a∈A σ(h) Q k h (s 1 h,k , • • • , s L h,k ; a) ; 8: Get next state (s 1 h+1,k , • • • , s L h+1,k ); 9: for i = 1 : σ(h) do 10: Put s i h+1,k into M ; 11: Put s h+1,k into N (s h,k ,a h,k ,s -1 h,k ) .

12:

Update P k,0 (s) = #{s ∈ M } |M | , ∀1 ≤ ≤ L, s ∈ S , Pk (s|e) = #{s ∈ N e } |N e | , ∀1 ≤ ≤ L, e ∈ E , s ∈ S .

4.2. REGRET BOUND FOR ALGORITHM 1:

In this subsection we provide a formal guarantee for Algorithm 1. We present a proof sketch in the next section, and the full proof is deferred to appendix. Theorem 4.1. Suppose we run Algorithm 1 for K ≥ 1 episodes on an hMDP. For k ∈ [K], let π k be policy played by the algorithm in episode k. Then we have, with probability at least 1 -δ,

R(K) = L =1 Õ H H |E | + H K H • |E |(|S | + log δ -1 ) .

where δ ∈ (0, 1) and R(K) is defined in Equation (2).

From this theorem, we observe that the regret bound only depends on

L =1 |S ||E |, where |E | = |S ||A ||S -1 | (here |E -1 |

is the number of endstates at level -1). Usually, the number of actions and the number of endstates at a level are much smaller than the number of states and can be viewed as constant. In this way our regret bound only depends on 

5. PROOF SKETCH:

The proof of Theorem 4.1 is divided into two parts. In 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 of the total variation (TV) distance between a distribution on the state space S of level and its empirical estimation using n samples. This TV distance can be bounded by Õ( |S |/n) with high probability.

The second part of proof tells that if the difference between empirical expectation and true expectation of the value function can be bounded by the bonus b, then the estimator Q k h of Q function is always an optimistic estimation to the true Q-function with high probability. That is, for every

s i ∈ S i , we have Q k h (s 1 , • • • , s L ) ≥ Q * h (s 1 , • • • , s L ).

Then we can show that the regret can be upper bounded by the sum of all bonuses along the sample path. Hence we can obtain the regret bound by summing over all bonuses in each step and horizon. We notice that at level there are only |E | distributions we need to estimate, and each one is a distribution on S . Therefore applying Hölder inequality we obtain the regret bound L =1 Õ( |S ||E |K), where we put the dependence on H and δ into Õ.

6. 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 is 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 is 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., 2017; 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 a framework to combine hierarchical learning and imitation learning. However, there is no formal statistical guarantee. We believe our analysis can be leveraged to understand deep hierarchical imitation learning too.

A PROOF OF THEOREM 4.1 A.1 NOTATIONS FOR THE PROOF We will specify some useful notations in the proof first.

To be convenient, we use

V h [K], Q h [K, a] to denote V h (s 1 k,h1 , • • • , s L k,h L ) and Q h (s 1 k,h , • • • , s L k,h ; a). We use V h [k] ⊗ to denote the |S 1 | × • • • × |S |-dimensional tensor whose (x 1 , • • • , x )-element is V h (x 1 , • • • , x , s +1 k,h+1 , • • • , s L k,h+1

). Given probability distribution P i (•) (1 ≤ i ≤ ) over the state space S i , we use P i to denote the operator over tensors:

EQUATION

which can be understood as taking the expectation on the i-th element. We can also define the tensor product operator

P i1 ⊗ P i2 , • • • ⊗ P ij for different i 1 , • • • , i j as the composite operator, where each P ij is a operator of dimension |S ij |.

A.2 PROOF OF THEOREM 4.1

We present the proof of Theorem 4.1 in this subsection. In the next we use e k,h to denote the state-action-endstate pair (s l k,h , a l k,h , s l-1 k,h ). 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 1 -δ, we have

P1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ Pk (•|e) -P 1 k,0 ⊗ • • • P -1 k,0 ⊗ P k (•|e) V k h+1 [k] ⊗ ≤ b(k, h, , e) for every k ≥ 1, 1 ≤ h ≤ H, 1 ≤ ≤ L and e ∈ E .

Proof. Given any k ≥ 1, 1 ≤ h ≤ H, 1 ≤ ≤ L and e = (s l , a l , s l-1 ) ∈ E , we have the following estimation of error between estimated transition model and true transition model.

P1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ Pk (•|e) -P 1 k,0 ⊗ • • • P -1 k,0 ⊗ P k (•|e) V k h+1 [k] ⊗ ≤ -1 i=1 P1 k,0 ⊗ • • • Pi k,0 • • • ⊗ P -1 k,0 ⊗ Pk (•|e) -P1 k,0 ⊗ • • • P i k,0 • • • P -1 k,0 ⊗ Pk (•|e) V k h+1 [k] ⊗ + P 1 k,0 ⊗ • • • P -1 k,0 ⊗ Pk (•|e) -P 1 k,0 ⊗ • • • P -1 k,0 ⊗ P k (•|e) V k h+1 [k] ⊗ = -1 i=1 Pi k,0 -P i k,0 ⊗ P1 k,0 ⊗ • • • Pi-1 k,0 ⊗ P i+1 k,0 • • • ⊗ P -1 k,0 ⊗ Pk (•|e) V k h+1 [k] ⊗ + Pk (•|e) -P k (•|e) ⊗ P 1 k,0 ⊗ • • • P -1 k,0 -P 1 k,0 ⊗ • • • P -1 k,0 V k h+1 [k] ⊗ ≤ -1 i=1 P i k,0 -P i k,0 1 P1 k,0 ⊗ • • • Pi-1 k,0 ⊗ P i+1 k,0 • • • ⊗ P -1 k,0 ⊗ Pk (•|e) V k h+1 [k] ⊗ ∞ + Pk (•|e) -P k (•|e) 1 P 1 k,0 ⊗ • • • P -1 k,0 -P 1 k,0 ⊗ • • • P -1 k,0 V k h+1 [k] ⊗ ∞ ≤ -1 i=1 P i k,0 -P i k,0 1 • H + Pk (•|e) -P k (•|e) 1 • H

According to Theorem 2.1 in Weissman et al. (2003) , for any 1 ≤ i ≤ -1, with probability at least 1 -δ we have

EQUATION

where we use the fact that till k horizons, we have k Hi samples for the initial distribution of level i.

Similarly, with probability at least 1 -δ we have

Pk (•|e) -P k (•|e) 1 ≤ 8(|S | + log δ -1 ) n(k -1, e) ,

where we use n(k -1, e) to denote the number of appearance of state-action-endstate tuple till k -1 horizons (including k -1 horizon). Replacing δ with δ/(4L 2 |S i ||E |k 2 ) and applying union bound on all 1 ≤ i ≤ , we obtain

-1 i=1 P i k,0 -P i k,0 1 • H + Pk (•|e) -P k (•|e) 1 • H ≤ H 8(|S | + log(4L 2 |S i ||E |k 2 /δ)) n(k -1, e) + H -1 i=1 min 1, 8(|S i | + log(4L 2 |S i ||E |k 2 /δ)) (k -1) Hi

with probability at least 1 -δ/(4L|S i ||E |k 2 ). Therefore, noticing that

EQUATION

then we have

P1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ Pk (•|e) -P 1 k,0 ⊗ • • • P -1 k,0 ⊗ P k (•|e) V k h+1 [k] ⊗ ≤ b(k, h

, , e) with probability at least 1 -δ/(2L|E |k 2 ).

Finally, we apply the union bound on all k ≥ 1, 1 ≤ ≤ L and e ∈ E ,

P1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ Pk (•|e) -P 1 k,0 ⊗ • • • P -1 k,0 ⊗ P k (•|e) V k h+1 [k] ⊗ ≤ b(k, h

, , e) holds for every k ≥ 1, 1 ≤ ≤ L, e ∈ E with probability at least 1 -δ.

Next we present a lemma indicating that if the event in Lemma A.1 holds, then V k h is always an optimistic estimation to the true value function V * h . Lemma A.2. Suppose the event in Lemma A.1 holds, then

V k h [k] ≥ V * h [k] holds for every 1 ≤ h ≤ H and 1 ≤ k ≤ K.

Proof. We will prove a stronger version of this lemma. That is, for every

(s 1 , • • • , s L ) ∈ S 1 × • • • × S L , we have V k h (s 1 , • • • , s L ) ≥ V * h (s 1 , • • • , s L ). We will prove this result by induction. When h = H, since V k h = V * h = 0, the inequality V k h [k] ≥ V * h [k]

already holds. Next we assume that this inequality holds for h + 1, and we consider the case h. For any (s 1 , • • • , s L ) ∈ S 1 × • • • × S L , a ∈ A , we let e = (s , a , s -1 ). Suppose σ(h) = , and for every i < , s , s i are all end-state of level i. According to the events in Lemma A.1, we have

Q k h (s 1 , • • • , s L ; a ) = r(s 1 , • • • , s L , a h ) + P1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ Pk (•|e) V k h+1 (• • • , •, s l+1 , • • • , s L ) + b(k, h, , e) ≥ r(s 1 , • • • , s L , a h ) + P 1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ P k (•|e) V k h+1 (• • • , •, s l+1 , • • • , s L ) ≥ r(s 1 , • • • , s L , a h ) + P 1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ P k (•|e) V * h+1 (• • • , •, s l+1 , • • • , s L ) = Q * h [k, a h ],

where the first inequality uses the event in Lemma A.1, and last inequality uses the fact that V k h+1 ≥ V * h+1 and P

1 k,0 ⊗ • • • ⊗ P -1 k,0 ⊗ P k (•|e

) is a nonnegative operator. Therefore, we have

V k h (s 1 , • • • , s L ) = min max a ∈A Q k h (s 1 , • • • , s L ; a ), H ≥ min max a ∈A Q * h (s 1 , • • • , s L ; a ), H = V * h (s 1 , • • • , s L )

This indicates that this lemma holds for h, which completes the induction. Hence for every 1 ≤ h ≤ H, this lemma holds.

Equipped with these two lemma, we are ready to prove Theorem 4.1.

Proof. Suppose the event in Lemma A.1 always holds (which will happen with probability at least 1 -δ), then we can calculate the value function.

V k h [k] -V π k h [k] = Q k h [k, a h ] -Q π k h [k, a h ] = P1 k,0 ⊗ • • • ⊗ Pl-1 k,0 ⊗ Pk (•|e k,l ) V k h+1 [k] ⊗ + b(k, h, , e k,h ) -P 1 k,0 ⊗ • • • ⊗ P l-1 k,0 ⊗ P k (•|e k,l ) V π k h+1 [k] ⊗ = P 1 k,0 ⊗ • • • ⊗ P l-1 k,0 ⊗ P k (•|e k,l ) V k h+1 [k] ⊗ -V π k h+1 [k] ⊗ + b(k, h, , e k,h ) + P1 k,0 ⊗ • • • ⊗ Pl-1 k,0 ⊗ Pk (•|e k,l ) -P 1 k,0 ⊗ • • • P l-1 k,0 ⊗ P k (•|e k,l ) V k h+1 [k] ⊗ = V k h+1 [k] -V π k h+1 [k] + ξ h+1,k + b(k, h, , e k,h ) + P1 k,0 ⊗ • • • ⊗ Pl-1 k,0 ⊗ Pk (•|e k,l ) -P 1 k,0 ⊗ • • • P l-1 k,0 ⊗ P k (•|e k,l ) V k h+1 [k] ⊗ ≤ V k h+1 [k] -V π k h+1 [k] + ξ h+1,k + 2b(k, h, , e k,h ),

where the last inequality uses Lemma A.2, and we define ξ h+1,k as follows:

ξ h+1,k = P 1 k,0 ⊗ • • • ⊗ P l-1 k,0 ⊗ P k (•|e k,l ) V k h+1 [k] ⊗ -V π k h+1 [k] ⊗ -V k h+1 [k] -V π k h+1 [k] .

Sum up this inequality for all 1 ≤ h ≤ H, and noticing that

V k H = V π k H = 0, we get V k 1 [k] -V π k 1 [k] ≤ H h=1 ξ h+1,k + 2 H h=1 b(k, h, σ(h), e k,h ), which indicates that K k=1 V * 1 [k] -V π k 1 [k] ≤ K k=1 V k 1 [k] -V π k 1 [k] ≤ K k=1 H h=1 ξ h+1,k + 2 K k=1 H h=1 b(k, h, σ(h), e k,h ). (11)

As for the first term in the above , it is easy to see that ξ h+1,k is a martingale difference sequence with respect to h, k. Since every ξ h,k is bounded by H = H 1 • • • H L , according to Azuma-Hoeffding inequality we have

EQUATION

with probability at least 1 -δ.

Under review as a conference paper at ICLR 2020 Next, we will analyze the second term in equation 11. According to formula equation 10, we have

EQUATION

In the first summation of the above equation, the one involved with 1/n(k -1, e k,h ) appears n(k, e k,h ) -n(k -1, e k,h ) times. And given 1 ≤ ≤ L, there exists H -1 -H choices of h such that σ(h) = . For given , there are |E | choices of n(k, e) where e ∈ E . Therefore, we have where the third inequality uses the fact that for any e ∈ E we have n(k, e) -n(k -1, e) ≤ H , and the second last equation uses the fact that e∈E n(K, e) is the number of all possible state-actionendstate pair appears up to K horizons, which is K times the number of m such that σ(h) = .

Therefore, the first term in equation 13 has the following estimation 

R(K) = K k=1 V * 1 [k] -V π k 1 [k] ≤ L =1 Õ H H |E | + H K H • |E |(|S | + log δ -1 ) + 4H HK log δ -1 = L =1 Õ H H |E | + H K H • |E |(|S | + log δ -1 )

:

Here we only consider cases where rewards are in [0, 1], but it is easy to know that this result can generalize to rewards in a different range using standard reductionSidford et al. (2018a). We can also generalize our

Figures and Tables:

=1 |S |. It means after K = Ω L =1 H H |E ||S | episodes, the algorithms achieves a constant average regret R(K)/K = O(1) (this is when the agent learns a meaningful amount of information). Let us consider the full hMDP, whose state space size is L =1 |S |. With a model based or model free algorithm like Jaksch et al. (2010); Jin et al. (2019), the number of episodes needed would be K L =1 |S | to achieve a constant average regret. Note that L =1 |S | can be exponentially larger than poly( L =1 |S |), therefore our algorithm achieves an exponential saving in the sample complexity for RL.

| + log(4L 2 |S ||E |k 2 /δ)) n(k -1, e k,h ) k, e) -n(k -1, e)) min 1, 8(|S | + log(4L 2 |S ||E |k 2 /δ)) n(k -1, e) k, e) -n(k -1, e)) 8(|S | + log(4L 2 |S ||E |k 2 /δ)) n(k -1, e) ≤ 2 H -1 |E | + 2 • K k=1,n(k-1,e)> H e∈E (n(k, e) -n(k -1, e)) 8(|S | + log(4L 2 |S ||E |k 2 /δ)) n(k, e) | + log(4L 2 |S ||E |k 2 /δ| + log(4L 2 |S ||E |k 2 /δ)) j ≤ 2 H |E | + e∈E 2 8(|S | + log(4L 2 |S ||E |k 2 /δ)) • n(K, e) ≤ 2 H |E | + 2 8(|S | + log(4L 2 |S ||E |k 2 /δ)) • |E | • e∈E n(K, e) = 2 H |E | + 2 8(|S | + log(4L 2 |S ||E |k 2 /δ)) • |E | • K( H -H +1 ) = Õ H |E | + K H • |E |(|S | + log δ -1 ) ,

σ(h) | + log(4L 2 |S σ(h) ||E σ(h) |k 2 /δ)) n(k, e k,h ) = L H H |E | + H K H • |E |(|S | + log δ -1 ) .As for the second term in equation 13, we haveH i | + log(4L 2 |S i ||E σ(h) |k 2 /δ)) i | + log(4L 2 |S i ||E |k 2 /δ)) i | + log(4L 2 |S i ||E |k 2 /δ)) (ki | + log(4L 2 |S i |( L j=1 |E j |)k 2 /δ)) (ki | + log(4L 2 |S i |( i | + log(4L 2 |S i |( L j=1 |E j |)k 2 /δ)) (k -1) Hi ≤ L i=1 Õ H Hi + H K Hi (|S i | + log δ -1 ) ,where in the last inequality we apply the Hölder inequality. Combined previous two estimations together, we obtain that , h, σ(h), e k,h )≤ L =1 Õ H H |E | + H K H • |E |(|S | + log δ -1 ) + L i=1 Õ H Hi + H K Hi (|S i | + log δ -1 ) = L =1 Õ H K H • |E |(|S | + log δ -1 )This equation, together with equation 11 and equation 12, indicates the regret bound

Peer review (iclr2020):
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.