Contextual Bilevel Reinforcement Learning for Incentive Alignment

We thank the reviewer for their helpful comments.

Q1: Entropy Entropy regularization allows us to compute the hypergradient explicitly without resorting to implicit differentiation. Without the entropy term, the lower level admits multiple solutions. The problem thus becomes ill-posed as one needs to decide which optimal policy to use in the upper-level objective and our method is not directly applicable.

However, with regularization, our problem is still harder than classical stochastic bilevel optimization with a strongly convex lower level. Moreover, important RL applications use regularization. For example, recent work has framed RL with human feedback (RLHF) as a BO-CMDP with lower-level entropy regularization [Chakraborty et al., 2024]. We will include this example in the next version. Additionally, prior work on bilevel RL also considered lower-level regularization. In fact, [12, 39] have shown that entropy-regularized RL approximates the unregularized problem as $\lambda \rightarrow 0$ by bounding the gap between the regularized and unregularized problems in both the upper and lower-level objectives.

Concerning meta-RL; in Sec. 2.2 we present a formulation with KL divergence instead of entropy regularization. The optimal policy in this case is also a softmax of the form $\pi^*_{x,\xi}(s;a)\propto \exp(Q^*_{\lambda,x,\xi}(s,a)/\lambda+\log(\tilde{\pi}(s,a)))$, with $\tilde{\pi}$ being the target policy [Vieillard et al., 2020]. Therefore, our analysis can extend to this setting. We will clarify this in the next version.

Q2: Experiments Thank you for the nice suggestions. The current experiment already covers the important economic application of Principal-Agent reward shaping, as motivated in Sec 2. We will clarify this connection in the final version. We would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence of HPGD, providing the first upper bound on the complexity of stochastic bilevel RL. For comparison to prior works and their complexities, see Table 1 in the attached PDF. It illustrates that our setting is more general and the randomized algorithm more practical.

Including more experiments would definitely be interesting. While Meta-RL, RLHF, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth a more thorough investigation, which we plan to address in future work.

Q3: Prop. 9 On a high level, the proof of Prop. 9 works similar to [30], as both papers use multi-level Monte Carlo (MLMC). However, on a more detailed level, there are several unique challenges in BO-CMDP, not covered in [30].

The first challenge (cf. Sec. 3.4) is that in [30] samples generated to estimate the hypergradient are independent from the lower-level decision variable. This is crucial to control the variance. When calculating their respective estimates $\frac{d}{dx}F_{t_{k+1}}$ and $\frac{d}{dx}F_{t_k}$, they can sample once and use the same data for both hypergradient estimates, such that the variance of $\frac{d}{dx}F_{t_1}+p_{{k}}^{-1}\left[\frac{d}{dx}F_{t_{{k}+1}}-\frac{d}{dx}F_{t_{{k}}}\right]$ is easy to bound. In our case (cf. Alg. 1), the hypergradient estimate depends on an action $a$ and a trajectory following $a$, both generated by the lower-level policy. Thus, the data used to estimate hypergradient depends on the lower-level decision and one cannot use one trajectory to estimate both $\frac{d}{dx}F_{t_{{k}}}$ and $\frac{d}{dx}F_{t_{{k}+1}}$. On the other hand, sampling different trajectories, according to $\pi_{t_k}$ and $\pi_{t_{k+1}}$ would significantly increases variance.

The second challenge is that the estimator of the advantage derivative $\widehat{ \partial_x A^{\pi^{t_k}}}(s,a)$, computed in Alg. 2 has itself a high variance. This issue does not arise in [30], as they do not consider RL in the lower level.

To address the first challenge, we can use importance sampling, i.e. sampling the action $a$ from $\pi_{t_{k+1}}$ for both estimators with an additional factor $\frac{\pi^{t_k}(a;s)}{\pi^{t_{k+1}}(a;s)}$ for the second one.

To address the second challenge, we can compute $\widehat{ \partial_x A^{\pi^{t_k}}}(s,a)$ by averaging over $2^k$ trajectories to control the noise.

By addressing these two challenges as described, we obtain a desired variance bound of $\mathcal{O}(K)$, which further strengthens Proposition 9. In the final version, we will clarify the challenges and the technical contributions we make in overcoming them.

To conclude, while the high-level proof ideas of Prop. 9 follows [30], extending their results to the class of BO-CMDP is important and non-trivial, as the latter poses unique challenges not addressed in previous works.

Q4: Lower-level Access To clarify, BO-CMDP is a broad class of problems where the upper level can influence some (but necessarily all) of the lower-level MDP's rewards, transitions and initial distribution. Contrary to previous works, we do not allow full access/control over how the lower-level problem is solved. The only exception is Sec. 3.4, where we discuss how to leverage full access to accelerate HPGD.

Our experiments study reward shaping, which is an important instance of BO-CMDP. While conducting experiments in other settings is interesting, we leave them for future investigation (see our answer to Q2). We hope this answers the question. Otherwise, please clarify what is meant by "access to lower-level components".

Final Remarks We hope our clarifications and proposed changes address the reviewer's questions, in which case, we greatly appreciate it if you could consider raising the score appropriately.

New References

Chakraborty et al., 2024. PARL: A unified framework for policy alignment in reinforcement learning from human feedback.

Vieillard et al., 2020. Leverage the average: an analysis of kl regularization in reinforcement learning.

We thank the reviewer for taking the time to evaluate our work and appreciate their comments.

For Assumption 3.1, we will clarify that the statement is with respect to the infinity norm. We will also add the assumption on the stepsize from [30] and fix the typo in line 551, where the extra 2 is not needed, as well as all other typos pointed out. Note that the results remain unchanged. We greatly appreciate your help to present the paper in its best possible form. In the attached one-page PDF, we add a summary table comparing the differences between our work and prior works that only consider deterministic updates without context information.

If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify. If you have no further concerns, we would appreciate it if you could consider raising the score as you see appropriate.

We thank the reviewer for their thoughtful evaluation and valuable comments.

Experiments. Thank you for the nice suggestions. The current experiment already covers an important economic application of Principal-Agent reward shaping, as initially motivated. We will clarify this connection in the final version of the paper. In addition, we would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence for HPGD, providing the first upper bound on the complexity of bilevel RL in a stochastic setting. For comparison to prior works and their complexities, we add a summary table in the attached PDF. It illustrates that our setting is more general and our randomized algorithm more practical.

Including more experiments would definitely be interesting. While Meta-RL, Reinforcement Learning with Human Feedback, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth more thorough investigation, which we plan to address in future work.

Naming. We really appreciate your suggestion to rename the problem setting. We agree that both "BO" and "CMDP" are overloaded terminology with “Bayesian Optimisation” and “Constrained-MDP”, respectively. We will consider renaming the problem setting.

We sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.

We thank the reviewer for taking the time to evaluate our work and appreciate their comments.

Experiments. Thank you for the nice suggestions. The current experiment already covers an important economic application of Principal-Agent reward shaping, as initially motivated. We will clarify this connection in the final version of the paper. In addition, we would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence for HPGD, providing the first upper bound on the complexity of bilevel RL in a stochastic setting.

Including more experiments would definitely be interesting. While Meta-RL, Reinforcement Learning with Human Feedback, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth more thorough investigation, which we plan to address in future work.

Complexity comparison. We followed your suggestion of providing a Table of comparison with prior works to highlight our contribution. It can be found in the attached PDF and will be included in the final version. The related works, which we compare to are listed below. Note that two of them were published only recently and were thus not yet included in our submission.

• [Chakraborty et al., 2024] Chakraborty, S., Bedi, A., Koppel, A., Wang, H., Manocha, D., Wang, M., and Huang, F. (2024). PARL: A unified framework for policy alignment in reinforcement learning from human feedback. In The Twelfth International Conference on Learning Representations.

• [Shen et al., 2024] Shen, H., Yang, Z., and Chen, T. (2024). Principled penalty- based methods for bilevel reinforcement learning and rlhf. arXiv preprint arXiv:2402.06886.

• [Chen et al., 2022] Chen, S., Yang, D., Li, J., Wang, S., Yang, Z., and Wang, Z. (2022). Adaptive model design for markov decision process. In International Conference on Machine Learning, pages 3679–3700. PMLR.

The table emphasizes that in our work we consider stochasticity in the hypergradient estimates, at the upper level (via the context), and at the lower level when using Q-learning. None of the three factors has been considered in previous work. Note that these three points are essential to design a scalable and practically relevant algorithm. Furthermore, we emphasize that if we do not have a stochastic hypergradient estimate, i.e. the variance of our estimator is zero, the last term $\alpha$ vanishes in our Theorem 3. This improves the convergence rate of HPGD to $\mathcal{O}(1/T)$, which translates to $\mathcal{O}(\varepsilon^{-2})$ complexity in the upper level in Table 1 and our analysis thus exactly recovers the deterministic rates of previous works. Theorem 3 therefore both subsumes and significantly extends the previous results in the literature.

We hope that our additional comparison table provides valuable insights for the reviewer, in which case, we would appreciate if you could consider raising the scores appropriately.