Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

Anders Jonsson Department of Engineering Universitat Pompeu Fabra [email protected]

Emilie Kaufmann Univ. Lille, CNRS, Inria Centrale Lille, UMR 9189-CRIStAL [email protected]

arXiv:2607.29294v1 [cs.LG] 31 Jul 2026

Gianmarco Tedeschi Dept. Electronics, Information, and Bioengineering Politecnico di Milano [email protected]

Lorenzo Steccanella Department of Engineering Universitat Pompeu Fabra [email protected]

Abstract We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel. HBPIUCRL exploits the fact that a high-level transition corresponds to a multi-step transition at the low level. We introduce two conditions on the low-level dynamics that are sufficient to make parallel HRL learnable. When these conditions hold, we prove that HBPI-UCRL has a polynomial sample complexity in the problem parameters. In the sparse-reward, goal-directed setting, our sample complexity upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart, providing theoretical justification for the empirical success of HRL.

Introduction

In hierarchical reinforcement learning (HRL), a branch of reinforcement learning (RL), the learning problem is decomposed into a hierarchy of subproblems, each a Markov decision process (MDP). At the top of the hierarchy is a semi-Markov decision process (SMDP) that selects between subproblems. When selected, a subproblem executes a local policy for multiple time steps before returning control to the SMDP. The aim is to approximate the optimal hierarchical policy, which involves maximizing a local value function of each subproblem as well as the value function of the SMDP. Many authors have demonstrated empirically that HRL carries several practical benefits, such as efficient exploration [Bellemare et al., 2020, Konidaris and Barto, 2009, Machado et al., 2022], improved sample efficiency [Levy et al., 2019, Nachum et al., 2018, Rafati and Noelle, 2019], better credit assignment [Vezhnevets et al., 2017], faster long-term planning [Gopalan et al., 2017] and generalization and transfer [Ahn et al., 2022, Matthews et al., 2022]. However, in spite of the long history and large body of work on HRL, there are surprisingly few works that prove theoretical guarantees for HRL algorithms. This is especially true when the SMDP and subproblem policies are learned in parallel. Hence an important research question is to establish theoretical foundations for HRL that explain its benefits. We present a novel model-based algorithm for episodic HRL called HBPI-UCRL, for hierarchical best policy identification. The algorithm learns the SMDP policy and subproblem policies in parallel by collecting data in the form of episodes. We assume that the subproblem MDPs share the transition dynamics but differ in the local reward functions. HBPI-UCRL performs best policy identification by computing empirical composite distributions and maintaining high-probability confidence bounds on the SMDP dynamics. Since the SMDP dynamics depend on the subproblem policies, the SMDP Preprint.

learning problem is non-stationary when the subproblem policies are learned in parallel. A key contribution of our work is to identify two conditions that relate the quality of the subproblem solutions to the accuracy of the SMDP dynamics. These conditions are sufficient for HRL to be PAC-learnable, and can also be of practical importance. When our two conditions hold, we prove that HBPI-UCRL is (ε, δ)-PAC with respect to the optimal 4 6 2 1 e hierarchical value function. Its sample complexity is of order O(SAH H /ε ) , where SA is the size of the subproblem state-action space, H is the subproblem horizon and H is the SMDP horizon. Notably, the sample complexity is independent of the number of high-level states S and the number of subproblems. In sparse-reward, goal-directed HRL, a version of HBPI-UCRL achieves a 2 2 2 e sample complexity bound of order O(SAH H /ε ), which is a factor S smaller than that of the non-hierarchical algorithm BPI-UCRL [Kaufmann et al., 2021], and only a factor H 2 larger than that of BPI-UCRL when applied to a single sparse-reward subproblem. To the best of our knowledge, ours is the first explicit sample complexity result for the parallel HRL setting. The only comparable work for parallel HRL is that of Drappo et al. [2025], who analyze the regret specifically for the goal-oriented setting. It is possible to use a regret-to-PAC conversion to obtain a sample complexity guarantee for their algorithm, but unlike HBPI-UCRL, their algorithm does not have a data-dependent stopping rule and cannot solve a more general class of HRL problems. We further elaborate on the differences in Section 5. The paper is organized as follows. Section 2 introduces two families of composite distributions and describes best policy identification (BPI) for episodic RL. Section 3 describes our formalism for episodic HRL and introduces our two key conditions for learnability. HBPI-UCRL is described in Section 4, in which we analyze its sample complexity, including the special case of sparse-reward, goal-directed HRL. Our sample complexity bounds are put in context of existing work in Section 5. In Section 6 we present some numerical experiments, and we conclude with a discussion. Notation Given a finite set X , ∆(X ) denotes the probability simplex on X . Given an integer n > 0, JnK denotes the set {1, . . . , n}. We use I(E) to denote the indicator function for an event E, a ∧ b to denote the minimum of a and b, and a ∨ b to denote the maximum. Given integers i and j such that 1 ≤ i ≤ j, let γi:j denote a partial sequence γi , . . . , γj of elements from a given alphabet Γ.

Reinforcement Learning

An episodic Markov decision process (MDP) is a tuple M = ⟨S, A, P, R, H⟩, where S is the finite state space with cardinality S = |S|, A is the finite action space with cardinality A = |A|, P : S × A → ∆(S)2 is a transition kernel, R : S × A → [0, 1] is a reward function, and H > 1 is an integer horizon. An episode s1 , a1 , · · · , sH , aH , sH+1 is valid if P(sh+1 |sh , ah ) > 0 for each PH h ∈ JHK. We say that M is sparse-reward if h=1 R(sh , ah ) ≤ 1 for each valid episode. A deterministic policy π = {πh }h∈JHK defines a mapping πh : S → A for each h ∈ JHK. The value function V π : JH + 1K × S → R of π measures the expected reward sum under π when starting from π state s at step h. The value function is recursively defined for each s ∈ S as VH+1 (s; R) = 0 and X π Vhπ (s; R) = R(s, πh (s)) + P(s′ |s, πh (s))Vh+1 (s′ ; R) ∀h ∈ JHK, s′

where the notation emphasizes the dependence on R. We assume known R but unknown P, and below we assume a unique initial state s1 , though all results generalize to fixed initial state distributions. We denote by π ∗ an optimal policy, whose value function satisfies V1∗ (s1 ; R) = maxπ V1π (s1 ; R). In online RL, in each episode t an agent chooses a policy π t and collects a state sequence st1:H+1 by taking in each step h the action ath = πht (sth ) and transitioning to the next state sth+1 ∼ P(·|sth , ath ). The policy π t can be selected based on data from previous episodes. Our paper focuses on a particular PAC RL problem, called best policy identification (BPI). In this setting, after each episode the agent can decide to stop data collection and output a guess π b for the optimal policy. The resulting algorithm is called (ε, δ)-PAC if |V1∗ (s1 ; R) − V1πb (s1 ; R)| ≤ ε with 1 The notation O e hides logarithmic factors in S, A, H, H, 1/ε and 1/δ, and states the result for the regime of small δ. 2 Several authors consider time-inhomogeneous transition kernels P , but this is uncommon in the HRL literature. h

probability larger than 1 − δ. The sample complexity of the algorithm is the number of episodes τ it requires before stopping and making an (ε, δ)-PAC guess. (ε, δ)-PAC algorithms with a minimax optimal sample complexity are based on sophisticated Bernstein bonuses [e.g. Dann et al., 2019]. In this work we instead focus our attention on a simpler algorithm called BPI-UCRL [Kaufmann et al., 2021], that couples an optimistic algorithm based on Hoeffding bonuses with an appropriate stopping rule. In this section, we present an alternative stopping rule for BPI-UCRL rooted in new bounds on the estimation error of composite probability distributions. As we shall see, this variant of BPI-UCRL can be naturally extended to an algorithm for HRL. Estimating transitions. We now introduce notation for model-based episodic RL algorithms. After t bt of the transition kernel as follows: episodes, we compute counts N t and an empirical estimate P N t (s, a, s′ ) =

t X H X

I((s, a, s′ ) = (sℓh , πhℓ (sℓh ), sℓh+1 )),

ℓ=1 h=1

t ′ bt (s′ |s, a) = PN (s, a, s ) , P t ′ s′ N (s, a, s )

bt (s′ |s, a) ≡ 1/S if N t (s, a) ≡ P ′ N t (s, a, s′ ) = 0. We remark that the episode with P s st1 , at1 , · · · , stH , atH , stH+1 is fully determined by st1:H+1 and π t . We use Phπ (s′ |s) = P(s′ |s, πh (s)) bt,π (s′ |s) = P bt (s′ |s, πh (s)) to denote the true and estimated transition kernels under the policy and P h π. Using time-uniform concentration, we establish in Appendix G that the event bt (·|s, a) − P(·|s, a) ≤ B t (s, a) . E = ∀t ∈ N, ∀(s, a) ∈ S × A, P (1) 1 p satisfies P(E) ≥ 1 − δ/2, where B t (s, a) = 2β(N t (s, a), δ)/N t (s, a) ∧ 2 and β is defined as β(n, δ) = log(2SA/δ) + (S − 1) log(e(1 + n/(S − 1))). Composite distributions. We consider two families of composite probability distributions induced by the transition kernels {Phπ }h∈JHK of π. Given integers i and j such that 1 ≤ i < j ≤ H + 1, let π Pi:j (·|si ) be the probability of sequences si+1:j conditional on a state si , recursively defined as π P (s |s ), if i + 1 = j, π Pi:j (si+1:j |si ) = Phπ (si+1 |si ) P π (s |s ), else. h

i+1

i+1:j

i+2:j

i+1

Given i and j such that 1 ≤ i ≤ j ≤ H + 1, let Pπi:j (·|si ) be the occupancy of states sj at step j conditional on a state si , recursively defined as Pπi:j (sj |si ) =

I(s if i = j, P i = sjπ), π P (s |s ) P (s |s ), else. i+1 i j i+1 i+1:j si+1 h

Replacing Phπ in the above definitions with another transition kernel for π induces different composite b t,π and P bt,π . bt,π have associated composite distributions P distributions, e.g. the empirical estimates P i:j i:j h BPI-UCRL Revisited. We present and analyze a variant of BPI-UCRL [Kaufmann et al., 2021] for best policy identification. In each episode t, BPI-UCRL computes an upper confidence bound on the optimal value function V ∗ . For each state-action (s, a), the algorithm first defines a confidence set bt (·|s, a) ≤ B t (s, a) . C t (s, a) = p ∈ ∆(S) p − P (2) 1

t An upper confidence bound V t on V ∗ can now be recursively defined for s as VH+1 (s; R) = 0 and h i X t Vht (s; R) = max R(s, a) + max p(s′ )Vh+1 (s′ ; R) ∀h ∈ JHK. (3) t a

The policy π

t+1

p∈C (s,a)

s′

in episode t + 1 is defined as the greedy policy for V t .

b t recursively defined for each s ∈ S as L b t (s) = 0 and Our analysis relies on an error function L H+1 h i X t,πt+1 t+1 t t ′ t ′ b (s) = min 2, B (s, π (s)) + b b L P (s |s)L ∀h ∈ JHK. (4) h h+1 (s ) h h s′

Intuitively, L compounds the approximation error of kernels in the confidence set C t across an entire episode. In Appendix C we show that this is enough to upper bound the difference between both types of composite probability distributions. We modify BPI-UCRL by redefining the stopping criterion as b t (s1 ) ≤ ε/(2H)}. Upon stopping, BPI-UCRL outputs the policy π τ = inf{t ∈ N : L b = π τ +1 . 1

In Appendix C we prove the following theorem that upper bounds the sample complexity of our variant of BPI-UCRL. The upper bound is a factor H larger than that reported by Kaufmann et al. [2021] for stationary transition kernels in their Appendix E. However, we believe that their proof is incorrect, and that the sample complexity in the stationary setting is of the same order as ours. Theorem 2.1. With probability larger than 1 − δ, BPI-UCRL with the modified stopping rule returns a policy π b that satisfies V1∗ (s1 ; R) − V1πb (s1 ; R) ≤ ε using a number of episodes SAH 5 SAH 4 SAH SAH log log . + S log τ =O 2 2 ε δ ε δ Our claims throughout focus on the regime of small δ [Kaufmann et al., 2021] in which the first term dominates, but any improvement in the sample complexity also carries over to the second term. In Appendix C we show that if M is sparse-reward, we can set the stopping criterion of BPI-UCRL to 2 2 b t (s1 ) ≤ ε/2 and achieve a sample complexity of order O(SAH e L /ε ) in the regime of small δ. 1

Hierarchical Reinforcement Learning

In episodic HRL, the aim is to identify a good hierarchical policy (defined below) in an episodic MDP M = ⟨Σ, A, X , Y, N ⟩, usually called the flat (i.e. non-hierarchical) MDP in the HRL literature. We assume that M admits a hierarchical structure. Concretely, the state space Σ is characterized by a high-level state space S with cardinality S = |S| and a subproblem state space S, and three known functions f : S × S → Σ, g : Σ → S and g : Σ → S map pairs (s, s) ∈ S × S to states σ ∈ Σ and vice versa. In addition, there are K subproblems in the form of episodic MDPs Mk = ⟨S, A, P, Rk , H⟩, k ∈ JKK, that share the transition kernel P but differ in the local reward function Rk . The transition kernel X of M can be expressed as follows for each transition (σ, a, σ ′ ): X X (σ ′ |σ, a) = P(s′ |g(σ), a) · I(σ ′ = f (g(σ), s′ )). s′

Hence the transitions of M are fully characterized by the kernel P and the functions f , g and g. Given a set of subproblem policies π = {π k }k∈JKK , an episodic semi-Markov decision process (SMDP) is a tuple Mπ = ⟨Σ, JKK, P π , Rπ , H⟩, where boldface indicates SMDP components. At each step h ∈ JHK, the learner observes a state σh ∈ Σ, selects a subproblem k ∈ JKK and executes the subproblem policy π k for H steps to generate a state sequence s1:H+1 starting from s1 = g(σh ). The state becomes σh+1 = f (g(σh ), sH+1 ), and the process repeats H times, implying HH = N . The SMDP transitions P π and reward Rπ depend on the subproblem policies π = {π k }k∈JKK . Given subproblem policies π, state pair (σ, σ ′ ) and subproblem k, the SMDP dynamics are defined as X k k P π (σ ′ |σ, k)= Pπ1:H+1 (sH+1 |s1 = g(σ))I(σ ′ =f (g(σ), sH+1 )), Rπ (σ, k)=V1π (g(σ); Yg(σ) ), sH+1

where Ys (s, a) = Y(f (s, s), a), s ∈ S. Hence SMDP transitions associated with subproblem k are k defined by the H-step transition kernel Pπ1:H+1 of π k , and SMDP rewards are defined by the value of k k bt,π b t,π and R b t,π to denote the empirical estimates induced by P π k under Y. We use P and Vb t,π . 1:H+1

A (deterministic) SMDP policy π = {πh }h∈JHK is a collection of mappings πh : Σ → JKK selecting the subproblem to be solved in step h. A hierarchical policy (π, π) consists of an SMDP policy π and a set of subproblem policies π = {π k }k∈JKK . The value function V π,π : [H + 1] × Σ → R of π,π the hierarchical policy (π, π) is defined for each σ ∈ Σ as VH+1 (σ) = 0 and X π,π Vhπ,π (σ) = Rπ (σ, πh (σ)) + P π (σ ′ |σ, πh (σ))Vh+1 (σ ′ ) ∀h ∈ JHK. σ′ π,π Vh (σ) is the value of the hierarchical policy (π, π) in the flat MDP M, i.e. the expected cumulative

sum of rewards under the original reward function Y when using a sequence of subproblem policies (π k1 , . . . , π kH ), with each subproblem kh = πh (σh ) chosen by the SMDP policy π. ∗

∗

Let Vh∗ (σ) ≡ maxπ Vhπ,π (σ) be the optimal value function of the SMDP Mπ induced by the optimal subproblem policies π ∗ = {π ∗,k }k∈JKK , where π ∗,k is the optimal subproblem policy under 4

f f

T s

σ1

3 σℓ

G f

L f B

f f f

Figure 1: a) An MDP representing a gridworld with 4 rooms and treasures; b) five subproblems corresponding to the terminal states G, L, R, T, B. Rk . The aim of the learner is to return a hierarchical policy (b π, π b) such that |V1∗ (σ1 ) − V1πb ,bπ (σ1 )| ≤ ∗ ε. Note that V is optimal with respect to the hierarchical structure, but usually different from the optimal value function of M. This is a commonly accepted tradeoff in the HRL community, since HRL algorithms can typically solve the SMDP problem more efficiently in practice. An SMDP example. To illustrate our definition of episodic SMDPs, Figure 1a) shows an episodic MDP M = ⟨Σ, A, X , Y, N ⟩ with initial state σ1 . The aim is to reach the goal state G while collecting treasures. The reward Y is 1 for collecting a treasure (f) and for reaching G, and 0 otherwise. A treasure disappears when the agent steps on it, making it impossible to collect the reward twice. We decompose M by defining high-level states S = {1, 2, 3, 4} for each room, and subproblems for reaching a terminal state among G, L, R, T, B inside a room. The subproblems include the location of treasures and have the same dynamics as the interior of each room. Figure 1b) shows the subproblem state corresponding to room 3. The local reward Rk is 1 for collecting a treasure and for reaching the correct terminal state, and 0 otherwise. The function f is not injective: both (1, B) and (3, s) map to state σ. Since σ is in room 3, g(σ) = 3 and g(σ) = s. We can use f to model that some terminal states are not available in a room, e.g. in room 3, reaching terminal state L causes the agent to move to the state σℓ = f (3, L). The goal state G is absorbing, but the agent can only achieve a reward of 1 the first time it observes G. The same is true of the terminal states of the subproblems. Sufficient conditions for PAC-Learnability. Since Mπ depends on the subproblem policies π, the SMDP learning problem is non-stationary [Nachum et al., 2018]. Two ingredients are necessary for the SMDP problem to be PAC-learnable. First, the optimal SMDP value function V ∗ has to be ∗ unique, else the difference |V1∗ (σ1 ) − V1πb ,bπ (σ1 )| is ambiguous. Hence the SMDP dynamics P π ∗ and Rπ of the optimal subproblem policies π ∗ have to be unique. Second, making progress towards ∗ ∗ π ∗ should also make progress towards estimating P π and Rπ , else a subproblem policy π may be π,π arbitrarily close to solving the subproblems, but V can still be very different from V ∗ for any π. We introduce two conditions that are sufficient to ensure that the SMDP problem is PAC-learnable. Assumption 3.1. For each subproblem k, each optimal policy π ∗,k for k, each other policy π k and each state pair (s, s1 ) ∈ S × S it holds that ∗,k

Pπ1:H+1 (·|s1 ) − Pπ1:H+1 (·|s1 ) 1 ≤ 2 V1π (s1 ; Rk ) − V1π k

V1π (s1 ; Ys ) − V1π

∗,k

(s1 ; Ys ) ≤ V1π (s1 ; Rk ) − V1π

∗,k

(s1 ; Rk ) ,

(s1 ; Rk ) .

These conditions achieve both criteria. If there are two optimal subproblem policies π1∗ and π2∗ , the ∗ ∗ ∗ ∗ conditions ensure that P π1 = P π2 and Rπ1 = Rπ2 . If a subproblem policy π is close to solving ∗ ∗ the subproblems, the right-hand side is small, implying that P π and Rπ tend towards P π and Rπ . In Appendix B we prove the following proposition about the SMDP example in Figure 1. Proposition 3.2. Assume that the subproblem horizon H is large enough for each optimal subproblem policy to collect all treasures in a room and reach the correct terminal state with probability 1. Then the SMDP example in Figure 1 satisfies Assumption 3.1. 5

Input: Parameters ε, δ, MDPs M, {Mk }k∈JKK , states S, functions f , g, g, horizons H, H Initialize t ← −1 and N 0 (s, a, s′ ) ← 0 for each s, a, s′ ∈ S × A × S repeat t←t+1 b t,k ← apply BPI(N t , H, Rk , δ) for each k ∈ JKK π t+1,k , L t+1 b t,π , R b t,πt+1 ← compute the empirical SMDP dynamics of the subproblem policies π t+1 P π t+1 , V t , Lt ← compute the value function upper bound in (5) and the error function in (6) use π t+1 , π t+1 to collect an episode and update N t+1 until Lt1 (σ1 ) ≤ ε/(6HH) return π t+1 , π t+1 Algorithm 1: HBPI-UCRL. To illustrate our conditions, we provide several examples of SMDPs that do not satisfy them. Assume that a subproblem Mk has two terminal states s∗1 and s∗2 with associated rewards 1 and 0.99. A subproblem policy π k that reaches s∗2 achieves almost the same value as an optimal policy π ∗,k that k ∗,k reaches s∗1 , but Pπ1:H+1 is completely different from Pπ1:H+1 . Next assume that a subproblem Mk has a single terminal state s∗ which is reached with probability p from s1 by an optimal policy π ∗,k . The k ∗,k difference ∥Pπ1:H+1 (·|s1 ) − Pπ1:H+1 (·|s1 )∥1 of a policy π k that reaches s∗ with probability q from s1 k ∗,k can be as large as 2(1−q), which can be arbitrarily larger than V1π (s1 ; Rk )−V1π (s1 ; Rk ) = p−q. A concrete example of such a policy is one that “gives up” once it cannot reach the terminal state and instead wanders in a different direction. A third example is one where the MDP rewards Y and subproblem rewards Rk are non-zero for different non-terminal states of a subproblem Mk . In this case, two policies can both be optimal for subproblem Mk but collect different amounts of reward under Y. To the best of our knowledge, these issues have been ignored in previous work on parallel HRL, and we believe that our conditions consistute a major contribution in this regard, since without such conditions the parallel HRL learning problem does not have a well-defined solution. We remark that our conditions are strictly weaker than those of Drappo et al. [2025] who assume a single terminal state reached with probability one and zero reward for non-terminal states.

The HBPI-UCRL Algorithm

We now present HBPI-UCRL, a novel model-based algorithm for HRL in episodic SMDPs. Intuitively, the algorithm performs best policy identification on both levels of the hierarchy, using carefully tailored confidence bounds on the empirical estimates of SMDP transitions. In each episode t, t the learner uses a hierarchical policy (π t , π t ) to generate a state sequence σ1:HH+1 . Let π t,h ≡ t π t,πh (σH(h−1)+1 ) be the subproblem policy selected by π t at each h ∈ JHK, and let st,h 1:H+1 be the resulting subproblem state sequence. The counts and empirical transition probabilities are given by N t (s, a, s′ ) =

t X H X H X

ℓ,h ℓ,h I((s, a, s′ ) = (sℓ,h h , ah , sh+1 )),

ℓ=1 h=1 h=1

t ′ bt (s′ |s, a) = PN (s, a, s ) , P t ′ s′ N (s, a, s )

t,h ℓ,h where aℓ,h h = πh (sh ). The event E in (1) still holds with probability P(E) ≥ 1−δ/2. HBPI-UCRL t bt

exploits that all uncertainty can be expressed in terms of the counts N and the estimate P of P.

Algorithm 1 provides pseudo-code for HBPI-UCRL. The input is the parameters ε, δ, the MDP M, the subproblems Mk , k ∈ JKK, and the hierarchy in the form of SMDP states S, functions f , g and g and horizons H, H. In each episode t, HBPI-UCRL performs best policy identification for each subproblem k. Concretely, the algorithm computes the confidence bounds C t in (2) and the upper confidence bound V t,k in (3) for each k, replacing R with the local reward function Rk . The policy π t+1,k is selected as the greedy policy for V t,k . Given π t+1 , the algorithm also computes the b t,πt+1 and R b t,πt+1 for π t+1 . b t,k in (4) for each k and the empirical SMDP dynamics P function L h To select the SMDP policy π t+1 , HBPI-UCRL computes an SMDP value function V t . In Appendix D we show that V t upper bounds V ∗ under event E and Assumption 3.1. We define confidence sets as n o b t,πt+1 (·|σ, k) ≤ 5H L b t,k (g(σ)) C t (σ, k) = p ∈ ∆(Σ) p − P ∀(σ, k). 1 1 6

t An upper confidence bound V t can now be recursively defined for each σ ∈ Σ as V H+1 (σ) = 0 and h h ii X t+1 ′ t ′ b t,π (σ, k) + 3H L b t,k (g(σ)) + max V ht (σ) = max min HH, R p(σ )V (σ ) . (5) h+1 1 t k

p∈C (σ,k)

σ′

The policy π t+1 is selected as the greedy policy for V t . For each h and σ we define the transition kernel for π t+1 that achieves the maximum over C t in (5) as X t Pht (· |σ) = arg max p(σ ′ )V h+1 (σ ′ ). t+1 p∈C t (σ,πh

(σ))

σ′

We next define an SMDP error function L recursively for each σ as LtH+1 (σ) = 0 and h i X Lth (σ) = min 2, Bht (σ) + Pht (σ ′ |σ)Lth+1 (σ ′ ) ∀h ∈ JHK,

(6)

σ′

t+1

t b t,πh (σ) (g(σ)). The stopping criterion of HBPI-UCRL is defined as τ = where Bh (σ) t≡ 10H L1 inf t ∈ N : L1 (σ1 ) ≤ ε/(6HH) . Upon stopping, HBPI-UCRL returns (π τ +1 , π τ +1 ).

General analysis of HBPI-UCRL. The following theorem provides a sample complexity upper bound for the novel algorithm HBPI-UCRL. Theorem 4.1. Under Assumption 3.1, with probability larger than 1 − δ HBPI-UCRL returns a hierarchical policy (b π, π b) such that ∥V1∗ (σ1 ) − V1πb ,bπ (σ1 )∥1 ≤ ε using a number of episodes SAH 4 H 6 SAH 5 H 7 SAHH SAHH τ =O log + S log log . ε2 δ ε2 δ The proof appears in Appendix E. If we apply BPI-UCRL to solve the flat MDP M, we obtain a 4 2 4 4 2 e e sample complexity bound of order O(|Σ|AN /ε ) = O(SSAH H /ε ) in the regime of small δ. Hence HBPI-UCRL is more sample efficient if H 2 < S, though we recall that the optimal policy for M is in general different from the optimal hierarchical policy (π ∗ , π ∗ ). HBPI-UCRL for Sparse-Reward SMDPs. We next show that in sparse-reward SMDPs, a modified version of HBPI-UCRL achieves a lower sample complexity. An SMDP Mπ is sparse-reward if both the flat MDP M and the subproblems Mk , k ∈ JKK, are sparse-reward. In Appendix B we prove that the SMDP example in Figure 1 is sparse-reward if we remove all treasures. To adapt HBPI-UCRL to sparse-reward SMDPs, we modify the algorithm in several ways. We first t redefine the upper confidence bound of the value function as V H+1 (σ) = 0 and h h ii X t+1 t ′ ′ b t,π (σ, k) + 3L b t,k (g(σ)) + max V ht (σ) = max min 1, R (σ ) , p(σ )V h+1 1 t k

p∈C (σ,k)

n C t (σ, k) = p ∈ ∆(Σ)

b t,πt+1

p−P

(·|σ, k)

b t,k (g(σ)) ≤ 5L 1 1

σ′

∀(σ, k).

Compared to (5), the confidence bound C t is tighter, and the value function upper bound takes the minimum with 1 instead of the minimum with HH. In Appendix F we prove that the new definition of V t is an upper bound on V ∗ for sparse-reward SMDPs under event E and Assumption 3.1. We t+1 b t,πh (σ) (g(σ)) and we modify the stopping criterion to be Lt (σ1 ) ≤ ε/6. redefine B t (σ) ≡ 10L h

In Appendix F we prove the following theorem. Theorem 4.2. For sparse-reward SMDPs, under Assumption 3.1, w.p. at least 1 − δ the modified HBPI-UCRL returns (b π, π b) such that ∥V1∗ (σ1 ) − V1πb ,bπ (σ1 )∥1 ≤ ε using a number of episodes SAH 2 H 2 SAH 3 H 3 SAHH SAHH τ =O log + S log log . 2 2 ε δ ε δ 2 2 2 e In comparison, the sample complexity of BPI-UCRL is O(SSAH H /ε ) for sparse-reward M in the small δ regime. Hence the sample complexity of HBPI-UCRL is a factor S smaller, and only a factor H 2 larger than that of BPI-UCRL when applied to a single sparse-reward subproblem Mk .

Related Work

Several authors have studied the sample complexity [Brunskill and Li, 2014] or regret [Drappo et al., 2023, Fruit et al., 2017] of HRL when the optimal subproblem policies are given as prior knowledge. Nachum et al. [2019] study representations that bound the suboptimality gap between the optimal flat policy and the optimal SMDP policy. Kuric et al. [2024] present an algorithm that provably converges to a hierarchical policy equivalent to the optimal flat policy. Recent works analyze the setting in which the SMDP and subproblem policies are learned in parallel. The focus of prior work is often on regret, and we believe that ours is the first sample complexity upper bound for parallel HRL policy learning. While we propose general conditions for efficient HRL, most existing works define SMDPs specifically for goal-oriented episodic tasks [Wen et al., 2020, Robert et al., 2023, Drappo et al., 2025]. Drappo et al. [2024] analyze the regret in a more general HRL framework, but the regret depends on the concentrability coefficients at the SMDP and subproblem levels, and the authors do not make any attempt to bound these coefficients. Manenti and Ianelli [2025] prove that Q-learning converges in the parallel HRL setting, but do not show that the optimal SMDP value function is unique. Wen et al. [2020] use posterior sampling to exploit a hierarchical structure and prove a bound on the Bayesian regret of the resulting algorithm in which the size of the state space is replaced by the size of the subproblem state space. Due to the Bayesian nature of this result, it is not possible to derive an (ε, δ)-PAC algorithm from their regret in our frequentist setting. Moreover, the algorithm that achieves their regret result does not learn a hierarchical policy. The work of Drappo et al. [2025] is more similar to ours in spirit, despite their focus on regret. Indeed, they also use an optimistic approach to learn the subproblem policies, but they build a quite different upper bound on the value of their high-level policy tailored to the goal-oriented setting. They assume that the next high-level state after solving a subproblem is known, which allows to obtain an efficient algorithm by storing high-level states only. Note that this approach cannot solve the example in Figure 1. Using the regret-to-PAC conversion [Jin et al., 2018], which runs their algorithm for a large enough T and outputs the hierarchical policy used in a random episode in {1, . . . , T }, one can 2 2 e prove that choosing T = O(SAKHH/(ε δ )) yields an (ε, δ)-PAC policy. Compared to this bound, our bound shaves off a factor K, which comes from the fact that their setting considers different possible state spaces for each subproblem (e.g. different room shapes but with the transitions all inherited from the underlying flat MDP). Our worse scaling in the horizons can be explained by two things. The improvement in H comes from the fact that their regret minizer is UCBVI with Bernstein bonuses [Azar et al., 2017], analyzed in the special case of sparse reward. Regarding our extra H factor, it is mitigated by the fact that their setting is slightly different, as their algorithm terminates an episode early when a subgoal is not reached by the current subproblem policy. Hence some of their episodes could contain only one low-level episode, which implies that the number of episodes has to be multiplied by H. In contrast, HBPI-UCRL never terminates an episode early. Besides the fact that our algorithm is not specific to the goal-oriented setting, the main improvement in our bound is the dependency in δ, which comes from our data-dependent stopping rule (a non-trivial component of HBPI-UCRL) instead of a deterministic sample size T fixed in advance. The work of Robert et al. [2023] considers a slightly different sample complexity: following Kakade [2003], their sample complexity is defined as the number of episodes collected using a policy that is not ε-optimal. Still, their lower bound also applies to our notion of sample complexity. Their main result states that any HRL algorithm needs a number of samples of order Ω(max(SAKH 2 /ε2 , SKH 2 /ε2 )), which is inconsistent with our sample complexity upper bounds in Theorems 4.1 and 4.2. In the first term, the additional factor K is due to the fact that unlike us, they do not assume that subproblems share the transition kernel. However, we believe that the second term only applies to a slightly different setting, in which the HRL algorithm has to sample high-level transitions and rewards. In contrast, we exploit the fact that high-level transitions and rewards are fully determined by the subproblem policies and the subproblem dynamics.

Numerical Experiments

In this section we present results from numerical experiments with episodic (S)MDPs. The aim is to show that HBPI-UCRL is more sample efficient in practice than BPI-UCRL [Kaufmann et al., 2021]. 8

(a) Stopping time τ as a function of S.

(b) Unverifiable stopping time as a function of S.

Figure 2: Stopping time of BPI-UCRL and HBPI-UCRL as functions of the number of high-level states S: (a) using the stopping criterion; (b) unverifiable by the algorithms but observed in practice. We carry out experiments on a deterministic version of the SMDP in Figure 1 with treasures removed, varying the size of each room and the number of rooms. Hence the SMDPs are sparse-reward and aim to reach the goal G. Implementation details and additional experimental results in domains with treasures and stochastic transitions can be found in Appendix I. In particular, some randomness is introduced by the use of a random initial state in each episode, and we perform experiments (that are very costly) with three different seeds, with the shaded area indicating the standard deviation. Figure 2a shows the stopping time τ of BPI-UCRL and HBPI-UCRL as functions of the number of high-level states S for rooms of size 3 × √ 3, varying the number of rooms from 2 × 2 to 18 × 18 and setting the SMDP horizon to H = 2 S. BPI becomes too slow for 11 × 11 rooms, and the broken line from√10 × 10 to 18 × 18 is an interpolation. The stopping time of HBPI-UCRL is clearly proportional to S, which validates our theory and indicates that a sample complexity of order 2 e O(SAHH/ε ) is possible for sparse SMDPs with a tighter analysis (i.e. independent of S but linear √ in H ∝ S). The stopping time of BPI-UCRL is clearly not sublinear in S. We carry out several ablations in Appendix I to separately test the impact of H and S on the sample complexity. t+1

t+1

Figure 2b reports the last episode t for which |V1∗ (σ1 ) − V1π ,π (σ1 )| > ε, for both BPI-UCRL and HBPI-UCRL. From that point on the algorithms keep using an ε optimal policy and have therefore identified one, but without being able to certify it. This quantity is related to the notion of unverifiable sample complexity introduced by Katz-Samuels and Jamieson [2020] for pure exploration in bandits. We remark an interesting phenomenon: Although the theoretical stopping time of HBPI-UCRL is larger than that of BPI-UCRL for small values of S, in practice it needs fewer episodes to converge. This experiment also reveals that the stopping time based on Hoeffding bounds is not tight.

Discussion

There are several possible extensions of our work, and here we mention a few. One such extension is to define the SMDP policy and value function on high-level states rather than full states, as is common in the HRL literature. The challenge in this setting is that the initial state of each subproblem is not fully determined, which makes it harder to formalize and analyze the SMDP dynamics. A related question is how to adapt Assumption 3.1 to make it more general. We have not fully characterized the class of HRL problems that satisfy the assumptions, but all known examples involve optimal subproblem policies that terminate in a single state with probability 1. Either HRL is sample efficient only in the case of goal-directed subproblems (which would be a contribution in its own right), or researchers have to propose other conditions that cause HRL to be PAC-learnable. 9

In our work, all subproblems share the transition dynamics, but this is not always the case. An open research question is how to extend HBPI-UCRL to SMDPs whose subproblems have different transition dynamics, or subproblems that belong to one of several equivalence classes. Finally, an interesting direction for future work is to extend HBPI-UCRL to the infinite-horizon setting.

References M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, C. Fu, K. Gopalakrishnan, K. Hausman, A. Herzog, D. Ho, J. Hsu, J. Ibarz, B. Ichter, A. Irpan, E. Jang, R. J. Ruano, K. Jeffrey, S. Jesmonth, N. Joshi, R. Julian, D. Kalashnikov, Y. Kuang, K.-H. Lee, S. Levine, Y. Lu, L. Luu, C. Parada, P. Pastor, J. Quiambao, K. Rao, J. Rettinghouse, D. Reyes, P. Sermanet, N. Sievers, C. Tan, A. Toshev, V. Vanhoucke, F. Xia, T. Xiao, P. Xu, S. Xu, M. Yan, and A. Zeng. Do As I Can and Not As I Say: Grounding Language in Robotic Affordances. In Conference on Robot Learning, 2022. M. Gheshlaghi Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, (ICML) 2017, 2017. M. G. Bellemare, S. Candido, P. S. Castro, J. Gong, M. C. Machado, S. Moitra, S. S. Ponda, and Z. Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588:77–82, 2020. E. Brunskill and L. Li. PAC-Inspired Option Discovery in Lifelong Reinforcement Learning. In International Conference on Machine Learning, pages 316–324, 2014. C. Dann, T. Lattimore, and E. Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Neural Information Processing Systems, pages 5713–5723, 2017. C. Dann, L. Li, W. Wei, and E. Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, 2019. G. Drappo, A. M. Metelli, and M. Restelli. An option-dependent analysis of regret minimization algorithms in finite-horizon semi-MDP. Transactions on Machine Learning Research, pages 1–24, 2023. G. Drappo, A. M. Metelli, and R. Marcello. A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning. Reinforcement Learning Journal, 2:819–839, 2024. G. Drappo, A. Robert, M. Restelli, A. A. Faisal, A. M. Metelli, and C. Pike-Burke. Efficient Exploitation of Hierarchical Structure in Sparse Reward Reinforcement Learning. In International Conference on Artificial Intelligence and Statistics, pages 2269–2277, 2025. R. Fruit, M. Pirotta, A. Lazaric, and E. Brunskill. Regret Minimization in MDPs with Options without Prior Knowledge. In Neural Information Processing Systems, 2017. N. Gopalan, M. desJardins, M. Littman, J. MacGlashan, S. Squire, S. Tellex, J. Winder, and L. Wong. Planning with Abstract Markov Decision Processes. In International Conference on Automated Planning and Scheduling, 2017. T. Jaksch, R. Ortner, and P. Auer. Near-optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11:1563–1600, 2010. C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-Learning Provably Efficient? In Advances in Neural Information Processing Systems, 2018. A. Jonsson, E. Kaufmann, P. Ménard, O. Darwiche Domingues, E. Leurent, and M. Valko. Planning in Markov Decision Processes with Gap-Dependent Sample Complexity. In Neural Information Processing Systems, 2020. S. Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, 2003. Julian Katz-Samuels and Kevin Jamieson. The true sample complexity of identifying good arms. In AISTATS, 2020. E. Kaufmann, P. Ménard, O. Darwiche Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive Reward-Free Exploration. In Algorithmic Learning Theory, pages 865–891, 2021. G. Konidaris and A. Barto. Skill Discovery in Continuous Reinforcement Learning Domains using Skill Chaining. In Neural Information Processing Systems, 2009. 11

D. Kuric, G. Infante, V. Gómez, A. Jonsson, and H. van Hoof. Planning with a Learned Policy Basis to Optimally Solve Complex Tasks. In International Conference on Automated Planning and Scheduling, 2024. A. Levy, G. Konidaris, R. Platt, and K. Saenko. Learning Multi-Level Hierarchies with Hindsight. In International Conference on Learning Representations, 2019. M. C. Machado, A. Barreto, D. Precup, and M. Bowling. Temporal Abstraction in Reinforcement Learning with the Successor Representation. Journal of Machine Learning Research, 24(80):1–69, 2022. M. Manenti and A. Ianelli. An ODE method approach for proving convergence and stability of Q-learning in Hierarchical Reinforcement Learning. In Workshop on Dynamics at the Frontiers of Optimization, Sampling, and Games at NeurIPS@26, 2025. M. Matthews, M. Samvelyan, J. Parker-Holder, E. Grefenstette, and T. Rocktäsche1. Hierarchical Kickstarting for Skill Transfer in Reinforcement Learning. In Conference on Lifelong Learning Agents, 2022. O. Nachum, S. Gu, H. Lee, and S. Levine. Data-efficient hierarchical reinforcement learning. In Neural Information Processing Systems, 2018. O. Nachum, S. Gu, H. Lee, and S. Levine. Near-Optimal Representation Learning for Hierarchical Reinforcement Learning. In International Conference on Learning Representations, 2019. J. Rafati and D. C. Noelle. Learning Representations in Model-Free Hierarchical Reinforcement Learning. In AAAI Conference on Artificial Intelligence, 2019. A. Robert, C. Pike-Burke, and A. A. Faisal. Sample Complexity of Goal-Conditioned Hierarchical Reinforcement Learning. In Neural Information Processing Systems, 2023. A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. FeUdal Networks for Hierarchical Reinforcement Learning. In International Conference on Machine Learning, 2017. Z. Wen, D. Precup, M. Ibrahimi, A. Barreto, B. Van Roy, and S. Singh. On Efficiency in Hierarchical Reinforcement Learning. In Neural Information Processing Systems, 2020.

Supplementary Materials 1

Introduction

Reinforcement Learning

Hierarchical Reinforcement Learning

4 The HBPI-UCRL Algorithm

Related Work

Numerical Experiments

Discussion

A Equivalent Definitions of Recursive Functions

B Properties of the SMDP Example

C Proof of Theorem 2.1

D The Value Function Upper Bound

E Proof of Theorem 4.1

F Proof of Theorem 4.2

G On High-Probability Events

H A Technical Lemma

Experimental Settings and Additional Results

Equivalent Definitions of Recursive Functions

In this appendix we prove the following lemma, which states that our composite probability distributions allow us to express equivalent definitions of recursive functions. Lemma A.1. Given a policy π, let {fh }h∈JHK and {ghπ }h∈JH+1K be sets of functions fh : S ×A → R and ghπ : S → R. The following three definitions of ghπ are equivalent for each sh if we assume π gH+1 (sh ) = 0: X π ghπ (sh ) = fh (sh , πh (sh )) + Phπ (s′ |sh )gh+1 (s′ ), s′

ghπ (sh ) =

π Ph:H+1 (sh+1:H+1 |sh )

sh+1:H+1

ghπ (sh ) =

H X X

H X

fi (si , πi (si )),

i=h

Pπh:i (si |sh )fi (si , πi (si )).

i=h si

The proof is by induction, with the base case given by h = H. In this case, each of the three definitions can be written as π gH (sH ) = fH (sH , πH (sH )) + 0 = fH (sH , πH (sH )), π gH (sH ) =

π PH:H+1 (sH+1:H+1 |sH )

sH+1:H+1

H X

fi (si , πi (si ))

i=H

= fH (sH , πH (sH ))

π PH (sH+1 |sH ) = fH (sH , πH (sH )),

sH+1 π gH (sH ) =

H X X

PπH:i (si |sH )fi (si , πi (si )) =

i=H si

I(si = sH )fi (si , πi (si )) = fH (sH , πH (sH )),

π where we have used the definitions of PH:H+1 and PπH:H .

The inductive case is given by h ∈ JH − 1K. We show that the second and third definitions are equivalent to the first. The second definition can be written X

ghπ (sh ) =

π Ph:H+1 (sh+1:H+1 |sh )

sh+1:H+1

H X

fi (si , πi (si ))

i=h

= fh (sh , πh (sh ))

π Ph:H+1 (sh+1:H+1 |sh )

sh+1:H+1

π Phπ (sh+1 |sh ) Ph+1:H+1 (sh+2:H+1 |sh+1 )

sh+1:H+1

H X

fi (si , πi (si ))

i=h+1

= fh (sh , πh (sh )) +

X sh+1

= fh (sh , πh (sh )) +

Phπ (sh+1 |sh )

π Ph+1:H+1 (sh+2:H+1 |sh+1 )

sh+2:H+1

H X

fi (si , πi (si ))

i=h+1

π Phπ (sh+1 |sh )gh+1 (sh+1 ),

sh+1

P π where we have used the equality sh+1:H+1 Ph:H+1 (sh+1:H+1 |sh ) = 1, the recursive definition of π Ph:H+1 and the inductive hypothesis. The third definition can be written ghπ (sh ) =

H X X

Pπh:i (si |sh )fi (si , πi (si ))

i=h si

X si

I(si = sh )fi (si , πi (si )) +

H X XX i=h+1 si sh+1

Phπ (sh+1 |sh )Pπh+1:i (si |sh+1 )fi (si , πi (si ))

= fh (sh , πh (sh )) +

X sh+1

= fh (sh , πh (sh )) +

H X X

Phπ (sh+1 |sh )

Pπh+1:i (si |sh+1 )fi (si , πi (si ))

i=h+1 si π Phπ (sh+1 |sh )gh+1 (sh+1 ),

sh+1

where we have used the definition of Pπh:h , the recursive definition of Pπh:i and the inductive hypothesis. This proves that the three definitions are equivalent.

Properties of the SMDP Example

In this section we prove Propositions 3.2 and B.1 given below, which state that the SMDP example in Figure 1 satisfies various assumptions. Proposition B.1. Assume that the subproblem horizon H is large enough for each optimal subproblem policy to reach the correct terminal state with probability 1. Then the SMDP example in Figure 1 with all treasures removed is sparse-reward and satisfies Assumption 3.1. We first show that if the subproblem horizon H is large enough for each optimal subproblem policy to collect all treasures and reach the correct terminal state s∗ with probability 1, then the first condition of the assumption holds. If a subproblem has m treasures, then the value of the optimal subproblem ∗,k policy π ∗,k in any non-terminal state s is V1π (s; Rk ) = m + 1. Any subproblem policy π k k ∗,k whose value is at most m satisfies the first condition since 2|V1π (s; Rk ) − V1π (s; Rk )| ≥ 2 ≥ k ∗,k k ∥Pπ1:H+1 (·|s) − Pπ1:H+1 (·|s)∥1 . If π k has value V1π (s; Rk ) > m, it reaches s∗ with probability at k k ∗,k k ∗,k least V1π (s; Rk ) − m, implying ∥Pπ1:H+1 (·|s) − Pπ1:H+1 (·|s)∥1 ≤ 2|V1π (s; Rk ) − V1π (s; Rk )|. We next show that under the same condition, the SMDP example in Figure 1 satisfies the second condition of the assumption. Recall that the reward functions Ys and Rk are the same for all nonterminal states of a subproblem k and all high-level states s. If a subproblem has m treasures, then ∗,k ∗,k the optimal subproblem policy π ∗,k satisfies V1π (s; Ys ) = m and V1π (s; Rk ) = m + 1. If k the value of a subproblem policy π k under Ys is V1π (s; Ys ) = ℓ, then the value under Rk can be k ∗,k k at most V1π (s; Rk ) = ℓ + 1, implying |V1π (s; Rk ) − V1π (s; Rk )| ≥ m − ℓ. Hence we have k ∗,k ∗,k k |V1π (s1 ; Ys ) − V1π (s1 ; Ys )| = m − ℓ ≤ |V1π (s; Rk ) − V1π (s; Rk )|, which satisfies the second condition. Taken together, these two results are enough to prove Proposition 3.2. To prove Proposition B.1, note that even if we remove all treasures, the reasoning above still holds. Specifically, this implies that Assumption 3.1 is satisfied. If we remove all treasures, the only available reward is 1 for reaching G the first time in the case of M, and 1 for reaching the correct terminal state the first time in the case of Mk . Hence the flat MDP M and the subproblems Mk , k ∈ JKK, are all sparse-reward, which is precisely the definition of a sparse-reward SMDP.

Proof of Theorem 2.1

In this appendix we prove Theorem 2.1, which states an upper bound on the sample complexity of b t but associated with the true BPI-UCRL. We first introduce an error function Lt analogous to L π t+1 t+1 t transition kernel P of π . The function L is recursively defined as LtH+1 (s) = 0 and X t+1 Lth (s) = B t (s, πht+1 (s)) + Phπ (s′ |s)Lth+1 (s′ ) ∀h ∈ JHK.

s′ t,π t We also define Bh (s) ≡ B (s, πh (s)) for each policy π and step h.

The following lemma bounds the L1-norm of the difference between the composite distributions bt,πt+1 and those induced by any transition kernel for π t+1 in the confidence sets C t . induced by P t+1

t+1

Lemma C.1. Let {Qπh }h∈JHK be a transition kernel for π t+1 s.t. Qπh (·|sh ) ∈ C t (sh , πht+1 (sh )) t+1 π t+1 for each h and sh , and let Qi:j and Qπi:j be its composite distributions. Under event E we have t+1

π t+1 b t,π (·|sh ) ≤ L b th (sh ) ≤ 3Lth (sh ), Qh:H+1 (·|sh ) − P h:H+1 1

t+1

bt,π (·|sh ) ≤ L b th (sh ) ≤ 3Lth (sh ). Qπh:H+1 (·|sh ) − P h:H+1 1 t+1

t+1

H:H+1

t+1 t+1 π t+1 QH:H+1 (·|sH ) = QπH:H+1 (·|sH ) = QπH (·|sH ),

h i t+1 t+1 b t (sH ) = min 2, B t,π (sH ) + 0 = B t,π (sH ), L H H H t,π since BH

t+1

(sH ) already involves a minimum with 2. Consequently we can write t+1

π t+1 b t,π QH:H+1 (·|sH ) − P H:H+1 (·|sH )

t,π ≤ BH

t+1

bt,π (·|sH ) − P H

t+1

b tH (sH ), (sH ) = L

= QπH

(·|sH )

t+1

t+1 where the inequality follows from the fact that QπH (·|sH ) belongs to C t (sH , πH (sH )). The proof t+1 t+1 t,π π b for ∥Q (·|sH ) − P (·|sH )∥1 is identical. In the inductive case h ∈ JH − 1K we have H:H+1

H:H+1

π t+1 b t,πt+1 (·|sh ) Qh:H+1 (·|sh ) − P h:H+1

t+1

π b t,π (sh+1:H+1 |sh ) Qh:H+1 (sh+1:H+1 |sh ) − P h:H+1

sh+1:H+1

t+1 t+1 π t+1 π t+1 bt,π (sh+1 |sh )Qh+1:H+1 Qπh (sh+1 |sh )Qh+1:H+1 (sh+2:H+1 |sh+1 ) − P (sh+2:H+1 |sh+1 ) h

≤(a)

sh+1:H+1

bt,π P h

t+1

π bt,π (sh+1 |sh )Qh+1:H+1 (sh+2:H+1 |sh+1 ) − P h

t+1

b t,π (sh+1 |sh )P h+1:H+1 (sh+2:H+1 |sh+1 )

sh+1:H+1

=(b)

Qπh

t+1

bt,π (sh+1 |sh ) − P h

t+1

(sh+1 |sh )

sh+1

t+1

π Qh+1:H+1 (sh+2:H+1 |sh+1 )

sh+2:H+1

t+1 π t+1 b t,πt+1 (sh+2:H+1 |sh+1 ) bt,π (sh+1 |sh ) + P Qh+1:H+1 (sh+2:H+1 |sh+1 ) − P h h+1:H+1 sh+1 sh+2:H+1

=(c) Qπh

t+1

≤(d) Bht,π

t+1

bt,π (·|sh ) − P h (sh ) +

t+1

(·|sh ) +

bt,π P h

t+1

bt,π P h

t+1

π π (sh+1 |sh ) Qh+1:H+1 (·|sh+1 ) − Ph+1:H+1 (·|sh+1 )

sh+1

b th+1 (sh+1 ) ≡ Z bht (sh ). (sh+1 |sh )L

sh+1 t+1

π t+1 b t,π In (a) we use the definition of Qh:H+1 and P h:H+1 and the triangle inequality, in (b) we use the equality |ab − ac| = a|b − c| for a ≥ 0, in (c) we use the definition of the L1-norm and the equality P π t+1 π t+1 (·|sh ) belongs to sh+2:H+1 Qh+1:H+1 (sh+2:H+1 |sh+1 ) = 1, and in (d) we use the fact that Qh C t (sh , πht+1 (sh )) and the inductive hypothesis for h + 1. Since the trivial bound 2 also applies, we obtain h i t+1 π t+1 b t,π (·|sh ) ≤ min 2, Zbt (sh ) = L b th (sh ). Qh:H+1 (·|sh ) − P h h:H+1 1

t+1

bt,π (·|sh )∥1 is very similar: The proof for ∥Qπh:H+1 (·|sh ) − P h:H+1 t+1

t+1

bt,π (·|sh ) Qπh:H+1 (·|sh ) − P h:H+1 ≤(a)

X X

= 1

t+1

bt,π (sH+1 |sh ) Qπh:H+1 (sH+1 |sh ) − P h:H+1

sH+1

t+1 t+1 t+1 t+1 bt,π (sh+1 |sh )Qπh+1:H+1 (sH+1 |sh+1 ) Qπh (sh+1 |sh )Qπh+1:H+1 (sH+1 |sh+1 ) − P h

sH+1 sh+1

X X

bt,π P h

t+1

bt,π (sh+1 |sh )Qπh+1:H+1 (sH+1 |sh+1 ) − P h

t+1

sH+1 sh+1

=(b)

X sh+1

Qπh

t+1

bt,π (sh+1 |sh ) − P h

t+1

(sh+1 |sh )

X sH+1

t+1

bt,π (sh+1 |sh )P h+1:H+1 (sH+1 |sh+1 )

Qπh+1:H+1 (sH+1 |sh+1 )

bt,π P h

t+1

(sh+1 |sh )

t+1

X sH+1

sh+1

t+1 t+1 bt,π (·|sh ) Qπh (·|sh ) − P h

=(c)

≤(d) Bht,π

t+1

bt,π Qπh+1:H+1 (sH+1 |sh+1 ) − P h+1:H+1 (sH+1 |sh+1 )

t+1

(sh ) +

bt,π P h

t+1

+ 1

bt,π P h

t+1

(·|sh ) Qπh+1:H+1 (·|sh+1 ) − Pπh+1:H+1 (·|sh+1 )

sh+1

b th+1 (sh+1 ) = Z bht (sh ). (·|sh )L

sh+1

b t (s)−Lt (s) ≤ 2Lt (s). The base case is h = H, in which case We next prove by induction on h that L h h h t+1 t+1 b t (s) = min[2, B t,π (sH )] = B t,π (sH ) = Lt (s), implying L b t (s) − Lt (s) = 0 ≤ 2Lt (s). L H H H H H H H The inductive case is h ∈ JH − 1K. Due to Lemma A.1, an alternative definition of Lth is given by H X X

Lth (s) =

t+1

Pπh:i (si |s)Bit,π

t+1

(si ).

i=h si

We can now write b th (s) − Lth (s) ≤ B t,π L h

t+1

(sh ) +

bt,π P h

t+1

b th+1 (s′ ) − B t,π (s′ |s)L h

t+1

(sh ) −

s′

Phπ

t+1

(s′ |s)Lth+1 (s′ )

s′

X t,πt+1 ′ X πt+1 ′ t t+1 b b th+1 (s′ ) + b h+1 (s′ ) − Lth+1 (s′ ) P (s |s) − Phπ (s′ |s) L Ph (s |s) L h

s′

bt,π ≤(a) 2 P h

≤(b) 2

t+1

(·|s) − Phπ

t+1

Pπh:h (si |s)Bit,π

(·|s)

+2 1

t+1

Phπ

t+1

(s′ |s)

s′

H X X

t+1

Pπh+1:i (si |s′ )Bit,π

t+1

(si )

i=h+1 si

H X X

(si ) + 2

t+1

Pπh:i (si |s)Bit,π

t+1

(si )

i=h+1 si

H X X

t+1

Pπh:i (si |s)Bit,π

t+1

(si ) = 2Lth (s).

i=h si

b t (s′ ) ≤ 2, the inductive hypothesis and the alternative definition In (a) we use the upper bound L h+1 t+1 of Lth+1 (s′ ). In (b) we use event E, the definition Pπh:h (si |s) = I(s = si ) and change the order of P t+1 t+1 t+1 summation to obtain s′ Phπ (s′ |s)Pπh+1:i (si |s′ ) = Pπh:i (si |s). Finally we identify the alternative b t (s) − Lt (s) ≤ 2Lt (s), it follows that L b t (s) = L b t (s) − Lt (s) + definition of Lth (s). Since L h h h h h h t t Lh (s) ≤ 3Lh (s). This concludes the proof of the lemma. We next prove that BPI-UCRL outputs an ε-optimal policy. To do so, let Pht (·|s, a) = P t arg maxp∈C t (s,a) s′ p(s′ )Vh+1 (s′ ; R) be the transition kernel that achieves the maximum over C t (s, a) in (3) for each h and (s, a), and let Pht,π (s′ |s) = Pht (s′ |s, πh (s)) be its transition kernel. Lemma C.2. Under event E, BPI-UCRL returns a policy π b such that V1∗ (s1 ; R) − V1πb (s1 ; R) ≤ ε. τ +1

Proof. Since V1∗ is optimal and V1τ is an upper bound on V1∗ under E, we have V1π (s1 ; R) ≤ V1∗ (s1 ; R) ≤ V1τ (s1 ; R). Since BPI-UCRL outputs the policy π b = π τ +1 , we can use the alternative τ π τ +1 definitions of Vh and Vh due to Lemma A.1 to bound the difference between V1∗ and V1πb as V1∗ (s1 ; R) − V1πb (s1 ; R) = V1∗ (s1 ; R) − V1π X

≤

τ +1

π P τ,π 1:H+1 (s2:H+1 |s1 ) − P1:H+1 (s2:H+1 |s1 )

s2:H+1

≤

(s1 ; R) ≤ V1τ (s1 ; R) − V1π

τ +1 τ +1 b t,π P τ,π 1:H+1 (·|s1 ) − P1:H+1 (·|s1 )

H X

τ +1

(s1 ; R)

R(si , πiτ +1 (si ))

i=1

+ 1

τ +1 b τ,π (·|s1 ) − P πτ +1 (·|s1 ) P 1:H+1 1:H+1 τ +1

i 1

b τ1 (s1 )H ≤ ε, H ≤ 2L

where we use the alternative definitions of Vhτ and Vhπ , the triangle inequality, the fact that τ +1 τ +1 P τ,π (·|sh ) and Phπ (·|sh ) belong to C τ (sh , πhτ +1 (sh )) under event E, Lemma C.1 and the h stopping criterion. 17

PH t For each h and (s, a), let nt (s, a) = h=1 Pπ1:h (s|s1 ) · I(a = πht (s)) be the expected number of Pt visits of (s, a) in episode t, and define pseudo-counts N t (s, a) = ℓ=1 nℓ (s, a). From Lemma G.2 in Appendix G (applied to H = 1) under the event 2SAH 1 E cnt = ∀t ≥ 1, N t (s, a) ≥ N t (s, a) − H log , 2 δ for all t the confidence bonuses satisfy the inequality s √ β N t (s, πht+1 (s)), Hδ t,π t+1 . Bh (s) ≤ 4 H N t (s, πht+1 (s)) ∨ H b t (s1 ) for Assume that the algorithm stops after episode τ . Before stopping, we have ε/(2H) ≤ L 1 each t ∈ Jτ K. Under events E and E cnt we can sum the contributions from each episode to obtain τ τ τ X H X X X X t+1 t+1 τε b t1 (s1 ) ≤ 3 ≤(a) L Lt1 (s1 ) = 3 Pπ1:h (sh |s1 )Bht,π (sh ) 2H t=1 t=1 t=1 h=1 sh s τ H √ X X X πt+1 β(N t (sh , πht+1 (sh )), δ/H) P1:h (sh |s1 ) ≤(b) 12 H N t (sh , πht+1 (sh )) ∨ H t=1 h=1 sh PH τ X P t+1 π t+1 X p sh h=1 P1:h (sh |s1 ) · I((s, a) = (sh , πh (sh ))) q ≤(c) 12 Hβ(Hτ, δ/H) t=1 s,a N t (s, a) ∨ H P τ X t+1 X p (sh , a) · I(s = sh ) sh n q =(d) 12 Hβ(Hτ, δ/H) t=1 s,a N t (s, a) ∨ H τ XX p N t+1 (s, a) − N t (s, a) q ≤(e) 12 Hβ(Hτ, δ/H) s,a t=1 N t (s, a) ∨ H τ p √ XX (N t+1 (s, a) − N t (s, a))/H q ≤(f ) 12 Hβ(Hτ, δ/H) H s,a t=1 N t (s, a)/H ∨ 1 p ≤(g) 12H β(Hτ, δ/H)SAτ .

In (a) we use Lemma C.1 and the alternative definition of Lt1 (s1 ) due to Lemma A.1. In (b) we convert the counts to pseudo-counts. In (c) q we use the monotonicity of β to obtain an upper bound β(Hτ, δ/H), and we move the term 1/

N t (s, a) ∨ 1 outside the sum over sh by summing over

s, a and introducing an indicator function I((s, a) = (sh , πht+1 (sh ))). In (d) we identify nt+1 (sh , a). In (e) we simplify the sum over sh and use the definitions of N t+1 (s, a) and N t (s, a). In (f ) we normalize the pseudo-counts by dividing them with H, and in (g) we apply Lemma 19 of Jaksch et al. [2010]. Rearranging the terms of the inequality to isolate τ on one side gives us p √ 24H 2 β(Hτ, δ/H)SA 576H · SAH 4 β(Hτ, δ/H) τ≤ ⇔ Hτ ≤ . ε ε2 Recalling the expression β(n, δ) = log(2SA/δ) + (S − 1) log(e(1 + n/(S − 1))), the last inequality is equivalent to 576H · SAH 4 (log(2SAH/δ) + (S − 1) log(e(1 + Hτ /(S − 1)))) . ε2 Using some inversion lemma such as Lemma 15 from Kaufmann et al. [2021] (which we restate for completeness as Lemma H.1) yields the bound SAH 4 SAH SAH 5 SAH τ =O log + S log log ε2 δ ε2 δ Hτ ≤

that is valid under the event E ∩ E cnt . Moreover, from Lemma G.1, this event holds with probability larger than 1 − δ, which concludes the proof. The proof follows a very similar strcuture compared to that of the original BPI-UCRL algorithm. A subtle difference is that BPI-UCRL is originally analyzed for time-inhomogeneous MDPs. For time-homogeneous transitions, the threshold function β in the event E can be chosen slightly smaller (removing an H inside the log) but the event E cnt needs to be defined in a slightly different way compared to the original analysis, with an extra H factor in the correction term involved therein (see Appendix G). This was actually overlooked in the initial work of Kaufmann et al. [2021] who claim that an improvement of a factor H can be obtained in the resulting sample complexity bound. b τ (s1 ) = ε/2: For sparse-reward MDPs, Lemma C.2 trivially holds for the stopping rule L 1 τ +1

V1∗ (s1 ; R) − V1πb (s1 ; R) ≤

τ +1

π P τ,π 1:H+1 (s2:H+1 |s1 ) − P1:H+1 (s2:H+1 |s1 )

s2:H+1

R(si , πiτ +1 (si ))

i=1

τ +1 b t,πτ +1 P τ,π 1:H+1 (·|s1 ) − P1:H+1 (·|s1 )

≤

H X

π τ +1 b τ,πτ +1 (·|s1 ) − P1:H+1 + P (·|s1 ) 1:H+1

b τ1 (s1 ) ≤ ε. ≤ 2L

Because of the modified stopping rule, the analysis from the proof of Theorem 2.1 directly yields p τε 576H · SAH 2 β(Hτ, δ/H) ≤ 12H β(Hτ, δ/H)SAτ ⇔ Hτ ≤ . 2 ε2 2 2 e Lemma H.1 now yields a sample complexity of order O(SAH /ε ).

The Value Function Upper Bound

In this appendix we show that the value function V t is an upper bound on V ∗ . We prove the statement using two lemmas that bound the transition kernels and rewards, respectively. ∗

Lemma D.1. Under Assumption 3.1 and event E, for each (σ, k) the transition kernels P π (·|σ, k) t+1 and P π (·|σ, k) belong to the high-level confidence set C t (σ, k). ∗ b t,πt+1 (·|σ, k) − P π∗ (·|σ, k)∥1 as Proof. To show that P π (·|σ, k) belongs to C t (σ, k), we bound ∥P

b t,π P

t+1

∗

(·|σ, k) − P π (·|σ, k) 1

≤(a)

b t,πt+1 (·|σ, k) − P πt+1 (·|σ, k) P

≤(b)

t+1,k π t+1,k bt,π P 1:H+1 (·|g(σ)) − P1:H+1 (·|g(σ))

+ Pπ

t+1

∗

(·|σ, k) − P π (·|σ, k)

+ 1

t+1,k ∗,k Pπ1:H+1 (·|g(σ)) − Pπ1:H+1 (·|g(σ))

b t,k (g(σ)) + 2 V1πt+1,k (g(σ); Rk ) − V1π∗,k (g(σ); Rk ) ≤(c) L 1 b b t,k (g(σ)) ≤ 5H L b t,k (g(σ)). ≤(d) Lt,k (g(σ)) + 4H L 1

b t,π and P π . In (c) we In (a) we use the triangle inequality, and in (b) we use the definitions of P apply Lemma C.1 and use Assumption 3.1, and in (d) we bound the value difference as in the proof b t,πt+1 (·|σ, k) − P πt+1 (·|σ, k)∥1 is the first term in step (a), the second of Lemma C.2. Since ∥P claim follows. b t,πt+1 (σ, k) − Lemma D.2. Under Assumption 3.1 and event E, for each (σ, k) it holds that R ∗ b t,πt+1 (σ, k) − Rπt+1 (σ, k) ≤ 3H L b t,k (g(σ)) and R b t,k (g(σ)). Rπ (σ, k) ≤ 3H L 1

Proof. We can bound the first term as follows: b t,π R

t+1

=(b) Vb1t,π ≤(c)

∗

b t,π (σ, k) − Rπ (σ, k) ≤(a) R t+1,k

(g(σ); Yg(σ) ) − V1π

t+1,k

t+1

(σ, k) − Rπ

t+1

(σ, k) + Rπ

(g(σ); Yg(σ) ) + V1π

π t+1,k b t,πt+1,k (·|g(σ)) − P1:H+1 P (·|g(σ)) 1:H+1

H+ 1

t+1,k

t+1

∗

(σ, k) − Rπ (σ, k)

(g(σ); Yg(σ) ) − V1π

∗,k

(g(σ); Yg(σ) )

t+1,k ∗,k V1π (g(σ); Rk ) − V1π (g(σ); Rk )

b t,k (g(σ)) + 2H L b t,k (g(σ)) ≤ 3H L b t,k (g(σ)). ≤(d) H L 1 1 1

b t,π and Rπ . In (c) we In (a) we use the triangle inequality, and in (b) we use the definitions of R bound the value difference using the composite distributions and use Assumption 3.1. In (d) we use Lemma C.1 and bound the value difference as in the proof of Lemma C.2. The second statement of b t,πt+1 (σ, k) − Rπt+1 (σ, k) is the first term of step (a). the lemma holds since R b t,πt+1 (σ, k) + 3H L b t,k (g(σ)) is an upper bound on As a consequence of Lemmas D.1 and D.2, R 1 ∗ ∗ Rπ (σ, k) for each (σ, k), and P π (· |σ, πh (σ)) belongs to the confidence set C t (σ, πh (σ)) for each π and σ. Since V t maximizes over C t (σ, k), this implies that V t is an upper bound on V ∗ . Since Vh∗ (σ) is trivially upper bounded by HH for each h and σ, taking the minimum with HH does not invalidate the bound.

Proof of Theorem 4.1

In this section we prove Theorem 4.1, which states an upper bound on the sample complexity of HBPI-UCRL. We first define an error function Lt analogous to Lt but for the true SMDP transition kernel of (π t+1 , π t+1 ). The function Lt is recursively defined for each σ as LtH+1 (σ) = 0 and X t+1 Lth (σ) = Bht (σ) + P π (σ ′ |σ, πht+1 (σ))Lth+1 (σ ′ ) ∀h ∈ JHK. σ′

We also introduce convenient notation for several transition kernels of the policy π t+1 . ∗

• P th (σ ′ |σ) = P π (σ ′ |σ, πht+1 (σ)) is the true transition kernel of π t+1 under π ∗ with associated composite distributions P ti:j and P ti:j . t+1

e t (σ ′ |σ) = P π (σ ′ |σ, π t+1 (σ)) is the true transition kernel of π t+1 under π t+1 with • P h h e t and P et . associated composite distributions P i:j i:j t+1

b t (σ ′ |σ) = P b t,π (σ ′ |σ, π t+1 (σ)) is the empirical transition kernel of π t+1 under π t+1 • P h h b t and P bt . with associated composite distributions P i:j i:j We are now ready to prove a lemma for SMDPs analogous to Lemma C.1 for MDPs. t+1

t+1

Lemma E.1. Let {Qπ }h∈JHK be any transition kernel for π t+1 such that Qπ (·|σ) ∈ h h t t+1 π t+1 π t+1 C (σ, π (σ)) for h, σ, and let Q i:j and Q i:j be the induced composite distributions. Under Assumption 3.1 and event E we have t+1

t t t Qπ h:H+1 (·|σ) − P h:H+1 (·|σ) 1 ≤ Lh (σ) ≤ 3Lh (σ), t+1

t t t Qπ h:H+1 (·|σ) − P h:H+1 (·|σ) 1 ≤ Lh (σ) ≤ 3Lh (σ),

where P th:H+1 and P th:H+1 are the composite distributions induced by Pht . Proof. We first prove the left inequalities by induction on h. The base case is h = H. In this case by definition we have t+1

t+1

π π Qπ H:H+1 (·|σH ) = Q H:H+1 (·|σH ) = QH

(·|σH ),

P tH:H+1 (·|σH ) = P tH:H+1 (·|σH ) = P tH (·|σH ), t LtH (σH ) = min 2, BH (σH ) + 0 . Consequently we can write t+1

t+1

π Q H:H+1 (·|σH ) − P tH:H+1 (·|σH )

≤

t+1 bt Qπ H (·|σH ) − P H (·|σH ) t+1

= Qπ H

(·|σH ) − P tH (·|σH )

b t (·|σH ) − P t (·|σH ) + P H H t+1

1 t+1

t b t,πH (σH ) (g(σH )) + 5H L b t,πH (σH ) (g(σH )) = 10H L b t,πH (σH ) (g(σH ) = BH ≤ 5H L (σH ), 1 1 1

t+1

t where we use the triangle inequality and the facts that Qπ H (·|σH ) and P H (·|σH ) belong to t+1 t+1 Qπ C t (σH , πH (σH )). Since the trivial bound 2 also applies, this shows that ∥Q H:H+1 (·|σH ) − t+1 t Qπ P tH:H+1 (·|σH )∥1 ≤ min[2, BH (σH )] = LtH (σH ). The proof for ∥Q H:H+1 (·|σH ) − P tH:H+1 (·|σH )∥1 is identical.

The inductive case is given by h ∈ JH − 1K. In this case we have t+1

t Qπ h:H+1 (·|σh ) − P h:H+1 (·|σh )

≤(a)

Qπ h

t+1

= 1

t+1

t Qπ h:H+1 (σh+1:H+1 |σh ) − P h:H+1 (σh+1:H+1 |σh )

σh+1:H+1 t+1

t+1

t Qπ Qπ (σh+1 |σh )Q h+1:H+1 (σh+2:H+1 |σh+1 ) h+1:H+1 (σh+2:H+1 |σh+1 ) − Ph (σh+1 |σh )Q

σh+1:H+1 t+1

t Qπ P th+1:H+1 (σh+2:H+1 |σh+1 ) Pht (σh+1 |σh )Q h+1:H+1 (σh+2:H+1 |σh+1 ) − Ph (σh+1 |σh )P

σh+1:H+1

=(b)

Qπ h

t+1

σh+1

t+1

Qπ h+1:H+1 (σh+2:H+1 |σh+1 )

σh+2:H+1

Pht (σh+1 |σh )

σh+1

=(c) Qπ h

(σh+1 |σh ) − Pht (σh+1 |σh ) X

t+1

t Qπ h+1:H+1 (σh+2:H+1 |σh+1 ) − P h+1:H+1 (σh+2:H+1 |σh+1 )

σh+2:H+1 t+1

(·|σh ) − Pht (·|σh ) X

t ≤(d) Bh (σh ) +

+ 1

t+1

t Pht (σh+1 |σh ) Q π h+1:H+1 (·|σh+1 ) − P h+1:H+1 (·|σh+1 )

σh+1

P th (σh+1 |σh )Lth+1 (σh+1 ) ≡ Z th (σh ).

σh+1 t+1

t In (a) we use the definition of Q π h:H+1 and P h:H+1 and the triangle inequality, in (b) we use the equality |ab − ac| = a|b − c| for a ≥ 0, in (c) we use the definition of the L1-norm and the P t+1 π t+1 equality σh+2:H+1 Q π (·|σh ) h+1:H+1 (σh+2:H+1 |σh+1 ) = 1, and in (d) we use the fact that Qh t t+1 t and P h (·|σh ) belong to C (σh , πh (σh )) and the inductive hypothesis for h + 1. Since the trivial bound 2 also applies, we obtain t+1 t Qπ ≤ min 2, Z th (σh ) = Lth (σh ). h:H+1 (·|σh ) − P h:H+1 (·|σh ) 1

t+1 t Qπ The proof for ∥Q h:H+1 (·|σh ) − P h:H+1 (·|σh )∥1 is very similar: t+1

π Q h:H+1 (·|σh ) − P th:H+1 (·|σh )

≤(a)

X X

Qπ h

t+1

= 1

t Qπ h:H+1 (σH+1 |σh ) − P h:H+1 (σH+1 |σh )

σH+1 t+1

t+1

t Qπ Qπ (σh+1 |σh )Q h+1:H+1 (σH+1 |σh+1 ) − Ph (σh+1 |σh )Q h+1:H+1 (σH+1 |σh+1 )

σH+1 σh+1

X X

t+1

t Qπ Pth+1:H+1 (σH+1 |σh+1 ) Pht (σh+1 |σh )Q h+1:H+1 (σH+1 |σh+1 ) − Ph (σh+1 |σh )P

σH+1 σh+1

=(b)

Qπ h

t+1

(σh+1 |σh ) − Pht (σh+1 |σh )

Pht (σh+1 |σh )

σh+1

=(c) Qπ h

t+1

Qπ h+1:H+1 (σH+1 |σh+1 )

σH+1

σh+1

t+1

t Qπ h+1:H+1 (σH+1 |σh+1 ) − P h+1:H+1 (σH+1 |σh+1 )

σH+1 t+1

(·|σh ) − Pht (·|σh )

t ≤(d) Bh (σh ) +

+ 1

t+1

t Pht (σh+1 |σh ) Q π h+1:H+1 (·|σh+1 ) − P h+1:H+1 (·|σh+1 )

σh+1 t

P th (σh+1 |σh )Lh+1 (σh+1 ) ≡ Z h (σh ).

σh+1

We next show by induction on h that Lth (σ) − Lth (σ) ≤ 2Lth (σ). The base case is given by t t h = H, in which case LtH (σ) = min[2, BH (σ)] ≤ BH (σ) = LtH (σ) by definition, implying t t t LH (σ) − LH (σ) ≤ 0 ≤ 2LH (σ). In the inductive case h ∈ JH − 1K we can write t Lth (σ) − Lth (σ) ≤ BH (σ) +

t P th (σ ′ |σ)Lth+1 (σ ′ ) − BH (σ) −

σ′

X σ′

e th (σ ′ |σ)Lth+1 (σ ′ ) P

X t ′ e th (σ ′ |σ) Lth+1 (σ ′ ) + e h (σ |σ) Lth+1 (σ ′ ) − Lth+1 (σ ′ ) P th (σ ′ |σ) − P P

σ′

b th (·|σ) + 2 P b th (·|σ) − P e th (·|σ) + 2 ≤(a) 2 P th (·|σ) − P 1

≤(b) 2

H X X

eth:h (σi |σ)Bit (σi ) + 2 P

σi

e th (σ ′ |σ) P

σ′

H X X

eth+1:i (σi |σ ′ )Bit (σi ) P

i=h+1 σi

eth:i (σi |σ)Bit (σi ) = 2 P

i=h+1 σi

H X X

eth:i (σi |σ)Bit (σi ) = 2Lth (σ). P

i=h σi

In (a) we use the trivial bound Lth+1 (σ ′ ) ≤ 2, the triangle inequality, the inductive hypothesis and the alternative definition of Lth+1 (σ ′ ) due to Lemma A.1. In (b) we use Lemma D.1 et (σi |σ) = I(σ = σi ) and change the order of summation to obtain twice, the definition P h:h P e t ′ et ′ t t t et P (σ |σ) P (σ ′ h h+1:i i |σ ) = P h:i (σi |σ). Since Lh (σ) − Lh (σ) ≤ 2Lh (σ), it follows that σ t t t t t Lh (σ) = Lh (σ) − Lh (σ) + Lh (σ) ≤ 3Lh (σ). This concludes the proof of the lemma. We next prove a lemma that bounds two particular choices of value functions. Lemma E.2. Let U t and W t be two value functions of π t+1 recursively defined for each σ as t t UH+1 (σ) = WH+1 (σ) = 0 and X t b t,πt+1 (σ, π t+1 (σ)) − Rπ∗ (σ, π t+1 (σ)) + Uht (σ) = R P th (σ ′ |σ)Uh+1 (σ ′ ), h h σ′

h i X t+1 t ′ t ′ b t,πh (σ) (g(σ)) + Wht (σ) = min 1, 3H L P (σ |σ)W (σ ) . h h+1 1 σ′

Under Assumption 3.1 and event E, for each h and σ it holds that Uht (σ) ≤ HHLth (σ) and Wht (σ) ≤ Lth (σ). Proof. We prove the claim by induction on h. In the base case h = H we have t+1

t t b t,πt+1 (σ, π t+1 (σ)) − Rπ∗ (σ, π t+1 (σ)) + 0 ≤ 3H L b t,πH (σ) (g(σ)) ≤ BH (σ), UH (σ) = R 1 H H h i t+1 t,π (σ) t t b H WH (σ) = min 1, 3H L (g(σ)) + 0 ≤ min 2, BH (σ) = LtH (σ), 1 t where we have used Lemma D.2. Since UH (σ) is trivially upper bounded by HH, we have t t t UH (σ) ≤ min HH, BH (σ) ≤ HH min[2, BH (σ)] = HHLtH (σ).

The inductive case is given by h ∈ JH − 1K. In this case we have b t,π Uht (σ) = R

t+1

∗

(σ, πht+1 (σ)) − Rπ (σ, πht+1 (σ)) +

t P th (σ ′ |σ)Uh+1 (σ ′ )

σ′

≤ Bht (σ) + HH

P th (σ ′ |σ)Lth+1 (σ ′ ),

σ′

t+1

b t,πh 1, 3H L 1

Wht (σ) = min

# (σ)

(g(σ)) +

t P th (σ ′ |σ)Wh+1 (σ ′ )

σ′

" ≤ min

# 2, Bht (σ) +

P th (σ ′ |σ)Lth+1 (σ ′ )

= Lth (σ),

σ′

where we have used Lemma D.2 and the inductive hypothesis. Since Uht (σ) is upper bounded by HH, we have " # X t t t ′ t ′ Uh (σ) ≤ min HH, Bh (σ) + HH P h (σ |σ)Lh+1 (σ ) σ′

" ≤ HH min

# 2, Bht (σ) +

P th (σ ′ |σ)Lth+1 (σ ′ )

σ′

This concludes the proof of the lemma. 22

= HHLth (σ).

t+1

t+1 ∗ b t,πH (σ) (g(σ)) ≤ B t (σ) due Since Rπ (σi , πit+1 (σi )) − Rπ (σi , πit+1 (σi ) ≤ 3H L 1 h b t,πt+1 (σi , π t+1 (σi )) − Rπ∗ (σi , π t+1 (σi ) with to the proof of Lemma D.2, replacing R i i

Rπ

t+1

∗

(σi , πit+1 (σi )) − Rπ (σi , πit+1 (σi ) in the definition of Uht (σ) yields the same bound.

We next prove an upper bound on the value function V t . t+1

t+1 t+1 t,π ,π Lemma E.3. Let Vb t,π ,π be a value function recursively defined for σ as VbH+1 and X t+1 t+1 t+1 t+1 b t,πt+1 (σ, π t+1 (σ)) + Vb t,π ,π (σ) = R P t (σ ′ |σ)Vb t,π ,π (σ ′ ).

t+1

(σ) = 0

h+1

σ′

For each h and σ it holds that V ht (σ) ≤ HHWht (σ) + Vbht,π

t+1

,π t+1

(σ).

Proof. By induction on h, with the base case given by h = H. In this case we have i h t+1 t b t,πt+1 (σ, π t+1 (σ)) + 3H L b t,πH (σ) (g(σ)) VH (σ) = min HH, R 1 H h i t+1 t,π (σ) b t,πt+1 (σ, π t+1 (σ)) b H ≤ min HH, HH3H L (g(σ)) + R 1 H t+1

t+1

t,π ,π t (σ) + VbH (σ). = HHWH The recursive case is given by h ∈ JH − 1K. In this case we have h i X t+1 t b t,πt+1 (σ, π t+1 (σ)) + 3H L b t,πh (σ) (g(σ)) + V ht (σ) = min HH, R Pht (σ ′ |σ)V h+1 (σ ′ ) 1 h σ′

t+1 t,πh (σ)

t+1

b t,π (σ, π t+1 (σ)) + 3H L b ≤ min HH, R (g(σ)) 1 h i X t,π t+1 ,π t+1 t + Pht (σ ′ |σ) HHWh+1 (σ ′ ) + Vbh+1 (σ ′ ) σ′ t+1

b t,πh ≤ min HH, HH3H L 1

(σ)

(g(σ)) + HH

i t Pht (σ ′ |σ)Wh+1 (σ ′ )

σ′

b t,π +R

t+1

(σ, πht+1 (σ)) +

t+1

t,π Pht (σ ′ |σ)Vbh+1

,π t+1

(σ ′ ) = HHWht (σ) + Vbht,π

t+1

,π t+1

(σ),

σ′

where we have used the inductive hypothesis. This concludes the proof. We note that Lemma A.1 applies to each transition kernel of π t+1 and associated composite distributions, which implies that we can write the value functions of π t+1 as Vhπ Vhπ Vbht,π

t+1

,π ∗

,π t+1

(σh ) =

P th:H+1 (σh+1:H+1 |σh )

H X

σh+1:H+1

i=h

H X

(σh ) =

et P h:H+1 (σh+1:H+1 |σh )

σh+1:H+1

i=h

H X

(σh ) =

P th:H+1 (σh+1:H+1 |σh )

σh+1:H+1

∗

Rπ (σi , πit+1 (σi )), Rπ

t+1

(σi , πit+1 (σi )),

b t,πt+1 (σi , π t+1 (σi )), R i

i=h

H X X t t Uh (σh ) = P h:H+1 (σh+1:H+1 |σh ) σh+1:H+1 i=h

b t,πt+1(σi , π t+1 (σi ))−Rπ∗(σi , π t+1 (σi )) . R i i

We are now ready to prove the first part of Theorem 4.1. Lemma E.4. Under Assumption 3.1 and event E, the policies π τ +1 and {π τ +1,k }k∈JKK returned by HBPI-UCRL satisfy |V1∗ (σ1 ) − V1π

τ +1

,π τ +1

(σ1 )| ≤ ε. 23

Proof. We first use the triangle inequality to obtain V1∗ (σ1 ) − V1π

τ +1

,π τ +1

(σ1 ) ≤ V1∗ (σ1 ) − V1π

τ +1

,π ∗

(σ1 ) + V1π

τ +1

,π ∗

(σ1 ) − V1π

τ +1

,π τ +1

(σ1 ) .

τ +1 ∗ Since V1π ,π (σ1 ) ≤ V1∗ (σ1 ) ≤ V 1τ (σ1 ), the first term can be bounded as

V1∗ (σ1 ) − V1π

τ +1

,π ∗

(σ1 ) ≤ V 1τ (σ1 ) − V1π

≤(a) HHW τ1 (σ1 ) + Vb1τ,π ≤(b) HHW τ1 (σ1 ) +

τ +1

,π

τ +1

(σ1 ) − V1π

P τ1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

,π ∗

(σ1 )

τ +1

,π ∗

H X

(σ1 )

b τ,πτ +1(σi , π τ +1 (σi )) − Rπ∗(σi , π τ +1 (σi )) R i i

i=1

P τ1:H+1 (σ2:H+1 |σ1 ) − P τ1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

H X

∗

Rπ (σi , πiτ +1 (σi ))

i=1

≤(c) HHW τ1 (σ1 ) + U τ1 (σ1 ) + P τ1:H+1 (·|σ1 ) − P τ1:H+1 (·|σ1 )

HH ≤ 3HHLτ1 (σ1 ).

In (a) we use the upper bound on V τ from Lemma E.3, and in (b) we use the alternative definitions of τ +1 τ +1 τ +1 ∗ Vb1τ,π ,π and V1π ,π and the triangle inequality. In (c) we identify the alternative definition of U τ , upper bound the reward sum by HH and apply Lemmas E.2 and E.1. The second term can be bounded as V1π

τ +1

≤(a)

,π ∗

(σ1 ) − V1π

τ +1

,π τ +1

(σ1 )

τ eτ P 1:H+1 (σ2:H+1 |σ1 ) − P 1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

Rπ

τ +1

(σi , πiτ +1 (σi ))

i=1

P τ1:H+1 (σ2:H+1 |σ1 )

H X

Rπ

τ +1

∗

(σi , πiτ +1 (σi )) − Rπ (σi , πiτ +1 (σi ))

σ2:H+1

i=1

P τ1:H+1 (σ2:H+1 |σ1 ) − P τ1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

≤(b)

H X

∗

Rπ (σi , πiτ +1 (σi ))

i=1

τ eτ P 1:H+1 (·|σ1 ) − P 1:H+1 (·|σ1 )

P τ1:H+1 (·|σ1 ) − P τ1:H+1 (·|σ1 )

HH + 1

HH + U τ1 (σ1 )

≤ 3HHLτ1 (σ1 ). τ +1

∗

τ +1

In (a) we use the alternative definitions of V1π ,π and V1π ,π and the triangle inequality, and in (b) we use the bound HH on the reward sums, identify the alternative definition of U τ1 (σ1 ) and apply Lemmas E.2 and E.1. Gathering the terms we obtain V1∗ (σ1 ) − V1π

τ +1

,π τ +1

(σ1 ) ≤ (3 + 3)HHLτ1 (σ1 ) ≤ 6HHLτ1 (σ1 ) ≤ ε,

where the last inequality follows from the stopping criterion Lτ1 (σ1 ) ≤ ε/(6HH).

We next define an appropriate notion of pseudo-counts for the hierarchical setting. In episode t + 1, since the policies are π t+1 and π t+1,k , k ∈ JKK, high-level transitions are governed by the transition t+1 ,π t+1 kernel P π . Letting k th = πht+1 (σh ), the expected number of visits of a state-action (s, a) h during episode t + 1 is nt+1 (s, a) =

H X X h=1 σh

t+1

,π Pπ 1:h

t+1

(σh |σ1 )

H X

t+1,kt h

π P1:h

(s|g(σh )) · I(a = π t+1,kh (s)).

h=1

The pseudo-count is the sum over all episodes, i.e. N t (s, a) =

ℓ ℓ=1 n (s, a).

While the algorithm does not stop, it holds that ε/(6HH) ≤ Lt1 (σ1 ). Under events E and Ecnt , summing the contributions of each episode yields 24

τ τ τ X H X X X X τε t,π t+1 (σh ) π t+1 ,π t+1 ≤(a) Lt1 (σ1 ) ≤ 3 (g(σh )) Lt1 (σ1 ) = 3 P 1:h (σh |σ1 )10HL1 h 6HH t=1 t=1 t=1 σ h=1

≤(b) 9

τ X H X X

t+1

,π Pπ 1:h

t+1

t,π t+1 (σh ) (σh |σ1 )10HL1 h (g(σh ))

t=1 h=1 σh

≤(c) 90H

τ X H X X

t+1

,π Pπ 1:h

t+1

(σh |σ1 )

t=1 h=1 σh

t+1 (σh ) t+1,π h

Pπ1:h

t+1 t+1,πh (σh )

(sh |g(σh ))B t (sh , πh

(sh ))

h=1 sh

τ X H X X

≤(d) 360H

H X X

t+1

,π Pπ 1:h

t+1

(σh |σ1 )

t=1 h=1 σh

H X X

t+1 t+1,π (σh ) h π

P1:h

h=1 sh

≤(e) 360H

v u t+1 t+1,πh (σh ) u (sh )), δ/HH) u HHβ(N t (sh , πh (sh |g(σh ))t t+1 t+1,πh (σh ) t N (sh , πh (sh )) ∨ HH

τ X X p q HHβ(HHτ, δ/HH) t=1 s,a

H X XX

t+1

,π Pπ 1:h

t+1

(σh |σ1 )

H X h=1

τ X X

HHβ(HHτ, δ/HH)

t=1 s,a

=(g) 360H

HHβ(HHτ, δ/HH)

N t (s, a) ∨ HH

t+1,kh

π P1:h

sh h=1 σh

=(f ) 360H

(sh |g(σh )) · I (s, a) = (sh , π t+1,kh (sh ))

t+1 (sh , a) · I(s = sh ) sh n

q N t (s, a) ∨ HH

τ XX N t+1 (s, a) − N t (s, a) q s,a t=1 N t (s, a) ∨ HH

τ XX p √ (N t+1 (s, a) − N t (s, a))/(HH) q HHβ(HHτ, δ/HH) HH s,a t=1 N t (s, a)/(HH) ∨ 1 p ≤(i) 360HH 2 β(HHτ, δ/HH)SAτ .

≤(h) 360H

In (a) we use Lemma E.1, the alternative definition of Lt1 (σ1 ) due to Lemma A.1 and the definition t,π t+1 (σ )

h of B t . In (b) we apply Lemma C.1, and in (c) we use the alternative definition of L1 h (g(σh )) due to Lemma A.1. In (d) we apply Lemma G.2 to convert the counts to pseudo-counts. In (e) weq use the monotonicity of β to obtain an upper bound β(HHτ, δ/HH), and we move the term

1/ N t (s, a) ∨ 1 outside the sum over sh by summing over s, a and introducing an indicator function

I((s, a) = (sh , πht+1,kh (sh ))). In (f ) we identify n̄t+1 (sh , a), and in (g) we simplify the sum over sh and use the definitions of N t+1 (s, a) and N t (s, a). In (h) we divide the pseudo-counts by HH, and in (i) we apply Lemma 19 of Jaksch et al. [2010]. Rearranging the terms of the inequality to isolate τ on one side gives us p √ 2160H 2 H 3 β(HHτ, δ/HH)SA τ≤ ε 4665600HH · SAH 4 H 6 β(HHτ, δ/HH) ⇔ HHτ ≤ . ε2 From here, using the expression of β together with Lemma H.1 applied to n = HHτ yields SAH 4 H 6 SAHH SAH 5 H 7 SAHH τ =O log + S log log . ε2 δ ε2 δ Finally, Lemma G.1 implies that the events E and Ecnt hold simultaneously with probability 1 − δ. 25

Proof of Theorem 4.2

We first remark that since the flat MDP M is sparse-reward, for any state sequence σ1:H+1 we have H X

b t,πt+1 (σh , π t+1 (σh )) R h

h=1

H X

Vb1t,π

t+1 t+1,π (σh ) h

(g(σh ); Yg(σh ) )

h=1

H X X

t+1,π

t+1

h b t,π P 1:H+1

(σh )

(s2:H+1 |s1 = g(σh ))

h=1 s2:H+1

H X

Y(f (g(σh ), si ), πit+1 (si ))

i=1

Γt1:HH+1 (σ2:HH+1 |σ1 )

σ2:HH+1

HH Y

µti (ai |σi )

a1:HH i=1

HH X

Y(σi , ai ) ≤ 1,

i=1

where Γt1:HH+1 is an appropriately chosen composite distribution on state sequences, and µti : Σ → ∆(A) is an appropriately chosen stochastic policy for each i ∈ JHHK. As a consequence, this implies that all value functions (both true as well as empirical) are upper bounded by 1. We next exploit that the subproblem MDPs are sparse-reward. We prove that Lemma D.1 still holds for the new definition of the confidence sets C t . b t,π P

t+1

∗

(·|σ, k) − P π (·|σ, k) 1

b t,π ≤ P

t+1

(·|σ, k) − P π

t+1

+ Pπ

(·|σ, k)

b t,k (g(σ)) + 2 V1π ≤L 1

t+1,k

∗

(·|σ, k) − P π (·|σ, k)

(g(σ); R

∗,k ) − V1π (g(σ); Rk )

b t,k (g(σ)) + 2 V t,k (g(σ); Rk ) − V1π ≤L 1 1 b t,k (g(σ)) + 2 ≤L 1

t+1

t+1,k

(g(σ); Rk ) t+1,k

t+1,k

π P t,π 1:H+1 (s2:H+1 |g(σ)) − P1:H+1 (s2:H+1 |g(σ))

s2:H+1

H X

Rk (si , πit+1,k (si ))

i=1

t+1,k b t,πt+1,k b t,k (g(σ)) + 2 P t,π ≤L 1 1:H+1 (·|g(σ)) − P1:H+1 (·|g(σ))

π t+1,k b t,πt+1,k (·|g(σ)) − P1:H+1 +2 P (·|g(σ)) 1:H+1

b t,k (g(σ)). ≤ 5L 1 t+1

(·|σh ) − Pht (·|σh )∥1 ≤ Bht (σh ) for the new This implies that Lemma E.1 still holds since ∥Qπ h b t,πt+1 (σ, k) + definition of B t . Consequently, the modified V t is still an upper bound on V ∗ since R ∗ b t,k (g(σ)) is an upper bound on Rπ (σ, k) due to Lemma D.2. Since M is sparse-reward, taking 3L 1 the minimum with 1 does not invalidate the bound. Lemma F.1. Under Assumption 3.1 and event E, for each h and σ it holds that Uht (σ) ≤ Lth (σ) and t t (σ) = 0 and Wht (σ) ≤ Lth (σ) for W defined as WH+1 " # X t+1 t,πh (σ) t t ′ t ′ b Wh (σ) = min 1, 3L (g(σ)) + P h (σ |σ)Wh+1 (σ ) . 1

σ′

Proof. We prove the claim by induction on h, with the base case given by h = H. In this case we have t+1 t t b t,πt+1 (σ, π t+1 (σ)) − Rπ∗ (σ, π t+1 (σ)) + 0 ≤ 3L b t,πH (σ) (g(σ)) ≤ BH UH (σ) = R (σ), 1 H H h i t+1 t t b t,πH (σ) (g(σ)) + 0 ≤ min 2, BH WH (σ) = min 1, 3L (σ) = LtH (σ). 1 t Since UH (σ) is upper bounded by 2 due to M being sparse-reward, we obtain t t UH (σ) ≤ min 2, BH (σ) ≤ LtH (σ).

The recursive case is given by h ∈ JH − 1K. In this case we have b t,π Uht (σ) = R

t+1

∗

(σ, πht+1 (σ)) − Rπ (σ, πht+1 (σ)) +

t P th (σ ′ |σ)Uh+1 (σ ′ )

σ′

≤ Bht (σ) +

P th (σ ′ |σ)Lth+1 (σ ′ ),

σ′

t+1

b t,πh 1, 3L 1

Wht (σ) = min

# (σ)

(g(σ)) +

t P th (σ ′ |σ)Wh+1 (σ ′ )

σ′

# 2, Bht (σ) +

≤ min

P th (σ ′ |σ)Lth+1 (σ ′ )

= Lth (σ),

σ′

where we have used the inductive hypothesis. Since Uht (σ) is upper bounded by 2 we obtain " # X t t t ′ t ′ Uh (σ) ≤ min 2, Bh (σ) + P h (σ |σ)Lh+1 (σ ) = Lth (σ). σ′

This concludes the proof of the lemma. Lemma F.2. For each h and σ it holds that V ht (σ) ≤ Wht (σ) + Vbht,π

t+1

,π t+1

(σ).

Proof. By induction on h, with the base case given by h = H. In this case we have h i t+1 t b t,πt+1 (σ, π t+1 (σ)) + 3L b t,πH (σ) (g(σ)) VH (σ) = min 1, R 1 H h i t+1 t+1 t+1 t,π (σ) b t,πt+1 (σ, π t+1 (σ)) = W t (σ) + Vb t,π ,π (σ). b H ≤ min 1, 3L (g(σ)) + R H 1 H H The recursive case is given by h ∈ JH − 1K. In this case we have h i X t+1 t ′ t ′ b t,πt+1 (σ, π t+1 (σ)) + 3L b t,πh (σ) (g(σ)) + V ht (σ) = min 1, R P (σ |σ)V (σ ) h h+1 1 h σ′

t+1

t+1 b t,πh (σ) (g(σ)) (σ, πht+1 (σ)) + 3L 1

b t,π ≤ min 1, R i X t,π t+1 ,π t+1 t + Pht (σ ′ |σ) Wh+1 (σ ′ ) + Vbh+1 (σ ′ ) σ′ t,π t+1 (σ)

b h ≤ min 1, 3L 1

(g(σ)) +

t Pht (σ ′ |σ)Wh+1 (σ ′ )

σ′

b t,πt+1

(σ, πht+1 (σ)) +

t+1

t,π Pht (σ ′ |σ)Vbh+1

,π t+1

(σ ′ )

σ′ t+1 t+1 = Wht (σ) + Vbht,π ,π (σ).

This concludes the proof. We are now ready to prove the first part of the theorem. Lemma F.3. Under Assumption 3.1 and event E, the policies π t+1 and {π t+1,k }k∈JKK returned by the modified version of HBPI-UCRL satisfy V1∗ (σ1 ) − V1π

t+1

,π t+1

(σ1 ) ≤ ε.

Proof. We first use the triangle inequality to obtain V1∗ (σ1 ) − V1π Since V1π

t+1

,π

∗

t+1

,π t+1

(σ1 ) ≤ V1∗ (σ1 ) − V1π

t+1

,π ∗

(σ1 ) + V1π

t+1

,π ∗

(σ1 ) − V1π

(σ1 ) ≤ V1∗ (σ1 ) ≤ V 1t (σ1 ), the first term can be bounded as

V1∗ (σ1 ) − V1π ≤ W t1 (σ1 ) +

t+1

,π ∗

(σ1 ) ≤ V 1t (σ1 ) − V1π

t+1

,π ∗

t+1 t+1 t+1 ∗ Vb1t,π ,π (σ1 ) − V1π ,π (σ1 )

(σ1 )

t+1

,π t+1

(σ1 ) .

≤ W t1 (σ1 ) +

H X

P t1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

b t,πt+1(σi , π t+1 (σi )) − Rπ∗(σi , π t+1 (σi )) R i i

i=1

P t1:H+1 (σ2:H+1 |σ1 ) − P t1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

H X

∗

Rπ (σi , πit+1 (σi ))

i=1

≤ W t1 (σ1 ) + U t1 (σ1 ) + P t1:H+1 (·|σ1 ) − P t1:H+1 (·|σ1 )

t ≤ 3L1 (σ1 ),

where we have used the upper bound 1 on the reward due to M being sparse-reward. The second term can be bounded as V1π ≤

t+1

,π ∗

(σ1 ) − V1π

t+1

,π t+1

(σ1 )

t et P 1:H+1 (σ2:H+1 |σ1 ) − P 1:H+1 (σ2:H+1 |σ1 )

σ2:H+1

H X

t+1

(σi , πit+1 (σi ))

i=1

P t1:H+1 (σ2:H+1 |σ1 )

H X

Rπ

t+1

∗

(σi , πit+1 (σi )) − Rπ (σi , πit+1 (σi ))

σ2:H+1

i=1

P t1:H+1 (σ2:H+1 |σ1 ) − P t1:H+1 (σ2:H+1 |σ1 )

Rπ

σ2:H+1

H X

∗

Rπ (σi , πit+1 (σi ))

i=1

t et ≤ P 1:H+1 (·|σ1 ) − P 1:H+1 (·|σ1 )

P t1:H+1 (·|σ1 ) − P t1:H+1 (·|σ1 )

+ 1

+ U t1 (σ1 ) ≤ 3Lt1 (σ1 ).

Gathering the terms we obtain V1∗ (σ1 ) − V1π

t+1

,π t+1

(σ1 ) ≤ (3 + 3)Lt1 (σ1 ) ≤ 6Lt1 (σ1 ) ≤ ε,

where we have used the new stopping criterion Lt1 (σ1 ) ≤ ε/6. This concludes the proof. The remaining analysis is the same as in the proof of Theorem 4.1. However, since the stopping criterion is different and since B t does not contain a factor H anymore, summing the contributions of each episode yields p τε ≤ 360HH β(HHτ, δ/HH)SAτ . 6 Rearranging the terms of the inequality to isolate τ on one side gives us p √ 2160HH β(HHτ, δ/HH)SA τ≤ ε 4665600HH · SAH 2 H 2 β(HHτ, δ/HH) ⇔ HHτ ≤ . ε2 From here, using Lemma H.1 gives SAHH SAH 3 H 3 SAHH SAH 2 H 2 τ ≤O log + S log log . ε2 δ ε2 δ Finally, Lemma G.1 implies that the events E and Ecnt hold simultaneously with probability 1 − δ.

On High-Probability Events

We first recall the definition of the counts and introduce the notion of pseudo-counts, in the general hierarchical setting. We have t

N (s, a)

t X H X H X

ℓ,h I(sℓ,h h = s, ah = a)

ℓ=1 h=1 h=1

N t (s, a)

t X H X H X X

ℓ

ℓ,π ℓ (σh )

ℓ

,π π h Pπ 1:h (σh |σ1 ) · P1:h

ℓ=1 h=1 h=1 σh

ℓ

(s|g(σh )) · I(a = π ℓ,πh (σh ) (s))

t X H X H X ℓ,h F P sℓ,h = s, a = a ℓ−1 h h

ℓ=1 h=1 h=1

where Fℓ is the filtration generated by the observation made in the ℓ first episodes. Indeed, by definition of the algorithm, the high level policy π ℓ and low level policies π ℓ,k used in episode ℓ are Fℓ−1 measurable. Observe that we are marginalizing out the starting state of each low-level episode, σh , in the computation of the conditional probability. ′

) With these definition, and the empirical transition probability P̂ t (s′ |s, a) = NN(s,a,s t (s,a) , we introduce the events n o E = ∀t ∈ N, ∀(s, a), P̂ht (·|s, a) − Ph (·|s, a) ≤ Bht (s, a) 1 1 and E cnt = ∀t ∈ N, ∀(s, a), Nht (s, a) ≥ N th (s, a) − β cnt (δ) 2 q t (s,a),δ) 2β(N h ∧ 2. where Bht (s, a) = N t (s,a) h

Lemma G.1. Choosing β(n, δ) = log(2SA/δ) + (S − 1) log(e(1 + n/(S − 1))) β cnt (δ) = HH log (2SAHH/δ) yields P (E c ) ≤ 2δ and P ((E cnt )c ) ≤ 2δ . Proof. To prove the first statement, we write X P (E c ) ≤ P ∃t ∈ N : ∥P̂ t (·|s, a) − P(·|s, a)∥1 > B t (s, a) s,a (a)

≤

s X

P ∃t ∈ N : ∥P̂ (·|s, a) − P(·|s, a)∥1 >

s,a (b)

≤

2β(N t (s, a), δ) N t (s, a)

X bt (·|s, a) P(·|s, a) > β(N t (s, a), δ) P ∃t ∈ N : N t (s, a) > 1, N t (s, a)KL P s,a

(c)

≤

X b(n) (·|s, a) P(·|s, a) > β(n, δ) P ∃n ≥ 1 : nKL P s,a

δ 2 where in (a) we use that the L1 norm between any two probability distributions is upper bounded b(n) (·|s, a) the empirical transition by 2, in (b) we use Pinsker’s inequality, in (c) we introduce P probability based on the first n visits of (s, a) (in any step h of any (high level) episode and any step h of a low-level episode) and in (d) we use the expression of β and Proposition 1 from Jonsson et al. [2020] which provides time-uniform concentration bound in KL on transition probabilities. ≤

To establish the second statement, for each h ∈ [H] and each h ∈ [H], we use Lemma F.4 in Dann et al. [2017] to prove that, for all δ ∈ (0, 1], ! t t X 1 X ℓ,h ℓ,h ℓ,h ℓ,h P ∃t ∈ N : I(sh = s, ah = a) < P sh = s, ah = a|Fℓ−1 − log(1/δ) ≤ δ. 2 ℓ=1

ℓ=1

As a consequence, we get that 



X  P ∃t ∈ N :

t X

I(sℓ,h = s, aℓ,h = a) < h h

h∈[H] ℓ=1 h∈[H]

≤

X h∈[H] h∈[H]

P ∃t ∈ N :

1 X 2

t X

h∈[H] ℓ=1 h∈[H]

t X ℓ=1

1 I(sℓ,h = s, aℓ,h = a) < h h 2

 P sℓ,h = s, aℓ,h = a|Fℓ−1 − HH log(1/δ) h h 

t X P sℓ,h = s, aℓ,h = a|Fℓ−1 − log(1/δ) h h ℓ=1

≤ HHδ .

Using the definition of the counts and pseudo-counts and a union bound over s and a further yields 1 t δ t P ∃t ∈ N, ∃s ∈ S, a ∈ A : N (s, a) < N (s, a) − HH log(2SAHH/δ) ≤ 2 2 hence we have P((E cnt )c ) ≤ δ/2. From counts to pseudo-counts Below we provide a simple extension of Lemma 7 from Kaufmann et al. [2021] to relate the counts and pseudo-counts. Lemma G.2. On the event E cnt (with β cnt as in Lemma G.1) it holds that, for all t and (s, a), s δ √ β N th (s, a), HH t B (s, a) ≤ 4 HH . N th (s, a) ∨ HH Proof. We assume that E cnt holds and fix a time step t and a triplet (h, s, a). To ease the notation, we let n = Nht (s, a) and n = N th (s, a). We consider a first case in which 14 n > HH log 2SAHH . On event E cnt , this implies n ≥ 14 n. δ Using the monotonicity properties of β yields β(n, δ) β (n/4, δ)) β(n, δ) β(n, δ) ≤ ≤4 =4 , n n/4 n n ∨ HH ≥ 4 log 2δ ≥ where the last equality follows from the observation that n ≥ HH as 4 log 2SAHH δ 1 for δ ∈ (0, 1). Hence r r 2β(n, δ) √ β(n, δ) ≤ 8 n n ∨ HH r r t t δ √ √ β (N h (s,a), HH ) β(N h (s,a),δ) which implies Bht (s, a) ≤ 8 ≤4 H . t t N h (s,a)∨HH

N h (s,a)∨HH

2SAHH

In the second case, we assume 14 n ≤ HH log hence n ≤ 4HH log 2SAH . As the δ δ right-hand side is also always larger than HH, we get 2SAHH . n ∨ HH ≤ 4HH log δ Hence we have δ δ 4HH log 2SAHH 4HHβ 0, HH 4HHβ n, HH δ 1≤ = ≤ n ∨ HH n ∨ HH n ∨ HH and s δ √ β n, HH 2 ≤ 4 HH . n∨1 r t δ √ β (N h (s,a), HH ) t t As Bh (s, a) ≤ 2, we also have Bh (s, a) ≤ 4 HH , which concludes the proof. N t (s,a)∨1 h

A Technical Lemma

For completeness, we provide below a technical lemma extracted from the literature that allows to get an upper bound on x from an inequality upper bounding x by some (quasi) linear function of log(x). Lemma H.1 (Lemma 15 of Kaufmann et al. [2021]). Let n ≥ 1 and a, b, c, d > 0. If n∆2 ≤ a + b log(c + dn) then √ √ 1 d n ≤ 2 a + b log c + 4 (a + b( c + d))2 . ∆ ∆ 30

Figure 3: Stopping time and execution time as functions of the policy update interval Ψ.

Experimental Settings and Additional Results

In this appendix, we discuss the experimental setting for the experiments provided in the main paper and we present further results. Algorithm Setting. We perform experiments on a synthetic grid maze as presented in Figure 1, with treasures removed. The environment consists of an m × m grid of rooms, where each room is a discrete grid of size n × n. Rooms are connected via specific doorways (corresponding to terminal states of subproblems). The total number of states is (m · n)2 + 1, with the goal state G separate from the grid. The action space is a discrete set of 5 possible actions, where the first four actions move the agent in a cardinal direction, and the last action is exclusively used to reach the goal G. The transitions are deterministic. The reward function is sparse as the agent only receives a reward of 1 upon reaching the goal state G in the final room, or when reaching the correct terminal state in the case of subproblems. In each episode, the agent starts in an initial state uniformly sampled within the first room. Without loss of generality this setting can be modelled using a unique dummy initial state s⊥ by defining the dynamics of each action a as R(s⊥ , a) = 0 and P(s′ |s⊥ , a) = ν(s′ ), where ν(s′ ) is the initial probability of s′ . All experiments are performed with three fixed random seeds, a confidence parameter δ = 0.1 and an accuracy ε = 1. Since the domain is deterministic, the value of a policy is 1 if it successfully reaches G, and 0 otherwise. Hence an accuracy ε = 1 is sufficient to distinguish optimal from non-optimal policies. For HBPI-UCRL, the theoretical confidence bounds derived from Hoeffding bonuses are not very tight. To make the algorithm more practical, we remove the constants in several expressions: 3 in the SMDP reward bonus of V t , 5 in the SMDP confidence set C t and 10 in the expression for B t . As is customary in the literature [e.g. Kaufmann et al., 2021], we use a simplified bound β(n, δ) = 2 log(1/δ) + log n in both BPI-UCRL and HBPI-UCRL. Since running the algorithms until stopping is slow, we implement an approximation that updates the policy only every Ψ episodes. Figure 3 shows the stopping time (red) and execution time (blue) of BPI (solid) and HBPI (broken) as functions of Ψ, in the setting of 3 × 3 rooms of size 3 × 3. For the experiments we choose Ψ = 20 for BPI and Ψ = 100 for HBPI since these values offer good tradeoffs between stopping time accuracy and execution time. All experiments were run on a single core of a standard CPU. Even with fewer policy updates, some executions of BPI-UCRL and HBPI-UCRL are slow, and can sometimes take multiple days of computation time. Additional Results on Specific Instances. To further understand the behavior of HBPI-UCRL, we present additional experiments over different domains, varying both the room size n and the grid dimension m. We first report the average reward of the algorithms, to get a sense on how fast the algorithms are playing near optimal policies. In Figure 4, we can notice how in small domains such as 2 × 2 = 4 rooms, BPI-UCRL manages, within a shorter horizon, to reach comparable performance to HBPI-UCRL. This result illustrates a 31

1.0

0.8

0.6

Reward

trade-off in the domain complexity as the benefit of a hierarchical structure can not be appreciated in such simple tasks.

0.4

BPI, H=12 BPI, H=16 BPI, H=20 HBPI, H=4x3=12 HBPI, H=4x4=16 HBPI, H=4x5=20

0.2 0.0 0

100

200

300

400

0.4

BPI, H=21 BPI, H=28 BPI, H=35 HBPI, H=7x3=21 HBPI, H=7x4=28 HBPI, H=7x5=35

0.2 0.0

500

200

(a) 2 × 2 grid 3 × 3 room.

400

600

800

1000 1200 1400

(b) 2 × 2 grid 5 × 5 room.

Figure 4: Comparison of observed reward between BPI-UCRL and HBPI-UCRL (dotted line for BPI and solid line for HBPI 3 runs, mean ± 95% C.I.).

1.0

0.8

0.6

0.4

BPI, H=20 BPI, H=24 BPI, H=28 HBPI, H=4x5=20 HBPI, H=4x6=24 HBPI, H=4x7=28

0.2 0.0 0

100

200

300

400

(a) 3 × 3 grid 3 × 3 room.

500

Reward

1.0

Reward

Differently, in Figure 5, as we approach larger domains with 3 × 3 = 9 and 4 × 4 = 16 rooms of dimension n = {3, 5}, the advantage of a hierarchical structure is more evident. HBPI-UCRL consistently manages to discover optimal policies in fewer time steps with respect to BPI-UCRL, which in more complex settings requires almost double the time to approximate an optimal policy (Figure 5c).This behavior is consistent with our analysis as HBPI-UCRL scales better in larger environments as it successfully mitigates the increase in the number of high-level states.

0.4

BPI, H=35 BPI, H=42 BPI, H=49 HBPI, H=7x5=35 HBPI, H=7x6=42 HBPI, H=7x7=49

0.2 0.0 0

200

400

600

800

1000 1200 1400

(b) 3 × 3 grid 5 × 5 room.

0.4

BPI, H=49 BPI, H=56 BPI, H=63 HBPI, H=7x7=49 HBPI, H=7x8=56 HBPI, H=7x9=63

0.2 0.0 0

200

400

600

800

1000 1200 1400

Figure 5: Comparison of observed reward between BPI-UCRL and HBPI-UCRL (dotted line for BPI and solid line for HBPI 3 runs, mean ± 95% C.I.). Eventually, pushing the grid size to 5 × 5 = 25 rooms, in Figure 6 we can consistently see the advantage of adopting a hierarchical structure both in terms of performance, as BPI-UCRL requires more time steps to reach an optimal policy, approximating the policy at a much slower rate than HBPI-UCRL. Figure 7 shows the heatmap of visited states during the first 40,000 timesteps of BPI-UCRL and HBPI-UCRL in the domain with 5 × 5 rooms of size 3 × 3. It is interesting to see that the two algorithms explore the space in very different ways. BPI-UCRL explores all states uniformly until it eventually finds a policy that reaches the goal state in the middle of the top right room, highlighted by the star marker. In contrast, HBPI-UCRL extensively explores the first room, but after that it does not need to explore all rooms and all states within a room since the rooms share the dynamics. Instead it proceeds more directly to the goal. The asymmetry is likely due to the fact that the subproblem for moving up has a lower index than the subproblem for moving to the right, which causes tiebreaking to prefer moving up first. 32

1.0

0.8

0.6

Reward

1.0

0.4

BPI, H=36 BPI, H=40 BPI, H=44 HBPI, H=4x9=36 HBPI, H=4x10=40 HBPI, H=4x11=44

0.2 0.0 0

200

400

600

0.4

BPI, H=63 BPI, H=70 BPI, H=77 HBPI, H=7x9=63 HBPI, H=7x10=70 HBPI, H=7x11=77

0.2 0.0

800 1000 1200 1400

(a) 5 × 5 grid 3 × 3 room.

200

400

600

800 1000 1200 1400

(b) 5 × 5 grid 5 × 5 room.

Figure 6: Comparison of observed reward between BPI-UCRL and HBPI-UCRL (dotted line for BPI and solid line for HBPI, 3 runs, mean ± 95% C.I.).

⋆

Figure 7: Heatmap of visited states in the domain with 5 × 5 rooms of size 3 × 3 for a) BPI-UCRL; b) HBPI-UCRL. Ablations. To test the exact dependency of the stopping time on S and H, we perform several ablations. Figure 8a shows the stopping time of BPI-UCRL and HBPI-UCRL as functions of S when H is fixed. As expected, the stopping time of BPI-UCRL is linear in S even when H is fixed. However, the stopping time of HBPI-UCRL actually decreases as a function of S. We believe that the stopping time of HBPI-UCRL is adversely affected by setting the horizon much too large (as is the case for small values of S in the figure), and we have two possible explanations for this. The first is that our implementation of HBPI-UCRL interrupts an episode or a subproblem when a terminal state is reached, preventing the algorithm from collecting as much data as the horizon allows. The second is that the policy update interval Ψ may cause a larger approximation error when the horizon is larger. Conversely, Figure 8b shows the stopping time of BPI-UCRL and HBPI-UCRL as functions of H and H when S is fixed, in the setting of 5 × 5 rooms of size 3 × 3. The stopping time of BPI-UCRL increases monotonically in HH, but the stopping time of HBPI-UCRL depends on the values of both H and H. Concretely, the stopping time of HBPI-UCRL increases as a function of H but is initially constant as a function of H. However, when increasing the subproblem horizon H, we observe the same effect as in Figure 8a, that the stopping time of HBPI-UCRL is adversely affected by setting 33

·106 BPI HBPI, H=9 HBPI, H=10 HBPI, H=11 HBPI, H=12 HBPI, H=13 HBPI, H=14 HBPI, H=15

1.6

Total Steps

1.4 1.2 1.0 0.8 0.6 0.4 0.2 40 (a) Stopping time of S for fixed H.

100 HH

120

140

(b) Stopping time of HH for fixed S.

Figure 8: Ablations varying S and HH while maintaining everything else constant. the horizon much too large. We conjecture that the stopping time of HBPI-UCRL depends on the effective subproblem horizon H, i.e. the number of time steps necessary to solve each subproblem in practice.

Figure 9: Stopping time τ of BPI-UCRL and HBPI-UCRL as a function of S in stochastic domains. Results for Stochastic Domains. Even though Assumption 3.1 is not guaranteed to hold for stochastic domains in which the probability of reaching a terminal state is less than 1, we carry out experiments in a version of the domain in Figure 1 with stochastic actions. Concretely, with probability 0.1 an action has a random effect among all neighboring states. We use the same setting as before with three seeds and varying the number of high-level states S. Figure 9 shows the stopping time of BPI-UCRL and HBPI-UCRL in this setting. We can observe that the stopping time of BPI-UCRL is no longer linear, while the stopping time of HBPI-UCRL still has a sublinear tendency. Results with Treasures. We also carry out experiments with HBPI-UCRL when treasures are present. Concretely, we consider a version of the example in Figure 1 with 2 × 2 rooms of size 3 × 3 and at most one treasure in each room. This example has almost 8, 000 states and over 300 million state-action-state triplets. Since BPI-UCRL has to maintain a count N t (s, a, s′ ) for each state-action-state triplet, the algorithm suffers extremely slow running time, which prevents it from solving the problem in practice. In contrast, Figure 10 shows the reward collected by HBPI-UCRL for a fixed subproblem horizon H = 10 and varying SMDP horizons H = 4, 6, 8.

Reward

1 HH = 40 HH = 60 HH = 80

0 0

0.5

1 t

1.5

2 ·104

Figure 10: Results for HBPI-UCRL with treasures.

Record · ID 422271 · SHA-256 4854967ce4c84104
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.