Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 = S1 × S2 × · × SL. 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.

heading: 2 RELATED WORK
text: 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 Õ( √ H4S2AT ) and Õ( √ H3S2AT ) respectively. Later, the UCBVI algorithm in Azar et al. (2017) adds bonus term to the Q function directly, and achieves the regret bound Õ( √ H2SAT ), 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 Õ( √ H3SAT ).
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.

heading: 3 PRELIMINARIES

heading: 3.1 EPISODIC MARKOV DECISION PROCESS
text: 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 → 4 (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
1Here 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 reduction Sidford et al. (2018a). We can also generalize our
from some initial state s1 ∈ S (draw from some distribution), the agent is able to play H steps (an episode) and then the system resets to another initial state s1 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: s1, a1, r1, s2, a2, r2, . . . , sH , aH , rH where r1 = r(s1, a1), s2 ∼ P (·|s1, a1), a2 ∼ π(s2), etc. The value function and Q-function at step h of a given policy is defined as V πh (s) = Eπ [∑H h′=h rh′
∣∣sh = s] and Qπh(s, a) = Eπ [∑H h′=h
∣∣sh = s, ah = a], where the expectation is over all sample trajectories. Then the optimal policy, π∗, is defined to be the policy with largest V π1 (s1) for all s1 ∈ 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) + Es′∼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.
R(K) = K∑ k=1 (V ∗1 (s1)− V πk 1 (s1)) . (2)
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) ≤ Õ (√ H2|S|2|A|HK ) .

heading: 3.2 DEEP HIERARCHICAL MDP
text: 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=1H`.
For each step h in the hMDP, we can represent it by a tuple (h1, · · · , hL), where h` ∈ [H`] is the step of `-th level MDP for 1 ≤ ` ≤ L. We use H̃` = ∏L i=`Hi to denote the effective horizon of level `, which represents the total number of actions in A` ∪ · · · ∪ AL needed to be played in an episode of the full hMDP. Note that, for each h = (h1, · · · , hL) ∈ [1, H], we have h+ 1 = (h′1, · · · , h′L) is the immediate next lexicographical tuple of (h1, · · · , hL). 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.
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 H`length trajectory in the `-th level MDP, the last state always falls in S ′` ⊂ Sl, 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: (s1, · · · , sL). 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 i0:
sih+1 ∼P i0 (·) , ∀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(s1h, · · · , sLh , 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.

heading: 3.3 DEEP HIERARCHICAL REINFORCEMENT LEARNING OBJECTIVE
text: 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 S1× · · · × SL× [H] toA1 ∪ · · ·AL, where π(s1, · · · , sL, h) ∈ A` if and only if σ(h) = `, s1 ∈ S ′1, · · · , s`−1 ∈ S ′`−1 and s` ∈ S`, · · · , sL ∈ SL. 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, · · · , sL; a) = r(s1, · · · , s`; a)
+ Es̃1∼P 10 ,··· ,s̃`−1∼P `−1,s̃`∼P (·|e)V π h+1(s̃ 1, · · · , s̃`, s`+1 · · · , sL),
V πh (s 1, · · · , sL) = Qkh(s1, · · · , sL;π(s1, · · · , sL, h))
V πH+1(s 1, · · · , sL) = 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 π∗.

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

heading: 4.1 MODEL-BASED HIERARCHICAL REINFORCEMENT LEARNING ALGORITHM
text: 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 `=1H` 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 (s1h,k, · · · , sLh,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, sih+1,k) for every 1 ≤ i ≤ ` − 1. We add them to a buffer, s`h+1,k to Neh,k corresponding to state-action-endstate tuple eh,k, and sih+1,k to Mi corresponding to level i. Here Mi and Neh,k are multisets, i.e., their elements can be repeated. We use Neh,k to estimate probability transition P (·|e`h,k), and Mi to estimate P i0(·) 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
P̃ `k,0(s) = #{s ∈M`} |M`| , (3)
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
P̃k(s|e) = #{s ∈ Ne} |Ne| , (4)
where #{s ∈ Ne} and |Ne| are the number of appearance of state s in bufferNe 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,
Qkh(s 1, · · · , sL; a) = r(s1, · · · , sL; a) + b(k, h, `, e)
+ Es̃1∼P̃ 1k,0,··· ,s̃`−1∼P̃ `−1 k,0 ,s̃ `∼P̃k(·|e)V k h+1(s̃ 1, · · · , s̃`, s`+1 · · · , sL),
V kh (s 1, · · · , sL) = min
{ H,max
a∈S`
[ Qkh(s 1, · · · , sL; a) ]} ,
(5)
where for 1 ≤ h ≤ H, ` = σ(h), e ∈ E` and V kH+1(s1, · · · , sL) = 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:
b(k, h, `, e) = H min { 1, √ 8(|S`|+ log(4L2|S`||E`|k2/δ))
n(k − 1, e)
}
+H `−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||E`|k2/δ))
(k − 1)H̃i
} ,
(6)
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
πk(s1, · · · , sL, h) = arg max a∈A`
[ Qkh(s 1, · · · , sL; a) ] . (7)
Algorithm 1 Model-based Algorithm for Hierarchical RL 1: Input: An MDP with hierarchical structure, δ 2: Initialize: M` = Ne = ∅ (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 kh , Q k h, πk with uses formula (5), (7).
6: for h = 1 : H do 7: Play action aσ(h)h,k = arg maxa∈Aσ(h) [ Qkh(s 1 h,k, · · · , sLh,k; a) ] ;
8: Get next state (s1h+1,k, · · · , sLh+1,k); 9: for i = 1 : σ(h) do
10: Put sih+1,k into M`; 11: Put s`h+1,k into N(s`h,k,a`h,k,s`−1h,k ).
12: Update
P̃ `k,0(s) = #{s ∈M`} |M`| , ∀1 ≤ ` ≤ L, s ∈ S`,
P̃k(s|e) = #{s ∈ Ne} |Ne| , ∀1 ≤ ` ≤ L, e ∈ E`, s ∈ S`.

heading: 4.2 REGRET BOUND FOR ALGORITHM 1
text: 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 Õ ( HH̃`|E`|+H √ KH̃` · |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 ∑L `=1 |S`|. It means
after K = Ω̃ (∑L `=1H √ 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.

heading: 5 PROOF SKETCH
text: 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 Õ( √ |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 Qkh of Q function
is always an optimistic estimation to the true Q-function with high probability. That is, for every si ∈ Si, we have Qkh(s1, · · · , sL) ≥ Q∗h(s1, · · · , sL). 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 Hölder inequality we obtain the regret bound ∑L `=1 Õ( √ |S`||E`|K), where we put the dependence on H and δ into Õ.

heading: 6 CONCLUSION
text: 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.

heading: A PROOF OF THEOREM 4.1
text: A.1 NOTATIONS FOR THE PROOF
We will specify some useful notations in the proof first.
To be convenient, we use Vh[K], Qh[K, a] to denote Vh(s1k,h1 , · · · , s L k,hL ) and Qh(s 1 k,h, · · · , sLk,h; a). We use Vh[k]⊗` to denote the |S1| × · · · × |S`|-dimensional tensor whose (x1, · · · , x`)-element is Vh(x1, · · · , x`, s`+1k,h+1, · · · , sLk,h+1). Given probability distribution P i(·) (1 ≤ i ≤ `) over the state space Si, we use Pi to denote the operator over tensors:
Pi [ V ⊗`h [k] ] = ∑ si∈S P i(si)Vh1,··· ,hL(·, · · · , si, · · · , ·, x`, s`+1k,h+1, · · · , s L k,h+1), (8)
which can be understood as taking the expectation on the i-th element. We can also define the tensor product operator Pi1 ⊗Pi2 , · · ·⊗Pij for different i1, · · · , ij as the composite operator, where each Pij is a operator of dimension |Sij |.
A.2 PROOF OF THEOREM 4.1
We present the proof of Theorem 4.1 in this subsection. In the next we use ek,h to denote the state-action-endstate pair (slk,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∣∣∣[P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+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 = (sl, al, sl−1) ∈ E`, we have the following estimation of error between estimated transition model and true transition model.∣∣∣[P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+1[k]⊗`∣∣∣ ≤
`−1∑ i=1 ∣∣∣[P̃1k,0 ⊗ · · · P̃ik,0 · · · ⊗ P`−1k,0 ⊗ P̃k(·|e)− P̃1k,0 ⊗ · · · Pik,0 · · · P`−1k,0 ⊗ P̃k(·|e)]V kh+1[k]⊗`∣∣∣ + ∣∣∣[P1k,0 ⊗ · · · P`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+1[k]⊗`∣∣∣
= `−1∑ i=1 ∣∣∣[[P̃ik,0 − Pik,0]⊗ P̃1k,0 ⊗ · · · P̃i−1k,0 ⊗ Pi+1k,0 · · · ⊗ P`−1k,0 ⊗ P̃k(·|e)]V kh+1[k]⊗`∣∣∣ + ∣∣∣[[P̃k(·|e)− Pk(·|e)]⊗ P1k,0 ⊗ · · · P`−1k,0 − P1k,0 ⊗ · · · P`−1k,0 ]V kh+1[k]⊗`∣∣∣ ≤ `−1∑ i=1 ∥∥∥P̃ ik,0 − P ik,0∥∥∥ 1
∥∥∥[P̃1k,0 ⊗ · · · P̃i−1k,0 ⊗ Pi+1k,0 · · · ⊗ P`−1k,0 ⊗ P̃k(·|e)]V kh+1[k]⊗`∥∥∥∞ + ∥∥∥P̃k(·|e)− Pk(·|e)∥∥∥
1 ∥∥∥[P1k,0 ⊗ · · · P`−1k,0 − P1k,0 ⊗ · · · P`−1k,0 ]V kh+1[k]⊗`∥∥∥∞ ≤
`−1∑ i=1 ∥∥∥P̃ ik,0 − P ik,0∥∥∥ 1 ·H + ∥∥∥P̃k(·|e)− Pk(·|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 ∥∥∥P̃ ik,0 − P ik,0∥∥∥
1 ≤
√ 8(|Si|+ log δ−1)
(k − 1)H̃i , (9)
where we use the fact that till k horizons, we have kH̃i samples for the initial distribution of level i. Similarly, with probability at least 1− δ we have∥∥∥P̃k(·|e)− Pk(·|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 δ/(4L2|Si||E`|k2) and applying union bound on all 1 ≤ i ≤ `, we obtain
`−1∑ i=1 ∥∥∥P̃ ik,0 − P ik,0∥∥∥ 1 ·H + ∥∥∥P̃k(·|e)− Pk(·|e)∥∥∥ 1 ·H
≤ H
(√ 8(|S`|+ log(4L2|Si||E`|k2/δ))
n(k − 1, e)
} +H
`−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||E`|k2/δ))
(k − 1)H̃i ) with probability at least 1− δ/(4L|Si||E`|k2). Therefore, noticing that∣∣∣[P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+1[k]⊗`∣∣∣ ≤ H if we choose
b(k, h, `, e) = H min { 1, √ 8(|S`|+ log(4L2|Si||E`|k2/δ))
n(k − 1, e)
}
+H `−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||E`|k2/δ))
(k − 1)H̃i
} ,
(10)
then we have∣∣∣[P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+1[k]⊗`∣∣∣ ≤ b(k, h, `, e) with probability at least 1− δ/(2L|E`|k2). Finally, we apply the union bound on all k ≥ 1, 1 ≤ ` ≤ L and e ∈ E`,∣∣∣[P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e)− P1k,0 ⊗ · · · P`−1k,0 ⊗ Pk(·|e)]V kh+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 kh 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 kh [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 (s1, · · · , sL) ∈ S1×· · ·× SL, we have
V kh (s 1, · · · , sL) ≥ V ∗h (s1, · · · , sL).
We will prove this result by induction. When h = H , since V kh = 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 (s1, · · · , sL) ∈ S1 × · · · × SL, a` ∈ A`, we let e = (s`, a`, s`−1). Suppose σ(h) = `, and for every i < `, s`, si are all end-state of level i. According to the events in Lemma A.1, we have
Qkh(s 1, · · · , sL; a`) = r(s1, · · · , sL, a`h`) + [ P̃1k,0 ⊗ · · · ⊗ P̃`−1k,0 ⊗ P̃k(·|e) ] V kh+1(· · · , ·, sl+1, · · · , sL)
+ b(k, h, `, e) ≥ r(s1, · · · , sL, a`h`) + [ P1k,0 ⊗ · · · ⊗ P`−1k,0 ⊗ Pk(·|e) ] V kh+1(· · · , ·, sl+1, · · · , sL)
≥ r(s1, · · · , sL, a`h`) + [ P1k,0 ⊗ · · · ⊗ P`−1k,0 ⊗ Pk(·|e) ] V ∗h+1(· · · , ·, sl+1, · · · , sL)
= Q∗h[k, a ` h` ],
where the first inequality uses the event in Lemma A.1, and last inequality uses the fact that V kh+1 ≥ V ∗h+1 and [ P1k,0 ⊗ · · · ⊗ P `−1 k,0 ⊗ Pk(·|e) ] is a nonnegative operator. Therefore, we have
V kh (s 1, · · · , sL) = min { max a`∈A` Qkh(s 1, · · · , sL; a`), H } ≥ min
{ max a`∈A` Q∗h(s 1, · · · , sL; a`), H } = V ∗h (s 1, · · · , sL)
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 kh [k]− V πk h [k] = Q k h[k, a ` h` ]−Qπkh [k, a ` h` ] = [ P̃1k,0 ⊗ · · · ⊗ P̃ l−1k,0 ⊗ P̃k(·|ek,l) ] V kh+1[k] ⊗` + b(k, h, `, ek,h)
− [ P1k,0 ⊗ · · · ⊗ P l−1k,0 ⊗ Pk(·|ek,l) ] V πkh+1[k] ⊗`
= [ P1k,0 ⊗ · · · ⊗ P l−1k,0 ⊗ Pk(·|ek,l) ] ( V kh+1[k] ⊗` − V πkh+1[k] ⊗`)+ b(k, h, `, ek,h)
+ [ P̃1k,0 ⊗ · · · ⊗ P̃ l−1k,0 ⊗ P̃k(·|ek,l)− P 1 k,0 ⊗ · · · P l−1k,0 ⊗ Pk(·|ek,l) ] V kh+1[k] ⊗`
= ( V kh+1[k]− V πk h+1[k] ) + ξh+1,k + b(k, h, `, ek,h)
+ [ P̃1k,0 ⊗ · · · ⊗ P̃ l−1k,0 ⊗ P̃k(·|ek,l)− P 1 k,0 ⊗ · · · P l−1k,0 ⊗ Pk(·|ek,l) ] V kh+1[k] ⊗`
≤ ( V kh+1[k]− V πk h+1[k] ) + ξh+1,k + 2b(k, h, `, ek,h),
where the last inequality uses Lemma A.2, and we define ξh+1,k as follows:
ξh+1,k = [ P1k,0 ⊗ · · · ⊗ P l−1k,0 ⊗ Pk(·|ek,l) ] ( V kh+1[k] ⊗` − V πkh+1[k] ⊗`)− (V kh+1[k]− V πkh+1[k]) .
Sum up this inequality for all 1 ≤ h ≤ H , and noticing that V kH = V πk H = 0, we get
V k1 [k]− V πk 1 [k] ≤ H∑ h=1 ξh+1,k + 2 H∑ h=1 b(k, h, σ(h), ek,h),
which indicates that
K∑ k=1 V ∗1 [k]−V πk 1 [k] ≤ K∑ k=1 V k1 [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), ek,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 byH = H1 · · ·HL, according to Azuma-Hoeffding inequality we have ∣∣∣∣∣ K∑ k=1 H∑ h=1 ξkh+1
∣∣∣∣∣ ≤ 4H√HK log δ−1 (12) with probability at least 1− δ.
Next, we will analyze the second term in equation 11. According to formula equation 10, we have
K∑ k=1 H∑ h=1 b(k, h, σ(h), ek,h)
= H K∑ k=1 H∑ h=1 min
{ 1, √ 8(|Sσ(h)|+ log(4L2|Sσ(h)||Eσ(h)|k2/δ))
n(k − 1, ek,h)
}
+H K∑ k=1 H∑ h=1 σ(h)−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||Eσ(h)|k2/δ))
(k − 1)H̃i
} .
(13)
In the first summation of the above equation, the one involved with √
1/n(k − 1, ek,h) appears n(k, ek,h)− n(k − 1, ek,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
K∑ k=1 H∑ h=1,σ(h)=` min
{ 1, √ 8(|S`|+ log(4L2|S`||E`|k2/δ))
n(k − 1, ek,h)
}
= K∑ k=1 ∑ e∈E` (n(k, e)− n(k − 1, e)) min
{ 1, √ 8(|S`|+ log(4L2|S`||E`|k2/δ))
n(k − 1, e)
}
= ∑ e∈E` K∑ k=1,n(k−1,e)≤H̃` (n(k, e)− n(k − 1, e))
+ ∑ e∈E` K∑ k=1,n(k−1,e)>H̃` (n(k, e)− n(k − 1, e))
√ 8(|S`|+ log(4L2|S`||E`|k2/δ))
n(k − 1, e)
≤ 2H̃`−1|E`|+ 2 · K∑
k=1,n(k−1,e)>H̃`
∑ e∈E` (n(k, e)− n(k − 1, e))
√ 8(|S`|+ log(4L2|S`||E`|k2/δ))
n(k, e)
≤ K∑ k=1 ∑ e∈E` n(k,e)∑ j=n(k−1,e)+1
√ 8(|S`|+ log(4L2|S`||E`|k2/δ))
j
= 2H̃`|E`|+ ∑ e∈E` n(K,e)∑ j=1
√ 8(|S`|+ log(4L2|S`||E`|k2/δ))
j ≤ 2H̃`|E`|+ ∑ e∈E` 2 √ 8(|S`|+ log(4L2|S`||E`|k2/δ)) · √ n(K, e)
≤ 2H̃`|E`|+ 2 √ 8(|S`|+ log(4L2|S`||E`|k2/δ)) · √ |E`| · ∑ e∈E` n(K, e)
= 2H̃`|E`|+ 2 √ 8(|S`|+ log(4L2|S`||E`|k2/δ)) · √ |E`| ·K(H̃` − H̃`+1)
= Õ ( H̃`|E`|+ √ KH̃` · |E`|(|S`|+ log δ−1) ) ,
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
H K∑ k=1 H∑ h=1 min
{ 1, √ 8(|Sσ(h)|+ log(4L2|Sσ(h)||Eσ(h)|k2/δ))
n(k, ek,h)
}
= L∑ `=1 Õ ( HH̃`|E`|+H √ KH̃` · |E`|(|S`|+ log δ−1) ) .
As for the second term in equation 13, we have
H K∑ k=1 H∑ h=1 σ(h)−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||Eσ(h)|k2/δ))
(k − 1)H̃i
}
= H K∑ k=1 L∑ `=1 H∑ h=1,σ(h)=` `−1∑ i=1 min
{ 1, √ 8(|Si|+ log(4L2|Si||E`|k2/δ))
(k − 1)H̃i
}
= H K∑ k=1 L∑ i=1 L∑ `=i+1 H∑ h=1,σ(h)=` min
{ 1, √ 8(|Si|+ log(4L2|Si||E`|k2/δ))
(k − 1)H̃i
}
≤ H K∑ k=1 L∑ i=1 L∑ `=i+1 H∑ h=1,σ(h)=` min 1, √√√√8(|Si|+ log(4L2|Si|(∑Lj=1 |Ej |)k2/δ)) (k − 1)H̃i  = H
K∑ k=1 L∑ i=1 H̃i min 1, √√√√8(|Si|+ log(4L2|Si|(∑Lj=1 |Ej |)k2/δ)) (k − 1)H̃i  ≤ H
L∑ i=1 H̃i +H K∑ k=1 L∑ i=1 H̃i √√√√8(|Si|+ log(4L2|Si|(∑Lj=1 |Ej |)k2/δ)) (k − 1)H̃i
≤ L∑ i=1 Õ ( HH̃i +H √ KH̃i(|Si|+ log δ−1) ) ,
where in the last inequality we apply the Hölder inequality. Combined previous two estimations together, we obtain that
K∑ k=1 H∑ h=1 b(k, h, σ(h), ek,h)
≤ L∑ `=1 Õ ( HH̃`|E`|+H √ KH̃` · |E`|(|S`|+ log δ−1) )
+ L∑ i=1 Õ ( HH̃i +H √ KH̃i(|Si|+ log δ−1) )
= L∑ `=1 Õ ( H √ KH̃` · |E`|(|S`|+ log δ−1) ) This equation, together with equation 11 and equation 12, indicates the regret bound
R(K) = K∑ k=1 V ∗1 [k]− V πk 1 [k]
≤ L∑ `=1 Õ ( HH̃`|E`|+H √ KH̃` · |E`|(|S`|+ log δ−1) ) + 4H √ HK log δ−1
= L∑ `=1 Õ ( HH̃`|E`|+H √ KH̃` · |E`|(|S`|+ log δ−1) )
holds with probability at least 1− 2δ. This completes the proof of Theorem 4.1.

Review summaries:
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. 

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.