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

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.

…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…

Thanks 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).

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

Thanks for this question:

1. 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]).
2. 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).
3. 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.

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

…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.)

Yes, 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.

1. 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).
2. 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.
3. 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).

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?

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

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}$?

The 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).

In what way do results depend on the goal function? Can it be quantified?…How would goal functions be derived in a realistic setup?

Thanks 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:

1. 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. In such settings, the algorithms we develop can already help to scale up bounded feedback and enable scalable oversight.
2. 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]).
3. 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].

Does the approach discussed in the paper extend to more than two levels of hierarchy?

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

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

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

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

Thanks for continuing to engage with us! We are happy to go over this, and will be sure to correct the typo as you suggest, thanks.

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

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

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

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

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

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

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

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

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

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

Again, thank you for your time and please let us know if there are any other questions!

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

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

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

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.

Algorithm 1 is somewhat difficult to follow. In particular, while the components make sense, the core insight of the bounds on the lower-level goals is difficult to locate.

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

Thank 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:

1. $\rho_h^k$: regret due to low level policy incurring sub-optimal returns.
2. $\gamma_h^k$ and $\sigma_h^k$: regret due to sub-optimal low-level policy not reaching the goal state.

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

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

Thank 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:

1. Invoke one copy of REGIME across all sub-MDPs with shared exploration (L2-4) and learned reward (L6).
2. Compute near-optimal, sub-MDP policies $\pi^{N_l}_{s,a}$ that the high level policy will invoke (L7).
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’}$.

We arrived at Algorithm 2 by improving upon the naive application of REGIME to the hierarchical setting, with the improvements as describe on L295-307.

Finally, 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.

In many ways this seems less to be a work about the nature of scalable feedback, and simply on the nature of hierarchical RL in providing regret bounds. This subject is of interest regardless but calls to question the framing of this work.

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

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

Certainly, 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.

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

Can the work on regret analysis of GCHRL be separated from the analysis of ordinal rewards?

What is the relationship between the analysis of these two?

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

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

Thank you for your review, reviewer Hzkp! It has definitely helped to improve our paper and its presentation.

Paper had quite a few typo’s. I would encourage the authors to use an automated tool to check for spelling / grammar mistakes.

Thank you for your careful reading! We will be sure to correct these.

Does the analysis for the linear setting generalize to the non-linear / function approximation setting?

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

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

Also, 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.

Thank you very much for your detailed review, reviewer 2zMJ! It has definitely helped to improve our paper and its presentation.

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.

Thanks 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:

1. 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. In such settings, the algorithms we develop can already help to scale up bounded feedback and enable scalable oversight.
2. 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]).
3. 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].

When discussing the bounds related to the second algorithm (Section 4), it was necessary to introduce several constants, but they were not discussed in more detail, providing, for example, intuitions on the magnitude of such constants. Without it, it is more challenging to understand the significance of the bounds…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?

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