A theoretical case-study of Scalable Oversight in Hierarchical Reinforcement Learning
Authors: Tom Yan
Zachary Chase Lipton
Venue: NeurIPS 2024 poster (2024)
Keywords: Scalable oversight
theoretical hierarchical reinforcement learning
Primary area: safety_in_machine_learning

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.

A theoretical case-study of Scalable Oversight in Hierarchical Reinforcement Learning
Tom Yan, Zachary Lipton
Machine Learning Department Carnegie Mellon University
Pittsburgh, PA 15213
(tyyan, zlipton)0cmu edu
Abstract
A key source of complexity in next-gencration Al models is the size of model outputs, making time-consuming parse and provide reliable feedback on. To ensure such models are aligned, we will need to bolster our understanding of scalable oversight and how scale up human feedback. To this end, we study the challenges of scalable oversight in the context of goal-conditioned hierarchi- cal 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 apt sub-MDP reward and algorithm that allows us acquire and scale up low-level feedback for learning with sublinear regret. the ordinal feedback setting, 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, work aims to consolidate the foundations of scalable oversight, formalizing and studying the various challenges thereof.
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 better our understanding of scalable oversight: the ability to provide scalable human feedback to these
complex models 2 g 15 5) An immediate, key challenge to overcome the size of model
outputs, making it come--oosuuing for humans to parse and provide reliable feedback on, even with
Al-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 answering the question:
How can we scale this limited feedback to supervise 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, investigate 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 humans produce many of our most complex creations.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To formalize the setting, we study scalable oversight in goal-conditioned hierarchical reinforcement learning (HRL) setup. Goal-oriented RL is 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 conceptua//eechnicl 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.
1.1 Preliminaries
We consider a finite-horizon, Markov Decision Process (MDP) M = P.,, H), with finite state space S finite action space A, transition probability P S x A A()), reward r(s, a) 5 x A - (0, 1] and finite horizon H. The learner interacts with M starting at state 81 and the episode ends after H = H Hi 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 TT, generated by policy 5 + A.
Accompanying Example: Consider the task of learning to generate long-form, argumentation essay. Providing feedback to an and-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 assign a single rating to the entire essay. A tractable alternative is to learn hierarchical model, with higher-lever 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 rating on the whole. This approach also mirrors existing rubrics for scoring essays []]
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 Hn, Hi). In particular, this means that for the global policy π S + A. it is infeasible to obtain reliable feedback for its trajectory ~ n, P. as |T| H₁ Hj. This thus motivates hierarchical learning, which makes possible the acquisition of reliable feedback in spite of bounded human supervision.
Bounded Feedback:
1.1.1 Goal-conditioned HRL
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 hierarchical policy. This set consists of a high-level policy xh : S + A(Ax) (outputs a high-level action a at state s E S), and set of low-/sub-pol policce-p nf a
St 3,0 + A(A), where 5t St.a. S S is the set of all states reachable from s after Hs 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 shorter horizon of at most max (Hn, Hi), making 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 at state to a goal-state g(s, a²) E St Sa For example, s is the current content of the essay, a is the action (in natural language) "add an argument using X" and g(s, a²) is the content of the essay with the "argument using X" included.
Goal-conditioned sub-MDP: Given high level action a at state s, this defines the sub-MDP M(s, a²), which has state space St a.ah S S, action space A (action space of the original M), transition probabilities /' restricted to St Sa starting state s and finite horizon H' The sub-MDP reward o will be defined later and as we will see, apt choice is important for achieving sublinear regret.
High-level MDP: Given a set of low-level policies, T may be thought of as operating over a high-level MDP with state space S, action space Ah, starting state s and finite horizon H², Impor- tantly, the bigh-level transition p' of this MDP is a function of the current set of low-level policies (r'(s")s, a²) = Pr(s Tzaah = 8'), which denotes the distribution over the (final) H,th state that n! ",aa reaches. Furthermore, the high-level reward ( a²) B Beg.ayya w.c. E
Hz f r(8g, 03)1s 1s s]

---

corresponds to the intermediate return of sub-policy T s in (s, to key complication in hierarchical learning. This is that both the transitions and rewards in the high-level MDP are non-stationary, as sub-policies Te,a" are updated over time.
a²). Altogether, this gives rise
Interaction Protocol: At each time-step the high level policy chooses high level action ar based on current state 8;. This defines the sub-goal state g(s,, (z), along with the corresponding sub-MDP (s;, at) with finite-horizon H,, in which sub-policy T Taa.a, is used to try to achieve the goal. The overall return of the high level policy net and low-level policies { fa..e.. A is the sum of intermediate returns aa))) incurred:
A
Ha a = 81].
Va (81)= =E
Instantiation in the example: returning to our example, for a cogent essay, the arguments need to be logically related and built top of each other. This results in sequential decision making problem corresponding to the one solved by the high level policy x². Given an argument g(s, a²) to flesh out, the low level policy _! * generates up to Hi 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.
1.1.2 Learning Task
Our aim is to learn hicrarchical policy, whose return is close to that of the optimal, goal-reaching hicrarchical policy, which we define as follows. For brevity, from this point on, we will use a" and interchangeably to denote high level action.
every sub-MDP M a), there exists a policy that achieves the goal g(s, a) almost surely. That is, there exists at least one policy E Is in the policy class le. such that Pr(sh, = g(s,(,880 a)) = 1.
Assumption
In other words, we assume that the goal function g is well-defined in that designates goals that are feasible to reach from the starting state (e.g. the argument can be successfully fleshed out in Hi 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 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
p2 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 r(x) C. Pr(sT, = g(8, a)), then æ is goal-reaching and Pr(s),, = g(s a)) = 1.
Definition 1. Define optimal low-level policies T E arg max r(T) + +C Pr(s}, g(s,a) a)). Define optimal high-level policy as πT" = arg 7an (T
In words, T has the highest intermediate return of all goal-reaching policies. Now let n² be the optimal legel policy fixing each sub-MDP policy to be ="
Learning Goal: We wish to learn set of near-optimal high- and low-level polices (π, (T. such
that: V= (2 Va < C.
1.2 Takeaways
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.
3

---

On a more technical level, this paper studies the challenge of training a set of (instead of a single) policies that work together 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 HRI 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 set of low-level policies. Notably, Algorithm [ 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- accumulates additively (instead of say multiplicatively) as speculated upon in 15
Under ordinal feedback, develop a novel hierarchical experiment-desinn Algorithm 2 building off of existing work on experiment design in preferenced-basee RL (29]. A key observation is that in the ordinal case, low-level feedback may not be sufficient and high-
level feedhack 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 used low-level feedback is sufficient and one form of feedback, with higher cognitive load, leads to better sample complexity.
2 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 (5). [22] studies goal-conditioned HRL with the key result being sample complexity lower bound associated with given hierarchical decomposition. On the upper-bound side, an algorithm (SHQL) is presented, albeit without theoretical guarantees. By contrast, our work presents learning algorithm with provable guarantces, and further shows that learning in goal-conditioned HRL reduces to multi-task lasti-task, sub-MDP regret minimization.
25 studies HRL under the options framework, providing a model-based Bayesian algorithm with access to prior distribution over MDPs that is updated over time. It does not adaptively learn sub- policies based on observed returns, computing instead an option for every exit- 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 ("bottleneckk") 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.
RL under ordinal rewards: There has also been considerable interest in bandits/RL from prefer- ences [26] 28
30, 29). Following the demonstrated success of RLHF 9 31] 19 A. 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.
18
14,

---

3 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, naive approach is to learn near-optimal sub-policies in every sub-MDP M(s,a) 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 high level policy that visits these "good" sub-MDPs. Please see the Appendix [or all the proofs. Note that in what follows, for brevity, theoretical statements will contain the phrase "with high probability" and the appendix will contain proof' that formalize this guarantee.
3.1 Sub-MDP reward design for Hier-UCB-VI
We 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 exploration bonus that tracks the best/unexplored sub-MDPs. To this end, we develop an adaptation of the classic UCB-VI algorithm two key ingredients needed to construct the Hier-UCB-V VI Algorithm I
We highlight
Tradeoff's in sub-MDP reward design:
Learned sub-policies in HRL have to tradeoff between two objectives. One is high intermediate returns r(Te.a). The other is that exit-state; sub-policies should not land at "bad" states, as even if the intermediate return is high, V(s)r;"" ss 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 calculate V/? Luckily, in the goal-conditioned setting, there is a natural answer for "good" exit-state: g(8, a))
To operationalize this, we design sub-MI>P reward that trades-off between intermediate sub-MDP return and goal-reachabilityy In sub-MDP Ms, a). at time-step h, sub-MDP reward fI, a') r(s', a') + x1 (h- Hi = g(s, a)). Crucially, here we the weighting λ max(2HH, Hi, C). which corresponds to an upper bound on the regret should we not reach the goal-state.
Next, wish to obtain UCB for r(*", Our main observation is that by using no-regret subroutine for learning in M a). the regret guarantee directly translates UCB. Due to our choice of sub-MDP reward rt, the UCB includes a penalty on non-goal reachability. Lemma (UCB implied by sub-MDP regret). Ler ( ()) be an upper bound on sub-MDP M (s, a)'s cumulative regret after n rounds. Define 3 (xs + H1)2 log(
UCB construction:
[CSS,A)lA, and bonus,
(n) UB(R" + B/n
2ha 1
* gg(s a²
(H
n
Then, the average reward plus bonus (s, a) + (n) is an UCB for for r(TT 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 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: to be the idealized transition (g(s, a) w.p. 1). This allows to prove our regret guarantee as described below.
3.2 Regret Analysis Hier-UCB-VI
We start with a definition on clusters of equivalent sub-MDPs. Let there be C(S, A²) such clusters. In the most general setting, not known apriori if there 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 (
(sss,,, 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 that HRI. 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
5

---

Algorithm HiieaachhicllUCCI-V (Ciie-UCC-VV
1: Initialize D = 0, Qu (s,a)
H₁, Hj Vs, VHa-I 0, max CC, 2H, H1)
2: for episode = 1,.... K do
3: for timestep i H,...., do
4: for (s, a) E Al do
5: if a) D then
6:
Update UCB: UB(r" (s,a)) (xMM( (s Set:
7:
Qi(s.a) min(H UB( (s. + V2+i(g(s,a))
(1)
8:
for E do
9:
Vi(s) = max Qi(s.a)
10:
for time step h = 1, 1,... H4, do
Take greedy high-level action a = arg m Qn(s a)
12:
Traverse sub-MDP M( with current sub-policy π N "ot
and transition to $
human supervisor provides low-level rewards the length-H, roll-out of Nh.
Feed low-level rewards into no-regret RI. algorithm A for sub-MDP Ms af)) Set the sum of the low-level rewards (the intermediate return of a s8.0 reward r(s a = r a4.
Nh. in ( ax) the high-level
14:
Add to dataset = DU [(h, sh, ah, r(s a
minimization in the cardinal reward case, which as we will see in the ordinal reward case will not always be true.
Theorem (HRL regret minimization reduces to multi-task, sub-MDP regret minimization). Let MoRKKMM (e (s.a)) be an upper bound on sub-MDP M(s, a)'s cumulative regret over K.H (s, a)
(RRN
visits:
Σ (81) (
Σ
UB(R ((())) H² (N..H.
(2)
S.REC(S,AM)
Proof Sketch. We describe the key regret decomposition, After some manipulation, the regret may decompose into the following form, EK Vi V (s1) s E
Hn. of ch
which may be parsed as follows.
pf: = UB(r" (s) r( Nidih shatt)
captures the regret due to sub-optimal intermediate return, the
return of S,S versus the return of T
nh = - Vii h+ (sf of of = PMA - (s a captures the regret due
sub-optimal policies missing realhaaachabilitt. Here Ph. the idcalized transition goal-reaching). while p is the transition induced by the current sub-policy.
c p (V/
(sh 1) is martingale difference that concen- trates via Azuma Hoeffding, and dominated by the previous three sums.
W (s a (V&
Focusing on Σ p + Th + o + st. we observe that 7h of s HH (5) * g af)). The key remaining step is to recognize that p + > + of resembles the instantancous regret in Ms dft), and the result follows after some further bounding and rearrangement.
For concrete bound, we note that if A is set as the classic UCB-VI algorithm, then attain the usual Õ(VK) 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 U'B(R" (s.a)
Goal Selection: An astute reader will note that the return of the learned hierarchical policy is close to Vi (81), 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 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 :...".. Then, an useful corollary of the sublinear K VP (s1) - VP (s1) S ŌlVK), that it directly implies Hier-UCB- VI regret bound, _े E
an UCB on Vi"' (*(1) (optimal return under goal g¹). 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' je(n]-
4 Learning from Preference Feedback
In the previous section, develop an algorithm efficiently learn a hierarchical policy, purely from low-level, cardinal feedback. Now, we consider learning from ordinal (preferences) feedhack. Our first observation is that the low-level feedback no longer sufficient for learning a good policy.
Proposition 1 ioon-identifiabiiity of ranking among sub-MDP returns). For any deterministic high- level policy learning algorithm with Nı samples of low-level feedback, there exists MDP instance that induces regret constant in Nt.
The intuition for this is simply that low-level, ordinal feedback can only identify rankings of low-level policies specific goal (sub-MDP), but not necessarily low level policies across differing goals. Thus, no matter how large the low-level sample-size N,, the regret is non- vanishing in N, and hence high-level feedback may be needed learn. Please see Appendix for all proofs of results in this section.
4.1 Labeler Feedback and Consequences for Reward Modeling
The canonical approach to learning from preferences 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 + RRd M has linear reward parametrization w.r.. o if there exists an unknown, reward vector 0* E IRd such that r(s, a) = (Ø(s, a), 0*) for all s, a E S x A.
Given trajectory т = (s1, a1...., SH aH), we may then define trajectory feature o(T) Ee,ocer Φ(s; oz), and policy feature expectation under transitions P, o² (T(TT) = E p(((T))
With known feature map and unknown reward parameter 0*, the preference feedback or follows the Tradley-Terry-Ioe (BTL) model [6].
Assumption 3. For trajectories 71, T2: Pr(m > 12) =
((r2))).
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?
- o(T,) EielH d(s/ a²); the key difficulty is that SuD feature expectation ((>), a²) is dependent on the sub-policy deployed in (s) af). Thus, the high level labeler will have to have mind some sub-policy Taaa when making the comparison. We study two natural types of feedback:
Consider high level trajectory Ty { ((ssaa))) Hn
7

---

1. Comparisons based on current sub-policy execution: It is natural to first assume that the labeler envisions o( af) = (( ". 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 Th (potentially through Al-assisted means).
This knowledge would need be updated over time as low-level policies Tyaa improve. which introduces 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 sub-policies used in the comparisons. A natural choice then is for the labeler to envision (05/ a²) "(m", sq.a? ). 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 mis- match of how the current sub sub-policies actually execute. Although it has the advantage that the labeler is no longer required to (somehow) keep track of low-level sub- sub-policies, thus reducing the cognitive load.
In what follows, we consider both types of feedback, showing that learning from feealized-feedback is possible. As we note, a drawback of dlealized-feedbalt realized features (since these are generated under current policies TT while current-feedback is unbiased. We present an upper bound on the bias below.
that it is biased with respect to the
Lemma (Bias of idealized-feedbacee
Suppose there are Nn, Ni high, low-level trajectories, bias b (mi) TTTh (mb)) (0", ob (x1) - 63t (TT))²² = ONN,/Ni)
No. such that: ||b||2 = Em K0"
Proposition 2 (Reward model learning). Let OMLE- = arg ming (0) and let Co denote an upper bound on bias C2 2 [[b]]. and y, constants. We have that with high probability:
CoV 722
C/ + d log(1/8) + AB2
- - -MME SA Ah +XI S SCV
4.2 Hierarchical Preference Learning
We now construct a hierarchical, preference-leaninee algorithm that invokes REGIME, a contemporary preference-leaminn algorithm with provable guarantees, as sub-routine for sub-MDP learning [29].
Sub-MDP reward learning: 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-reachabilityy For trajectory т, define Φi a.)) [oriig (sT, a. 1 = H1 A s7 g(s,a) a))
and for policy म, feature expectation (s7 az) = Worig (87 ),), (i Hi) Pr(sT, g(s,a)))
The corresponding reward vector will also change to become 6" = (0riig x]] for unknown Corig K. 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 coal-reachability such that is higher than some given threshold. As before, we take the threshold be max(C: Ht), And so while x is unknown, we know that 2 max(C, H,, With this set up, we can then bound the regret due 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 sub-policies). For any high-level policy with high probability:
C1
F0 (P(P((T)) 65 N (TT))(()))))))))))) < HhC
+CE')
VNI
where this bound makes use of the REGIME guarantee on sub-MDP M(s, a) that (6 0*) ppe (m 001 C VN: + Cze' 129].
8

---

Algorithm 2 Hierarchiicll-REGIMEE (Hier-REGIME)
Require: High-level policy class 11 low level-policy classes 1I, 1: for episode I,..,, Ni do
simulator p' with e' e'-prccisio
2: ( x2) - arg max a1 32 EU.. IT. 1 (T1)
(T2)
b explore using policy
feature expectation across sub-MDPs
3: St 2x+1 Σn (0"h (TT) - of (T2) (o
(T (TT))²
4: Generate trajectories T Tá and acquire comparison feedback on comparison feedback for
the pair of length- H1 trajectories
5: Compute MLE 6 from {rp]. T and (o
6: Compute Ni = arg e s,a
(0 (T),
7: for episode
1, ..... N₂. do (TT, m + arg max,, mlll |1 pe (TI) " (T2) (TT)) > high-level policy
8:
feature expectation generated using No
Sh+1= D + ( (TI)
" (T2)) " (TI) - " (TT)))²
9:
Generate trajectories 7f', 7 and acquire comparison feedback on comparison feedback for the pair of length-H,, H1 trajectories
11:
Compute MIE 6h from (-i, 12) and (o
arg max zn " 0h), low-level policies
12: return high-level policy +
[x 8,800 S.
Lemma 4 (Regret due sub-optimal simulator pe'), Let pp' (T) denote the feature expectation under high level policy n, sub-MDP policies No and transitions P With high probability, for any high level policy a: M (T),0") S SO(HHdd + HAH + H3
4.3 Hier-REGIME Analysis
Now, we present the Hier- REGMME Algorithm At high-level description goes 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 compute sub-MDP policies :N for each sub-MDP (s, a) (L6). Finally, we invoke one copy REGIME for the high-level MDP, where the feature function is defined o S (L8). Next, note properties about Algorithm 2
Hierarchical Exploration: A key aspect of experiment design in offline RI. 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 (T,, { H), (T, {=? E (IT*) X
s.a IT
instead of over æ1, π2 & However, show that in the goal-HRL case, we can fix the sub-policies to be Nu (for N₁ large enough), and this is sufficient to compete with the optimal, hierarchical policy.
Additionally, unlike the tabular setting, sub-MDPs now share common reward parameter 0", thus allowing us to jointly, instead 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: {o (TT) 6P" (m2) क E US.. [1aa) and
P0 ( (T2) ni T2 I T..a T.M Vs. Therefore, when coverage of high level policy subsumed by low-level features already (the latter a subset of the former), 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 better rates. First, we derive the regret decomposition and then use it evaluate the sample complexity.

---

Theorem 2. With high probability, under N₁ > O:
V V
(2dlog(1 (1 + NA
$ f0t (TTt.((T)) - - (x)))) VN
1)100 - -0lls,hn"
d
"p" (T"),
K0 pp (+) 0" ", P(f))
To parse this, the regret decomposes into four terms. The first term is the regret due to sub sub-optimality low-level policies T. The remaining three terms are derived from sub-optimality due to high-level policy Rt decomposing into the second term on regret due to bias in learned reward 0 the third and fourth term on regret due to sub-optimality of simulator p''.
A main benefit of developing learning Algorithm ii that we can then quantitatively assess the sample complexity associated with the two types human feedback. As one may expect, there is 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
obtain the following rates in terms data tradeoffs:
Idealized-feedbcck and required high-/low-level feedback: feedbbbc the overall rate comes out to ONN, + N 1, While high level trajectories provide additional coverage, it also incurs bias linear in Nr. of the bias of the low-level trajectories, thus slowing down the rate (Lemma 2
Current-feedhack and required high-/low-level feedback: the overall rate comes out to O(N,1/2= + N, N=-1/2.. The current-feellbck unbiased and results more efficient reward learning with ||0 -80--010 - = 01) (29].
Only feedback is required due to sufficiency in coverage: the overall rate comes out to O(N, In nutshell, this is because we can explore with just Ni low-level samples which is unbiased, resulting in ||0 Allss, =11). Hence, both exploration and reward learning is efficient.
5 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.
In condiiioid HRL. regret guarantees 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 leam 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 Al-assistance.
Limitations & Future Work:
References
[1] AP English Literature Scoring Rubries. http://ggggggggppaaaaa.ooaaaaaar pdf pal//apenglish Literature-ant wtwp::/wwww.......oo..oooooooeaa -or.::onnnrroao----33--oooooo-or pdf Accessed: 2024-05-15.
[2] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint (rXiv11606.06655.3 2016.
[3] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pages 263-272.
PMLR, 2017.
10

---

[4] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:200.00580 2022.
[5] Samuel Bowman, Jeeyoon Hyun, Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamilé Lukošiūté, Amanda Askell, Andy Jones, Anna Chen, et al. Measuring progress on scalable oversight for large language models. arXiv preprint arXiv:2211.035400 2022.
[6] Ralph Allan Bradley and Milton E Terry Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
[7] Elliot Chane-Sane, Cordelia Schmid, and Ivan I Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International Conference on Machine Learning, pages 1430-1440. PMLR, 2021.
[8] Paul Christiano, Buck Shlegeris, and Dario Amodei. Supervising strong learners by amplifying weak experts. arXiv preprint arXiv:/8/0.0888 2018.
[9] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[10] Danijar Hafner, Kuang- Huei Lee, Ian Fischer, and Pieter Abbeel. Deep hierarchical planning from pixels. Advances Neural Information Processing Systems, 35:26091-26100 2022.
[11] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pages 4349-4358. PMLR, 2021.
[12] Evan Hubinger. Ai safety via market making, YWwzcccGbccM:JKpT44555 aaa/ safesty via waraaattt-i----aeee------e- makingg Accessed: 2024-05-15.
[13] Geoffrey Irving, Paul Christiano, and Dario Amodei. Ai safety via debate. arXiv preprint 1805 00899, 2018.
[14] Kimin Lee. Laura Smith, and Picter Abbeel. Pebble: bredback-efficienn interactive rein- forcement learning via relabeling experience and unsupervised pre-training. arXiv preprint arXiv:2106.05091, 2021.
[15] Jan Leike, David Krueger, Tom Everitt, Miljan Martic, Vishal Maini, and Shane Legg. Scalable agent alignment via reward modeling: a research direction. arXiv preprint arXiv: 181100777, 2018.
[16] Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierar- chies with hindsight. arXiv preprint
2017.
[17] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.
[18] Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference- based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1033 PMLR, 2020.
[19] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkín, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
[20] Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.0m 2021.
[21] Jack Parker-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Ef- fective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems, 33: 1350-188-8, 2020.

---

[22] Arnaud Robert, Ciara Pike- Pike-Burke, and Aldo A Faisal. Sample complexity of goal-conditioned hierarchical reinforeement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[23] William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiuuing models for assisting human evaluators. arXiv preprint arXiv:2206.05802 2022.
[24] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021 2020.
[25] Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33:6708 66188, 2020.
[26] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46, 2017.
[27] Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively summarizing books with human feedback. arXiv preprint arXiv:2109. 10862, 2021.
[28] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference- based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18794, 2020.
[29] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Provable reward-agnostic preference-based reinforcement learning. arXiv preprint arXiv:2305. 18505, 2023.
[30] Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or w-wiee comparisons. arXiv preprint arXiv:2301. 2023.
[31] Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 19099.88999 2019.
12

---

A More Related Works
Scalable Oversight: Scalable oversight a nascent but important topic in the area of Al alignment 2 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 market-making, all of which aim to have the model (or auxiliary models) generate interpretable and/or lower-dimensional forms of outputs for human to parse [15 13 24 23 [2]. Our
1, 5
work studies how one may leverage hierarchical structure one approach to scaling up feedback.
Goal-conditioned RL: Further afield, there has been lot of work demonstrating the promise/success of goal-conditioned RL with examples from the likes of [16] 17 7 [O]. 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 roal-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.
B Concrete Hierarchical MDP Example
The prototypical example in HRL is the maze, as studied in for instance [17 22]. maze consists of rooms with doors. The goal is get the exit in few steps possible. The MDP may be defined as follows:
For the global MDP, Sh St where h denotes the index of the current room, and s' 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 consists of moving to the (N, S, E, W) door of the room. is the current location of the agent, and g(s, a²) maps the goal (door) to its location.
For the Low-level MDP, it has state space St S and the action 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 225
13

---

Notation
(s,a)
sub-MDP at state with high level action
Tha
policy used by sub-MDP (s,, a)'s no-regret algorithm during the i-th visit optimal policy in sub-MDP (s,aa
Tao
expected reward of policy v in sub-MDP M(s,a) sub-MDD reward definition. observed reward of policy in sub-MDP M(s, average observed policy reward (s, = Ei= ((T sub-MDP (s,, a) cumulative regret across n steps, (8, Ei=1 r(T (
FLA
F(T).a)
(s)
R" (3,
N s,a)
number of times M (s, a) has been visited up until episode k. horizon
(- 8,a)
distribution over states of policy after going through subMDP M (s. a)
4n
factor such that ,i,, Ö(vr)) where the Ô omits up log dependence K
Table 1: Table of notation used in this section.
C Proofs for Section 3
C.1 Sub-MDP Bonus Construction
Sub-MDP Reward Definition:
Define the reward in sub-MDP M(s, a) at time step to be: r1,4(s' ,') r(s', d') x1 H1 A = g(s,
Firstly, since by definition N² E arg mal, r(*) + C Pr(s = g(s, we have that Tha E arg max sell,, r(T) + K. Pr(s = g)).a)).
Indeed,
((T),a) Pr(SH T2. g(s
= [ = Crrr(s No.
= + (K (k- ( Si = g(8,4))
2 (r(T) + C- Pr(ss a)s + (k- C) Pr( = =s(s,a)
(Pr(s F. g(s, a)) 1 12 Pr(s g(s, VT)
Secondly, using the definition of rı, we have that:
r((=(,a) r((T((a) = r(Ttta)) + kP(s "T = g(s, - -r(T <P(s t. = g(s,a))
g(s, a)) = 1. this implies that By the reachability assumption, P(s :=..
ri(TTaa) - ri(TT = r(TTTa)) -(( + kP(s the # g(s,
Therefore, summing this across visits to (s, a), we have:
Rd R*,saa) a)
n((T) - -r((TT
i=
Σ ((((a))) - -((T)))) + D P(sm. + g((,,))
This statement is useful because we can compute an UCB on Σ T(TT and, implicitly, a LCB on E r( (provided we do not bound R a)).
14

---

Lemma 5 (Bonus with "penalty" for non-reachability) Let UB(R" (s, a)) be any upper bound on the sub-MDP regret, then we define:
(n) UB(R"(s,a)) + (N + H1)2 ((S.A"))HaK
1 The
SH + 9()
n
Then, as, + (n) is an UCB for r( with probability Let the event that the above holds be ag
Proof.
(T
R" (s)
P + {((8,a)) +
the
Σ
((T
i=
i=1
RR S
# g(8, ()), - r/nn +
Σ
r r(maaa)
(o)
t=1
1=1
(s
1s 2 * g(s, a)) + kapn +
n
n
r(
Σ
f(m),a))
i=1
i=1
i=1
n
< UU(R" (k + Hi) E1 the
a)s
Σ
f(
(K' = k Hi)
(o) Here we use two applications of Azema-Hofffding:
With probability higher than 1-8: 8:
n
n
Σ
P + g((,,a)) - Σ
1s + g(s)a))) Stnn =2vn
* We have that (P the + g((s,a)) 18 g(s, a))]=[-1]] O.
This is true because P(s + ggs a)) and 1 (s - 0 + g(s, a) are function of only the transition probability of the MDP the step conditioned on F,-1. Thus, P(H Th.- g(s, a)) 1(sH, x=.. g(s, a)) is martingale difference. And With probability higher than 1 - 8:
Azuma- Doeff-ioe.iiing.
r
f(T < High S H22vn
This again follows from Azuma- hauma-Hoeffding on martingale difference r( f(Tr)a)) as ((((T) = 0. And |r( f(T).)) I Hi-
Thus.
1
r(TTaa) <
f( 8. + (n) = r(m2a) - Fn(s,a) (n)
i=1
15

---

Remark One choice for U (B) 2///2 /1/2V//Shall Vist.alAAp if we let As,a be the standard UCB-VI algorithm (3).
C.2
Optimism Lemma
Lemma (Optimism). Let VI be the V value as in Algorithm a episode Let xt" be the optimal hierarchical policy. For fixed k and h, if Ex holds, then:
(s) 2 VI (s) vs
Proof. Fix episode k. We will prove this lemma via induction on H + 1,-.,,.
Base case: At h Hn + (s) 2 0 Vi (s) for all s.
Induction Step: Suppose this is true for up until h HA 1.....N h'' 1. Now at time step h and any 8,
Firstly, if ()) = Ha Hr (e.g. if 8, & D then (s, 2 (8,(s,)). Otherwise, 2 < H, Hj and we have that:
(s, - a) = +2
a)) + V ( a))] - (r(*))n) (r((T))))
Ph. VT
(Q) definition as in Equation
(2 - Pv. P
(s, a)) (FxtA bū.0 (2
an UCB of rfT),))
(0) - (o
(T reaches goal state w.p 1, so Pa (g(s, (induction hypothesis)
2 0
Thus, (s) = max, Q (8, 2 max (8, = V2 (s).
Corollary 2.
K Σ Vi (a1) V/ (81) k=1
(x))
Σ v+((s) ( (77((s)
(81)
C.3 Supporting results needed for regret analysis
Proposition 3.
K Σ (s1) - -T (81)
K H
ch + th +ox + Ph
(3)
Jam Jum
Proof. For any and h, we consider bounding v+(()) Vi (stt), which is equal to:
Vi (s)) = (Q) - ( att
S (Famaceg.at) att) + b bg (Nrhi oft))) - r( ( (s
( a()) - A h+t1 (sti
(due to the min)
= p + |V at)) pasa Vith at))
where we set 1 F at) 1 at (s r(T (
16

---

Continuing with the original proof and focusing on the second term:
i a.))) PTAAA (sh oi)
- (n c ahi) - P P an) + p - -
(Ph A Vi+++ (s af,)
P (V V h ab))
(Ph is the transition under optimal sub MDP policy so it takes of a to gl at) deterministically)
(Pr pma W (.t.A)VVt (sh, of + (Ph p( V at) + prsd (V/+t1 Vit41)
= + of paad (V (s ott
where
the = (Ph - pan. ) (sf, a
of = (Ph- - p= (s
In summary,
(s - 1/= (sh)
s p + * + of paa. (V
h+1 V (sh att)
(v V ( + ch th + oh + p/:
where we introduce the notation ch = P 1++1 (sh (V/41 Unrolling the recursion starting at h
(** - Vi (5%) h
1(5h Mh + oh Ph. +... (I)""(sh,, + -in + onn + pir))
Ha
th + t + pt))
Summing across E [K], it suffices to bound:
K
K H
(i V7 (81)
ch
th
o
ph.
(4)
Remark 2. There are two sources of sub-optimality the bound.
One is the sub-op hub-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 ph-
The other is the sub-optimality of not landing g(s af), there is covered by r of which affects future reward. The martingale difference ch is zero in expectation, so it is not some measure of suboptimality.
We first bound the Ç's, whose sum is dominated by ΣK ΣHI, P %h oi.
17

---

Lemma 7. With probability 2 1 5/3:
K H
t s ''
k=1k=1
Let the event that the above inequality hold be Ec.
Proof. The concentration of S follows from Azuma Hoeffding, as the following is martingale difference.
ch = P (V
V (sh (Vi+1 V (+
with EECk| = 0, since the expectation is only wrt randomness in + Moreover, this martingale difference is bounded by 4H H
Next, we simplify the sum of remaining terms.
Lemma 8. We have that:
Hn
H
H
p ( * #l a4))
k=1k=1
h=1
and
K
H
K H
of < n H
park (s 4 glsti att
Rmn Am1
k 7uml
Proof.
K H
(Pn - p.AKA
1=1k=1
p (s # gg(sh (1) o(i) (
H, < Hh
pmak (sti + g(st)
Similarly,
18

---

K Hh.
PPr - PREM (sth) at)
Hn.
pan. (sh+1 # g a ( (ith) ah)) -V+++1 - 1/ (sh+))))))))
Ha
S H H
p # 9(522
1= 1=1
Lemma 9. With probability 2 1 -8/3:
K
H
(n.a)
(s..) Σ
UB(R)(s,a)) (R' a) (k" + k)).
Σ
P
Σ
r(T2aa) -
E
k=1k=1
*,0EC(S,A5)
S,0EC(S,AM)
t=1
Let E be the event that this holds.
Proof.
We first expand the p sum:
H
Ph
K
Ha
b (NA. (()) r(x (s
TN ag)
(sh,
ot
(K.
Σ
F.(s,a) + bz - r
NK.Ha (s,a)
UBB(R((s,)) + - - E₁ 16 + g(s.a))
E
Σ
f( 5.a
r(Tr)a)
S,
j=1
(using definition of bonus) sT.
(x.Ml(ss.a (s,a)
Hod
UB(RR((s,)) + + E 11 + g(s
Σ
Σ
((T +
r(m),a)
AA)
j=1
(Azume-Hoeffding for concentration of f around r)
Using the two-sided concentration bound we had before (the other way): Ej=1 18 + g)) + 2h.a
v/ 2 E P( + a(s w.h.p:
((T -r(TT(a) 2 R² (s, k( Σ
1 N/.
1s # g(ssa)) + vi)
==1
Σ ( Ri(ss a) + na/ 2 Σ
r( [ K Σ
1(8H, # g()),)))
1=l
1=1
1=1
19

---

We continue our derivation:
NK. (s,a)
Σ
(s) + R
Σ
[ss * g(s,a))) r((),a))
1=1
j=1
(n" = n + Hi)
NK. (s,a)
(x.Ha
(B(R'(s, (s) + K
Σ s,0EC(S,AM)
(
+ x -R)
r(T +
Σ
s,aEC(S,AM) (using the identity above)
NXK Σ
(k..a(s..)
UB(R'(s,a)) - -R'(s, + (n" + K));
r(Tiaa) -r(m +
Σ
s,8EC(S.A4)
i=1
,,EEC(S,A")
2=1
20

---

C.3.1 Overall Regret Bound
Theorem 3. Under events Nsa Sia 3E n EP, we have that:
K H Ph
to
Σ
(s.)) +0 ) (s,
k=1k=1
*,0EC(S,A))
Proof.
K
H
R + th + 0%
Am 1 hml
NK. (s.a)
Σ 6,
Σ
r(Tz,e) -r(T2,a)
(s.a)
(s, - -R'(s, + kah
K H
+ 2H H
p (s # #g(sh.
i
A,
Romm
1 Po m
N.. (3,0)
UBBRR(ss (8, - Rs(ss, a) + math
E
A,EEC(S,A))
NAKiMi (o.a)
N.K. (s.a)
Σ
Σ
r(TTaa)) - -r(Ts,a) HH Σ
Σ
P(sm # g(sh at))
(,EEC(S,AR)
S,8EC(S,A*)
(group third sum by 8, a)
(H,a))
(B(R'(s,a)) (s. 0) + ka
Σ
NAK.Mi (x.a)
(K.Man(s.)) (s.a)
Σ
Σ
- - + Σ
P( * (())
The
(x 2 2H, H)
S,0E0(S,AN)
(K.a)
(B(R"(s,a)) aR) mar
Σ
(a
A.
(using the definition for sub-MDP regret)
(s.aH
KR (s.a)
Σ
Σ
(B(
R (K..a
Σ
kth
N.K.Ha (s.a)
(B(R)(s,a))
Σ
+UB(R (*.
O (K.H.(s,a))
A,
(,
(since Azuma-Hoeflding s.t v O(vi))
(x.a)
UK.
Σ
+ A. (b..a)
O(H" H* / (K.HH(s,
A,E
(using monotonicity of upper bound U (s, a)) in assumption that C O(1nHHi)
(H (s, + IRR NK (B.o) + +OH / (NK.Ha(s,a)
21

---

Corollary 3 (Regret under (C(S, | 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:
(log(N Ho (s,a)) + A,0EC(S,AM)
Σ
+1) T)R +O(H" (K,HH(),
$ (log 1 1)
Σ
(.
1I 11
s,0EC(S,AM)
EnnECiS, NK. = K)
- (log K
Σ
11 VISE /I (s, O( CI((S, K)
s,0EC(S,A4)
(plug in UCB-U guarantees)
$ 5(H,)/2 /max (S) / (CS.A)) + HI C(S, (H) a,a
V
C En,EE((SAA)) NR, = K)
using UC's guarantee that upper bound U UB(R" N (sa))== = =H,/² St llllN (s,
Remark (High Probability Bound), For completeness, we show that the regret bound holds with probability greater than - 8. The regret bound holds under As,a En NEE n EP, by union bound:
Pr( E% NE NEB)
Σ Pr(-E.,) --r(-E5)-) - -Pr(-EP))
8,4,
5
(IC(S, | 3)C(S,A"))HA) 5/3 -8/3
= =1-
22

---

D Proofs for Section
D.1 Low-level Feedback insufficient for learning
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 iooniidenifiaaiiity of ranking among sub-MDD returns). For any deterministic high- level policy learning algorithm with N₁ samples of low-level feedback, there exists a MDP instance that induces regret constant in Nt.
Proof. Consider two-horizon MDP with starting state $1 with H₁, = L, H₁ = 2. There are two possible high-level actions ai and 02 at 81-
For any policy π in sub-MDP M(s1, 01). let it have feature expectation ((π²) [ (T*), 1, 0j. and for any x² in sub-MDP M (s1, 02), <(*²) [ (TT"), 0, 1].
[0, C², 0] for some positive Now, we consider two MDP instances with = [0, 0, C*] and constant C".
Under both instances, we observe identical low-level feedback for trajectories т. T' in sub-MDPs M (s1, j j E [2]: the feedback is Bernoulii with parameter a ((Ø'(T) - (T), 0*)).
Consider any deterministic learning algorithm. WLOG it outputs high level policy x" (st) = a1 with some set of N₁ samples of low-level feedback.
Then, it follows that its regret under l [e1, O, C*] is C", since the reward (and return since H₁ 1) of π 11.01 is O, while the reward of the optimal policy which visits M(1, .2) is C².
D.2
Hierarchical Experiment Design via REGIME 29
D.2.1 MLE Definition:
We first define the MLE expression; note that the MLE is in terms trajectories only. Define:
f(lu) (x.)=n) Σ 11 13o(0"xx)) x.)) 11 = 0}(1 a(0 x:))
(D(0)= = ((b)) (a))a)) Es(,, " J (1:-0))11)
(5)
High-level trajectories: has realized features,
H Σ o' (
Hy Σ l (T (8) (0) (
=== -f. 60 P
T; =
where (())) is the feature of the high-level trajectory under sub-policy Ni and transition (since trajectories are collected from roll-outs in the actual MDP as in (2)). On the other hand, under sub-MDP has been executed perfectly (i.e. by ataa) and so the features correspond to:
the labeler assumes that each goal-conditioned
Ha x = -==0""P((T (()))
-
Comparison of high level trajectories follows Bernoulli distribution y, a00 2;).
23

---

Low-level trajectories: has realized features,
H ( (
Ha. Σ o(5) ..7)
x/ =
Σ
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 yi = 0 2
24

---

D.2.2 Requisite Lemmas
Lemma 10 (Lemma of (29)). Let oracle p be such that with probability 6/5, the following
holds. Let d (s, a} and (s, a) be the visitation measure of policy a under P and p we have for all h [H] and II:
Σ (s. d7 (s, = Σ (s) - ds)( S hd
This applies across all sub-MDPs M(s a). Let the event that this expression hold be E Lemma 11 (Low-level MLE Bound, Lemma 2 of 29 ). With probability at least 6/5:
1100
1s; Ô(1)
Let the event that this holds for learning from sub-MDP trajectories be E\-
Lemma 12 (Lemma 3 of (2 If low-leev trajectories T/ n². p then with probability least 1 - 8/5:
|00 - 6 1ss S V2 - 8'1lss + O(Bv dloog 4n/6W)
Let the event that this holds for learning from sub-MDP trajectories be Ez.
D.2.3 Bias when using idealized-feedbade high level trajectory data in MILE
Proposition (sub-MDP REGIME guarantee of 29 For sub-MDP M(s, a), under Esd nei
C(( N₂
(o"(T"), (0 1,.
+ +0(e)
where (ō) = 0 (log()))))
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 o' having higher reward than o and upper bound comes from no-regret. Due to optimality of π², we have the lower bound as well:
C1
s (o"
(T)))
1 VN.
+ +()))
Additionally, we have that:
Lemma 13 (Lemma 6 of 29 For any sh, ah ||l 2B, 9 e Rd and ||o|| S R under ga.a ni E/:
1(0P" (Bn, (sn, ( an ()))),))) BRIe'
With this,
16 (T)), -00 (*~))001 -f'M,,,000"0 G1 +0()))++++) BRR VN:
C1 VNi
+ Cze
Now, analyze the bias of including high level trajectory data in the MLE computation: Lemma 14. Suppose there are Nr, N2 high, low-level trajectories, bias is such that, under Nea E0. E E
16|1 Σ 10" xi) "0",,;)P= 2HrT(2HH C2 VN
+ C26l))
25

---

Proof.
Σ x7)) 21)1
2
Σ (
Σ
p (1) + Σ (((t(6,a))- - Σ
O (s))
1=1 8,4ETf
5,EET$
2,0ET
6,EET
< h Σ Σ
(T)) - (T)) -
((0"(T'(s,))) - (oo (s))
S,
8,0ET
C1
22HT((HH 02
VN.
Thus,
Σ 100, xz) - (0", ,2))}= & 2H C1
|b||| =
+ C2E)VT
VNI
26

---

D.2.4 MLE Analysis
Under current-feedback, following Lemma 2 of (291, || +h S O().. Now, we consider the bias in learned reward under idealized-feeee feedback.
Proposition 6. Let IMLE arg ming (0) and ler C. ||b|]- Then with probability at least
1 8/5:
(1/
| A $00
C.
+ C + + log(1/6)
72 1
+ AB
n
where En En N.5. AI.
Proof. Define A = OALLE 0' As in 330, we have the same convexity result due to (0, r;) E [ 2LB). Suppose we let max, |>| S and maxace ||]|| 2-exp(- -exppp we have that:
B, then with
E(0^ + A) - -(00) (Ve(0))) A
And so,
{(OMLE) SE(00) = E(10 + + ((0))))))))))) - (V(())))) -((((() -(VE(0))
Thus,
~|4 [V((0") -|A|l(E+>D)
The key part bounding |V((0)) ( We have that:
-11 n1
1 Σ
v((00)
[1: 1)0((0",2z)) 1ss 0}(1 (000"xz)))
1 XT b)
where v; ((0 2 w.p 0(18" ,x;)) and -(1 ((0''((2) =z))) w.p ((8", .z)) And so, entry- wise V is such that [.] = and [V] < 1. Note that Vú are independent due to the independence of the random variables Y,
Extra term bias is defined as:
6, 1(; 10(a((00) (0', (0'),)))))) 1(y, -00000((00) (1 o((0", =(( xz)) 0100 ())
By definition, C2 such that: |b|| S C₁. As before, define M = 1.- X(E: + -XX We use the fact that ||M lop S. 1/n. Then, have that:
27

---

[V((0")) = (V+ +)² M(V +b)
= =VTMV + -V Mb +b+bb Mb Mb
3 <0 1o log(1/6) d
211V [|] + 6z Mb
(by Matrix Bernstein,
V MV v
Cd w.p. 2 5/10)
$ d + log(1/8)
1 |b|| +
C
2|| d 1og((10)) 2(C2v 2(C2v
(using that |M S 1/n)
C
0
"1
n (l0g(10000) w.p. 2 8/100)
(by Hoeffding ||
C d log(1/6)
1 0
+
vn
n
|| 2 E+N S ||(e(0))
\(>l|A113)
(E+AI)
$ ||Ve(0)) -= + 42y
This implies that with probability 2 21-8.
C. | SCHNISCA SV
+ CP log(1/8) + AB?
72
72n
Corollary 4. Let AMLLE = arg min& (f). then under Ns Edh with probability 2 8/5:
N2 + d log(1/5) AB2 PVNN
1
1
110- - -MME LS NA +XI
S C
+
N2N
No where ΣNZ Nr. Di=1 x.a...
Let the event that this holds for learning from sub-MDP trajectories be Eh. Proof. Firstly,
C1
VNn
|bb|| < 2H VN
+ +2E' N1 = 0
VNne')
N
With this, we have that:
| EN, +X7
C.
C + d log(1/0)
AB2)
N2Nr
No/Ni + VNaed ///N
No/N: + No + d + log(1/6)
+ AB2
NN
28

---

Hence by choosing À = A/NE:
N2/²
N + (Nhe)(12 + C0
|l EN, +AI S 50-
D.2.5 Relating 100- 100'-0"11s, to 10 15
Define:
1. mn + 1 (0 (Tt) - 0F P ((T)) 00Ti.P ((²))
((T)))² _ where 7. Tl, nN P. 2. En AI + (+(T)) o(T)))
3. En A Ei (0 " pd' (T - のه
pe' (T)) o= " pe (m²))²
We wish relate ||0~ nt lss.. |10 8 1":....
Lemma 15 (Lemma of (. If T:? कं. Ni, pe then with probability at least 5/5:
|0 - 1ss V2 I1 Õ(B dloo 4n/8W)
Let the event that this holds for learning from sub-MDP trajectories be E
Lemma 16. We have that under Ns, 8, n E n n n
110 00 -0 + +O (l/B/dlogg//WW) + VBnC(é, 6)
Proof. Under event E/ as trajectories sampled from P, we have that:
110 0r 15=, S /2110* 0n Is. + Vdlogg////
It remains upper bound ||0- - 1l by 110 8"11..
We have that under Mama ga.0 ng ng:
1000% (TT) ppp (T) S (((,
*(00*1 (mi) 0= ,rd (m)); 1/}l s 1(0=ti. - 8t (TL)) wi}l 20((',0)
*160="1, pee' (mi) 15 ()) w/12 < 20 3Tm1 (m²) - 2(2C(c'
Thus,
||01
N (mi) ppdd (TT) (Ti) - M=M (T²)) yo
= =(T+
K0 1 ppe (xzt) pp b1)),
= 211ul| +
$ 21aaal1 + Σ ( Ni (TT)) 0z p u) + 80()'
5 2| + SnC(e', 8)2
Plugging in v 0" 6th we have that:
29

---

100 -1.
S <22100- - 12, +V8n((é,))
< 2|16" - -8" + dlog + VBnC(é',))
30

---

D.2.6 High-level policy regret bound
Lemma 17. For any under event NN Eh ne n
(0T))((T)) - ((T), S Ha( Ci
VN + C2c)
Proof.
(0T:P(T) - (*))
Hn
,r ba (sh, anl) Vhti (g(sh: an)) - (sh, VxT (sh-1))
E
M
Hy.
E
as ~ p (sh, an)) - NN (sh, + P( * g(sh. an)) (g(sh,a))) Vn+1 (8n+1))
h=1
Ha
E
ax))
P(s + g(sh: an))H,H,Hii
h=1
Hi
Σ
B. (sh, an)) + P(s = g(sh, an Hi - r( ( (sn, an)) P(s = g(sh, ()),H,
E
h=1
Hr
E
(s0 (sh,
4=1
C1 VNi
HA
C26')
Because for any Sh, ah, (Ø(TT" (sh, ax)), 0*) ( an)), 0-) s VN.
Cr
+Ce'.
31

---

Lemma 18 (Lower bound on Reachability Probability). We have that under event Ne 8x E
P Ni + a(s, S kHA KHaHiVN, +
1
C1
O2e'
+
HH
and
pd (sh" + g(ss,))) S kHn aHNHiVN,
1
+
Ci
+
Czé' KHHHH
+ Hid
Proof. Due the regret guarantee, have that:
C1
+ C2é'
VN.
2 (0f(m) (T*) -x((x (x²)),0 ),0%)
= r((")) + kH,, Hi 11 - - -KH Hi P(s =())a))
2 0 - Hi + KH1 P( + fg(s,a))
Thus, we have that:
NN P( * a(s,,))) S 1 RHn sHAlliNN +
+ Ci
C2e'
KHAH
Additionally, we have that from Lemma 5.1:
a)) (o(s
di (o(s, P(s + g(), - p (s + g(s s Hid
Thus,
pe' ( (1 + {(),a)) <
kHn wHAH.VM + C2d
1
Ct
RH + Hie'
Define goal non-reachability probability to be: 8 = 1 +
Ca kHA H.N. HHH + Hie'.
C +
Lemma 19. Let t5 Mr (π) denote the feature expectation under high level policy m, sub-MDP policies No and MDP transitions p Under event Nr. Es.a n n we have that, for any high level policy n:
Ho P.PP) (
MM (T),0") 2H, H8H
Proof. Let Ereach denote the event that roll-out n,, Ni P is such that all high level goals reached, and similarly event Erech for roll-out 7' n,, Ni pe'
By union bound, Pr(-Ereach) Pr(]si, di, 8H, ((nia))) g(s,, a:)))) < H and similarly Pr(- Pr(-E) S HnO.
+ g(s;,a))) S Eth Pr(sn, (s..a)) +
32

---

1(0 M. (TT) 10 (T), 0-)
B ((((T), 0-) Erachh Pr Pr(erachh) E M. (()(T) (0](T)),))00 Yeachl Pr(Ereach))
+ E E ((((T)) Ereach Pr((-reach) - E M [(((T), 87) Ec Pr(-Ereachh)
B B [(((T) 0 ( Ereach Pr(Ereach) - E TOU N,,p pe/ (3) Pr(Ereach) + 2(H, (since [8 7 p(()(T), 07) Ereach] Pr( (((e-rrrchhl S
H4, Hi) and likewise the other term)
Hn
PP((Erech))
d(sh. an Bll (x (Sh, an)) Ereach]
h=1 Sh
-Pr(Erench)
d(sh, a, E[ (sn an)), 8 Eoacehll H1
hm Kh.ah
(under goal reachability, high-level state visitation measure d(s), an)) is the same)
Hn
d(sn, an) Pr((react) (s), (sn, an)), ) Ereach]
h=1 Ph
-Pr(Ereach) Eib (sn,, an)), Grachll + 21
Hi
d(sn, an) Pr(Ereacc)) (T (sn, an)), 0-) anhant))))
1=1 ShaRh
-Pr(Ereach) El(b (a (sh, 0")1) (eeee + HHH
(E ehreahh the event that g(Sh, an) reached under Ni, P)
Hn
d(sn, an) Pr(Erench) (8 (s an), 8-) an El(o (s)) 0')1 rercchll
h=1 Phiak
(Pr(Ereach)) Pr(EFeach))BB ( Ni (sh, an) E sh. aeeeccll + 2H3,1188
Hn
d(sn,an) an) (E8 (T (N an )), 0-) 18) axraahh) - Bi(o (sn, (sh,an)), 1-) (e,. + (Hro)
1= Sh.Rk
2HH,H
(since Pr(Ereacth) Pr(Ereact) [1 Hnō, 1)
To finish, we will relate the expression to K Ni ax)) az)) Ni ax)), 07)
33

---

Hh.
d(sh, an 1B(@ (T (sh, an)), El (sh, an)), (s + 3H
h= Ph
H
d(sn, and
Pr(Esh (Elo (s), an)); (1))))
h=
Pr(E Pr(E saacch BB( pi (sH, reaachll 3 H16
Pr(E arreeh.
Hn.
dish, an) Pr(Ess)onreaahh)
Pr(EEs,.n ) (T (T an))) (") (*)
1= 1 Sp
aareantll Hn (1-8- -1)HHHH + H
-Pr(E reach [[(( -Pr(E"n.asroaca
(shh (aneraaalll
(0)
Hn.
1
Msh ah)
1-8 Pr( Ex (cack (6 (o
h=1 5h
Prr(-Eg, osh El( PK (1) oon
[0 (Sn. (s))
(n), 07)1 4
(using that r-3 1511
H
1 d(sh, an) 1-8 (2(0) + BRd&)) + H,
(00)
Am
Hr
d(sn, an )2 (2H + BRd&E) + H1H
T 2)
1= Shath
2H, B + H1 C(E'5))
Pr(E ay
11 S max(1 (1 5) 1) since Pr(g (0) PrEEA reach))
sn akreachh) sn E
[1 - 8, 1].
(00)
1 (TN (sh, an))
(SN, I
BRde
and
Pr(-E aareach ) Pr(-E"
reach))) E 10,
34

---

Lemma 20 (use of the Elliptical Lemma).
(0 De (m-)-~->; M (a) 0) vNn
1
(2d + NVz 1)100- -11ss.n
Proof.
1 (x²) - " (4), 0- - 0)
S 1,0 pr (TT* x= "1 pp' (+) N, 110 - -01lEmm
1
b pp (T*) 83 Ni pe' (a)lls, =100 18r-01 -011smm
Cxd 3 1
N
N
.pa (Ti) - ~-M .m (T)))ls,-11 110 - -01EE,
(definition of n(.2)
N
Me (m(it) M (Tb)) 110 - -011..
N
(2d log(11 + No
d 1110 011smA
(Elliptical Lemma)
Theorem 4 (Main regret bound). We have that under event Na, go.a ng ng g n E and Nn > 0:
p - VR.a"/ s <O(N: + N₂ 1/11/1100 - -(1lsm))
Proof.
V=',=' - -
100T" ' P(TT)( - 10 P()),
-10" ((T')
" (T)))((')))))))))))))))))))))) ( P ((()) 8=h ((t),8))))
(first term = sub-MDD sub-optimality; second term = high-level policy sub-optimality)
C1
S Hnl
+ C2c') + ( P ((TT) Z. (*)
VN
Ci
+ C2e') + (6 pi (TT) Jt pa (7)
Hn
VNi
P((''
gzth p (m'), 1(0 ppd (f) xTth P 0*)
Ci
+ Cze') + 2C((',)) + 10 Mi pr (T*) x pr pr (+) r - 0) + ( pr (x*) - xr -r (f), 0)
Hnl
VN
(expand out the second term
C1 S Hnl VN
pr ( - - pp (#), 0" - 8)
+ C2c') 20((',)) + ()),,,)++00
(definition of t: (6=*1 p=' (I*)
M (4). < 0)
C1 VN:
1
(2dlog(1 + Nn No 1110100 0 01|s,
Hnl
+ C2d' + 2)((())) + NN
(use of Elliptical lemma)
35

---

Data Tradeoff: Using the above bound, we can derive the following rates:
Under feeallieed-feddbace and requiring both high- and low-level feedback, the overall rate comes out to O(N, 1/4 +
Nn 1/2).
This is because ΣN, O
N + +1).
Thus, the dominating factor is the bias of the
NP74
reward learning.
Under current-feedbace and requiring both high- and low-level feedback, the overall rate comes out O(N, 1/2 + N/= 1/2))
This because ||0" 0llsx, 0(1)
Under only low-level feedback (due sufficiency in coverage), the overall rate comes to ONN,1/2)
We have that:
( ,pe (x²) " (t), 0r 8)
S 11 (TT) 0 pp' ( (a) 110 -111.
( -
1
1 (mt) pp' (xb) 110 -01
(0)
Nn
1
No (2d log(1
d >)10000 01lsm
VNi
(o): since low-level policy feature expectation is a superset of high-level policy expecta-
tion, follows that by choice of low-level policies チf. Ti: | [ (m)) of" (mz) 1l, 2
% pe (TT) - pe (+) (#)
Moreover, since low-level feedback is always unbiased, 1|0 - Ōll 01). Thus, the
overall rate comes out O(N, 1/2).
Remark 4 (High Probability Guarantee). For completeness, we show that the theorem statement holds with probability at least
Pr(
8 63.0 n
ng n n
8,0
2 1 - Pr(
(0.0) Pr(-E)) Pr(- - Pr(-E() Pr(-E))
8,0
- 8/5 - 8/5 8/5 8/5 0 8/5
D.2.7 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,
36

---

C1 +c2))+20((,, + VNa
(2dlog(1 1 + NA 11100 - -01lSNo
Hh(
VN
d
C1
Hn(
C26) (0((()) N₂ 2/ (2110- -NM.lENN
+O(Bydlog Na/oW) + C8N,
VNi
+ C26') (8d + 2)C(((,8) + N₂ 1/2 (N11/2
Hhl VNi
C1
+ +NNnc)118
+ + +O' dlog No/oW)
|N/1/4
(HAC)) 1/2 + 2d,, 1/4 C2ttne + de 9dC((' + 2dC N 1/2 =HHCO)N 1/2 + 2dN, - -C2Hne' + 1/2 + 9d (2H1, + HH0H + 2dC N & (2d + HACD)N (C2Hn + 18d BR) + 72dH H1o + 2dC Nr 1/2 1/2
1/2
Setting the upper bound to be below e, each term to be below e/4, we obtain the following bounds:
Ni 2 O((tH....))
Nr (
K 2 0 1
72dH H1ō s/4 + < ( I
Recall d H aH, Niv
Oge' KHH Hi
HiC'.
This implies that x: 2 O dHj
and é S 0 50 न.
e' S Omin( म. TH,
Finally, we also require that (C2Hn + 18d H& <//4 6 50 we need that e' s O(min( u. TH.BA)
Thus,
37

---

E
Statistical Efficiency of HRL
An useful sanity check for hierarchical RL algorithms is that achieves improved statisical sample complexity in settings with repeated sub-MDP structure [25] As in [25], we examine if Algorithm | also improves upon algorithms that do not leverage hierarchical structure. We make this comparison with vanilla UCB-VI VI under the same isomophism assumption.
Corollary 5. Setting As.a to be the standard UCB-VI algorithm with U BRR (RNN.
O(H, all (5,a)), we have the following bound:
Σ
UB(RNK.HLee.. + 11 H¹ / (yK.Ha(s.o)
s,8EC(S,A)
EO(H) max 1S |
|C(S, (H), + H Hiy CCSS, H)
Comparison with vanilla UCB-VI: Standard application of UCB-VI yields the following rate: Ó(HH, /() Hier-UCB-VI compares favorably to vanilla UCB-VI, if max 1S "l A << [S]. Or in words, there is lot of repeated/identical sub-MDPs and sub-MDPs have small state space size.
38

---

NeurIPS paper checklist
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatiio right after your answer (even for NA).
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper contains everything that is covered in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
This is covered in the "Discussions" section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well sell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
39

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All the proofs for results are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: This is theory paper that has experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
40

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is theory paper that does not involve code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc.
cotpsiiynnoooyyl for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttp:/cccppcccguuiiieeeeeec htths///uiidds/oeeeeuuubmiii wtwp:d//e/ooeetuaiiiiiioooo
assionPolcyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
This is theory paper that has no experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is theory paper that has experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theory paper that has no experiments section.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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 (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
ines?
Answer: [Yes]
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.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. 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 positive/negative social impact.
42

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
43

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

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.
45


Reviews:
[{"review_id": "ugqV5T55Zw", "reviewer": "Reviewer_2zMJ", "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.", "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": "The authors discuss the limitations of the work. No major concerns.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a combination of very important topics: theoretical understanding of hierarchical reinforcement learning and the outcomes of incorporating human feedback. I believe that the field still lacks a strong theoretical understanding of HRL, and this paper provides a step in that direction.\n\nThe paper is generally very well written and easy to follow. The authors clearly state the setting they are dealing with, provide a useful running example, and intuitive discussions about their theoretical results.", "weaknesses": "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. \n\nWhen 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review, reviewer 2zMJ! It has definitely helped to improve our paper and its presentation.\n\n```\nThe 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. \n\nHowever, the authors do recognize the limitation of this assumption and propose, on a high-level, how this could be dealt with in future work.\n```\n\nThanks for this question, we agree that our learned policy is only as good as the goal function chosen (L224-5), which is key to the success of GC-HRL:\n\n1. As we write on L29-32, there are already many settings of interest where we *have* prior knowledge of a good hierarchy/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.\nIn such settings, the algorithms we develop can already help to scale up bounded feedback and enable scalable oversight.\n2. Indeed, this approach of explicitly encoding prior knowledge in the learning algorithm is common in both GC-HRL literature (e.g. we know apriori mazes consist of rooms [22]) and scalable oversight literature (e.g. books consist of chapters [27]).\n3. Outside of such settings, we agree it is an open problem to learn apt hierarchical decompositions/goals (L329-30). It is an exciting direction that could realize end-to-end scalable oversight [15].\n\n\n```\nWhen 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…There were a few variables/subscripts used throughout the paper that, I believe, were not formally introduced…Could the authors please add clarifications about these variables?\n```\n\nThank you for your careful reading, we will definitely clarify these notations as you suggest! We have also centralized the notation in Table 1 of the appendix, which we will also add to and link in the main paper for added clarity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5eLTPpgSxU", "reviewer": "Reviewer_Hzkp", "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.", "questions": "* Does the analysis for the linear setting generalize to the non-linear / function approximation setting?", "limitations": "Yes they are discussed in Section 5.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The problem is significant and of high importance to the community.\n* The theoretical analysis and sub-MDP reward design for Hierarchical-UCB-VI appears novel. Furthermore, the extension to ordinal (preferences) feedback appears novel, specifically in the proposed Hierarchical-REGIME algorithm and analysis.", "weaknesses": "* Minor: It would be a nice addition to the paper to empirically demonstrate Algorithm 1 &2 as well.\n* 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.\n\nTypos:\n\n* L61: “policies aims to” -> “policies aim to”\n* L183: “approach is avoid” -> “approach is to avoid”\n* L218: “identifical” -> “identical”\n* L250: “what can we assume the” -> “what can we assume is the”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, reviewer Hzkp! It has definitely helped to improve our paper and its presentation.\n\n```\nPaper had quite a few typo’s. I would encourage the authors to use an automated tool to check for spelling / grammar mistakes.\n```\n\nThank you for your careful reading! We will be sure to correct these.\n\n```\nDoes the analysis for the linear setting generalize to the non-linear / function approximation setting?\n```\n\nThanks for this question! Our paper invokes REGIME as a subroutine, taking its guarantees as a given. REGIME is designed with the assumption of linear reward, and we believe more work is required to extend it to the non-linear setting. \n\nWith that said, linearity is an often used assumption in offline RLHF literature [29,30]. The justification for it is that we often do not have to learn features $\\phi$. Such features may already be available from (self-supervised) pre-training. Thus, for reward modeling, it is common to assume a linear model on top of non-linear features $\\phi$ to do reward modeling.\n\nAlso, we note that the linearity assumption pertains to the specifics of the subroutine invoked (in this case REGIME). The insight from our analysis of favoring low-level learning given sufficient coverage applies regardless.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9YdKpBS7fx", "reviewer": "Reviewer_poPw", "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.", "questions": "Can the work on regret analysis of GCHRL be separated from the analysis of ordinal rewards?\n\nWhat is the relationship between the analysis of these two?", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The method provides clear and applicable analysis of hierarchical goal-conditioned RL, even outside of the context of feedback.\n\nThe derivation of the regret due to goal-conditioned HRL is informative and interesting.\n\nThe proposed insight of ensuring hierarchical consistency is meaningful for many applications of GCHRL.", "weaknesses": "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.\n\nThe 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. \n\nThe 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. \n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review, reviewer poPw! These are great questions, which have definitely helped to improve our paper and its presentation.\n\n```\nAlgorithm 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.\n\nThe 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.\n```\n\nThank you for this question! To answer your question, the regret is *only* a function of low-level error in the cardinal case. Hence, one of our main results is that GC-HRL reduces to multi-task, sub-MDP regret minimization. In our proof sketch, we provided an outline of the errors terms that contribute to regret. More specifically:\n\n1. $\\rho_h^k$: regret due to low level policy incurring sub-optimal returns.\n2. $\\gamma_h^k$ and $\\sigma_h^k$: regret due to sub-optimal low-level policy not reaching the goal state.\n\nThe product of horizons $H_h H_l$ shows up in the low-level regret when low-level policies miss the goal. Indeed, when the goal state is not reached, it is unclear which state the agent would be in. Thus, the maximal difference between any two returns, $H_h H_l$, is used as an upper bound on the resultant regret.\n\n\n```\nThe 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.\n```\n\nThank you for this nice feedback! Our current algorithm includes the full details of REGIME. We agree with you that a more modular description of Algorithm 2 would improve the presentation. We will be sure to include this in our next revision. Here it is with reference to line numbers:\n\n> 1. Invoke one copy of REGIME *across* all sub-MDPs with shared exploration (L2-4) and learned reward (L6).\n> 2. Compute near-optimal, sub-MDP policies $\\pi^{N_l}_{s,a}$ that the high level policy will invoke (L7). \n> 3. Invoke one copy of REGIME for the high-level MDP, where the feature expectation of each sub-MDP is computed according to $\\pi^{N_l}_{s,a}$ and $P^{\\epsilon’}$.\n\nWe arrived at Algorithm 2 by improving upon the naive application of REGIME to the hierarchical setting, with the improvements as describe on L295-307.\n\nFinally, as for the role of the simulator, the REGIME algorithm assumes access to a simulator $P^{\\epsilon’}$ to compute policy feature expectations. We do the same when invoking REGIME, denoting the feature expectation with notation $\\phi^{P^{\\epsilon’}}(\\pi)$ in our algorithm.\n\n\n```\nIn 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.\n```\n\nTo clarify, our work does shed some light on the nature of scalable feedback. We show that one way to generate scalable feedback is by leveraging hierarchical structure (L27-29). Our work analyzes how to scale feedback, and develops HRL algorithms that efficiently learn with provable guarantees. \n\nA general point that our paper makes is that besides the benefits of easier credit assignment and exploration (as listed in [25]), HRL has the added benefit of allowing for scalable oversight.\n\nCertainly, we agree that our work does not provide a full characterization of “the nature of scalable feedback”, as you write. We study one natural setting (hence a “case-study” as in our title), the hierarchical setting, where we show we can provably scale up bounded feedback. \n\nThis may not be the only setting that allows for scalable feedback. And discovering other types of scalable feedback and analyzing their nature is verily unexplored (and exciting) territory.\n\n\n\n```\nCan the work on regret analysis of GCHRL be separated from the analysis of ordinal rewards?\n\nWhat is the relationship between the analysis of these two?\n```\n\nThanks for this question! The key difference between the two analyses is that in the cardinal case, the total regret decomposes into the sum of sub-MDP regret (Theorem 1).  In the ordinal case, the total regret decomposes into both high-level MDP regret and sub-MDP regret. As we show in Proposition 1, this is because we need to not only learn from comparison which policies are best within sub-MDPs (incurring low-level regret), but also which sub-MDPs yield the highest returns across sub-MDPs (incurring high-level regret). This is made explicit starting from the third line of the proof of Theorem 4 (L645 in the appendix), and results in a different type of analysis.\n\nThe key commonality underlying the two analyses is that an apt sub-MDP reward design is needed to incentivize goal-reaching *in balance* with maximizing the return of the sub-MDP (L172-175). This we believe is one of our main contributions, in finding the “right” reward setting and weighting to balance the two objectives. It is also what allows us to derive a new form of bonus that trades off between the two (L176-8), such that we can bound the resultant cumulative regret w.r.t. the global MDP.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KIQ1gM9wAS", "reviewer": "Reviewer_z273", "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: \n - 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$\n - 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.\n\nIn 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).\n\nIn 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.", "questions": "Questions:\n - 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?\n - 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}$?\n - 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). \n - What are the policy classes $\\Pi^h$ and $\\Pi_{s,a}$? They appear to be assumed in the definitions, but are not introduced otherwise.\n - I do not know the REGIME algorithm, but I could not find it in the provided reference?\n - Does the approach discussed in the paper extend to more than two levels of hierarchy?\n - What is $S_h$ in line 217/218?\n - Algorithm 2, line 12 - shouldn't it say length H^h trajectories?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper studies an important problem of scalable oversight, and approaches it from a perspective that could potentially be used as a basis for a practical implementation, both in ordinal and cardinal setup, at least if the problems mentioned in Weaknesses are resolved. The fundamental idea of doing a hierarchical UCB-VI is quite simple, but computing the right form of the bonus, and the insight to operate in the goal-conditioned setup (leading to a particular form of low-level reward functions and simplifying the theory quite a lot) seem novel and non-trivial. The paper looks to be technically sound, and although I did not carefully check very technical proofs of various inequalities, which span 30 pages in the appendix, very detailed notes make it possible to spot-check it without issues.", "weaknesses": "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.\n\nIn 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.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review, reviewer z273! These are thoughtful questions and we address the main concerns below due to the space limit. We will be sure to clarify the notation (e.g. $\\Pi^h$) as you suggest.\n\n```\n…The task studied is then to find a high-level policy and a set of low-level policies…This is done by employing a two-level UCB-VI procedure…\n```\n\nThanks for the thorough summary! Just to clarify, H-UCB-VI does not have to use UCB-VI as a subroutine. Any no-regret subroutine will do (L177). For instance, if sub-MDPs are linear, one can use LSVI. If sub-MDPs are linear and share structure, one can use more specialized algorithms like [11] for better guarantees (L220-2).\n\n```\nMy 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. This means that the transition probabilities and rewards must be known for the whole MDP… 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.\n```\n\nThanks for this question:\n\n1. Firstly, the assumption from [25] is that we know which sub-MDPs share the same transitions and belong to the same cluster. It does not mean we know the transitions of the MDPs in the clusters, as this would indeed trivialize the problem (and the results of [25]).\n2. Next, the concern is that the paper improves upon UCB-VI when there are many isomorphic sub-MDPs. Our goal in providing this corollary (of our main result) is simply to emulate the analysis of [25], which makes this assumption to show the statistical efficiency of HRL. We do not claim that this assumption is widely applicable. Rather, this corollary serves a “sanity check” that our hierarchical algorithm *is* more efficient in a setting where it should be (L211-213).\n3. Our main result in this section is that HRL reduces to multi-task, sub-MDP regret minimization. This result allows one to flexibly leverage shared structure, beyond the cluster assumption, to improve the regret. Please see our answer above.\n\nIf it improves the presentation of the paper, we can move the corollary to the appendix and not mention the clusters to avoid confusion, as this corollary is not central to the paper.\n\n```\n…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.)\n```\n\nYes, we can definitely provide more examples to aid understanding! A canonical example in HRL is the maze (e.g. [22]). A maze consists of rooms with doors. The goal is to get to the exit in as few steps as possible.\n\n1. For the global MDP, $S = S^h \\times 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).\n2. 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.\n3. Low-level MDP: has state space $S^l_{s,a} \\subset S$ and the action set $A$ is the same moving (U, D, L, R, Stay).\n \n\n```\nThe definition of the MDP in the introduction does not contain a reference to high-level actions. How do they fit into the definition, formally?\n```\n\nThe high-level action $A_h$ is usually set based on prior knowledge. We describe what it is in the essay example (L63-5). $A_h$ does not have to be related to $A$ in the global MDP definition. For example in the maze case, moving to the N,S,E,W door is a wholly different action set from moving in the U,D,L,R direction.\n\n```\nWhy 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}$?\n```\n\nThe high level action is needed to determine the goal state of the sub-MDP, which defines the sub-MDP reward. The action set is defined to be $A$ in sub-MDPs, as is commonly assumed in GC-HRL literature. An action cannot lead to a state outside of $S^l_{s,a}$, because by definition, $S^l_{s,a}$ is the set of all reachable states (L60).\n\n```\nIn what way do results depend on the goal function? Can it be quantified?…How would goal functions be derived in a realistic setup?\n```\n\nThanks for this question, we agree that our learned policy is only as good as the goal function chosen (L224-5), which is key to the success of GC-HRL:\n\n1. As we write on L29-32, there are already many settings of interest where we *have* prior knowledge of a good hierarchy/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.\nIn such settings, the algorithms we develop can already help to scale up bounded feedback and enable scalable oversight.\n2. Indeed, this approach of explicitly encoding prior knowledge in the learning algorithm is common in both GC-HRL literature (e.g. we know apriori mazes consist of rooms [22]) and scalable oversight literature (e.g. books consist of chapters [27]).\n3. Outside of such settings, we agree it is an open problem to learn apt hierarchical decompositions/goals (L329-30). It is an exciting direction that could realize end-to-end scalable oversight [15].\n\n```\nDoes the approach discussed in the paper extend to more than two levels of hierarchy?\n```\n\nOur algorithm is applicable to any number of levels of hierarchy due to the reduction of HRL to multi-task, sub-MDP regret minimization. This allows for the case when each sub-MDP is hierarchical as well, and one can invoke H-UCB-VI calling H-UCB-VI as the subroutine.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)