Provable Hierarchy-Based Meta-Reinforcement Learning
Authors: Kurtland Chua
Qi Lei
Jason D. Lee
Venue: ICLR 2022 Submitted (2022)
Keywords: RL theory
regret bounds
hierarchical RL
meta-RL

Abstract: Hierarchical reinforcement learning (HRL) has seen widespread interest as an approach to tractable learning of complex modular behaviors. However, existing work either assume access to expert-constructed hierarchies, or use hierarchy-learning heuristics with no provable guarantees. To address this gap, we analyze HRL in the meta-RL setting, where a learner learns latent hierarchical structure during meta-training for use in a downstream task. We consider a tabular setting where natural hierarchical structure is embedded in the transition dynamics. Analogous to supervised meta-learning theory, we provide “diversity conditions” which, together with a tractable optimism-based algorithm, guarantee sample-efficient recovery of this natural hierarchy. Furthermore, we provide regret bounds on a learner using the recovered hierarchy to solve a meta-test task. Our bounds incorporate common notions in HRL literature such as temporal and state/action abstractions, suggesting that our setting and analysis capture important features of HRL in practice.

Under review as a conference paper at ICLR 2022
PROVABLE HiBRARCHY-BASER META META-REINFORE REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Hierarchical reinforcement learning (HRL) has seen widespread interest as ap- proach to tractable learning of complex modular behaviors. However, existing work either assume access to expert-constructed hierarchies, or use hierarchy- learning heuristics with no provable guarantees. To address this gap, we analyze HRL in the meta-RL setting, where learner learns latent hierarchical structure during meta- training for use in a downstream task. We consider a tabular set- ting where natural hierarchical structure is embedded the transition dynamies. Analogous to supervised meta-learning theory, we provide "diversity conditions" which, together with a tractable optimism- based algorithm, guarantee sample- efficient recovery of this natural hierarchy. Furthermore, on a learner using the recovered hierarchy to solve a meta-test task. Our bounds incorporate common notions in HRL literature such as temporal and state/action abstractions, suggesting that our setting and analysis capture important features HRL in practice.
provide regret bounds
INTRODUCTION
Reinforcement learning (RL) has demonstrated tremendous successes in many domains (Schulman al., 2015 Vinyals et al., 2019 Schrittwieser et al. 2020), learning near-optimal policies despite limited supervision. Nevertheless, RL remains difficult to apply to problems requiring temporally extended planning and/or exploration (Ecoffet et al. 202T). A promising approach to this problem is hierarchical reinforcement learning (HRL), which has seen continued interest due to its appealing biological basis. its most basic form, HRI. seeks to decompose tasks into sequence of skills, each of which is casier learn individually than the full task. By restricting the agent to using learned skills, the search space over policies can be greatly reduced. Furthermore, learned skills can induce simpler state and/or action spaces, simplifying the learning problem. Finally, learned skills with useful semantic behavior can be reused across tasks, enabling transfer learning.
Naturally, hierarchy- baased learner is limited by the quality of skills that are made available and/or learned. Accordingly, many empirical works have proposed algorithms for online skill learning in the context of single RL task (Nachum al. 2019a; 2018). These approaches have been exper- imentally demonstrated to be effective in finding useful and interpretable skills. Other approaches consider the skill learning problem in the context of meta-RL (Frans et al.) 2018), or in the reward- free setting (Eysenbach et al., 2018). Nevertheless, the heuristics and algorithms proposed in these empirical works do not provide any provable guarantees on the quality of learned skills.
On the other hand, theoretical analyses have mostly focused on how learners benefits from having access to skills. For example,/Fres Fruit & Lazaric (2017) provide a regret bound on learning with skills in the infinite-horizon average reward case. Meanwhile, in the meta-RI. setting, Brunskill & Li 2014) considers the problem of finding and using skills in a continual learning setting and provides sample complexity analysis. However, these analyses either sidestep the question of how the skills are obtained, or do not address the problem in a computationally tractable manner.
In this work, we aim to take a step towards providing provable guarantees for hierarchy learning through tractable algorithms. We focus on the meta-RL setting, in which a learner extracts skills from set of provided tasks which are then used in a downstream task. We work in the tabular case, assuming the transition dynamics of the given tasks share latent hicrarchical structure induced by predetermined clustering and bottlenecks. Our contributions
follows:

---

Under review as a conference paper at ICLR 2022
1. "Diversity conditions" ensuring hierarchy recovery. We develop natural optimism- based coverage conditions which ensure that bottlenecks embedded in the transition dy- namics are detectable by solving provided meta-training tasks.
2. A tractable hierarchy-learning algorithm. We provide algorithm that provably learns the latent hierarchy from interactions, assuming the coverage conditions above. Our method has sample complexity sealing S) in the leading term compared to O(T5*A) A) for a brute-force method, where T are the numher of tasks, 5 is the number of states, the number of actions, and K < SA is the number of skills learn.
3. Regret bounds on downstream tasks. We provide regret bounds for learners that apply the extracted hierarchy from meta-training on downstream tasks. Furthermore, we show an exponential regret separation between hierarchy-basee and sherarchy-obliioou learners for a family of task distributions, corroborating prevailing intuitions regarding when/why HRL helps. In particular, hierarchy- basedd learners incur regret bounded by O(VH2N) while hierarchy-oblivvee learners incur worst-case regret of at least 0(2"/2/H2)
NOTATION
We now introduce notation which we will use throughout the paper. We write [K] = (1..... (1..... K}. Furthermore, we use the standard notations O O to denote orders of growth, and Ô 6, to indicate suppressed logarithmic factors. We use ((x) to denote the Dirac delta measure on
We work with hoite-horizon Markov decision processes (MDPs), defined as a tuple M (S, A. P, r. H), where S is the set of states, A is the set of actions, P : S x A S + [0.1] are the transition dynamics, r assume stationary dynamics unless otherwise noted, in which case p(A) is the dynamies at time step h. For constants relating to horizons, we will define [M] == {O..... ........ H - 1}. Given policy
A ~ [0, 1] is the reward function, and H is the horizon. We
T [H] x A. we define the value functions
H-1 rssk, ax)
H Σ r(sk, ax) (sh, = -0 b==
(8) = E
Σ A==
8h = s and (h(s,a==
= E
where SK+1 P(. Sk, 0x) and ag Ty (Sx). Furthermore, write V and Q" to denote optimal value functions obtained by maximizing over π (and are attained by the optimal policy x*). When learner plays -1,-.., AN in M, we define its regret
Regret b (M)
Σ
Vi (50) (8o).
We use e to denote a terminal state. We T. denote the (random) trajectory generated by æ. For state and length-H trajectory we write 8 E T, if for some h [H]. We define (s.a) E similarly. Finally, given an MDP M, M(HH) denotes a copy of M with a doubled horizon.
3 SETTING
We work in the tabular meta-RL setting. The learner can access T meta-training MDPs ((S, A, P,, Heery = (Meherrry Note that IP and r, both vary across tasks. We set S = [S] and = [A]. After interacting with these tasks, the learner presented with a meta-test MDP (S, A, (T,,T, Hf), where the learner seeks to minimize its regret. We assume, without loss of generality, that the MDPs have a shared starting state 8p- For meta-learning to succeed, the MDPs must have shared structure. We focus on the following notion of shared hierarchical structure:
Definition 3.1 (Latent Hierarchy). Let } be a partition of the state space S into clusters. We associate with each cluster Z a set entrances Ent(Z) C Z and a set exits Ext(Z) C Z x A. We say that the tasks have latent hierarchy with respect to ([Ze). Ent(-), Ex)(-)) if for any Z.:
(a) For any (s) (Ze x A) Ext (x)) (P(( 18, a,))) is constant over and supported on Z...
2

---

Under review as a conference paper at ICLR 2022
(b) For any (s,a) E Ext(Zz) there exists t, t' with t' such that P. (:1 s,a) & Pe(. s, Furthermore, Pr(- 8, a) is supported on U. Ent Ze) for any E [7].
Definition 3.1 partitions the shared state space of the MDPs into clusters such that (1) non-exit (s, a) dynamics do not change be- tween the MDPs and (2) exits are bottlenecks between clusters.
Example 3.1 (Gated Four-Room), Figure illustrates the gated four-room environment along with sample task. The environment has a latent hierarchy with respect to the rooms outlined by colored gates (which can be open closed). Entrances colored aqua, while exits are marked by arrows.
Although we assume single fixed starting state, we can model uuskddepndeent initial states by appending a dummy state so- A dummy action ag then takes the agent to the starting state for the task. Observe that (so, Gp) is exit, and therefore must transition to an entrance.
To how Definition 3.1 captures intuitive notions of hierarchy in practical settings, we provide an example of a continuous setting roughly fitting into our framework:
Example 3.2 (The Alchemy benchmark). Alchemy (Wang al. 202T) is recently proposed empirical benchmark for meta-RL, where the agent needs place a stone series potions ob- tain some desired appearance, as illustrated in Figure 2 Dipping stone into potion traverses an edge (determined by the potion) in graph where nodes are possible stone appearances. We focus on task distributions that randomize the edges of this graph (i.e., potion positions and feasible stone appearances are fixed). Then, the set of obtainable MDPs has latent hierarchy where dipping the stone into any of the potions is exit. Indeed, other than dipping the stone into potion, all other actions (e.g., moving the stone around the room) have the same dynamics in all tasks.
The gated four- room setting, with task quiring navigation from the green square the star.
Figure I:
For convenience, we will define several relevant notions. First, for any cluster 7, we define its interior 7 == (Z xx) (Z). Furthermore, let (S) = U. Fat (Ze) denote the of all entrances and Ext(S) = U. Ext(xx( (Z)) the set of all exits. Finally, we define
K = [Ex((S) M = sup (Z.)
= [S)
Alchemy. Placing stones in potions moves the agent through latent graph of object properties
Figure 2:
so that K and L are the total number of exits and entrances, respectively, while M is the maximal number of exits from any cluster.
Query Model. We work in the online setting, where the agent interacts with the tasks by playing policies from the initial state 8g. During meta-training, we allow the agent to interact with the environments using unbounded number of timesteps for each trajectory before resetting. We then compute query complexity in terms of the total number of timesteps spent in all tasks in total.
4 META- META-TRAINING ANALYSIS
In this section, we outline an algorithm for uncovering the latent structure that can be used for downstream tasks. Recall that exits are defined by changing dynamics between tasks. To quantify the number of samples needed for exit detection, we define the following quantity:
Image from Wang 2021) extracted from larger figure with other modifications (License).

---

Under review as a conference paper at ICLR 2022
Definition 4.1 (3-dynamics separation). There exists B 0 such that for any t, t'
[T] and
(s, (s E Ext(S), Pr(- s, s, Per(: s,a) = [ 8, s, ( av 2 B.
In defining B above, we ensure pogo-prbbability exit detection with 0²)/3²) samples. Note that there is brute-force approach to learning the underlying structure: one can learn Pe(- s, a) for all (s. and [T], and iterate over (s, a) check for changing dynamies. This can be done with query complexity OT A/B²). However, under reasonable "coverage" assumptions outlined in the next section, this query cost can lowered to Ö(TK5/8²).
4.1 DEFINING NOTION OF COVERAGE
In supervised meta-learning, "diversity conditions" ensure that the meta- meta-training tasks reveal the underlying latent structure (Tripuraneni al., 2020 Du et al., 2020). We provide analogous condi- tions ensuring that .M,.... ..... Mr "cover" the latent hierarchy. Since solving max, V* (so) requires fewer samples than learning P. we expect such conditions to provide sample complexity gains.
Visitation Probabilities and a-Importance. Minimally, exits should visited by optimal poli- cies of the meta-training tasks for coverage. We thus define the following notion:
Definition 4.2. Fix MDP M (S, A, A, H), and let (s,a) S x A. Construct modified MDP M (s, a), where (s, a) brings the agent to a terminal state with no reward. Then, we say that (s, a) a-important for M if Vo (x,,a) (s0)) V. (sa) a.
The a-importance condition quantifies the value gap between policies that can use (s, a) and those that cannot. For example, consider the task in Figure 3 Any with (so) 0 must visit the marked (s, a) pair with some probability. Therefore, (s, a) is Vo"" (sp)-important, This sug- gests that high importancc implies high visitation probability by near- optimal policies. The following result, proven in Section A formalizes this connection:
Lemma 4.1. If (8,a) is a-important for M, then for any policy n, (*(8p) - V (so) < implies that P((s,a) E Tx)) (a e)/H.
Figure Illustrating a- importance. Since the black arrow is the only path to the goal, it is Vi (so)-important.
A Preliminary Coverage Assumption? Lemma 4.1 suggests simple coverage condition: for any (s, a) & Ext(S), assume that there exists t, [7] that (s, a) is a-important for and l', and P.. a) * (: s, a). However, as the following example shows, this condition excludes natural settings:
Example 4.1. In Example gates are either open closed. For closed gates, the associated (s, a) pairs are unimportant for any goal. Thus, if (s,a) a) is a-important for some f, E [T) with a 0, then PP s, a) (. (-1 a). and no change dynamics can detected using n, and xy.
TI
Figure 4: The black arrow is not a-significant for one of the tasks, but is nevertheless "covered" by optimistic imagination.
Figure Using optimistic imag- ination for exit detection.

---

Under review as a conference paper at ICLR 2022
Figure 4 iillustrates how the proposed condition fails in covering exit marked with a black arrow. While (s, a) is unused by optimal policies in the first task, it is Vo (su) -important for the second.
Optimistic Imagination
Coverage Mechanism. The proposed assumption fails because there are cases where exits are only a-imppotant in certain configurations (e.g., only open corridors a-important in Example 3.1). In such cases, near-optimal policies only ever one configura- tion of the dynamics for those exits and thus are insufficient for formalizing exit coverage.
As alternative, consider the following hypothetical scenario in the context of Figure an agent has solved both tasks, achieving optimal values Vi and V/- Additionally, in the process of learning the second task, the agent has learned P2(-) 4). If the agent then relearns the first task while setting P. 4) f P2(.1 4), it would obtain new value Vi >> V/". Thus, can reasonably conclude that the black arrow must have been exit. We illustrate this process in Figure 5 where is the optimal policy after "borrowing dynamics." " The learner could then run T for exit detection.
We refer to the counterfactual reasoning about the dynamics used above optimistic imagination. Unlike the preliminary condition, optimistic imagination only requires that an exit be important for task and induce value gap in another when borrowing dynamics weaker condition in many cases. With the above intuition in mind, we now present the main coverage assumption.
Assumption 4.1 (a, coveraaee Assume (Me)re have latent hierarchy with respect to (1 ((Za). Ent(-), Ext(-)). There exists a, S such that for any ((11,0),,. (Sn, [n)) (Snn)...,,,,,,,,,
S Ext(S),
(a) For any E [n]. (st, a;) is a-important for some meta-training MDP M,
(b) For some Me with E [T], if we construct a new MDP M4 (S, S,P, H) via [ (- s) (s,a)= (
[TMMi
P(- s,a) ( s, otherwise
iee. we replace (si, a,) dynamics with those from Mi then VM (so) VMe (sa) + C.
Informally, (a, (). -coverage ensures that optimistic imagination can borrow dynamics for unknown exits from other tasks to find a better optimal policy Most reasonable task distributions satisfy (a, --coveree with enough tasks we provide heuristic explanation in the appendix.
4.2 ALGORITIM OUTLINE
In this section, we outline the algorithm that we use to detect exits. Our procedure can be naturally divided into three phases: task-solving phase, reward-free phase, and an exit detection phase. Throughout, we illustrate our steps in Figure [ showing how Phases and II allow the learner to find the imagined policy æz. The full details of the algorithm are provided in Section A.I
4.2.1 PHASE I: -PECCIIC DYNAMICS LEARNING
First, we solve Mı,... 1h,...,M,, with UCBVI. Using UCBVI regret bounds from Azar et al. (2077) together with Lemma 4. we can guarantee that all a-important exits are sufficiently visited. Thus, during optimistic imagination, the learner would able to borrow high-quality estimates of exit dynamics from other tasks. For example, learner that has solved both tasks in Figure 4 can borrow open blue gate dynamics for use in the first task during optimistic imagination, in Figure 6
4.2.2 PHASE II: REWARD-FREF RI.
In order to perform optimistic imagination, the learner also needs to sim- ulate non-borrowed (s, a) dynamics. This is done by fully learning the dynamics of one of the tasks, proving a template Po. Learning Pu is achieved using reward-free RL (Jin et al. 2020).
Figure 6: Phase con- tribution to learning in Figure 5 marked with an arrow.
? Incorppraaingg the preliminary condition into Assumption | can further weaken the required task diversity. However, our algorithm handles this extension trivially, and thus focus optimistic imagination.
5

---

Under review as a conference paper at ICLR 2022
To understand the necessity of Phase II, note that in Figure near- optimal policies have no coverage over states past the blue gate (as shown by the red region). Therefore, dynamics estimates from Phase I are insufficient for optimistic imagination. On the other hand, by learn- ing the dynamics fully in one of the tasks (and thus learning the green region), the learner can nevertheless simulate the dynamics if the blue gate were open and successfully recover ZI.
4.2.3 PHASE III: EXIT DETECTION
Having completed the previous two phases, the learner can use optimistic imagination to detect exits. In particular, consider modified value iteration method where the learner optimistically chooses dynamics esti- mates from Phases I and II to perform Bellman backups. This implicitly defines an MDP whose optimal value is at least as large as Mr in As- sumption 4.1 M, would have been feasible for this process. Analo- gously with a-importance, this value gap implies that the corresponding optimal policy πz for this new MDP must visit an (s, a) pair whose dynamics are borrowed. There- fore, by playing TT, the learner can determine a new exit.
Figure 7: Phase II con- tribution. Optimal pol- icy state coverage (red) is insufficient for learn- ing æz, which requires the green region.
4.3 TRAINING GUARANTEE
We now outline our main result for the algorithm in Section We first define a "hierarchy oracle" that will used downstream tasks:
Definition 4.3 (Hierarchy oracle). Let @s and @p denote successful and failed termination, respec- tively. Consider any tuple (z, f, r, H) such that x Ent(S), f Ext(S) + (es, @F), ri reward function, and H S H. Such tuple induces an MDP M(x, f,r, H) (s. A, whose starting state is and whose transition dynamics is given by
(8((s,))) a))
(s,a) E Ex((S)
Py( 8) =
8(s)
8 S (es,
P. 8.
otherwise, for any / [T].
An e-suboptimal hierarchy oracle, when queried with any valid (z, f,r, H), returns an e-suboptimal policy for M(x, f.r,
To motivate Definition 4.3 observe that learning a new MDP with the same latent hierarchy only requires visiting exits (as reward-free learning has coverage over cluster interiors). This, in turn, can be achieved by agent that has policy for reaching any exit from every entrance in any cluster. We emphasize that the learner does not need to know the states the actual clusters themselves. Formally, for entrance in cluster Z and exit
Ext(Z), we can query the hierarchy oracle with (r, 1 ((:.) = e] I. = θs] H) to obtain the desired reaching policy. Disconnecting the clusters ensures that the learner cannot use any other exits, and thus the validity of the policy under any MDP that has the same latent hierarchy
Our meta- trata-traiiing guarantee ensures that the hierarchy oracle is implementable:
Theorem 4.1 MMta--rrining guarantee, informal). Under Assumption 4.7 and other assumptions in Section A.2 the data obtained from the algorithm in Section 4.2 allows for:
(a) implementing an e-suboptimal hierarchy oracle, and
(b) determining, for every E Ent(S), the reachable exits in the cluster containing
simultaneously with probability at least 1 p. Furthermore, this is achieved with query complexity
ò O min
KL
ac2 + SA KS²AA
KS
S
S2
poly(H) (H).
min(a, 2)2
min(E,
min(E, C)2
As side effect, the reachability of from he determined from the predicted value for the prior query.

---

Under review as a conference paper at ICLR 2022
As point of comparison, have the following guarantee on brute-force hierarchy learning:
Theorem 4.2. The brute-force approach outlined in Section A.3 mines the set of exits with high probability and query complexity
under Assumption 4.7 (a), deter-
ò
S²
A
SA a
S
poly(H).
When a, and are of the same order, we that the proposed method incurs smaller query complexity compared to brute force learner that has only learned the exits. We provide proofs of both results in Section A along with all other necessary assumptions and full algorithm details.
5 HETA-TEST ANALYSIS
In this section, we provide regret bounds on learning an MDP MTg using the hierarchy oracle. We first characterize family tasks for which one can achieve improved regret bounds. Furthermore, we provide sufficient conditions ensuring that using the hierarchy incurs low suboptimality.
5.1 ASSUMPTIONS
In this section, we outline the assumptions that we make to prove regret bound on the meta-test task. Let MTg = AS,A,PTTs PTg. H) be the meta-test MDP. We assume that PTg( s,a) = Pt(- s, a) for any (s, & Ext(S) and t E [T]. Our first assumption restricts our attention to meta-test tasks which are compatible with the hierarchical structure:
Assumption 5.1 (Task Compatibility). There exists a cluster Z" such that rrg is supported on (z*) U Ext(S). Furthermore, there exists an optimal policy n² satisfying
(a) Conditioned on St. E Z", we have that (sw axe) & Ext(Z*) for h almost surely.
(b) The number of exits encountered by nt is bounded by Hett with probability Ç.
Hierarchical compatibility. Intuitively, Assumption 5.1 suggests that the task can be decom- posed into (Z*) )-sarchhing phase and a within-(Z") (2*) phase. This decomposition captures the goal- conditioned RL setting, which has been studied extensively in recent empirical works (Nachum al., 2019a; Levy al., 2018) Nachum al. 2018). We expect the hierarchy oracle reduce the complexity of exploration in both phases. Thus, these conditions ensure compatibility with the learned hierarchy.
Temporal Abstraction. Since hierarchical learner makes decisions upon entering a new cluster (to decide which exit to use/whether to stay), hierarchical plamning can reduce the planning horizon. Condition (b) quantifies this reduction. Note that in most practical settings, a learner that has access good sub-skills achieve low failure probability even with modest values of Heg.
Hierarchical Suboptimality. Restricting the learner executing hierarchical policies can greatly reduce the search space. While this reduction leads to improved regret bounds, this also incurs approximation error, as the optimal policy may not lie this restricted class. We refer this error as hierarchical suboptimality. We will show that hierarchical suboptimality is controllable with appropriate conditions on Pr, which require the following notions of reaching times:
Definition 5.1 (Reaching times). Fix a cluster Z, starting and goal states 8,g E Z, and planning horizon H < H. For any policy n. let (so, $1, s.. be the states visited by from s, where 80 = Then, we define
(s,9)) min { h 0, {o.......i
sh g and sN E Z for H' < h <hju H1
(7,),)) inf [T] [s
(s.) = inf P(T h) > 0}.

---

Under review as a conference paper at ICLR 2022
In words, (5, g) is the time takes to reach state from while remaining within the same cluster. By minimizing this quantity in expectation over all policies, we obtain T (8. g)- Finally, Twin (s, 9) is the minimum time for which it is possible to reach from 8. Definition 5.2 (Regular and low-variance dynamics), There exists a, 8,7 0 such that for any cluster Z, states 8,9 Z, and horizon H H,
(a) ((a, ()-uneeliabilitt) For any deterministic policy with E (8, g)] - Th
T7 (5,0) < a.
(8,g) has sub-Gaussian upper tail with variance proxy T (s.g)}² T H
(b) (y-goal-reaching suboptimality) (s. S t))"mmimms)))))
To understand (a, -)uunelliayility note that the condition only considers near-optimal deterministic policies. Therefore, (a) quantifies the randomness in 7"" (s. derived from the transition dynamics. On the other hand, 7-goal-reaching suboptimality quantifies the regularity ing whether near-optimal goal-reaching policies nearly achieve the optimal expected reaching time. Deterministic environments satisfies these conditions with a oc and / ? 0. We provide an extended discussion of why these quantities control hierarchical suboptimality in Section B.5 Note that the guarantees of Definition 5.2 scales with the cluster width, and thus we have the following final assumption:
the dynamics. measur-
Assumption 5.2. For any cluster Z and 8, E Z with s + g. Tmin (s,g) S W. Furthermore, Han W < H.
Assumption 5.2 limits the length of the subtasks within each cluster. This is consistent with hieserchy-based methods in practice, with skills only being executed for a limited amount of time. This width bound, together with Assumption 5.1 suggests that π requires O( timesteps with high probability. Therefore, the condition Hef W < H means that the task horizon is much longer than the minimum time required to complete the task, which often holds in practice.
5.2 META-TEST REGRET GUARANTEE
We note that Assumption 5.1 implies that the hierarchy oracle induces "high-level" MDP. We have the following regret bound on applying EULER to this MDP:
Theorem 5.1. We work under Assumptions 5.7 and 5.2 Furthermore, assume that the learner has access to e-suboptinal hierarchy oracle guaranteed by Theorem 4.1 where < Then,
learner that applies the procedure in Section B.2 to MTg incurs regret
Regret(N) S WH Ha + NEsubopt
Esubopt (1 + Hot + B Han)e +
H + +11++))V Han
W + ÇH.
with high probability.
Observe that the irreducible hierarchical suboptimality Esubopt (i.e. when 0) tends zero 7, 33, O. In particular, environ- ments with deterministic in-cluster dynamics do not incur hierar- chical suboptimality. We prove this regret bound in Section
Zi
When does knowing the hierarchy help? Consider the binary tree environment in Figure All of the leaves take the learner a state with exits with probability 1/2, with the exception of special leaf (" that does so with probability (1/2) + Rewards can only be collected upon performing one of the exits (bluc/purple). To achieve low regret, a learner has to quickly identity E and the correct exit.
Z2
Z3
We consider the set of task distributions indexed by l" that ran- domize the swward-granting exit. Knowing the hierarchy amounts to knowing L* reducing the exploration problem determining the correct exit. However, a hierarchy-oblivee learner needs to explore the tree, leading to regret that exponential in the tree depth. Formally, have the following result:
Figure 8: The hard instance in
Theorem 5.2
8

---

Under review as a conference paper at ICLR 2022
Theorem 5.2. There exists famity of task distributions such that any dierarchy-oblivion learner incurs expected regret lower bounded by 022 VH²N) on at least one task distribution. In con- trast, leaneer with access a O-suboptima hierarchy oracle incurs regret bounded by O(VH²N) with high probability, over any sampled task from any of the task distributions.
We prove this result in Section B.4.3 using recent results by Domingues et al. (021)) which demon- strate that the set of binary tree subproblems above form a set of minimax instances for any RL algorithm. This separation result suggests that hierarchy-based learners gain in situations where temporally extended exploratory behaviors are needed. This corroborates the experimental findings of Nachum et al. (2019b), which attributes the benefits of hierarchical RI. to improved exploration.
6 RELATED WORK
Hierarchical reinforcement learning has been studied extensively (Suttonn et al. 1999 Parr & Russell 1998 Dietterich et al. 1998) Vezhnevets et al.] (017). An early approach formalizing the use of hierarchies in RL is the options framework (Sutton et al. 1999), which fixes a finite set of available skills/options. Since then, a large body of work has focused on designing methods for learning and
adapting these options during the learning process (McGovern & Barto 2001] Menache al. 2002] Simsck & Barto 2004 Mann et al., 2014). Of particular note is the work of Frans et al. (018). which learns a finite set of neural network sub-skills in the meta-RL. setting. On the other hand, Laplacian-based option discovery in Machado et al. (2017) (018)) defines options using value functions (Mahadevan] 2005), which captures global features of the state space. In more theoretical directions, Fruit & Lazaric (2017); Brunskill & Li (2014) provide regret and sample complexity bounds, respectively, for learning with options. Additionally, Mann & Mannor (2014) demonstrate that options improve the convergence rate of upproximate value iteration.
More recent empirical work has considered the problem of hierarchy learning beyond the options framework in wide variety of settings. Nachum et al. (2019a); Levy et al. (2018) provide algo- rithms for learning hierarchies based on goal-conditioned policies, reducing the learning problem to choosing subgoals. Nachum et al. (2018) considers more general case when learned representa- tions are used to map states to goals. Other works such as Co-Reyes et al. (2018); Eysenbach et al.) 2018 Sharma al. (2019) provide intrinsic objectives for learning hierarchies without rewards.
Closely related is the work of Wen et al. (2020), which introduces similar latent structure on the state space, and provides sufficient conditions ensuring sample-efficien and tractable hierarchy- based learning. However, their works hinges on prior knowledge of the latent structure, while a major focus of our work discovering the structure itself from interactions.
Several heuristics have been proposed in prior work for the detection of useful bottlenecks in MDPs (McGovem & Barto| 2000: Menache et al.) [202]] [Sinçek & Barto 2004 (Simyk et al.] (005). In particular, Şimşck & Barto (2004) define the notion of access states, states which maximize short- term novelty future states. Although exits as defined in Definition 3.1 meet this heuristic, we note that cluster interiors may also contain bottlenecks also meet these conditions. In contrast, our algorithm would not detect these bottlenecks; however, this behavior is desirable as such bottlenecks are unimportant for meta-learning.
7 CONCLUSION
We have demonstrated that certain natural coverage conditions allow for learning useful hierarchies from tasks. Interesting future directions include analyzing hicrarchy-based multi-task RL and ex- tending the ideas in this work to continuous state and/or action spaces. Another interesting direction would be to provide sample-efficient algorithms for learning additional structures that can be im- posed on the learned hierarchy, such as cluster equivalences in Wen et al. (2020).
"We use O-suboptimal hierarchy oracle for the separation result for ease of presentation.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning. In International conference on machine learning, pp. 316-324. PMLR, 2014.
John Co-Reyes, YuXuan Liu, Abhishek Gupta, Benjamin Eysenbach, Pieter Abbeel, and Sergey Levine. Self-consistent trajectory autoencoder: Hierarchical reinforcement learning with trajec- tory embeddings. In International Conference on Machine Learning, pp. 1009-1018. PMLR, 2018.
Thomas G Dietterich et al. The maxq method for hierarchical reinforcement learning. JCML, volume 98, pp. 118-126. Citeseer, 1998.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 778-598. PMLR, 2021.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.088 094444,,999444. 2020.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580-588) 2021.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. International Conference on Learning Representa- tions, 2018.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. The information geometry of unsupervised reinforcement learning. arXiv preprint arXiv:2110.02719, 2021.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In International Conference on Learning Representations, 2018.
Ronan Fruit and Alessandro Lazaric. Exploration-exploitii in mdps with options. In Artificial Intelligence and Statistics, pp. 576-584. PMLR, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879. PMLR, 2020.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In International Conference Learning Representations, 2018.
Marlos C Machado, Mare Bellemare, and Michael Bowling. laplacian framework for op- tion discovery in reinforcement learning. In International Conference on Machine Learning, pp- 2295-2304. PMIR, 2017.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Representations, 2018.
Sridhar Mahadevan. Proto-value functions: of the 22nd international conference on Machine learning, pp. 553-560, 2005.
Developmental reinforcement learning. In Proceedings
Timothy Mann and Shie Mannor. Scaling up approximate value iteration with options: Better poli- cies with fewer iterations. In International conference on machine learning, pp. 127-135. PMLR, 2014.
Timothy Mann, Daniel Mankowitz, and Shie Mannor. rege-regulrrized interrupting options (trio). In International Conference on Machine Learning, pp. 1350-1358. PMLR, 2014.
10

---

Under review as a conference paper at ICLR 2022
Amy McGovem and Andrew G Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In Proceedings of the Eighteenth International Conference on Machine Learning. pp. 361-368, 2001.
Ishai Menache, Shie Mannor, and Nahum Shimkin. Q-cut dynami discovery of sub-goals in reinforcement learning. In European Conference on Machine Learning, pp. 295-306. Springer, 2002.
Nachum, S Gu, H Lee, and S Levine. Data-efficient hierarchical reinforcement learning. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), pp. 3303-3313, Curran Associates, Inc., 2019a.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierarchical reinforcement learning. In International Conference on Learning Representa- tions, 2018.
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 1rX9v:1909.110 10618, 2019b.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. Advances in neural information processing systems, pp. 1043-1049, 1998.
Julian Schrittwesser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604-669 2020.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-awan unsupervised discovery of skills. In International Conference on Learning Representations, 2019.
Özgür Şimşek and Andrew G Barto. Using relative novelty to identify useful temporal abstractions in reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 95, 2004.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. Proceedings of the 22nd international conference on Machine learning, pp. 816-822 823, 2005.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 33, 2020.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference Machine Learning, pp. 3540- PMLR, 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki,, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft i using multi-agent reinforeement learning, Nature, 575(7782):350-334 2019.
Jane X Wang, Michael King, Nicolas Porcel, Zeb Kurth-Nelson, Tina Zhu, Charlie Deck, Peter Choy, Mary Cassin, Malcolm Reynolds, Francis Song, et al. Alchemy: A structured task distri- bution for meta-reiinforemment learning. arXiv preprint arXiv:2102.0220 2021.
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, 2020.
11

---

Under review as a conference paper at ICLR 2022
Andrea Zanette and Emma Brunskill. Tighter problem-dependen regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
A META-TRAINING PROOFS
A.1 ALGORITHM
In this section, we provide the complete algorithm for exit detection with optimistic imagination. For readabiliiy, we separate the three phases.
A.1.1 PHASE I: TASK-SPECIFIC LEARNING
Algorithm Exit Detection, Phase Task-Specific Learning
Require: Tasks MI,.... Mr, NUCEVI UCBVI iterations, Nrs policy samples, threshold NTS 1: for all E [7] do
thresh
2: D' <- Ø.
3: Obtain policy set of UCBVI(M,, NNCCBVI..
4: for all n 1,..., Nrs do
5: Sample π Unif ($*).
6: Play π in Mr, add all (s, a, s') pairs to D', get Form estimated dynamics model P. from Dr-
get sum of rewards (7(x).
7:
Nrs
8: Form optimal value estimate V/ + NTs n=l
((n)
9: Ne(s,a) a) + [(,, u, x') E D; x = 8, = azf-
for all (8, a) E S A do if (s, a)
NTS
threshh then P. s. +
12:
return dynamics estimates P. and value estimates V; for i E (T].
A.1.2 PHASE II: LEARNING REFERENCE DYNAMICS
Algorithm Exit Detection, Phase II: Learning Reference Dynamics
Require: MDP M, N
EULER Euler iterations, NRF policy samples Set policy class V +- and dataset DRr +- Ø
2: for all S do
3: Create MDP M, from M with horizon 2H and P(o g, for any
4: (3,3, a) + 1 g] for any (s, (S)( A.
5: Φ9 +- EULER(M, g. Tg. NELLER
6:
( g) + Unil (A) for x E $9, [H].
7:
Add policies in 4 to L.
8:
for all n ,,...,,.Eee. do
9:
Sample π ~ Unif (V)
Play π in A and obtain trajectory (So, ag..... $2H)
11: Sample h ~ Unif ([2H]) and add (sh, ah. sh+1) to DRF.
return reference dynamics Po formed from DRF.
13

---

Under review as a conference paper at ICLR 2022
A.1.3 PHASE III: EXIT DETECTION
Algorithm Exit Detection, Phase III: Exit Detection
Require: NED, thresh> "BULER NEL policy samples
.ED NEL
1: Initialize ISEXIT a] & FALSE for (s,a) E S x A.
2: while True do
3: for all t [T] do
4: Po(. s, + P. 8, for (s, ES x A with ISEXIT[s, a].
5: V V',Q" - OPTIMGVI(PP (Pi,..., Pr), re, ISEXIT)
6:
if (o V/2 (2/3)ç then
7:
Run greedy policy with respect to Q NED times and form estimate P for (s, a) pairs visited least N Whhrash times.
8:
for all (s.a)
A with PP- s, a) & do
9:
if (3I E [T') (- 8, a) # and P(-|s,ay Pel. s,
a)) l 8/2 then
ISEXIT[s, a) True .-( 8, a) + LEARN-EXIT(MM, (8, a),
NEL
BULER NEL. for all E (7)
12:
if no new exits found after passing through T tasks since last found exit then return ISEXIT
Algorithm 4 Borrowing Optimistically Across Tasks during Value Iteration (BOAT-VI)
procedure BOAT- VI(Reference dynamics Po. Estimated dynamics (P1...., .r).. Reward function Table IsExIT[S AA)
1:
2:
(s) 0 for S.
3:
for all = 1, do
4:
for all (s. E S A do ISEXIT(ss, then
5:
6:
(s) + r(s,a) + Po
7:
else
8:
(n(sa)) - r(s + max PeVn+i(s,a)
9:
VA (5) + max, (s, a) f
10: return V.
Algorithm Exit-learning subroutine
EULER EULER iterations, NEL policy samples) 2: Create MDP M from M (ee s,a) 1.
1: procedure LEARN-EXIT(MID M, exit (s, a), NEL
3: P(s',a') t 1 [(s', a') (s, a)] for any (s',a') (Su A.
4: V <- EULER(MM NV EL
EULER
5:
for all n = 1, 1....... ,N.. do
6:
Sample π Unif (V).
7: Play π in M and obtain trajectory (Sp, Qu...., $H)
return reference dynamics TP(, s, a) formed from all trajectory data. 8:
14

---

Under review as a conference paper at ICLR 2022
A.2 OTHER ASSUMPTIONS AND RELEVANT DEFINITIONS
The remaining assumptions quantify the reachability of certain states. First, we have the following assumption, which in effect ensures that one reach most states regardless of exit configuration in the meta-training tasks:
Assumption A.1 (Non-limiting exit configurations). Let M (S,A, be any reward-free environment with time-varying dynamics
(- |s,a) Pith.s.a(- s,a) for some t: [H] x XSx [T..
Then, there exists C >> such that for any and & [T].
max PM E Tx) C'ax PM,
Intuitively, the assumption states that the reachability of state in Mr would not be significantly improved even under an optimal configuration of the exits. Therefore, running reward-free RL on one of the veta-training tasks is sufficient for learning all non-exit (s,a) a) pairs.
Remark A.1. We note that Assumption A. is restrictive that it requires that every state be roughly reachable in any of the meta-training MDPs. This may not hold in practice, e.g., consider four-room environment where one of the rooms is blocked off for one of the tasks. However, this can be weakened requiring that s be reachable in at least tasks. This would require that the algorithm run Phase II over N meta-training tasks, which results in a benign increase the query complexity of the algorithm, so long as N constant much smaller than T'. We focus on the N = I case for ease of presentation.
of N arbitrarily chosen meta-training
To simplify the presentation of the rest of the assumptions, recall the following definition of 6-significance in Jin et al. (2020):
Definition A.1. A state is d-significant if max, P(s E Tx) 2 6. Additionally, say that (s,a) is 5-significant if 8 is ö-significant.
Note that we have modified the definition to remove the dependence on the timestep h E [H]. This is because the dynamics are stationary, and thus it does not matter when is visited in trajectory.
Note that Assumption A.1 implies that reachable entrance in task is reachable in all tasks (i.e., is significant in the sense of Definition A.I) Therefore, we can quantify the minimum level of significance []
Definition A.2 (p-significant entrances). For any E Ent(S), 8 is p-significant for any task.
Finally, we want to quantify the reachability of every exit from any entrance in the same cluster, assuming that it is indeed reachable:
Definition A.3 (In-cluster exit reachability). Fix any cluster Z, entry E Ent(Z), and exit (g. a) E Ext(Z). Consider the reward-free environment Melz = A, H), where Pe|2 the restriction of P, Z x A and the starting state is Then, if g has nonzero significance in Melz for any E (T), then it is eg-significant.
The requirement that the assumption hold for any / E (T) is without loss of generality since non-exit dynamics do not change.
A.3 VERIFYING EXIT DETECTION
In this section, demonstrate that the algorithm in Section A.1 can successfully discover Ext(S) with high probability. Formally, we have the following result: the algorithm in Section A. with the pa-
Theorem A.1 (Provable exit detection). Assume rameter choices given in Table 7 Then, with probability at least 1 - p. the algorithm returns an array ISEXIT satisfying:
((x,a) ISEXIT [s, a]} = Ex)(S).
To prove this result, we proceed with phase-by- by-phse analysis of the algorithm in Section A.I which we then compile into proof of the desired result.
*One weaken this assumption in way that is compatible with the weakened form of Assumption A.1
15

---

Under review as a conference paper at ICLR 2022
Parameter
Value
H²SA
HSAT
NUCBVI
log²
min(a.ç)2
p
11
SAHT
NTS thresh
S max
log
32
po po.min(3.)
H
H
SAHT
H
SAT
Nrs
S max
log
log
a(2" a.
pa mommin (3,5)
min(a, C)²
HSA p
NRF EULER
minnppmin(e,,)).// log
5² min(,min(s,s0)) E,) (2/C)
A
NRF
log
S
SAH
NED thresh
log
B
pCB
HKS
SAH
H²K²
K
NED
log
log
CB2
PCB
5²
H
CSAHT
ELL thresh
L max
log
( /3
pa min(3.
C A
HSAT
NEL EULER
log
P
CH CH
CSAHT
C² a²
SAT
NEL
L Lmxx
log
+
log
a² a,32
pa min(3, (3,C)
p
Table 1: Table of parameters for the results in Theorem A.1 does not need to know K L in advance, at the expense of a worse sample complexity bound.
Since K < SA and L S S, the agent
A.3.1 PHASE ANALYSIS
First, we prove that during Phase I, [ sufffccinnty visits relevant exits and that all value estimates are sufficiently close. Formally, have the following result:
Proposition A.1. Set
H1 1 2 32
SAHTNTS
TTS thresh
max
log
p
and consider the following procedure applied to one of the meta-training tasks Me:
1. UCBVI run for
H²SA H.SA
NUCBVI =
log
min(a, 2)
p
iterations, generating policies π (0)
(1)
Nueavi
16

---

Under review as a conference paper at ICLR 2022
2. The learner uniformly samples
H NTS thresh
H²
TK p
NTS Ω
log
min(a, a; Ç)2
policies from the previous step, runs each policy in Mr, and obtains a dataset of transitions D. and returns V(1), ,.... V(
Then, with probability at least 1 p/3T,
(a) We have the regret bound
NucEVI
(0)
S
Vū V (so)
Voah
(s0)
NUCBVI
6
k=
(b) The of obtained returns satisfy
NTs
NUCAVI (0)
V
Vo
(so)
NTS
(c) (f, a) is a-important for Mr then Ne(s, a) 2 Nthresh-
(d) For every (s, a) pair such that Ne(8, a) 2 Nehressh
[ P (s, (s, < min
C 8H 24H 2
sup [08-(0.H]
To prove the above result, we first recall the following regret bound on UCBVI, as proven by Azar et al. (017):
Lemma A.1 (UCBVI regret bound). For sufficiently large N, with probability at least 1 - -p/6.
1 N
H2SA
HSAN
(50)
(so)
log
N
p
As will later on, with choice of NUCBVI, obtain the desired regret bound in (a). Additionally, by Hoeffding's inequality, the average of NTs returns concentrates around the desired quantity with high probability, proving (b). Thus, all that remains is ensuring that every a-impprtant exit is sufficiently visited, and thus their dynamics are sufficiently well-estimated.
Recall from the main text that the key step is demonstrating that near-optimal policy for task must visit its a-important states with non negligiie probability:
Lemma A.2. Let (8, a) be a-important for M, and let æ be an e-suboptimal policy for < a. Then,
P((),a))TT)> 1 (a s).
H
Proof. By a-importance,
a 5 (Mo)((s)) vo vinnn (o)o),)(())) (so) 5 - (oM.((s)) -VM
+ (s0) vo vyllow (5o)
< (v.M..(ss)) - vililnns) (5o) +
Therefore, by applying Lemma A.17 and noting that (A O 7 Ø3 ((s,a) Tx), we obtain the desired result.
Through the prior result, we can relate the UCBVI regret bound to the probability that randomly chosen UCB VI-generated policy visits a-important state:
17

---

Under review as a conference paper at ICLR 2022
Lemma A.3. Let (s, be a-important for M. Assume that UCBVI,
when run for
H²SA
HSA
NUCRVI = =Q
log"
a²
P
iterations, generates policies :I...., WN. If we sample a uniformly from these policies and let be the (random) trajectory generated by this randomly selected policy, then
P((s,a) a) ET) 2H
a
conditioned on the high probability event Lemma A.1
Proof. By Lemma A.2 for any fixed π, we can write
1 (a (s)) Vo" (so)])+,
P((s,a) ET) H
where 24 = x1 [ > O). Then, since x is chosen randomly from the policies generated by UCBVI,
1
1
P((s,a) E)) P((s,a) Tx
(a (V) ViD (so)))+
HN
a Vo (5p) - v (sp)
H
Therefore, by applying the regret bound in Lemma A.I and the choice of N, find that
P((s, a) ET) 2H
With all of the above intermediate results, we can now prove Proposition A.1
Proof of Proposition A.I.
Throughout this proof, we condition on the high-probability event in instantiated to occur with probability at least p/ //2.
Lemma A.I
(a) By the choice of NUCAVI.
H2SA HHAT C2
NUCBVI 2
log²
P
and thus, obtain the desired bound by plugging this value into the regret bound provided by Lemma A.I
(b) Note that (V() are ii.d., bounded in [0, H], and for any i E [Nis].
N
E
v
VoTh (so).
N
k=
Therefore, by applying Hoeffding's inequality, with probability least p/ 1/,
NTs
NucavI
112 T
log (so) E Nrs
NTS
NUCBVI
The result immediately follows from the fact that Nrs 2 (H² /(2) log(()))
(c) The result simply follows from Lemma A.16 instantiated with failure probability 1 p/ 12T, together with the choice of thresh
(d) With the choice of NUCEVI, the conclusion of Lemma A.1 can be made to hold with proba- bilityy at least 1 p/24T. Fix a-important exit (s, a) for Me. so that the probability that (s, a) is visited by the procedure is at least ar 0H/2H. By Lemma A. sampling NTs trajec- tories is sufficient to ensure that (1 a) 2 NTS thresh with probability at least pp247 K. Therefore, by performing union bound over the set of a-important exits (which contains TS
at most K elements), Ny(s, a) 2 thresh for any a-imppotant exit with probability least 1- p/247. Thus, overall, this event occurs with probability least 1 - p/12T.
Since each part fails with probability at most p/ 12T, the overall failure probability is at most p/3T, the desired result.
18

---

Under review as a conference paper at ICLR 2022
A.3.2 PHASE II ANALYSIS
In this section, provide guarantees on the dataset DRF obtained by performing reward-free RL in A Formally, we have the following high-probability result:
Proposition A.2. For any > and failure probability p. if Algorithm is run with parameters
H2S
HSA
NRP EULER
=
log
P
C
A A Alog
NRF O
max
(
pm))
S
Then, with probability at least 1 - p/3:
(a) The distribution μ generating each sample in DRF satisfies
P((s,a) ETx) ((s,a)
8 E S is ö-significant in M1(2H)
max a.
S 4SAH.
(b) The estimated dynamics model Po satisfies
[ (s, (s.
la v(s)]
max max ((aa)~ f:8 [ V-S+A
5²
pmin(E,Eo))
1
< min
4 14
16
HASA
The details of the proof of Proposition A.2 follow that of Jin et al. (2020) which we provide here for completeness. First, we adapt the regret bound from Zanette Brunskill (2019) for any MDP and reward function used in Algorithm
Lemma A.4. For any g E S, running EULER in My N iterations returns N policies . NN satisfying the regret bound
N
SA SAHN AH' SAHN
Vi (80) - N
Σ
Vo
(80)
S V
(s)
log +
N log
N
with probability at least
Proof. Observe that
H-1
Ere
Σ r(sh, an)
100t (s0)
90
NH
2
r(sh, and
+ (VoT* (so))2
80
NH
k=1
H-1
2
E
r(sh an) + (so)
50
NH
(so).
H
Therefore, by applying the regret bounds from Zanette & Brunskill (0019), we obtain the regret bound
1
SA N log
SAHN
8 A H
SAHN
(80)
v (50) S
(50)
4V%
log
N
p
N
p
with probability at least p.
19

---

Under review as a conference paper at ICLR 2022
With the regret bound above, now proceed to prove Proposition A.2
Proof of Proposition A.2 (a) Fix d-significant 9 S. Note that for Tg. ( P(g Tx for any policy Therefore, via the regret bound from Lemma A.4 and the choice of NRF EULER obtain
RRF
1
max P(g E Ta)
P(get))
max P(g E Tx))
NRF EULER
max P(g E TT)
Σ EM)
BULER
RF
m
with probability at least - p/25. Now, since x((1g)
~ Unif (A), we have that for any a,
2A
max
ET) ET)
P((g,a))TT)
N-ELERR
RF
NE
Finally, by applying the same argument above across all 8-significant E S, we have that for any (g. a).
max (((g. ET) -
max (((g.)) E 2SA Σ
P((g,a) E Tx)
SI ER RF
0,
gES
TEW
with probability at least - p/2. To complete the proof of (a), observe that
P((+,a) E Ta)
Σ
P((G,a) E S ((s max
< <SAAH,
SAEEEERR
2H
M(s.a)
NEW
since conditioned on ag E Tg. the probability that (g, a) is sampled is at least 1/2H.
(b) The result follows by following the same proof of Lemma C.2 in Jin et al. (020), with failure probability p/2. Note that the dynamics are stationary, and thus we do not need to perform a union bound over the time step h [H].
A.3.3 PHASE III ANALYSIS
Having analyzed the previous two phases, we now show that Algorithm Susiithhmmuuuussfflly finds all exits during Phase III. As part of this, we prove the following guarantee:
Proposition A.3. Assume that Algorithm 3 is Line having just arrived this step for the first time, or after finding a new exit. Let E [ss a) [sEXIT[s a]}. We assume:
(a) C Ext(S).
(b) The higb--robabillity events in Proposition A.1 (for any E [T] and Proposition A.2 (for
8 < (/2AC11SS) both hold, providing estimators Po. PI,...,,PP
(c) For every (s,a) E E and E [T', we have access to estimator Pe(. s, a) for l,(.) satisfying
[ - (s, (s, & min
3H
max [.8-+
24H
2
Then, if =F)((S) the algorithm terminates after passing through tasks. Otherwise, if +
Ext(S), the following events hold simultaneously with probability at least p/3K:
(a) For one of the next T tasks that the algorithm inspects, there exists at least one t E [T] such that
V > 5.
20

---

Under review as a conference paper at ICLR 2022
(b) For the task in (a), running Lines] 11 finds least one (s.a) E Exx((S) \ E (and only
(s, a) pairs in this set), and learns an estimator Pel- 8, a, for Pe(: 8, a, satisfying
[ (s. S min
C 3H
max S (..
24H 2
To prove the above result, will consider the following special set of MDPs: Definition A.4 (Imaginable MDPs). Fix task M₁. Furthermore, let E S Ext(S). For any function I: S A H] + {O....,T}; T.). we can construct an associated MDP .M (S,A, Fr, H) via
P (- s, a) = Pz(s.a,h)() a).
We define the set of imaginable MDPs be the set M, be the set of MDPs generated by any I satisfying
[t} a)) E [ ( {Kl (s, 2 Neturssh
{
(s,a) E E otherwise
Informally, (.( is the set of obtainable MDPs by borrowing dynamics for (s, a) pairs that are not known to be exits. This set is particular interest in our analysis, since BOAT-VI performs a maximization over the MDPs in this set:
Lemma A.S (Optimism). Assume the preconditions of Proposition A.3 Over the course of running Algorithm 4 the algorithm implicitly defines index function I S A [H] t0,...,77 T). This
function I satisfies Mz E Mr, (E), and Mz is a maximizer of
max max M.M. (so). (E)
Proof. To see that My E (E),), note that if (s, E E, then (s, = for any h E [M]] Otherwise, note that although the maximum is over all indices, Pa(s' 8,a) = 0 for any 8 if Ne(s, a) N Therefore, since the estimated value function is always positive, the maximum effectively only over any & with (N a) 2 0. Thus, My E M,(E).
Now, we prove that My = . is maximizer of the estimated value function, which we prove by induction. Let I' be another index function satisfying M' = =Mr E M,(E). Clearly, V.M.* (s) < и > (s). Then, for any h E [H] and (s,a).
M.* (s, = r(s, a) + PI(s,a,t)
D.Mii 2 rs, a) + Pr Vi4 (8, r(8,a) Procea, "ifi""s,0
MM *(s,a).
where the first inequality follows from the definition of I, and the second follows from the inductive hypothesis. Therefore, for any 8,
V. M. (s) = max Q (M. a) 2 max Q M', (s,
- M (s)
Thus, by induction, M. (so) M (sa)) Since the argument applies for any I', we have shown
the desired optimality result.
Note that M is contained (E) via our assumed preconditions, suggesting that the BOAT- VI should find an MDP with sufficiently over-optimistic value. However, the maximization above makes use estimated dynamics, and thus we need to prove that every MDP M, (E) is sufficiently well-estimated. We now show that the preconditions of Proposition A.3 To this end, we recall the performance difference lemma:
are sufficient for estimation.
Lemma A.6 (Performance Difference). Fix two MDPs M AS, and M' (S, A, P', H). Then, for any policy n.
HH-1 Σ 4=0
".M''"(ss) - V.M.a (sv) ) = E,M
[P,, P.) Pa) 80
21

---

Under review as a conference paper at ICLR 2022
We now present the estimation result:
Lemma A.7. For any x and t E (T), let (so) be the value of a policy a in M E (,E)), and T (8o) estimate using available quanfities from the preconditions of Proposition A.3 Then,
5
V. (80) - Vo (50)
sup 1 (E)
sup
Proof. Fix att [T), M E (E) and policy n, with associated index function I. Lemma A.6 implies that
H-1
1/0 (oM..(Bo) - -Vo..((su)
5
EM
[[((CC)) / (sn, an)l
hm0
#-1
[(B(h) -p(M))-p()) p(tt) a) (s,
h= (a.a)
We now define the following sets:
Us {(s a) is 6-insignificant for Mi}
B₁ = {(s, a) [s a) + 0} \ (EUUs)
R, {(s a) (s, = 03 Ug.
Note that Rd is estimated via reference dynamics from Phase II, while B₁ is estimated using task- specific dynamics from Phase I. Then, for fixed h, we can decompose the inner sum above as
Σ (s,a)
[10hh) - pp(h)) Vitta] ) as
Σ
[((CN] - -p(i)) - / (s) p. (s,a)
(x,O)E
=(0
(((()-P()) ((h)) Vi+ (s) pr
(s
=10
- -p(t) ) (s, a) (s
-1II
((P(C)) - pp()))
((M7)_p(())Ce / (s,
(s, a) PMMi"(s,
(s.a)Et's
(IV)
Note the inequality since E n Us is not necessarily disjoint. We now bound the four terms above separately.
Bounding (I): Dynamics Error from Known Exits. We first bound (I), which we note derives from errors in estimating the dynamics of known exits. Recall that by precondition (c) in Proposition A.3
[ - [(P)-P.)]] (s, a) s S
sup [:
21H
Therefore,
(I) =
Σ
[[(P(()) - p( (s, a) (s,
(s
Σ
[ 10h-PPpp -P.-P- (s, ph (.M. S 24H
Σ (MM.T(ss))
(s,a)EB
(s,))E
<
24H
22

---

Under review as a conference paper at ICLR 2022
Bounding (II): Reference Dynamics Error. Note that within RA, PA Po. which estimate via Fo- Therefore, we bound the error resulting from using DRF to estimate Po. This part of the proof follows that of Jin et al. (020)) First, by Cauchy-Schwarz,
(II = Σ
[ - p(())) (s) (s,
(s Ba
E (s.a)ERa
[Pu (PPu-Po)Via (s. P)M.
=
1/2
Σ
[ PP) Po) h+1 (s, (s,a) " (pMit(ssa))
(s.0)ER
Observe that V 4+1
only depends on x through timesteps h + I,..., H - 1. Therefore,
Σ RR
[ Po) (s.
[ - (s,
Po) -Poo (s, 2 (s) (u(s) = a].
max v v-S-A
By applying Assumption A.I
P.M. (s) S (M (s E T>) S max Pm (s Tx) S Cmax p.n PM
h
max (M2 Tπ)) S 4CHSAp(ssa);
where we have applied Assumption 4.1 to move from M to Mi. Substituting into the earlier expression,
Σ
|[(oo-Po) Po) (s,a) ? (M)( [v(s) aa
max V
[ - Po) (s.a) 2
4CHSA max vsS
Σ
[a (()=v())
(x,))En,
Po) h+1 -PP (s) 2
S 4CHSA max
Σ
aa = v(s)) u(s,a)
USS
8,a
[[((o-Pa)ViT)) Io) Vhtt (s, a) 2 1 la u(s)]
4CHSA max E (s)a)) SSA
Thus, by applying the bound on the right-hand side provided by Proposition A.2
Σ [[000]] -
) (s, a) PM (s,a) S 24H
(II
(R.0)ERA
Bounding (III): Error from Task-Specific Dynamics. Recall that on B₁, Pn = Pp for some k + O. Thus, (III) is the error resulting from dynamics estimation in Algorithm [ By following the same argument as that used to bound (I) and applying Proposition A. we find that
Σ BB
(s, (s, M.M. (8. S 24H
S
Bounding (IV): Error from d-Insignificance. The remaining set (x, a) pairs are those such that is 5-insignificant in M₁. Note that
(IV)
Σ (e,a)EUss
(Pp()) - -P()) (s, p)M. < H Σ
PMM.T (s. a)
(s.a)eUs
H Σ pyM. (sM.
aEUs
23

---

Under review as a conference paper at ICLR 2022
As result,
PM. (s) & TT) max PM Tx) I Cmax p.i Tx)
S6..
By setting 8 = S/2ACC when performing reward-free RL in Phase II, we thus find that
Σ
[[((0)) p(() ( (s, a) Pr (s. S
S
24H
(s.a)EUs
Concluding, By combining the bounds on (I) through (IV) and summing across h = O,...,H. H -1, find that
Vi M.n. (8o) Vo (oM.7(so)) - <
6
Note that this argument simultaneously applies to any such M; therefore, the desired conclusion follows.
The prior estimation result, together with Assumption 4.1 suggests that BOAT-VI should find an MDP that sufficiently overestimates the value of the task so long not all exits have been found. This ensures that the exit-finding routine triggered. Formally,
Lemma A.8. Assume the preconditions of Proposition A.3 and that E. * Ext(S). Additionally, let t [T] be the task with (-overoptimistic value when borrowing exits Ext(S) \ E. Finally, let V be the value function returned by Algorithm F on Mr. Then,
(80) V. 3
Proof. Throughout this proof, omit the timestep 0 and the initial state so for brevity. Define M and n² to be the maximizers of
mAX max V.M..
MEM, (E)
a
Furthermore, let M be the imagined MDP guaranteed by Assumption 4.1 on top of Mr, such that V.M- VMu** Ç. Then, we have that
M.M.F VM.. (DM,5 ) + (V VM'
>-666
+ (VM""=" 5 - V.M.e. + (V-,, |MMr
20
>
5
C
6
Furthermore,
Neeavi
Neeavi
MM - 1/-
V.Me.
1.
NUCBVI
NUCBVI
20
C/6
where first follows from optimality, while the second follows from Proposition A.2 putting the two inequalities together.
Thus,
Ve V1 3
While the prior algorithm ensures that at least of the tasks will trigger the exit condition, the actual task that triggers the condition may not the same one invoked in the proof above. Never- theless, prove that the trigger condition ensures that the algorithm will find new exit.
24

---

Under review as a conference paper at ICLR 2022
Lemma A9, Assume the preconditions of Proposition A.3 and that E o Ext(S). Lett E [T] be task such that the value estimate V returned by Algorithm 4 satisfies (8)) - V, (2/3) and let be the optimal policy for V. Then, there exists (s, a) Ext(S) \ such that for some t' + t,
(a) (s, a) 2 N thresh and Pt(:) (,,a),a))))))))) + PP(( s.
(b) pM. ((s, TT)) C/6KH.
Proof. Let M be the implicit MDP defined by Algorithm in the process of computing V We will prove value gap between M and Mr which implies that must visit state-action pairs with imagined dynamics.
Note that
Vi V., VoM."(so)) (sp) - V.Mei = (MMi -Vo((s))
+ (s0) Vi
2-c/0
2(2/3)6
Nucavi
1
Vo Me (1)
1/
(so)
NUCBVI
2-5/6
NUCBVI
Vo
(1)
(so)
VoMait (so)
NUCBVI
2-C/6
where the first inequality comes from Lemma A.7 and the last two inequalities come from Proposi-
tion A.l Thus, V.M.x (5o) Vo M., (ss) 2 C/6.
We now leverage this value gap to show that must use some exit (s,a) whose dynamics
in M have been modified from Mr with some probability. Formally, define the set A = {(s, a, h) P # (M s, aa) ]. By construction, A S Ext(S) x [H), and for any (s, a, h) thresh and (- s, a)
PMM s,a). Furthermore, A must be non-empty, as otherwise, P.- = PM for all h. and thus V.M.a (so) s Vo Mi, (so). a contra- diction. Therefore, by applying Lemma A.17 we find that
A, there exists 1' such that (e a)
S Sxp' PoM (Ta 0 + 6H
Σ
pM (M) E
((saa (3..)))E))
which implics the desired result, as {(s, a) (s, a, h)) E A} has at most K elements.
Because of Lemma A.9 we simply need run enough times and threshold the number of sam- ples needed to reliably determine which (s, pairs have an ( change in TV distance between tasks.
Lemma A.10. We work in the setting of Lemmal A.9 Ser
( S 32
SAHNED
[KK
H²K² K C
) p
ED thresh
log
and NED S
NED
thresh
log
p
Then, if we execute π within M, NED and let ((s, a) be the number of times that (s, a) is played in this process, then with probability least p/6K, the following hold:
(a) For the (8, a) pair and task E' in Lemma A.9 (ss,a) 2 thresh and
IP(
ac-1s.a-PPrr ss
TV 2
(b) For any (s & Ext(S) with N(s,a) 2 Muresh and t' with No a) 20.
NED
| (, - 8, s, TV < 3
2
25

---

Under review as a conference paper at ICLR 2022
Proof. By the choice of NED and the lower bound P. ((s, a) E Tx) </6K from Lemma
A.9 we guarantee that N(s, a) 2 NED thresh with probability at least 1 - p/12K. Furthermore, due N (s, a) 2 NED thresh+ with probability at least p/12K, we have that for any (s, a) with thresh"
to the choice of NED
|PC (,.ls.a) - Pol- (,
8 TV 4
by applying Lemma A.lma.A.16 We condition these two events simultancously for the rest of the proof, which occurs with probability at least p/6K.
We now prove each part separately. For brevity, omit (s, a) wherever it is understood.
(a) By applying the triangle inequality,
P. - Frllyy < Pr
PP TV
1 Pr TV + || P.r
TV |
Pv
TV
Therefore, by lower bounding the left-hand side using 3-dynamics separation in Definition we find that
PP (s,a) Prr( s0
ITV
8
TV 2
(b) The triangle inequality implies that
P
Pr.
P
+ PP Pv Pyllry+
Pr Pr
11 TV
S 8
TV
TV
2
29/4
S3/4
where the bound on the first term provided by Proposition A.I
The prior result demonstrates that if the exit-finding condition is detected at any point by the al- gorithm, then the algorithm finds a previously undiscovered exit in Ext(S). At this point, all that remains is to ensure that the algorithm sufficiently learns the dynamics of the newly-found exit in all of the meta-training tasks.
Lemma A.11. Fix an (s, a) Ext(S), which was found via exit detection, and let
NEL thresh
{ m.x
Ω
(5²²) 32
11ah 1
log
SAHN T
2
p
Assume the exit-learning subroutine with
EL BULER
ACSAHH
log
(
(SHHT) and NEL. =0
CH
NEL
EL thresh
C2 a²
log
SAT p
in each of the tasks. Then, with probability at least 1 - pp/6K,
[[ PP.s]] (8, [ f:S [0.m
S 3H 24H 2
max
S min
for every E [T].
Proof. Fix a task E [T]. Note that Assumption 4.1 implies that (s, a) is (a/ -iignniiin for some task. Then, (s,a) must be Hee/CCH-sinnifffeee for all of the other tasks by Assumption A.
By applying Lemma A.4 the set of policies found by the exit-learning subroutine for every task
I E (T) satisfies
N VEL
max P P((s, a) T
Σ
P((s,a) E TTa)
VEL EULER
1=1
SA
SAHTNER
8 A11
SAHTNE EL
I max P((8,a)
log
log
N
EL EULER
EL EULER
P
26

---

Under review as a conference paper at ICLR 2022
with probability at least p/18TK. By setting
CS2 AH3
HSAT
NEL BULER
log"
p
we thus find that for any E [T].
max (ax
Σ
P((s,o))TTT)
2CH
VEL
EILLRR xEd.(s.a)
Note that the right-hand side is exactly the probability that the trajectory of randomly chosen policy in (s a) contains (s, a) in the trajectory. Therefore, by applying Lemma A.15
playing
CHHNNE
NEL thresh
C SAT a log
NEL =
P
sufficient guarantee that we obtain least NEL
thresh samples from P.(- s, a) with probability at
least 1 - p/18T K. Since (s, a) E Ext(S), (- 8, a) (and by extension, P,(- s, a,a)) is supported on Ent(S). Therefore, 1 p/ 18K we get the bound
modify the proof in Lemma A. so that with probability at least
[(P-- P.)s] (s,a) &
[ [[(e-- (1)P)))]] (8)
max 1
max J:Em($))((0.11
311
< min
24H 2
tthresh depending linearly on instead of Note that by performing a union-bound, all events occur with probability at least 1 7/ K. Performing a second union-bound over all of the available tasks results in the desired failure proba- bility.
with NEL
At this point, we have effecttiveyy proven the second half of our Phase III guarantee. All that remains to prove that if ((s, a) IsExIT(s: (s, a}} = ESt(S), then the algorithm terminates without triggering the exit-finding condition.
Lemma A.12. Assume that E = {(s,a) a) ISEXIT[s, a}} Ext(S). Then, under the preconditions of Proposition A.3 every task satisfies
2 ('(60) 1/ S c.
Proof. Fix a task E [T]. Once E Ext(S), then (E) ) = {Me), since the only (s, d)-dynamics that be substituted from other tasks are those of non-exits, which do change between tasks. Therefore, by Lemma A.5 v=*(s)) (TMM*(so). Finally, by applying Lemma A.7 we thus find that
('(()) V. (. (5o) v:M.((so) (s0) + [Vvo
[VoM:-(00 Vol
The desired result follows since the argument holds for any task
A.3.4 PROOF THFORFM
In this section, we compile the guarantees provided by each of the three phases into proof of Theorem A.1
Proof of Theorem A.7
We condition on the following high- bigh-probability events:
(a) Proposition
A.1
guarantees for all M, with t E [T].
(b) Proposition A.2
27

---

Under review as a conference paper at ICLR 2022
Via union-bound, this holds with probability at least 1 - (2/3)p.
To prove the theorem, we provide an induction-basse analysis of Phase III. In particular, we will show that while E' {(s, a) IsExIT[s, al} _ Ext(S), Phase III will add at least one state-action pair to E' that belongs to Ext(S) \ E.
Formally, let Fg denote the internal state of the algorithm after it has added & state-action pairs. Note that with = 0, {(s, a) IsExIT[s, a|} in F2 is empty. Thus, Fx satisfies the preconditions of Proposition A.3 which in turn implies that the algorithm adds new state-action pair in Ext(S) and sufficiently learns its dynamics for all tasks with probability at least - p/3K. In short, the internal state of the algorithm at time Fi also satisfies the preconditions of Proposition A.33 with probability at least 1 - p P/3. More generally, Proposition A.3 ensures that if F3 satisfies the preconditions of Proposition A.3 then so does Fs+1- Therefore, with probability least - p/3, FK satisfies the preconditions of Proposition A.3] which necessarily implies that {(s, a) IsEXIT's is, a]] = Ext(S)
in FK. and thus the algorithm exits as desired. By performing union bound, all this occurs with probability least 1 P.
A.4 PROVING THE META- TRAINING GUARANTEE
Having demonstrated that EXt(S) can be successfully recovered by interacting with the environ- ment, now show that the data can also be used to determine exit reachability and implement the hierarchy oracle.
We formally state our main result here:
Theorem A.2. Assume that Mr have latent hierarchy with respect to ([Zc) Ent(.). Ex)(.)), and assume that these tasks satisfy the (a, C)-covrrageee condition in Assumption (4.1] Furthermore, running the algorithm in Section (. with the parameters in Table I with probability at least - the collected data be used implement the following:
assume the additional assumptions in Section [A.2) Then, by
(a) An e-suboptimal hierarchy oracle.
(b) A function AvExt(s) EEt((S + P(Ex((8)) such that, given E Ent(Z.), returns Ext(Zz).
The algorithm achieves both of these with query complexity
S*A
S
δ
min mimmmmnnn min(e, (oninne,,)),//C
C/C)
min(pmin(s,o))/cC7)
SA
KS
K²
CKS2A
CKL
)
+ T
+ +
+
poly(H))
min(a: Ç)²
CB2
a
amax({,
A.4.1 IMPLEMENTING THE HIERARCHY ORACLE
We first show that implement the hierarchy oracle in this section. In particular, we have the following result:
Proposition A.4. Let M be the MDP corresponding to the index J,r, H) as described in Defi- nition 4.3 Then, given (x, f.r, H), can form the following estimator for Py:
()(f(s,))
(s,a) E EEx((S)
P 8, =
8(s)
8 == == or 0
PPo(. 8,a)
otherwise
where Po is the estimator obtained from Phase I1 in Section A.1 Assuming that the high-probability
event in Proposition A.2 holds for â S pe ps/2SH? value iteration using IP, returns policy such
that M.M. (x) V.M.* (x,,)()))) S..
Throughout the rest of this section, we fix the tuple (x, r, H) and the corresponding MDP M. Furthermore, we write Z for the cluster containing
28

---

Under review as a conference paper at ICLR 2022
To prove Proposition A.4 will show that M can be sufficiently simulated that the value of any policy can be reasonably estimated. Given this simulation result, we can then show that value iteration finds the desired policy. This simulation result depends on the following intermediate result, which provides insight as to why Phase II data is sufficient:
Lemma A.13. For any 8" E 2,
max pMi (x TH)] [max (M E ra)) S max P Tx))
Proof. First, we note that there exists an MDP such that (M E ) is the corresponding value function, In particular, modifying Mi (2FF so that any action from s leads to terminal state and defining r(s, a) = 1 [s s*] results in such an MDP.
Now, let ae and a be the policies achieving
max Www
(x Tx) and max (M Ta),
respectively. Consider the concatenation of Tu and T.. into history-dependent policy that runs T until the agent reaches 8, and switches to thereafter. This policy reaches with probability at least
max P ( Ez))
Ima PM E cn))
within the modified MDP described above. Since the optimal value among all policies is achieved by history-independent policy, obtain the desired inequality.
Informally, the prior result states that if x: is reachable within horizon H, then any state reachable from x within Z is also reachable in Mi within 2/ horizon. Therefore, performing reward- free RL with horizon 2/l during Phase Il provides coverage over all clusters. Now, we prove the simulation result.
Lemma A.14. Assume that the Phase Il guarantee in Proposition A.2 is instantiated for 5 S pe/4SH2. Then, if V is the value of a under M, and V is its corresponding estimate under F, then
(T)()) - (z) S
E
Proof.
The proof follows similarly to that of Lemma
A.7 By the performance difference lemma,
#-1
(v)
(s)
<
E.M.
(P)) Vitts (sh. an)
PF))
h=0
A
( -P)) Vin (s, (s.
k= (s,a)
Observe that if E 8 \ Z, (s, 0 for any Furthermore, since the dynamics within (Gs, er) are known, (fp V (s. 0 for s E {0s, @p). Therefore, we can restrict the sum to be over Z x A.
Now, let Zs denote the set of 6-significant (s, a) pairs Z from x, for some 8 be determined.
For fixed h E [H], we can decompose the inner sum as
El((B, -P,) Vitt1 (s, (s) PV ())
(s.a)
Σ [[(P,- - Vitta] (s, a) P (x) (e.a)
Σ
[[(P,-P/)
-
Vi+t1] (8, a)
PM (x, a).
(s.a)EZs
(1)
29

---

Under review as a conference paper at ICLR 2022
Bounding (II): Error from 6-Insignificance By the definition of é-significance,
(T) = Σ
[ PP Vhtta (s, a)
Ph (e, H
Σ (s) - HS8 - 4H
(s.0)EZs
2gZs
where the last inequality follows from setting 8/4SH²
Bounding (I): Reference Dynamics Error.
By the Sauchy-Schwar inequality,
(T)
Σ (x,a)EZz
[[(t; Ppy) Vhtza (s, (s,
Ph (s)
Σ [[(p)-Pp) Vitz (3,0) 2 Ph (s, (s
<
Then,
Σ
- -P)) -[() Vitt1 (s) 2 Pf (s)
(s,a)E2
Σ
[[(e,- ( Vitt (s, (s,a) (s) = =].
I max
viS+AA (s,a)E2,
Since is p-significant in M1 (2H)) by Definition A.2 Lemma A.13 together with 6-significance in M implies po of-significance in Mi (2H). Therefore,
1 max (2. (2m)) (x)
4HSA
(a) < max (M Tx)
u(8,a),
p
p
where the last inequality follows by part (a) of the Phase II guarantee in Proposition A.2 Substituting into the prior expression,
max v
Σ (8,0)E7
[[(P; - -Pr) Vitt1 (s,a) a)
(s) (u(s) = a]
4HSA
Σ
[[(B,- -Pp) V (s, a)) (u(s) = a) u(s.a) a)
max
P
VSS+A
(s
4HSA
[[[ - P.) Vitun (s, aa)) (M(s) aD
max
E (x
P
S
Thus by applying part (b) of the Phase II guarantee in Proposition A.2 we have that
4HSA
max E. (e [[[(e, - -P,) Vhtz (s, a) 1 [p(s) = al s 4H
(1) S
MSS S
Concluding.
By combining the bounds on (I) and (II), we obtain the desired result.
With this estimation result, we can now prove Proposition A.4
Proof of Proposition A.4 Let be the policy found by value iteration using TPy, which achieves the maximal value in the corresponding MDP. Then, by Lemma A.
Vi" (x) Vo (a)) <
(v)( Vo- (so)
Vir (8o)
Vi (ov)
(su) - vo (oo)
Se
S=/2
<0
Se/2
30

---

Under review as a conference paper at ICLR 2022
A.4.2 DETERMINING AVAILABLE EXITS
In this section, we prove that we can determine the set of available exits. We have the following formal result:
Proposition A.5. Assume access to the e-suboptimal hierarchy oracle from the previous section and that the guarantee in Theorem A.1 holds. Then, we can implement the function Av AvExt(s) Ent(S) + P(Ext(()) which, given E Ent(Z.), returns the subset of Ext(Za) that is reachable from s.
Proof. Fix an input Ent(S), which we assume belongs some cluster Zn. It suffices to demonstrate that we can implement 1 [e E Zx] for any fixed E Ent(S), Define
@s (r otherwise
(s.a)= =e
fa(s,
and va(8,a) a) = 1 a(),a)= e]. By Definition A.3] the MDP M corresponding to the tuple (Ir, for Te: H) has optimal value V c Ze A reachable from æi) Additionally, by Lemma A.14 (s) Vo (a:) e/2. We now proceed by cases. If Zu or e is not reachable from T, then (z) 0 for any policy and thus value iteration can only find policy with Vo (I:) eo/3. Otherwise, for E Zu, Vo én, and thus value iteration necessarily must find a with Vi (x) 2 200/3. Putting these together, if V is the optimal estimated value in M, then
2 Eo
[e E Zz]
v
Note that this is implementable for all e E Ext(S) (and returns a subset of Ext(Zx) for the query above) since the set of exits are already known.
A.4.3 FINALIZING THE GUARANTEE: QUERY COMPLEXITY
In this section, finalize the proof of the meta-training guarantee by computing the query com- plexity.
Proof of Theorem As demonstrated by Proposition and Proposition A.5 running the algo- the desired guarantees with probability
rithm in Section A.I with the parameters in at least 1 p-p-
To compute the query complexity, observe that we perform the following number of trajectories while executing the algorithm in Section A.1
O [T(NuCnvi NTS) + NRF EULER + NRF + K KND TK(N
EL BULER NEL.)]
(ULEE
Ignoring terms that do not depend on 7' or s, we obtain the claim.
A.5 BRUTE-FORCE LEARNING OF THE HIEARCHY
Theorem A.3. Assume that Algorithm ii run with parameters satisfying
NEULER = Ω CHHSAA
log SAHT
a
and
Ω ( S SAHNT 32
(CH Nthresh
CC
C SAT a²
Nehresh
log
and N N= Ω
log
P
p
Then, the returned by the algorithm is exactly Ext(S) with probability at least 1 Further- more, the algorithm achieves this result with query complexity
δ 0
CS$
A +
CSAA
poly(H).
ag
31

---

Under review as a conference paper at ICLR 2022
Algorithm 6 Brute-force learning of the latent hierarchy.
1: procedure LEARNHHERARCHY((M...............
NEVLER iterations, N policy samples, thresh-
old Nthresh)
2:
for all I. [T], E do
3: Create MDP Mř so P(e 8, = for any a.
4:
[a(s', a') f 1 [s' s].
5:
2 < T,
6:
for all I. (7), s E S, E A do
7:
Modify policies in V to play on 8.
8:
for all [AV] do
9:
Sample π ~ Unif (4/7).
Play π in M,, collect sample (s, a, s/,) if (s, a) is encountered (1, a) + number of times (s, a) is encountered above.
11:
12:
Pr(- 8, a) t estimate of (s, a) dynamics i.
13: return (s,a) (Et 1') |
Pe TV
> 3/2, () 2 Natresh }
Proof. For any (s, a) E Ext(S), Lemma A.2 iimples that s a -siinnifinnn for some task t [2]]
Therefore, is He-H-iiiiiff for any task & [T], by Assumption A.1
Now, by an argument similar to that used in the proof of Lemma A.2 we have that with probability least 1 p/3T, the choice of NEULER implies
Σ (M (TT a
NEULER
2CH
NEW?
for any exit as,a) Ext(S) and fixed task e [T]. Therefore, by a union-bound over the tasks, the same guarantee holds for all tasks simultaneously with probability at least 1 p/3.
Now, for any fixed (a/CH) -iignifiitt (s, a) pair, sampling from V at least N times guarantees that with probability at least 1 p/3S AT, N: (e, a) 2 Nthresh- Therefore, once again performing the necessary union-bound, we obtain the same result uniformly over any and E [T] with probability at least 1 p/3.
(s, a)
Finally, for fixed (8,a) and I, the estimator for Pp(. 8,a) satisfies the property that when [(s, a) 0,
H²S SAHNT HS SAHNT as
(.(- P,(. 1. (,,ls,a)/
log
log
V
P
(.
P
with probability at least 1 1-p/35AD using an argument similar to that used in Lemma A. 16 Again, by union bound, the same guarantee holds for any (8,a) and & [T]. In particular, for any (8,a) with Ne(s, a) 2 Nthresh.
|Pc ss))) P,(- s,
< 4'
TV
Therefore, by similar argument to Lemma A.10 the following true:
(a) If as E Ext(S), then there exists f, t' for which
| s, Pe 8, a) TV
8 2
(b) If as g ESt((S,, then for any o 1' with No(s, a), (s, > Nehresh:
P.. s..1s,a)) P.( 8, a)
<
2'
Putting everything together, we see that the set returned by Algorithm 6 is exactly Ext(S), with probability least. 1 p.
32

---

Under review as a conference paper at ICLR 2022
A.6 TECHNICAL LEMMAS
Lemma A.15. Let XI,..., XM be iidd Ber (p) random variables. Then, if
N
1
M
+
log
8
p
p
then with probability at least 1 - 6,
M
Σ
1
Proof. By applying Hoeffding's inequality,
P
Σ 1
M
1|
=
N 1[x = p
M p
M
N
[[x 0| (1- p
M
N 2
I exp
22M
Setting the final expression to the failure probability and solving, we obtain the quadratic inequality
2N log 1
1
p² M2
M N 0.
2
Finally, via solving this inequality for M, we find that
2N
1
M
log
2p
5
sufficient to guarantee the desired event with failure probability 6, desired.
Lemma A.16 (Dynamics estimation error bound). Fix policy x. MDP with stationary dynamics M AS P, r,, r. H), and N N. Assume that a is played N times in M, and all transitions are used to form an estimator P( s, a) using empirical averages. For any (s,a) E S x A, let N a) be the number of times (s, a) is encountered in this process. Then, with probability at least 1 p.
any (8, a) with (ss, a) > satisfies
H2S SAHN HS ((s.a)
SAHN
sup 1:8-10,81
(8, (s. V ass log
log
p
Proof. Assume that the obtained samples are given by ((sk, az (s H8 Hnntr (1) is the 7h time step in the th execution of in M for any s N-1 and 0 < r < H
ax $ k E [HN]}, so that
Fix any as E S A, and assume that (s(g) a()) {)) the j sample from IP s, a). Fur- thermore, let my (8, a) denote the index at which the 5th sample is obtained. We claim that for any E S and M HT.
M
1
Σ
[m
& HT (1 ((66)
=51
P(s s,
M
PPss' s
s
1 S
log +
log 8.
M
Let F; be defined as the o olagebrr induced by the set of random variables
{ my (a),(), 1 (6 =
- =))
33

---

Under review as a conference paper at ICLR 2022
Clearly, (F.) is filtration such that the 7th term in the sum above is measurable with respect to Fyy Furthermore, observe that
E I [mng(, a) S HT) (1 (/6 = 5-| - -P(s" 8, s,a)) Fy-1]
= [ (6))) = sr] - PP(s" |s,a) F5-1. & HT] P(m,(s,a) & HT)
Therefore, the random variables the sum forms martingale difference sequence. Furthermore, the sequence is bounded in [-1, 1], and satisfies
Var 1 [m)(s.a) S HT (1 [66 = -P(s" ss,a)) [r)-1]
=E Var [ [1/06) = 80 - PP(s" |,,a) m,,,, s HT] [5-1]
s (P(" s,a).
Therefore, by applying Azuma- Cruma-Bernstein, we have that
M
(s, a) S HT] [1[0/) ss
-P(ss s, s.a))
Psss
M
2P 18,a)
SAHN
2
SAHN
log
log 6
M
M
with probability at least P/SAHN.
By applying union bound on as, a, s*) and M, we thus have that with probability at least P.
M
[m a) S HT]
[6 (I(50))
5*
- 1 s,a))
-P(s
M
(s 18,a) SAHN 2
SAHN
M log
log 8
M
holds for any (s, s)) and M. Conditioned on this event, we thus have that for any (s, with ((s, a) 0,
Prl. s, P.( P.(.1ssa)
1
Pa(s' (s -P((s' ssa)
TV
2
.'ES
P(s' s, a)
SAHN S
SAHN
Σ
log 5
log
N(8 a)
N(8
8
S log
SAHN
S log 8
SAHN
N(s, a)
8
N(s,a)
The final result follows simply by noting that
[ [())_ a) - IP. s, P.c.1ss00 s, a)
TV ll
Lemma A.17. Fix two MDPs M = A, H) and M' = AS,,,P r, H). Let A denote the subset of S A for which (. a) # F., s, a). Then, for any policy n.
Vo M' (ss))
Mi (so) > p = PM (Tx A Ø) = PM (Tx 0) H
34

---

Under review as a conference paper at ICLR 2022
Proof. Write q = PM (Tr O A Ø). Note that VoM'.
("(so) can be decomposed
H-1
Vol: (50)) qlE.
Σ
rh and
Tx T
#
+ (1 - BM
Σ
(n(sn, ah)
Ta 0 Ø
qlf + - (1-q)lEM
Σ
Th(sh an)
Tx 0
h=0
Since P and IP' agree (8 x A [H]) \ A, the dynamics of M and M' agree up until π performs an action in A, and thus
PM (Tx 0 # PM
(Tx 0 A Ø)
H-1
H-1
EM
Σ
nh (Sh; ah)
Tr TN EM
Σ
(s an)
T5 --
Furthermore,
(1 g)
(sh. an)
Ta n8== = Ø
< V.M.a (so) S (VoMi.()))
4=
Putting everything together,
VoMisT (5o) S 9H VsM) q H
A.7 WHYY SHOULD OPTIMISTIC IMAGINATION HOLD?
In this section, we provide heuristic explanation for why optimistic imagination can be expected to hold in most scenarios for which Definition holds
Recall from the main text that if exit satisfies the preliminary coverage condition, then be detected using only Phase I data. Therefore, we can restrict our discussion of Assumption t. subsets of exits that only have nonzero importance for task if IP, (- other words, we can only guarantee that near-optimal policies for the source tasks observe de. We will provide heuristic reason to why we can then expect to find an MDP such that condition (b) of Assumption 4.1 holds for such a subset S.
is some distribution de. In
State visitation measures. function is given by
Recall that the value function in an MDP with a stationary reward
V.M.
Σ E... (r(sn,a)) sal h=
Now, if we assume that the reward is only function of the state (as in goal-conditioned RL.), and view as a vector in |S)), then we can write V.M, (so) HPM. where
#-1 M. (s). = = so).
(s) =
H
h=
That is, PMr. is the state visitation measure of x within M with horizon H. This geometric view- point explored by Eysenbach et al.) (2221) in the context of unsupervised RL in the discounted infinite-horizon setting. We note that for any fixed M, {PM,al a convex subset the probability simplex.
35

---

Under review as a conference paper at ICLR 2022
Constructing the desired reward function. Let M be any task such that the set T {e E S (- # ] is non-empty. Furthermore, let M be the corresponding MDP described in Assumption b. after borrowing dynamics, so that
P( | s,a)
(s,a) S otherwise
P(- [,
(ds,aa)
> B for any S, heuristically, we expect the is the dynamics of M.. Since |PM - (M(-e))-dellvv following to true: Assumption A.2. There exists n² such that PM {pMa).
Stated less formally, expect there to be states that n² reach better in M compared any policy in M.
Example A.1. In the four-room example, this intuition captured by the fact that the agent can spend more time in states past open gates compared to if they were closed.
Under Assumption A.2 above, since {PM,-} is convex, we can find reward direction separating {PM,)} and p more formally,
PM sup P M.
Then, the MDP M with reward function r satisfies the desired condition in Assumption 4. ()- Thus, under Assumption(A.2) the coverage condition can indeed hold with sufficiently diverse source tasks.
36

---

Under review as a conference paper at ICLR 2022
B META-TEST PROOFS
We now provide an analysis of the regret incurred by learner using approximately learned hierarchy at meta-test time. We first show that the hierarchy oracle from the source tasks can provide useful temporally extended behavior. We then show that using these policies results in bounded suboptimality and achieves a better regret bound compared to standard UCB-VI.
Throughout this section, fix an optimal x satisfying the conditions of Assumption 5.1 Further- more, we assume that we have access to a hierarchy oracle that provides e-suboptimal policies as defined in Definition
B. USING THE HIERARCHY ORACLE
In this section, show that the hierarchy oracle can be used implement two useful behaviors: (I) reaching exits and (2) behaving optimally within a cluster.
B.1.1 NEAR-OPTIMAL GOAL REACHING
Assume that the agent is currently at state = E U at time step h, and intends to exit the current cluster Z via exit (s* aa*) Ext(Z). We obtain policy implementing the high-level intent as follows:
(1) Define the termination for any (s, a) E ExI(S) as:
fs( = ees
(s, = g
1 otherwise
(2) Define reward as Tes (s, = 1 Osl
(3) Provide (z. fg. res: H h) to the hierarchy oracle and obtain policy Tz.g.h-
For simplicity, we will write Thier (z, g) for a (2,g) g) throughout our analysis. The following proposition quantifies the performance of the obtained policy:
Proposition B.1. hhhre satisfies the following inequality:
E
[hher H- (=, S (T +e.
Proof. Due to the definition of Py, and r, observe that for any I,
V0T (z) EF
rshh: ap) 8n = = =( h) (
Therefore,
(H - h) - Ti T (2.g) - (H h) - [T
(rppeer(2, (2.
E ( (z,e +
B.1.2 NEAR-OPTIMAL WITHIN-CLUSTER BEHAVIOR
Assume that the agent is currently state E {oo} U Ent(S) at time h, and intends to remain in the current cluster Z while maximizing given reward function r. We obtain a policy for this high-level intent follows:
(1) Define transition dynamics for any as E Ext(Z) as P(: s, = 8(er).
Provide IP, and planning horizon H h to the hierarchy oracle, and obtain policy æ.
37

---

E Z G) Under review as a conference paper at ICLR 2022
B.2 FORMAL LEARNING PROCEDURE
In this section, we describe the procedure for learning policy using the cracle-provided policies described in the previous section. Formally, we construct surrogate MDP whose dynamics are determined by M and the oracle. We can then apply any tabular learning method this new MDP (in our case, EULER), obtaining policy in the surrogate MDP that readily translates into policy M.
The components defining the surrogate Man Ph, Rai, Het) are follows:
Meta-state space 2.
We set
= (Ent(S) x {o.................. H ++1))
where H is high-probabiligg bound on the time to move through Het exits (to be determined later). We incorporate the time step into the meta-state to ensure that both the dynamics and reward computable from the state information (ensuring that Mbi is indeed an MDP)
Meta-action space G. Given a current meta-state (s, where Z, the available meta vcta-actiins G can be identified with Ext(Z) U (e).
Algorithm 7 Performing a Meta-Transition
1: procedure PERFORM
b Executes the desired meta-transition in the original MDP M.
2: if then
3: return e
4: else = h)) then
5:
if h <. H then
6:
if 7* or - then
7:
Execute within-cluster policy from oracle until termination. return @
8:
9:
else
10:
Execute Nz.g.A obtained from oracle until g is performed or h H. 8 N current state and time step
11:
12:
if was performed then return (s', h!)
13:
14:
else
return (s, H 14+10 1)
16:
else
17:
if 7" or θ then
18:
return e
else
20:
return h)
Meta-dynamics Phi- Fix (z,g) E x G for some + e, so that = = hs We consider the procedure Algorithm for generating the meta-dynamics. Intuitively, we execute meta-action * e by running the oracle-provided policy until the learner encounters g, or has acted for H timesteps the current episode. On the other hand, if g = o the agent executes the oracle-provided e-suboptimal policy that remains within the current cluster and acts for H h timesteps.
Formally, the next state z' is given by
E or =
1'
(s' hs)
h< H
otherwise
38

---

Under review as a conference paper at ICLR 2022
where s' and h' are generated given Th (s.g)
hier 1' h (s,g) g) = min(h + T (s. + +11)
IP g)) h' s
s M
((s)
otherwise
Note that the learner can only execute meta-actions while h - H. Furthermore, given access to M, one can easily simulate the dynamics Mai.
Meta-reward Rai- Fix ((s, g) E 2 x g. Recall that the reward function of M is supported on Ext(S) (Z*) Thus, this reward function can be lifted onto Mbn Formally, we define the following reward function:
(s)
= == (s, 8 7" and h < H 2 == (s, z and h' < H
(2, = r(g)
otherwise
where (s) the random sum of rewards obtained by playing a within-cluster policy starting from s' for the rest of the episode. Note that Rui depends on Pui and is thus random. Furthermore, this reward function is consistent with how meta-transitions are performed in Algorithm 7
Meta-horizon Hell Recall that there exists an optimal policy that encounters most Hell exits with high probability. Accordingly, we limit the learner to being able to choose Het high-level actions, which recall can be choices of exits.
Solving Ma1- To obtain the desired policy, apply EULER to Mn. By the construction in Algorithm 7 the policy set returned by EULER easily translates into policies on M. Furthermore, the value of this policy is the same both MDPs.
B.3 PROVING THE REGRET BOUND
Having defined the procedure for learning policy using the hierarchy, regret analysis. Our analysis proceeds by constructing a policy expressible in Mai that achieves near-optimal returns by imitating the high-level decisions made by n" We then use this policy comparator policy when applying EULER regret bounds to Mal-
proceed with the
To formally construct the desired comparator policy, need first define the notion of meta- history, which contains the set of high-level decisions made by any policy:
Definition B.1. Fix a policy n, which given some horizon L, generates a (random) trajectory (Su, .o. 8L). Let Ext(T) be the number of exits performed in the trajectory, i.e.
T-1
Ext(TT=
Σ [(,,, an) E Ext(S))
h=0
The meta-history (T)(T) corresponding to this trajectory is the sequence
(zo, 9o, 21, 21,91....... (Ext(s)) = (Sior ($jor as,); Si, (8),;;;)) siguto));
where
== 0 in In-1 otherwise
0
in min
1 [(5h, an) E Ext(S)]
h=
Note that 2, E Ent(S) and gi EXt(S) for all 0x...,,,E((( Ext(T).. We omit in writing Ha when the underlying policy is understood.
Informally, Hii tracks all entrances and exits contained in a trajectory generated by я. We define the length of meta-history Hn. denoted as |HHi], the number of exits contained in Hui-
39

---

Under review as a conference paper at ICLR 2022
B.3.1 POLICY CONSTRUCTION
We now proceed with constructing the desired policy, Intuitively, the comparator imitates the dis- tribution over (TTTT") ), conditioned on [Ha((T)) I Heft- To see why this is sufficient for near- optimality, recall that the reward on Mrg supported on Ext(Z*) (Z*).. Consequently, by imitating the distribution over meta-histories the policy is expected to obtain roughly the same sum of rewards in expectation from the exits. Therefore, all that remains to ensure that the learner
collects roughly the same sum of rewards from Z", which is the same ensuring that this policy does not take too long to reach Z"
Construction. Let H. be the running meta-history, containing k S. Hoff actions. The optimal policy induces a distribution q(- H) over Ant representing the next exit it take
5 We then define и as
. 2 H) = H)) z = (8, (), H
(g( e
otherwise.
Observe that π terminates the episode upon reaching H. Furthermore, this policy is dependent on the meta-history. However, since Mu is MDP, there exists a stationary policy that achieves at least the same value.
B.3.2 SUBOPTIMALITY ANALYSIS
In this section, we prove that и achieves bounded suboptimality. Rather than analyzing т directly in Mhi, we construct a new Ma and to better track the meta-history. In particular, conditioned on the event that requires more than H time steps execute, then the agent would not be able to imitate the full meta-history generated by n², even after having performed less than Hetr exits.
Constructing a surrogate for analysis. We now formalize the construction of the surrogate MDP Ma and the policy मे corresponding to π in this MDP. To obtain Mu. we redefine the dynamics from Maл so that s' h' P(- 99) in Mni. In effect, we allow the policy continue performing transitions beyond H, although without any reward. Accordingly, we define मे as म H)
4(1 H). The following lemma formalizes how ă and Mui have desirable properties for the analysis: Lemma B.1 (Surrogate Policy Characterization). Let μ. denote the distribution of Hhi(=*) [Haa(=)]| S Helt in MTg. and jı the distribution of ((F) in Mai Then, (1 (1-()) O) S j..
Proof. Let v² be the distribution induced by the following procedure:
(1) Sample a meta-history from the distribution Ha((T") [P(m(*T)) > Hat-
(2) Truncate the obtained meta-history to length Haf.
It is easy to see from the definition of स that j 5)p" + Çv*. The desired result follows.
Thus, we have indeed shown the desired property that गं properly tracks the (truncated) meta- victa-hstoryy generated by प.. To justify performing our analysis on (Mii, 7), we have the following result, which shows that any result on the value of the pair above applies to the value of π in Mai-
Lemma B.2. As constructed above, V. (so) Mai. (so).
Proof. We write M = Mai and M = Mai. Similarly, we write n' = न. We proceed by proving chain of equalities.
(V"'.M" (so) V=.M' (su)). We omit M' in this part of the argument for clarity. By the perfor- mance difference lemma, we have that for any [Hetr] and = E Shi.
H
Vi (50) Vor((0)
(so)
E Exwdy
[A] (z,
'The distribution g can return the learner stays in the cluster until episode termination.
40

---

Under review as a conference paper at ICLR 2022
Let A == {2 Sni & 2 HJ, which is the set which and x' disagree. Observe that for any π and k, (z) = for any a E A, and thus A (z, T) = for all such states. For any other 2, A (2, T) is clearly 0. Thus, we obtain the desired result.
(VT.M (80) Vm.M(sn) We omit in this part of the argument for clarity, Using the simulation lemma,
Halr
Vo (80)
(50) Σ
E (2z)))aam
[[(PMM PMM)
Observe that the behavior of the two MDPs are identical conditioned on // < H. On the other hand, conditioned h' H, can longer receive rewards from either MDP. Therefore, [(PPMM FMO) (z, g) = 0 for any j. 2,g by decomposing the relevant expectations along the two events. We thus obtain the desired result.
Analyzing the surrogate. values
With the results above, now proceed to analyze the difference in
Vor0 Mrs (5o) - Mu (so),
which then implies the desired suboptimality result. First, we have the following lemma character- izing the time स requires to fully execute a given meta- veeta-history in the base MDP M:
Lemma B.3. Fix any Hal (20.900 9u................. ... such that (Hall I Hel. Furthermore, define the sequence of reaching times
To = and Tp = Tk-1 + Thiie T--r,,, (kk-1,2k-11) 2k--))
We define Thier (Ha)) to be the time required by the hierarchy to execute Hus which is formally given by T THail in the sequence above. Then,
(a) E [Thier (Hw)) & [1 + (1 (1+ W) HeHHet-
(b) Let 0² = (3 W) + e] Hot.... Then, for any 1 0.
P (I hirr (Hm)) 2 (1++ + +e]ttetf + +t) S Se-
Proof.
We prove the two parts separately:
(a) We will prove via induction that E Thl S k (1 + w)W + E). For any and Ts-1,
E Thiier The nn- (ZK- 1, 92-1) T
< E
Th-n- (zu gh-1) Th Tk-1 +e
s s( 1 + E Ti-m, (
Th-2 te
1 (1 W +
where the first inequality uses properties of the hierarchy oracle, while the final inequality follows by combining Definition (52 and Assumption 5.2 Therefore, by linearity and the tower property of expectation,
Th
E [Tk
1] + E
TH
(2k 11 9h-
E
T + E
Thier
TT (2 12--1-92-11 Ta-1]
E [T-i] + 11 (1 W)W +E.
The desired result then follows by induction.
(b) Let Bg == [1 +
+ and (a( = E Theer(zz (zx,g:) Note that for any & and 1, B&-1 1 + (1) & BE, by following the argument in (a). Therefore, for any X > 0.
E (exp {> (Th - BBHH
E E /exp {> (Tx B+)} Th-ill
E E exx {a (Th-1 + Thier 1 BE-1 (n-1(Ta-1))} TR-1]]
41

---

Under review as a conference paper at ICLR 2022
where the last inequality uses the monotonicity of the exponential function. Therefore, by applying the sub- Gaussian condition given in Definition 55.2
(exp {} (Tk BB]H
E exp {} (TR-1 Bk-1)}
{x Thieer H-Tx-1 1k--1) - fk - (T=-) [T-]]]
exp
$ B exp (M(Tk-1 Bk-1)H exp [A²C*/2]]
where we have used the fact that Theer Th-1 (=x- s(gn-1)) has sub-Gaussian upper tail with variance proxy
=² B2 TH- 6 Tk-1] 1
S [ w) +e]²
Note that we have once again used the properties of the hierarchy oracle, and Assumption 5.2 Therefore, by induction, E [exp {) (Th- - B&)H < E {>(VVCC)//2 from which desired tail bound follows by making use of Chernoff's inequality.
As we have shown that स closely tracks the meta-history of π" and have analyzed the distribution of time it takes to execute given meta-history, can now analyze its suboptimality: Lemma B.4. There exists policy π expressible in Mn such that
V. Mixi (so) V. t (8o) $ (1 + Hos + B HaH)
( 3(1 + 7) Hes W + CH.
Proof. Assume that π² generates (random) meta-history of length N given by Hml (2o: 90, 21, I1, ...,, 2N). Furthermore, let T denote the (random) time takes to reach 2N. Then, given Hhi and T observe that we can write
(sn) E (R-- (Hmi), where (76()) = (=N) [IN E 2
r(g));
using the assumptions on the reward function and condition (a) in Assumption 5.1 letting E be the event (N < Hes), we can bound the hand side as
Subsequently,
Vo (o) E R (Ha)) < (1 ()E [R (Hai) E] CH,
where we have used Assumption 5.1 to bound the probability that N > HaR
Our goal for the rest of this proof to transform the expectation on the right-hand side into form that lower bounds V (su). To this end, we define
N-1 Th Ta-1 Theer H-TT-- (Zk, gz).
Rhier (Hm) = Vihler (EN) [EN E 24 +
r(g)),
and the sequence of times
To and
Note that Rhier and TN are analogous to R and 7*, respectively. Then, letting F be the event (Tn S lI). note that
Vi - (1
<) R E + CH
= (1 -{)E Rr plile
+ phier
E] + ÇH
< E (RT- Rdler) 1 [F]
E + (1 C)
phier [F] E + [c + P(FO) E)] H.
(II)
42

---

Under review as a conference paper at ICLR 2022
We bound (I) and (II) separately.
Bounding (I). Let be the event En EaN E Z*}. Then, if we define
N-1
Tmin ux) S N(W + +1) min Σ
as the minimum time needed to execute Hmi we then have that
E [ -R
[F]
E] = E Rī--
RTw E]
IE Vi- (2N) - Vhier (zn) G]
E V (ZN) - Vin (ZN) G]
H P P(V (2N)
Vi (2N) > a G) da.
Note that the bound on Tin follows from Assumption 5.2 To convert the different in values into a difference of times, observe that if TN Tiin S E, then
Vi Tam (EN) Vhhier (NN) Vig mi (EN) ViN (EN) + VTN (EN)
VT (EN)
< (T T min) +
a.
Therefore,
H1
P P(V (2N) - IN (2N) a G) da
H1
P(TN Tiin > a aa- G) da
H1
E
P(TN T min a Hml) da G
I" P(TN - [1+ (1++) Hefffff > a- Hort(W + +8) } Hhi) da G
E
SE Hotl + +e)+ +E 1 P(TN 1+ 7 + HH
Hhi) do G
S6+ (> + +) + ([ + W + ss)
where the final inequality integrates the tail bound provided in Lemma B.3 Overall, have that by rearranging,
I Hos Bv Han)
[ + +13(1 v)v Hot W.
Bounding (II). By the characterization of ग in Lemma B.1
(1 (1-C)E [Rbber (Ha )) [F] E < Relier (Ha ( [F]] I Vo (s0), where the final inequality uses the fact that Rt (T)) is the return of न in Mns. given F. Concluding, Putting all of the previous bounds together, find that
Vo (8o) < V0rh (so) + (1 + Hen + BB He + H + 3(1 + 7) Hen W
+ | + P E)] H.
By setting H to sub-Gaussian tail bounds on Tx implies that P (FC) E) S Ç. Finally, by Lemma B.2
3[(1 + W) + +ely 2He log C < = + (1 + W) + +c]
H,
V. Manc (so) Mar (so) Vo Mrg.
where the last equality follows by the construction of Ma1. We thus obtain the desired suboptimality bound.
43

---

Under review as a conference paper at ICLR 2022
B.3.3 REGRET ANALYSIS
As earlier suggested, we now make use of ir as a comparator policy in order to prove regret bound on a learner making use of the procedure outlined in Section B.2
Theorem B.1. Assume that EULER generates policies Ti:..,;Ny on Mb,, as constructed in Sec-
fion B.2
Then, we have the following regret bound:
((o - (s0* S V HHHLMN Essbopp:
where
Exubopt = (1 Heff + BV Hen)e+ E + [y + 3(1 + Helt
W + CH.
Throughout the proof, we consider applying EULER to Mui where the rewards are scaled by 1/H to ensure that rewards are bounded in [0, 1]. As result, can bound G < in the EULER regret bound in Zanette & Brunskill (2019), since the sum of rewards in Mul is also the sum of rewards in M, and scaling by I/H gives the desired bound on G. Therefore.
Proof.
Mii - V0 (5o) E H H V VHRHLMN. vo
Hell
Furthermore,
Vo (So) Vi MM (so) (s)) (s0) + Vo Mst. Vo Mst.) S Esubopt- We thus obtain the desired result.
B.4 AN EXPONENTIAL REGRET SEPARATION FOR A HIBRARCIYY-OBLIVOOSS LEARNER
In this section, we provide proof of the exponential regret separation between a hierarchical learner and learner oblivious to the hierarchy. The overall idea behind our proof is the reduction of solving family of minimax instances described Domingues et al. (202T) to particular family of task distributions.
B.4.1 THE HARD TASK DISTRIBUTION FAMILY
In this section, we describe the family of task distributions that forces any meta vreta-taiiiigg-eee obliviouu learner incur exponential regret. For any string s, we write [s] for its length.
We now define the family of binary tree room MDPs Mw of depth W. We index member of this family by tuple (E* a", ee*). where t" a binary string of length W-1, 1, and a" a",e" E {0. 1). The MDP Mie M(rr,a,,"") AS,A, P, (E",a""ee)) H) corresponding to this tuple is constructed as follows:
State Space S. We create root 8ront, 2W 1 states indexed by binary strings of length most W collected into a set T = {sD, 81, 800, so ). a gate state Sgate, and terminal states Strap: θs, Sp.
Action Space A.
The set of available actions at every state is the set (0, 1}.
Transition Dynamics (eetaa))))>
We define the dynamics as follows:
6(su)
Sroot
d(sta)
St T, W
+ (1-b)6(Quap) b6(sgate)
8 = s; E T, | = W - 1,
Per ae 8,,))
8 + sr., b ~ Ber (1/2)
68 6ō(sgate)
+ (1)bb)8(Sua))
sp b Ber (1/2 + =1 [a a²))
5(es)
Sgato, e²
6(0F)
8 = Sgate, a E.
44

---

Under review as a conference paper at ICLR 2022
Reward Function The reward function is r(s, a) [ Os] + 1|s Sgate, a*).
Having described all the components of every member of Mw, all that remains is to construct the family of task distributions Tw. Each member of this family will be indexed by (l*,a"), where & and a are as described above. Then, the task distribution T(--,a)) Tw chooses uniformly within the set {Mee-aa (0))" .0) M at., Note that this implicitly defines the latent hierarchy so that the
clusters are {Sroot: Sgate: Otrap] UT, {0s), and (0r). Furthermore, the set exits for the first cluster is {Sggate 0), (Sgate: 1)}-
B.4.2 A FAMILY OF HARD INSTANCES
In this section, we describe the family of hard instances which we reduce to solving the task distri- bution above. Intuitively, if an algorithm incurs low regret throughout Mww, then it must be able to quickly find policy to reliable reach the gate state Sgate for any MDP in the family.
Constructing the hard instances. Accordingly, we define a new MDP family Nw, which now is only indexed by (L", a a²), and is constructed similarly as any member of Mw. but ignoring states outside (root Sgate, Strap UT'. Additionally, we redefine the reward function r for any member to be r(s,a) a) regret bound in Domingues et al. (2021).
s S-ate]- We note that this is exactly the of hard tasks used to prove minimax
The lower bound. We state the lower bound result from Domingues et al. (202T), in a slightly more restricted form for case of proof and presentation. In particular, we consider the following more restricted definition of an algorithm:
Definition B.2. Let Hn be the trajectory data generated by playing policy Tn in an MDP M. That is, H., = ((50, do, ro, 81), ($1, 01, F1, 82), (sH-1, ",, sH))), where and ao are fixed, Fh r(s,, an., and 8h41 FM[- 5h; an). Additionally, we Ho Ø.
Then, a valid algorithm A for our purposes is one which, for the nh episode, outputs deterministic, non-stationary policy ı that is solely a function of the current state and action and U H4. That is, does not output policies that adapt to the current running episode.
We again emphasize that this restriction is not necessary but that many algorithms nevertheless satisfy this condition (including UCBVI and EULER). We then have the following hardness result:
Theorem B.2 (Domingues et al. (202)) Theorem 9, restated). Assume that W 2 and N 3W. Then, for every algorithm A, there exists an MDP M E Nw such that
N
EM.A
Σ
Vo (Sroot) V0T"((soool)
2 22/2
H 2
Algorithm 8 The reduction of learning Nw to learning Mw in Section B.4.3
1: procedure PA(M E Nw)
2: Initialize Ho = Ø
3:
for all [N] do
4: Obtain nn A(Ho............ Hn-1).
5:
Play n. in M, get history In ((50, 0og Fo, 100..((99-11,,0-11700-11111
6:
sw+1 = Sgate then S $ SW+1
7:
8:
for all W + 1,...,,14 do
9:
if h W then
10:
s h+1 t θs if an = 1 else Op.
11:
- 1 las =
else
13:
1h441 t sh. T/e + Th
14:
Replace (sh, an. The (h+1) with (sh, an. The sher) In
Hn Gn.
45

---

Under review as a conference paper at ICLR 2022
B.4.3 PROVING THE HARDNESS RESULT
We now use the hardness result in the previous section to demonstrate that no algorithm can incur sub-exponential regret in W on all tasks in Mw. We do so by proving that an algorithm solving all tasks in Mw can be used to construct an algorithm for solving all tasks in Nw.
Formally, let A be any algorithm for learning any MDP in Mw. We then construct an algorithm PA for learning any MDP in Nw as in Algorithm g
Given this reduction, we aim to prove the following result: Proposition B.2. For any Mee E NNw, we have that
N
N
EM a*).P
Σ
Vo (S000)) - Vo (froot) S E an at and
Σ
Vo (Sroot) - V/0 (Sroot)
To prove this result, first prove that PA simulate Me)rar.1)
Lemma B.5. For any the distribution over (Ho..... H.) induced by running Algorithm 8 over ar) E Nw equal to that induced by running A over Mir E Mw.
M()
Proof. We proceed by induction. The result holds trivially for n
Now, assume that the result holds for some nt We condition on the histories (Ho...., Hn) Then, note that both algorithms play the same policy Th+1, since PA uses A to obtain the next policy. As a result, by the construction of M(e-.a") and MMe-.a the distribution over (sh. ah, The 8h+1) are equal for h < W. Furthermore. Lines on Sw+1 = $gate, while conditioned on sw+1 = Strap, the dynamics of the two MDPs are the same. Therefore, conditioned on any (Ho...., Hn)). the distribution over Ha+1 induced by the two algorithms are also the same. Thus, the claim holds by induction.
14 simulates the dynamics of Mieaar.. conditioned
Finally, we can prove Proposition
B.2
Proof of Proposition B.2 Throughout this proof, we omit the starting state Stoot and the timestep in the value. We prove the result by induction. Clearly, the result holds for N = 0.
Assume that the bound holds for some N. Then, we have that
N+1
EM
Σ
V
Van
=EMer P
Σ V vTn
+ E EM IV*
VTN+1]
< EMe and
Σ V*
VTa
+ EM
E [V*
V (Ho.... Hx))l
where the final inequality uses the inductive hypothesis and the tower property of expectation. Now, recall from Lemma that
E EM P [V V
EM A [ IV* - 1 (Ho, HN)]].
We emphasize that the value functions still with respect to M(e However, for any policy output by A,
V" V Emirr (a) [H W 1)1 [sw+1 * Sgatel]
< Em(e [H W - 1)1 [sW+1 + Sgate aw + 1]]
s EM 1),a [H - W - -1)1 [sw+1 * Sgate or aw+1 * 1]].
Note that the right-hand side is the regret in M(E" a", 1) for playing म. Therefore, since both algorithms play the same policy #1+1, thus obtain the desired result by induction.
46

---

Under review as a conference paper at ICLR 2022
With Proposition B.2 now formally state and prove the separation result:
Theorem B.3. There exists task distribution T(e E Tw such that an algorithm A, without access to the meta-training tasks {and thus without access to the hierarchy), incurs expected regret lower bounded as
BM RRegret (M,, 2 2W/2//2N.
On the other hand, for any task distribution in the family, the hierarchy-bac based learner in Section B.2 with access o-suboptimal hierarchy oracle, achieves regret bounded by v H2N with high probability on any sampled lask.
Proof. Fix any algorithm A. Using Theorem B.2 there exists M(Ex,a>) such that
(rroo)) V0aT (Sroot)
~ 22/2
Thus, by Proposition
B.2
E M a)
Σ Vo' ( ($ro0t) Via (Sroot)
2 22/22/222
Note that the proof in Proposition B.2 can be extended for M(e-rat.0) with approprite modifications to P... and thus the same inequality holds. Consequently,
E BM [Regret y (AA) 2 2w/2 V
On the other hand, with access to the 0-suboptimal hierarchy oracle, observe that the learner only has to plan at timesteps 0 and W + I, allowing us obtain tighter bounds (as Sn is smaller than the construction in Section BB.2). Furthermore, the suboptimality of planning with the hierarchy oracle O for any task distribution in the family. We thus obtain the desired bound.
B.5 A DISCUSSION OF DEFINITION 5
In this section, we discuss why the values defined in Definition 5.2 control the suboptimality of the hierarchical learner. In particular, we provide examples of MDPs that satisfy Assumption [5.1 and are thus in a sense tasks that are "compatible with the hierarchy", but nevertheless force a hierarchy- based learner to incur O(H) suboptimality.
B.5.1 (a,, -...)NNRLLLABB..TY
Consider the MDP in Figure 9 with horizon H + 2 and two actions a" and 01. The optimal policy
chooses a" at every step, achieving a value of H- - -O(1, since
1
1 H
+ 1 4 ([I-1) -1) 4 (
(00+ H V
"1
# h
= Σ
Σ h=1
H - 0(1).
2h 2
2h
Now, assume that the MDP has latent hierarchy so that the set of exits are given by (ti, a) for any i E [H] and a A. Clearly, the optimal hierarchy-basee learner would always choose (lo, a²) or (tu, a1) as its high-level action. However, if the agent fails to transition to ty at the first timestep due to stochasticity, will go the end of the chain, back to Su and try a" once more. This is because it already has set meta-action, and does not replan until an exit is performed. Thus, the optimal agent on the meta-MDP achieves value of H/2, and therefore O O-suboptimal hierarchy oracle.
even with a
Intuitively, hierarchy-based learners as formulated in Section B.2 fail on the MDP in Figure 9 be- cause such learners commit to skill until completion. Thus, when such skills exhibit high variance in completion times, hierarchy-basee based the current state (e.g.. in this case, choose another exit if a" fails to take the agent to the current subgoal). Thus, (a, 5) rellabbbyy serves to eliminate such MDPs, ensuring that the skills corresponding to reaching exits reliable.
learners fare worse than other learners which are able to replan
47

---

Under review as a conference paper at ICLR 2022
1,=1
g*
to
4
L
0.5
0.5
0.5
0.5
0.5
0.5
0.5
80
SH
Figure 9: An MDP that does not satisfy low (a, -ureeliiabil where a" is in blue, and a, is in red (and purple for both actions). State shading represents state clusters, and rewards are 0 unless indicated otherwise.
B.5.2 7-GOAL-REACIING SUBOPTIMALITY
In this section, we show that even when hierarchy-based learner has access to highly reliable skills as in the previous section, the learner may still incur high hierarchical sub-optimality. Consider the MDP in Figure 10] where we focus are two exits, one from 1//2 and one from T2//-- Note that a O-suboptimal hierarchy oracle has highly reliable goal-reaching policies for reaching both of these exit states, requiring exactly H/2 timesteps with stochasticity.
single room for simplicity. Furthermore, assume that there
However, given the values assigned to (H/2 and TH/2, the optimal policy would opt to take the state t, which transitions to either state with probability at least 1/2 only two environment steps. Therefore, the optimal policy achieves an optimal value of H O(1). However, the optimal policy, in having to commit to exactly one of the exits, will achieve a value of H/2, and thus be O(H)- suboptimal despite having perfect hierarchy oracle.
Hierarchy- learners fail on the MDP Figure because an optimal policy for geal-reaching does not necessarily reach goal as quickly possible. Thus, r-goal-reaching suboptimality is regularity condition that ensures that this is indeed the case.
0.5
0.5
14/2
TH/2
Vg =
(r = H
Figure 10: An MDP that does not satisfy low 7-goal-reaching suboptimality. with three actions indicated by red, blue, and purple, and exits and rh. The MDP satisfies (oo, -)-unneliabbility yet nevertheless exhibits high hierarchical suboptimality.
48


Reviews:
[{"review_id": "w7QYGTYKGBm", "reviewer": "Reviewer_AT7G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "However, the current version does not convince me to recommend acceptance due to the following concerns:\n\nQ1. The authors assume that the agent has access to transition models (including transition probabilities and reward functions), but transition models are difficult to obtain especially for complex real-life environments. I, therefore, suspect whether the theory is valid for MDPs with high-dimensional state spaces and complex transition models?\n\nQ2. The authors assume that the latent hierarchy partitions MDPs into clusters such that the non-exit dynamics is unchanged. Does that latent hierarchy exist in general meta-learning RL problems? Additionally, in many meta-learning settings, meta-training tasks do not necessarily share a common state space. I suspect whether the proposed theory and algorithms can be used in general meta-learning RL problems.\n\nQ3. The authors make many assumptions, but never explain whether they are reasonable for realistic RL problems.\n\nQ4. The main text does not introduce how to partition the state space into clusters, and how to optimize the high-level and low-level hierarchical policies. \n", "summary_of_the_paper": "The authors develop a theoretical framework to discover the latent hierarchical structures shared across meta-training RL tasks, and propose a tractable hierarchy-learning algorithm with provable guarantees. The paper seems to be theoretically solid, and is well organized. I appreciate the proposed notions, such as latent hierarchy, $\\beta$-dynamics separation, $\\alpha$-importance, and so on. I believe they can provide researchers with a novel perspective for studying hierarchical RL.", "summary_of_the_review": "Although the paper seems to be theoretically solid and presents many interesting notions, the current version does not convince me to recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VNw88tXTRSf", "reviewer": "Reviewer_WLF1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The formulation of hierarchical structures (Definition 4.1) is quite interesting and covers many real situations in HRL. From the discussion on the related work, I understand that this formulation is novel enough, and the understanding of HRL is still limited. I believe that this paper can serve as a good start to the theoretical understanding of HRL. \n\nHowever, I feel disappointed that there are so many assumptions in both the main text and the appendix. Since most of these assumptions are proposed for the first time and not commonly used in the previous literature, I believe the authors should discuss more on the necessity of each assumptions. Also, there should be more discussion on whether combining these assumptions may exclude common situations in HRL. I state several problems that I am mostly concerned:\n - Assumption 5.2 seems to be made to ensure that optimistic imagination works for the latent hierarchy formulation. However, it looks artificial and I doubt whether this assumption is commonly satisfied in the HRL tasks. \n- In Assumption 6.1 you assume that only one cluster has the positive reward. Why this assumption is necessary? This is not the common case in HRL tasks, and can we remove this assumption?\n- There are many parameters in these assumptions such as $\\alpha$, $\\zeta$,$\\rho$, $\\tilde{H}$, $T^*_{\\tilde{H}}$, $T^{min}$ ... If possible, I wonder the magnitude of these parameters in common HRL tasks, e.g. the gated four-room environment used in this paper as an example.\n\nIn section 5, the authors propose a novel algorithm to learn the transition dynamics and detect exits. Compared with the query complexity of the brute-force approach, is the complexity in Theorem 5.1 strictly better in all parameter regimes? Can you briefly explain the main difference between your algorithm and the brute-force approach?\n\nAnother minor issue is about Theorem 6.2. The regret bound in Theorem 6.2 ignores the sample complexity to learn the hierarchy oracle. If I understand correctly, the total complexity to learn both the hierarchy and the sampled task can still be exponential in $W$ in the hard instance construction. Therefore, there is actually no exponential separation between HRL methods and brute-force methods.\n\nThe paper can be further polished by fixing the typos and clarify several statements:\n\n- The definition of Regret in Section 3: $V^*, V^{\\pi}$ -> $V_1^*, V_1^{\\pi}$\n- Section 5.2.3, line 2: What do you mean by optimistically choosing dynamics estimates?\n- Section 5.2.3, line 4: $M_t$ in Assumption 5.2, not Assumption 5.1?\n- Definition 5.2: What is successful and failed termination? Are they two newly-constructed states in the definition of the new MDP? What is the definition of the distribution $\\delta$? Is the input of the oracle the four-tuple $(x,f,r,\\tilde{H})$? If so, how can we know $P_t$ used in the definition of $P_f$?\n- Theorem 5.1: By saying query complexity, do you mean the total samples needed in all three phases (sample complexity)?\n ", "summary_of_the_paper": "This paper proposes a novel formulation  to analyze the provable benefits of hierarchical RL algorithms. Based on this new formulation of hierarchical structures, they propose new algorithms to learn the latent hierarchy and apply the extracted hierarchy on the downstream tasks. Under several assumptions, they prove that their algorithms enjoy better regret or sample complexity bounds than brute-force methods.", "summary_of_the_review": "Overall, I believe that the formulation and algorithms are quite novel, and the hierarchy formulation covers many real situations in HRL. The paper can be further improved by adding more explanation about assumptions and main theorems. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NSoviWQ1SJk", "reviewer": "Reviewer_wF2a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points\n- paper provides several interesting theoretical results\n\nWeak points\n- the study is limited to a tabular setting\n- discussion on the relation to the existing methods can be improved\n\nWhile theoretical analysis is limited to the tabular setting, the paper presents interesting theoretical results for HRL in a meta-RL setting. \nAlthough I'm not the expert in the field of the theoretical analysis of HRL, the regret -guarantee for the meta-test setting seems novel.\nSimilarly, it is interesting to see that it is provable that the hierarchical oracle is implementable using the proposed algorithm. \n\nOn the other hand, I would like to see clearer connection to the existing methods. The methods for discovering the bottleneck states have been investigated for decades, and there are many ways to define the bottleneck states. I would like to encourage authors to discuss the connection between the exits found by the proposed algorithm and the bottleneck states found by the existing methods. For example, I would like to see the connection between the proto-value function and the exits found by the proposed algorithm or $\\alpha$-importance used in this study.\n\nMinor comments\n- Regarding the work by Wei et al. (2020), I think that it is not very appropriate to state like \"they focus on the reduction in regret when the learner already knows the decomposition.\" In my understanding, their work revealed the sample efficiency of HRL based on some quantities that characterize HRL and suggested what kind of structure should be used in HRL. Although this is just my opinion, please consider better way to phrase the position of the work.   ", "summary_of_the_paper": "This paper presents a theoretical analysis of hierarchical reinforcement learning in a meta-RL setting. This work is focused on a tabular  case. To quantify the importance of the state-action pair, $\\alpha$-importance is introduced. Subsequently, for exit coverage, optimistic imagination is introduced. The proposed algorithm discovers exits that characterize the hierarchical structure by leveraging these concepts. It is theoretically proved that the hierarchy oracle that reduces the complexity of exploration is implementable using the proposed algorithm. In addition, the regret bound of a hierarchical oracle is theoretically proved. ", "summary_of_the_review": "While theoretical analysis is limited to the tabular setting, the paper presents interesting theoretical results for HRL in a meta-RL setting. To further clarify the contribution of the work, I would like to encourage the authors to deepen the discussion on the relation to the previous studies.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3skyaR203oH", "reviewer": "Reviewer_ht9E", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As the authors themselves point out, while there has been much work in HRL and many methods proposed for how hierarchical structure might be recovered by an agent - there remain little to no formal guarantees (either for the discovery of the hierarchy, or for the performance on novel tasks using the hierarchy). The current paper might therefore constitute an important contribution to an at-present poorly understood area.\n\nI found the paper to be generally well written, albeit perhaps not so well presented. In particular, it seems that in order to get any traction with the problem the authors had to build up a large number of loosely justified assumptions building up to a result which is difficult to reason about given the afore mentioned setup. A clearer presentation might've been to _assume_ the existence of the latent hierarchy (or better yet a comparable structure more closely related to the existing literature) and then prove the regret bounds. And then separately (in a follow on paper or in the appendix) note that the assumed hierarchy is in fact recoverable.\n\nI have some concerns with the specific assumptions / constructions that the paper builds up en-route to it's final result:\n- the authors first introduce the notion of a 'latent hierarchy' defined, loosely speaking, in terms of entrance and exit states. While this definition is appealing in the rooms domain I am not convinced about its generality. I did however appreciate the author's attempts to at least somewhat address this question in their consideration of the Alchemy benchmark. Nevertheless this setup feels particularly geared towards domains with obvious bottle-neck states (and there are a number of other papers whose methods would recover the bottle necks at least in this domain). It's worth noting that this sort of condition doesn't lend itself naturally to a description of hierarchy in trivial open domains (like a 1d chain or empty room).\n- while some notion of 'coverage' is a typical requirement, I found the proposed 'optimistic imagining' largely unprincipled. The authors first defined the notion of /alpha-importance (ok), then noted that it doesn't work in the simple rooms domain and so propose an alternative definition that does work in the rooms domain... but it's generality remains completely unclear (my intuition is, again, that is probably unique to domains with single bottleneck states).\n- the authors propose an algorithm by which the latent hierarchy is recoverable, but it seems that in order to implement it (phase 2) requires that the agent explore in a reward-free way in order to determine the full transition dynamics. That is to say that the proposed algorithm indeed demonstrates that the latent hierarchy is recoverable, but not practically so. Given the paper's earlier assertion that the latent hierarchy they define suggests a natural set of options policies, I wonder whether the whole first part of the paper might be done away with, and the key result demonstrated under the assumption that the option policies are already provided? (in line with my earlier suggestion)\n- the key results establish regret bounds for an agent utilizing the latent hierarchy when performing novel tasks... but critically these tasks must themselves satisfy a number of additional conditions - in particular the tasks must be 'hierarchically compatible'. This would seem to exclude the vast majority of tasks (to see this in the rooms domain it seems it would suffice for one to just consider the set of tasks with |S|-choose-k terminal states with equal reward).\n\nAnd so, in summary, it seems that the key result is established only for a new definition of what constitutes a hierarchy, where the meta-RL tasks satisfy a bespoke definition of coverage, and is then applicable only to a small percentage of tasks (even in the single motivating domain).\n\nWith all that said, I think we desperately need more stable theoretical footing in HRL. I would encourage the authors to consider a reframing of their work addressing the separate contributions separately, and hopefully in more generally applicable ways.", "summary_of_the_paper": "In this paper the authors prove specific regret bounds for an RL agent utilizing a particular hierarchy when solving (some) novel tasks in the domain. The authors further demonstrate that the particular hierarchy considered is recoverable, and present a method for doing so. ", "summary_of_the_review": "An interesting paper proving regret bounds in a meta-learning HRL setting. However, in order to get any traction on the problem, the authors seem to need to make a large number of unprincipled assumptions (and introduce many novel definitions) such that the general interest / applicability of results is in questions.\n\nA reframing of the results in which the authors present the key contributions separately would likely result in a much more impactful contribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies meta-learning in hierarchical RL, where the unknown hierarchy is learned during meta-training and then applied to a test task. The authors propose an optimistic algorithm for solving this problem and analyze it. The main contribution of the paper is in the first end-to-end analysis.

This paper has three borderline reviews and one reject. Despite the differences in the scores, all reviewers share the same opinion. The idea is novel and very interesting. However, the algorithm and its analysis rely on many assumptions, many of which are introduced in this work and not properly discussed. Because of this, the paper needs a major revision and is rejected for now.
Decision: Reject