Year: 2021

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 hierarchylearning 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 sampleefficient 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.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has demonstrated tremendous successes in many domains (Schulman et 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., 2021). A promising approach to this problem is hierarchical reinforcement learning (HRL), which has seen continued interest due to its appealing biological basis. In its most basic form, HRL seeks to decompose tasks into a sequence of skills, each of which is easier to 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, a hierarchy-based 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 a single RL task (Nachum et al., 2019a; 2018). These approaches have been experimentally 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 rewardfree 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, Fruit & Lazaric (2017) provide a regret bound on learning with skills in the infinite-horizon average reward case. Meanwhile, in the meta-RL setting, Brunskill & Li (2014) considers the problem of finding and using skills in a continual learning setting and provides a 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 a 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 hierarchical structure induced by predetermined clustering and bottlenecks. Our contributions are as follows:
1. “Diversity conditions” ensuring hierarchy recovery. We develop natural optimismbased coverage conditions which ensure that bottlenecks embedded in the transition dynamics are detectable by solving provided meta-training tasks.
2. A tractable hierarchy-learning algorithm. We provide an algorithm that provably learns the latent hierarchy from interactions, assuming the coverage conditions above. Our method has sample complexity scaling as O(TKS) in the leading term compared to O(TS2A) for a brute-force method, where T are the number of tasks, S is the number of states, A is the number of actions, and K SA is the number of skills to 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-based and hierarchy-oblivious learners for a family of task distributions, corroborating prevailing intuitions regarding when/why HRL helps. In particular, hierarchy-based learners incur regret bounded by O( √ H2N) while
hierarchy-oblivious learners incur worst-case regret of at least O(2H/2 √ H2N).

heading: 2 NOTATION
text: We now introduce notation which we will use throughout the paper. We write [K] := {1, . . . ,K}. Furthermore, we use the standard notations O,Θ,Ω to denote orders of growth, and Õ, Θ̃, Ω̃ to indicate suppressed logarithmic factors. We use δ(x) to denote the Dirac delta measure on x.
We work with finite-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 × A × S → [0, 1] are the transition dynamics, r : S × A → [0, 1] is the reward function, and H is the horizon. We assume stationary dynamics unless otherwise noted, in which case P(h) is the dynamics at time step h. For constants relating to horizons, we will define [H] := {0, . . . ,H − 1}. Given a policy π : [H]× S → A, we define the value functions
V πh (s) := E [ H−1∑ k=h r(sk, ak) ∣∣∣∣∣ sh = s ] and Qπh(s, a) := E [ H−1∑ k=h r(sk, ak) ∣∣∣∣∣ (sh, ah) = (s, a) ]
where sk+1 ∼ P(· | sk, ak) and ak = πk(sk). Furthermore, we write V ∗ and Q∗ to denote optimal value functions obtained by maximizing over π (and are attained by the optimal policy π∗). When a learner plays π1, . . . , πN inM, we define its regret as
RegretN (M) := N∑ t=1 V ∗0 (s0)− V πt 0 (s0).
We use to denote a terminal state. We let τπ denote the (random) trajectory generated by π. For a state s and length-H trajectory τ , we write s ∈ τπ if sh = s for some h ∈ [H]. We define (s, a) ∈ τπ similarly. Finally, given an MDPM,M(2H) denotes a copy ofM with a doubled horizon.

heading: 3 SETTING
text: We work in the tabular meta-RL setting. The learner can access T meta-training MDPs {(S,A,Pt, rt, H)}t∈[T ] = {Mt}t∈[T ]. Note that Pt and rt both vary across tasks. We set S := |S| and A := |A|. After interacting with these tasks, the learner is presented with a meta-test MDP (S,A,PTg, rTg, H), where the learner seeks to minimize its regret. We assume, without loss of generality, that the MDPs have a shared starting state s0. 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 {Zc} be a partition of the state space S into clusters. We associate with each cluster Z a set of entrances Ent(Z) ⊆ Z and a set of exits Ext(Z) ⊆ Z × A. We say that the tasks have a latent hierarchy with respect to ({Zc} ,Ent(·),Ext(·)) if for any Zc:
(a) For any (s, a) ∈ (Zc×A)\Ext(Zc), Pt(· | s, a) is constant over t and supported on Zc.
(b) For any (s, a) ∈ Ext(Zc), there exists t, t′ with t 6= t′ such that Pt(· | s, a) 6= Pt′(· | s, a). Furthermore, Pt(· | s, a) is supported on ⋃ c Ent(Zc) for any t ∈ [T ].
Definition 3.1 partitions the shared state space of the MDPs into clusters such that (1) non-exit (s, a) dynamics do not change between the MDPs and (2) exits are bottlenecks between clusters.
Example 3.1 (Gated Four-Room). Figure 1 illustrates the gated four-room environment along with a sample task. The environment has a latent hierarchy with respect to the rooms outlined by colored gates (which can be open or closed). Entrances are colored aqua, while exits are marked by arrows.
Although we assume a single fixed starting state, we can model task-dependent initial states by appending a dummy state s0. A dummy action a0 then takes the agent to the starting state for the task. Observe that (s0, a0) is an exit, and therefore must transition to an entrance. y
To see 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 et al., 2021) is a recently proposed empirical benchmark for meta-RL, where the agent needs to place a stone in a series of potions to obtain some desired appearance, as illustrated in Figure 2. Dipping a stone into a potion traverses an edge (determined by the potion) in a 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 a latent hierarchy where dipping the
stone into any of the potions is an exit. Indeed, other than dipping the stone into a potion, all other actions (e.g., moving the stone around the room) have the same dynamics in all tasks. y
For convenience, we will define several relevant notions. First, for any clusterZ, we define its interior Z◦ := (Z×A)\Ext(Z). Furthermore, we let Ent(S) := ⋃ c Ent(Zc) denote the set of
all entrances and Ext(S) := ⋃ c Ext(Zc) the set of all exits. Finally, we define
K := |Ext(S)| L := |Ent(S)| M := sup
c |Ext(Zc)|
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 s0. During meta-training, we allow the agent to interact with the environments using an 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.

heading: 4 META-TRAINING ANALYSIS
text: 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:
1Image from Wang et al. (2021), extracted from a larger figure with no other modifications (License).
Definition 4.1 (β-dynamics separation). There exists β > 0 such that for any t, t′ ∈ [T ] and (s, a) ∈ Ext(S), Pt(· | s, a) 6= Pt′(· | s, a) =⇒ ‖Pt(· | s, a)− Pt′(· | s, a)‖TV ≥ β.
In defining β above, we ensure high-probability exit detection with Õ(S/β2) samples. Note that there is a brute-force approach to learning the underlying structure: one can learn Pt(· | s, a) for all (s, a) and t ∈ [T ], and iterate over (s, a) to check for changing dynamics. This can be done with query complexity Õ(TS2A/β2). However, under reasonable “coverage” assumptions outlined in the next section, this query cost can be lowered to Õ(TKS/β2).

heading: 4.1 DEFINING A NOTION OF COVERAGE
text: In supervised meta-learning, “diversity conditions” ensure that the meta-training tasks reveal the underlying latent structure (Tripuraneni et al., 2020; Du et al., 2020). We provide analogous conditions ensuring thatM1, . . . ,MT “cover” the latent hierarchy. Since solving maxπ V π(s0) requires fewer samples than learning P, we expect such conditions to provide sample complexity gains.
Visitation Probabilities and α-Importance. Minimally, exits should be visited by optimal policies of the meta-training tasks for coverage. We thus define the following notion:
Definition 4.2. Fix an MDPM = (S,A,P, r,H), and let (s, a) ∈ S × A. Construct a modified MDPM\ (s, a), where (s, a) brings the agent to a terminal state with no reward. Then, we say that (s, a) is α-important forM if VM\(s,a),∗0 (s0) < V M,∗ 0 (s0)− α.
The α-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 V π(s0) > 0 must visit the marked (s, a) pair with some probability. Therefore, (s, a) is V ∗0 (s0)-important. This suggests that high α-importance implies high visitation probability by nearoptimal policies. The following result, proven in Section A, formalizes this connection:
Lemma 4.1. If (s, a) is α-important for M, then for any policy π, V ∗(s0)− V π(s0) < ε implies that P ((s, a) ∈ τπ) > (α− ε)/H .
A Preliminary Coverage Assumption? Lemma 4.1 suggests a simple coverage condition: for any (s, a) ∈ Ext(S), assume that there exists t, t′ ∈ [T ] so that (s, a) is α-important for t and t′, and Pt(· | s, a) 6= Pt′(· | s, a). However, as the following example shows, this condition excludes natural settings:
Example 4.1. In Example 3.1, gates are either open or closed. For closed gates, the associated (s, a) pairs are unimportant for any goal. Thus, if (s, a) is α-important for some t, t′ ∈ [T ] with α > 0, then Pt(· | s, a) = Pt′(· | s, a), and no change in dynamics can be detected using π∗t and π∗t′ .
Figure 4 illustrates how the proposed condition fails in covering an exit marked with a black arrow. While (s, a) is unused by optimal policies in the first task, it is V ∗0 (s0)-important for the second. y
Optimistic Imagination as a Coverage Mechanism. The proposed assumption fails because there are cases where exits are only α-important in certain configurations (e.g., only open corridors are α-important in Example 3.1). In such cases, near-optimal policies only ever see one configuration of the dynamics for those exits and thus are insufficient for formalizing exit coverage.
As an alternative, consider the following hypothetical scenario in the context of Figure 4: an agent has solved both tasks, achieving optimal values V ∗1 and V ∗ 2 . Additionally, in the process of learning the second task, the agent has learned P2(· | ⇓). If the agent then relearns the first task while setting P̂1(· | ⇓) ← P2(· | ⇓), it would obtain a new value V̂1 V ∗1 . Thus, it can reasonably conclude that the black arrow must have been an exit. We illustrate this process in Figure 5, where πI is the optimal policy after “borrowing dynamics.” The learner could then run πI for exit detection.
We refer to the counterfactual reasoning about the dynamics used above as optimistic imagination. Unlike the preliminary condition, optimistic imagination only requires that an exit be important for one task and induce a value gap in another when borrowing dynamics – a weaker condition in many cases. With the above intuition in mind, we now present the main coverage assumption. Assumption 4.1 ((α, ζ)-coverage). Assume (Mt)t∈[T ] have a latent hierarchy with respect to ({Zk} ,Ent(·),Ext(·)). There exists α, ζ > 0 such that for any {(s1, a1), . . . , (sn, an)} ⊆ Ext(S),
(a) For any i ∈ [n], (si, ai) is α-important for some meta-training MDPMi.
(b) For someMt with t ∈ [T ], if we construct a new MDP M̄t = (S,A, P̄, rt, H) via P̄(· | s, a) = { PMi(· | s, a) (s, a) = (si, ai) PMt(· | s, a) otherwise ,
i.e. we replace (si, ai) dynamics with those fromMi, then V M̄t,∗(s0) > VMt,∗(s0) + ζ.
Informally, (α, ζ)-coverage ensures that optimistic imagination can borrow dynamics for unknown exits from other tasks to find a better optimal policy.2 Most reasonable task distributions satisfy (α, ζ)-coverage with enough tasks – we provide a heuristic explanation in the appendix.

heading: 4.2 ALGORITHM OUTLINE
text: In this section, we outline the algorithm that we use to detect exits. Our procedure can be naturally divided into three phases: a task-solving phase, a reward-free phase, and an exit detection phase. Throughout, we illustrate our steps in Figure 5, showing how Phases I and II allow the learner to find the imagined policy πI . The full details of the algorithm are provided in Section A.1.
4.2.1 PHASE I: TASK-SPECIFIC DYNAMICS LEARNING
First, we solveM1, . . . ,MT with UCBVI. Using UCBVI regret bounds from Azar et al. (2017) together with Lemma 4.1, we can guarantee that all α-important exits are sufficiently visited. Thus, during optimistic imagination, the learner would be able to borrow high-quality estimates of exit dynamics from other tasks. For example, a learner that has solved both tasks in Figure 4 can borrow open blue gate dynamics for use in the first task during optimistic imagination, as in Figure 6.

heading: 4.2.2 PHASE II: REWARD-FREE RL
text: In order to perform optimistic imagination, the learner also needs to simulate non-borrowed (s, a) dynamics. This is done by fully learning the dynamics of one of the tasks, proving a template P̂0. Learning P̂0 is achieved using reward-free RL (Jin et al., 2020).
2Incorporating the preliminary condition into Assumption 4.1 can further weaken the required task diversity. However, our algorithm handles this extension trivially, and thus we focus on optimistic imagination.
To understand the necessity of Phase II, note that in Figure 7, nearoptimal 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 learning 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 πI .

heading: 4.2.3 PHASE III: EXIT DETECTION
text: Having completed the previous two phases, the learner can use optimistic imagination to detect exits. In particular, we consider a modified value iteration method where the learner optimistically chooses dynamics estimates from Phases I and II to perform Bellman backups. This implicitly defines an MDP whose optimal value is at least as large as M̄t in Assumption 4.1, as M̄t would have been feasible for this process. Analogously with α-importance, this value gap implies that the corresponding
optimal policy πI for this new MDP must visit an (s, a) pair whose dynamics are borrowed. Therefore, by playing πI , the learner can determine a new exit.

heading: 4.3 META-TRAINING GUARANTEE
text: We now outline our main result for the algorithm in Section 4.2. We first define a “hierarchy oracle” that will be used in downstream tasks:
Definition 4.3 (Hierarchy oracle). Let S and F denote successful and failed termination, respectively. Consider any tuple (x, f, r, H̃) such that x ∈ Ent(S), f : Ext(S)→ { S , F }, r is a reward function, and H̃ ≤ H . Such tuple induces an MDPM(x, f, r, H̃) = (S ∪ { S , F } ,A,Pf , r, H̃) whose starting state is x and whose transition dynamics is given by
Pf (· | s, a) =  δ(f(s, a)) (s, a) ∈ Ext(S) δ(s) s ∈ { S , F } Pt(· | s, a) otherwise, for any t ∈ [T ].
An ε-suboptimal hierarchy oracle, when queried with any valid (x, f, r, H̃), returns an ε-suboptimal policy forM(x, f, r, H̃).
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 an agent that has a policy for reaching any exit from every entrance in any cluster. We emphasize that the learner does not need to know the states in the actual clusters themselves. Formally, for an entrance x in cluster Z and exit e ∈ Ext(Z), we can query the hierarchy oracle with (x,1 [(·, ·) = e] ,1 [· = 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.3
Our meta-training guarantee ensures that the hierarchy oracle is implementable:
Theorem 4.1 (Meta-training guarantee, informal). Under Assumption 4.1 and other assumptions in Section A.2, the data obtained from the algorithm in Section 4.2 allows for:
(a) implementing an ε-suboptimal hierarchy oracle, and
(b) determining, for every s ∈ Ent(S), the reachable exits in the cluster containing s,
simultaneously with probability at least 1− p. Furthermore, this is achieved with query complexity
Õ [ T ( KL
αmin(ζ, β)2 + KS αζ2 +
SA min(α, ζ)2 + KS2A α
) + S4A
min(ε, ζ) +
S2A
min(ε, ζ)2
] poly(H).
3As a side effect, the reachability of e from x can be determined from the predicted value for the prior query.
As a point of comparison, we have the following guarantee on brute-force hierarchy learning:
Theorem 4.2. The brute-force approach outlined in Section A.5, under Assumption 4.1(a), determines the set of exits with high probability and query complexity
Õ [ T ( S2A
αβ2 + SA α2 + S4A α
)] poly(H).
When α, β, and ζ are of the same order, we see that the proposed method incurs a smaller query complexity compared to a 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.

heading: 5 META-TEST ANALYSIS
text: In this section, we provide regret bounds on learning an MDPMTg using the hierarchy oracle. We first characterize a family of tasks for which one can achieve improved regret bounds. Furthermore, we provide sufficient conditions ensuring that using the hierarchy incurs low suboptimality.

heading: 5.1 ASSUMPTIONS
text: In this section, we outline the assumptions that we make to prove a regret bound on the meta-test task. Let MTg = (S,A,PTg, rTg, H) be the meta-test MDP. We assume that PTg(· | s, a) = Pt(· | s, a) for any (s, a) 6∈ Ext(S) and t ∈ [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 rTg is supported on (Z∗)◦ ∪ Ext(S). Furthermore, there exists an optimal policy π∗ satisfying
(a) Conditioned on sh ∈ Z∗, we have that (sh′ , ah′) 6∈ Ext(Z∗) for h′ ≥ h almost surely.
(b) The number of exits encountered by π∗ is bounded by Heff with probability ζ.
Hierarchical compatibility. Intuitively, Assumption 5.1 suggests that the task can be decomposed into a (Z∗)-searching phase and a within-(Z∗) phase. This decomposition captures the goalconditioned RL setting, which has been studied extensively in recent empirical works (Nachum et al., 2019a; Levy et al., 2018; Nachum et al., 2018). We expect the hierarchy oracle to reduce the complexity of exploration in both phases. Thus, these conditions ensure compatibility with the learned hierarchy.
Temporal Abstraction. Since a hierarchical learner makes decisions upon entering a new cluster (to decide which exit to use/whether to stay), hierarchical planning can reduce the planning horizon. Condition (b) quantifies this reduction. Note that in most practical settings, a learner that has access to good sub-skills can achieve low failure probability ζ even with modest values of Heff .
Hierarchical Suboptimality. Restricting the learner to 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 in this restricted class. We refer to this error as hierarchical suboptimality. We will show that hierarchical suboptimality is controllable with appropriate conditions on PT , which require the following notions of reaching times: Definition 5.1 (Reaching times). Fix a cluster Z, starting and goal states s, g ∈ Z, and planning horizon H̃ ≤ H . For any policy π, let (s0, s1, . . . , sH̃) be the states visited by π from s, where s0 = s. Then, we define
Tπ H̃
(s, g) := min { h ∈ { 0, . . . , H̃ } ∣∣∣ sh = g and sh′ ∈ Z for h′ < h} ∪ {L} T ∗ H̃ (s, g) := inf π E [ Tπ H̃ (s, g) ]
Tmin(s, g) := inf π min {h ∈ N | P (Tπ(s, g) = h) > 0} .
In words, Tπ H̃ (s, g) is the time π takes to reach a state g from s while remaining within the same cluster. By minimizing this quantity in expectation over all policies, we obtain T ∗
H̃ (s, g). Finally,
Tmin(s, g) is the minimum time for which it is possible to reach g from s. Definition 5.2 (Regular and low-variance dynamics). There exists α, β, γ > 0 such that for any cluster Z, states s, g ∈ Z, and horizon H̃ < H ,
(a) ((α, β)-unreliability) For any deterministic policy π with E[Tπ H̃ (s, g)] − T ∗ H̃ (s, g) < α, Tπ H̃ (s, g) has a sub-Gaussian upper tail with variance proxy β2E[Tπ H̃ (s, g)]2.
(b) (γ-goal-reaching suboptimality) T ∗ H̃ (s, g) ≤ (1 + γ)Tmin(s, g).
To understand (α, β)-unreliability, note that the condition only considers near-optimal deterministic policies. Therefore, (a) quantifies the randomness in Tπ(s, g) derived from the transition dynamics. On the other hand, γ-goal-reaching suboptimality quantifies the regularity of the dynamics, measuring whether near-optimal goal-reaching policies nearly achieve the optimal expected reaching time. Deterministic environments satisfies these conditions with α = ∞ 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: Assumption 5.2. For any cluster Z and s, g ∈ Z with s 6= g, Tmin(s, g) ≤ W . Furthermore, HeffW H .
Assumption 5.2 limits the length of the subtasks within each cluster. This is consistent with hierarchy-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(HeffW ) timesteps with high probability. Therefore, the condition HeffW H means that the task horizon is much longer than the minimum time required to complete the task, which often holds in practice.

heading: 5.2 META-TEST REGRET GUARANTEE
text: We note that Assumption 5.1 implies that the hierarchy oracle induces a “high-level” MDP. We have the following regret bound on applying EULER to this MDP: Theorem 5.1. We work under Assumptions 5.1 and 5.2. Furthermore, assume that the learner has access to an ε-suboptimal hierarchy oracle as guaranteed by Theorem 4.1, where ε < α. Then, a learner that applies the procedure in Section B.2 toMTg incurs regret
Regret(N) . √ H2HeffWLMN +Nεsubopt
εsubopt := (1 +Heff + β √ Heff)ε+ [ γHeff + β(1 + γ) √ Heff ] W + ζH.
with high probability.
Observe that the irreducible hierarchical suboptimality εsubopt (i.e. when ε = 0) tends to zero as γ, β, ζ → 0. In particular, environments with deterministic in-cluster dynamics do not incur hierarchical suboptimality. We prove this regret bound in Section B.
When does knowing the hierarchy help? Consider the binary tree environment in Figure 8. All of the leaves take the learner to a state with exits with probability 1/2, with the exception of a special leaf `∗ that does so with probability (1/2)+ε. Rewards can only be collected upon performing one of the exits (blue/purple). To achieve low regret, a learner has to quickly identity `∗ and the correct exit.
We consider the set of task distributions indexed by `∗ that randomize the reward-granting exit. Knowing the hierarchy amounts to knowing `∗, reducing the exploration problem to determining the
correct exit. However, a hierarchy-oblivious learner needs to explore the tree, leading to regret that is exponential in the tree depth. Formally, we have the following result:
Theorem 5.2. There exists a family of task distributions such that any hierarchy-oblivious learner incurs expected regret lower bounded by Ω(2W/2 √ H2N) on at least one task distribution. In contrast, a learner with access to a 0-suboptimal4 hierarchy oracle incurs regret bounded byO( √ H2N) 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. (2021) which demonstrate 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 RL to improved exploration.

heading: 6 RELATED WORK
text: Hierarchical reinforcement learning has been studied extensively (Sutton et al., 1999; Parr & Russell, 1998; Dietterich et al., 1998; Vezhnevets et al., 2017). 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 et al., 2002; Şimşek & Barto, 2004; Mann et al., 2014). Of particular note is the work of Frans et al. (2018), 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; 2018) defines options using proto-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 can improve the convergence rate of approximate value iteration.
More recent empirical work has considered the problem of hierarchy learning beyond the options framework in a wide variety of settings. Nachum et al. (2019a); Levy et al. (2018) provide algorithms for learning hierarchies based on goal-conditioned policies, reducing the learning problem to choosing subgoals. Nachum et al. (2018) considers a more general case when learned representations are used to map states to goals. Other works such as Co-Reyes et al. (2018); Eysenbach et al. (2018); Sharma et al. (2019) provide intrinsic objectives for learning hierarchies without rewards.
Closely related is the work of Wen et al. (2020), which introduces a similar latent structure on the state space, and provides sufficient conditions ensuring sample-efficient and tractable hierarchybased learning. However, their works hinges on prior knowledge of the latent structure, while a major focus of our work is discovering the structure itself from interactions.
Several heuristics have been proposed in prior work for the detection of useful bottlenecks in MDPs (McGovern & Barto, 2001; Menache et al., 2002; Şimşek & Barto, 2004; Şimşek et al., 2005). In particular, Şimşek & Barto (2004) define the notion of access states, states which maximize shortterm novelty of 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.

heading: 7 CONCLUSION
text: We have demonstrated that certain natural coverage conditions allow for learning useful hierarchies from tasks. Interesting future directions include analyzing hierarchy-based multi-task RL and extending 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 imposed on the learned hierarchy, such as cluster equivalences as in Wen et al. (2020).
4We use a 0-suboptimal hierarchy oracle for the separation result for ease of presentation.

heading: A META-TRAINING PROOFS

heading: A.1 ALGORITHM
text: In this section, we provide the complete algorithm for exit detection with optimistic imagination. For readability, we separate the three phases.

heading: A.1.1 PHASE I: TASK-SPECIFIC LEARNING
text: Algorithm 1 Exit Detection, Phase I: Task-Specific Learning
Require: TasksM1, . . . ,MT , NUCBVI UCBVI iterations, NTS policy samples, threshold NTSthresh 1: for all t ∈ [T ] do 2: Dt ← ∅. 3: Obtain policy set Φt ← UCBVI(Mt, NUCBVI). 4: for all n = 1, . . . , NTS do 5: Sample π ∼ Unif (Φt). 6: Play π inMt, add all (s, a, s′) pairs to Dt, get sum of rewards V̂ (n). 7: Form estimated dynamics model P̂t from Dt.
8: Form optimal value estimate V̂t ← 1
NTS NTS∑ n=1 V̂ (n)
9: Nt(s, a)← |{(x, u, x′) ∈ Dt | x = s, u = a}|. 10: for all (s, a) ∈ S ×A do 11: if Nt(s, a) < NTSthresh then P̂t(· | s, a)← 0. 12: return dynamics estimates P̂t and value estimates V̂t for t ∈ [T ].

heading: A.1.2 PHASE II: LEARNING REFERENCE DYNAMICS
text: Algorithm 2 Exit Detection, Phase II: Learning Reference Dynamics
Require: MDPM, NRFEULER Euler iterations, NRF policy samples 1: Set policy class Ψ← ∅ and dataset DRF ← ∅ 2: for all g ∈ S do 3: Create MDPMg fromM with horizon 2H and P ( | g, a) = 1 for any a. 4: rg(s, a)← 1 [s = g] for any (s, a) ∈ (S ∪ { })×A. 5: Φg ← EULER(Mg, rg, NEULERRF ) 6: πh(· | g)← Unif (A) for π ∈ Φg , h ∈ [H]. 7: Add policies in Φg to Ψ. 8: for all n = 1, . . . , NRF do 9: Sample π ∼ Unif (Ψ). 10: Play π inM and obtain trajectory (s0, a0, . . . , s2H). 11: Sample h ∼ Unif ([2H]) and add (sh, ah, sh+1) to DRF. 12: return reference dynamics P̂0 formed from DRF.

heading: A.1.3 PHASE III: EXIT DETECTION
text: Algorithm 3 Exit Detection, Phase III: Exit Detection
Require: NED, NEDthresh, NELEULER, NEL policy samples 1: Initialize ISEXIT[s, a]← FALSE for (s, a) ∈ S ×A. 2: while True do 3: for all t ∈ [T ] do 4: P̂0(· | s, a)← P̂t(· | s, a) for (s, a) ∈ S ×A with ISEXIT[s, a]. 5: Ṽ t, Q̃t ← OPTIMGVI(P̂0, (P̂1, . . . , P̂T ), rt, ISEXIT) 6: if Ṽ t0 (s0)− V̂t > (2/3)ζ then 7: Run greedy policy with respect to Q̃ NED times and form estimate P̂ for (s, a) pairs
visited at least N ′thresh times. 8: for all (s, a) ∈ S ×A with P̂(· | s, a) 6≡ 0 do 9: if (∃t ∈ [T ]) P̂t(· | s, a) 6≡ 0 and ∥∥∥P̂(· | s, a)− P̂t(· | s, a)∥∥∥ TV
> β/2 then 10: ISEXIT[s, a]← True 11: P̂t(· | s, a)← LEARN-EXIT(Mt, (s, a), NELEULER, NEL) for all t ∈ [T ] 12: if no new exits found after passing through T tasks since last found exit then 13: return ISEXIT
Algorithm 4 Borrowing Optimistically Across Tasks during Value Iteration (BOAT-VI)
1: procedure BOAT-VI(Reference dynamics P̂0, Estimated dynamics (P̂1, . . . , P̂T ), Reward function r, Table ISEXIT[S ×A]) 2: V̂H(s)← 0 for s ∈ S. 3: for all h = H − 1, . . . , 0 do 4: for all (s, a) ∈ S ×A do 5: if ISEXIT[s, a] then 6: Q̂h(s, a)← r(s, a) + P̂0V̂h+1(s, a) 7: else 8: Q̂h(s, a)← r(s, a) + maxt=0,...,T P̂tV̂h+1(s, a) 9: V̂h(s)← maxa Q̂h(s, a) for s ∈ S.
10: return V̂ , Q̂
Algorithm 5 Exit-learning subroutine
1: procedure LEARN-EXIT(MDPM, exit (s, a), NELEULER EULER iterations, NEL policy samples) 2: Create MDP M̃ fromM so P ( | s, a) = 1. 3: r̃(s′, a′)← 1 [(s′, a′) = (s, a)] for any (s′, a′) ∈ (S ∪ { })×A. 4: Ψ← EULER(M̃, r̃, NELEULER) 5: for all n = 1, . . . , NEL do 6: Sample π ∼ Unif (Ψ). 7: Play π inM and obtain trajectory (s0, a0, . . . , sH). 8: return reference dynamics P̂(· | s, a) formed from all trajectory data.

heading: A.2 OTHER ASSUMPTIONS AND RELEVANT DEFINITIONS
text: The remaining assumptions quantify the reachability of certain states. First, we have the following assumption, which in effect ensures that one can reach most states regardless of exit configuration in the meta-training tasks: Assumption A.1 (Non-limiting exit configurations). Let M = (S,A,P, H) be any reward-free environment with time-varying dynamics
P(h)(· | s, a) = Pt(h,s,a)(· | s, a) for some t : [H]× S ×A → [T ]. Then, there exists C > 1 such that for any s and t ∈ [T ],
max π PM(s ∈ τπ) ≤ C max π PMt(s ∈ τπ)
Intuitively, the assumption states that the reachability of a state in Mt would not be significantly improved even under an optimal configuration of the exits. Therefore, running reward-free RL on one of the meta-training tasks is sufficient for learning all non-exit (s, a) pairs. Remark A.1. We note that Assumption A.1 is restrictive in 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 a four-room environment where one of the rooms is blocked off for one of the tasks. However, this can be weakened to requiring that s be reachable in at least one of N arbitrarily chosen meta-training tasks. This would require that the algorithm run Phase II over N meta-training tasks, which results in a benign increase in the query complexity of the algorithm, so long as N is a constant much smaller than T . We focus on the N = 1 case for ease of presentation. y
To simplify the presentation of the rest of the assumptions, we recall the following definition of δ-significance in Jin et al. (2020): Definition A.1. A state s is δ-significant if maxπ P (s ∈ τπ) ≥ δ. Additionally, we say that (s, a) is δ-significant if s is δ-significant.
Note that we have modified the definition to remove the dependence on the timestep h ∈ [H]. This is because the dynamics are stationary, and thus it does not matter when s is visited in a trajectory.
Note that Assumption A.1 implies that a reachable entrance in one task is reachable in all tasks (i.e., is significant in the sense of Definition A.1). Therefore, we can quantify the minimum level of significance:5
Definition A.2 (ρ-significant entrances). For any s ∈ Ent(S), s is ρ-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 s ∈ Ent(Z), and exit (g, a) ∈ Ext(Z). Consider the reward-free environment Mt|Z = (Z,A,Pt|Z , H), where Pt|Z is the restriction of Pt to Z × A and the starting state is s. Then, if g has nonzero significance in Mt|Z for any t ∈ [T ], then it is ε0-significant.
The requirement that the assumption hold for any t ∈ [T ] is without loss of generality since non-exit dynamics do not change.
A.3 VERIFYING EXIT DETECTION
In this section, we demonstrate that the algorithm in Section A.1 can successfully discover Ext(S) with high probability. Formally, we have the following result: Theorem A.1 (Provable exit detection). Assume we run the algorithm in Section A.1 with the parameter choices given in Table 1. Then, with probability at least 1 − p, the algorithm returns an array ISEXIT satisfying:
{(s, a) | ISEXIT[s, a]} = Ext(S).
To prove this result, we proceed with a phase-by-phase analysis of the algorithm in Section A.1, which we then compile into proof of the desired result.
5One can weaken this assumption in a way that is compatible with the weakened form of Assumption A.1.

heading: A.3.1 PHASE I ANALYSIS
text: First, we prove that during Phase I, Algorithm 1 sufficiently visits all relevant exits and that all value estimates are sufficiently close. Formally, we have the following result:
Proposition A.1. Set
NTSthresh = Ω
[ Smax ( H4
ζ2 ,
1
β2
) log
SAHTNTS p
] ,
and consider the following procedure applied to one of the meta-training tasksMt:
1. UCBVI is run for
NUCBVI = Ω
( H2SA
min(α, ζ)2 log2
HSAT
p ) iterations, generating policies π(t)1 , . . . , π (t) NUCBVI .
2. The learner uniformly samples
NTS = Ω
( H
α NTSthresh +
H2
min(α, ζ)2 log
TK
p ) policies from the previous step, runs each policy inMt, and obtains a dataset of transitions Dt and returns V̂ (1), . . . , V̂ (NTS).
Then, with probability at least 1− p/3T ,
(a) We have the regret bound
V ∗0 (s0)− 1
NUCBVI NUCBVI∑ k=1 V π (t) k 0 (s0) < ζ 6 .
(b) The set of obtained returns satisfy∣∣∣∣∣ 1NTS NTS∑ i=1 V̂ (i) − 1 N NUCBVI∑ k=1 V π (t) k 0 (s0) ∣∣∣∣∣ < ζ6 . (c) If (s, a) is α-important forMt, then Nt(s, a) ≥ Nthresh.
(d) For every (s, a) pair such that Nt(s, a) ≥ Nthresh,
sup f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ < min( ζ 24H , βH 2 ) .
To prove the above result, we first recall the following regret bound on UCBVI, as proven by Azar et al. (2017):
Lemma A.1 (UCBVI regret bound). For sufficiently large N , with probability at least 1− p/6,
V ∗0 (s0)− 1
N N∑ k=1 V πk0 (s0) .
√ H2SA
N log
( HSAN
p
) .
As we will see later on, with our choice of NUCBVI, we 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 α-important exit is sufficiently visited, and thus their dynamics are sufficiently well-estimated.
Recall from the main text that the key step is demonstrating that a near-optimal policy for a task must visit its α-important states with non-negligible probability:
Lemma A.2. Let (s, a) be α-important forM, and let π be an ε-suboptimal policy for ε < α. Then,
P ((s, a) ∈ τπ) > 1
H (α− ε).
Proof. By α-importance,
α ≤ VM,∗0 (s0)− V M\(s,a),∗ 0 (s0) ≤ [ VM,∗0 (s0)− V M,π 0 (s0) ] + [ VM,π0 (s0)− V M\(s,a),∗ 0 (s0) ] ≤ [ VM,π0 (s0)− V M\(s,a),∗ 0 (s0) ] + ε.
Therefore, by applying Lemma A.17 and noting that {∆ ∩ τπ 6= ∅} = {(s, a) ∈ τπ}, we obtain the desired result.
Through the prior result, we can relate the UCBVI regret bound to the probability that a randomly chosen UCBVI-generated policy visits an α-important state:
Lemma A.3. Let (s, a) be α-important forM. Assume that UCBVI, when run for
NUCBVI = Ω
( H2SA
α2 log2
HSA
p ) iterations, generates policies π1, . . . , πN . If we sample π uniformly from these policies and let τ be the (random) trajectory generated by this randomly selected policy, then
P ((s, a) ∈ τ) > α 2H ,
conditioned on the high probability event in Lemma A.1.
Proof. By Lemma A.2, for any fixed π, we can write
P ((s, a) ∈ τπ) ≥ 1
H (α− [V ∗0 (s0)− V π0 (s0)])+,
where x+ = x1 [x > 0]. Then, since π is chosen randomly from the policies generated by UCBVI,
P ((s, a) ∈ τ) = 1 N N∑ k=1 P ((s, a) ∈ τπk) ≥ 1 HN N∑ k=1 (α− [V ∗0 (s0)− V πk 0 (s0)])+
≥ 1 H
[ α− 1
N N∑ k=1 V ∗0 (s0)− V πk 0 (s0)
] .
Therefore, by applying the regret bound in Lemma A.1 and the choice of N , we find that
P ((s, a) ∈ τ) > α 2H .
With all of the above intermediate results, we can now prove Proposition A.1.
Proof of Proposition A.1. Throughout this proof, we condition on the high-probability event in Lemma A.1, instantiated to occur with probability at least p/12T .
(a) By the choice of NUCBVI,
NUCBVI & H2SA
ζ2 log2
HSAT
p ,
and thus, we obtain the desired bound by plugging this value into the regret bound provided by Lemma A.1.
(b) Note that (V̂ (i)) are i.i.d., bounded in [0, H], and for any i ∈ [NTS], E [ ˆV (i) ] = 1
N N∑ k=1 V π (t) k 0 (s0).
Therefore, by applying Hoeffding’s inequality, with probability at least 1− p/12T ,∣∣∣∣∣ 1NTS NTS∑ i=1 V̂ (i) − 1 NUCBVI NUCBVI∑ k=1 V π (t) k 0 (s0) ∣∣∣∣∣ . √ H2 NTS log T p The result immediately follows from the fact that NTS & (H2/ζ2) log(T/p).
(c) The result simply follows from Lemma A.16 instantiated with failure probability 1 − p/12T , together with the choice of NTSthresh.
(d) With the choice of NUCBVI, the conclusion of Lemma A.1 can be made to hold with probability at least 1− p/24T . Fix an α-important exit (s, a) forMt, so that the probability that (s, a) is visited by the procedure is at least α/2H . By Lemma A.15, sampling NTS trajectories is sufficient to ensure that Nt(s, a) ≥ NTSthresh with probability at least 1− p/24TK. Therefore, by performing a union bound over the set of α-important exits (which contains at most K elements), Nt(s, a) ≥ NTSthresh for any α-important exit with probability at least 1− p/24T . Thus, overall, this event occurs with probability at 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.

heading: A.3.2 PHASE II ANALYSIS
text: In this section, we provide guarantees on the dataset DRF obtained by performing reward-free RL in Algorithm 2. Formally, we have the following high-probability result: Proposition A.2. For any δ > 0 and failure probability p, if Algorithm 2 is run with parameters
NRFEULER = O
( H2S2A
δ log3
HSA
p ) NRF = O [ max ( C
ζ2 ,
1
ρmin(ε, ε0)2
) H5S2A log A
p ]. Then, with probability at least 1− p/3:
(a) The distribution µ generating each sample in DRF satisfies
s ∈ S is δ-significant inM1(2H) =⇒ max a,π P ((s, a) ∈ τπ) µ(s, a) ≤ 4SAH.
(b) The estimated dynamics model P̂0 satisfies
max f :S→[0,H] max ν:S→A
E(s,a)∼µ [∣∣∣[(P̂− P)f] (s, a)∣∣∣2 1 [a = ν(s)]]
. min
( ζ2
4 · 242C , ρmin(ε, ε0)
2
16
) 1
H3SA .
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 2. Lemma A.4. For any g ∈ S, running EULER inMg forN iterations returnsN policies π1, . . . , πN satisfying the regret bound
V ∗0 (s0)− 1
N N∑ k=1 V πk0 (s0) .
√ 4V ∗0 (s0) SA
N log
SAHN p + S2AH2 N log3 SAHN p
with probability at least 1− p.
Proof. Observe that
1
NH N∑ k=1 Eπk (H−1∑ h=1 r(sh, ah)− V πk0 (s0) )2 ∣∣∣∣∣∣ s0 
≤ 2 NH N∑ k=1 Eπk (H−1∑ h=1 r(sh, ah) )2 + (V πk0 (s0)) 2 ∣∣∣∣∣∣ s0 
≤ 2 NH N∑ k=1 Eπk [ H−1∑ h=1 r(sh, ah) + V πk 0 (s0) ∣∣∣∣∣ s0 ]
≤ 4 H V ∗0 (s0).
Therefore, by applying the regret bounds from Zanette & Brunskill (2019), we obtain the regret bound
V ∗0 (s0)− 1
N N∑ k=1 V πk0 (s0) .
√ 4V ∗0 (s0) SA
N log
SAHN p + S2A2H2 N log3 SAHN p
with probability at least 1− p.
With the regret bound above, we now proceed to prove Proposition A.2.
Proof of Proposition A.2. (a) Fix a δ-significant g ∈ S . Note that for rg , V π0 (s0) = P (g ∈ τπ) for any policy π. Therefore, via the regret bound from Lemma A.4 and the choice of NRFEULER, we obtain
max π
P (g ∈ τπ)− 1
NRFEULER NRFEULER∑ k=1 P (g ∈ τπ) ≤ 1 2 max π P (g ∈ τπ)
=⇒ max π
P (g ∈ τπ) ≤ 2
NEULERRF ∑ π∈Φg P (g ∈ τπ)
with probability at least 1− p/2S. Now, since π(· | g) ∼ Unif (A), we have that for any a,
max π
P ((g, a) ∈ τπ) ≤ 2A
NEULERRF ∑ π∈Φg P ((g, a) ∈ τπ).
Finally, by applying the same argument above across all δ-significant g ∈ S , we have that for any (g, a),
max π P ((g, a) ∈ τπ) ≤ ∑ g∈S max a,π P ((g, a) ∈ τπ) ≤ 2SA
[ 1
SNEULERRF ∑ π∈Ψ P ((g, a) ∈ τπ)
]
with probability at least 1− p/2. To complete the proof of (a), observe that
1
SNEULERRF ∑ π∈Ψ 1 2H P ((g, a) ∈ τπ) ≤ µ(s, a) =⇒ max s,a,π P ((s, a) ∈ τπ) µ(s, a) ≤ 4SAH,
since conditioned on (g, a) ∈ τπ , 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. (2020), 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].

heading: A.3.3 PHASE III ANALYSIS
text: Having analyzed the previous two phases, we now show that Algorithm 3 successfully finds all exits during Phase III. As part of this, we prove the following guarantee:
Proposition A.3. Assume that Algorithm 3 is at Line 3, having just arrived at this step for the first time, or after finding a new exit. Let E = {(s, a) | ISEXIT[s, a]}. We assume:
(a) E ⊆ Ext(S).
(b) The high-probability events in Proposition A.1 (for any t ∈ [T ]) and Proposition A.2 (for δ ≤ ζ/24CH2S) both hold, providing estimators P̂0, P̂1, . . . , P̂T .
(c) For every (s, a) ∈ E and t ∈ [T ], we have access to an estimator P̂t(· | s, a) for Pt(· | s, a) satisfying
max f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ min( ζ 24H , βH 2 ) .
Then, if E = Ext(S), the algorithm terminates after passing through T tasks. Otherwise, if E 6= Ext(S), the following events hold simultaneously with probability at least 1− p/3K:
(a) For one of the next T tasks that the algorithm inspects, there exists at least one t ∈ [T ] such that ∣∣∣Ṽ t − V̂t∣∣∣ > 2
3 ζ.
(b) For the task in (a), running Lines 7–11 finds at least one (s, a) ∈ Ext(S) \ E (and only (s, a) pairs in this set), and learns an estimator P̂t(· | s, a) for Pt(· | s, a) satisfying
max f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ min( ζ 24H , βH 2 ) .
To prove the above result, we will consider the following special set of MDPs: Definition A.4 (Imaginable MDPs). Fix a taskMt. Furthermore, letE ⊆ Ext(S). For any function I : S ×A× [H]→ {0, . . . , T}, we can construct an associated MDPMI = (S,A,PI , rt, H) via
P(h)I (· | s, a) = PI(s,a,h)(· | s, a).
We define the set of imaginable MDPs to be the set Mt(E) to be the set of MDPs generated by any I satisfying
I(s, a, h) ∈ { {t} (s, a) ∈ E {0} ∪ { k ∣∣ Nk(s, a) ≥ Nthresh} otherwise .
Informally, Mt(E) is the set of obtainable MDPs by borrowing dynamics for (s, a) pairs that are not known to be exits. This set is of particular interest in our analysis, since BOAT-VI performs a maximization over the MDPs in this set: Lemma A.5 (Optimism). Assume the preconditions of Proposition A.3. Over the course of running Algorithm 4, the algorithm implicitly defines an index function I : S×A× [H]→ {0, . . . , T}. This function I satisfiesMI ∈Mt(E), andMI is a maximizer of
max M∈Mt(E) max π
V̂M,π0 (s0).
Proof. To see that MI ∈ Mt(E), note that if (s, a) ∈ E, then Ih(s, a) = t for any h ∈ [H]. Otherwise, note that although the maximum is over all indices, P̂k(s′ | s, a) = 0 for any s′ if Nt(s, a) < Nthresh. Therefore, since the estimated value function is always positive, the maximum is effectively only over any k with Nk(s, a) ≥ 0. Thus,MI ∈Mt(E). Now, we prove thatMI = M is a maximizer of the estimated value function, which we prove by induction. Let I ′ be another index function satisfyingM′ =MI′ ∈ Mt(E). Clearly, V̂M,∗H (s) = 0 ≤ V̂M
′,∗ H (s). Then, for any h ∈ [H] and (s, a),
Q̂M,∗h (s, a) = r(s, a) + P̂I(s,a,h)V̂ M,∗ h+1 (s, a)
≥ r(s, a) + P̂I′(s,a,h)V̂M,∗h+1 (s, a) ≥ r(s, a) + P̂I′(s,a,h)V̂ M′,∗ h+1 (s, a) = Q̂M ′,∗
h (s, a),
where the first inequality follows from the definition of I, and the second follows from the inductive hypothesis. Therefore, for any s,
V̂M,∗h (s) = maxa Q̂M,∗h (s, a) ≥ maxa Q̂ M′,∗ h (s, a) = V̂ M′,∗ h (s)
Thus, by induction, V̂M,∗0 (s0) ≥ V̂ M′,∗ 0 (s0). Since the argument applies for any I ′, we have shown the desired optimality result.
Note that M̄ is contained in Mt(E) via our assumed preconditions, suggesting that the BOATVI should find an MDP with a sufficiently over-optimistic value. However, the maximization above makes use of estimated dynamics, and thus we need to prove that every MDP in Mt(E) is sufficiently well-estimated. We now show that the preconditions of Proposition A.3 are sufficient for estimation. To this end, we recall the performance difference lemma: Lemma A.6 (Performance Difference). Fix two MDPs M = (S,A, r,P, H) and M′ = (S,A, r,P′, H). Then, for any policy π,
VM ′,π 0 (s0)− V M,π 0 (s0) = EM,π [ H−1∑ h=0 [(P′h − Ph)V̂h+1](sh, ah) ∣∣∣∣∣ s0 ] .
We now present the estimation result: Lemma A.7. For any π and t ∈ [T ], let VM,π0 (s0) be the value of a policy π inM ∈ Mt(E), and V̂M,π0 (s0) an estimate using available quantities from the preconditions of Proposition A.3. Then,
sup t∈[T ] sup π
M∈Mt(E) ∣∣∣V̂M,π0 (s0)− VM,π0 (s0)∣∣∣ < ζ6 . Proof. Fix a t ∈ [T ], M ∈ Mt(E) and policy π, with associated index function I. Lemma A.6 implies that∣∣∣V̂M,π0 (s0)− VM,π0 (s0)∣∣∣ ≤ H−1∑
h=0
EM,π [∣∣∣[(P̂(h) − P(h))V̂ πh+1] (sh, ah)∣∣∣]
≤ H−1∑ h=0 ∑ (s,a) ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a). We now define the following sets:
Uδ = {(s, a) is δ-insignificant forM1} Bh = {(s, a) | Ih(s, a) 6= 0} \ (E ∪ Uδ) Rh = {(s, a) | Ih(s, a) = 0} \ Uδ.
Note that Rh is estimated via reference dynamics from Phase II, while Bh is estimated using taskspecific dynamics from Phase I. Then, for a fixed h, we can decompose the inner sum above as∑
(s,a) ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤
∑ (s,a)∈E ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a)︸ ︷︷ ︸ =:(I)
+ ∑
(s,a)∈Rh ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a)︸ ︷︷ ︸ =:(II)
+ ∑
(s,a)∈Bh ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a)︸ ︷︷ ︸ =:(III)
+ ∑
(s,a)∈Uδ ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a)︸ ︷︷ ︸ =:(IV)
Note the inequality since E ∩ Uδ 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,
sup f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ ζ 24H .
Therefore, (I) = ∑
(s,a)∈E ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) =
∑ (s,a)∈E ∣∣∣[(P̂t − Pt)V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤ ζ24H ∑ (s,a)∈E PM,πh (s, a)
≤ ζ 24H .
Bounding (II): Reference Dynamics Error. Note that within Rh, Ph = P0, which we estimate via P̂0. Therefore, we bound the error resulting from using DRF to estimate P0. This part of the proof follows that of Jin et al. (2020). First, by Cauchy-Schwarz,
(II) = ∑
(s,a)∈Rh ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) =
∑ (s,a)∈Rh ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤
 ∑ (s,a)∈Rh ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 PM,πh (s, a) 1/2 .
Observe that V̂ πh+1 only depends on π through timesteps h+ 1, . . . ,H − 1. Therefore,∑ (s,a)∈Rh ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 PM,πh (s, a) ≤ max ν:S→A ∑ (s,a)∈Rh
∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 PM,πh (s)1 [ν(s) = a] . By applying Assumption A.1,
PM,πh (s) ≤ P M(s ∈ τπ) ≤ max π PM(s ∈ τπ) ≤ C max π PM1(s ∈ τπ)
≤ C max π PM1(2H)(s ∈ τπ) ≤ 4CHSAµ(s, a),
where we have applied Assumption 4.1 to move from M to M1. Substituting into the earlier expression,
max ν:S→A ∑ (s,a)∈Rh ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 PM,πh (s)1 [ν(s) = a] ≤ 4CHSA max
ν:S→A ∑ (s,a)∈Rh ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 1 [a = ν(s)]µ(s, a) ≤ 4CHSA max
ν:S→A ∑ s,a ∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 1 [a = ν(s)]µ(s, a) = 4CHSA max
ν:S→A E(s,a)∼µ [∣∣∣[(P̂0 − P0)V̂ πh+1] (s, a)∣∣∣2 1 [a = ν(s)]] . Thus, by applying the bound on the right-hand side provided by Proposition A.2,
(II) = ∑
(s,a)∈Rh ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤ ζ24H . Bounding (III): Error from Task-Specific Dynamics. Recall that on Bh, Ph = Pk for some k 6= 0. Thus, (III) is the error resulting from dynamics estimation in Algorithm 1. By following the same argument as that used to bound (I) and applying Proposition A.1, we find that∑
(s,a)∈Bh ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤ ζ24H . Bounding (IV): Error from δ-Insignificance. The remaining set of (s, a) pairs are those such that s is δ-insignificant inM1. Note that
(IV) = ∑
(s,a)∈Uδ ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤ H ∑ (s,a)∈Uδ PM,πh (s, a)
= H ∑ s∈Uδ PM,πh (s).
As a result,
PM,πh (s) ≤ P M(s ∈ τπ) ≤ max π PM(s ∈ τπ) ≤ C max π PM1(s ∈ τπ)
≤ Cδ.
By setting δ = ζ/24CH2S when performing reward-free RL in Phase II, we thus find that∑ (s,a)∈Uδ ∣∣∣[(P̂(h) − P(h))V̂ πh+1] (s, a)∣∣∣PM,πh (s, a) ≤ ζ24H . Concluding. By combining the bounds on (I) through (IV) and summing across h = 0, . . . ,H − 1, we find that ∣∣∣V̂0M,π(s0)− VM,π0 (s0)∣∣∣ ≤ ζ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 as not all exits have been found. This ensures that the exit-finding routine is triggered. Formally,
Lemma A.8. Assume the preconditions of Proposition A.3, and that E 6= Ext(S). Additionally, let t ∈ [T ] be the task with a ζ-overoptimistic value when borrowing exits Ext(S) \ E. Finally, let Ṽ t be the value function returned by Algorithm 4 onMt. Then,
Ṽ t0 (s0)− V̂t > 2
3 ζ.
Proof. Throughout this proof, we omit the timestep 0 and the initial state s0 for brevity. DefineM∗ and π∗ to be the maximizers of
max M∈Mt(E) max π
VM,π.
Furthermore, let M̄ be the imagined MDP guaranteed by Assumption 4.1 on top ofMt, such that V M̄,∗ > VMt,∗ + ζ. Then, we have that
V̂M,π − VMt,∗ = (V̂M,π − V̂M ∗,π∗)︸ ︷︷ ︸
≥0
+ (V M̂ ∗,π∗ − VM ∗,π∗)︸ ︷︷ ︸ >−ζ/6
+ (VM ∗,π∗ − V M̄,π̄)︸ ︷︷ ︸ ≥0 + (V M̄,π̄ − VMt,∗)︸ ︷︷ ︸ >ζ
> 5
6 ζ.
Furthermore,
VMt,∗ − V̂t = ( VMt,∗ − 1
NUCBVI NUCBVI∑ k=1 VMt,π (t) k ) ︸ ︷︷ ︸
≥0
+
( 1
NUCBVI NUCBVI∑ k=1 VMt,π (t) k − V̂t ) ︸ ︷︷ ︸
≥−ζ/6
,
where the first follows from optimality, while the second follows from Proposition A.2. Thus, putting the two inequalities together,
Ṽ t − V̂t > 2
3 ζ.
While the prior algorithm ensures that at least one of the tasks will trigger the exit condition, the actual task that triggers the condition may not be the same one invoked in the proof above. Nevertheless, we can prove that the trigger condition ensures that the algorithm will find a new exit.
Lemma A.9. Assume the preconditions of Proposition A.3, and that E 6= Ext(S). Let t ∈ [T ] be a task such that the value estimate Ṽ t returned by Algorithm 4 satisfies Ṽ t0 (s0) − V̂t > (2/3)ζ, and let π be the optimal policy for Ṽ . Then, there exists (s, a) ∈ Ext(S) \ E such that for some t′ 6= t,
(a) Nt′(s, a) ≥ NTSthresh and Pt(· | s, a) 6= Pt′(· | s, a).
(b) PMt((s, a) ∈ τπ) > ζ/6KH .
Proof. Let M be the implicit MDP defined by Algorithm 4 in the process of computing Ṽ t. We will prove a value gap betweenM andMt, which implies that π must visit state-action pairs with imagined dynamics.
Note that
VM,π0 (s0)− V Mt,∗ 0 (s0) = [ VM,π0 (s0)− Ṽ t0 (s0) ] ︸ ︷︷ ︸
≥−ζ/6
+ [ Ṽ t0 (s0)− V̂t ] ︸ ︷︷ ︸ ≥(2/3)ζ
+ [ V̂t −
1
NUCBVI NUCBVI∑ k=1 V Mt,π(t)k 0 (s0) ] ︸ ︷︷ ︸
≥−ζ/6
+
[ 1
NUCBVI NUCBVI∑ k=1 V Mt,π(t)k 0 (s0)− V Mt,∗ 0 (s0) ] ︸ ︷︷ ︸
≥−ζ/6
,
where the first inequality comes from Lemma A.7 and the last two inequalities come from Proposition A.1. Thus, VM,π0 (s0)− V Mt,∗ 0 (s0) ≥ ζ/6.
We now leverage this value gap to show that π must use some exit (s, a) whose dynamics in M have been modified from Mt with some probability. Formally, define the set ∆ ={ (s, a, h) ∣∣ Pt(· | s, a) 6= PMh (· | s, a)}. By construction, ∆ ⊆ Ext(S)×[H], and for any (s, a, h) ∈ ∆, there exists t′ such that Nt′(s, a) ≥ NTSthresh and Pt′(· | s, a) = PMh (· | s, a). Furthermore, ∆ must be non-empty, as otherwise, Pt = PMh for all h, and thus V M,π 0 (s0) ≤ V Mt,∗ 0 (s0), a contradiction. Therefore, by applying Lemma A.17, we find that
ζ
6H < PMt(τπ ∩∆ 6= ∅) ≤ ∑ {(s,a) | (s,a,h)∈∆} PMt((s, a) ∈ τπ),
which implies the desired result, as {(s, a) | (s, a, h) ∈ ∆} has at most K elements.
Because of Lemma A.9, we simply need to run π enough times and threshold at the number of samples needed to reliably determine which (s, a) pairs have an O(β) change in TV distance between tasks. Lemma A.10. We work in the setting of Lemma A.9. Set
NEDthresh = Ω
( S
β2 log SAHNED p
) and NED = Ω ( HK
ζ NEDthresh +
H2K2
ζ2 log
K
p
) .
Then, if we execute π withinMt NED and let N(s, a) be the number of times that (s, a) is played in this process, then with probability at least 1− p/6K, the following hold:
(a) For the (s, a) pair and task t′ in Lemma A.9, N(s, a) ≥ NEDthresh and∥∥∥P̂(· | s, a)− P̂t′(· | s, a)∥∥∥ TV > β 2 .
(b) For any (s, a) 6∈ Ext(S) with N(s, a) ≥ NEDthresh and t′ with Nt′(s, a) ≥ 0,∥∥∥P̂t(· | s, a)− P̂t′(· | s, a)∥∥∥ TV ≤ β 2 .
Proof. By the choice of NED and the lower bound PMt((s, a) ∈ τπ) > ζ/6KH from Lemma A.9, we guarantee that N(s, a) ≥ NEDthresh with probability at least 1 − p/12K. Furthermore, due to the choice of NEDthresh, with probability at least 1 − p/12K, we have that for any (s, a) with N(s, a) ≥ NEDthresh, ∥∥∥P̂(· | s, a)− Pt(· | s, a)∥∥∥
TV < β 4 ,
by applying Lemma A.16. We condition on these two events simultaneously for the rest of the proof, which occurs with probability at least 1− p/6K. We now prove each part separately. For brevity, we omit (s, a) wherever it is understood.
(a) By applying the triangle inequality, ‖Pt − Pt′‖TV ≤ ∥∥∥Pt − P̂∥∥∥ TV + ∥∥∥P̂− P̂t′∥∥∥ TV + ∥∥∥P̂t′ − Pt′∥∥∥ TV ≤ ∥∥∥P̂− P̂t′∥∥∥ TV + β 2 .
Therefore, by lower bounding the left-hand side using β-dynamics separation in Definition 4.1, we find that ∥∥∥P̂(· | s, a)− P̂t′(· | s, a)∥∥∥
TV > β 2 .
(b) The triangle inequality implies that∥∥∥P̂− P̂t′∥∥∥ TV ≤ ∥∥∥P̂− Pt∥∥∥
TV︸ ︷︷ ︸ ≤β/4 + ‖Pt − Pt′‖TV︸ ︷︷ ︸ =0
+ ∥∥∥Pt′ − P̂t′∥∥∥
TV︸ ︷︷ ︸ ≤β/4
≤ β 2 ,
where the bound on the first term is provided by Proposition A.1.
The prior result demonstrates that if the exit-finding condition is detected at any point by the algorithm, 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
NELthresh = Ω
[ Lmax ( H4
ζ2 ,
1
β2
) log SAHNELT
p ] Assume we run the exit-learning subroutine with
NELEULER = Ω
[ CS2AH3
α log3
( SAHT
p
)] and NEL = Ω ( CH
α NELthresh +
C2H2
α2 log
SAT
p
) .
in each of the tasks. Then, with probability at least 1− p/6K,
max f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ min( ζ 24H , βH 2 ) for every t ∈ [T ].
Proof. Fix a task t ∈ [T ]. Note that Assumption 4.1 implies that (s, a) is (α/H)-significant for some task. Then, (s, a) must be (α/CH)-significant for all of the other tasks by Assumption A.1.
By applying Lemma A.4, the set of policies found by the exit-learning subroutine for every task t ∈ [T ] satisfies
max π
P ((s, a) ∈ τπ)− 1
NELEULER NELEULER∑ k=1 P ((s, a) ∈ τπk)
. √ max π P ((s, a) ∈ τπ) SA
NELEULER log
SAHTNELEULER p + S2AH2 NELEULER log3 SAHTNELEULER p
with probability at least 1− p/18TK. By setting
NELEULER & CS2AH3
α log3
( HSAT
p
) ,
we thus find that for any t ∈ [T ],
α 2CH ≤ 1 2 max π P ((s, a) ∈ τπ) ≤ 1
NELEULER ∑ π∈Φt(s,a) P ((s, a) ∈ τπ) .
Note that the right-hand side is exactly the probability that the trajectory of a randomly chosen policy in Φt(s, a) contains (s, a) in the trajectory. Therefore, by applying Lemma A.15, playing
NEL = Ω
( CH2NELthresh
α + C2H4 α2 log SAT p ) is sufficient to guarantee that we obtain at least NELthresh samples from Pt(· | s, a) with probability at least 1 − p/18TK. Since (s, a) ∈ Ext(S), Pt(· | s, a) (and by extension, P̂t(· | s, a)) is supported on Ent(S). Therefore, we can modify the proof in Lemma A.16 so that with probability at least 1− p/18TK we get the bound
max f :S→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ max f :Ent(S)→[0,H] ∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ ≤ min ( ζ
24H , βH 2 ) with NELthresh depending linearly on L instead of S.
Note that by performing a union-bound, all events occur with probability at least 1 − p/6TK. Performing a second union-bound over all of the available tasks results in the desired failure probability.
At this point, we have effectively proven the second half of our Phase III guarantee. All that remains is to prove that if {(s, a) | ISEXIT[s, a]} = Ext(S), then the algorithm terminates without triggering the exit-finding condition.
Lemma A.12. Assume that E = {(s, a) | ISEXIT[s, a]} = Ext(S). Then, under the preconditions of Proposition A.3, every task satisfies ∣∣∣Ṽ t(s0)− V̂t∣∣∣ ≤ 2
3 ζ.
Proof. Fix a task t ∈ [T ]. Once E = Ext(S), then Mt(E) = {Mt}, since the only (s, a)-dynamics that can be substituted from other tasks are those of non-exits, which do not change between tasks. Therefore, by Lemma A.5, Ṽ t(s0) = V̂ M,∗ 0 (s0). Finally, by applying Lemma A.7, we thus find that
Ṽ t(s0)− V̂t = [ V̂M,∗0 (s0)− V M,∗ 0 (s0) ] + [ VM,∗0 (s0)− V̂t ] < ζ
3 .
The desired result follows since the argument holds for any task t.

heading: A.3.4 PROOF OF THEOREM A.1
text: In this section, we compile the guarantees provided by each of the three phases into a proof of Theorem A.1.
Proof of Theorem A.1. We condition on the following high-probability events:
(a) Proposition A.1 guarantees for allMt with t ∈ [T ].
(b) Proposition A.2.
Via a union-bound, this holds with probability at least 1− (2/3)p. To prove the theorem, we provide an induction-based analysis of Phase III. In particular, we will show that while E = {(s, a) | ISEXIT[s, a]} ( Ext(S), Phase III will add at least one state-action pair to E that belongs to Ext(S) \ E. Formally, let Fk denote the internal state of the algorithm after it has added k state-action pairs. Note that with k = 0, {(s, a) | ISEXIT[s, a]} in Fk is empty. Thus, Fk satisfies the preconditions of Proposition A.3, which in turn implies that the algorithm adds a new state-action pair in Ext(S) and sufficiently learns its dynamics for all tasks with probability at least 1− p/3K. In short, the internal state of the algorithm at time F1 also satisfies the preconditions of Proposition A.3 with probability at least 1− p/3K. More generally, Proposition A.3 ensures that if Fk satisfies the preconditions of Proposition A.3, then so does Fk+1. Therefore, with probability at least 1 − p/3, FK satisfies the preconditions of Proposition A.3, which necessarily implies that {(s, a) | ISEXIT[s, a]} = Ext(S) in FK , and thus the algorithm exits as desired. By performing a union bound, all this occurs with probability at least 1− p.

heading: A.4 PROVING THE META-TRAINING GUARANTEE
text: Having demonstrated that Ext(S) can be successfully recovered by interacting with the environment, we 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 M1, . . . ,MT have a latent hierarchy with respect to ({Zc} ,Ent(·),Ext(·)), and assume that these tasks satisfy the (α, ζ)-coverage condition in Assumption 4.1. Furthermore, we assume the additional assumptions in Section A.2. Then, by running the algorithm in Section A.1 with the parameters in Table 1, with probability at least 1− p, the collected data can be used to implement the following:
(a) An ε-suboptimal hierarchy oracle.
(b) A function AvExt(s) : Ent(S) → P(Ext(S)) such that, given s ∈ Ent(Zs), returns Ext(Zs).
The algorithm achieves both of these with query complexity
Õ
[ S4A
min(ρmin(ε, ε0), ζ/C) +
S2A
min(ρmin(ε, ε0)2, ζ2/C)
+ T
( SA
min(α, ζ)2 + KS ζβ2 + K2 ζ2 + CKS2A α +
CKL
αmax(ζ, β)2
)] poly(H).
A.4.1 IMPLEMENTING THE HIERARCHY ORACLE
We first show that we can implement the hierarchy oracle in this section. In particular, we have the following result:
Proposition A.4. LetM be the MDP corresponding to the index (x, f, r, H̃) as described in Definition 4.3. Then, given (x, f, r, H̃), we can form the following estimator for Pf :
P̂f (· | s, a) =  δ(f(s, a)) (s, a) ∈ Ext(S) δ(s) s = S or s = F P̂0(· | s, a) otherwise ,
where P̂0 is the estimator obtained from Phase II in Section A.1. Assuming that the high-probability event in Proposition A.2 holds for δ ≤ ρε/2SH2, value iteration using P̂f returns a policy π such that VM,∗0 (x)− V M,π 0 (x0) ≤ ε.
Throughout the rest of this section, we fix the tuple (x, f, r, H̃) and the corresponding MDP M. Furthermore, we write Z for the cluster containing x.
To prove Proposition A.4, we will show that M can be sufficiently simulated so 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 s∗ ∈ Z,[ max π PM1(x ∈ τπ) ] [ max π PM(s∗ ∈ τπ) ] ≤ max π PM1(2H)(s∗ ∈ τπ)
Proof. First, we note that there exists an MDP such that PM1(2H)(s∗ ∈ τπ) is the corresponding value function. In particular, modifyingM1(2H) so that any action from s∗ leads to a terminal state and defining r(s, a) = 1 [s = s∗] results in such an MDP.
Now, let πx and πs∗ be the policies achieving
max π PM1(x ∈ τπ) and max π PM(s∗ ∈ τπ),
respectively. Consider the concatenation of πx and πs∗ into a history-dependent policy that runs πx until the agent reaches s, and switches to πs∗ thereafter. This policy reaches s with probability at least [
max π
PM1(x ∈ τπ) ] [
max π
PM(s∗ ∈ τπ) ] .
within the modified MDP described above. Since the optimal value among all policies is achieved by a history-independent policy, we 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 M1 within a 2H horizon. Therefore, performing rewardfree RL with horizon 2H during Phase II provides coverage over all clusters. Now, we prove the simulation result.
Lemma A.14. Assume that the Phase II guarantee in Proposition A.2 is instantiated for δ ≤ ρε/4SH2. Then, if V π is the value of π under M, and V̂ π is its corresponding estimate under P̂f , then ∣∣∣V̂ π0 (x)− V π0 (x)∣∣∣ ≤ ε2 . Proof. The proof follows similarly to that of Lemma A.7. By the performance difference lemma,
∣∣∣V̂ π0 (s)− V π0 (s)∣∣∣ ≤ H̃−1∑ h=0 EM,π [∣∣∣[(P̂f − Pf) V̂ πh+1] (sh, ah)∣∣∣]
≤ H̃−1∑ h=0 ∑ (s,a) ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a). Observe that if s ∈ S \ Z, Pπh (s, a) = 0 for any π. Furthermore, since the dynamics within { S , F } are known, (P̂f − Pf )V̂ πh+1(s, a) = 0 for s ∈ { S , F }. Therefore, we can restrict the sum to be over Z ×A. Now, let Zδ denote the set of δ-significant (s, a) pairs in Z×A from x, for some δ to be determined. For a fixed h ∈ [H̃], we can decompose the inner sum as∑ (s,a)
∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a) ≤
∑ (s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a)︸ ︷︷ ︸ (I) + ∑ (s,a)6∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a)︸ ︷︷ ︸ (II) .
Bounding (II): Error from δ-Insignificance By the definition of δ-significance,
(II) = ∑
(s,a) 6∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a) ≤ H ∑ s 6∈Zδ Pπh (s) ≤ HSδ ≤ ε 4H ,
where the last inequality follows from setting δ = ε/4SH2.
Bounding (I): Reference Dynamics Error. By the Cauchy-Schwarz inequality,
(I) = ∑
(s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣Pπh (s, a) ≤
 ∑ (s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 Pπh (s, a) 1/2 .
Then, ∑ (s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 Pπh (s, a) ≤ max ν:S→A ∑ (s,a)∈Zδ
∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 Pπh (s)1 [ν(s) = a] . Since x is ρ-significant inM1(2H) by Definition A.2, Lemma A.13 together with δ-significance in M implies ρδ-significance inM1(2H). Therefore,
Pπh (s) ≤ max π
PM(s ∈ τπ) ≤ 1
ρ max π
PM1(2H)(s ∈ τπ) ≤ 4HSA
ρ µ(s, a),
where the last inequality follows by part (a) of the Phase II guarantee in Proposition A.2. Substituting into the prior expression,
max ν:S→A ∑ (s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 Pπh (s)1 [ν(s) = a] ≤ 4HSA
ρ max ν:S→A ∑ (s,a)∈Zδ ∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 1 [ν(s) = a]µ(s, a) ≤ 4HSA
ρ max ν:S→A
E(s,a)∼µ [∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 1 [ν(s) = a]] .
Thus by applying part (b) of the Phase II guarantee in Proposition A.2, we have that
(I) ≤
√ 4HSA
ρ max ν:S→A E(s,a)∼µ [∣∣∣[(P̂f − Pf) V̂ πh+1] (s, a)∣∣∣2 1 [ν(s) = a]] ≤ ε4H .
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 P̂f , which achieves the maximal value in the corresponding MDP. Then, by Lemma A.14
V ∗0 (x)− V π0 (x) ≤ [ V ∗0 (s0)− V̂ π ∗ 0 (s0) ]
︸ ︷︷ ︸ ≤ε/2
+ [ V̂ π ∗ 0 (s0)− V̂ π̂0 (s0) ]
︸ ︷︷ ︸ ≤0
+ [ V̂ π̂0 (s0)− V π̂0 (s0) ] ︸ ︷︷ ︸
≤ε/2
≤ ε.

heading: A.4.2 DETERMINING AVAILABLE EXITS
text: 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 ε-suboptimal hierarchy oracle from the previous section and that the guarantee in Theorem A.1 holds. Then, we can implement the function AvExt(s) : Ent(S) → P(Ext(S)) which, given s ∈ Ent(Zs), returns the subset of Ext(Zs) that is reachable from s.
Proof. Fix an input x ∈ Ent(S), which we assume belongs to some cluster Zx. It suffices to demonstrate that we can implement 1 [e ∈ Zx] for any fixed e ∈ Ent(S). Define
fe(s, a) = { S (s, a) = e F otherwise
and re(s, a) = 1 [(s, a) = e]. By Definition A.3, the MDP M corresponding to the tuple (x, fe, re, H) has optimal value V ∗ = ε01 [e ∈ Zx ∧ e reachable from x]. Additionally, by Lemma A.14, |V π0 (s) − V̂ π0 (x)| ≤ ε/2. We now proceed by cases. If e 6∈ Zx or e is not reachable from x, then V π0 (x) = 0 for any policy π, and thus value iteration can only find a policy π with V̂ π0 (x) ≤ ε0/3. Otherwise, for e ∈ Zx, V ∗0 (x) = ε0, and thus value iteration necessarily must find a π with V̂ π0 (x) ≥ 2ε0/3. Putting these together, if V̂ is the optimal estimated value inM, then
1 [e ∈ Zx] = 1 [ V̂ ≥ 2
3 ε0
] .
Note that this is implementable for all e ∈ Ext(S) (and returns a subset of Ext(Zx) for the query above) since the set of exits are already known.

heading: A.4.3 FINALIZING THE GUARANTEE: QUERY COMPLEXITY
text: In this section, we finalize the proof of the meta-training guarantee by computing the query complexity.
Proof of Theorem A.2. As demonstrated by Proposition A.4 and Proposition A.5, running the algorithm in Section A.1 with the parameters in Table 1 provides the desired guarantees with probability at least 1− 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 (NUCBVI +NTS) +N RF EULER +NRF +KNED + TK(N EL EULER +NEL) ] .
Ignoring terms that do not depend on T or ε, we obtain the claim.

heading: A.5 BRUTE-FORCE LEARNING OF THE HIEARCHY
text: Theorem A.3. Assume that Algorithm 6 is run with parameters satisfying
NEULER = Ω
( CH3S2A
α log3
SAHT
p ) and
Nthresh = Ω
( S
β2 log
SAHNT
p
) and N = Ω ( CH
α Nthresh +
C2H2
α2 log
SAT
p ) Then, the set returned by the algorithm is exactly Ext(S) with probability at least 1 − p. Furthermore, the algorithm achieves this result with query complexity
Õ [ T ( CS4A
α + CS2A αβ2
)] poly(H).
Algorithm 6 Brute-force learning of the latent hierarchy. 1: procedure LEARNHIERARCHY((M1, . . . ,MT ), NEULER iterations, N policy samples, thresh-
old Nthresh) 2: for all t ∈ [T ], s ∈ S do 3: Create MDPMst so P ( | s, a) = 1 for any a. 4: r̃s(s′, a′)← 1 [s′ = s]. 5: Ψst ← EULER(Mst , r,NEULER) 6: for all t ∈ [T ], s ∈ S, a ∈ A do 7: Modify policies in Ψst to play a on s. 8: for all n ∈ [N ] do 9: Sample π ∼ Unif (Ψst ).
10: Play π inMt, collect sample (s, a, s′n) if (s, a) is encountered 11: Nt(s, a)← number of times (s, a) is encountered above. 12: P̂t(· | s, a)← estimate of (s, a) dynamics in t. 13: return { (s, a) ∣∣∣ (∃t 6= t′)∥∥∥P̂t − P̂t′∥∥∥ TV > β/2,min(Nt(s, a), Nt′(s, a)) ≥ Nthresh } .
Proof. For any (s, a) ∈ Ext(S), Lemma A.2 implies that s is α/H-significant for some task t ∈ [T ]. Therefore, s is α/CH-significant for any task t ∈ [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 at least 1− p/3T , the choice of NEULER implies
1
NEULER ∑ π∈Ψst PMt(s ∈ τπ) ≥ α 2CH
for any exit (s, a) ∈ Ext(S) and a fixed task t ∈ [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 (α/CH)-significant (s, a) pair, sampling from Ψst at least N times guarantees that with probability at least 1 − p/3SAT , Nt(s, a) ≥ Nthresh. Therefore, once again performing the necessary union-bound, we obtain the same result uniformly over any (α/CH)-significant (s, a) and t ∈ [T ] with probability at least 1− p/3. Finally, for a fixed (s, a) and t, the estimator for Pt(· | s, a) satisfies the property that when N(s, a) > 0,∥∥∥P̂t(· | s, a)− Pt(· | s, a)∥∥∥
TV ≤
√ H2S
Nt(s, a) log
SAHNT
p +
HS
Nt(s, a) log
SAHNT
p
with probability at least 1−p/3SAT , using an argument similar to that used in Lemma A.16. Again, by a union bound, the same guarantee holds for any (s, a) and t ∈ [T ]. In particular, for any (s, a) with Nt(s, a) ≥ Nthresh, ∥∥∥P̂t(· | s, a)− Pt(· | s, a)∥∥∥
TV ≤ β 4 .
Therefore, by a similar argument to Lemma A.10, the following are true:
(a) If (s, a) ∈ Ext(S), then there exists t, t′ for which∥∥∥P̂t(· | s, a)− P̂t′(· | s, a)∥∥∥ TV > β 2 .
(b) If (s, a) 6∈ Ext(S), then for any t 6= t′ with Nt(s, a), Nt′(s, a) ≥ Nthresh,∥∥∥P̂t(· | s, a)− P̂t(· | s, a)∥∥∥ TV ≤ β 2 ,
Putting everything together, we see that the set returned by Algorithm 6 is exactly Ext(S), with probability at least 1− p.

heading: A.6 TECHNICAL LEMMAS
text: Lemma A.15. Let X1, . . . , XM be i.i.d. Ber (p) random variables. Then, if
M = Ω
( N
p +
1
p2 log
1
δ
) ,
then with probability at least 1− δ, M∑ i=1 1 [Xi = 1] ≥ N.
Proof. By applying Hoeffding’s inequality,
P ( M∑ i=1 1 [Xi = 1] < N ) = P ( 1 M M∑ i=1 1 [Xi = 1]− p < N M − p )
= P
( 1
M M∑ i=1 1 [Xi = 0]− (1− p) > p− N M
)
≤ exp [ −2M ( p− N
M )2] Setting the final expression to the failure probability δ and solving, we obtain the quadratic inequality
p2M2 − ( 2Np+ 1
2 log
1
δ
) M +N2 ≥ 0.
Finally, via solving this inequality for M , we find that
M ≥ 2N p + 1 2p2 log 1 δ
is sufficient to guarantee the desired event with failure probability δ, as desired.
Lemma A.16 (Dynamics estimation error bound). Fix a policy π, MDP with stationary dynamics M = (S,A,P, r,H), and N ∈ N. Assume that π is played N times inM, and all transitions are used to form an estimator P̂(· | s, a) using empirical averages. For any (s, a) ∈ S ×A, let N(s, a) be the number of times (s, a) is encountered in this process. Then, with probability at least 1 − p, any (s, a) with N(s, a) > 0 satisfies
sup f :S→[0,H] ∣∣∣[(P̂− P) f] (s, a)∣∣∣ ≤√ H2S N(s, a) log SAHN p + HS N(s, a) log SAHN p .
Proof. Assume that the obtained samples are given by {(sk, ak, s′k) | k ∈ [HN ]}, so that (sHn+r, aHn+r, s ′ Hn+r+1) is the r
th time step in the nth execution of π inM for any 0 ≤ n ≤ N−1 and 0 ≤ r ≤ H − 1. Fix any (s, a) ∈ S × A, and assume that (s(j), a(j), s′(j)) is the j
th sample from P(· | s, a). Furthermore, let mj(s, a) denote the index at which the jth sample is obtained. We claim that for any s∗ ∈ S and 0 < M ≤ HT ,∣∣∣∣∣∣ 1M M∑ j=1 1 [mj(s, a) ≤ HT ] ( 1 [ s′(j) = s ∗ ] − P(s∗ | s, a)
)∣∣∣∣∣∣ ≤ √
P(s′ | s, a) M log S δ + 1 M log S δ .
Let Fi be defined as the σ-algebra induced by the set of random variables{( mj(a),1 [ s′(j) = s ∗ ]) ∣∣∣ j ≤ i} .
Clearly, (Fi) is a filtration such that the jth term in the sum above is measurable with respect to Fj . Furthermore, observe that
E [ 1 [mj(s, a) ≤ HT ] ( 1 [ s′(j) = s ∗ ] − P(s∗ | s, a) ) ∣∣∣ Fj−1] = E [ 1 [ s′(j) = s ∗ ] − P(s∗ | s, a)
∣∣∣ Fj−1,mj(s, a) ≤ HT]P (mj(s, a) ≤ HT ) = 0.
Therefore, the random variables in the sum forms martingale difference sequence. Furthermore, the sequence is bounded in [−1, 1], and satisfies
Var [ 1 [mj(s, a) ≤ HT ] ( 1 [ s′(j) = s ∗ ] − P(s∗ | s, a) ) ∣∣∣ Fj−1] = E [ Var [ 1 [ s′(j) = s ∗ ] − P(s∗ | s, a)
∣∣∣ Fj−1,mj(s, a) ≤ HT] ∣∣∣ Fj−1] ≤ P(s∗ | s, a).
Therefore, by applying Azuma-Bernstein, we have that∣∣∣∣∣∣ 1M M∑ j=1 1 [mj(s, a) ≤ HT ] ( 1 [ s′(j) = s ∗ ] − P(s∗ | s, a) )∣∣∣∣∣∣ ≤ √
2P(s′ | s, a) M log SAHN δ + 2 M log SAHN δ .
with probability at least 1− p/SAHN . By applying a union bound on (s, a, s∗) and M , we thus have that with probability at least 1− p,∣∣∣∣∣∣ 1M M∑ j=1 1 [mj(s, a) ≤ HT ] ( 1 [ s′(j) = s ∗ ] − P(s∗ | s, a)
)∣∣∣∣∣∣ ≤ √
2P(s′ | s, a) M log SAHN δ + 2 M log SAHN δ
holds for any (s, a, s∗) and M . Conditioned on this event, we thus have that for any (s, a) with N(s, a) > 0,∥∥∥P̂t(· | s, a)− Pt(· | s, a)∥∥∥
TV =
1
2 ∑ s′∈S ∣∣∣P̂t(s′ | s, a)− Pt(s′ | s, a)∣∣∣ . ∑ s′∈S √ P(s′ | s, a) N(s, a) log SAHN δ + S N(s, a) log SAHN δ
.
√ S
N(s, a) log
SAHN
δ +
S
N(s, a) log
SAHN
δ .
The final result follows simply by noting that∣∣∣[(P̂t − Pt)f] (s, a)∣∣∣ . ∥∥∥P̂t(· | s, a)− Pt(· | s, a)∥∥∥ TV ‖f‖∞ .
Lemma A.17. Fix two MDPsM = (S,A,P, r,H) andM′ = (S,A,P′, r,H). Let ∆ denote the subset of S ×A× [H] for which Ph(· | s, a) 6= P′h(· | s, a). Then, for any policy π,
VM ′,π 0 (s0)− V M,∗ 0 (s0) > ρ =⇒ PM (τπ ∩∆ 6= ∅) = PM′ (τπ ∩∆ 6= ∅) > ρ
H .
Proof. Write q = PM′ (τπ ∩∆ 6= ∅). Note that VM ′,π 0 (s0) can be decomposed as
VM ′,π 0 (s0) = qEM′ [ H−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩∆ 6= ∅ ]
+ (1− q)EM′ [ H−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩∆ = ∅ ]
≤ qH + (1− q)EM′ [ H−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩∆ = ∅ ] .
Since P and P′ agree on (S ×A× [H]) \∆, the dynamics ofM andM′ agree up until π performs an action in ∆, and thus
PM (τπ ∩∆ 6= ∅) = PM′ (τπ ∩∆ 6= ∅)
EM [ H−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩∆ = ∅ ] = EM′ [ H−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩∆ = ∅ ]
Furthermore,
(1− q)E [ h−1∑ h=0 rh(sh, ah) ∣∣∣∣∣ τπ ∩ δ = ∅ ] ≤ VM,π0 (s0) ≤ V M,∗ 0 (s0).
Putting everything together,
VM ′,π 0 (s0) ≤ qH + V M,∗ 0 (s0) =⇒ q > ρ
H .

heading: A.7 WHY SHOULD OPTIMISTIC IMAGINATION HOLD?
text: In this section, we provide a heuristic explanation as for why optimistic imagination can be expected to hold in most scenarios for which Definition 3.1 holds.
Recall from the main text that if an exit e satisfies the preliminary coverage condition, then e can be detected using only Phase I data. Therefore, we can restrict our discussion of Assumption 4.1 to subsets of exits that only have nonzero importance for a task t if Pt(· | e) is some distribution de. In other words, we can only guarantee that near-optimal policies for the source tasks observe de. We will provide a heuristic reason as to why we can then expect to find an MDP such that condition (b) of Assumption 4.1 holds for such a subset S.
State visitation measures. Recall that the value function in an MDP with a stationary reward function is given by
VM,π0 (s0) = H−1∑ h=0 EM,π [r(sh, ah) | s0] .
Now, if we assume that the reward is only a function of the state (as in goal-conditioned RL), and view r as a vector in R|S|, then we can write VM,π0 (s0) = Hρ>M,πr, where
ρM,π(s) = 1
H H−1∑ h=0 PM,π(sh = s | s0).
That is, ρM,π is the state visitation measure of π withinM with horizon H . This geometric viewpoint was explored by Eysenbach et al. (2021) in the context of unsupervised RL in the discounted infinite-horizon setting. We note that for any fixedM, {ρM,π} is a convex subset of the probability simplex.
Constructing the desired reward function. Let M be any source task such that the set T ={ e ∈ S ∣∣ PM(· | e) 6= de} is non-empty. Furthermore, let M̃ be the corresponding MDP described in Assumption 4.1(b) after borrowing dynamics, so that
P̃(· | s, a) = { P(· | s, a) (s, a) 6∈ S d(s,a) otherwise
is the dynamics of M̃. Since ∥∥PM(· | e)− de∥∥TV > β for any e ∈ S, heuristically, we expect the following to be true: Assumption A.2. There exists a π∗ such that ρM̃,π∗ 6∈ {ρM,π}.
Stated less formally, we expect there to be states that π∗ can reach better in M̃ compared to any policy inM. Example A.1. In the four-room example, this intuition is captured by the fact that the agent can spend more time in states past open gates compared to if they were closed. y
Under Assumption A.2 above, since {ρM,π} is convex, we can find a reward direction separating {ρM,π} and ρM̃,π∗ , or more formally,
ρ>M̃,π∗r > sup π ρ>M̃,π∗r.
Then, the MDP M with reward function r satisfies the desired condition in Assumption 4.1(b). Thus, under Assumption A.2, the coverage condition can indeed hold with sufficiently diverse source tasks.

heading: B META-TEST PROOFS
text: We now provide an analysis of the regret incurred by a learner using an 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, we fix an optimal π∗ satisfying the conditions of Assumption 5.1. Furthermore, we assume that we have access to a hierarchy oracle that provides ε-suboptimal policies as defined in Definition 4.3.

heading: B.1 USING THE HIERARCHY ORACLE
text: In this section, we show that the hierarchy oracle can be used to implement two useful behaviors: (1) reaching exits and (2) behaving optimally within a cluster.

heading: B.1.1 NEAR-OPTIMAL GOAL REACHING
text: Assume that the agent is currently at a state z ∈ {s0}∪Ent(S) at time step h, and intends to exit the current cluster Z via exit g = (s∗, a∗) ∈ Ext(Z). We obtain a policy implementing the high-level intent as follows:
(1) Define the termination for any (s, a) ∈ Ext(S) as:
fg(s, a) := { S (s, a) = g F otherwise
(2) Define reward as r S (s, a) := 1 [s = S ]
(3) Provide (z, fg, r S , H − h) to the hierarchy oracle and obtain a policy πz,g,h.
For simplicity, we will write T hierH−h(z, g) for T πz,g,h H−h (z, g) throughout our analysis. The following proposition quantifies the performance of the obtained policy:
Proposition B.1. T hier satisfies the following inequality:
E [ T hierH−h(z, g) ] ≤ T ∗H−h(z, g) + ε.
Proof. Due to the definition of Pfg and r, observe that for any π,
V π0 (z) = E [ H−h∑ h=0 r(sh, ah) ∣∣∣∣∣ s0 = z ] = (H − h)− E [ TπH−h(z, g) ] .
Therefore,
(H − h)− T ∗H−h(z, g)− ε ≤ (H − h)− E [ T hierH−h(z, g) ] =⇒ E [ T hierH−h(z, g) ] ≤ T ∗H−h(z, e) + ε.

heading: B.1.2 NEAR-OPTIMAL WITHIN-CLUSTER BEHAVIOR
text: Assume that the agent is currently at a state z ∈ {s0} ∪ Ent(S) at time h, and intends to remain in the current cluster Z while maximizing a given reward function r. We obtain a policy for this high-level intent as follows:
(1) Define transition dynamics for any (s, a) ∈ Ext(Z) as P(· | s, a) = δ( F ).
(2) Provide P, r, and planning horizon H − h to the hierarchy oracle, and obtain a policy π.

heading: B.2 FORMAL LEARNING PROCEDURE
text: In this section, we describe the procedure for learning a policy using the oracle-provided policies described in the previous section. Formally, we construct a surrogate MDP whose dynamics are determined byM and the oracle. We can then apply any tabular learning method to this new MDP (in our case, EULER), obtaining a policy in the surrogate MDP that readily translates into a policy inM. The components defining the surrogateMhl = (Z,G,Phl, Rhl, Heff) are as follows:
Meta-state space Z . We set
Z := ( Ent(S)× { 0, . . . , H̄ + 1 }) ∪ { } ,
where H̄ is a high-probability bound on the time to move through Heff exits (to be determined later). We incorporate the time step into the meta-state to ensure that both the dynamics and reward are computable from the state information (ensuring thatMhl is indeed an MDP).
Meta-action space G. Given a current meta-state (s, h) where s ∈ Z, the available meta-actions G can be identified with Ext(Z) ∪ { }.
Algorithm 7 Performing a Meta-Transition 1: procedure PERFORMMETATRANSITION((z, g) ∈ Z × G) . Executes the desired meta-transition in the original MDPM.
2: if z = then 3: return 4: else if z = (s, h) then 5: if h ≤ H̄ then 6: if s ∈ Z∗ or g = then 7: Execute within-cluster policy from oracle until termination. 8: return 9: else
10: Execute πz,g,h obtained from oracle until g is performed or h = H̄ . 11: s′, h′ ← current state and time step 12: if g was performed then 13: return (s′, h′) 14: else 15: return (s, H̄ + 1) 16: else 17: if s ∈ Z∗ or g = then 18: return 19: else 20: return (s, h)
Meta-dynamics Phl. Fix (z, g) ∈ Z × G for some z 6= , so that z = (s, h). We consider the procedure in Algorithm 7 for generating the meta-dynamics. Intuitively, we execute a meta-action g 6= by running the oracle-provided policy until the learner encounters g, or has acted for H̄ timesteps in the current episode. On the other hand, if g = , the agent executes the oracle-provided ε-suboptimal policy that remains within the current cluster and acts for H − h timesteps. Formally, the next state z′ is given by
z′ =  s ∈ Z∗ or g = (s′, h′) h ≤ H̄ (s, h) otherwise ,
where s′ and h′ are generated given T hierH−h(s, g) as
h′ | T hierH−h(s, g) = min(h+ T hierH−h(s, g), H̄ + 1) s′ | h′ ∼ { P(· | g) h′ ≤ H̄ δ(s) otherwise .
Note that the learner can only execute meta-actions while h ≤ H̄ . Furthermore, given access toM, one can easily simulate the dynamics ofMhl.
Meta-reward Rhl. Fix ((s, h), g) ∈ Z × G. Recall that the reward function ofM is supported on Ext(S) ∪ (Z∗)◦. Thus, this reward function can be lifted onto Mhl. Formally, we define the following reward function:
Rhl(z, g) =  Wh(s) z = (s, h), s ∈ Z∗ and h ≤ H̄ r(g) z = (s, h), s 6∈ Z∗ and h′ ≤ H̄ 0 otherwise ,
whereWh(s) is the random sum of rewards obtained by playing a within-cluster policy starting from s′ for the rest of the episode. Note that Rhl depends on Phl and is thus random. Furthermore, this reward function is consistent with how meta-transitions are performed in Algorithm 7.
Meta-horizon Heff . Recall that there exists an optimal policy that encounters at most Heff exits with high probability. Accordingly, we limit the learner to being able to choose Heff high-level actions, which recall can be choices of exits.
Solving Mhl. To obtain the desired policy, we apply EULER to Mhl. By the construction in Algorithm 7, the policy set returned by EULER easily translates into policies onM. Furthermore, the value of this policy is the same on both MDPs.

heading: B.3 PROVING THE REGRET BOUND
text: Having defined the procedure for learning a policy using the hierarchy, we now proceed with the regret analysis. Our analysis proceeds by constructing a policy expressible in Mhl that achieves near-optimal returns by imitating the high-level decisions made by π∗. We then use this policy as a comparator policy when applying EULER regret bounds toMhl. To formally construct the desired comparator policy, we need to first define the notion of a metahistory, which contains the set of high-level decisions made by any policy:
Definition B.1. Fix a policy π, which given some horizon L, generates a (random) trajectory (s0, a0, . . . , sL). Let Ext(π) be the number of exits performed in the trajectory, i.e.
Ext(π) = L−1∑ h=0 1 [(sh, ah) ∈ Ext(S)] .
The meta-historyHhl(π) corresponding to this trajectory is the sequence
(z0, g0, z1, g1, . . . , zExt(π)) = (si0 , (sj0 , aj0), si1 , (sj1 , aj1) . . . , siExt(π)),
where
in :=
{ 0 n = 0
jn−1 + 1 otherwise
jn := min h=in,...,L−1 1 [(sh, ah) ∈ Ext(S)] .
Note that zi ∈ Ent(S) and gi ∈ Ext(S) for all i = 0, . . . ,Ext(π). We omit π in writing Hhl when the underlying policy π is understood.
Informally, Hhl tracks all entrances and exits contained in a trajectory generated by π. We define the length of a meta-historyHhl, denoted as |Hhl|, as the number of exits contained inHhl.

heading: B.3.1 POLICY CONSTRUCTION
text: We now proceed with constructing the desired policy. Intuitively, the comparator imitates the distribution over Hhl(π∗), conditioned on |Hhl(π∗)| ≤ Heff . To see why this is sufficient for nearoptimality, recall that the reward on MTg is 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 is to ensure that the learner collects roughly the same sum of rewards from Z∗, which is the same as ensuring that this policy does not take too long to reach Z∗.
Construction. LetH be the running meta-history, containing k ≤ Heff actions. The optimal policy induces a distribution q(· | H) over Ahl representing the next exit it takes6. We then define π as
π(· | z,H) = { q(· | H) z = (s, h), h < H̄ otherwise.
Observe that π terminates the episode upon reaching H̄ . Furthermore, this policy is dependent on the meta-history. However, sinceMhl is an MDP, there exists a stationary policy that achieves at least the same value.

heading: B.3.2 SUBOPTIMALITY ANALYSIS
text: In this section, we prove that π achieves bounded suboptimality. Rather than analyzing π directly inMhl, we construct a new M̃hl and π̃ to better track the meta-history. In particular, conditioned on the event that π requires more than H̄ time steps to execute, then the agent would not be able to imitate the full meta-history generated by π∗, even after having performed less than Heff exits.
Constructing a surrogate for analysis. We now formalize the construction of the surrogate MDP M̃hl and the policy π̃ corresponding to π in this MDP. To obtain M̃hl, we redefine the dynamics fromMhl so that s′ | h′ ∼ P(· | g) in M̃hl. In effect, we allow the policy to continue performing transitions beyond H̄ , although without any reward. Accordingly, we define π̃ as π̃(· | z,H) = q(· | H). The following lemma formalizes how π̃ and M̃hl have desirable properties for the analysis: Lemma B.1 (Surrogate Policy Characterization). Let µ∗ denote the distribution of Hhl(π∗) | |Hhl(π∗)| ≤ Heff inMTg, and µ̃ the distribution ofH(π̃) in M̃hl. Then, (1− ζ)µ∗ ≤ µ̃.
Proof. Let ν∗ be the distribution induced by the following procedure:
(1) Sample a meta-history from the distributionHhl(π∗) | |Hhl(π∗)| > Heff .
(2) Truncate the obtained meta-history to length Heff .
It is easy to see from the definition of π̃ that µ̃ = (1− ζ)µ∗ + ζν∗. The desired result follows.
Thus, we have indeed shown the desired property that π̃ properly tracks the (truncated) meta-history generated by π∗. To justify performing our analysis on (M̃hl, π̃), we have the following result, which shows that any result on the value of the pair above applies to the value of π inMhl.
Lemma B.2. As constructed above, V M̃hl,π̃0 (s0) = V Mhl,π 0 (s0).
Proof. We writeM :=Mhl andM′ := M̃hl. Similarly, we write π′ := π̃. We proceed by proving a chain of equalities.
(V π ′,M′(s0) = V π,M′(s0)). We omitM′ in this part of the argument for clarity. By the performance difference lemma, we have that for any k ∈ [Heff ] and z ∈ Shl,
V π0 (s0)− V π ′ 0 (s0) = Heff−1∑ j=0 Ez∼dπj [ Aπ ′ j (z, π) ] .
6The distribution q can return if the learner stays in the cluster until episode termination.
Let ∆ := { z ∈ Shl ∣∣ z = (s, h), s 6∈ Z∗, h ≥ H̄}, which is the set on which π and π′ disagree. Observe that for any π and k, V πk (z) = 0 for any z ∈ ∆, and thus Aπ ′
k (z, π) = 0 for all such states. For any other z, Aπ ′
k (z, π) is clearly 0. Thus, we obtain the desired result.
(V π,M ′ (s0) = V π,M(s0)) We omit π in this part of the argument for clarity. Using the simulation lemma,
VM0 (s0)− VM ′ 0 (s0) = Heff−1∑ j=0 E(z,g)∼dM′j [ [(PM − PM′)VMj+1](z, g) ] .
Observe that the behavior of the two MDPs are identical conditioned on h′ ≤ H̄ . On the other hand, conditioned on h′ > H̄ , π can no longer receive rewards from either MDP. Therefore, [(PM − PM′)VMj ](z, g) = 0 for any j, z, g by decomposing the relevant expectations along the two events. We thus obtain the desired result.
Analyzing the surrogate. With the results above, we now proceed to analyze the difference in values
V MTg,∗ 0 (s0)− V M̃hl,π̃ 0 (s0),
which then implies the desired suboptimality result. First, we have the following lemma characterizing the time π̃ requires to fully execute a given meta-history in the base MDPM: Lemma B.3. Fix anyHhl = (z0, g0, . . . ) such that |Hhl| ≤ Heff . Furthermore, define the sequence of reaching times
T0 := 0 and Tk := Tk−1 + T hierH−Tk−1(zk−1, uk−1).
We define T hier(Hhl) to be the time required by the hierarchy to execute Hhl, which is formally given by T|Hhl| in the sequence above. Then,
(a) E [ T hier(Hhl) ] ≤ [1 + (1 + γ)W + ε]Heff .
(b) Let σ2 := β2[(1 + γ)W + ε]2Heff . Then, for any t > 0, P ( T hier(Hhl) ≥ [1 + (1 + γ)W + ε]Heff + t ) ≤ e−t 2/2σ2 .
Proof. We prove the two parts separately:
(a) We will prove via induction that E [Tk] ≤ k [1 + (1 + γ)W + ε]. For any k and Tk−1, E [ T hierH−Tk−1(zk−1, gk−1) ∣∣∣ Tk−1] ≤ E [T ∗H−Tk−1(zk−1, gk−1) ∣∣∣ Tk−1]+ ε = 1 + E [ T ∗H−Tk−1(zk−1, s(gk−1))
∣∣∣ Tk−1]+ ε ≤ 1 + (1 + γ)W + ε,
where the first inequality uses properties of the hierarchy oracle, while the final inequality follows by combining Definition 5.2(b) and Assumption 5.2. Therefore, by linearity and the tower property of expectation,
E [Tk] = E [Tk−1] + E [ T hierH−Tk−1(zk−1, gk−1) ] = E [Tk−1] + E [ E [ T hierH−Tk−1(zk−1, gk−1)
∣∣∣ Tk−1]] ≤ E [Tk−1] + 1 + (1 + γ)W + ε.
The desired result then follows by induction. (b) Let Bk := k [1 + (1 + γ)W + ε] and fk(t) := E [ T hierH−t(zk, gk) ] . Note that for any k and
t, Bk−1 + fk−1(t) ≤ Bk, by following the argument in (a). Therefore, for any λ > 0, E [exp {λ (Tk −Bk)}]
= E [E [exp {λ (Tk −Bk)} | Tk−1]] ≤ E [ E [ exp { λ ( Tk−1 + T hier H−Tk−1(zk−1, gk−1)−Bk−1 − fk−1(Tk−1) )} ∣∣∣ Tk−1]] ,
where the last inequality uses the monotonicity of the exponential function. Therefore, by applying the sub-Gaussian condition given in Definition 5.2,
E [exp {λ (Tk −Bk)}] ≤ E [ exp {λ (Tk−1 −Bk−1)}
E [ exp { λ ( T hierH−Tk−1(zk−1, gk−1)− fk−1(Tk−1) )} ∣∣∣ Tk−1]] ≤ E [exp {λ(Tk−1 −Bk−1)}] exp [ λ2C2/2 ] ,
where we have used the fact that T hierH−Tk−1(zk−1, s(gk−1)) has a sub-Gaussian upper tail with variance proxy
C2 = β2E [ TπH−Tk−1(zk−1, s(gk−1)) ∣∣∣ Tk−1]2 ≤ β2 [(1 + γ)W + ε]2 .
Note that we have once again used the properties of the hierarchy oracle, and Assumption 5.2. Therefore, by induction, E [exp {λ (Tk −Bk)}] ≤ E [ λ2( √ kC)2/2 ] , from which the
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 a given meta-history, we can now analyze its suboptimality: Lemma B.4. There exists a policy π expressible inMhl such that
V MTg,∗ 0 (s0)− V MTg,π 0 (s0) . (1 +Heff + β √ Heff)ε+ [ γHeff + β(1 + γ) √ Heff ] W + ζH.
Proof. Assume that π∗ generates a (random) meta-history of length N given by Hhl = (z0, g0, z1, g1, . . . , zN ). Furthermore, let T ∗ denote the (random) time π∗ takes to reach zN . Then, givenHhl and T ∗, observe that we can write
V ∗0 (s0) = E [R∗T∗(Hhl)] , where R∗T (Hhl) := V ∗T (zN )1 [zN ∈ Z∗] + N−1∑ k=0 r(gk),
using the assumptions on the reward function and condition (a) in Assumption 5.1. Subsequently, letting E be the event {N ≤ Heff}, we can bound the right-hand side as
V ∗0 (s0) = E [R∗T∗(Hhl)] ≤ (1− ζ)E [R∗T∗(Hhl) | E] + ζH,
where we have used Assumption 5.1 to bound the probability that N > Heff .
Our goal for the rest of this proof is to transform the expectation on the right-hand side into a form that lower bounds V π0 (s0). To this end, we define
RhierT (Hhl) := V hierT (zN )1 [zN ∈ Z∗] + N−1∑ k=0 r(gk),
and the sequence of times
T0 = 0 and Tk := Tk−1 + T hierH−Tk−1(zk, gk).
Note that Rhier and TN are analogous to R∗ and T ∗, respectively. Then, letting F be the event{ TN ≤ H̄ } , note that
V ∗0 (s0) ≤ (1− ζ)E [R∗T∗ | E] + ζH = (1− ζ)E [ R∗T∗ −RhierTN +R hier TN ∣∣ E]+ ζH ≤ E [( R∗T∗ −RhierTN ) 1 [F ]
∣∣ E]︸ ︷︷ ︸ (I) + (1− ζ)E [ RhierTN 1 [F ] ∣∣ E]︸ ︷︷ ︸ (II) + [ ζ + P ( FC ∣∣ E)]H.
We bound (I) and (II) separately.
Bounding (I). Let G be the event E ∩ {zN ∈ Z∗}. Then, if we define
Tmin = N−1∑ k=0 Tmin(zk, uk) ≤ N(W + 1)
as the minimum time needed to executeHhl, we then have that E [( R∗T∗ −RhierTN ) 1 [F ] ∣∣ E] ≤ E [R∗T∗ −RhierTN ∣∣ E] ≤ E [ V ∗T∗(zN )− V hierTN (zn)
∣∣ G] ≤ E [ V ∗Tmin(zN )− V hier TN (zN )
∣∣ G] ≤ ∫ H
0
P ( V ∗Tmin(zN )− V hier TN (zN ) > α ∣∣ G) dα. Note that the bound on Tmin follows from Assumption 5.2. To convert the different in values into a difference of times, observe that if TN − Tmin ≤ α− ε, then
V ∗Tmin(zN )− V hier TN (zN ) = V ∗ Tmin(zN )− V ∗ TN (zN ) + V ∗ TN (zN )− V hier TN (zN )
≤ (T̄ − Tmin) + ε ≤ α.
Therefore,∫ H 0 P ( V ∗Tmin(zN )− V hier TN (zN ) > α ∣∣ G) dα ≤ ∫ H
0
P (TN − Tmin > α− ε | G) dα
≤ E [∫ H 0 P (TN − Tmin > α− ε | Hhl) dα ∣∣∣∣∣ G ]
≤ E [∫ H 0 P (TN − [1 + (1 + γ)W + ε]Heff > α− ε−Heff(γW + ε) | Hhl) dα ∣∣∣∣∣ G ]
≤ ε+Heff(γW + ε) + E [∫ ∞
0
P (TN − [1 + (1 + γ)W + ε]Heff > α | Hhl) dα ∣∣∣∣ G]
. ε+Heff(γW + ε) + β[(1 + γ)W + ε] √ Heff ,
where the final inequality integrates the tail bound provided in Lemma B.3. Overall, we have that by rearranging,
(I) . (1 +Heff + β √ Heff)ε+ [ γHeff + β(1 + γ) √ Heff ] W.
Bounding (II). By the characterization of π̃ in Lemma B.1, (1− ζ)E [ RhierTN (Hhl(π ∗))1 [F ] ∣∣ E] ≤ E [RhierTN (Hhl(π̃))1 [F ]] ≤ V π̃0 (s0),
where the final inequality uses the fact that R̄T̄ (Hhl(π̃)) is the return of π̃ in M̃hl, given F . Concluding. Putting all of the previous bounds together, we find that
V ∗0 (s0) ≤ V π̄0 (s0) + (1 +Heff + β √ Heff)ε+ [ γHeff + β(1 + γ) √ Heff ] W
+ [ ζ + P ( FC ∣∣ E)]H. By setting H̄ to
H̄ = Heff [1 + (1 + γ)W + ε] + β[(1 + γ)W + ε] √ 2Heff log 1
ζ H, sub-Gaussian tail bounds on TN implies that P ( FC ∣∣ E) ≤ ζ. Finally, by Lemma B.2, V M̃hl,π̃0 (s0) = V Mhl,π 0 (s0) = V MTg,π 0 , where the last equality follows by the construction ofMhl. We thus obtain the desired suboptimality bound.

heading: B.3.3 REGRET ANALYSIS
text: As earlier suggested, we now make use of π̃ as a comparator policy in order to prove a regret bound on a learner making use of the procedure outlined in Section B.2. Theorem B.1. Assume that EULER generates policies π1, . . . , πN onMhl, as constructed in Section B.2. Then, we have the following regret bound:
N∑ k=1 V ∗0 (s0)− V πk 0 (s0) . √ H2H̄LMN +Nεsubopt,
where εsubopt := (1 +Heff + β √ Heff)ε+ [ γHeff + β(1 + γ) √ Heff ] W + ζH.
Proof. Throughout the proof, we consider applying EULER toMhl where the rewards are scaled by 1/H to ensure that rewards are bounded in [0, 1]. As a result, we can bound G ≤ 1 in the EULER regret bound in Zanette & Brunskill (2019), since the sum of rewards in Mhl is also the sum of rewards inM, and scaling by 1/H gives the desired bound on G. Therefore,
N∑ k=1 V ∗,Mhl0 (s0)− V πk 0 (s0) . H
√ 1
Heff H̄LMHeffN =
√ H2H̄LMN.
Furthermore,
V ∗0 (s0)− V ∗,Mhl 0 (s0) ≤ V ∗0 (s0)− V π0 (s0) + V π,Mhl 0 (s0)− V ∗,Mhl 0 (s0) ≤ εsubopt.
We thus obtain the desired result.

heading: B.4 AN EXPONENTIAL REGRET SEPARATION FOR A HIERARCHY-OBLIVIOUS LEARNER
text: In this section, we provide proof of the exponential regret separation between a hierarchical learner and a learner oblivious to the hierarchy. The overall idea behind our proof is the reduction of solving the family of minimax instances described in Domingues et al. (2021) to a particular family of task distributions.

heading: B.4.1 THE HARD TASK DISTRIBUTION FAMILY
text: In this section, we describe the family of task distributions that forces any meta-training-oblivious learner to 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 a member of this family by a tuple (`∗, a∗, e∗), where `∗ is a binary string of length W − 1, and a∗, e∗ ∈ {0, 1}. The MDPM(`∗,a∗,e∗) = (S,A,P(`∗,a∗,e∗), r,H) corresponding to this tuple is constructed as follows:
State Space S. We create a root state sroot, 2W − 1 states indexed by binary strings of length at most W − 1 collected into a set T = {s0, s1, s00, s01, . . . }, a gate state sgate, and terminal states trap, S , F .
Action Space A. The set of available actions at every state is the set {0, 1}.
Transition Dynamics P(`∗,a∗,e∗). We define the dynamics as follows:
P(`∗,a∗,e∗)(· | s, a) =  δ(sa) s = sroot δ(sta) s = st ∈ T, |t| < W − 1 bδ(sgate) + (1− b)δ( trap) s = st ∈ T, |t| = W − 1, s 6= s`∗ , b ∼ Ber (1/2) bδ(sgate) + (1− b)δ( trap) s = s`∗ , b ∼ Ber (1/2 + ε1 [a = a∗]) δ( S) s = sgate, a = e∗ δ( F ) s = sgate, a 6= e∗.
Reward Function r. The reward function is r(s, a) = 1 [s = S ] + 1 [s = sgate, a = 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 (`∗, a∗), where `∗ and a∗ are as described above. Then, the task distribution T(`∗,a∗) ∈ TW chooses uniformly within the set { M(`∗,a∗,0),M(`∗,a∗,1) } . Note that this implicitly defines the latent hierarchy so that the clusters are {sroot, sgate, trap} ∪ T , { S}, and { F }. Furthermore, the set of exits for the first cluster is {(sgate, 0), (sgate, 1)}.

heading: B.4.2 A FAMILY OF HARD INSTANCES
text: In this section, we describe the family of hard instances which we reduce to solving the task distribution above. Intuitively, if an algorithm incurs low regret throughout MW , then it must be able to quickly find a 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 (`∗, a∗), and is constructed similarly as any member of MW , but ignoring states outside {sroot, sgate, trap}∪T . Additionally, we redefine the reward function r for any member to be r(s, a) := 1 [s = sgate]. We note that this is exactly the set of hard tasks used to prove a minimax regret bound in Domingues et al. (2021).
The lower bound. We state the lower bound result from Domingues et al. (2021), in a slightly more restricted form for ease 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 a policy πn in an MDP M. That is, Hn = ((s0, a0, r0, s1), (s1, a1, r1, s2), . . . , (sH−1, aH−1, rH−1, sH)), where s0 and a0 are fixed, rh = r(sh, ah), and sh+1 ∼ PM(· | sh, ah). Additionally, we setH0 = ∅. Then, a valid algorithmA for our purposes is one which, for the nth episode, outputs a deterministic, non-stationary policy π that is solely a function of the current state and action and ⋃n−1 i=1 Hi. That is, A 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. (2021), Theorem 9, restated). Assume that W ≥ 2 and H ≥ 3W . Then, for every algorithm A, there exists an MDPM∈ NW such that
EM,A [ N∑ n=1 V ∗0 (sroot)− V πn 0 (sroot) ] & 2W/2 √ H2N.
Algorithm 8 The reduction of learning NW to learning MW in Section B.4.3. 1: procedure PA(M∈ NW ) 2: InitializeH0 = ∅ 3: for all n ∈ [N ] do 4: Obtain πn = A(H0, . . . ,Hn−1). 5: Play πn inM, get history Gn = ((s0, a0, r0, s1), . . . , (sH−1, aH−1, rH−1, sH)). 6: if sW+1 = sgate then 7: s′W+1 ← sW+1 8: for all h = W + 1, . . . ,H − 1 do 9: if h = W then 10: s′h+1 ← S if ah = 1 else F . 11: r′h ← 1 [ah = 1] 12: else 13: s′h+1 ← s′h, r′h ← rh 14: Replace (sh, ah, rh, sh+1) with (s′h, ah, r ′ h, s ′ h+1) in Gn 15: Hn ← Gn.

heading: B.4.3 PROVING THE HARDNESS RESULT
text: 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, letA be any algorithm for learning any MDP in MW . We then construct an algorithm PA for learning any MDP in NW as in Algorithm 8.
Given this reduction, we aim to prove the following result: Proposition B.2. For anyM(`∗,a∗) ∈ NW , we have that
EM(`∗,a∗),PA [ N∑ n=1 V ∗0 (sroot)− V πn 0 (sroot) ] ≤ EM(`∗,a∗,1),A [ N∑ n=1 V ∗0 (sroot)− V πn 0 (sroot) ] .
To prove this result, we first prove that PA can simulateM(`∗,a∗,1): Lemma B.5. For any n, the distribution over (H0, . . . ,Hn) induced by running Algorithm 8 over M(`∗,a∗) ∈ NW is equal to that induced by running A overM(`∗,a∗,1) ∈MW .
Proof. We proceed by induction. The result holds trivially for n = 0.
Now, assume that the result holds for some n. We condition on the histories (H0, . . . ,Hn) Then, note that both algorithms play the same policy πn+1, since PA uses A to obtain the next policy. As a result, by the construction ofM(`∗,a∗) andM(`∗,a∗,1), the distribution over (sh, ah, rh, sh+1) are equal for h ≤ W . Furthermore, Lines 6 − 14 simulates the dynamics of M(`∗,a∗,1) conditioned on sW+1 = sgate, while conditioned on sW+1 = trap, the dynamics of the two MDPs are the same. Therefore, conditioned on any (H0, . . . ,Hn), the distribution overHn+1 induced by the two algorithms are also the same. Thus, the claim holds by induction.
Finally, we can prove Proposition B.2.
Proof of Proposition B.2. Throughout this proof, we omit the starting state sroot and the timestep 0 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
EM(`∗,a∗),PA [ N+1∑ n=1 V ∗ − V πn ]
= EM(`∗,a∗),PA [ N∑ n=1 V ∗ − V πn ] + EM(`∗,a∗),PA [V ∗ − V πN+1 ]
≤ EM(`∗,a∗,1),A [ N∑ n=1 V ∗ − V πn ] + EM(`∗,a∗),PA [E [V ∗ − V πN+1 | (H0, . . . ,HN )]] ,
where the final inequality uses the inductive hypothesis and the tower property of expectation. Now, recall from Lemma B.5 that
EM(`∗,a∗),PA [E [V ∗ − V πN+1 | (H0, . . . ,HN )]]
= EM(`∗,a∗,1),A [E [V ∗ − V πN+1 | (H0, . . . ,HN )]] .
We emphasize that the value functions are still with respect toM(`∗,a∗). However, for any policy π output by A,
V ∗ − V π = EM(`∗,a∗),π [(H −W − 1)1 [sW+1 6= sgate]] ≤ EM(`∗,a∗),π [(H −W − 1)1 [sW+1 6= sgate or aW+1 6= 1]] ≤ EM(`∗,a∗,1),π [(H −W − 1)1 [sW+1 6= sgate or aW+1 6= 1]] .
Note that the right-hand side is the regret in M(`∗, a∗, 1) for playing π. Therefore, since both algorithms play the same policy πN+1, we thus obtain the desired result by induction.
With Proposition B.2, we can now formally state and prove the separation result: Theorem B.3. There exists a task distribution T(`∗,a∗) ∈ 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
EM∼T(`∗,a∗) [RegretN (M,A)] & 2 W/2 √ H2N.

heading: On the other hand, for any task distribution in the family, the hierarchy-based learner P in Section
text: B.2, with access to a 0-suboptimal hierarchy oracle, achieves regret bounded by √ H2N with high probability on any sampled task.
Proof. Fix any algorithm A. Using Theorem B.2, there existsM(`∗,a∗) such that
EM(`∗,a∗),PA [ N∑ n=1 V ∗0 (sroot)− V πn 0 (sroot) ] & 2W/2 √ H2N
Thus, by Proposition B.2,
EM(`∗,a∗,1),A [ N∑ n=1 V ∗0 (sroot)− V πn 0 (sroot) ] & 2W/2 √ H2N.
Note that the proof in Proposition B.2 can be extended forM(`∗,a∗,0) with appropriate modifications to PA, and thus the same inequality holds. Consequently,
EM∼T(`∗,a∗) [RegretN (A)] & 2 W/2 √ H2N.
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 + 1, allowing us to obtain tighter bounds (as Shl is smaller than the construction in Section B.2). Furthermore, the suboptimality of planning with the hierarchy oracle is 0 for any task distribution in the family. We thus obtain the desired bound.

heading: B.5 A DISCUSSION OF DEFINITION 5.2
text: 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 hierarchybased learner to incur O(H) suboptimality.
B.5.1 (α, β)-UNRELIABILITY
Consider the MDP in Figure 9 with horizon H + 2 and two actions a∗ and a1. The optimal policy chooses a∗ at every step, achieving a value of H −O(1), since
V ∗H+1(s0) = 1
2 H +
1 2 V ∗H(s1) = 1 2 H + 1 4 (H − 1) + 1 4 V ∗H−1(s2)
= H H∑ h=1 1 2h − 1 2 H∑ h=1 h 2h = H −O(1).
Now, assume that the MDP has a latent hierarchy so that the set of exits are given by (ti, a) for any i ∈ [H] and a ∈ A. Clearly, the optimal hierarchy-based learner would always choose (t0, a∗) or (t0, a1) as its high-level action. However, if the agent fails to transition to t0 at the first timestep due to stochasticity, it will go to the end of the chain, back to s0 and try a∗ once more. This is because it already has set a meta-action, and does not replan until an exit is performed. Thus, the optimal agent on the meta-MDP achieves a value of H/2, and is therefore O(H)-suboptimal, even with a 0-suboptimal hierarchy oracle.
Intuitively, hierarchy-based learners as formulated in Section B.2 fail on the MDP in Figure 9 because such learners commit to a skill until completion. Thus, when such skills exhibit high variance in completion times, hierarchy-based learners fare worse than other learners which are able to replan based on the current state (e.g., in this case, choose another exit if a∗ fails to take the agent to the current subgoal). Thus, (α, β)-reliability serves to eliminate such MDPs, ensuring that the skills corresponding to reaching exits are reliable.
B.5.2 γ-GOAL-REACHING SUBOPTIMALITY
In this section, we show that even when a 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 on a single room for simplicity. Furthermore, assume that there are two exits, one from lH/2 and one from rH/2. Note that a 0-suboptimal hierarchy oracle has highly reliable goal-reaching policies for reaching both of these exit states, requiring exactly H/2 timesteps with no stochasticity.
However, given the values assigned to lH/2 and rH/2, the optimal policy would opt to take the state t, which transitions to either state with probability at least 1/2 in 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 a perfect hierarchy oracle.
Hierarchy-based learners fail on the MDP in Figure 10 because an optimal policy for goal-reaching does not necessarily reach a goal as quickly as possible. Thus, γ-goal-reaching suboptimality is a regularity condition that ensures that this is indeed the case.

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

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. 

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.