A theoretical case-study of Scalable Oversight in Hierarchical Reinforcement Learning

Authors: tom  yan
zachary  lipton
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:12:11

Abstract: A key source of complexity in next-generation AI models is the size of model outputs, making it time-consuming to parse and provide reliable feedback on. To ensure such models are aligned, we will need to bolster our understanding of scalable oversight and how to scale up human feedback. To this end, we study the challenges of scalable oversight in the context of goal-conditioned hierarchical reinforcement learning. Hierarchical structure is a promising entrypoint into studying how to scale up human feedback, which in this work we assume can only be provided for model outputs below a threshold size. In the cardinal feedback setting, we develop an apt sub-MDP reward and algorithm that allows us to acquire and scale up low-level feedback for learning with sublinear regret. In the ordinal feedback setting, we show the necessity of both high- and low-level feedback, and develop a hierarchical experimental design algorithm that efficiently acquires both types of feedback for learning. Altogether, our work aims to consolidate the foundations of scalable oversight, formalizing and studying the various challenges thereof.

Main paper: 
 introduction: 
 Next-generation AI models are poised to produce sophisticated outputs such as long-form texts and videos, and execute complex tasks as agents. To build these AIs responsibly, we need to better our understanding of scalable oversight: the ability to provide scalable human feedback to these complex models [2, 8, 15, 5] . An immediate, key challenge to overcome is the size of model outputs, making it time-consuming for humans to parse and provide reliable feedback on, even with AI-assistance [24, 27, 23] . To this end, in this work, we consider human labelers with bounded processing ability such that accurate feedback can only be provided for outputs below some threshold size. We are interested in answering the question: How can we scale this limited feedback to supervise a model with outputs larger than this limit? Verily, this task is difficult without further assumptions. If the model output can only be assessed in its entirety, it is impossible for humans to provide reliable feedback. Thus, we investigate a natural setup that gives us hope to overcome the limitation in feedback -when model outputs have hierarchical structure. Hierarchical structure exists in many high-dimensional outputs of interest, including long-form texts (books made up of chapters), videos (movies made up of scenes) and code (main functions made up of helper functions). Indeed, it reflects the way we humans produce many of our most complex creations.To formalize the setting, we study scalable oversight in a goal-conditioned hierarchical reinforcement learning (HRL) setup. Goal-oriented RL is a popular approach that has seen sizable success in leveraging state space structure to overcome sparse rewards over long horizons [16, 17, 10] . Our aim in this paper differs in using this as an entry-point into understanding how to scale up bounded human feedback, and formalizing the conceptual/technical challenges thereof. It turns out that one known advantage of HRL, besides more efficient exploration and efficient credit assignment, is the ability to enable scalable oversight.We consider a finite-horizon, Markov Decision Process (MDP) M = ⟨S, A, P, r, s 1 , H⟩, with finite state space S , finite action space A, transition probability P : S × A → ∆(S), reward r(s, a) : S × A → [0, 1] and finite horizon H. The learner interacts with M starting at state s 1 and the episode ends after H = H h H l time-steps. In this work, policies are trained using human feedback. And so, we assume that a human supervisor is needed to evaluate and provide reward r for trajectories τ ∼ π, P generated by policy π : S → A.Accompanying Example: Consider the task of learning to generate a long-form, argumentation essay. Providing feedback to an end-to-end policy is difficult as labelers would have to read through entire essays to rate the outputs, after which it may be difficult still to assign a single rating to the entire essay. A tractable alternative is to learn a hierarchical model, with a higher-level policy that generates the essay arguments (goals), and lower-level policies that flesh out these points (realize these goals). It would then be easier for the labeler to rate the shorter-length essay content, and also individual fleshed out arguments, in order to generate a rating on the whole. This approach also mirrors existing rubrics for scoring essays [1] .Bounded Feedback: To formalize the difficulty of human supervisors assessing long-form outputs, we assume that reliable feedback can only be provided for trajectories of length at most max(H h , H l ). In particular, this means that for the global policy π : S → A, it is infeasible to obtain reliable feedback for its trajectory τ ∼ π, P , as |τ | = H h H l . This thus motivates hierarchical learning, which makes possible the acquisition of reliable feedback in spite of bounded human supervision.Since we are unable to learn a single, monolithic policy, our goal instead will be to learn a set of smaller policies that make up a hierarchical policy. This set consists of a high-level policy π h : S → ∆(A h ) (outputs a high-level action a h at state s ∈ S), and a set of low-/sub-policies π l s,a h : S l s,a h → ∆(A), where S l s,a h ⊆ S is the set of all states reachable from s after H l steps. In a nutshell, the high-level policy designates goals by choosing high level actions. The low-level policies then aim to realize these goals, while also trying to achieve a high intermediate return.Importantly, both such policies act over a shorter horizon of at most max(H h , H l ), making it amenable for human supervisors to evaluate.Goal Function: in the goal-conditioned HRL setting, we assume access to a function g mapping high-level action a h at state s to a goal-state g(s, a h ) ∈ S l s,a h . For example, s is the current content of the essay, a h is the action (in natural language) "add an argument using X" and g(s, a h ) is the content of the essay with the "argument using X" included.Goal-conditioned sub-MDP: Given a high level action a h at state s, this defines the sub-MDP M (s, a h ), which has state space S l s,a h ⊆ S, action space A (action space of the original M), transition probabilities P restricted to S l s,a h , starting state s and finite horizon H l . The sub-MDP reward r l will be defined later and as we will see, an apt choice is important for achieving sublinear regret.High-level MDP: Given a set of low-level policies, π h may be thought of as operating over a high-level MDP with state space S, action space A h , starting state s 1 and finite horizon H h . Importantly, the high-level transition P ′ of this MDP is a function of the current set of low-level policies Pr ′ (s ′ |s, a h ) = Pr(s π s,a h H l = s ′ ), which denotes the distribution over the (final) H l th state that π l s,a h reaches. Furthermore, the high-level reward r h (s, a h ) = E sj ,aj ∼π s,a h ,P [ H l j=1 r(s j , a j )|s 1 = s] corresponds to the intermediate return of sub-policy π s,a h in M (s, a h ). Altogether, this gives rise to a key complication in hierarchical learning. This is that both the transitions and rewards in the high-level MDP are non-stationary, as sub-policies π s,a h are updated over time.Interaction Protocol: At each time-step t, the high level policy chooses a high level action a t based on current state s t . This defines the sub-goal state g(s t , a t ), along with the corresponding sub-MDP M (s t , a t ) with finite-horizon H l , in which sub-policy π l st,at is used to try to achieve the goal. The overall return of the high level policy π h and low-level policies {π l s,a } s,a∈S×A h is the sum of intermediate returns r(π l st,at ) incurred:V π h ,π l (s 1 ) = E at∼π h (st),st+1∼Pr(sπ l s t ,a t H l ) [ H h t=1 r(π l st,at )|s t=1 = s 1 ].Instantiation in the example: returning to our example, for a cogent essay, the arguments need to be logically related and built on top of each other. This results in a sequential decision making problem corresponding to the one solved by the high level policy π h . Given an argument g(s, a h ) to flesh out, the low level policy π l s,a h generates up to H l words, whose content aims to realize this argument. Additionally, low-level policies can incur intermediate rewards (return) for eloquent diction and clear structure when fleshing out the argument, all of which add to the essay's persuasiveness.Our aim is to learn a hierarchical policy, whose return is close to that of the optimal, goal-reaching hierarchical policy, which we define as follows. For brevity, from this point on, we will use a h and a interchangeably to denote high level action.Assumption 1 (Goal-Reachability). In every sub-MDP M (s, a), there exists a policy that achieves the goal g(s, a) almost surely. That is,there exists at least one policy π ∈ Π s,a in the policy class Π s,a such that Pr(s π H l = g(s, a)) = 1.In other words, we assume that the goal function g is well-defined in that it designates goals that are feasible to reach from the starting state s (e.g. the argument can be successfully fleshed out in H l words or less given the essay content thus far). To motivate this assumption, we note there that there are already many settings of interest, where we have prior knowledge of a good goal function. This is because we humans have often (and successfully) taken the hierarchical approach to build up to and produce these long-form creations. So we know what are good goals to set e.g. we write essays by first writing an outline of arguments, then expanding out each point in the outline. Indeed, this approach of explicitly encoding prior knowledge in the hierarchical learning algorithm has been done in both HRL literature (e.g. we know apriori mazes has hierarchical structure in that it consists of rooms [22] ) and scalable oversight literature (e.g. we know that books consists of chapters [27] ).With this assumption, there exists constant C large enough such that if π ∈ arg max π∈Πs,a r(π) + C • Pr(s π H l = g(s, a)), then π is goal-reaching and Pr(s π H l = g(s, a)) = 1. Definition 1. Define optimal low-level policies as π * s,a ∈ arg max π∈Πs,a r(π) + C • Pr(s π H l = g(s, a)). Define optimal high-level policy as π * = arg max π∈Π h V π,π * s,a (s 1 ).In words, π * s,a has the highest intermediate return of all goal-reaching policies. Now let π * be the optimal high-level policy fixing each sub-MDP policy to be π * s,a . Learning Goal: We wish to learn a set of near-optimal high-and low-level polices (π, {π s,a }) such that: V π * ,π * s,a (s 1 ) -V π,πs,a ≤ ϵ.The broad takeaway from this paper is that hierarchical structure, if it exists, can be provably used to scale up limited human supervision. That is:Hierarchical learning can enable scalable oversight.On a more technical level, this paper studies the challenge of training a set of (instead of a single) policies that work together to form the hierarchical policy. This is the more complicated problem we turn to solve when it is not feasible to train a monolithic policy, due to bounded human supervision. We thus consider learning in the goal-conditioned HRL setup, under both cardinal and ordinal feedback. A key insight that applies in both settings is that an apt sub-MDP reward design (a suitable penalty for non-goal reachability) is needed for bounding regret and controlling the exit state of learned low-level policies. This is so that learned sub-policies do not land at bad states with sizable probability. Doing so would then allow one to compose low-level policies together, and stabilize high-level policy learning in the high-level MDP. More specific takeaways for both types of feedback are as follows:• Under cardinal feedback, we develop a novel no-regret learning, Algorithm 1, that jointly learns a high-level and a set of low-level policies. Notably, Algorithm 1 only requires low-level feedback. Our main structural result in this setting is that hierarhical RL reduces to multi-task, sub-MDP regret minimization. Thus, the regret from the low-level accumulates additively (instead of say multiplicatively) as speculated upon in [15] .• Under ordinal feedback, we develop a novel hierarchical experiment-design Algorithm 2, building off of existing work on experiment design in preferenced-based RL [29] . A key observation is that in the ordinal case, low-level feedback may not be sufficient and highlevel feedback may be needed. This introduces complications in human supervision, as the high-level feedback would need to account for the current performance of sub-policies. To this end, we study two natural forms of feedback, requiring differing cognitive loads on the human supervisor. Through the experiment design algorithm we develop, we then analyze the differing sample complexity under the two types of feedback. Finally, we show that high-level feedback should not be used if low-level feedback is sufficient and one form of feedback, with higher cognitive load, leads to better sample complexity. 
related works: 
 HRL under cardinal rewards: There has been sizable interest in understanding of the sample complexity of HRL algorithms, which to our knowledge has thus focused on learning from cardinal rewards. On this subject, the two closest papers to that of ours are [22] and [25] . [22] studies goal-conditioned HRL with the key result being a sample complexity lower bound associated with a given hierarchical decomposition. On the upper-bound side, an algorithm (SHQL) is presented, albeit without theoretical guarantees. By contrast, our work presents a learning algorithm with provable guarantees, and further shows that learning in goal-conditioned HRL reduces to multi-task, sub-MDP regret minimization.[25] studies HRL under the options framework, providing a model-based, Bayesian algorithm with access to a prior distribution over MDPs that is updated over time. It does not adaptively learn subpolicies based on observed returns, computing instead an option for every exit-profile and equivalence class at each time during model-based planning. By contrast, our work does not assume knowledge of the prior nor ability to update posteriors, and does adaptively explore sub-MDPs via the UCB principle. Additionally, [25] demonstrate that when the size of the set of exit ("bottleneck") states is small, learning is efficient. Our work shed further light on this insight by showing that under a suitable sub-MDP reward, we can induce a small set of exit states with high probability. Thus, even though the total number of possible exit-states may be high, this condition is sufficient for learning with sublinear-regret.There has also been considerable interest in bandits/RL from preferences [26, 28, 18, 14, 30, 29] . Following the demonstrated success of RLHF [9, 31, 19, 4] , there has been great interest in studying offline RL from preference feedback, and particularly experiment design for enhanced sample efficiency [30, 29] . Due to the success of RLHF in alignment, we also consider studying scalable oversight in this setup. Please see the Appendix A for further discussions on scalable oversight and goal-conditioned RL. 
learning from cardinal feedback: 
 We begin by considering the setting when feedback is in the form of cardinal rewards. As noted before, in HRL, the high-level policy performance is dependent on the low-level policies performance. Thus, a naive approach is to learn near-optimal sub-policies in every sub-MDP M (s, a), and then learn a high-level policy on top. However, a more sample efficient approach is to strategically explore sub-MDPs, and discover sub-policies with high intermediate returns in tandem with a high level policy that visits these "good" sub-MDPs. Please see the Appendix C for all the proofs. Note that in what follows, for brevity, theoretical statements will contain the phrase "with high probability" and the appendix will contain proofs that formalize this guarantee.3.1 Sub-MDP reward design for Hier-UCB-VIWe are interested in adaptively learning the necessary sub-policies (the useful goals to achieve) and the associated high level policy that invokes these sub-policies. It is natural then to adopt an upper confidence bound approach and construct an exploration bonus that tracks the best/unexplored sub-MDPs. To this end, we develop an adaptation of the classic UCB-VI algorithm [3] . We highlight two key ingredients needed to construct the Hier-UCB-VI Algorithm 1. H l ) ≈ 0 means the return from hereon out (and hence the overall return) will be low. Thus, in sub-policy learning, we also need to consider the goodness of the exit-state. But how can we incentivize sub-policies to land at "good" states without being able to calculate V ? Luckily, in the goal-conditioned setting, there is a natural answer for a "good" exit-state: g(s, a).To operationalize this, we design a sub-MDP reward that trades-off between intermediate sub-MDP return and goal-reachability. In sub-MDP M (s, a), at time-step h, sub-MDP reward r l,h (s ′ , a ′ ) = r(s ′ , a ′ ) + κ1(h = H l ∧ s ′ = g(s, a)). Crucially, here we set the weighting κ = max(2H h H l , C), which corresponds to an upper bound on the regret should we not reach the goal-state.UCB construction: Next, we wish to obtain an UCB for r(π * s,a ). Our main observation is that by using a no-regret subroutine for learning in M (s, a), the regret guarantee directly translates to a UCB. Due to our choice of sub-MDP reward r l , the UCB includes a penalty on non-goal reachability. Lemma 1 (UCB implied by sub-MDP regret). Let U B(R n (s, a)) be an upper bound on sub-MDP M (s, a)'s cumulative regret after n rounds. Defineβ = (κ + H l )2 log( |C(S,A)|H h K δ ) and bonus, b s,a r (n) = U B(R n (s, a)) + β √ n n - κ n n i=1 1(s π i s,a H l ̸ = g(s h , a h )).Then, the average reward plus bonus rn (s, a) + b s,a r (n) is an UCB for r(π * s,a ) with high probability. High-level MDP transition stabilization: An additional benefit of incentivizing goal-reachability is that we know the idealized transition probability in the high-level MDP. As mentioned before, another key difficulty with HRL is that the empirically estimated transitions in the high-level MDP drifts over time. In our algorithm, the key stabilization approach is to avoid estimation and set the transition in the upper bound Q i to be the idealized transition (g(s, a) w.p. 1). This allows us to prove our regret guarantee as described below.We start with a definition on clusters of equivalent sub-MDPs. Let there be C(S, A h ) such clusters. In the most general setting, it is not known apriori if there is any shared structure, in which case each sub-MDP will simply be its own cluster. Definition 2 (Equivalent sub-MDPs [25] ). Two subMDPs M (s, a) and M (s ′ , a ′ ) are equivalent if there is a bijection F between state space, and through F, the subMDPs have the same transition probabilities and rewards.Our main structural result is that HRL regret decomposes to multi-task, sub-MDP regret in the cardinal reward setting. This has the implication that only low-level feedback is needed for regret Algorithm 1 Hierarchical-UCB-VI (Hier-UCB-VI)1: Initialize D = ∅, Q H h +1 (s, a) = H h H l ∀s, a, V H h +1 = 0, κ = max(C, 2H h H l ) 2: for episode k = 1, ..., K do 3:for timestep i = H h , ..., 1 do Set:EQUATIONfor s ∈ S do 9: V i (s) = max a∈A h Q i (s, a)s k h ,a k h in M (s k h , a k h )) as the high-level reward r(s k h , a k h ) = r(π N h,k s k h ,a k h ) 14: Add to dataset D = D ∪ {(h, s k h , a k h , r(s k h , a k h )}minimization in the cardinal reward case, which as we will see in the ordinal reward case will not always be true.Theorem 1 (HRL regret minimization reduces to multi-task, sub-MDP regret minimization). Let U B(R N K,H h (s,a) ) be an upper bound on sub-MDP M (s, a)'s cumulative regret over N K,H h (s, a) visits:EQUATIONProof Sketch. We describe the key regret decomposition. After some manipulation, the regret may decompose into the following form,K k=1 V k 1 (s 1 ) -V π k 1 (s 1 ) ≤ K k=1 H h h=1 ρ k h + γ k h + σ k h + ζ kh , which may be parsed as follows.ρ k h = U B(r π * (s, a)) -r(π N k,h s k h ,a k h) captures the regret due to sub-optimal intermediate return, the return of π * S,a versus the return ofπ s k h ,a k h . γ k h = (P h -P π k,h )V π * h+1 (s k h , a k h ), σ k h = (P h -P π k,h )(V k h+1 -V π * h+1 )(s k h , a k h) captures the regret due to sub-optimal policies missing goal-reachability. Here P h is the idealized transition (goal-reaching), while P π k,h is the transition induced by the current sub-policy.ζ k h = P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) -(V k h+1 -V π k h+1 )(s k h+1) is a martingale difference that concentrates via Azuma Hoeffding, and is dominated by the previous three sums.H h h=1 ρ k h + γ k h + σ k h + ζ k h , we observe that γ k h , σ k h ≤ 2H h H l P π k,h (s k h+1 ̸ = g(s k h , a k h )). The key remaining step is to recognize that ρ k h + γ k h + σ k h resembles the instantaneous regret in M (s k h , a k h ), and the result follows after some further bounding and rearrangement.For a concrete bound, we note that if A is set as the classic UCB-VI algorithm, then we attain the usual Õ( √ K) regret. Furthermore, we note that our bound is flexible in that one can choose more specialized learning algorithms A to leverage prior knowledge. For instance, if it is known that sub-MDPs are linear, one may choose to invoke multi-task RL algorithms that offer more refined regret bounds for U B(R N K,H h (s,a) ) [11] .Goal Selection: An astute reader will note that the return of the learned hierarchical policy is close to V * 1 (s 1 ), the return of the optimal hierarchical policy under goal function g. In other words, our learned policy is only as good as the goal function g we choose.One way to relax the assumption that we have a good goal function g is to assume we have access to multiple goal functions to choose from: g 1 , .., g n . Then, an useful corollary of the sublinear Hier-UCB-VI regret bound, 1K [ K k=1 V g i , * 1 (s 1 ) -V g i ,π k 1 (s 1 )] ≤ Õ( √ K), is that it directly implies an UCB on V g i , *1 (s 1 ) (optimal return under goal g i ). Hence, we may apply any UCB-based bandit algorithm on top of this to compete with the return of the best goal out of all the candidates {g j } j∈[n] . 
learning from preference feedback: 
 In the previous section, we develop an algorithm to efficiently learn a hierarchical policy, purely from low-level, cardinal feedback. Now, we consider learning from ordinal (preferences) feedback. Our first observation is that the low-level feedback is no longer sufficient for learning a good policy.Proposition 1 (Non-identifiability of ranking among sub-MDP returns). For any deterministic highlevel policy learning algorithm with N l samples of low-level feedback, there exists a MDP instance that induces regret constant in N l .The intuition for this is simply that low-level, ordinal feedback can only identify rankings of low-level policies specific to a goal (sub-MDP), but not necessarily low level policies across differing goals. Thus, no matter how large the low-level sample-size N l , the regret is non-vanishing in N l and hence high-level feedback may be needed to learn. Please see Appendix D for all proofs of results in this section.The canonical approach to learning from preferences is reward modeling. Following previous works, we study offline experiment design and assume we have the ability to collect comparison feedback data, in our hierarchical setting both high and low-level data that are then used to learn the reward model [29] . For tractable analysis, we consider the commonly studied linear reward setup [21, 20, 30, 29] .Assumption 2 (Linear Reward Parametrization). Suppose we have access to some feature map ϕ : S × A → R d , M has linear reward parametrization w.r.t. ϕ if there exists an unknown, reward vector θ * ∈ R d such that r(s, a) = ⟨ϕ(s, a), θ * ⟩ for all s, a ∈ S × A.Given trajectory τ = (s 1 , a 1 , ..., s H , a H ), we may then define trajectory feature ϕ(τ ) = si,ai∈τ ϕ(s i , a i ), and policy feature expectation under transitions P , ϕP (π) = E τ ∼π,P [ϕ(τ )].With known feature map ϕ and unknown reward parameter θ * , the preference feedback o t follows the Bradley-Terry-Luce (BTL) model [6] .Assumption 3. For trajectories τ 1 , τ 2 : Pr(τ 1 ≻ τ 2 ) = σ((θ * ) T (ϕ(τ 1 ) -ϕ(τ 2 ))).With the definitions out of the way, we now describe a conceptual challenge that we encounter when learning from high-level feedback, which as we have shown before may be necessary for learning.What can we assume about the high-level labeler's knowledge? Consider a high level trajectoryτ j = {(s j i , a j i )} H h i=1 . ϕ(τ j ) = i∈[H h ] ϕ(s j i , a j i );the key difficulty is that sub-MDP feature expectation ϕ(s j i , a j i ) is dependent on the sub-policy deployed in M (s j i , a j i ). Thus, the high level labeler will have to have in mind some sub-policy π s,a , when making the comparison. We study two natural types of feedback:1. Comparisons based on current sub-policy execution: It is natural to first assume that the labeler envisions ϕ(s j i , a j i ) = ϕ(π t s j i ,a j i ) at time t. In words, it is equivalent to asking: "How well does the high level policy do given current execution of sub-goals?" Current-feedback of this form has the caveat that the labeler will have know about the performance of the current set of sub-policies π t s,a (potentially through AI-assisted means). This knowledge would need to be updated over time as low-level policies π t s,a improve, which introduces a sizable cognitive load. 2. Comparisons based on idealized sub-policy execution: To reduce the cognitive load on the labeler, it is natural to fix the sub-policies used in the comparisons. A natural choice then is for the labeler to envision ϕ(s j i ,a j i ) = ϕ(π * s j i ,a j i ).In words, it is equivalent to asking: "How well does the high level policy do given perfect execution of the sub-goals?" Instantiated in some examples, this would be: "how good is the essay if each argument is fleshed out perfectly" or "how good is the code if each helper function is implemented perfectly".Idealized-feedback of this form has the caveat that the high-level feedback will be a mismatch of how the current sub-policies actually execute. Although it has the advantage that the labeler is no longer required to (somehow) keep track of low-level sub-policies, thus reducing the cognitive load.In what follows, we consider both types of feedback, showing that learning from idealized-feedback is possible. As we note, a drawback of idealized-feedback is that it is biased with respect to the realized features (since these are generated under current policies π t s,a ), while current-feedback is unbiased. We present an upper bound on the bias below. Lemma 2 (Bias of idealized-feedback). Suppose there are N h , N l high, low-level trajectories, bias b is such that:∥b∥ 2 = N h t=1 |⟨θ * , ϕ π N l (π i 1 ) -ϕ π N l (π i 2 )⟩ -⟨θ * , ϕ π * (π i 1 ) -ϕ π * (π i 2 )⟩| 2 = O(N h /N l ).Proposition 2 (Reward model learning). Let θ M LE = arg min θ ℓ D (θ) and let C b denote an upper bound on bias C b ≥ ∥b∥, and γ, B constants. We have that with high probability:∥θ * -θ M LE ∥ Σh N h +λI ≤ C C b √ N h γ 2 + C 2 b + d + log(1/δ) γ 2 + λB 2We now construct a hierarchical, preference-learning algorithm that invokes REGIME, a contemporary preference-learning algorithm with provable guarantees, as sub-routine for sub-MDP learning [29] .To start, we again need to incentivize goal-reaching in the sub-MDP reward. As such, given original feature ϕ orig , we introduce an additional feature accounting for goal-reachability. For trajectory τ , defineϕ i (s τ i , a τ i ) = [ϕ orig (s τ i , a τ i ), 1(i = H l ∧ s τ i = g(s, a))] and for policy π, feature expectation ϕ i (s π i , a π i ) = [ϕ orig (s π i , a π i ), 1(i = H l ) Pr(s π H l = g(s, a))]. The corresponding reward vector will also change to become θ * = [θ * orig , κ] for unknown θ * orig , κ. Assumption 4. Through instructions to the labeler, κ may be raised beyond a threshold of our choosing.That is, we assume we can provide instructions to the labeler, emphasizing goal-reachability such that κ is higher than some given threshold. As before, we take the threshold to be max(C, 2H h H l ). And so while κ is unknown, we know that κ ≥ max(C, 2H h H l ). With this set up, we can then bound the regret due to sub-optimal sub-policies, and sub-optimal simulator P ϵ ′ , both of which are needed in the final regret analysis. Lemma 3 (Regret due to sub-optimal sub-policies). For any high-level policy π, with high probability:⟨ϕ π * ,P (π) -ϕ π N l ,P (π), θ * ⟩ ≤ H h ( C 1 √ N l + C 2 ϵ ′ )where this bound makes use of the REGIME guarantee on sub-MDP M (s, a) that |⟨ϕ P (π * s,a ), θ * ⟩ -ϕ P ϵ ′ (π N l s,a ), θ * | ≤ C1 √ N l + C 2 ϵ ′ [29].Algorithm 2 Hierarchical-REGIME (Hier-REGIME)Require: High-level policy class Π h , low level-policy classes Π l s,a , simulator P ϵ ′ with ϵ ′ -precision 1: for episode n = 1, ..., N l do 2:(π n 1 , π n 2 ) ← arg max π1,π2∈ s,a Π l s,a ∥ϕ P ϵ ′ (π 1 ) -ϕ P ϵ ′ (π 2 )∥ ( Σl n ) -1▷ explore using policy feature expectation across sub-MDPs 3:Σl n+1 = Σl n + (ϕ P ϵ ′ (π n 1 ) -ϕ P ϵ ′ (π n 2 ))(ϕ P ϵ ′ (π n 1 ) -ϕ P ϵ ′ (π n 2 )) T 4:Generate trajectories τ n 1 , τ (π n 1 , π n 2 ) ← arg max π1,π2∈Π h ∥ϕ π N l ,P ϵ ′ (π 1 ) -ϕ π N l ,P ϵ ′ (π 2 )∥ ( Σh n ) -1▷ high-level policy feature expectation generated using π N l s,a 9:Σh n+1 = Σh n + (ϕ π N l ,P ϵ ′ (π 1 ) -ϕ π N l ,P ϵ ′ (π 2 ))(ϕ π N l ,P ϵ ′ (π 1 ) -ϕ π N l ,P ϵ ′ (π 2 )) T 10:Generate trajectories τ n 1 , τ Lemma 4 (Regret due to sub-optimal simulator P ϵ ′ ). Let Φ π N l ,P ϵ ′ (π) denote the feature expectation under high level policy π, sub-MDP policies π N l and transitions P ϵ ′ . With high probability, for any high level policy π:|⟨ϕ π N l ,P (π) -ϕ π N l ,P ϵ ′ (π), θ * ⟩| ≤ O((H h d 2 + H 3 h H 2 l )ϵ ′ + H 2 h H l κ )Now, we present the Hier-REGIME Algorithm 2. At a high-level description goes as follows. First, we invoke one copy of REGIME across all sub-MDPs with shared exploration (L1-4) and learned reward (L5). Next, we use the learned reward to compute sub-MDP policies π N l s,a for each sub-MDP M (s, a) (L6). Finally, we invoke one copy of REGIME for the high-level MDP, where the feature function is defined as ϕ π N l s,a ,P ϵ ′ (L8). Next, we note two properties about Algorithm 2.A key aspect of experiment design in offline RL is ensuring sufficient coverage with exploration. The difficulty with coverage in the hierarchical setting is that at first glance, we may need to search for pairs of trajectories over(π 1 , {π 1 s,a }), (π 1 , {π 2 s,a }) ∈ (Π h , × s,a Π l s,a), instead of over π 1 , π 2 ∈ Π h . However, we show that in the goal-HRL case, we can fix the sub-policies to be π N l s,a (for N l large enough), and this is sufficient to compete with the optimal, hierarchical policy. Additionally, unlike the tabular setting, sub-MDPs now share a common reward parameter θ * , thus allowing us to jointly, instead of separately as in tabular case, explore across sub-MDPs.Sufficiency of low-level feedback: Through the algorithm, we can observe that low-and high-level exploration generates feature expectations set:{ϕ P ϵ ′ (π 1 ) -ϕ P ϵ ′ (π 2 ) | π 1 , π 2 ∈ s,a Π l s,a } and {ϕ P ϵ ′ (π 1 ) -ϕ P ϵ ′ (π 2 ) | π 1 , π 2 ∈ Π h , π s,a = π N ls,a ∀s, a}. Therefore, when coverage of high level policy is subsumed by low-level features already (the latter is a subset of the former), it suffices to explore only using low-level feedback. As shown before in Proposition 2, it is not always sufficient. However, as we will see below, when it is sufficient, using low-level feedback leads to better rates. First, we derive the regret decomposition and then use it evaluate the sample complexity.Theorem 2. With high probability, under N h > 0:V π * ,π * -V π,π N l ≤ ⟨ϕ π * ,P (π * ) -ϕ π N l ,P (π * ), θ * ⟩ + 1 √ N h (2d log(1 + N h d ))∥θ * -θ∥ Σh N h + |⟨ϕ π N l ,P (π * ) -ϕ π N l ,P ϵ ′ (π * ), θ * ⟩| + |⟨ϕ π N l ,P ϵ ′ (π) -ϕ π N l ,P (π), θ * ⟩|To parse this, the regret decomposes into four terms. The first term is the regret due to sub-optimality in low-level policies π N l . The remaining three terms are derived from sub-optimality due to high-level policy π, decomposing into the second term on regret due to bias in learned reward θ, the third and fourth term on regret due to sub-optimality of simulator P ϵ ′ .A main benefit of developing a learning Algorithm 2 is that we can then quantitatively assess the sample complexity associated with the two types of human feedback. As one may expect, there is a tradeoff between better sample complexity and cognitive load, with current-feedback attaining better sample efficiency but also requiring higher cognitive load on the human supervisor.Corollary 1. Using Theorem 2, we obtain the following rates in terms of data tradeoffs:• Idealized-feedback and required high-/low-level feedback: the overall rate comes out to O(N-1/4 l + N -1/2 h). While high level trajectories provide additional coverage, it also incurs bias linear in N h of the bias of the low-level trajectories, thus slowing down the rate (Lemma 2).• Current-feedback and required high-/low-level feedback: the overall rate comes out toO(N -1/2 l + N -1/2 h). The current-feedback is unbiased and results in more efficient reward learning with ∥θ * -θ∥ Σh ). In a nutshell, this is because we can explore with just N l low-level samples which is unbiased, resulting in ∥θ * -θ∥ Σl N l = O(1). Hence, both exploration and reward learning is efficient.Under current-feedback, following Lemma 2 of [29] , ∥∆∥ Σ h n +λI ≤ Õ(1). Now, we consider the bias in learned reward under idealized-feedback. Proposition 6. Let θ M LE = arg min θ ℓ D (θ) and let C b ≥ ∥b∥. Then with probability at least 1 -δ/5:∥∆∥ Σn+λI ≤ O C b γ 2 √ n + C 2 b + d + log(1/δ) γ 2 n + λB 2 where Σ n = 1 n n i=1 x i x T i + λI. Proof. Define ∆ = θ M LE -θ * .As in [30] , we have the same convexity result due to ⟨θ,x i ⟩ ∈ [-2LB, 2LB]. Suppose we let max x ∥x∥ ≤ L and max θ∈Θ ∥θ∥ ≤ B, then with γ = 1 2+exp(-2LB)+exp(2LB) , we have that:ℓ(θ * + ∆) -ℓ(θ * ) -⟨∇ℓ(θ * ), ∆⟩ ≥ γ∥∆∥ 2 ΣAnd so,ℓ(θ M LE ) ≤ ℓ(θ * ) ⇒ ℓ(θ * + ∆) -ℓ(θ * ) -⟨∇ℓ(θ * ), ∆⟩ ≤ -⟨∇ℓ(θ * ), ∆⟩Thus,γ∥∆∥ 2 Σ ≤ ∥∇ℓ(θ * )∥ (Σ+λI) -1 ∥∆∥ (Σ+λI)The key part is bounding ∥∇ℓ(θ * )∥ (Σ+λI) -1 . We have that:∇ℓ(θ * ) = - 1 n n i=1 [1{y i = 1}σ(⟨θ * , x i ⟩) -1{y i = 0}(1 -σ(⟨θ * , x i ⟩)]x i = - 1 n X T (V + b)wherev i = σ(⟨θ * , x * i ⟩) w.p 1 -σ(⟨θ * , x * i ⟩) and -(1 -σ(⟨θ * , x * i ⟩)) w.p σ(⟨θ * , x * i ⟩). And so, entry- wise V is such that E[V i ] = 0 and |V i | ≤ 1. Note that V i are independent due to the independence of the random variables Y i .Extra term bias is defined as:b i = 1{y i = 1}(σ(⟨θ * , x i ⟩) -σ(⟨θ * , x * i ⟩)) -1{y i = 0}(1 -σ(⟨θ * , x i ⟩ -(1 -σ(⟨θ * , x * i ⟩)) = σ(⟨θ * , x i ⟩) -σ(⟨θ * , x * i ⟩)By definition, C b is such that: ∥b∥ ≤ C b . As before, define M = 1 n 2 X(Σ + λI) -1 X T . We use the fact that ∥M ∥ op ≤ 1/n. Then, we have that:∥∇ℓ(θ * )∥ 2 (Σ+λI) -1 = (V + b) T M (V + b) = V T M V + 2V T M b + b T M b ≤ C d + log(1/δ) n + 2∥V ∥∥M b∥ + b T M b (by Matrix Bernstein, V T M V ≤ C d+log(10/δ) n w.p. ≥ 1 -δ/10) ≤ C d + log(1/δ) n + 2∥V ∥ 1 n ∥b∥ + C 2 b n (using that ∥M ∥ op ≤ 1/n) ≤ C d + log(1/δ) n + 2(C 2 √ n 1 n )C b + C 2 b n (by Hoeffding ∥V ∥ ≤ O(log(10/δ) √ n) w.p. ≥ 1 -δ/10.) ≤ O( C b √ n + C 2 b + d + log(1/δ) n ) γ∥∆∥ 2 Σ+λI ≤ ∥∇ℓ(θ * )∥ (Σ+λI) -1 ∥∆∥ (Σ+λI) + λ(γ∥∆∥ 2 ) ≤ ∥∇ℓ(θ * )∥ (Σ+λI) -1 ∥∆∥ (Σ+λI) + 4λγB 2This implies that with probability ≥ 1 -δ:∥∆∥ Σ+λI ≤ C C b γ 2 √ n + C 2 b + d + log(1/δ) γ 2 n + λB 2Corollary 4. Let θ M LE = arg min θ ℓ D (θ), then under s,a E s,a , with probability ≥ 1 -δ/5:∥θ * -θ M LE ∥ Σh N h +λI ≤ C 1 γ 2 √ N l + 1 γ 2 N l + d + log(1/δ) γ 2 N h + λB 2whereΣ N h = 1 N h N h i=1 x i x T i .Let the event that this holds for learning from sub-MDP trajectories be E h 1 .Proof. Firstly,∥b∥ ≤ 2H h ( C 1 √ N l + C 2 ϵ ′ ) N h = O( √ N h √ N l + N h ϵ ′ )With this, we have that: ∥∆∥ ΣN h +λI = O C b γ 2 √ N h + C 2 b + d + log(1/δ) γ 2 N h + λB 2 ) = O   N h /N l + √ N h ϵ ′ γ 2 √ N h + N h /N l + N h ϵ ′2 + d + log(1/δ) γ 2 N h + λB 2   ∥θ * -θ n ∥ Σn ≤ √ 2∥θ * -θ n ∥ Σn + √ 8nC(ϵ ′ , δ) ≤ 2∥θ * -θ n ∥ Σn + O(B d log n/δW ) + √ 8nC(ϵ ′ ,⟨ϕ π * ,P (π) -ϕ π N l ,P (π), θ * ⟩ ≤ H h ( C 1 √ N l + C 2 ϵ ′ )Proof.⟨ϕ π * ,P (π) -ϕ π N l ,P (π),θ * ⟩ = H h h=1 E s h ,a h ∼π,π N l ,P E s h+1 ∼π N l (s h ,a h ),P [r(π * (s h , a h )) + V π,π * h+1 (g(s h , a h )) -(r(π N l (s h , a h )) + V π,π N l h+1 (s h+1 ))] = H h h=1 E s h ,a h ∼π,π N l ,P [r(π * (s h , a h )) -r(π N l (s h , a h )) + P (s π N l h+1 ̸ = g(s h , a h ))(V π,π * h+1 (g(s h , a h )) -V π,π N l h+1 (s h+1 ))] ≤ H h h=1 E s h ,a h ∼π,π N l ,P [r(π * (s h , a h )) -r(π N l (s h , a h )) + P (s π N l h+1 ̸ = g(s h , a h ))κH h H l ] = H h h=1 E s h ,a h ∼π,π N l ,P [r(π * (s h , a h )) + P (s π * h+1 = g(s h , a h ))κH h H l -r(π N l (s h , a h )) -P (s π N l h+1 = g(s h , a h ))κH h H l ] = H h h=1 E s h ,a h ∼π,π N l ,P [⟨ϕ(π * (s h , a h )), θ * ⟩ -⟨ϕ(π N l (s h , a h )), θ * ⟩] ≤ H h ( C 1 √ N l + C 2 ϵ ′ )Because for any s h , a h , ⟨ϕ(π * (s h , a h )), θ * ⟩ -⟨ϕ(πN l (s h , a h )), θ * ⟩ ≤ C1 √ N l + C 2 ϵ ′ .Lemma 18 (Lower bound on Reachability Probability). We have that under event s,a E s,a ∩ E l 1 ∩ E l 2 :P (s π N l H l ̸ = g(s, a)) ≤ 1 κH h + C 1 κH h H l √ N l + C 2 ϵ ′ κH h H l and P ϵ ′ (s π N l H l ̸ = g(s, a)) ≤ 1 κH h + C 1 κH h H l √ N l + C 2 ϵ ′ κH h H l + H l ϵ ′Proof. Due to the regret guarantee, we have that:C 1 √ N l + C 2 ϵ ′ ≥ ⟨ϕ P (π * ) -ϕ P (π N l ), θ * ⟩ = r(π * ) + κH h H l • 1 -r(π N l ) -κH h H l • P (s π N l H l = g(s, a)) ≥ 0 -H l + κH h H l • P (s π N l H l ̸ = g(s, a))Thus, we have that:P (s π N l H l ̸ = g(s, a)) ≤ 1 κH h + C 1 κH h H l √ N l + C 2 ϵ ′ κH h H lAdditionally, we have that from Lemma 5.1:|d π N l H l (g(s, a)) -dπ N l H l (g(s, a))| = |P (s π N l H l ̸ = g(s, a)) -P ϵ ′ (s π N l H l ̸ = g(s, a))| ≤ H l ϵ ′Thus,P ϵ ′ (s π N l H l ̸ = g(s, a)) ≤ 1 κH h + C 1 κH h H l √ N l + C 2 ϵ ′ κH h H l + H l ϵ ′Define goal non-reachability probability to be:δ = 1 κH h + C1 κH h H l √ N l + C2ϵ ′ κH h H l + H l ϵ ′ .Lemma 19. Let Φ π N l ,P ϵ ′ (π) denote the feature expectation under high level policy π, sub-MDP policies π N l and MDP transitions P ϵ ′ . Under event s,a E s,a ∩ E l 1 ∩ E l 2 , we have that, for any high level policy π:|⟨ϕ π N l ,P (π) -ϕ π N l ,P ϵ ′ (π), θ * ⟩| ≤ 2H h BRd 2 ϵ ′ + 8H 3 h H l δProof. Let E reach denote the event that roll-out τ ∼ π, π N l , P is such that all high level goals are reached, and similarly event E ′ reach for roll-out τ ′ ∼ π, π N l , P ϵ ′ .By union bound, Pr(¬E reach ) = Pr(∃s i , a i , sπ N l (si,ai) H l ̸ = g(s i , a i )) ≤ H h i=1 Pr(s π N l (si,ai) H l ̸ = g(s i , a i )))) ≤ H h δ, and similarly Pr(¬E ′ reach ) ≤ H h δ. |⟨ϕ π N l ,P (π) -ϕ π N l ,P ϵ ′ (π), θ * ⟩| ≤ |E τ ∼π,π N l ,P [⟨ϕ(τ ), θ * ⟩|E reach ] Pr(E reach ) -E τ ∼π,π N l ,P ϵ ′ [⟨ϕ(τ ), θ * ⟩|E ′ reach ] Pr(E ′ reach )| + |E τ ∼π,π N l ,P [⟨ϕ(τ ), θ * ⟩|¬E reach ] Pr(¬E reach ) -E τ ∼π,π N l ,P ϵ ′ [⟨ϕ(τ ), θ * ⟩|¬E ′ reach ] Pr(¬E ′ reach )| ≤ |E τ ∼π,π N l ,P [⟨ϕ(τ ), θ * ⟩|E reach ] Pr(E reach ) -E τ ∼π,π N l ,P ϵ ′ [⟨ϕ(τ ), θ * ⟩|E ′ reach ] Pr(E ′ reach )| + 2(H h δ)(H h H l ) (since |E τ ∼π,π N l ,P [⟨ϕ(τ ), θ * ⟩|¬E reach ] Pr(¬E reach )| ≤ (H h δ)(H h H l ) and likewise the other term) = | Pr(E reach ) H h h=1 s h ,a h d(s h , a h )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E reach ] -Pr(E ′ reach ) H h h=1 s h ,a h d(s h , a h )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ reach ]| + 2H 2 h H l δ(under goal reachability, high-level state visitation measure d(s h , a h ) is the same)≤ H h h=1 s h ,a h d(s h , a h )| Pr(E reach )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E reach ] -Pr(E ′ reach )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ reach ]| + 2H 2 h H l δ = H h h=1 s h ,a h d(s h , a h )| Pr(E reach )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] -Pr(E ′ reach )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + 2H 2 h H l δ (E s h ,a h reach is the event that g(s h , a h ) is reached under π N l , P ) ≤ H h h=1 s h ,a h d(s h , a h ) Pr(E reach )|E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] -E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + |(Pr(E reach ) -Pr(E ′ reach ))E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + 2H 2 h H l δ ≤ H h h=1 s h ,a h d(s h , a h ) |E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] -E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + (H h δ)(H h H l ) + 2H 2 h H l δ (since Pr(E ′ reach ), Pr(E reach ) ∈ [1 -H h δ, 1])To finish, we will relate the expression to |⟨ϕP ϵ ′ (π N l (s h , a h )) -ϕ(π N l (s h , a h )), θ * ⟩|. ≤ H h h=1 s h ,a h d(s h , a h )|E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] -E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + 3H 3 h H l δ = H h h=1 s h ,a h d(s h , a h )| 1 Pr(E s h ,a h reach ) Pr(E s h ,a h reach )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] - 1 Pr(E ′ s h ,a h reach ) Pr(E ′ s h ,a h reach )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + 3H 3 h H l δ ≤ H h h=1 s h ,a h d(s h , a h ) 1 Pr(E s h ,a h reach ) | Pr(E s h ,a h reach )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|E s h ,a h reach ] -Pr(E ′ s h ,a h reach )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|E ′ s h ,a h reach ]| + H h ( 1 1 -δ -1)H h H l + 3H 3 h H l δ (⋄) ≤ H h h=1 s h ,a h d(s h , a h ) 1 1 -δ | Pr(¬E s h ,a h reach )E[⟨ϕ P (π N l (s h , a h )), θ * ⟩|¬E s h ,a h reach ] -Pr(¬E ′ s h ,a h reach )E[⟨ϕ P ϵ ′ (π N l (s h , a h )), θ * ⟩|¬E ′ s h ,a h reach ]|+ |E[⟨ϕ P ϵ ′ (π N l (s h , a h )) -ϕ P (π N l (s h , a h )), θ * ⟩]| + 4H 3 h H l δ (using that 1 1-δ -1 ≤ 1) ≤ H h h=1 s h ,a h d(s h , a h ) 1 1 -δ 2(δ)(H h H l ) + BRd 2 ϵ ′ + 4H 3 h H l δ (⋄⋄) ≤ H h h=1 s h ,a h d(s h , a h )2 2H h H l δ + BRd 2 ϵ ′ + 4H 3 h H l δ ( 1 1-δ ≤ 2) ≤ 2H h BRd 2 ϵ ′ + 8H 3 h H l δ = C(ϵ ′ , δ) (⋄) : | Pr(E ′ s h ,a h reach ) Pr(E s h ,a h reach ) -1| ≤ max(1 -(1 -δ) 1 1-δ -1) since Pr(E ′ s h ,a h reach ), Pr(E s h ,a h reach ) ∈ [1 -δ, 1]. (⋄⋄) : |⟨ϕ P ϵ ′ (π N l (s h , a h )) -ϕ P (π N l (s h , a h )), v⟩| ≤ BRd 2 ϵ ′ and Pr(¬E s h ,a h reach ), Pr(¬E ′ s h ,a h reach ) ∈ [0, δ]Lemma 20 (use of the Elliptical Lemma).⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ * -θ⟩ ≤ 1 √ N h (2d log(1 + N h d ))∥θ * -θ∥ ΣN h Proof. ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ * -θ⟩ ≤ ∥ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π)∥ Σ-1 N h ∥θ * -θ∥ ΣN h ≤ 1 N h N h i=1 ∥ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π)∥ Σ-1 i ∥θ * -θ∥ ΣN h ( Σ-1 N h ⪯ Σ-1 i ) ≤ 1 N h N h i=1 ∥ϕ π N l ,P ϵ ′ (π i 1 ) -ϕ π N l ,P ϵ ′ (π i 2 )∥ Σ-1 i ∥θ * -θ∥ ΣN h (definition of π i 1,2 ) ≤ 1 √ N h N h i=1 ∥ϕ π N l ,P ϵ ′ (π i 1 ) -ϕ π N l ,P ϵ ′ (π i 2 )∥ 2 Σ-1 i ∥θ * -θ∥ ΣN h ≤ 1 √ N h (2d log(1 + N h d ))∥θ * -θ∥ ΣN h (Elliptical Lemma) Theorem 4 (Main regret bound). We have that under event s,a E s,a ∩ E l 1 ∩ E l 2 ∩ E h 1 ∩ E h 2 and N h > 0: V π * ,π * -V π,π N l ≤ Õ N -1/2 l + N -1/2 h ∥θ * -θ∥ ΣN h Proof. V π * ,π * -V π,π N l= ⟨ϕ π * ,P (π * ) -ϕ π N l ,P (π), θ * ⟩ = ⟨ϕ π * ,P (π * ) -ϕ π N l ,P (π * ), θ * ⟩ + ⟨ϕ π N l ,P (π * ) -ϕ π N l ,P (π), θ * ⟩ (first term = sub-MDP sub-optimality; second term = high-level policy sub-optimality)≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + ⟨ϕ π N l ,P (π * ) -ϕ π N l ,P (π), θ * ⟩ ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ * ⟩ + |⟨ϕ π N l ,P (π * ) -ϕ π N l ,P ϵ ′ (π * ), θ * ⟩| + |⟨ϕ π N l ,P ϵ ′ (π) -ϕ π N l ,P (π), θ * ⟩| ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + 2C(ϵ ′ , δ) + ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ * -θ⟩ + ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ⟩ (expand out the second term) ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + 2C(ϵ ′ , δ) + ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ * -θ⟩ (definition of π: ⟨ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π), θ⟩ ≤ 0) ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + 2C(ϵ ′ , δ) + 1 √ N h (2d log(1 + N h d ))∥θ * -θ∥ ΣN h (use of Elliptical lemma)Data Tradeoff: Using the above bound, we can derive the following rates:• Under idealized-feedback and requiring both high-and low-level feedback, the overall rate comes out to O(N-1/4 l + N -1/2 h).h = O N 1/2 h N 1/4 l+ 1 . Thus, the dominating factor is the bias of the reward learning.• Under current-feedback and requiring both high-and low-level feedback, the overall rate comes out to O(N-1/2 l + N -1/2 h).This is because ∥θ * -θ∥ ΣN h = O(1).• Under only low-level feedback (due to sufficiency in coverage), the overall rate comes out to O(N -1/2 l).We have that:EQUATION⋄) : since low-level policy feature expectation is a superset of high-level policy expectation, it follows that by choice of low-level policies π i 1 , π i 2 :∥ϕ P ϵ ′ (π i 1 ) -ϕ P ϵ ′ (π i 2 )∥ Σ-1 i ≥ ∥ϕ π N l ,P ϵ ′ (π * ) -ϕ π N l ,P ϵ ′ (π)∥ Σ-1 N lMoreover, since low-level feedback is always unbiased, ∥θ * -θ∥ ΣN l = O(1). Thus, the overall rate comes out to O(N -1/2 l).Remark 4 (High Probability Guarantee). For completeness, we show that the theorem statement holds with probability at least 1 -δ:Pr( s,a E s,a ∩ E l 1 ∩ E l 2 ∩ E h 1 ∩ E h 2 ) ≥ 1 -Pr(¬ s,a E s,a ) -Pr(¬E l 1 ) -Pr(¬E l 2 ) -Pr(¬E h 1 ) -Pr(¬E h 2 ) ≥ 1 -δ/5 -δ/5 -δ/5 -δ/5 -δ/5 = 1 -δ D.2. 
discussion: 
 Our work considers scalable oversight in the context of goal-conditioned HRL, in which we show that one can efficiently use hierarchical structure to learn from bounded human feedback.Limitations & Future Work: In goal-conditioned HRL, our regret guarantees are with respect to the return of the optimal, hierarchical policy, whose performance is dependent on the usefulness of goal function g. Further research is needed to understand on how to learn good goal functions, using limited supervised or unsupervised learning. Additionally, under current-feedback, the labeler providing high-level feedback is somehow made aware of sub-policy performance. An exciting research direction is how one may provide such knowledge through AI-assistance.Scalable Oversight: Scalable oversight is a nascent but important topic in the area of AI alignment [2, 8, 15, 5] , wherein the goal is to boost the labeler's ability to provide feedback to complex models. Proposed approaches include (recursive) self-critique, summarization, debate, plain model Interaction and market-making, all of which aim to have the model (or auxiliary models) generate interpretable and/or lower-dimensional forms of outputs for the human to parse [15, 13, 24, 27, 23, 5, 12] . Our work studies how one may leverage hierarchical structure as one approach to scaling up feedback.Goal-conditioned RL: Further afield, there has been a lot of work demonstrating the promise/success of goal-conditioned RL with examples from the likes of [16, 17, 7, 10] . The sub-MDP reward is often set to incentivize only goal state reachability, as oftentimes the MDP of interest has sparse rewards, making intermediate returns zero. In our setting, rewards need not be sparse, thus bringing into consideration the tradeoff between intermediate return and goal-reachability. This work initiates the study of scalable oversight in goal-oriented HRL, and owing to the success of goal-oriented HRL in practice, it is our hope that it can be stepping stone towards developing practical scalable oversight techniques.The prototypical example in HRL is the maze, as studied in for instance [17, 22] . A maze consists of rooms with doors. The goal is to get to the exit in as few steps as possible. The MDP may be defined as follows:• For the global MDP, S = S h × S l where s h denotes the index of the current room, and s l denotes the position of the agent in the room. Action set A consists of moving (L, R, U, D, Stay). • For the High-level MDP, high-level action A h consists of moving to the (N, S, E, W) door of the room. s is the current location of the agent, and g(s, a h ) maps the goal (door) to its location. • For the Low-level MDP, it has state space S l s,a ⊂ S and the action set A is the same moving (U, D, L, R, Stay).As noted in the previous section, HRL algorithms can achieve superior statistical sample complexity when there is lots of repeated sub-MDP structure (there are many isomoprhic rooms) and each room has small state-space size [25] . r l,h (s ′ , a ′ ) = r(s ′ , a ′ ) + κ1(h = H l ∧ s ′ = g(s, a)).Firstly, since by definition π * s,a ∈ arg max π∈Πs,a r(π)+ C • Pr(s π H l = g(s, a)), we have that π * s,a ∈ arg max π∈Πs,a r(π) + κ • Pr(s π H l = g(s, a)). Indeed, r(π * s,a ) + κ Pr(s π * s,a H l = g(s, a)) = [r(π * s,a ) + C • Pr(s π * s,a H l = g(s, a))] + (κ -C) Pr(s π * s,a H l = g(s, a)) ≥ [r(π) + C • Pr(s π H l = g(s, a))] + (κ -C) Pr(s π H l = g(s, a)) (Pr(s π * s,a H l = g(s, a)) = 1 ≥ Pr(s π H l = g(s, a)) ∀π)Secondly, using the definition of r l , we have that:r l (π * s,a ) -r l (π i s,a ) = r(π * s,a ) + κP (s π * s,a H l = g(s, a)) -r(π i s,a ) -κP (s π i s,a H l = g(s, a))By the reachability assumption, P (sπ * s,a H l = g(s, a)) = 1, this implies that r l (π * s,a ) -r l (π i s,a ) = r(π * s,a ) -r(π i s,a ) + κP (s π i s,a H l ̸ = g(s, a))Therefore, summing this across n visits to M (s, a), we have:R n (s, a) = n i=1 r l (π * s,a ) -r l (π i s,a ) = n i=1 r(π * s,a ) -r(π i s,a ) + κ n i=1 P (s π i s,a H l ̸ = g(s, a))This statement is useful because we can compute an UCB on n i=1 r(π * s,a ) and, implicitly, a LCB on n i=1 r(π i s,a ) (provided we do not bound R n (s, a)).Lemma 5 (Bonus with "penalty" for non-reachability). Let U B(R n (s, a)) be any upper bound on the sub-MDP regret, then if we define:b s,a r (n) = U B(R n (s, a)) + (κ + H l )2 log( |C(S,A h )|H h K δ ) √ n n - κ n n i=1 1(s π i s,a H l ̸ = g(s, a))Then, rn (s, a) + b s,a r (n) is an UCB for r(π * s,a ) with probability ≥ 1 -δ 3|C(S,A h )|H h K . Let the event that the above holds be E n s,a .Proof.n i=1 r(π * s,a ) = R n (s, a) -κ n i=1 P (s π i s,a H l ̸ = g(s, a)) + n i=1 r(π i s,a ) ≤ R n (s, a) -κ( n i=1 1(s π i s,a H l ̸ = g(s, a)) -ψ n ) + n i=1 r(π i s,a ) (⋄) = R n (s, a) -κ n i=1 1(s π i s,a H l ̸ = g(s, a)) + κψ n + n i=1 r(π i s,a ) + ( n i=1 r(π i s,a ) - n i=1 r(π i s,a )) ≤ U B(R n (s, a)) + (κ + H l )ψ n -κ n i=1 1(s π i s,a H l ̸ = g(s, a)) + n i=1 r(π i s,a ) (κ ′ = κ + H l ) (⋄) :Here we use two applications of Azuma-Hoeffding:• With probability higher than 1 -δ:| n i=1 P (s π i s,a H l ̸ = g(s, a)) - n i=1 1(s π i s,a H l ̸ = g(s, a))| ≤ ψ n = 2 √ nWe have that E[P (sπ i s,a H l ̸ = g(s, a)) -1(s π i s,a H l ̸ = g(s, a))|F i-1 ] = 0.This is true because P (sπ i s,aH l ̸ = g(s, a)) and 1(sπ i s,aH l ̸ = g(s, a) are a function of only the transition probability of the MDP at the ith step conditioned on F i-1 . Thus, P (sπ i s,a H l ̸ = g(s, a)) -1(s π i s,a H l ̸ = g(s, a)) is a martingale difference. And we can use Azuma-Hoeffding.• With probability higher than 1 -δ:| n i=1 r(π i s,a ) - n i=1 r(π i s,a )| ≤ H l ψ n ≤ H l 2 √ nThis again follows from Azuma-Hoeffding on martingale difference r(π i s,a ) -r(π i s,a ), asE[r(π i s,a ) -r(π i s,a )|F i-1 ] = 0. And |r(π i s,a ) -r(π i s,a )| ≤ H l . Thus, r(π * s,a ) ≤ 1 n n i=1 r(π i s,a ) + b s,a r (n) ⇒ r(π * s,a ) -rn (s, a) ≤ b s,a r (n) Remark 1. One choice for U B(R n (s, a)) = H 3/2 l|S l s,a ||A|n if we let A s,a be the standard UCB-VI algorithm [3] .Lemma 6 (Optimism). Let V k h be the V value as in Algorithm 1 at episode k. Let π * be the optimal hierarchical policy. For a fixed k and h, if ∀s, a, n, E n s,a holds, then:V k h (s) ≥ V π * h (s) ∀sProof. Fix some episode k. We will prove this lemma via induction on h = H h + 1, ..., 1.EQUATIONs) for all s. Induction Step: Suppose this is true for up until h = H h + 1, ..., h ′ + 1. Now at time step h ′ and any s, a.Firstly, if Q k h ′ (s, a) = H h H l (e.g. if s, a ̸ ∈ D k ), then Q k h ′ (s, a) ≥ Q * h ′ (s, a). Otherwise, Q k h ′ (s, a) < H h H l and we have that:Q k h ′ (s, a) -Q * h ′ (s, a) = [r N k,h (s,a) (s, a) + b s,a r (N k,h (s, a)) + V k h ′ +1 (g(s, a))] -(r(π * s,a ) + P h ′ V π * h ′ +1 (s, a)) (Q k h ′ definition as in Equation 1) ≥ V k h ′ +1 (g(s, a)) -P h ′ V π * h ′ +1 (s, a) (r N k,h (s,a) (s, a) + b s,a r (N k,h (s, a)) is an UCB of r(π * s,a )) = V k h ′ +1 (g(s, a)) -V π * h ′ +1 (g(s, a)) (π * s,a reaches goal state w.p 1, so P h ′ (g(s, a)|s, a) = 1) ≥ 0 (induction hypothesis) Thus, V k h ′ (s) = max a Q k h ′ (s, a) ≥ max a Q * h ′ (s, a) = V π * h ′ (s). Corollary 2. K k=1 V π * 1 (s 1 ) -V π k 1 (s 1 ) ≤ K k=1 V k 1 (s 1 ) -V π k 1 (s 1 )C.3 Supporting results needed for regret analysis Proposition 3.EQUATIONProof. For any k and h, we consider boundingV k h (s k h ) -V π k h (s k h ), which is equal to: V k h (s k h ) -V π k h (s k h ) = (Q k h -Q π k h )(s k h , a k h ) ≤ (r N k,h (s k h ,a k h ) (s k h , a k h ) + b s k h ,a k h r (N k,h (s k h , a k h ))) -r(π N k,h (s k h ,a k h ) s k h ,a k h ) + V k h+1 (g(s k h , a k h )) -P π k,h V π k h+1 (s k h , a k h ) (due to the min) = ρ k h + [V k h+1 (g(s k h , a k h )) -P π k,h V π k h+1 (s k h , a k h )]where we setρ k h = rN k,h (s k h ,a k h ) (s k h , a k h ) + b s k h ,a k h r (N k,h (s k h , a k h ))) -r(π N k,h (s k h ,a k h ) s k h ,a k h ).Continuing with the original proof and focusing on the second term:V k h+1 (g(s k h , a k h )) -P π k,h V π k h+1 (s k h , a k h ) = V k h+1 (g(s k h , a k h )) -P π k,h V k h+1 (s k h , a k h ) + P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) = (P h -P π k,h )V k h+1 (s k h , a k h ) + P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) (P h is the transition under optimal sub MDP policy so it takes s k h , a k h to g(s k h , a k h ) deterministically) = (P h -P π k,h )V π * h+1 (s k h , a k h ) + (P h -P π k,h )(V k h+1 -V π * h+1 )(s k h , a k h ) + P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) = γ k h + σ k h + P π k,h (V k h+1 -V π k h+1 )(s k h , a k h )where• γ k h = (P h -P π k,h )V π * h+1 (s k h , a k h ) • σ k h = (P h -P π k,h )(V k h+1 -V π * h+1 )(s k h , a k h )In summary,V k h (s k h ) -V π k h (s k h ) ≤ ρ k h + γ k h + σ k h + P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) = (V k h+1 -V π k h+1 )(s k h+1 ) + ζ k h + γ k h + σ k h + ρ k h ,where we introduce the notationζ k h = P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) -(V k h+1 -V π k h+1 )(s k h+1). Unrolling the recursion starting at h = 1:V k 1 (s k h ) -V π k 1 (s k h ) ≤ 1(ζ k h + γ k h + σ k h + ρ k h ) + ... + (1) H h (ζ k H h + γ k H h + σ k H h + ρ k H h ) = 1 • ( H h h=1 ζ k h + γ k h + σ k h + ρ k h )Summing across k ∈ [K], it suffices to bound:EQUATION)Remark 2. There are two sources of sub-optimality in the bound.One is the sub-optimality while executing the sub-MDP policies. This is covered by the per-step high level reward bonus (which is also the UCB on the return of the sub-MDP's return) in ρ k h . The other is the sub-optimality of not landing on g(s k h , a k h ), there is covered by γ k h , σ k h , which affects future reward. The martingale difference ζ k h is zero in expectation, so it is not some measure of suboptimality.We first bound the ζ's, whose sum is dominated byK k=1 H h h=1 ρ k h + γ k h + σ k h . Lemma 7. With probability ≥ 1 -δ/3: K k=1 H h h=1 ζ k h ≤ Õ(H h H l √ H h K)Let the event that the above inequality hold be E ζ .Proof. The concentration of ζ k h follows from Azuma Hoeffding, as the following is a martingale difference.ζ k h = P π k,h (V k h+1 -V π k h+1 )(s k h , a k h ) -(V k h+1 -V π k h+1 )(s k h+1 ) with E[ζ k h |F k,h ] = 0, since the expectation is only wrt randomness in s k h+1 . Moreover, this martingale difference is bounded by 4H h H l Next, we simplify the sum of remaining terms.Lemma 8. We have that:K k=1 H h h=1 γ k h ≤ H h H l K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h ))andK k=1 H h h=1 σ k h ≤ H h H l K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h )) Proof. K k=1 H h h=1 γ k h = K k=1 H h h=1 (P h -P π k,h )V π * h+1 (s k h , a k h ) = K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h ))(V π * h+1 (g(s k h , a k h )) -V π * h+1 (s k h+1 )) ≤ H h H l K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h )) Similarly, K k=1 H h h=1 σ k h = K k=1 H h h=1 (P h -P π k,h )(V k h+1 -V π * h+1 )(s k h , a k h ) = K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h ))[(V k h+1 -V π * h+1 )(g(s k h , a k h )) -(V k h+1 -V π * h+1 )(s k h+1 )] ≤ H h H l K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h )) Lemma 9. With probability ≥ 1 -δ/3: K k=1 H h h=1 ρ k h ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 r(π * s,a )-r(π i s,a )+ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + (κ ′′ + κ)ψ i iLet E ρ be the event that this holds.Proof. We first expand the ρ k h sum:K k=1 H h h=1 ρ k h = K k=1 H h h=1 rN k,h (s k h ,a k h ) (s k h , a k h ) + b s k h ,a k h r (N k,h (s k h , a k h ))) -r(π N k,h (s k h ,a k h ) s k h ,a k h ) = s,a∈C(S,A h ) N K,H h (s,a) i=1 ri (s, a) + b s,a r (i) -r(π i s,a ) = s,a∈C(S,A h ) N K,H h (s,a) i=1 1 i i j=1 r(π j s,a ) + U B(R i (s, a)) + κ ′ ψ i -κ i j=1 1(s π j s,a H l ̸ = g(s, a)) i -r(π i s,a ) (using definition of bonus) ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 1 i i j=1 r(π j s,a ) + H l ψ i i + U B(R i (s, a)) + κ ′ ψ i -κ i j=1 1(s π j s,a H l ̸ = g(s, a)) i -r(π i s,a )(Azume-Hoeffding for concentration of r around r)Using the two-sided concentration bound we had before (the other way):i j=1 1(s π j s,a H l ̸ = g(s, a)) + ψ i ≥ i j=1 P (s π j s,a H l ̸ = g(s, a)) w.h.p: i j=1 r(π * s,a ) -r(π j s,a ) ≥ R i (s, a) -κ( i j=1 1(s π j s,a H l ̸ = g(s, a)) + ψ i ) ⇒ i j=1 r(π * s,a ) -R i (s, a) + κψ i ≥ i j=1 r(π j s,a ) -κ i j=1 1(s π j s,a H l ̸ = g(s, a))We continue our derivation:s,a∈C(S,A h ) N K,H h (s,a) i=1 1 i ( i j=1 r(π j s,a ) + U B(R i (s, a)) + κ ′′ ψ i -κ i j=1 1(s πj H l ̸ = g(s, a))) -r(π i s,a ) (κ ′′ = κ ′ + H l ) ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 1 i [ i j=1 r(π * s,a ) -R i (s, a) + κψ i ] -r(π i s,a ) + s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) + κ ′′ ψ i i (using the identity above) ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 r(π * s,a ) -r(π i s,a ) + s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + (κ ′′ + κ)ψ i i C.3.1 Overall Regret Bound Theorem 3. Under events s,a,n E n s,a ∩ E ζ ∩ E ρ , we have that: K k=1 H h h=1 ρ k h +γ k h +σ k h ≤ s,a∈C(S,A h ) (log(N K,H h (s, a))+1)U B(R N K,H h (s,a) )+O(H h H l N K,H h (s, a)) Proof. K k=1 H h h=1 ρ k h + γ k h + σ k h ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 r(π * s,a ) -r(π i s,a )+ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + κψ i i + 2H h H l K k=1 H h h=1 P π k,h (s k h+1 ̸ = g(s k h , a k h )) = s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + κψ i i + s,a∈C(S,A h ) N K,H h (s,a) i=1 r(π * s,a ) -r(π i s,a ) + 2H h H l s,a∈C(S,A h ) [ N K,H h (s,a) i=1 P (s π i s,a H l ̸ = g(s k h , a k h ))](group third sum by s, a)≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + κψ i i + s,a∈C(S,A h ) N K,H h (s,a) i=1 r(π * s,a ) -r(π i s,a ) + κ N K,H h (s,a) i=1 P (s π i s,a H l ̸ = g(s k h , a k h )) (κ ≥ 2H h H l ) = s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) -R i (s, a) + κψ i i + s,a∈C(S,A h ) R N K,H h (s,a)(using the definition for sub-MDP regret)≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) i + R N K,H h (s,a) + s,a∈C(S,A h ) N K,H h (s,a) i=1 κψ i i ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R i (s, a)) i + U B(R N K,H h (s,a) ) + s,a∈C(S,A h ) O(κ N K,H h (s, a)) (since Azuma-Hoeffding is s.t ψ i = O( √ i)) ≤ s,a∈C(S,A h ) N K,H h (s,a) i=1 U B(R N K,H h (s,a) ) i + U B(R N K,H h (s,a) ) + s,a∈C(S,A h ) O(H h H l N K,H h (s, a)) (using monotonicity of upper bound U B(R i (s, a)) in i, assumption that C = O(H h H l )) = s,a∈C(S,A h ) (log(N K,H h (s, a)) + 1)U B(R N K,H h (s,a) ) + O(H h H l N K,H h (s, a))Corollary 3 (Regret under |C(S, A h )| clusters of isomorphic sub-MDPs [25] ). Let us set UCB-VI to be the sub-MDP learning algorithm, then we have the following regret bound:s,a∈C(S,A h ) (log(N K,H h (s, a)) + 1)R N K,H h (s,a) + O(H h H l N K,H h (s, a)) ≤ (log H h K + 1) s,a∈C(S,A h ) R N K,H h (s,a) + O(H h H l |C(S, A h )| • H h K) ( s,a∈C(S,A h ) N K,H h (s, a) = H h K) ≤ (log H h K + 1) s,a∈C(S,A h ) H 3/2 l |S l s,a ||A|N K,H h (s, a) + O(H h H l |C(S, A h )| • H h K) (plug in UCB-VI guarantees) ≤ Õ(H 3/2 l max s,a |S l s,a ||A| |C(S, A h )|(H h K) + H h H l |C(S, A h )|H h K) ( s,a∈C(S,A h ) N K,H h (s, a) = H h K) using UCB-VI's guarantee that upper bound U B(R N K,H h (s,a) ) = H 3/2 l|S l s,a ||A|N K,H h (s, a). Remark 3 (High Probability Bound). For completeness, we show that the regret bound holds with probability greater than 1 -δ. The regret bound holds under s,a,n E n s,a ∩ E ζ ∩ E ρ , by union bound:Pr( s,a,n E n s,a ∩ E ζ ∩ E ρ ) ≥ 1 - s,a,n Pr(¬E n s,a ) -Pr(¬E ζ ) -Pr(¬E ρ )) ≥ 1 -(|C(S, A h )|H h K) δ 3|C(S, A h )|H h K -δ/3 -δ/3 = 1 -δTo prove the results below, our approach is to construct two MDP instances with identifical low level feedback such that any deterministic learning algorithm picks the arbitrarily worse high level policy.Proposition 4 (Non-identifiability of ranking among sub-MDP returns). For any deterministic highlevel policy learning algorithm with N l samples of low-level feedback, there exists a MDP instance that induces regret constant in N l .Proof. Consider two-horizon MDP with starting state s 1 with H h = 1, H l = 2. There are two possible high-level actions a 1 and a 2 at s 1 .For any policy π 1 in sub-MDP M (s 1 , a 1 ), let it have feature expectation ϕ(π 1 ) = [ϕ ′ (π 1 ), 1, 0], and for anyπ 2 in sub-MDP M (s 1 , a 2 ), ϕ(π 2 ) = [ϕ ′ (π 2 ), 0, 1].Now, we consider two MDP instances with θ * = [0, 0, C ′ ] and θ * = [0, C ′ , 0] for some positive constant C ′ .Under both instances, we observe identical low-level feedback for trajectories τ, τ ′ in sub-MDPs M (s 1 , a j ), j ∈ [2]: the feedback is Bernoulli with parameter σ(⟨ϕ′ (τ ) -ϕ ′ (τ ), θ ′ ⟩).Consider any deterministic learning algorithm. WLOG it outputs high level policy π h (s 1 ) = a 1 with some set of N l samples of low-level feedback.Then, it follows that its regret under θ * = [ϵ1, 0, C ′ ] is C ′ , since the reward (and return since H h = 1) of π * s1,a1 is 0, while the reward of the optimal policy which visits M (s 1 , a 2 ) is C ′ .We first define the MLE expression; note that the MLE is in terms of trajectories only. Define:EQUATION• High-level trajectories: has realized features,x i = ϕ π N l ,P (τ i 1 ) -ϕ π N l ,P (τ i 2 ) = H h j=1 ϕ P (π N l (s τ i 1 j , a τ i 1 j )) - H h j=1 ϕ P (π N l (s τ i 2 j , a τ i 2 j ))where ϕ π N l ,P (τ i j ) is the feature of the high-level trajectory under sub-policy π N l and transition P (since trajectories are collected from roll-outs in the actual MDP as in [29] ). On the other hand, under idealized-feedback, the labeler assumes that each goal-conditioned sub-MDP has been executed perfectly (i.e. by π * s,a ) and so the features correspond to:x * i = ϕ π * ,P (τ i 1 ) -ϕ π * ,P (τ i 2 ) = H h j=1 ϕ P (π * (s τ i 1 j , a τ i 1 j )) - H h j=1 ϕ P (π * (s τ i 2 j , a τ i 2 j ))• Comparison y of high level trajectories follows Bernoulli distributiony i = σ(θ * • x * i ).• Low-level trajectories: has realized features,x s,a i = ϕ(τ i 1 ) -ϕ(τ i 2 ) = H h j=1 ϕ(s τ i 1 j , a τ i 1 j ) - H h j=1 ϕ(s τ i 2 j , a τ i 2 j )Note that unlike the high level features, low-level features data are always unbiased. Thus, using high level and low-level comparisons has the same bias from the high level. • Comparison y of low level trajectories follows Bernoulli distribution y i = σ(θ * • x s,a i ).Lemma 10 (Lemma 5 of [29] ). Let oracle P ϵ ′ be such that with probability 1 -δ/5, the following holds. Let d π h (s, a) and dπ h (s, a) be the visitation measure of policy π under P and P ϵ ′ , we have for all h ∈ [H] and π ∈ Π:s,a |d π h (s, a) -dπ h (s, a)| = s |d π h (s) -dπ h (s)| ≤ hϵ ′This applies across all sub-MDPs M (s, a). Let the event that this expression hold be E s,a . Lemma 11 (Low-level MLE Bound, Lemma 2 of [29] ). With probability at least 1 -δ/5:∥θ * -θ t ∥ Σl n ≤ Õ(1)Let the event that this holds for learning from sub-MDP trajectories be E l 1 . Lemma 12 (Lemma 3 of [29] ). If low-leve trajectories τ 1,2 i ∼ π i , P ϵ ′ , then with probability at least 1 -δ/5:∥θ * -θ t ∥ Σl n ≤ √ 2∥θ * -θ t ∥ Σl n + O(B d log 4n/δW )Let the event that this holds for learning from sub-MDP trajectories be E l 2 .D.2.3 Bias when using idealized-feedback, high level trajectory data in MLE Proposition 5 (sub-MDP REGIME guarantee of [29] ). For sub-MDP M (s, a), under E s,a ∩ E l 1 ∩ E l 2 :⟨ϕ P (π * ), θ * ⟩ -⟨ϕ P (π N l ), θ * ⟩ ≤ C 1 (δ) √ N l + O(ϵ ′ )where C 1 (δ) = O( log(1/δ)).Note that for estimation and bias, we have to have both an upper bound and a lower bound (see PbRL example). This requires two-sided bound, where lower bound comes from ϕ * having higher reward than ϕ and upper bound comes from no-regret. Due to optimality of π * , we have the lower bound as well:0 ≤ ⟨ϕ P (π * ), θ * ⟩ -⟨ϕ P (π N l ), θ * ⟩ ≤ C 1 √ N l + O(ϵ ′ )Additionally, we have that: Lemma 13 (Lemma 6 of [29] ). For any s h , a h ,∥v i ∥ ≤ 2B, θ ∈ R d and ∥ϕ∥ ≤ R under E s,a ∩ E l 1 ∩ E l 2 : |⟨ϕ P ϵ ′ (π N l (s h , a h )) -ϕ P (π N l (s h , a h )), v⟩| ≤ BRd 2 ϵ ′ With this, |⟨ϕ P (π * ), θ * ⟩ -ϕ P ϵ ′ (π N l ), θ * | ≤ ( C 1 √ N l + O(ϵ ′ )) + BRd 2 ϵ ′ = C 1 √ N l + C 2 ϵ ′Now, we can analyze the bias of including high level trajectory data in the MLE computation: Lemma 14. Suppose there are N h , N l high, low-level trajectories, bias b is such that, unders,a E s,a ∩ E l 1 ∩ E l 2 : ∥b∥ 2 = T t=1 |⟨θ * , x i ⟩ -⟨θ * , x * i ⟩| 2 ≤ 2H h T (2H h ( C 1 √ N l + C 2 ϵ ′ ) 2 ) Proof. T t=1 |⟨θ * , x * i ⟩ -⟨θ * , x i ⟩| 2 ≤ 2 T t=1 |⟨ s,a∈τ t 1 ϕ P (π * (s, a)) - s,a∈τ t 1 ϕ P ϵ ′ (π N l (s, a)), θ * ⟩| 2 + |⟨ s,a∈τ t 2 ϕ P (π * (s, a)) - s,a∈τ t 2 ϕ P ϵ ′ (π N l (s, a)), θ * ⟩| 2 ≤ 2H h T t=1 s,a∈τ t 1 |⟨ϕ P (π * (s, a)) -ϕ P ϵ ′ (π N l (s, a)), θ * ⟩| 2 + s,a∈τ t 2 |⟨ϕ P (π * (s, a)) -ϕ P ϵ ′ (π N l (s, a)), θ * ⟩| 2 ≤ 2H h T (2H h ( C 1 √ N l + C 2 ϵ ′ ) 2 )Thus,∥b∥ = T t=1 |⟨θ * , x i ⟩ -⟨θ * , x * i ⟩| 2 ≤ 2H h ( C 1 √ N l + C 2 ϵ ′ ) √ T D.2. 
additional guarantees: 
 In addition, we derive requisite conditions on the constants for idealized-feedback (the most interesting case).Necessary Auxiliary Parameters Bound: We have that,H h ( C 1 √ N l + C 2 ϵ ′ ) + 2C(ϵ ′ , δ) + 1 √ N h (2d log(1 + N h d ))∥θ * -θ∥ ΣN h ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + 2C(ϵ ′ , δ) + N -1/2 h 2d 2∥θ * -θ N h ∥ ΣN h + O(B d log N h /δW ) + 8N h C(ϵ ′ , δ) ≤ H h ( C 1 √ N l + C 2 ϵ ′ ) + (8d + 2)C(ϵ ′ , δ) + N -1/2 h 2d N 1/2 h N 1/4 l + (N h ϵ ′ ) 1/2 + C ′ + O(B d log N h /δW ) ≤ (H h C 1 )N -1/2 l + 2dN -1/4 l + C 2 H h ϵ ′ + dϵ ′1/2 + 9dC(ϵ ′ , δ) + 2dC ′′ N -1/2 h = (H h C 1 )N -1/2 l + 2dN -1/4 l + C 2 H h ϵ ′ + dϵ ′1/2 + 9d 2H h BRd 2 ϵ ′ + 8H 3 h H l δ + 2dC ′′ N -1/2 h ≤ (2d + H h C 1 )N -1/4 l + (C 2 H h + 18d 3 H h BR)ϵ ′ + 72dH 3 h H l δ + 2dC ′′ N -1/2 hSetting the upper bound to be below ϵ, or each term to be below ϵ/4, we obtain the following bounds:EQUATION).•N h ≥ O( d 2 ϵ 2 ). • κ ≥ O( dH 2 h H l ϵ ): 72dH 3 h H l δ ≤ ϵ/4 ⇒ δ ≤ O( ϵ dH 3 h H l ). Recall δ = 1 κH h + C1 κH h H l √ N l + C2ϵ ′ κH h H l + H l ϵ ′ . This implies that κ ≥ O( dH 2 h H l ϵ ) and ϵ ≤ O( ϵ dH 3 h H 2 l ). • ϵ ′ ≤ O(min( ϵ dH 3 h H 2 l , ϵ d 3 H h BR ): Finally, we also require that (C 2 H h + 18d 3 H h BR)ϵ ′ ≤ ϵ/4 ⇒ ϵ ′ ≤ O( ϵ d 3 H h BR ). Thus, we need that ϵ ′ ≤ O(min( ϵ dH 3 h H 2 l , ϵ d 3 H h BR ).An useful sanity check for hierarchical RL algorithms is that it achieves improved statisical sample complexity in settings with repeated sub-MDP structure [25] . As in [25] , we examine if Algorithm 1 also improves upon algorithms that do not leverage hierarchical structure. We make this comparison with vanilla UCB-VI under the same isomophism assumption.Corollary 5. Setting A s,a to be the standard UCB-VI algorithm with U B(REQUATION)), we have the following bound: • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.s,a∈C(S,A) U B(R N K,H h (s,a) ) + H h H l N K,H h (s, a) ≤ Õ(H 3/2 l max s,a |S l s,a ||A| |C(S, A h )|(H h K) + H h H l |C(S, A h )|H h K) 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This is a theory paper that has no experiments section.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in the paper does conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: To our knowledge, this theory paper has no positive/negative social impact.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  


Decision: After lengthy discussion, the reviewers are all recommending acceptance of this work. Several reviewers raised valuable questions and concerns regarding the assumptions made, and the clarity of notation and writing---I am recommending the paper for acceptance, but I encourage the authors to take the reviewers' suggestions into account.

Reviews: review: paper_summary: paper_summary: In this paper, the authors study how to scale human feedback, in the context of goal-conditioned hierarchical reinforcement learning. For this work, the authors assume that humans can only provide feedback for outputs with length below a certain threshold. Thus, it is necessary to scale the little feedback provided, in order to improve the complete output. This means, for example, that a human can provide feedback about the high-level actions taken in the hierarchy, but not the detailed steps of the low-level policies. The authors propose two algorithms: one that learns from low-level feedback only, and one that learns by incorporating human preference over high-level trajectories. The authors also present regret bounds for the proposed algorithms.
strength_weakness: strength_weakness: The results are based on a very strong assumption that there is a well-defined goal function available (that is, a goal function that only proposes feasible goals). It is very hard to guarantee goal feasibility, so assuming that this function is given is very ambitious. However, the authors do recognize the limitation of this assumption and propose, on a high-level, how this could be dealt with in future work. 

When discussing the bounds related to the second algorithm (Section 4), it was necessary to introduce several constants, but they were not discussed in more detail, providing, for example, intuitions on the magnitude of such constants. Without it, it is more challenging to understand the significance of the bounds.
questions: questions: There were a few variables/subscripts used throughout the paper that, I believe, were not formally introduced. As some examples, $a$ on line 60, $h$ and $i$ on the Interaction Protocol paragraph (no line numbers here), $l$ on line 67, $\bar{r}$ on line 179, $N(s,a)$ on line 194, $d$ on Lemma 4. Could the authors please add clarifications about these variables?
limitations: limitations: The authors discuss the limitations of the work. No major concerns.
paper_summary: paper_summary: This paper analyzes scalable oversight in the context of goal-conditioned hierarchical reinforcement learning. Specifically, it theoretically shows that it is possible to efficiently use hierarchical structure to learn from bounded human feedback.
strength_weakness: strength_weakness: * Minor: It would be a nice addition to the paper to empirically demonstrate Algorithm 1 &2 as well.
* Minor: Clarity: Paper had quite a few typo’s. I would encourage the authors to use an automated tool to check for spelling / grammar mistakes.

Typos:

* L61: “policies aims to” -> “policies aim to”
* L183: “approach is avoid” -> “approach is to avoid”
* L218: “identifical” -> “identical”
* L250: “what can we assume the” -> “what can we assume is the”
questions: questions: * Does the analysis for the linear setting generalize to the non-linear / function approximation setting?
limitations: limitations: Yes they are discussed in Section 5.
paper_summary: paper_summary: Provides proofs of the regret bounds for cardinal and ordinal feedback using the sub-MDP framework of goal-conditioned HRL. Sub-MDPs are defined by a starting state, fixed horizon, high-level action and subspace. The high-level policy selects transitions between sub-MDPs. This work first proposes an upper confidence bound algorithm based on lower-level reachability and selection, then proves the regret of this algorithm.
strength_weakness: strength_weakness: Algorithm 1 is somewhat difficult to follow. In particular, while the components make sense, the core insight of the bounds on the lower-level goals is difficult to locate.

The regret analysis proof sketch could provide more insight. In particular, the separation of which components occur because of the high-level and low-level errors, which introduce the product of horizons, is not intuitively clear. 

The work for ordinal feedback is not particularly well contained, since it relies on the properties of REGIME, which are not made clear in this work. In particular, it is not obvious without looking into that work where the sub-policy simulator fits in. 

In many ways this seems less to be a work about the nature of scalable feedback, and simply on the nature of hierarchical RL in providing regret bounds. This subject is of interest regardless but calls to question the framing of this work.
questions: questions: Can the work on regret analysis of GCHRL be separated from the analysis of ordinal rewards?

What is the relationship between the analysis of these two?
limitations: limitations: The analysis of other components of HRL, such as goal sampling, learning procedure, etc. are not that well captured, though this is typically challenging to analyze theoretically.
paper_summary: paper_summary: The paper studies the scalable oversight problem in the goal-conditioned hierarchical reinforcement learning setup. The starting point of the paper is that, if the time horizon $H$ is large, there is only a limited amount of feedback that can be given (authors use an example of essay or code writing, which requires the labeller to read through and provide feedback on the whole output, which is is very expensive). Thus, it is crucial to leverage hierarchical feedback (e.g. judging one paragraph, or one helper function, or the high-level plan). Given a tabular MDP, the task of finding a good policy is decomposed into two levels: 
 - a high-level policy $\pi^h$ that computes, in a state $s$, a high-level action $a^h$ which in turn gives a goal $g(s,a^h) \in S$ and a sub-MDP $M(s, a^h)$ that operates on a subset of states $S_{s, a^h} \subseteq S$, but has access to all actions $A$
 - a set of low-level policies $\pi_{s,a^h}$, for each state $s$ and high-level action $a^h$, which attempt to reach a goal $g(s,a^h)$ (almost surely) while collecting as much reward on the way as possible.

In the first part of the paper, the feedback is assumed to be cardinal. The goal function is assumed to be given and fixed. The task studied is then to find a high-level policy and a set of low-level policies, which give close-to-optimal return. This is done by employing a two-level UCB-VI procedure, where high-level actions correspond to learning UCB over sub-MDPs. The reward feedback is then only given for the low-level trajectories of length $H_l$ (since the high-level reward is computed by adding low-level ones).

In the second part of the paper, the feedback is assumed to be ordinal, and to follow BTL model. Authors point out that there is a subtle issue with the low-level feedback not always being sufficient for no-regret learning, and high-level feedback depending on what the labeller believes the low-level polices will be (e.g. whether they judge wrt to optimal or actual low-level policies). They develop a hierarchical preference-learning algorithm H-REGIME and analyse its regret in all three cases discussed above.
strength_weakness: strength_weakness: My main question/objection is about the H-UCB-VI algorithm. For shared learning, the algorithm involves assigning the chosen sub-MDP to an appropriate cluster $C(s,a)$. This means that the transition probabilities and rewards must be known for the whole MDP (well, for all sub-MDPs). But if this is the case, then there's no need for using UCB - we can use VI directly. Moreover, the paper improves over UCB-VI only in case there are many (small) isomorphic sub-MDPs, which makes the dependence on shared learning crucial for this to be useful. (Moreover, the motivating example used throughout the paper is given to be essay writing, which does not seem to enjoy this property. Other than that, authors do not give any other examples, nor do any concrete example calculations - even in the appendix - which makes it more difficult to understand and appreciate the work.) This is where I might be fundamentally misunderstanding the work - please correct me if I'm wrong, this is the main reason for my low rating.

In general, it was very unclear to me what exactly is the influence of the goal function on the whole setup - see questions below. The discussion was limited to a few lines in "Goal Selection" paragraph, but I did not gain a good intuition the interplay between the high-level policy performance, and the goal function. (For example, how much work is good goal function doing when comparing to the baseline UCB-VI.)
questions: questions: Questions:
 - The definition of the MDP in the introduction does not contain a reference to high-level actions. How do they fit into the definition, formally?
 - Why are states for sub-MDPs indexed by high-level action as well? Why are all actions $A$ available in sub-MDPs? What if an action leads outside of $S_{s,a}$?
 - In what way do results depend on the goal function? Can it be quantified? Is it possible to derive $W(g)$ of the value of the optimal policy wrt to this goal function, and say something about the sensitivity of of this $W$ on the parameter? How would goal functions be derived in a realistic setup? (Those questions are probably somewhat, or even significantly, out of scope of the paper, but I'd appreciate if the authors provided at least some preliminary answers, since the practicality and a lot of the value of this development hinges on this problem). 
 - What are the policy classes $\Pi^h$ and $\Pi_{s,a}$? They appear to be assumed in the definitions, but are not introduced otherwise.
 - I do not know the REGIME algorithm, but I could not find it in the provided reference?
 - Does the approach discussed in the paper extend to more than two levels of hierarchy?
 - What is $S_h$ in line 217/218?
 - Algorithm 2, line 12 - shouldn't it say length H^h trajectories?
limitations: limitations: Yes.

Comments: title: Reply to Reviewer 2zMJ
Reply to Reviewer z273
Response
Reply to Reviewer Hzkp
Reply to Reviewer z273
Response
Reply to Reviewer z273
Response
Reply to Reviewer poPw
Response to authors
comment: Thank you for getting back to us and taking the time to read through everything (which is quite a bit), we appreciate it!
Thank you for the added details! After reading your response and the other reviews/discussions, I still believe the paper should be accepted.
Thank you for your timely response and update! To wrap up our discussion, we have two more quick points to share if we may.

```
So I remain convinced about the centrality of the known-clustering assumption, via the chain "Unknown clustering" -> "Algorithm 1 uses trivial clustering" -> "Theorem 1 proves trivial bound about its regret" -> "Corollary 1 doesn't improve on the baseline".
```

This is exactly right. To confirm, without this assumption, we cannot derive Corollary 1. The clustering assumption is central to the favorable comparison result (and that of [25]).

```
if the learner doesn't know that sub-MDP A is isomorphic to a sub-MDP B, but they indeed are, presented results are not impactful in any way.

At the same time, I agree that, introducing the assumption about the feedback being limited to $H_l, H_h$ is an important (but, I think, a bit separate, point), which makes the contribution valuable on its own
```

Just to offer our understanding,

1. Under the “trivial clustering”, Theorem 1 leads to some no-regret guarantee. In a vacuum, we completely agree with you that this guarantee is not impactful. It doesn’t improve upon the baseline (non-hierarchical algorithm), which one can readily use.
2. However our previous point was that under the premise of the paper (limited feedback), the regret guarantee, even under the “trivial clustering”, does become *more* meaningful. This is because the baseline is no longer applicable. And so, we think having an algorithm that can achieve *some* no-regret guarantee is a step forward, in the context of scalable oversight.

Lastly, we definitely agree that the algorithm can be improved, since it doesn’t do online clustering. It can only leverage certain types of multi-task structure, but not all. We will highlight this as a key direction for future work.

Please let us know if there are more questions, and thank you again for your thorough engagement during the process! It has definitely helped to improve our paper.
I again applaud the authors for engaging with me on this.

I think the last exchange validates the key points of my understanding of the theorem. So I remain convinced about the centrality of the known-clustering assumption, via the chain "Unknown clustering" -> "Algorithm 1 uses trivial clustering" -> "Theorem 1 proves trivial bound about its regret" -> "Corollary 1 doesn't improve on the baseline".  Or, more straightforwardly, if the learner doesn't know that sub-MDP A is isomorphic to a sub-MDP B, but they indeed are, presented results are not impactful in any way.

At the same time, I agree that, introducing the assumption about the feedback being limited to $H_l, H_h$ is an important (but, I think, a bit separate, point), which makes the contribution valuable on its own, so I decided to increase my score to recommend acceptance.
Thank you for getting back to us, we appreciate it!
Thank you for your detailed rebuttal response. I have raised my score.
Thanks for continuing to engage with us! We are happy to go over this, and will be sure to correct the typo as you suggest, thanks.

```
Theorem 1 analyses the behavior of Algorithm 1, and shows that the regret grows not faster than (number of clusters)*(upper bound on regret in a cluster).
```

More precisely, it is the sum of the upper bound on the regret of the clusters, which in settings with shared structure between sub-MDPs can be better than (number of clusters)*(upper bound on regret in a cluster).

```
As the authors claim above, Algorithm 1 can work with a clustering function that is a refinement of the true clustering function (that is, the clusters are more fine-grained).
```

That is right, Algorithm 1 provides a regret guarantee for any cluster function that is correct. 

Our previous point is that even in settings where we take each sub-MDP to be its own cluster (the most refined clustering if you'd like), improvements in the regret bound are still possible e.g. due to low-rank structure.

```
However, as far as I understand, the bound uses the $C$ that is actually used in the algorithm, and not the (unknown) "ground-truth" clustering given by Definition 2.
```

This is correct. When the cluster function is unknown, the algorithm will use the one where each sub-MDP is its own cluster (and not the unknown, best cluster function).

```
In particular, if we assume no prior knowledge of the clustering structure, the bound becomes proportional to $|A_h|\cdot |S|$... my reading was that, in this case, it was trivialising the bound of Theorem 1. (I.e. if the hierarchical structure is a prior unknown, then we can do no better than a normal non-hierarchical approach).
```

That’s right, without prior knowledge, we do not do better than the non-hierarchical algorithm in terms of statistical complexity, as you write. With that said, Corollary 1 emulates the comparison done in [25]. In [25], it is assumed this cluster function is *known* and the HRL algorithm is proven to be better under certain conditions. We do the same here, also assuming the cluster function is known (with no endorsement of how realistic this assumption is). We agree with you it would be interesting future work to design an algorithm that can cluster on the fly.

Finally, and importantly, the comparison above is in terms of statistical efficiency. Under our assumption of bounded feedback, the non-hierarchical approach is actually *not applicable* here, due to its excess trajectory length of $H_h H_l$ (L54). Hence, we believe Algorithm 1 is not trivial, but rather a useful contribution that can achieve no-regret while learning from bounded cardinal feedback.

Again, thank you for your time and please let us know if there are any other questions!
I thank the authors for the clarification.

I'd like to continue this discussion for a bit still. In light of the above, it seems that I have trouble interpreting the content of the Theorem 1. My understanding is that:
 - Theorem 1 analyses the behavior of Algorithm 1, and shows that the regret grows not faster than (number of clusters)*(upper bound on regret in a cluster).
 - As the authors claim above, Algorithm 1 can work with a clustering function that is a refinement of the true clustering function (that is, the clusters are more fine-grained).
 - However, as far as I understand, the bound uses the $C$ that is actually used in the algorithm, and not the (unknown) "ground-truth" clustering given by Definition 2.
 - In particular, if we assume no prior knowledge of the clustering structure, the bound becomes proportional to $|A_h|\cdot |S|$
 - I don't know what is the cardinality of the set $A_h$ is - in particular, I am not sure what is the "MDP's hierarchical structure" the authors refer to in the above answer. But my reading was that, in this case, it was trivialising the bound of Theorem 1. (I.e. if the hierarchical structure is a prior unknown, then we can do no better than a normal non-hierarchical approach).

(Also, on a related note, it is probably advisable to write explicitly the chain of regret inequalities

$\sum_{k=1}^{K} V^{\pi^*}_1(s_1) - V^{\pi_k}_1(s_1) \leq \sum V^{k}_1(s_1) - V^{\pi_k}_1(s_1) \leq \ldots$

which follows, as far as I understand, from the optimism lemma in the Appendix B.2. Otherwise, it is not clear what the exact connection to regret even is, since $V^{k}_1$ is not analysed before this point. And there appears to be some typography problem in the statement of the optimism lemma.)
Thank you for getting back to us!

```
I am still unconvinced by the assumption that clustering function is available. I admit it isn't literally implying that transition probabilities and rewards are known, but at the same time, I have hard time imagining any semi-realistic situation in which one does not imply the other. 
```

Firstly, we wish to emphasize that this assumption of the known clustering function is *only* used in this paper to derive Corollary 1, to do the "sanity check" comparison. This assumption is *not* central to the paper's main results. Outside of Corollary 1, removing this assumption does not affect any other result. This is because overall, our work is about scaling up bounded feedback via HRL, and not comparing the statistical efficiency of HRL vs RL (as in [25]). We will be sure to clarify this in our revision and we apologize for the confusion.

Secondly, as we write in our previous response, we agree with you that the cluster assumption from [25] is quite specific/strong. When we remove the assumption and the cluster function is unknown, we can simply have each sub-MDP be its own cluster. In such settings, our main result in section 3 (Theorem 1) is still useful as it can capture improvements in regret from other general forms of shared learning, since we have shown learning reduces to multi-task, sub-MDP regret minimization.

One example of this is [11] applicable to the linear sub-MDP setting (L221-222), which makes use of the low-rank and not the cluster assumption. This is perhaps another point of difference between our paper and [25] in that we formalize the reduction to multi-task learning, which demonstrates improvements in the regret bound from other forms of shared learning.


```
In full RL, the agent doesn't know which situation (which sub-MDP) it found itself in
```

As a point of clarification, in our setting, the agent *does* know which sub-MDP it is in. sub-MDPs are defined by the state and high-level action, both of which are known to the agent. Presumably, you meant to write "sub-MDP cluster" here?

```
...except I still don't understand how exactly the authors want the set $A_h$ to be formally defined (e.g. [25] introduces a similar notion formally in Definition 1 using a notion of partition of states MDP states).
```

Thank you for this! The definition you point to in [25] is specific to a particular class of hierarchical MDPs. We chose not to define $A_h$, because it is really dependent on the MDP's hierarchical structure. But we agree with you that for concreteness it helps to have a formal definition. Following your suggestion, we will cite their definition as an example of how $A_h$ can be formally defined to model a certain class of hierarchical MDPs (e.g. mazes).

Thank you again for taking the time, and please do not hesitate to follow up if you have any further questions! We appreciate it.
I thank the authors for their thorough response. I think all of the minor points and questions are satisfactorily handled, except I still don't understand how exactly the authors want the set $A_h$ to be formally defined (e.g. [25] introduces a similar notion formally in Definition 1 using a notion of partition of states MDP states).

However, I am still unconvinced by the assumption that clustering function is available. I admit it isn't literally implying that transition probabilities and rewards are known, but at the same time, I have hard time imagining any semi-realistic situation in which one does not imply the other. In full RL, the agent doesn't know which situation (which sub-MDP) it found itself in, which would necessitate querying the clustering function online, and that in turn would imply knowing $\tau$ and $R$. Indeed, the running example of essay writing is still not showing that, and the maze environment is very simplistic. 

As far as I see, [25] does not discuss the feasibility of the assumption about the partition being known (agent having access to the clustering function, in the terminology here), but a large amount of their analysis is in the context of planning, where the full structure of MDP is known anyway.

Of course, it is possible that the algorithm would still work as expected if the clustering was only approximate - but the paper does not say anything about that.

I am therefore maintaining my rating for now.
Thank you for getting back to us, and we appreciate your helpful feedback!
I appreciate the detailed response and believe the work should be accepted, and will maintain my score.