Sample Complexity of Goal-Conditioned Hierarchical Reinforcement Learning
Authors: Arnaud Robert
Ciara Pike-Burke
Aldo A. Faisal
Venue: NeurIPS 2023 poster (2023)
Keywords: Hierarchical Reinforcement Learning
Sample Complexity

Abstract: Hierarchical Reinforcement Learning (HRL) algorithms can perform planning at multiple levels of abstraction. Empirical results have shown that state or temporal abstractions might significantly improve the sample efficiency of algorithms. Yet, we still do not have a complete understanding of the basis of those efficiency gains nor any theoretically grounded design rules. In this paper, we derive a lower bound on the sample complexity for the considered class of goal-conditioned HRL algorithms. The proposed lower bound empowers us to quantify the benefits of hierarchical decomposition and leads to the design of a simple Q-learning-type algorithm that leverages hierarchical decompositions. We empirically validate our theoretical findings by investigating the sample complexity of the proposed hierarchical algorithm on a spectrum of tasks (hierarchical $n$-rooms, Gymnasium's Taxi). The hierarchical $n$-rooms tasks were designed to allow us to dial their complexity over multiple orders of magnitude. Our theory and algorithmic findings provide a step towards answering the foundational question of quantifying the improvement hierarchical decomposition offers over monolithic solutions in reinforcement learning.

Sample Complexity of Goal-Conditioned Hierarchical Reinforcement Learning
Arnaud Robert
Ciara Pike-Burke Dept. of Mathematics
Brain & Behaviour Lab
Dept. of Computing
Imperial College London, UK
Imperial College London, UK a .robeet20@iimeriilll ac
pikke-burreeiineeriall ac.uk uk
A. Aldo Faisal
Brain & Behaviour Lab
Depts. of Computing & Bioengineering Imperial College London, UK
Chair in Digital Health & Data Science University of Bayreuth, Germany a. f www.fasslllmeett @imperial.ll.l.m ac uk
Abstract
Hierarchical Reinforcement Learning (HRL) algorithms can perform planning multiple levels of abstraction. Empirical results have shown that state temporal abstractions might significantly improve the sample efficiency of algorithms. Yet, we still do not have complete understanding of the basis of those efficiency gains, nor any seeeorticclll-groundee
design rules. this paper, we derive a lower bound the sample complexity for the considered class of goal-conditioned HRL algorithms. The proposed lower bound empowers us to quantify the benefits hierarchical decomposition and leads to the design of simple Q-lcarning-yy algorithm that leverages hierarchical decompositions. We empirically validate our theoretical findings by investigating the sample complexity of the proposed hierar- chical algorithm on a spectrum of tasks (hierarchical n n-rooms, Gymnasium's Taxi). The hierarchical n-rooms tasks were designed allow to dial their complexity over multiple orders of magnitude. Our theory and algorithmic findings provide step towards answering the foundational question of quantifying the improve- ment hierarchical decomposition offers over monolithic solutions in reinforcement learning.
Motivation
Hierarchical Reinforcement Learning (HRL) [7] 8 4 leverages the hierarchical decomposition of a problem to build algorithms that are more sample efficient. While there is significant empirical evidence that hierarchical implementations can drastically improve the sample efficiency of Rein- forcement I Learning (RI.) algorithms (20) 21 29 8), there are also cases where temporal abstraction worsens the empirical sample complexity (16). Therefore, natural question to ask is: when does lead to improved sample complexity, and how much of an improvement can it provide?
Theoretical work on sample-complexitg bound in Machine Learning has been integral to the devel- opment the field. Moreover, theoretical results (e.g. [7 [8 3 15 26)) often uncover interesting principles useful for improving algorithm design. For example, the Q-lerningg algorithm analysed in [1]] improved our understanding of exploration strategies in model-frea RL and the policy gradient
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(sh. rn)
Enviromment
high-level policy
Mu Prr..i.
low-level policy
Mi (St P.. Mi)
(Sc. Po.
Figure 1: The left block diagram depicts the interactions between the different components of our goal-conditioned hierarchical agent. The diagram suggests that the agent is composed of a low-level policy and a high-level policy that collaborate in order to solve task. The high-level policy xh observes the pair (5n, Ta). which denotes the high-level state and reward. It then sends sub-goal Isub as an input to the low-level policy x/. x'' observes the pair (s,, which encodes the low-level state 8y and the low-level reward ri. To achieve the sub-goal Jsub: the low-level policy xF interacts with the environment through primitive actions a. The right diagram illustrates the decomposition of the original MDP Mo into the low-level MDP MM and the high-level MDP MM, A detailed description of this decomposition is given in Sec. 2.2
theorem [26 gave birth to a wide range of new RL methods. In contrast, there are few theoretical results in hierarchical RL and many key studies are empirical, e.g. hierarchies of states X 10] time
233. or action 128
To address this gap in the literature, consider a tabular version of the goal-based approach to HRL [20 (), and we analyze the induced MDP decomposition to derive a lower bound on the sample complexity of this specific HRL framework. This lower bound allows us to understand when hicrarchical decomposition is beneficial and motivates a new hicrarchical Q-learning algorithm that leverage the hierarchical structure improve its sample efficiency. In the goal-based HRL framework, high-level policy and a low-level policy are jointly learned to solve an overarching goal. In such goal- hiaahhierarchical RL system, the high-level policy chooses sub- -obbgoal for the low-level policy, which in turn executes primitive actions to solve the sub-goal (Fig. [ left diagram). This natural way to break down tasks universal (i.e., it can be applied wide range of tasks) and it induces a decomposition of the original MDP into two sub-MDPs (detailed in Sec. (.2
This paper improves understanding of HRL through the following contributions:
We provide lower bound on the sample complexity associated with the hierarchical decomposition (see Sec. B. This lower bound allows practitioners to quantify the efficiency gain they might obtain from decomposing their task.
We propose a simple, yet novel, Q-learning-type algorithm for goal-hierarchin RL, inspired by the type decomposition considered (see Sec.
We empirically validate the theoretical findings using a synthetic task with hierarchical properties that can be scaled in complexity (see Sec. This evidence confirms that the derived bound is able to successfully identify instances where a hierarchical decomposition could be beneficial (see Sec. 5
2 Background
We consider a system where an agent needs to make a sequence of decisions in an uncertain environment to maximise the sum of cumulated rewards. Such problems are modelled as Markov Decision Processes (MDPs) and can be solved by RL algorithms (25). When task is too complex, the number of interactions required complexity typically depends on the difficulty of temporal credit assignment (which is directly related to the episode length) and the size of the state and action spaces 19]. To address this complexity. HRL leverages temporal abstractions [27] and state abstractions [8] to improve sample efficiency when learning an optimal policy. There exists a wide range of HRL frameworks; see [14 for a survey. In
learn a near-optimal policy becomes prohibitive. The task
this paper, we focus on the goal-conditioned HRI. framework (20) 4 Of the other HRL frameworks, only the options framework [27) and the resulting semi-Markov Decision Process [12 30 5 []]
benefit from some theoretical understanding, However, in practice, the goal- coal-conditioned hierarchical

---

framework presented in Fig. D is often preferred. Unlike the options framework, the goal concionnit HRL framework requires no prior knowledge about the task [4,, and its ability generalize over the goal space when function approximation is used leads to significant performance gains in benchmark
tasks (29] 20 13.. Existing theoretical work [30 12 1 on the options framework does not consider
the case where all the hierarchy levels are jointly learned. The regret analysis proposed by [30] focuses on the benefit of leveraging repeating sub-structures in hierarchical MDPs. Other regret analyses 02 II] highlight the efficiency gain of learning with temporally extended actions (such as options). However, they always assume the set of options is known, and the intra-option policies are not learned. Options are composed of an intra-option policy, which governs the agent's 's behaviour while the corresponding option is executed, making intra-option policies very similar to the low-level policy we consider. However, the condiiond HRL setting considered in this article quantifies the benefits of state abstraction, action abstraction, and time abstraction while jointly learning all levels of the hierarchy (low-level and high-level policy) through interaction with the environment. A detailed description of the option framework and its connection to HRL is available in Appendix [B]
For the remainder of this section, we define episodic finite-horizon MDPs and the hierarchical decomposition we consider.
2.1 Episodic MoriteHoriizon Markov Decision Process
An episodic finite-horizon MDP is defined by the following tuple: M = S is a finite state space of size [S] and A is a finite action space of size |A]. The goal of the task is encoded in a terminal state E S. We assume the reward function r(s, E [-a, bj (for a, b 2 0) is known Vs E S and reward the completion of the task with a positive reward of b. The initial state distribution po is distribution over states that used to determine in which state an episode starts. The learner interacts with the MDP in episodes of at most H time steps. The episode's 's starting state so ~ Po is drawn from the initial state distribution. In each time step ( = 0, ....., H 1, the learner observes a state 8t and chooses an action a, Given state action pair (st, a,) the next state $1+1 ~ P(-|s,, ag) is drawn from the transition kernel. Eventually, the episode ends because the agent reaches the terminal state or has interacted with the environment for H time-steps.
po. H). Where
g E S, the reward function penalises each step with a negative reward of at most -a
The agent's objective is to select actions that maximize the expected return throughout an episode. We typically assume actions are chosen according to a policy, at ~ π (s:),, where π is function that maps each state and time step pair to distribution over actions æ : S x [H - 1] - A. and A is the set of all probability distributions over A and [H] is the set of natural numbers up to H. The agent aims to select a policy where the expectation is over the initial state distribution, the policy and the stochastic transitions. Note that it is usually the case for finite-horizon MDPs that the policy also depends on the current time step. However, to simplify notation, we do not make this relation explicit.
maximize the sum of expected rewards, E rzla, n (s,)),
For given policy π, we define the value function, VF(s), (s), and the Q-function, QF a), at time step T E [ 1] as follows:
H Σ -
= -,8, ~ x { (x = E
H H-1 1
(8) = E
Σ
rels7 = =8,0 = a0 1,,0++1H111111
where s E S denotes the state, a E A is the action and the notation a,:H-1 ~ T is used to specify that actions between time step T and time step H - were selected using π. The optimal policy x² is the policy with the highest value function for every time step and every state, V.¹" (s) = (s) max, ViT VT E H 1], Vs e S. There always a deterministic Markov policy that maximizes the total expected reward in finite-horizon MDP (24].
In this article, we assess the quality of a policy by its expected value at the beginning of an episode.
To lighten the notation, we define \* = Exp=po [V7 (s)] to be the expected value from the beginning of episode where the expectation is taken over initial states.
2.2 Episodic Finite-Horizen Hierarchical MDP
For given episodic finite-horizon MDP Mo. we assume it can be hierarchically decomposed into pair of MDPs MM) illustrated on right diagram of Fig. I To avoid ambiguity, we use
3

---

the following notation: the subscript o denotes the original MDP, while subscripts / and h denote low-level and high-level MDPs, respectively.
A, mi, Pı, po.t, Hi) The low-level and high-level MDPs consist of the following tuples M, = An,
and M₁ = (Sh, Ar, Pa, Pn,k: Hs), respectively. To be valid hierarchical decomposition, require that these MDPs satisfy the following set of conditions:
Action space: The low-level action space consists of the set of primitive actions that the agent can use to interact with the environment. It is equivalent to the original MDP action space A. The high-level action space A,, is the set of the sub-goals the high-level agent can instruct to the low-level agent. We assume that the set of sub-goals encoded in A,, is sufficient to solve the task for any state. Note that the set of available actions An depends on the current high-level state St. To simplify our notation, we do not make this relationship explicit.
State spaces: The low-level state 8 and the high-level state 8y contain all necessary information to reconstruct the corresponding state, 8, in the original MDP. States E S C Rd are usually described as multi-dimensional vectors, where each dimension encodes a specific characteristic. For example, state description can be factored in a tuple (st, 5%) E S x Sh. with part of the state description that belongs to the low-level MDP and another part to the high-level MDP. Hence, in this work, we consider that any state S. can be represented by tuple (st, 5%. E St x Sh. Additionally, since the low-level policy is goal-conditioned, its state space also contains the goal description leading to the following state space for the low-level MDP: S x An, complete low-level state consists of the concatenation of the low-level state description st and the sub- sub-goal description d/s.
Initial state distribution: The high-level initial state distribution Po, is a restriction of the original state distribution pa on Sn- The low-level initial state distribution po. is conditioned on the initial high-level state 84.0 and spans the low-level space, ensuring that (s) Po, (8h (o.))...( (s) (s)). where 8t and 8, are the decomposition of 8.
Transition functions: The low-level transition function Pt is the restriction of P on St x Ar. One challenge in HRL is that the high-level transition function, Ph. depends on the low-level policy since the quality of the low-level policy influences the likelihood of reaching a sub-goal state. The high-level transition probability PA (s 4h, mi) is the probability that the agent transitions to s given the current high-level state sh, the sub-goal ag and low level policy गy. Since Ph. depends on the low-level policy. it is non- non-stationary. making the learning task more challenging.
Reward functions: Since the terminal states for the original MDP belong to S and the sub- aub-goals for the lew-level MDP lie in St the low-level reward function can be obtained from the original reward function, (s Isub) 2r(s, g). where s and g are the reconstruction of the low-level state and the sub-goal in the original MDP, using the current high-level state. The high-level reward function is the sum of rewards obtained by the low level during the sub-episode, where the high-level action plays
the role of a sub-goal: rA (sh, an) ΣE, ri (8L,t, an).
Horizons: The original MDP allows an episode to last most H steps. Consequently. the horizons of the high-level, Hr, and low-level, Hi, MDPs must satisfy the following equality H = H Hi.
Note that we can always find a decomposition that satisfies these assumptions; naive way to decompose any MDP would be to consider a high-level agent whose only action encodes the end goal of the task and low-level with complete state information (i.e. it does not use state abstraction). While this decomposition is valid, it is not necessarily beneficial. Here, our goal is to identify when a given decomposition is useful, specifically in terms of improvements in the sample efficiency.
We denote by Ny a policy interacting with the low-level MDP M, and TT policy interacting with the high-level MDP Mr. In gond-condi HRI., the low-level policy maps low-level state and sub-goal pair to an action: Ti S, x A,, >> A and the high-level policy maps high-level state to high-level action: W. S₁, -> An- Each policy can be evaluated using the corresponding high and low-level value functions V/#1 and V, Similar to the non-hierarchical case, we can define optimal high-level and low-level policies कं argmax,, ViT for the low-level policy and कं argmax,,, vi for the high-level policy. Moreover, as shown below, every pair of policies (m, nT) can be combined to produce a policy π that interacts with the original MDP Mo
Definition 2.1. hierarchical policy consists of a pair (m,, mT) that can be mapped to a policy π in the original MDP M, as follows:
Tals) (ca)ss,
Σ
(a(anls)) st)-
(1)
on A.EAA

---

The optimal hierarchical policy is obtained when merging (mi, xx) It is important to note that not all policies i in the original MDP have a corresponding decomposition (zi, m.), and in particular, there is no guarantee that the optimal policy in the original MDP can be decomposed.
We aim to understand when hierarchical decomposition of the MDP allows us learn a near-optimal policy faster. Therefore, we are interested in evaluating the performance of the combination of m and TT while they interact with the original MDP MM To convey the fact that we are evaluating a hierarchical policy in the original MDP, we use the following notation: given a pair of policies (m, Th) and their associated policy in the original MDP, т, the value function of the hierarchical policy is denoted by V= = Egg Expo [V., (su)), where the subscript is a reminder that we are evaluating a policy on the original MDP MM..
When learning in a decomposed MDP, the learner has to learn two policies, the high-level policy, Th, and the low-level policy, my. This is done in episodic setting where episode unfolds as follows. Firstly, the learner observes the initial state and uses the high-level policy to find the most appropriate sub-goal. For the next H4 time steps, the low-Ievel policy attempts to solve the sub-goal. The low-level agent updates its policy at the end of each low-level step. Once the H; time steps are over or if the sub-goal has been reached, the high-level agent observes a new high-level state and can finally perform an update to its policy. The high-level agent instructs a new sub-goal if the overall task is not completed. These interactions are repeated until the task is completed or the horizon H is reached. We can now think of HRL as two agents interacting with the environment. Often, each agent will try to find the policy that maximizes their value function, max,; Vi"h and maxzA Vi
2.3 Probxbby-Aprrxximately Correct RL
We aim to find, in as few episodes as possible, a pair of policies (mi, mT.) with a near-optimal value. To formalize this, we introduce the Probably-AAproximatee by As the sub-optimality gap, that is the difference between the optimal mon-hierarchical policy n² and the current hierarchical policy (TY T&):: A& == Vi - Vot "i Note that both policies are evaluated on the original MDP M.. The PAC guarantee in this paper follows the definition in [6]
Correct (PAC) RL notion. We denote
Definition 2.2. An algorithm satisfies a PAC bound if, for a given input e, d > 0, satisfies the following condition for any episodic fixed-horizon MDP: with probability at least 1 5, the algorithm plays policies that are at least e-optimal after at most N episodes. That is, with probability at least 1 6. max,k N : A > c) S N, where N is a polynomial that can depend the properties of the problem instance.
In Section 3 we will bound the sample complexity of HRL algorithms. In this context, the sample complexity refers to the number of episodes, N, in the original MDP, during which the algorithm may not follow policy that is at least c-optimal with probability at least 1 8.
2.4 Running Example
We consider the following companion example. The original MDP describes the task of solving maze in a grid-world environment. The state consists of a tuple (R. C') that indicates in which room, R. and which cell within that room, C, the agent is currently in. The reward function incurs a small cost, -a, at each time step unless the agent reaches the absorbing goal state. Once the goal state is reached, the agent stops receiving penalties and receives reward of 0 for all the remaining time steps. Mathematically, r(s)= = -al {8 # g} where g E S is the goal state, and 1 is the indicator function.
We can decompose this MDP as follows. The high-level MDP describes a similar maze, but instead of moving from cell to cell, the agent moves from room to room, so the state is just the current room. The high-level agent aims to find the room sequence that leads to the goal. Hence, at each (high-level) time step, it indicates the most valuable exit the low-level agent should take from the room. As specified in Section 2.2, the high-level reward for sub-goal is the sum of the rewards accumulated by the low-level agent during that sub-episode. The low-level agent is myopic to other rooms - it only sees the current room and the exit it has to reach, and it receives penalty of -2a for each action it takes unless it reaches the sub-goal, in which case it does not receive any penalty. Hence, if goub is the sub-goal, it receives reward r(s) -2al (s * ysub).
We will return to this example throughout the paper, but it should be noted that the framework we consider is general enough to be applied to wide range of tasks. One such example is robotics, where
5

---

the low-level agent would be tasked with controlling the joints of the robot to produce movements selected by the high-level policy, whose goal to perform tasks that require a sequence of distinct movements (i.e. navigational tasks, manipulation tasks or a combination of both).
3 Lower Bound on the Sample Complexity of HRL
has been proven in 7 that, for any RL algorithm, the number of sample episodes necessary to obtain an -accurree policy (in the original MDP) is lower bounded by:
B = |
1 8 )
In
where e is a positive constant.
We now extend this result to hierarchical MDPs. Before doing so, it is essential to notice that even the best hierarchical policy (as constructed in Eq. (I)) might be sub-optimal. This direct consequence of the goal-conditioned architecture. If, while executing sub-episode, it appears that another sub-goal becomes more valuable, the architecture proposed does not allow interruptions. The agent will first have to complete the current sub-episode before being able to adapt to the new
circumstances. Let V æi denote the value of the optimal hierarchical policy value function in the original MDP. Then, the sub-optimality gap is larger than the gap between the current policy pair and the optimal hierarchical policy As = V - Vor varii Vo xi V . Therefore, for some N, V V. - 2 c for at least N episodes, must also be the case that 4₁ 2 c for at least N episodes. Hence, N is lower bound the number of episodes where the algorithm must follow sub-optimal policy.
In the following theorem, lower bound the number of episodes required to learn pair of policies (m,, mh) which are e-accurate with respect to the optimal hicrarchical policy (#f mg). By the above argument, this will also be lower bound the number of episodes necessary learn an e-accurate policy with respect to the optimal policy π..
Theorem 3.1. There exist positive constants c, Ch. and ôn such that for every ô E (0, 8g) and for every algorithm A that satisfies PAC guarantee for (e, 8) and outputs a deterministic policy, there is fixed horizon MDP such that A must interact for
|| 2
Sh HH
Sn
E[N] Ω max
In 5 Ca
In
8 Ch
episodes, in the original MDP, until the policy is (c. -accurraee.
The complete proof is in Appendix A.I In the following, we highlight the main steps. Sketch of the proof: An e-accurate pair of policies must satisfy the following inequality, | .ن VT < e. To find a lower bound on the number of episodes N before we obtain an e-accurate pair of policies (m,, m.) used the following steps:
We decompose the objective using the triangle inequality, [/ VTL.hh
wi
<.
(ii) We show that the number of samples required to guarantee |V Ti
ii S 6/2 is bounded
by Ω
|SalIAA
IH
In
J+es
(iii) We show that the number of samples required to guarantee
- < <e/2 bounded VV
by 2
|LA14 27
In
b+tc
Combining these three steps gives the result in Theorem 3.1 see A. for more details.

---

3.1 Interpretation of the Sample Complexity Bound:
By comparing this lower bound to that in the original MDP, we can identify the problem char- acteristics that might lead to improved sample efficiency. In general, only one of the two MDP characteristics will dominate the overall sample complexity because of the max operator in the bound in Eq. 3 To maintain the max as small as possible, the complexity should be distributed between the low- and high-level MDP as evenly as possible. We discuss some of these key insights below: State abstraction: Only one of the two-state space cardinalities will dominate the bound in Eq 3 This suggests that an efficient decomposition tends to separate the original state space evenly as possible between the two levels of the hierarchy. Another phenomenon at stake the low-level re-usability. Due to the state abstraction, the low-level agent can re-use its learned policy in different states (i.e. different states 81, 82 E S whose low-level component 81 are the same). We rewrite the lower bound 3 in terms of the re-usability index K
[S]
[
[SxAn
AAHH In
Sn
|
H
N = Ω max
+ c
+ ch
Eq. highhlights that a large re-usability index improves the sample efficiency. Temporal abstraction: Similarly, only one of the two-time horizons will dominate the bound, again suggesting fair repartition of the load. The temporal abstraction (reducing H to H₁, and Hi) simplifies the credit assignment problem for the high-level and the low-level policies by giving denser feedback. The low-level agent is rewarded for completing sub-tasks that are significantly shorter than the original task, and the high-level trajectory consists of significantly fewer (high-level) steps than a trajectory in the original MDP.
High-level action space: This is the only term that appears on both sides of the max(..) in Eq. 3 This highlights that both the high-level and the low-level benefit from compact sub-goal representation.
It is interesting to note the contrast between the state space decomposition and the design of the high-level action space. To find efficient state decomposition, the amount of information available at each level must be distributed among each level of the hierarchy. In the case of the sub-goal space, it appears that both levels benefit from a compact representation.
The above discussion highlights properties of the hierarchical decomposition that could improve sample complexity. Note, however, that our bound also shows that a hierarchical decomposition does not always improve the sample efficiency. Indeed, there will be some settings where using a "bad" hicrarchical decomposition does not improve the sample complexity. Our bound can, therefore. provide sanity check to determine whether hierarchical decomposition could lead to an improved sample complexity. However, finding an algorithm that achieves this improved sample complexity can still be challenging. Nevertheless, the proposed Q-learning- based hierarchical algorithm empirically demonstrates the potential benefits of leveraging the considered decomposition. In Section [5] we consider several MDP decompositions and empirically validate that when our bound suggests the hierarchical decomposition is beneficial, our algorithm (see Sec. leverages this to achieve lower sample complexity.
4 Stationary Hierarchical Q-Learning
Once we know that we in an MDP where the hierarchical decomposition could lead to improved sample complexity, the next challenge is to design an algorithm to exploit this. This section proposes the Stationary Hierarchical Q-learning algorithm (SHQL) for this purpose. One of the most chal- lenging aspects of jointly learning a pair of policies is the non-stationarity of the high-level transition dynamics, Ph. It was briefly mentioned (in Sec. (2.2) that the high-level transition function, Pa. is non-stationary since it depends on the low-level policy, Ty with the next high-level state depending on whether ny managed to reach the sub-goal. To address this issue, we leverage the fact that the algorithm knows what a successful sub-episode is, i.e. it knows if the low-level agent managed to
Note that this is a lower bound- we still do not know if there exist algorithms which achieve this lower bound.
7

---

55093 ln thousands
0.08
1.2
0.04
0.08
0.4
0.00
0.0
0.0
2000
opisndes
Q-leariing
SHQL
Figure 2: The grid of plots depicts, on the top row, the mazes whose size ranges from 4 rooms to 1024 rooms. The bottom row shows the steps required for SHQL (in blue) and Q-learning (in red) to complete the maze. The standard deviation is obtained by running ten different seeds.
arrive the desired sub sub-goal. the case of off- off-policy methods, this is typically leveraged with hindsight correction [77. However, in the
Algorithm 1: Stationary Hierarchical Q-learning (SHQL)
= 0, Q 0, done;, False, Input: Q k=
considered on-policy setting, we pro-
while not done; and k < K do
pose that the algorithm only makes an update if the low-level agent be- haves reasonably well (i.e. solving the sub-goal). In this way, the algo- rithm filters all bad examples from the training set, and the behaviour of PA is more stable. Note, however, that the reward function the high- level agent remains non-stationary. At first, sub-goals won't be solved optimally, incurring a small reward to the high-level agent. However, the associated reward will increase as the low-level agent learns to solve sub-goals more efficiently. As de- tailed in the function LowLevelUp- date in Algorithm T the low-level agent performs Q-learning updates on the observed low-level transitions and rewards. The high-level agent also performs Q-learning updates, but only successful transitions, specified at line 10 of Algorithm
Observe S/. St
9aub (sh)
done; = Folse /+ True if sub-goal solved */
while not done; and t < T do
TI(si)
Observe Sy, rı, done;
LowLevelUpdaate(s:: at, rt, s/, goub))
10
=
1=1+1
12
Observe Sy Th. done, if done; then
13
Qh max O
Qh Len.geus = =Q '/
-ss.gems + (rh + Q
15
16
Sh. 8/
17
18
Function LowLevelUpdate (s, a, 5, gsub):
Q' maxx Q Qy
Q Q = - + a (r Qhar)
20
[
21
return Q'
5 Experiments
We now empirically evaluate the impact of the decomposition on various MDPs to validate the lower bound found in Section 3 and evaluate the performance of our proposed SHQL algorithm. To satisfy the assumption of hierarchical structure, the environments considered are a generalization of the four-room problem with an arbitrary number of rooms, called the n-rooms problem. The entire maze is built by arranging an arbitrary number of rooms on a grid. The high-level task would involve
Exxerimmnnts were run on th Gen Intel Core i7 with 16GB of RAM, to train the agents on the largest considered takes 7 minutes.

---

learning the shortest sequence of rooms that lead the agent from the starting position (the top left room) to the goal room (the bottom right room). The low-level task is learn how to navigate within each room and to reach the instructed hallway. To further modulate the task's difficulty (in addition to the maze size), we vary the room profiles used, as depicted the rightmost plot of Fig.
The set of MDPs generated by these environments are the following: The original MDP: This is standard grid-world MDP, where the state space indicates the cell where the agent is located, and the action space allows the agent to move one cell in any cardinal direction (North, South, East, West). To obtain stochastic environments, each action has success probability of Praccess 4/5. In case of failure. the action will be chosen at random.
The high-level MDP: The high-leved state space is restricted the room where the agent is currently located, and the exact position of the agent within that room is abstracted away. The high-level actions instruct the low-level reach one of the available hallways. Note that not all rooms have access to the four hallways.
The low-level MDP: The low-level agent only observes the agent's current location within a room and the goal instructed by the high-level agent (one of the reachable hallways). It then uses the primitive action space (the four cardinal directions) to reach the desired hallway, All required code to reproduce the experiments is made available online (}.
5.1 Identical Rooms
We first introduce the experimental setting in its simplest form. The environments considered in this subsection are mazes built by assembling identical rooms without obstacles (i.e. the top room profile in Fig. Fig. 2 iillustrates the empirical performance of our SHQL algorithm against Q-learning in the original MDP. As expected for simple mazes (c.g. with 4 or 16 rooms), the hierarchical decomposition does not provide much improvement. Still, as the problems grow more complex, the empirical evaluation suggests significant improvement in sample efficiency. This is also confirmed by our bound (yellow curve on the rightmost plot of Fig. 4) which highlights that the efficiency gain of HRL is mostly achievable in complex MDPs (i.e. MDPs with large state and action spaces). It is essential to notice that in this experiment, the low- decomposition remains constant for a given set of room profiles. This is why the benefit of HRL increases with the number of rooms (i.e. the high-level state space) until plateau is reached. Once the bound is dominated by the high-level MDP, the unchanging complexity of the low-level MDP causes the ratio between the RL bound (Eq. 2 and the high-level part of the HRL bound (Eq. rooms might still grow).
[S] A|H remain constant (even though number of 55 An,
5.2 Different n-rooms & Gymansium Taxi Task
To make the task more challenging, we next increase the number of room profiles used to construct the mazes. As depicted in the rightmost plot of Fig. 4 we considered four different room profiles, each one with a different obstacle in the room. The low-level agent must now learn to navigate multiple
steps (in thousenes))
0.16
0.04
0.08
0.8
2
0.00
2000
0.00
2000
0.0
2000
2000
5000
episodes
episodes
episodes
episodes
learning
SHQ
Figure 3: Those plots are similar to the ones shown in Fig. showing the performance obtained on mazes built from four different room layouts.

---

bound ratio (RL/HRL)
104
107
4 room profiles
107
3 room profiles
2 room profiles
101
room profile
10-
10a
10
number of rooms
room profiles
Figure 4: The left-hand plot shows the evolution of the ratio between the RL bound Eq. (2) and the HRL bound Eq. (3) for various mazes and different room profiles. The plateau is obtained when the
LAIH high-level MDP dominates the bound, leading to the following ratio: [S, 1A,,H, The curves are colour-coded such that a darker curve indicates more room profiles were considered. The right-hand side of the plot shows the different room profiles available to build the mazes.
types of rooms to reach the sub-goal sent by the high-level agent. The performance of the algorithms with four different rooms is shown in Fig. 3 The introduction of different room profiles allows us to modulate the complexity of the low-level MDP, in contrast to varying the number of rooms, which only affects the complexity of the high-level MDP. This additional complexity results in a larger state space S₁ but may also result in longer horizon H2 as the optimal trajectory might require more time to navigate around obstacles to reach the desired hallway successfully. It also becomes evident that, as the number of rooms increases, the hierarchy's s benefits become more significant. Nevertheless, comparing Fig. 2 and Fig. 3 we can observe that the introduction of various room layouts has little effect on the Q-leariig curve (in red). At the same time, makes the task slightly more challenging for the HSQL learning curve (in blue), especially when the number of rooms is small since it suffers from the increased complexity of the low-level MDP. But, when the number of rooms is sufficiently large for the high-level MDP complexity of hierarchical decomposition becomes evident. The evolution of the bound ratio (HRL/RL) for the various MDPs considered is shown in the leftmost plot of Fig. 4 It shows that the low-level MDP dominates the bound when the maze consists of small number of rooms. However, the curves clearly indicate that the expected sample efficiency improves as the high-level MDP becomes more complex (i.e., balancing the complexity between the two levels of the hierarchy). This result is also supported by empirical evidence illustrated in Figs. experiments presented in Appendix A.2.2 further validate our approach and conclusion on an entirely different task.
dominate the bound, the benefit
and 6 The Gymnasium Taxi environment []]
Conclusion
In this work, we analysed the sample complexity of goal-conditioned HRI. To the best of our knowledge, we provide the first result that analyses the decomposition induced by goal-conditioned HRL. In particular, our lower bound offers a valuable tool for practitioners that could help them decide whether they should consider a hicrarchical decomposition for their problem. We also designed a novel algorithm that can leverage the hierarchy to improve its sample efficiency and implemented this on a set of bierarchical tasks. These experimental results further emphasizes the usefulness the proposed bound since theoretical findings support empirical efficiency gains.
Although this paper has taken a significant first step bettering our understanding of the benefits of hierarchical decomposition, there is still scope for further work in this area. Three immediate open questions are: (i) whether our lower bound could be refined by explicitly accounting for the interactions between the low-level and the high-level agent, (ii) is it possible to design algorithm that can thcoretically match the proposed lower bound, (iii) the current results only consider the cardinality of the sub-goal space because assumed that the sub-goal-space was given and that all sub-goals where solvable. Methods that design efficient sub-goal spaces remain largely unexplored and are critical aspect of the design of HRL algorithms. Moreover, the insights we proposed framed in a tabular setting and do not yet extend to a continuous setting where function approximation could be leveraged to allow the lowelevel agent generalise over sub-goals and to consider setting beyond the tabular case described in this article. Overcoming those limitations is an interesting direction for future work.
10

---

Acknowledgments
AR was supported by an EPSRC CASE studentship supported by Shell, and AAP was supported by UKRI Turing AI Fellowship (EP/VO25444/1).
References
[1] A. A. Faisal A. Robert, C. Pike-Burke. Code and resources for running Hierarchical Stationary Q-learning:
[2] Ekaterina Abramova, Luke Dickens, Daniel Kuhn, and Aldo Faisal. Hierarchical, heterogeneous control of non-linear dynamical systems using reinforcement learning. In European Workshop On Reinforcement Learning, at ICML, volume 2012, 2012.
[3] Peter Auer and Ronald Ortner. Online regret bounds for a new reinforcement learning algorithm. In Ist Austrian Cognitive Vision Workshop, pages 35-42. Österr. Computer-Ges, 2005.
[4] Benjamin Beyret, Ali Shafti, and Aldo Faisal. Dot-to-dot: Explainable hierarchical rein- forcement learning for robotic manipulation. In 20/9 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5014-5019. IEEE, 2019.
[5] Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning. In International Conference on Machine Learning, pages 316-324, PMLR, 2014.
[6] Christoph Dann. Strategic Exploration in Reinforcement Learning-New Algorithmss and Learn- ing Guarantees. PhD thesis, Google, 2019.
[7] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. Advances in Neural Information Processing Systems, 28, 2015.
[8] Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. Advances in neural information processing systems, 5, 1992.
[9] Thomas Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artificial intelligence research, 13:227-303, 2000.
[10] Thomas G Dietterich et al. The maxq method for hierarchical reinforcement learning. In International Conference on Machine Learning, volume 98, pages 118-126, 1998.
[11] Ronan Fruit and Alessandro Lazaric. Exploration-explootation in mdps with options. In Artificial intelligence and statistics, pages 576-584. PMLR, 2017.
[12] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. Advances in Neural Information Processing Systems, 30, 2017.
[13] Tuomas Haarnoja, Kristian Hartikainen, Pieter Abbeel, and Sergey Levine. Latent space policies for hierarchical reinforcement learning. In International Conference on Machine Learning. pages 1851-1860. PMLR, 2018.
[14] Matthias Hutsebaut-Buye Buysse, Kevin Mets, and Steven Latré. Hierarchical reinforcement learning: survey and open research challenges. Machine Learning and Knowledge Extraction, 4(1):172- 221, 2022.
[15] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in Neural Information Processing Systems, 31, 2018.
[16] Nicholas K Jong, Todd Hester, and Peter Stone. The utility of temporal abstraction in reinforce- ment learning. In AAMAS (1), pages 299-306, 2008.
[17] Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierar- chies with hindsight. arXiv preprint arXiv:1712.00945 2017.

---

[18] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275 2022.
[19] Amy McGovern, Richard S Sutton, and Andrew H Fagg. Roles of macro-actions in accelerating reinforcement learning. In Gruce Hopper celebration of women in computing, volume 1317, page 15, 1997.
[20] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
[21] Ofir Nachum, Haoran Tang, Xingyu Lu, Shixiang Gu, Honglak Lee, and Sergey Levine. Why does hierarchy (sometimes) work so well in reinforcement learning? arXiv preprint arXiv: 10618, 2019.
[22] Marc Pickett and Andrew G Barto. Policyblocks: algorithm for creating useful macro-actions in reinforcement learning. In International Conference on Machine Learning, volume 19, pages 506-512 506-513,200 2002.
[23] Doina Precup and Richard S Sutton. Multi-time models for temporally abstract planning. Advances in Neural Information Processing Systems, 10, 1997.
[24] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[25] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[26] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
[27] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1- 2):181-211, 1999.
[28] Alexander Vezhnevets, Volodymyr Mnih, Simon Osindero, Alex Graves, Oriol Vinyals, John Agapiou, al. Strategic attentive writer for learning macro-actions. Advances in Neural Information Processing Systems, 29, 2016.
[29] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukeuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pages 3540-3549. PMLR, 2017.
[30] Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33:6708 6718, 2020.
12

---

A Appendix
A.1 Proof of Theorem
Theorem 3.1 states that there exist positive constants ct. cb and dn such that for every 8 E (0, (0, and for every algorithm that satisfies a PAC guarantee for (e, 5) and outputs a deterministic policy, there is fixed horizon MDP such that A must collect
B[N.] = 52( max
Sh AA
1 $11)) 8 +
In
(5)
0+9
2
episodes until its policy is (e, aaacuurcee
Proof. An e-accurate pair of policies (m, Th) satisfies
IVo Th V.u.T S c. Note that by the triangle inequality, IV mm We therefore focus on showing:
Vo
VaLtn then we will have [Vo mn - Vit
(i) the number of samples required to guarantee V VATTINN S e/2 is bounded by
Q |S.IIA 11 In (xtean
(ii) the number of samples required to guarantee Vo VaLLan) S c/2 is bounded by
s [S AAIH In (stte)
Then, once we have both (i) and (ii), we know that after
22 max
|SIIIAN|AAIRR
| H
In
In
22
+
episodes, we will have |V V.T
VTLTT S and VV a
V.L.TN S e.
Part (i) Note that only learning the high-level policy when the low-level policy optimal equivalent to learning an c-accurate high-level policy interacting with MA with a stationary transition function (since the low-level behaviour is not evolving anymore). Hence we can bound the number of episodes
N₁ required to have: IV
V
I <, by directly applying Eq. (2) to the high-level MDP to get
E[Na] |SAl|AAn H3 In 5 Ch 2
1
To be able to use this result construct the bound of interest, we need to make sure these results can be translated into the original MDP: |v, 15h V.77 S e. In particular, the reward functions not the same for M, and M,, We defined the original MDP's reward function to penalize each step unless it reaches the end goal, in which case it rewards the agent with a bonus. This reward function was initially defined to take values in the interval [-a, b). Without loss of generality, we shift the reward function so that the rewards are now drawn from the interval [-a - b, 0j. In this new setting, successful completion of the task is rewarded with bonus of 0. Similarly, the low-level reward function penalizes each step unless it reaches the instructed sub-goal. Lastly, the high-level reward function (s 0%)) = ΣHr (1 an), consists of the sum of the low-level rewards accumulated during each sub-episode. A difference of scale in value function arises because high-level rewards include the bonus the low-level agent receives for completing each sub-goal, whereas the value functions the original MDP do include this bonus. To compensate for this difference, the low-level reward is re-scaled with penalty twice larger; the low-level reward rı now takes values in [-2a- 2b. 0). and, under this specific reward function, the completion of sub-goal is rewarded by 0 as well. The re-scaling ensures that the accumulated penalties are larger in the high-level MDPs, even for trajectories with a single intermediary step. This guarantees that
V ...j. .g. V," FF < V V,T -[ Hence after E[Nx] episodes, we have IV* "i
13

---

Part (ii) By similar argument to Part (i), we can bound the number of episodes in the low-level MDP required obtain an e-optimal low-level policy for fixed high- policy Th. In particular, lower bound on the number of episodes N2 required to have | Th Vi S e can directly be obtained from Eq. (
|SIIA
1 8 + C1 )
[ 9
Ultimately, we are interested in a lower bound on the number of episodes in the original MDP No- Since a single episode the original MDP corresponds to several episodes in the low-level MDP, we can divide the number of episodes by factor d₁: E[N,] 2 Hr,
E[Ni] However, the difference in episode
length between the two MDPs also induces difference scale in their value functions. To ensure that
the learned policies e-optimal in the original MDP we need ensure that [V, : -V, V,t IS f
which requires at least [NN] low-level episodes. Combining the two arguments, we get that HH2
E[N.] Hn. E[Ni H Since we are computing lower bound on the number of episodes in the original MDP required to learn a near-optimal policy and recognising that H, 1, we can conclude that E [N.. 2 TE [M]]
This leads to lower bound the number of episodes needed to obtain e-accurate pair of policies as the one stated in the theorem.
A.2
Additional Experiments
A.2.1 More n-rooms Problems
In the experimental section (Sec. 5), we used several room layouts. In the main paper, we only provide learning curves for mazes that are composed of rooms without any obstacles mazes that are composed of all the possible room layouts depicted in the rightmost plot of Fig. 4 To complete our experiment, we show below in (Fig. and Fig. (6) the learning curve obtained when mazes are built from two or three different room layouts. These learning curves highlight the same behaviour that we previously discussed. With simple mazes, the low-level MDP strongly dominates the bound but as we increase the high-level MDP complexity (i.e. the number of rooms), the benefit of the hicrarchical machinery becomes evident. Note also that those results were used to plot the evolution of the bound ratio in the leftmost plot of Fig.
D.r 1000
00000
steps (in thousands)
0.08
0.16
1.6
4
0.04
0.08
0.8
2000
2000
2000
2000 episodes
2000
episades
episodes
episodes
episades
Q-leaming
HQL
Figure 5: Shows learning curves on various maze sizes with different room instances; either the room is empty, or has a U-shape obstacle in it. The agent's performance is measured in the number of steps it requires to solve the task.
14

---

steps (In thousands)
0.08
0.16
1.6
0.04
0.00
0.00
0.0
2000
2000
2000
2000
2000 episodes
episades
episades
episades
episodes
Q-leaming
HQL
Figure 6: Shows learning curves on various maze sizes with three different room layouts; either the room is empty it has either a U-shape obstacle or the room is stripped with horizontal walls. The performance of the agent is measured in the number of steps it requires to solve the task. A.2.2 Taxi Environment
Another task we consider the taxi environment [9] this environment, the agent is tasked to pick up passenger and bring them to a specific location. As illustrated in Fig. / the taxi environment a grid world composed of 25 cells (5 5 grid). At the beginning of an episode, the passenger is assigned a random initial location, which can only be in one of the four taxi stations depicted by the letters R, G. Y and Fig. right plot, and a final destination which any of the three remaining taxi stations. When visualising the environment, the location of the passenger is denoted by the letter in blue and the final destination by the purple letter. The initial position of the taxi is also randomly sampled, and to complete the task, the taxi will have first to pick up the passenger and then deliver him to his final destination.
This problem can be formalized by MDP. The state space S encodes the 404 reachable states. While the 25 possible taxi locations, the 4 possible destinations and the potential passenger locations suggest that there are 500 states. The states where the passenger is at the destination but the taxi is somewhere else are not possible and there are 24 consists of the six possible actions (move up, down, left, right, pickup. dropoff). The default horizon H considered for this environment is 200 steps. The initial state distribution uniformly chooses the cell in which the taxi starts the episode as well as the passenger's 's initial location and destination. The reward function assigns a positive bonus (+20) for successfully delivering the passenger, a penalty for illegal action such as inappropriate dropoff and pickup action (-10) and small penalty (-1) for each remaining step. The characteristies of the original MDP for this problem are the following 6 and H 200.
96 such configurations. The action space A
[S] 404, |A|
To apply HSQL, the following decomposition was considered:
(i) High-level MDP: The high-level state space only encodes the current passenger location and the final desired destination, hence |Sp| = 20. The high-level action space is composed of 8 possible sub- goals |A,1 = 8. Each sub-goal encodes one of the four special locations and whether the passenger should be picked up or dropped off. Since all possible initial configurations can be completed with only two sub-goals. first pick-up instruction and then drop-off instruction, the horizon of the high-level MDP is H 2.
(ii) Low-level MDP: The low-level agent needs to be able perform all primitive actions so A A. Then, the low-level state space encodes the current location of the taxi as well as the instructed sub-goal, yielding to state space of size S 200. Since the trip is evenly divided into two separate instructions, the horizon of the low-level agent Hi = 100.
By Theorem 3.1 we can observe that the low-level MDP is likely to dominate the bound and to drive the overall complexity of the problem. Ignoring the constant terms in the bound, our theory suggests that small improvement should still be possible. This is confirmed by our empirical results in Fig. 7 (left plot) which shows a significantly steeper learning curve for HSQL compared to Q- learning on the taxi task. In order to make the comparison between the two algorithms as fair as possible, we considered a range of possible hyperparameter values and for each algorithm, we only report the best-performing setting. The hyperparameters considered are the initial exploration rate
15

---

Q-learning
R:
:G
Number of steps
200
HSQL
:
100
0
Y
BB:
500
1000
Number of episodes
Figure 7: Left plot shows the learning curves of HSQL and Q-learning in the taxi environment. Right plot illustrates the taxi environment; the agent (yellow square) needs to navigate a grid world reach the pickup location (encoded by the blue letter) and drop off the passenger at its final destination (encoded as the purple letter). The remaining letters are the possible pickup and drop-off locations. Note that the taxi needs to learn how to navigate the grid world in order to avoid the walls represented by solid lines.
c E [0.1, 0.3. ... 0.7, 0.9] and the decay rate 5 E [1 10 10
4, ... - 10-7) Note that
we only considered the following decay function 6x+1 = cg 8k+11 where denotes the current episode number. The error bars obtained by running ten different seeds.
B The Option Framework and Goal-Conditioned HRL
As most of the existing theory on HRL 30 12 has been developed in the option framework, we recall below the definition of that framework and the connection has with the goal-condition HRL framework considered in this article. An immediate difference is that those previous works consider an infinite horizon setting while we focus on a finite horizon setting. For the remainder of this section, describe some other significant differences.
Let's first recall that the tuple M (S, deseribe a finite MDP, where a finite set of states, A is a finite set of actions, p(s' (s, is the probability of transitioning the state s' given that state action a was executed, r(8, a) is the reward distribution associated with the state action pair (s, a) and, lastly, is the discount factor. A policy S - A maps each state to action. An option tuple o = {Ip, Boy Jo where I, C is the initiation set, i.e. the set states where option can be started, 3, S - [0, 1] is the probability distribution to terminate in option in a given state and finally T. the intra-option policy, i.c. the policy followed until the option ends.
Whenever the set of primitive actions A is replaced by set of options O the original MDP M. becomes semi-MDP Mo = (So, O, po: ro, TO). The state space So S is the all initial and terminal states. O denotes the set of options and po(s', o, s) is the probability to end option in state s' given that it was started in state s:
po(s',0,5)
Σ P(s = s (o)o('))..
where P(sk = s'|s, n.) is the probability to reach state s' exactly & steps from state s under policy To. 0)) is the distribution of reward cumulated when starting policy лo in state s. Lastly, is the distribution of holding time, i.c. the number of primitive steps exccuted to reach s' from under policy n..
is possible to map the goal-conditioned HRL framework onto the options framework. Sub-goals would correspond to options, the initiation set of a given option includes all states where the corresponding sub-goal gaub available, the option will terminate with probability if the goal state has been reached or the H, time steps have been executed and terminate with probability 0 otherwise. Lastly, the intra-option policy n, corresponds to the low-level policy कy (:lgsu)) conditioned on the corresponding sub-goal.
16

---

From a theoretical standpoint, the key difference between the results in [11 30 and the ones presented in this article are that they assume the intra-option policies %, to be known. assume strong prior knowledge about the task, the number of potential intra-option policies will be prohibitive. In this article, we investigate algorithms that not make assumptions about the low-level policy and jointly learn the low- and high-level policies through interactions with the environment, thus going beyond what has been done for the options framework.
do not
17


Reviews:
[{"review_id": "3yp7Iz1SxJ", "reviewer": "Reviewer_VzQJ", "summary": "Provides a sample bound on the complexity of goal-conditioned HRL algorithms based on the two MDPs they are decomposed into, and a Q learning algorithm to leverage these findings. Formulates HRL as a two-level problem, where the upper level passes actions to the lower level policy. The work proves a lower bound on the complexity of the HRL formulation which pivotally scales according to the size of the high level action space and the reusability of the low level space. A new algorithm is introduced which identifies the need for a consistent low level action space, and this method is asssessed in four-room gridworld domains. ", "questions": "See the weaknesses section", "limitations": "Limited empirical assessment in multiple domains\n\nAdditional evidence of how the terms of the bound translate to empirical results would be insightful", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This work provides a clean proof with a highly understandable sketch and a strong intuition. Together, this provides an extremely clear and easy-to-read description of the sample complexity of HRL In addition, the theory provides some clear insights into how to understand other HRL work.\n\nThis work provides a simple idea applied to the existing framework of HRL in the description of the high-level training based on low-level performance. It also seems like adding the intuition of the shared upper-level complexity term would be useful for keeping the size of the upper policy action space small (by somehow limiting the goals), which is empirically verified in other HRL work.\n", "weaknesses": "Figure 1 is difficult to comprehend, somehow managing to be simultaneously overly simple (this is a basic construction of hierarchical RL) and overly complicated (what is the intuition for the equations on the right-hand side?\n\nThis work contrasts against the Options framework in the first paragraph of the background, without specific Ying what the options framework is. As a framework itself, the options framework also makes no assumptions about prior knowledge, no prevents from state abstraction, both statements made about the framework. \n\nThis work spends much of the earlier part justifying the context of the goal-based hierarchy, but it appears that other than the state-based complexity term, there is no strict requirement that the hierarchy be goal based as opposed to simply parameter based. As long as there exists a measure of the performance of the lower-level policy, it seems like the same reasoning would apply. \n\nThe empirical results are somewhat lacking. In particular, while the proof should apply generally to HRL contexts, the work only empirically verifies in maze environments, and maze environments which are constructed to amplify the advantages of the upper-level policy. A different kind of environment such as a mountain car or multiple inverted pendulum would have been interesting, notwithstanding an environment that requires a deep RL method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your feedback and for your interest in our work. In the following, we try to clarify your concerns.\n\nFigure 1 is actually composed of two independent figures, the leftmost schema describes the HRL framework and the rightmost plot is simply an illustration of the MDP decomposition induced by the HRL framework. It can be seen that the “original” MDP can be decomposed into a high-level MDP and low-level MDP. This decomposition is described in great detail in section 2.2. We agree that the original caption of Figure 1 is a bit vague regarding the rightmost plot. We will modify the caption to explain more clearly what we are illustrating, and explicitly refer to section 2.2 where a complete description can be found. \n\nThank you for pointing out this misleading statement about the option framework, we will make sure to introduce the option framework formally and correct the erroneous affirmation made about the framework.\n\nRegarding the additional experiment we agree with you that it would be interesting to investigate the performance on a different set of tasks. The reason why we investigated the maze environment first is simply because the hierarchical decomposition is natural in those environments and it is easy to modulate the complexity of the MDP i.e adding more rooms or adding more room layouts. Following your feedback, we will add experiments on the taxi environment to the final version of the paper.\n\nTo summarise based on your comments we intend to do the following modification to the final draft:\n- Update caption of Figure 1.\n- Introduce more formally the option framework and remove erroneous claims\n- Add experiments based on the taxi environment. \n\nBest regards,\nThe authors"}, {"review_id": "gqUqh9Go1b", "reviewer": "Reviewer_hRCv", "summary": "The paper takes an important step toward quantifying the benefits achieved due to hierarchical decomposition of an MDP by deriving lower bound on sample complexity of goal-conditioned HRL algorithms. The paper also proposes a novel hierarchical Q-learning algorithm that exploits goal-based hierarchical decomposition of an MDP into a high-level and a low-level sub-MDPs and jointly learns their policies. The authors evaluate hierarchical policies for different decompositions on original MDPs to validate when decomposition provides benefits and whether it aligns with the derived bound. \n\nThe paper is well motivated and clearly written. The ideas of the paper to quantify benefits of hierarchical decomposition are novel. The derived theoretical guarantees on the lower bound are sound. I suggest clarifying that the derived bounds only apply to tabular setting of RL i.e. discrete state space problems in the Introduction. The theoretical findings are  backed by empirical results on maze environments of different sizes with convincing insights. The empirical evaluation would benefit from diversification of domains and tasks not restricted to navigation, and an investigation of bounds when using bad and good decompositions for the same environment. ", "questions": "(I) How are the ideas of the Stationary Hierarchical Q-learning to overcome non-stationarity of the high-level policy related to the ideas in [1]? \n\n(II) Can you elaborate what it means to separate the original state space evenly between the two level of hierarchy? \n\n(III) Does the method apply only to dense reward functions?\n\n(IV) Would the bounds identify when a decomposition for an environment would degrade performance of the proposed algorithm compared to Qlearning? \n\nReferences:\n\n[1] Levy, A., Konidaris, G., Platt, R. and Saenko, K., 2017. Learning multi-level hierarchies with hindsight. arXiv preprint arXiv:1712.00948.\n\n[2] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, pages 2107–2116. PMLR, 2018.\n\n[3] Thomas Dietterich. State abstraction in maxq hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 12, 1999.", "limitations": "(Included in the weaknesses)", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(I) The paper provides strong theoretical guarantees on the lower bound of the number of episodes given a decomposition needed to learn an epsilon-accurate hierarchical policy, which also serves as a lower bound to learn an epsilon-accurate optimal policy. \n\n(II) The paper also identifies properties relating to state and temporal abstractions and the size of the high-level action space from the derived bound that can improve sample efficiency.\n", "weaknesses": "(I) The assumptions regarding the scope of the derived bounds restricted to a tabular setting need to be clarified in the Introduction. \n\n(II) All experiments are on maze environments of different sizes. While the current analysis is convincing for navigation tasks, it will be interesting to see if the benefits of decomposition and the derived bounds align for more diverse domains and tasks that not restricted to just navigation e.g. officeworld [2], taxiworld [3] etc.\n\n(III) It is not clear how the bounds will identify when a decomposition is bad enough and would degrade the performance compared to non-hierarchical algorithms. \n\nMinor errors:\n(I) Line 48: proposes -> propose", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your enthusiasm about our work and for your detailed feedback.\nIn what follows we address the concerns raised during your review.\n\ni) “*The assumptions regarding the scope of the derived bounds restricted to a tabular setting need to be clarified in the Introduction.*”\n\nAt the moment these assumptions are stated in the background section, but we agree with you, we could contextualise the work more thoroughly in the introduction allowing us to mention those assumptions. We will change this section accordingly.\n\nii) “*It will be interesting to see if the benefits of decomposition and the derived bounds align for more diverse domains and tasks.*”\n\nWhile it would be interesting to investigate the performance on a different set of tasks, we choose to investigate maze-like environments because the hierarchical decomposition is natural and it is easy to modulate the complexity of the MDP i. e. adding more rooms or room layouts. The main purpose of the article is to better understand the relationship between the sample efficiency and the characteristics of the decomposition. To that end we focus on environments for which it is possible to modify at will the MDP’s complexity, hence yielding a diverse set of decomposed MDPs. This allows us to empirically verify the properties suggested by the derived lower bound and confirms that the introduction of the hierarchical machinery becomes more beneficial as the task’s complexity increases. That being said, we will integrate experiments on the taxi environment in the final version of the paper.\n\niii) “*It is not clear how the bounds will identify when a decomposition [...] would degrade the performance compared to non-hierarchical algorithms.*” and “*Would the bounds identify when a decomposition for an environment would degrade performance of the proposed algorithm compared to Q-Learning?*”\n\nIn theory, we can compare the HRL lower bound in Thm 3.1 and the RL lower bound given in eq. 4 to quantify if the problem could be solved more efficiently with an HRL algorithm. The idea is that if the HRL lower bound is larger than the one for standard RL, this may indicate that the decomposition is not necessarily helpful so we should proceed with caution. However, we should note that in practice, there is no guarantee that any proposed algorithm matches the lower bound efficiency. However, we agree that it would be interesting to propose a provably efficient algorithm for HRL. We will mention this as a potential future research direction in our conclusion. \n\niv) “*How are the ideas of SHQL to overcome non-stationarity of the high-level policy related to the ideas in [1]?*”\n\nThe idea used in [1] is similar to the one used for our algorithm, Stationary Hierarchical Q-learning. The idea is to leverage the fact that we know that an optimal low-level policy will reach the subgoal. In the off-policy case considered in [1] they use a form of hindsight correction, while in our on-policy scenario we have to filter the transitions on which we perform the update. For both the principle is the same: the non-stationary induced by the low-level changing behaviour is mitigated because high-level updates are computed using only transitions that exhibit a near optimal behaviour, but the difference is that we consider on-policy updates. We will make sure to refer to [1] when we discuss the update to highlight the similarity between the methods.\n\nv) “*Can you elaborate what it means to separate the original state space evenly between the two levels of hierarchy?*”\n\nState abstraction is an important concept in HRL that implies that, depending on its level, the policy needs different information about the current state. In the framework we consider, the state representation is decomposed (or separated), the high-level observes a part of the original state information and the low-level observes another part. For example, in our experiment, the high-level is only aware of the current room ID and the low-level only observes the current location within the room. As large state spaces are challenging for RL algorithms to explore, the state abstraction induced by the HRL framework represents an interesting opportunity to mitigate the issue of exploring a large state space. The “max” operator in equation 6 indicates that the overall HRL sample complexity is driven by the decomposed MDP (either low- or high-level MDP) with the largest sample complexity.  Hence, efficient decompositions will have to balance the complexity as evenly as possible between the two MDPs. The decomposition of the state space is then an important aspect to consider when finding this balance. However, our lower bound also highlights that other characteristics of the decomposition such as the subgoal space’s size and the respective time horizons have also an influence on the final sample complexity.  We will clarify the above in section 3, in the paragraph dedicated to the interpretation of the bound. \n\nvi) “*Does the method apply only to dense reward functions?*”\n\nWe only assume that the reward is in an interval [-a,b] with a, b >= 0, this assumption is flexible enough to encode dense or sparse reward functions. So, our theory is also valid for sparse reward functions. \n\nBased on your feedback we propose the following list of the modifications:\n- Mention the tabular assumption in the Introduction.\n- Clarify the usage of the bound as explained above\n- Make correction on line 48: proposes -> propose\n- Add reference to [1] for the update “trick”.\n- Add experiments on the taxi domain.\n- Add clarification about the state space state decomposition.\n- Mention the design of provably efficient HRL algorithm as a future research direction. \n\nBest regards,\n\nThe authors\n\n[1] Levy, A., Konidaris, G., Platt, R. and Saenko, K., 2017. Learning multi-level hierarchies with hindsight.\n"}, {"review_id": "KE94WQSYYZ", "reviewer": "Reviewer_2sTV", "summary": "The paper presents a theoretical analysis of the sample complexity in goal-conditioned hierarchical reinforcement learning (HRL) and establishes a lower bound using hierarchical decomposition to quantify it. Additionally, the paper empirically validates the theoretical results by examining the sample complexity of the proposed hierarchical algorithm on several toy grid-world tasks.", "questions": "Q1. The selection of the sub-goal space plays a vital role in the efficiency of the HRL algorithm, as different choices of sub-goal spaces can result in varying sample efficiencies, such as in HIRO [1], HRAC [2], HIGL [3], and others [4]. Unfortunately, in Theorem 3.1, the authors do not analyze the impact of different sub-goal spaces on the sample efficiency of HRL. Therefore, I find the theoretical results to be trivial.\n\n[1] Nachum, Ofir, et al. \"Data-efficient hierarchical reinforcement learning.\" Advances in neural information processing systems 31 (2018).\n\n[2] T. Zhang, S. Guo, T. Tan, X. Hu and F. Chen, \"Adjacency Constraint for Efficient Hierarchical Reinforcement Learning,\" in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 4, pp. 4152-4166, 1 April 2023.\n\n[3] Junsu Kim, et al. \"Landmark-guided subgoal generation in hierarchical reinforcement learning. \" Advances in Neural Information Processing Systems, 34: 28336–28349, 2021.\n\n[4] Lee, Seungjae, et al. \"DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learning.\" Advances in Neural Information Processing Systems 35 (2022): 13668-13678.\n\nQ2. Another limitation of the paper is the absence of a comparison between the proposed method and other existing HRL algorithms in the experimental section. It would be valuable to include such a comparison to provide a more comprehensive evaluation of the proposed approach", "limitations": "See Questions", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I commend the authors for addressing an important theoretical problem in the field of HRL and deriving a lower bound to quantify the sample complexity of goal-conditioned HRL.", "weaknesses": "One significant aspect that the paper lacks is a thorough theoretical analysis regarding the selection of sub-goal spaces in continuous environments or sets in discrete environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the time you dedicated to evaluating our work. \n\nWe thank you for recognising that we are working on a “critical problem in HRL”. Our bound highlights the importance of the design of the subgoal space. In particular, the high level action space,which in our framework corresponds to the subgoal space, comes directly into the bound in equation 6. Additionally, the high-level action space's size impacts both the high-level and the low-level MDP. The aim of our analysis is to provide a tool that evaluates a given decomposition and relates the characteristics of that decomposition to the sample efficiency. Therefore, our bound provides a sanity check to determine whether a proposed decomposition could be beneficial. Investigating methods that learn a subgoal representation (or space) is beyond the scope of our paper, although it is a challenging problem of great interest so we will mention it as a future research direction.\n\nThe lower bound we proposed is valid for any hierarchical algorithm; the point of our experimental validation was to show that the dynamics suggested by the lower bound manifest themself empirically. We proposed this algorithm to empirically observe some of the insights suggested by our lower bound. Of course, one could think of other algorithms for this problem, but that is beyond the scope of our work. The lower bound suggests that higher efficiency gains are obtained when the given decomposition balances as evenly as possible the complexity between the two MDPs (high- and low-level). This is observed empirically by our experiments that start with a high low-level complexity and as we increase the high-level complexity the improvement of the hierarchical method becomes more apparent.\n\nBest regards,\nThe authors\n"}]

Author rebuttal:
We are grateful for the time and the effort the reviewers dedicated to our work, which will strengthen our article. We are also pleased to see that several of the reviewers were enthusiastic about our work, especially on the writing: “clean proof with a highly understandable sketch and a strong intuition”, “provides an extremely clear and easy-to-read description of the sample complexity of HRL” and on the broader impact “provides some clear insights into how to understand other HRL work”.

Please find a response for each review question as a direct reply to the reviewer asking it.
 
Best regards,
The authors

Meta-review: Hierarchical Reinforcement Learning (HRL) algorithms are attracting a lot of attention but their theoretical understandings are quite lagging behind. This paper offers some of the first sample complexity bounds for the proposed class of goal-conditioned RL algorithms, and uses it to design new RL algorithms. The reviewers are unanimous about accepting this paper.
Decision: Accept (poster)