PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback
Authors: Souradip Chakraborty
Amrit Bedi
Alec Koppel
Huazheng Wang
Dinesh Manocha
Mengdi Wang
Furong Huang
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning
Policy optimization
Policy alignment
Preference based RL
RLHF
Primary area: reinforcement learning
TL;DR: Aligning agent policy with utility and human preferences

Abstract: We present a novel unified bilevel optimization-based framework, \textsf{PARL}, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning using utility or preference-based feedback. We identify a major gap within current algorithmic designs for solving policy alignment due to a lack of precise characterization of the dependence of the alignment objective on the data generated by policy trajectories. This shortfall contributes to the sub-optimal performance observed in contemporary algorithms. Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design)  by the lower optimal variable (optimal policy for the designed reward). Interestingly, from an optimization perspective, our formulation leads to a new class of stochastic bilevel problems where the stochasticity at the upper objective depends upon the lower-level variable. {True to our best knowledge, this work presents the first formulation of the RLHF as a bilevel optimization problem which generalizes the existing RLHF formulations and addresses the existing distribution shift issues in RLHF formulations.} To demonstrate the efficacy of our formulation in resolving alignment issues in RL, we devised an algorithm named \textsf{A-PARL} to solve PARL problem, establishing sample complexity bounds of order $\mathcal{O}(1/T)$. Our empirical results substantiate that the proposed \textsf{PARL} can address the alignment concerns in RL by showing significant improvements (up to 63\% in terms of required samples) for policy alignment in large-scale environments of the Deepmind control suite and Meta world tasks.

Published as a conference paper at ICLR 2024
PARL: A UNIFIED FRAMEWORK FOR POLICY ALIGNMENT IN REINFORCEMENT LEARNING FROM HUMAN FEEDBACK
Souradip Chakraborty', Amrit Singh Bedi², Alec Koppel Huazheng Wang',
Dinesh Manocha', ,Megdi Wang". Furong Huang' Uniiersityy of Maryland, College Park, University of Central Florida, J.P. Morgan Al Research, 'Oregon State University.s Princeton University (s ccchkra3 @mmd. edu
ABSTRACT
We present a novel unified bilevel optimization- based framework, PARL, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning using utility or preference-basee feedback. We identify a major gap within current algorithmic designs for solving policy alignment due lack of precise characterization of the dependence of the alignment objective on the data generated by policy trajectories. This shortfall contributes to the sub-optimal performance observed in contemporary algorithms. Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design) by the lower optimal variable (optimal policy for the designed reward). Interestingly, from an optimization perspective, our formulation leads to new class of stochastic bilevel problems where the stochasticity at the upper objective depends upon the lower-level variable. True to our best knowledge, this work presents the first formulation of the RLHF as bilevel optimization problem which generalizes the existing RLHF formulations and addresses the existing distribution shift issues in RLHF formulations. To demonstrate the efficacy of our formulation in resolving alignment issues in RL, we devised an algorithm named A-PARL to solve PARL problem, establishing sample complexity bounds of order O(/TT). Our empirical results substantiate that the proposed PARL can address the alignment concerns in RL by showing significant improvements (up to 63% in terms of required samples) for policy alignment in large-scale environments of the Deepmind control suite and Meta world tasks.
INTRODUCTION
The increasing complexity and widespread use of artificial agents highlight the critical need to ensure that their behavior aligns well (Al alignment) with the broader utilities such as human preferences, social welfare, and economic impacts (Frye & Feige, 2019; Butlin, 2021; Liu al., 2022). In this work, we study the alignment problem in the context of reinforcement learning (RL), because a policy trained on misspecified reward functions could lead to catastrophic failures (Ngo et al., 2022: Casper et al., 2023). For instance, an RL agent trained for autonomous driving could focus on reaching its destination as quickly as possible, neglecting safety constraints (misalignment). This could lead to catastrophic failures, such as causing high-speed accidents. The question of alignment in RL may be decomposed into two parts: (i) How can we efficiently align the behavior (policy) of RL agents with the broader utilities or preferences? (ii) How to reliably evaluate if the current RL policy is well aligned or not? Addressing the first question is crucial because it serves as a preventive measure, ensuring that the RL agent operates within desired boundaries from the outset. The second question equally vital as it acts as a diagnostic tool, enabling real-time or retrospective assessment of the RL agent's behavior which could help identify early signs of misalignment avoid severe consequences.

---

Published as a conference paper at ICLR 2024
UL
Walker
Doar Open
X
Gap
Feedback for Aligmeent
Gap
Lebes
2000
Choda
Samples
Eniow Sips
(a)
(b)
Figure 1: (a) This figure shows the proposed PARL framework for policy alignment in reinforcement learning. The standard RL is at the lower level (LL.), and the alignment objective is at the upper level (UL). (b) This figure shows the performance gap of the SOTA approach due to policy misalignment. The blue curve should be as close as possible to the red dotted line of oracle.
In this work, we propose novel unified bilevel framework called PARL, capturing the challenge of policy alignment in reinforcement learning using utility or human preference-based feedback. Our PARL framework shown in Figure (()) consists of upper level (UL) and lower level (LL.). The lower level performs the policy alignment step for given parametrized reward function (addressing question (i)), and the upper level evaluates the optimal lower-level policy check possible alignment (addressing the question (ii)). A bilevel approach is crucial because of the dependence of the alignment objective on the data generated by the optimal policy of the RL agent.
There are existing approaches such as PEBBLE (Lee et al., 2021) and SURF (Park et al., 2022), which have proposed a heuristic iterative procedure for possible policy alignment in RL but do not focus on the entanglement between the alignment objective and the trajectory collecting policy, This gap (our formulation resolved this) in existing stateoof-the-an (SOTA) approaches results in a misaligned objective for alignment evaluation and sub-optimal performance in terms of alignment. We highlight the performance gap of the SOTA approach in Figure 1(b). This gap exists because, without considering the correct evaluation objective at the upper level, existing alignment methods set the initial trajectory for the agent, but they do not offer ongoing assurance of the agent's 's behavior. Policies can drift or become misaligned due various factors such as data distribution shifts, model updates, or environmental changes (which we observe in (b)). Our proposed formulation provides a rigorous mathematical formulation to address questions (i) and (ii) and improves the performance to achieve policy alignment in practice. We summarize our contributions as follows.
we formulate the RL agent policy alignment as a bilevel optimization problem where the upper-level centers on reward design through policy evaluation over the horizon, and the lower level pertains to policy alignment with the designed reward via policy optimization.
Bilevel formulation for policy alignment in RL:
Correct evaluation objective for policy alignment in RL: We highlight the dependence of data distribution of the alignment objective on the RL agent policy, which is missing from the prior research. This provides reliable objective to evaluate the performance the current policy of the RI. agent at the upper level.
Analysis of new class of stochastic bilevel problems: Interestingly, our bilevel problem does not fall under the class of standard stochastic bilevel optimization problems in the literature (Chen et al., 2022; Kwon et al., 2023; Li al., 20226; Ji al., 2021; Cao et al., 2023; Akhtar et al., 2022: Ghadimi & Wang, 2018h 8b) with the only exception being (Lu, 2023), which also studies coupled decision dependent bilevel optimization problem but not in the context of RL. The unique feature of our problem is to explicitly consider the dependence of data collection at the upper level on the optimal policy parameter at the lower level. We also propose a novel A- A-PARL algorithm to solve the bilevel problem and derive precise sample complexity bounds of O(1/T), where T is the number of episodes.
Empricial evidence of improved policy alignment. We evaluate the proposed approach on various large-scale continuous control robotics environments in DeepMind control suite (Tassa et al., 2018) and Meta MetaWorld World (Yu al., 2021). We show that our approach archives better policy alignment due to the use of the corrected leper-level objective we propose in this work. We achieve up to 63% improvement in samples required to solve the task.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORKS
Preference Based RL. Revealed preferences a concept in economics that states that humans in many cases do not know what they prefer until they are exposed to examples via comparisons (Caplin & Dean, 2015). This idea gained traction as it provided a substantive basis for querying humans and elucidating feedback on pecision-making problems with metrics whose quantification is not obvious, such as trustworthiness or fairness. Efforts to incorporate pairwise comparison into RL, especially as mechanism to incorporate preference information, have been extensively studied in recent years see Wirth et al. (2017) for a survey. A non-exhaustive list of works along these lines is (Roth et al., 2016; Hill al., 2021; Wirth et al., 2017: Zhu et al., 2023; Xu al., 2020; Saha al., 2023; Chakraborty et al., 2023c;;2:0:: 2024).
Inverse RL and Reward Design. Reward design has also been studied through an alternative lens in which an agent is provided with demonstrations or trajectories and seeks to fit a reward function. Inverse reinforcement learning (Ziebart et al., 2008a; Brown et al., 2019; Arora & Doshi, 2020) learns a reward to learn behaviors deemed appropriate by expert. On the other hand, imitation learning directly seeks to mimic the behavior of demonstrations (Ho Ermon, 2016; Kang et al., 2018; Ghasemipour et al., 2019; Xiao et al., 2019). However, acquiring high-quality demonstrations can be expensive or infeasible (Bai et al., 2022; Chen et al., 2023; Wolf et al., 2023). also sidesteps some questions about whether reward can be well-posed for given collection of trajectories. A further detailed context of related works has been discussed in the Appendix B
PROBLEM FORMULATION
with state space S, action space A, transition dynamics P. discount factor (0, 1), and reward r S x A + R. Starting from state E S, an agent takes action a, and transitions s' P(. s, s,a). The agent follows stochastic policy that maps states to distributions over actions S + 4.a, which is parameterized by 8 E Rd. The standard finite horizon policy optimization problem is
Consider the Markov Decision Process (MDP) tuple M (8, A, A, P.r,
H -
max V2 =
Σ
7 r
an) on ~ =o(anlsa), 80 =
1=
where the expectation is with respect to the stochasticity in the policy Te and the transition dynamics P. We note that the formulation in (1) learns policy for specific reward function r (fixed priori). As detailed in the introduction, if the reward function r does not capture the intended behavior required by humans, it would lead learning misaligned policy. Therefore, policy learning with fixed reward does not allow one to tether the training process to an external objective such as human preferences (Christiano al., 2017), social welfare (Balcan et al., 2014), or market stability (Buehler al., 2019). To address this issue, we propose bilevel framework for policy alignment next.
3.1 POLICY ALIGNMENT IN REINFORCEMENT LEARNING: A BILEVEL FORMULATION
To achieve policy alignment RL, we consider the following bilevel optimization problem: (upper)
max G(y,0'(p)
He
(lower) s.t. (v()) = arg max E
Σ
rn an)
aas Te(aa(s)).so =
h=o
where 0 is the policy parameter as in (1) and v RD is the reward parameter. We discuss the formulation (2) detail as follows.
Lower Level (LL);: This is the policy learning stage for given reward parameterization v. For fixed v, LL problem the same as in (I) but note the explicit dependence of LL objective (2) on the reward parameter v which is different from (1). In this work, we restrict focus to the case that the optimizer 8" (v) at the lower level is unique, which mandates that one parameterize the policy in tabular (Agarwal et al., 2020; Bhandari & Russo. 2021) or softmax fashion (Mei et al., 2020a); otherwise, at most one can hope for with a policy gradient iteration to obtain approximate local extrema (Zhang et al., 2020). We defer more technical discussion of this aspect Section 5.
3

---

Published as a conference paper at ICLR 2024
Upper Level (UL)): This level (we also call it the designer level) evaluates the optimal policy learned at the lower level and tests for alignment. In (2), we aim to maximize an objective function G(v, 8 (v)), which depends on the reward parameters V and optimal policy parameter 8* (v), which is an implicit function of v. To be specific, we consider a utility (which is the alignment objective) at the upper level of the form
C(u,0 (m)) + Z(v),
which is comprised of two terms: a quantifier (()) of the merit of design parameters V E R", and (v) representing a regularizer or prior directly defined over the parameters of the reward function. More specifically, the explicit mathematical form of ((TTT- (v)) decides the quality of policy (T)(v)) by collecting trajectories (denoted by r) and associating a designer's 's evaluation reward (T) given by
(.))))))))[(()]]]]+) (())=(v)) = Extr (n)) -U - O(T;6(()))
(4)
where p(T; 8 (v)) denotes the probability distribution over the trajectories and can be explicitly expressed as p(T; (v)) = p(se) I P(s Sh, T (v) (v)(a))))), where Hy denotes the length of upper-level trajectory, p(8a) represent the initial state distribution. We discuss the explicit form of such an objective U2, in detail in Section 3.2 and also in Appendix C.
Remark 1 (Contrast with Standard Stochastic Bilevel Optimization), We highlight an important difference between our formulation in (2) and the standard stochastic bilevel optimization (SBO) in literature (Ghadimi & Wang. 2018a; Akhtar et al., 2022). We note that in (2), the distribution of stochastic upper-level alignment objective depends on the lower-level optimal variable (policy in our case). This differs from the existing works SBO where the expectation is over data whose distribution does not depend upon the lower level optimization variable. Hence, developing solutions for (2) exhibits unique technical challenges not found in the prior research.
3.2 REINFORCEMENT LEARNING FROM HUMAN FEEDBACK (RLHF) SPECIAL CASE
In this section, we demonstrate how our formulation proposed in (3) generalizes the RLHF paradigm (Christiano et al., 2017; Lee et al., 2021; Park et al., 2022). In RLHF, as proposed in Christiano et al. (2017), operates mainly in three iterative steps: start by (step 1) learning a policy (say TV-(v)) for
given reward ry by solving arg max, E Σ Σn=0 ""rr(s,, an) (step 2) collect human feedback after collecting trajectories (denoted by dataset D) from (v)- (step 3) learn new aligned reward model by solving min, Ey.no.7 - (v; y, To. ri) where denotes the alignment objective, and then go back (step 1). This iterative process is repeated over multiple iterations as detailed in Christiano et al. (2017); Lee et al. (2021); Park et al. (2022). Irrespective of its effectiveness in practice, rigorous mathematical formulation for RLHF missing from the literature. Furthermore, the existing RLHF pipeline, in step 3, completely ignores the fact that the data D is the function of π (w) which results in an incorrect objective to learn reward parameter. This results in policy misalignment and a performance gap, as highlighted in Figure 1(b). We reformulate the RLHF problem following our bilevel formulation as follows
max y
E (P log PT(TO > TI) + (1 -11-10 y) log PA < 71)
(5)
He-1
s.t. (v) = arg max E
Tr an) 1,
h=
where (T > TI) is the probability of preferring To over TI (denoted by y 1). We can model Pa using the well-known Bradley Terry model (Bradley & Terry, 1952) by
exp Σ H.-1 (x ag)
Pr( > n2)
(6)
exp Ehn ve a + exp En ro(s), (f))
where (s), a denotes state-action pair hh time-step in the tth trajectory. At the up- per level in (5), we highlight the dependence of data distribution (a(T; ( (v)) on the parame- ter via optimal policy (M)- The sampling distribution is given as paly, To, TI: 0* (v))
4

---

Published as a conference paper at ICLR 2024
Ty Ti P(Te (2))))((r:0 where, h(y/Tu,71) represents the human distribution of tra- jectory preference (unknown and realized only through samples). The trajectories To, T1 are sampled as P(T; 0* (v)) with the policy given by (w) (a)s). Hence, looking at (5), we note that it matches exactly with our formulation in (2) with upper level objective
Glv, 0 (v)) ==
log (To TI) + (1 log < <n)...
(7)
4 PROPOSED APPROACH: AN ALGORITHM TO SOLVE PARL
As mentioned in Remark 1, the resulting bilevel optimization problem in (2) differs from the standard bilevel problem studied well the optimization literature. Hence, we cannot directly apply any off-the-shelf algorithm to solve 2. In this section, we provide a step-by-step development of an iterative procedure to solve the policy alignment in (2) based on the bilevel algorithm' available in Ghadimi & Wang (2018b). Let us begin by deriving the gradient of the upper objective (cf. (3) and (4)) with respect to design parameter V, which is given by
V,G(v, 0 (v)) V. ΣU,() p(T; +
(8)
U.(T) V. log(p(T: (v))) ((T; (v)) + V,
(a(ria (T(T)
(p(r V, (og(((() Fo (.Ur+
H.
= -Ep(r:0(e)) (2))
(2(T)
V. log k (v) (anls))
+ Ep(r:0 (v)) (.U VvZ((,
h=0
where we have used the log-trick and standard rule of expectation get the final expression in (8)
(Williams, 1992; Sutton et al., 1999).
Novel terms in gradient evaluation: We emphasize two terms (a) the score function term V. log TT- (v) (a]s) ) in (8), denotes the gradient of logarithm of the optimal policy with respect to the
design parameter i; and (b) the expectation is with respect to the trajectory distribution p(T; 0* (v)) generated under policy at the lower-level (v). This term captures the change of optimal policy with respect to the reward parameters. This is crucial because the designer (such as a regulatory body or central planner) at the upper level can directly control the policy learning by modifying the reward parameters. We remark that both these terms are missing from the existing RLHF formulation in literature (such as the objective in step detailed Section 3.2).
Challenges: However, the estimation of V, log (T) (an (sx) is nontrivial as it depends on the solution of the lower-level problem in (2), and therefore requires the evaluation of hypergradient (v) To see that, let us employ the shorthand notation fa. (0" (v)) log vh rewrite the gradient² as
(T) (v) (an (s,), we can
v. =
(9)
Now, from the first order optimality condition for the lower level in (2), it holds that
VoVa (v)) O,
(10)
which is the gradient of lower-level objective with respect to parameter evaluated at the optimal (v).. Now, differentiating again with respect on both sides of (34), we obtain
V., 0* (v)) v 0. (V) 0" (v) O.
(11)
The above expression would imply that we can write the final expression for the gradient in (9) as
v.fr(0 2 (M, 8" (,
(12)
'e remark that is possible to follow more advanced bilevel optimization algorithms the literature to solve the bilevel problem in (2), we resort to the basic algorithm to highlight the novel aspects of our problem formulation for RLHI.
Throughout the analysis, we follow the convention as follows : let's say E R R² Hence. gradient terms V. (.f((0 E Rd VeJa (0) E It and hessian term (a E I1d2xdo and Jacobian 0.0" (v) E Rd, xdz and subsequently V,0 (v) Rd2xd2
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 Algorithm for Policy Alignment in Reinforcement Learning (A-PARL)
Input: Reward parametrization Po policy initialization 8", upper and lower-level step sizes Qu > 0, ay > 0 respectively f
2: for all 0, 2, ...,
do
3: for all k = 0, ..... K do
4: Sample N trajectories from equation (15)
pT:; 0 (v:)) and estimate policy gradient VaV. VoVa (1r,0K (ve))
5:
Update the policy gradient parameter as
Tik (wr) - (v,) + at VaV, V 0² (v))
policy update
6: Update the reward parameterization in the upper-level from equation (14) as
Ti t Tv. -an O (v:))
reward update
7: Output: Vr, 6 (VT)
We substitute (12) into (8) to write the final expression for the gradient of the upper objective in (2) as
Ha-1
G.Glu, =E ((( UT(
Σ
2 Vo
(1)
+ Bp(:000 (v)) V (T)] V2Z(v).
(13)
Even for the gradient expression in (13), there are three intertwined technical challenges such as the requirement estimate (T)( evaluating Jacobians and Hessians of the lower-level problem, and sampling trajectories in unbiased manner from (v)) which depends upon TT-(v)- We write the explicit values of the terms as follows. This establishes precise connection to the generalized alignment objective.
Upper-level gradient estimation: To estimate the gradient of the upper-level objective in (8), we require information about (v) which is not available in general unless the lower-level objective has a closed-forn solution. Hence, we approximate Th (vc) with TTK i.e., running K-step policy gradient steps at the lower level to obtain the approximate gradient of the upper level is as
H
M (o) (v))) V.ttat) + + V.Z())
V.G(v, 00 (v:)) E Bp(r:( (v)))
Un(T)
(14)
where M -. 0K (u:) V.V. VV OK (v.))-1
Lower-level objective gradient, Jacobian, and Hessian estimation: Here, derive the gradients for the lower-level objective and, subsequently the Hessian and mixed Hessian terms for our algorithmic description. First, we write down the gradient of lower-level objectives using the policy gradient theorem (Williams, 1992; Sutton et al., 1999) as
Hr-1
VoVa(v, 8K (v)) Ep (ve)
Σ h=0
Th (8h, and
Σ vo log nOx (me) (w))
(15)
where He is the horizon the episode length. Similarly, the Hessian of the lower objective is:
H
VVV. 8K (v()) =E (v))
Σ
rr (Sh, an)
Σ v log (o
(16)
A=o
Finally, we can write the mixed second-order Jacobian matrix as
H
h
V2 (1,,, 8 (v+) = =Ep(ri
Σ
Vuru rv (sh. and
Vo log Ron Tox (m)((())))))
(17)
h=0

---

Published as a conference paper at ICLR 2024
Now, utilizing the expressions in (14)-(17), summarize the proposed steps in Algorithm 1. We explain the execution of Algorithm with the help of Figure 4 in the Appendix B. We denote the number of lower-level iterates by K for better exposition which is function of upper iterations E T in the convergence analysis. Before shifting to analyzing the convergence behavior of Algorithm 1, we close with remark.
We have only presented the analytical forms of the first and second-order information required to obtain a numerical solver for problem in (2). However, in practice, these update directions unavailable due to their dependence Therefore, only sampled estimates of the expressions in (14)-(17) are available. For this work, we sidestep this challenge by assuming access to the oracles (14)-(17). This helps us to focus more on the policy and reward entanglement in our bilevel formulation. We can extend the analysis to stochastic settings utilizing the standard techniques in stochastic optimization literature (Chen et al., 2022; K won et al., 2023; Li et al., 2022b; Ji et al., 2021; Ghadimi & Wang, 2018b).
Remark 2.
distributions p(T; 0' (v)) and MDP transition model P.
Remark 3 (Gradient derivations for RLHF problem in Section 3.2). For the special case RLHF discussed in, we provide detailed derivations for the gradients at the lower and upper level objectives in Appendix D.
5 CONVERGENCE ANALYSIS
In this section, we analyze the convergence behavior of Algorithm 1. Since the upper level G(v,, 0* (v)) is non-convex with respect to v, consider V, V,G 0 (*())
lever
convergence criteria and show its convergence to a first-order stationary point, as well as the convergence of gK(v) (v) to 6* Taken together, these constitute local KKT point (Boyd & Vandenberghe, 2004)[Ch. 5] Without loss of generality, our convergence analysis is for the minimization (upper and lower level objectives). We proceed then by introducing some technical conditions required for our main results.
Assumption 1 (Lipschitz gradient of upper objective). For any E LR, the gradient of the upper objective is Lipschitz continuous w.r.f to second argument with parameter Lg. i.e., we may write
Vv, 0) V.G(u,
T, 0'1l-
(18)
Assumption 2. For all S and E A, reward function is bounded as rs(s, S R and Lipschitz w.r.t to v, i.e., Irv, (s, a) 1 Tvu (s, a)l S L, - -/2ll-
Assumption 3. The policy No is Lipschitz with respect parameter 9, which implies [|<T, (-1s)
Te, (-s)) < L0 02l1 for all 0,, 0z. The score function Va Volog To (a(a)s) is bounded [[V log To(a)s) S B and Lipschitz, which implies
Vo log no, (-1s) Vo log No, To,(1))) (+1=)] S L1 02ll--
(19)
Further, the policy parameterization induces a score function whose Hessian is Lipschitz as 1 g log Tu,
(-1s) Tu,(-1)) Va log no, (+1=)] L2|10, 02ll for all 0,,02 02.
(20)
Assumption 4. The value function Vs(v, 0) satisfies the Polyak-Lojoe Lojasiewicz (PI.) condition (with unique minima) with respect to 0 with parameter J.. We denote VV(VVV,(v, (,) as the eigenval- ues of Hessian matrix V2V.(v, 0). Although, (v,,v) 8) is non-convex in 9, but follows the restriction on the eigenvalues VVV 0)) E (-i, U [ā,
Assumption is standard in the analysis of non-convex optimization, and Assumption is common in RL which bounds the reward function value (Zhang et al., 2020; Agarwal al., 2020; Bhandari & Russo, 2021). In Assumption 3, the score function Lipschitz part is considered in the literature. But because we are dealing with a bilevel formulation here, which requires dealing with evaluating the lower level policy at the upper level, and also utilizing second-order information of the value function (cf. (13)). we need to assume policy and Hessian of policy are Lipschitz as well. Also, the second-order smoothness condition was studied in establishing conditions under which local extremum is attainable in the non-convex setting (Zhang et al., 2020) (Sec. 5]. Additionally, we need Assumption 4 because we are in bilevel regime without lower level strong convexity (Huang, 2023; Liu et al., 2023). However, the value function satisfies the
(PL) condition under common policy parameterizations (Bhandari & Russo, 2021; Mei et al., 2020b). م. defined in Appendix 4. we provide detailed discuss in Appendix I. Next, we introduce key technical lemmas
7

---

Published as a conference paper at ICLR 2024
Doo Opmn
Bulle Frex
Chick
5500
POSPS brstite
Estocdo Risur
PSABLO
-0e
PEREL
130
Enviioemmntal Steps 10
Environmental Stapo X
Envirommnnal Stops X
Figure 2: In this figure, we compare the performance of our algorithm A-PARL against SOTA baselines Pebble (Lee et al., 2021), PEBBLE+SURF (Park et al., 2022) and Oracle (true reward) for Walker (DMSuite (Tassa et al., 2018)), DoorOpen and ButtonPress (MetaWorld Yu et al. (2021)) w.r.t ground truth return (averaged over 5 seeds). It clearly demonstrates the superiority of our algorithm over existing baselines in terms of episodic return, where A-PARL achieves near-oracle performance in much faster time. This highlights the importance of our bilevel framework which considers the dependence (missing from existing literature) of distribution on the lower-level policy parameter during training.
regarding the iterates generated by Algorithm 1. We begin by quantifying the distributional drift associated with the transition model under approximate policy (ve) as compared with T (ex) at the lower level, which results in transient effect at the upper level.
Lemma 1. Under Assumptions 1 4. for trajectory {sA an I= it holds that
Dy(p(r; 0r (V)), plT; (0)))((()))))))))))))))))))))( HuL2 100 (v) 0 (w)l
(21)
2
where Dj is the f-divergence between distributions and L2 is the Lipschitz parameter (cf. Assun. 3).
The proof of Lemma 1 in provided in Appendix G.I. We highlight that the upper bound in Lemma 1 is novel to our analysis of bilevel RL which will not appear in the RLHF setup considered in the literature. Next, we establish some error bound conditions key second-order terms that appear in equations (14)-(17) when we substitute 0 (v:) by 0 (Pt).
Lemma 2. Under Assumptions 1-(4), the lower level iterates of Algorithm / satisfies ||0K (vs) 0" (2)))1 < n Z, where, Z == max, ||00 6 (v) == 1 - Qzs, = ac(1 oike ). LG L, HL2 + Ls, L5 = Hf RL1, μ is the PL constant, and K denotes the number of lower-level iterations, and policy gradient step-size satisfies at < 2/ min(H;Lg μ), with μ as the PL constant (Assumption 4).
2
The proof of Lemma 2 is provided in Appendix H.7. The proof relies on the assumption that the value function satisfies a Polyak Lojasiewiez (PL.) condition under appropriate policy parametrization. Theorem 1. Under Assumptions 1-4. for the proposed Algorithm 1, it holds that
GV, 0 (v:))1 Go- no2LoZ
(22)
8,T
T8
where Go == G(vo, 0 (vo)) and G denotes the global optimum of the upper objective, 5 au (1 (1- 2cj Lgau) and on = au ( Lyju), e1 is a positive constant defined in egn. (45), and the step-size range of satisfies an < Lgg with Ly as in Assumption and 0g as stated in Lemma
In Theorem 1, note that we achieve final rate of O1/TT), which matches with bilevel optimization for non-convex upper objective without requiring strong convexity at the lower level in (Ghadimi Wang, 2018a).
6 EXPERIMENTAL EVALUATIONS
We consider the challenging tasks of robotic locomotion and manipulation in the human preference- based RI. setting also considered in Lee et al. (2021); Park et al. (2022); Metcalf et al. (2022).
8

---

Published as a conference paper at ICLR 2024
Human Feedback: Although real-human preferences would have been ideal for the experiments, but it is hard to get them. Hence, we leverage simulated human teachers as used in prior research (Lee et al., 2021; Park et al., 2022). The simulated teacher provides preferences to the agent according to the underlying true reward function, which helps us to evaluate the policy alignment efficiently. To design more human-like teachers, various human behaviors like stochasticity, myopic behavior, mistakes, etc. are integrated while generating preferences as in Lee et al. (2021); Park et al. (2022).
pairwise trajectories
Baselines: We consider two state-of-the-art baselines for preference-based RL, which are PEBBLE (Lee al., 2021) and PEBBLE+SURE (Park et al., 2022). We specifically compare with these two algorithms since PEBBLE+SURE (Park et al., 2022) and PEBBLE (Lee et al., 2021) already outperforms all the other existing algorithms, including (Metcalf et al., 2022; Christiano et al., 2017) in similar environment and configu configurations. is important to note that PEBBLE+SURFF utilizes additional unsupervised data and augmentations to improve the performance of PEBBLEE and hence depending on the quality and amount of the unsupervised information, the performance of PEBBLE+SURF varies rapidly. Hence, it is not extremely fair to compare PEBBLE+SURF with ours due to this obvious benefit, but still, we observe that our algorithm performs better than PEBBLE+SURF with controlled augmentations.
Experimental Results Discussions and Evaluation: To evaluate the performance of our algorithm against baselines, we select true episodic reward return as a valid metric. Since the eventual goal of any RL agent is to maximize the expected value of the episodic reward return, which is widely used in the literature. We conduct the experimental evaluations primarily centered on three key ideas -i.) First, we characterize the gap in the performance of the current SOTA methods due to inexact alignment strategies as demonstrated in Figure I which clearly shows a significant gap in current SOTA methods. ii.) Second, we compare the performance of our algorithm against baselines in the above benchmarks w.r.t ground truth return as shown in Figure 2 (averaged over 5 seeds). Environments: We evaluate the performance of the proposed algorithm for our framework PARL on large-scale continuous control robotics tasks in DM Control suite (Tassa et al., 2018) and Meta-World (Yu et al., 2021).
demonstrates our algorithm's 'ss superiority over existing basclines in terms of episodic return, where A-PARL achieves near-oracle perfor- mance in a much faster time with improved sample efficiency of approximately 63%. iii.) Finally, we test the alignment behavior of our learned policy by validating the generated tra- jectories on interacting with the environment against potential hacking or spurious learning. We validated if the agent is learning desired be- haviors or has learned to hack the fitted reward due to the issue of reward overoptimization in RLHF (Gao et al., 2022) (specifically at an early stage of learning where it hits the high reward point). As observed in Figure 3, our agent learns the desired behavior and is able to open the door, whereas the existing algorithm (PEBBLE) fails to do so, demonstrating the effectiveness of our
[b]
Figure 3: A visualization of learned behavior for the baseline Pebble (top row) and proposed (in the bottom row) (with policy at Env-Step 0.5 x 10%). We note that the proposed A-PARL algorithm has been able to learn the aligned behavior of open- ing the door in the generated trajectory (top-right) whereas PEBBLE gets stuck depicting our algo- rithm's 's efficiency in alignment.
algorithm in alignment.
7 CONCLUSION
Potentially misaligned agents pose a severe risk to society; thus making Al alignment at the forefront of research of the current times (Liu et al., 2022). We identify major gap within current algorithmic designs for AI alignment due to a lack of characterization of the dependence of the alignment objective on the data generated by policy trajectories. To mitigate the gap. we develop unified bilevel optimization-brn reinforcement learning. Our proposed algorithm demonstrates superior performance over existing SOTA methods in large-scale robotics control tasks with provable convergence guarantces of rate O(/T)).
framework, PARL as a first step to address the policy alignment issue in

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENT
Chakraborty and Huang are supported by the National Science Foundation NSF-IIS-FAI program, DOD-ONR-Ofiie of Naval Research, DOD Air Foree Office of Scientific Research, DOD-DARPA- Defense Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), Adobe, Capital One, and JP Morgan faculty fellowships. Manocha and Bedi would like acknowledge the support by Army Cooperative Agreement W91 INF2120076 and Amazon Research Awards 2022.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
Zeeshan Akhtar, Amrit Singh Bedi, Srujan Teja Thomdapu, and Ketan Rajawat. Projection-free stochastic bi-level optimization. IEEE Transactions on Signal Processing, 70:6332-6347, 2022.
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress, 2020.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34:25799-2588 2021.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, Ben Mann, and Jared Kaplan. Training helpful and harmless assistant with reinforcement learning from human feedback, 2022.
Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-
Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V Vazirani. Learning economic parameters from revealed preferences. In Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 17, 2014. Proceedings 10, pp. 338-33 338-353. Springer, 2014.
Amrit Singh Bedi, Souradip Chakraborty, Anjaly Parayil, Brian M Sadler, Pratap Tokekar, and Alec Koppel. On the hidden biases of policy mirror ascent in continuous action spaces. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 1716-1731. PMLR, 17-23 Jul 2022. URI https: wtwpprreeeiing...m www.prrsss............ v1 62. /bdiibdii 22a html.
Viktor Bengs, Rbrbert Busa-Fekete Adil El Mesaoudi-Paul and Eyke HÄlillermeier. Preference- based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22 (7):1-108, 2021. URL http: jmmrr. r org/ httpppppss/s// wttpss//v2//1e/// 546. html.
Dimitris Bertsimas and Constantine Caramanis. Finite adaptability in multistage linear optimization. IEEE Transactions on Automatic Control, 55(12):2751-276 2010.
Dimitris Bertsimas, Dan A lancu, and Pablo A Parrilo. Optimality of affine policies in multistage robust optimization. Mathematics of Operations Research, 35(2):363-394, 2010.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pp. 2386-2394. PMLR. 2021.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21 1973.
10

---

Published as a conference paper at ICLR 2024
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324, 1952. URL hwtph::/p////. /app. semanticscholl...... org/CorpusID 125209808.
Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond
suboptimal demonstrations via inverse reinforcement learning from observations, 2019.
Hans Buchler, Lukas Gonon, Josef Teichmann, and Ben Wood. Deep hedging. Quantitative Finance, 19(8):17111121, 2019.
Patrick Butlin. Ai alignment and human reward. In Proceedings of the 2021 AAAI/ACM Conference AI, Ethics, and Society, pp. 437-445, 2021.
Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem, 2023.
Zehong Cao, KaiChiu Wong, and Chin-Teng Lin. Weak human preference supervision for deep reinforcement learning, 2020.
Andrew Caplin and Mark Dean. Revealed preference, rational inattention, and costly information acquisition. American Economic Review, 105(7):2133-2203 2015.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307.15217, 2023.
Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Pratap Tokekar, and Dinesh Manocha. Dealing with sparse rewards in continuous control robotics via heavy-tailed policies, 2022.
Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Brian M. Sadler, Furong Huang, Pratap Tokekar, and Dinesh Manocha. Posterior coreset construction with kernelized stein discrepancy for mosel-based reinforcement learning. 2023a.
Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Mengdi Wang, Furong Huang, and Dinesh Manocha. Steering: Stein information directed exploration for model-based reinforcement learning,
2023b.
Souradip Chakraborty, Amisha Bhaskar, Anukriti Singh, Pratap Tokekar, Dinesh Manocha, and Am- rit Singh Bedi. Rebel: A regularization-basse based solution for reward overoptimization in reinforcement learning from human feedback, 2023c.
Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Furong Huang, Dinesh Manocha, Am- rit Singh Bedi, and Mengdi Wang. Maxmin-rlhf: Towards equitable alignment large language models with diverse human preferences, 2024.
Pei-Yu Chen, Myrthe L. Tielman, Dirk K. J. Heylen, Catholijn M. Jonker, and M. Birna van Riemsdijk. Ai alignment dialogues: An interactive approach to ai alignment in support agents, 2023.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In Gustau Camps-Valls. Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statisticy, volume 151 of Proceedings of Machine Learning Research, pp. https: /ttp:///ccceeeeegsseeee mlr press vi vvlvvvllvv// httpsccchhaae chen22e .htmm.................mm
PMLR, 28-30 Mar 2022. URL
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.
Miroslav Dudík, Katja Hofmann, Robert Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits, 2015.
11

---

Published as a conference paper at ICLR 2024
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Convergence of learning dynamics in stackelberg 2019.
games. arXiv preprint
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning, pp. 3133-3144. PMLR, 2020.
Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine.
connection between generative adversarial networks, inverse reinforcement learning, and energy-based models, 2016.
Christopher Frye and Ilya Feige. Parenting: Safe reinforcement learning from human input. arXiv preprint arXiv:1902.06766 2019.
Johannes Fürnkranz, Eyke Hüllermeier, Weiwei Cheng, and Sang-Hyeun Park. Preference-based reinforcement learning: A formal framework and a policy iteration algorithm. Mach. Learn., 89
(1-2):123-156, oct 2012. ISSN 0885-6125. doi: 10. 11.1007/119994-01-5333333 URL https:
//ddoi.or//// 1007 -00----4---2--------------
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization, 2022.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: ToXi::/002.0240 2018a
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming, 2018b. URL wass//s100 1802 02246.
atttps:/aartt aariiv. org/ abs/
Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective imitation learning methods, 2019.
Denizalp Goktas, Sadie Zhao, and Amy Greenwald. Zero-sum stochastic stackelberg games, Advances in Neural Information Processing Systems, 35:1 1511161611672, 2022.
Edward W. Hill, Marco Bardoscia, and Arthur E. Turrell. Solving heterogeneous general equilibrium economic models with deep reinforcement learning. ArXiv, abs/ https/2003.166777 2021.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning, 2016.
Jonathan Ho, Jayesh K. Gupta, and Stefano Ermon. Model-free imitation learning with policy optimization, 2016.
Zehong Hu, Yitao Liang, Jie Zhang, Zhao Li, and Yang Liu. Inference aided reinforcement learning for incentive mechanism design in crowdsourcing. Advances in Neural Information Processing Systems, 31, 2018.
Feihu Huang. On momentum-based gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprint arXiv:2303.03944 2023.
Feihu Huang, Junyi Li, Shangqian Gao, and Heng Huang. Enhanced bilevel optimization via bregman distance. Advances in Neural Information Processing Systems, 35:28928-28939, 2022.
Leonid Hurwicz. Mechanism design without games. Advances in Economic Design, pp. 429 437, 2003.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari, 2018.
Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. Journal of Machine Learning Research, 23:1-56, 2022.
Kaiyi Ji, Junjie Yang, and Yinghin Liang. Bilevel optimization: Convergence analysis and enhanced design, 2021.
Bingyi Kang, Zequn Jie, and Jiashi Feng. Policy optimization with demonstrations. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 2668- PMLR, 10-15 Jul 2018. URL https::/ http//ppoeeddde// ngs ml r.press///see v a 8a html.
12

---

Published as a conference paper at ICLR 2024
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double monole-mmmnntmm.. Advances in neural information processing systems, 34:30271-30223 2021.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. A fully first-order method for stochastic bilevel optimization, 2023.
Kimin Lee, Laura Smith, and Pieter Abbeel. Pebble: Feedback-efficiet interactive reinforcement learning via relabeling experience and unsupervised pre-training, 2021.
Tyler Lekang and Andrew Lamperski. Simple algorithms for dueling bandits, 2019.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7434-7434, 2022a.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum- variance reduction, 2022b.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (00dv::55990099900 529771 2015.
Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Averaged method multipliers for bi-level optimization without lower-level strong convexity. arXiv preprint arXhv:2302.03407 2023.
Ruibo Liu, Ge Zhang, Xinyu Feng. and Soroush Vosoughi. Aligning generative language models with human values. In Findings of the Association for Computational Linguistics: NAACL 2022, pp. 241- 252, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/v1/ 2022.finding 2022.findings-naac.. 18.. URL https: /tae///aaaaa /accaaaaaaaa /aclanthooogy org/ 2022. indings-naace 18.
Songtao Lu. Bilevel optimization with coupled decision-dependent distributions. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. -27799 PMLR, 23-29 Jul 2023. URL https:// proceedings www.m.rr.......... wwi.r.press/v200
Boxiang Lyu, Qinglin Meng. Shuang Qiu, Zhaoran Wang, Zhuoran Yang, and Michael I Jordan. Learning dynamic mechanisms in unknown environments: reinforcement learning approach.
arXiv preprint 2rXh::200..12733 2022a.
Boxiang Lyu, Zhaoran Wang, Mladen Kolar, and Zhuoran Yang. Pessimism meets veg: Learning dynamic mechanism design via offline reinforcement learning. In International Conference Machine Learning, pp. 14601-14638, PMLR, 2022b.
Hamid R. Maei, Csaba Szepesvári, Shalabh Bhatnagar, Doina Precup. David Silver, and Richard S. Sut- ton. Convergent temporal-differeen learning with arbitrary smooth function approximation. In Pro- ceedings of the 22nd International Conference on Neural Information Processing Systems, NIPS'09, pp. 1204-1212, Red Hook, NY, USA, 2009. Curran Associates Inc. ISBN 978 178165667919.
Chinmay Maheshwari, Shankar Sasty, Lillian Ratliff, and Eric Mazumdar. Convergent first-order methods for bi-level optimization and stackelberg games. arXiv preprint arXiv:2302.01421, 2023.
Eric S Maskin. Mechanism design: How to implement social goals. American Economic Review, 98 (3):567-576, 2008
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp.
6820-6829. PMLR, 2020a.
13

---

Published as a conference paper at ICLR 2024
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Hal Daumé and Aarti Singh (eds.), Proceedings of the 37th International Conference Learning Research, pp. 6820-6829. PMIR, 13-18 Jul 2020b. URL https: /ttp///rooceeeeeeeeoeoeooooooooe nggs mlr. mlr.press// v 9 met 20b ht.l.
Machine Learning, volume 119 of Proceedings of Machine
Katherine Metcalf, Miguel Sarabia, and Barry-John Theobald. Rewards encoding environment dynamics improves preference- based reinforcement learning, 2022.
Roger B Myerson. Mechanism design. Springer, 1989.
Andrew Y. Ng and Stuart J. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML '00, pp. 663-670, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
Richard Ngo, Lawrence Chan, and Sören Mindermann. The alignment problem from deep learning perspective. arXiv preprint wrXiv2209.00626, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling Reinforcement learning with trajectory preferences, 2023.
Jongjin Park, Younggyo Seo, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. Surf: Semi-supervised reward learning with data augmentation for feedback-efficien preference-bas reinforcement learning, 2022.
Georg Ch Pflug and Alois Pichler. Multistage stochastic optimization, volume 1104. Springer, 2014.
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Watch and learn: Optimizing from revealed preferences feedback. In Proceedings of the Firty-Eighth Annual ACM Symposium on Theory of Computing. STOC 16, pp. 949-962, New York. NY. USA, 2016. Association for Computing Machinery. ISBN 978 1450341333 doi: 10.1145/2895518.88977777 URL https: //oii org/ 10. 15 8897589933 2897579.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pp. 6263 2269. PMLR, 2023.
Kyriacos Shiarlis, Joao Messias, and Shimon Whiteson. Inverse reinforcement learning from failure. In Proceedings of the 2016 International Conference Autonomous Agents & Multiagent Systems, AAMAS 11,, pp. 1060-1068, Richland, SC, 2016. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450342391.
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On integral probability metrics, g-divergences and binary classification, 2009.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances neural information processing systems, 12, 1999.
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-different learn- ing with linear function approximation. In Proceedings of the 26th Annual International Con- ference on Machine Learning, ICML '09, pp. 993- 1000, New York, NY, USA, 2009, Associa- tion for Computing Machinery. ISBN 978 1781665581161. doi: 10. (0.1145/1533374115555) URL 1141 1111111/15333774 1553501.
https: wttp:/do..oooo www./1......... 11111...111.11.
Pingzhong Tang. Reinforcement mechanism design. In IJCAI, pp. 5146-5150, 2017.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmalcki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite, 2018.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
14

---

Published as a conference paper at ICLR 2024
Quoc-Liem Vu, Zane Alumbaugh, Ryan Ching, Quanchen Ding, Arna Mahajan, Benjamin Chasnov, Sam Burden, and Lillian Ratliff. Stackelberg policy gradient: Evaluating the performance of leaders and followers. In ICLR 2022 Workshop Gamification and Multiagent Solutions.
Pawel Wawrzyúski. Real-time reinforcement learning by sequential actor eetor-criticss and experience replay. Neural Networks, 22(10):1444-197, 2009, ISSN 0893-6080. doi: htpp:///biiorg/10011066 20euueet.000.000001.. URL https:/ /www. sci enceddeddsiccc weceeedirree...mm com/ /tt/s/icnneeaarrcceeee p11/S09936800000100 026..
Kasun Weerakoon, Souradip Chakraborty, Nare Karapetyan, Adarsh Jagan Sathyamoorthy, Am- rit Singh Bedi, and Dinesh Manocha. Htron:efficient outdoor navigation with sparse rewards via heavy tailed adaptive reinforce algorithm, 2022.
Ronald J Williams. Simple statistical moddient-following algorithms for connectionist reinforcement learning. Reinforcement learning, pp. 5-32, 1992.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. A bayesian approach for policy learning from trajectory preference queries. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.). Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL ht http::ttp///ommm / file/1 6c222aa 98 ptwc///occeedioooooooooooooeoecc ngs neur ips
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136): 2017.
Yotam Wolf, Noam Wies, Yoav Levine, and Amnon Shashua. Fundamental limitations alignment in large language models, 2023.
Markus Wulfmeier, Peter Ondruska, and Ingmar Posner. Maximum entropy deep inverse reinforcement learning, 2016.
Huang Xiao, Michael Herman, Joerg Wagner, Sebastian Ziesche, Jalal Etesami, and Thai Hong Linh. Wasserstein adversarial imitation learning, 2019.
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:18884-11777444 2020.
Junjie Yang. Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 13670-136888 2021.
Tianhe Yu. Deirdre Quillen, Zhanpeng He, Ryan Julian, Avnish Narayan, Hayden Shively, Adithya Bellathur, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning, 2021.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 2586-3612, 2020.
Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Can reinforcement learning find stackelberg- nash equilibria in general-sun markov games with myopic followers? arXiv preprint arXiv:2112.135211 2021.
Banghua Zhu, Jiantao Jiao, and Michael I. Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons, 2023. URL /tttp::///rxiv...// abs/ 2301. 11270.
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI'08, pp. 1438. AAAI Press, 2008a. ISBN 978 9781577333683.
15

---

Published as a conference paper at ICLR 2024
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAT'08, pp. 1433-1438. AAAI Press, 2008b. ISBN 9781577353683.
Brian D. Ziebart, J. Andrew Bagnell, and Anind K. Dey. Modeling interaction via the principle of maximum causal entropy. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10. pp. 2255-1262, Madison, WI. USA, 2010. Omnipress. ISBN 978 1055899077
16

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Notations
18
B Detailed Context of Related Work
18
Additional Motivating Examples
20
Gradient Evaluations RLHF
21
E Additional Lemmas
22
F Proof of Theorem 1
23
G Proof Lemmas
26
Proof Lemma
G.2 Proof of Lemma
28
H Additional Supporting Lemmas
31
H.1 Proof of Lispchitzness and Boundedness condition for f-) defined in (74)
31
H.2 Proof of Lispchitzness and Boundedness for fa(-) defined in (82)
32
H.3 Proof of Smoothness Condition on the Value function
32
H.4 Upper-bound
Norm hessian for the Bilevel RI.
34
Upper-boune bound on the Norm of the 2nd Order Mixed-Jaccobel term Bilevel
H.6 Proof of Lemma
35
H.7 Proof of Lemma
36
1 Discuss of Assumption 3 and Assumption 4
37
J Additional Experimental Details
38
Additional Experimental Descriptions
39
17

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
We collectively describe the notations used in this work in Table 1.
Table 1:
Notations
Details
S,A
State space, action space
())
State-action pair
(,)))
Transition kernel
a))
Reward function parameterized by designer's parameters e R"
(-1s)
Policy parameterized by 0(v) R for design parameters
V(()
lower objective Value function for state at upper parameter and policy parameter ((v)
(v),
upper objective
B DETAILED CONTEXT OF RELATED WORK
Bilevel Optimization. Multi-stage optimization has a long-history in optimization and operations research, both for deterministic (Bertsimas & Caramanis, 2010) and stochastic objectives (Pflug & Pichler, 2014). In general, these problems exhibit NP-hardness if the objectives are general non-convex functions. Therefore, much work in this area restricts focus to classes of problems, such affine (Bertsimas & Caramanis, 2010; Bertsimas et al., 2010). From both the mathematical optimization community (Bracken & McGill, 1973) and algorithmic game theory (Von Stackelberg, 2010), extensive interest has been given to specifically two-stage problems. A non-exhaustive list contains the following works (Ghadimi & Wang. 2018b; Yang al., 2021; Khanduri al., 2021; et al., 2022a; & Liang, 2022; Huang et al., 2022). Predominately, one these works do not consider that either stage is a MDP, and therefore while some of the algorithmic strategies are potentially generalizable the RL agent alignment problem, they are not directly comparable to the problem studied here.
Stackleberg Games. Algorithmic methods for Sackleberg games are a distinct line of inquiry that develops methods to reach the Stackleberg equilibrium of a game, which have received significant attention in recent years. Beginning with the static Stackleberg game setting, conditions for gradient play to achieve local equilibria have been established in (Fiez al., 2019). Follow work studied conditions for gradient play to converge without convexity. but does not allow for MDP/trajectory dependence of objective functions at either stage (Maheshwari et al., 2023). On the other hand, the access to information structures have gradually been relaxed to allow bandit feedback (Bai et al., 2021) and linear MDPs (Zhong al., 2021). Value iteration schemes have been proposed to achieve Stackleberg-Nart equilibria as well (Goktas et al., 2022), although it is unclear how to generalize them to handle general policy parameterization in a scalable manner. Most similar to our work are those that develop implicit there are no performance certificates for these approaches.
based gradient play (Fiez et al., 2020; Vu et al.); however,
Mechanism Design. In this line of research, one studies the interrelationship between the incentives of an individual economic actor and their macro-level behavior the level of social welfare objective. This literature can be traced back to (Myerson, 1989; Hurwicz, 2003; Maskin, 2008), and typically poses the problem as one that does not involve sequential interactions. More recently, efforts to cast the evolution of the upper-stage which quantifies social welfare ethnical considerations sequential process, i.c., an MDP, have been considered (Tang, 2017; Hu et al., 2018). In these works, agents' behavior is treated fixed and determining of the state transition dynamics, which gives rise to a distinct subclass of policy optimization problems (Lyu et al., 2022a;b).
Reinforcement Learning with Preferences. Revealed preferences is concept in economics that states that humans in many cases do not know what they prefer until they are exposed to examples (Caplin& & Dean, 2015). This idea gained traction it provided substantive basis for querying
18

---

Published as a conference paper at ICLR 2024
Initial To Reward
Agent's inner goal (flexible)
Social welfare goal (implicit)
Learn Policy
To (ro)
T (r1)
T2 T2((2)
100
Generate Trajectories Ty ru P(ru: mo)
Generate Trajectories ~ P(mim))
Generate Trajectories P(zz m2)
Learn Rewards
m min L(T.
min ((T,,))
rs : min C(T2,
Figure 4: This figure describes the implementation flowchart of the iterative process of policy alignment in reinforcement learning. We start with some initial reward ro. learn an optimal policy To for that particular reward function at instant t = O, and utility evaluates the policy generate an updated reward function ri. Then at the next iterate = 1, we learn and so on.
humans and elucidating feedback on decision-making problems with metrics whose quantification is not obvious, such as trustworthiness or fairness. In its early stages, (Wilson et al., 2012) proposed the policies directly from preferences.
Bayesian framework to learn posterior distribution However, (Fürnkranz et al., 2012) focused on learning a cost or utility function as supervised learning objective maximize the likelihood of the preferences and subsequently maximize the policy under the estimated utility. An alternative and interesting line of research involves dueling bandits, which focuses on the comparison of two actions//rajectories and aims to minimize regret based on pairwise comparisons (Dudík et al., 2015; Bengs et al., 2021; Lekang & Lamperski, 2019; Pacchiano al., 2023). (Christiano al., 2017) was one of the first to scale deep preference- learning for harge-scale continuous control tasks by learning reward function aligned with expert preferences. This was later improved by introducing additional demonstrations (Ibarz et al., 2018) and non-binary rankings (Cao et al., 2020). Most recent works (Lee et al., 2021; Park et al., 2022) improve the efficiency of preference- pre-training. However, rigorous mathematical formulation analysis of the problem is still missing from the literature with special emphasis on the aligmment objective and evaluations.
learning for large-scale environments with off ofl-policy learning and
Inverse Reinforcement Learning & Behavioral Cloning. Implicitly contained in the RL with preferences framework is the assumption that humans should design a reward function to drive an agent toward the correct behavior through its policy optimization process. This question of reward design has also been studied through an alternative lens in which one provides demonstrations or trajectories, and seeks fit a reward function to represent this information succinetly. Inverse RL (IRL) is concerned with inferring the underlying reward function from a set of demonstrations by human experts. Pioneering work in IRL, notably by Ng and Russell Ng & Russell (2000), centers on the max max-margin inverse reinforcement learning framework for reward function estimation. Another prominent direction by Ziebart al. (2008b; 2010) introduced the Max Entropy IRL. framework which excelled in handling noisy trajectories with imperfect behavior via adopting probabilistic perspective for reward learning. However, a major drawback in all these prior methods was the inability to incorporate unsuccessful demonstration which was efficiently solved in Shiarlis et al. (2016) with constraint optimization formulation, by also maximizing the between the empirical feature expectation of unsuccessful examples and the feature expectation learned from the data. Interestingly Ho et al. (2016) posed it in the min- min-max formulation where the objective is to maximize the optimal policy and minimize the divergence to the occupancy indicated by the current policy and expert trajectories.
19

---

Published as a conference paper at ICLR 2024
Later, with Deep RL methods, Finn et al. (2016); Wulfmeier et al. (2016) extended the maximum entropy deep IRL to continuous action and state spaces. Although IRL methods are effective, they still are extremely dependent high-quality demonstrations which are expensive and might be hard to obtain for real-world sequential decision-making problems. Hence, there has been recent research on reward shaping and information-directed approaches Chakraborty et al. (2023b); Weerakoon et al. (2022); Bedi et al. (2022); Chakraborty et al. (2023a; 2022) which provides principled methods to learn under sparsity. However, such methods fail to scale large state space roboties environments.
C ADDITIONAL MOTIVATING EXAMPLES
Example 1: Energy efficient and sustainable design for robotic manipulation. Consider a robotic manipulation task where the objective of the agent is to learn an optimal policy to transport components from a fixed position to target position v == (z. y). On the other hand, the designer's objective is to select the work-bench position to minimize the energy consumption of the robotic arm during the transportation task. Hence, it naturally boils down to the following bilevel problem as
H
max E (v( (v)) (2
Σ
w/ an ~ (o)()))))5))
(23)
H (rrossh an no(an (o(an)ln),,
s.t. 0 (v) = arg max E
where (p(r.(-(v)) denotes the expectation with respect to the trajectories collected by the lower- level optimal policy (z). In (23), action aş, denotes the angular acceleration of the robotic arm, the state is represented by 8a. (an, wP), ). Og is the discretized angle, and wy angular velocity of the robotic arm. we define the transitions as (a++1, W(+1) = (as + wh, wh + an). The reward of the lower objective (sh, ax) = -A1 ||s; - 1 A //,ll i.e., reward increases as the arm moves closer to the workbench with a controlled angular velocity. The upper objective focuses on minimizing the energy emission during transport and thus entangled with the trajectories generated under the optimal policy obtained via the lower-level. Therefore, to see that the problem in (23) a special case of (2), we note that the upper objective (cf. (3)) takes the special form as follows
G(N₁ 0" (v)) U (T) = (x)) 2h=1 Wa,
an To (e) (-1sn)) where Z(v) = 0 for
this example.
Example Social welfare aligned tax design for households. Consider the problem of tax design for individual households while remaining attuned to social welfare, motivated by (Hill et al., 2021) From the houschold's 's perspective, each household seeks maximize its own utility un based on the number of working hours, consumption of goods, and net worth. Let us denote the accumulated asset as state 8h- each time step h, the household agent selects an action ag (nA, Cj,h), ) an ~ wo (a [s)]))). where is the number of hours worked, and Gr is the consumption of good i at a pre-tax price of Pi. and 0 denotes the policy parameter. We denote f*x) as the reward for the accumulative asset
updated at each time step by $h+1 = 8n + (1 - wrn EM Cs.A and = (z, y1) is the uniform tax across
income tax rate and consumption tax rate for good i. Here we note that tax rate. Then the houschold agent's utility at
all households, whereas y; is houschold-specin
where the product term corresponds to Cobb-Doughe function (Roth al., 2016). In contrast, the objective of the regulatory body or government (upper-level) is to maximize the social welfare by adjusting the tax rates v based on the optimal policy of the household agent (lower level). Hence, the upper objective
time step h is given by the equation Un = f(s)) y + II,M- [p((1+y)]
C.AA
representing the social welfare defined 2n = s(*)) + E. T+w: + In [ 6..0 w.r,h) (1+t))
where 9(-) is the reward for the accumulative asset, & is positive constant, and w is the wage rate. The household agent follows a policy that maximizes its discounted cumulative reward, while the social planner aims maximize the discounted total social welfare by tuning the tax rates and y;-
20

---

Published as a conference paper at ICLR 2024
Thus, the bilevel formulation is given by H
max E (((r00(()) (w))
Uy (shs
(24)
s.t. (v) : arg max 0
Σ h=0
7 un an) an ~ To(an)sh) 80
where 7 is the discount rate, and (v) represents the optimal lower policy of the household agent, which maximizes its expected cumulative return over time horizon Hç.
Example 3: Cost-effective robot navigation with Human feedback. Consider an N x maze- world environment where the robot needs navigate from start state
goal state g. The maze is represented by grid with discrete positions (i, j), and the robot can take four actions {1 + 4, } The agent receives a reward Rg(T), on reaching the goal and the objective of the agent is to learn the optimal policy πς- for goal reaching. The designer on the other hand, bears an additional cost of moving the goal position from the terminal state (N 1, N 1) and hence need to optimize for general utility metric considering both the objectives and can be formulated as the bilevel optimization as
max 9
-11lg (N - 1,N - 1)]12 >22 (n) (Ry(T)
(25)
He-1
s.t. 0r arg max E
Σ ("rg(sh,an) an) I an no (o(anls)) 80 h=0
where the reward function is characterized by the goal state g. The upper objective deals with finding a suitable position of the goal state that can optimize the sustainability metric and the lower objective deals with optimal policy and reward achieved under the same.
D GRADIENT EVALUATIONS FOR RLHF
In this section, we demonstrate how our A-PARL algorithm is applicable to the Reinforcement Learning from Human preferences paradigm. We begin by writing the gradient of the upper-level preference objective in equation (7) as
Giv, 8 (v)) Vyy Pr m1) + (1 y) log PT Tz)l
(26)
= -V,E(fuToo T.1 = V. Σ fo T1, p(y, To: To: T1;00(
where, let's denote (T.T,.11,9) = y log PT > n) + (1 (1- y) log Pe(TO < 7)) for simplicity of notation and stated before 7 = (To, Tı, have
=1,8). 3). Now expanding upon the gradient in equation (30), we
V,C(u, = FV (To T1, v1. + Σ Su (u(TO.T1.1) Vup(y, To. T1, (v))
(27)
where, we use the chain-rule and replace summation with expectation to get the equation (27).
VeG(v, (v)) = EVV TI, TI. rJ]l =I. + Σ T. Vup(y, To. T1: (v))
(28)
v. [V + (To
vo T: (v))
Term 1
Term
where, we divide and multiply the second term by the ply, To, TTs 00 (v)) to get the log gradient term inside expectation. Now, to compute the expression, we first compute the gradient of f((o, T y, v). From the definition in equation (6), know that
exp RT(TT)
Pr > T))
(29)
exp Ry (To) exp Ry (TI) log P, > T1) = (TU) log(exp R2 (To) + exp (T))) log Pr( To) = (T) log(exp (T)) exp (T)))
21

---

Published as a conference paper at ICLR 2024
Now, with the above equation, the expression of Term in equation (28) can be expanded
E[Vnf(ro. T1 v)] = log > m)) + (1 - y),, (To < T1)] = R, (o) +
(30)
V (T -
exp (To) V, (T) exp (T)(T))
exp R, (T)) + cxp (T))
E (T)) (1- (1-)))))) - VyRR((T)PPut 71) (T) m))
Note that this term can be easily estimated under any differentiable parametrization of the reward function Rg Next, we move term where the trajectories Tu, T1 are drawn from the distribution P(T; l (v) parametrized by the policy T6" (v)). The Term 2 from equation (28) can be written as
Ef (To. F1,8) V log ply, TO, T1: (v))
(31)
(To, T1.9) V log (hylTo, ai ( (v)))(T)
(To, m,,) (V log p(ro 0 (v)) V. log
Now, the term V, p( 0* (u)) can be expressed exactly done in equation (8)
V. log p(T1; (v)) = Σ Vu log Ta (w) (4x]st)
(32)
Now, exactly following the similar steps as done from equation (33) equation (36) can rewrite the gradient in the context of Bilevel RLHF as
Va (0 =
(33)
From the first order optimality condition for the lower level objective, it holds that
VaVa(1, ( (v)) = O,
(34)
which is the gradient of lower-level objective with respect to parameter 0 evaluated at the optimal 8" (v)). Now, differentiating again with respect to y on both sides of (34), we obtain
Vi.VV.( 0* (v)) + V v o (V)VVV, 0 (v))
(35)
The above expression would imply that we can write the final expression for the gradient in (33) as
(ora(O*))) V2, (v, (v)) 8"
(36)
Now, replacing this in Term 2 we will get the final expression. It is important to note that it requires the same gradient computations as shown Section for our generalized policy alignment algorithm.
E ADDITIONAL LEMMAS
Lemma (Value function related upper bounds). Under Assumptions -4, it holds that
(i) The second order Jacobian term V2, Vo.VV 6 (vt)) is bounded as V/ (v,, 0K (v.) L, where He is the horizon length for the lower level [ef. (2)], Lyp the reward Lipschitz parameter lcf. Assumption 2], and B is the score function bound [ef. Assumption 31.
(ii) The Hessian of the value function is Lipschitz with parameter
V. 6t (v)) - V%V, (v, 8K (v)) < (')
-
8 (v)
(37)
where, L' = L La + Ltp, and Ls, L2H? R. Here, He is the horizon length at the lower level, X1 is constant defined in (77), R is the maximum reward (cf. Assumption 2), and L2 the Lipschitz parameter of the Hessian of the policy defined in Assumption 3.
(ii) The second order mixed jacobian term V2 v. V. 8K (v)) is Lipschitz continuous w.r.t 0 i.e
V2 00 (v.)) V2 V. HK (v)) < L'110* 6 (v)ll
(38)
2 where, L" L 12 Hs L2 + Lsg and Lys = L, H?. Here, X2 is a constant defined in equation
(85), and other constants as defined in statement (ii).
22

---

Published as a conference paper at ICLR 2024
The proof of Lemma is in Appendix G.2. To prove this result, we start by considering the value function expression, and evaluating it's gradient, Hessian, and Jacobians. After expanding each of them, we separate the reward and policy-related terms and then utilize the aforementioned assumptions to upper bound them, respectively.
Lemma 4. Let us define the update direction associated with the gradient in (13) as
H
(1(7)=-U(T)
V2 O.NK
(39)
0.0
H and 22(T) :
e. V. (0) 0 (0) (v)))
(40)
1=0
Under Assumptions 1 14 it holds that
(T) & Huun 10 (v) 0 (v)ll:
(41)
where "1 == KLL + Lu + L" 1 Here, û is the upper bound of utility (T) defined in (4), l L are policy-related Lipschitz parameters (cf. Assumption 3), L' and L" as defined Lemma 3, and mixed condition number defined in equation (109) and Lv,0 upper-hound of the norm of second order mixed jacobian term, defined in equation (107)
The proof of Lemma 4 is in Appendix H.6.
F PROOF OF THEOREM 1
Without loss of generality, for the analysis, we consider the algorithm updates as if we are minimizing the upper and lower level both.
Proof. We begin by the smoothness assumption in the upper-level objective (cf. Assumption 18), which implies that
+ (V.G(u, (v:)), u4t1 vz) + T. |1 11l1 (42)
Giv 8r (v++1)) S
From the update of upper parameter u++1 (cf. (14)), we holds that
G(ve+1, 8* (v(+1) SG(u,, (vi) V G(v, (, au Gln, 0K ((x)))
(43)
Lga Giu, 8 (v:)))1² 2
+
We add subtract the original gradient V V,,G(u, 0" (vi) (ef. (13)) in (43) as follows G(ve+1, 0² (I)+ SG(M,, (f))) (V, 0 (u:)), aa G(v, aa (,, (u:)), V.G( (vi) 0"
(44)
Lga V
(vi)) + G.G(u,, 0 (v+)) - O
2
0 a. V G(m, 0" (v:))]1
(45)
a. (V, 0- (v:)),
0³ (v:)) G,,, V.G(u, 0*
L, Gv,, 0 (v.) + G,G,,, 0* (v:)) - (
Using Peter-Paul inequality for the third term on the right hand side of (45), get
G(ve+1, 0* (v++1)) ( a. V.G(v, 0r (v:)))1 +
O
(46)
201
anCi
V. Gu,, (7 G.G((r, 0 (u,))l
2
L
400 V.G(u,, + F.Glu,, 0 (kx))) V.G(M,,0'',,))
2
23

---

Published as a conference paper at ICLR 2024
where 0j 2 O. Next, after grouping the terms, we get
G(v++1, O (v++1)) SG(M,, 0 (v:) duu 1 1
OVG((,,
201
anCi
V Guu, 00 (v4) V.G(u,, (vx)))
2
+ V 0 (v1))] + ا V,, 0 (vi)) (
1- 1 -1---, Ln (V
-G(u, (vi)) - au
Ly
2c1
+ aau ( + 1, VVV, 0 (v)) - o* (v:))
C1
(47)
where we use the inequality ||a + 611² S 2||a|12 + 2|16|| followed by algebraic operations to get the final expression of equation (47). Next, we analyze the term [V, 0 (v,)) V,, (K,)), (1, from equation (47). It is important to note that the dependency of the lower optimal variable on the sampling distribution of the upper objective is novel compared the standard class of stochastic bilevel problems and requires novel analysis which we emphasize in the subsequent sections. Let us start by considering the explicit expressions of V, 0* (v)) and V.G(vs, 8* (ve)) in equations (13) and (14) as
V,G(M, (v) - G, (v)) B -B (x)))) (12)(
(48)
where we define
(T) (T)()
(49)
Ha
and (2(T) =U.(T)
v VeVVV
8*
(0) (1))) V.U.(T).
(50)
Now, we expand the terms in (48) by adding subtracting the term E, (x))(( in the right hand side as follows
V,G(u, Gl,, (v))) -E (en (or
(51)
+ E E (w)) |0 (r) 1
=E (x)) 01 (T) - (
+ + |0 d2((T].
(52)
This is an extremely critical point of departure from existing bilevel algorithms where we characterize the complexity in the sampling distribution (mentioned above) by breaking into 2 parts and introducing notion of probabilistic divergence the analysis. We note that the first term on the right-hand side of (52) can be written as:
Er-p((re (1))) [o (r)] - EE (n)) (T) S sup (w)) Erppprax (oy) (T)
dEF
(53)
This boils down to the standard definition of Integral Probability Metric(IPM) which, under suitable assumption on the function class F can generalize various popular distance measures in probability theory for ex Total variation, Wasserstein, Dudley metric etc. For a more detailed discussion on the connection to f-divergence and IPM, refer to (Sriperumbudur et al., 2009). Specifically, for our analysis, we will be dealing primarily with a subclass of f-divergences that satisfy the triangle inequality as D (p(p, q) < (p) + D (r,4) q) which includes divergences such as Total variation or Hellinger distances. Specifically, we show that under certain boundedness conditions on the function class o E F || < Ç. we can upper- upper-bound bound the divergence which is a critical and interesting point of our analysis. Interestingly for the Reinforcement learning problem under study, satisfies such boundedness condition which we prove in sections. Thus we were able to utilize the special structure in RL to solve this special type of Bilevel problems.
24

---

Published as a conference paper at ICLR 2024
On the other-hand, the second term the right-hand side of (52) is expected difference between the two functions. Hence, we can write (52) as
V.G(u, G(u, o (v))
(v)))
+ ( Φ2(r)),
(54)
where Dy denotes the f-divergence between two distributions. Taking the norm on both sides and from the statements of Lemma and Lemma 4, we write
11 V GV,,(,,, - G.,, (v)))
+ 22H (10(()) - 9* (v)11.
(55)
2
Utilizing this bound in (47), we get
(0V++1,0(14+1)))
-G(r),0((1))
1
S 00a
201
H2 + 211
+ au
C1 + Lear))
- -
(56)
2
2
where write the final expression for the convergence analysis from equation (47)
and for simplicity of notations, let's assume d1 aa (1- 2 an and å2
Ou ( Tugau)
(²2
12 + 2H715277) which leads the simplified version of the equation (56)
G(v++1, 8 (v(+1)) G(v,, 0 (vi) I VV 0* (vo))lI 82 (vo) a (v))11.. (57)
From the statement of Lemma 2, we can upper bound the above expression as
17 L6 7, C(vet1,0(ME44))) G( 0 < -h V...V.V.. (v:))) dr
(58)
1
where we know 17 E (0, 1). Next, select K + obtain
17 Lo Z.
0(ve+1,0' G(u,, 0r (v.) < -2 V V. (v,)) +
(59)
P
Taking the summation over to on both sides, we get
G(vT, (' G(vo, 0" (vo)) S -1 O 8gL6Z T-1
Σ 11 1+
(60)
1
After rearranging the terms, we get
0 G(vo, 0'0,))))))) G(VT, -G(UT, (vT)
n02L0Z T-1
Σ
81
81
1
G(vo, 0* (vo)) G(VT, (UT)
1022
(61)
81
8,11(1 - n)
- where G* denotes the global optimal value of the upper objective. After dividing both sides in (61) by T, we get
Let us denote Go == G(vo, 8" (20)) and upper bound -G(rT, (G((T,0'(pr)) (
Go G
L6.
(62)
8
T8, -m
25

---

Published as a conference paper at ICLR 2024
G PROOF OF LEMMAS
G.1 PROOF OF LEMMA
Proof. The probability distribution of the trajectory {sh, an |i is given by (as defined after the equation (3) in main body)
H II 1=1
(v)
no- (o- P(s41llhh an).
(63)
Similarly, can derive an equivalent expression for the probability of trajectory induced by the policy TT*(()) (v) by replacing (1() with 8* (v). Here, P(s a₂) the transition probability which remains the same for both and p(so) is the initial state distribution. Next, the f-divergence between the two distributions Dy(p(r; (v)), p(T; (v))) can be written as
(v))) s
P)(p(T:3), (v))). (64)
which holds by triangle inequality of the class of f-divergences we considered as discussed above.
p(T; represents the trajectory probability induced by another hybrid policy 7 which executes the action based on the policy Ta*(() (v) (-Is) for the first time-step and then follows the policy (T- (+15)
for subsequent timesteps. Now, we focus on term in (64), we get
((T;
Σ ((T
(65)
p(T:
((su) (() (s)) au) II To ( (t an)
E(TT;))
(( (())))) (o) I To (o)
To (w)
E(T:3))
(g)( (an
where first we expand upon the definition of the trajectory distribution induced by both policies and get the final expression of the equation (65). By expanding the term p(T; (3) in (65), we obtain
To. (w) Tax (c) Σ ao
Dy(p(T:0 (x)),
Σp(so)
Σ P( ao)
(o
80
(a-(w)(als)
= Σ p(s) Σ (alss
(als))
(a-(w)(als) (als)
Ep(a)
= Ep(o) (())))
(66)
where, the first equation we expand upon the sum over all trajectories with the occupancy distribution states and actions, and replacing with f-divergence, we get the final expression.
26

---

Published as a conference paper at ICLR 2024
Next, we expand similarly for the term II in (64) and expand as
P(T:
((::
= [p(t:O"(v)))) (v)))f
p( 0K (v))
((so) P() ao)
II To (w) (an (s ( (hh an)
-M(T;O"(uN)) (w)))S
Po(SO)TOO (w))) ao)
II Tox (a))s)))))))) ((5++ (sh, an)
h= To (z)
an)
Ep(50) Σ (a0 Σ P(si(s0: 0n)
mh= TT (ox (0) (( an)
4g
a1
81
Σ To Σ (l) (v), ((T
Σ ((5))
((T1;0K(M))
Σ p(5))
(v)).
(67)
where we expand the trajectory distribution induced by the policies and subsequently express as the ratio of the probability of trajectories wrt 7ı, get the final expression. Now, expand upon the f-divergence of the trajectory Tı distribution as
(v))) D)(p(T; 0), P(; 8* (v))))((())))))))))))))))))))() = Σ p(so) Σ Tok
(v))
(68)
p(5o)
(arm
Dj ()(T P(T
where using the triangle inequality and get back the similar form with which we had started in equation (64) similar to term and term II. Here, similarly continuing this expansion, we finally get
H-1
Dy(p(T;0 0" (v)) p(T;0 (v))) <
Σ Eapp" ix (v) (0) (om
HE
(o)) Dj
H
Pak (v) (8) (
- HD
(69)
where, we upper bound the first equation by the total number of timesteps or horizon length H of trajectory and subsequently upper-bound the divergence by the state (8,a) pair for which the Dy( (w) (a s), TT* (w)(s))) is maximum and is given as (s', a'). Next, in (69), by considering the total variation as the f-divergence (it falls into the class of f-divergence under consideration) and expanding using definition with countable measures obtain
D((p(::0 (v))) < HDrv(To (a')ss)
H
< [T (a'(w)
2
HL2 |0 (v) -8
< 2
(70)
where, the saudient-boundedin condition the score function (cf. Assumption 3) on the policy parameter to get the final expression of equation (70). We note that the result holds for any general horizon length H.
27

---

Published as a conference paper at ICLR 2024
G.2 PROOF oF LEMMA 3
G.2.1 PROOF OF LEMMA 3 STATEMENT (1)
Proof. We start with the definition from (17)
T
Hr Σ
V2 Vo 0 (v)) = E((T; (vs)
Vuron (sh,
Σ
Vo log n (v))(a))))))
h=0
T
Me
h
%/. Vuru (5h
Σ j=0
Va log TON (en
Σ p(T= (vi))
h=0
T
Hi / (s
h Vo log TO ( (d5sss))
(71)
where r' = [(s6, d6) (s/, represents the trajectory for which the lower product term is maximum and thereby upper-bounding with that leads to expression in equation (71). Next we upper-bound the norm of the Vo 100000(((0)))) (vt))l as
||
V Volu, 0* (v+))l S
Σ
h (u
Vo log Tok (o (d5l(()))
h=0
Σ
/h V (5
Vo log Top (n) (d)()))))))
h=
< L,B
(72)
where apply the fauchy-Schwanl inequality get the inequality in the second line. Subsequently. we apply triangle inequality with reward boundedness assumption from Assumption 2 and bounded score function of the policy from Assumption get the final bound for the mixed hessian term. O
G.2.2 PROOF OF LEMMA 3 STATEMENT (1)
Proof. We start by considering the term
(v, ViValu, 0 (v)) = B (11) (w))a))
(73)
where we define
Hr Σ
fi(T)
-h h-1 Fv, (Sh, (sh,
V log Te To. (ag(8)))
(74)
K=0
He
f2(T)
7 h-1
Tu, (sk, ax)
v log Tox(w)
(75)
A=0
Subsequently, we write the norm of the equation (73) into parts as
= [Bp(re (T) - E Excro + + B - Be(ror
7 + [|
(76)
First triangle incquality and then add and subtract E ex( (un) to get the expression
where, Ti (w)(::0(w))f((T)) ( (T) and T2 = EE (x(r: (i - (x) (2()). This is an interesting point of departure from existing Bilevel analysis where the stochasticity is
mainly iid noise. Hence to deal with this, we separate the terms 1. divergence b/w two probability distributions and 2. expected diff b/w two functions under the same distribution. We next, upper-bound the individual terms get the final Lispehitz constant.
28

---

Published as a conference paper at ICLR 2024
First, focus the first term of inequality i.e 1 given
T p (v)) (T) (etrax(onf((T)
(77)
S pupplBptrio (v)) (n) - (o(Ti)(
S Xidrv 0 (V)),
H
S X: 2 L2 (2) 8 (w)ll-
where we first upper-bound the expression to a standard Integral Probability Metric form by taking the supremum and then dividing and multiplying with the norm of the function given by X1 = fI H1 RL, from equation (96). With that, we get the expression as the of Total variation distance(by definition (Sriperumbudur et al., 2009)) in the third inequality. Then, we upper-bounded the total variation using the results from equation (70) to get the final expression. Note that, in equation (70), we have shown for any general H, which will be H1 for our case.
Now, we proceed to the second term of the equation T2 and derive an upper bound as
T2 = EphE Ol (V))(((F) (2((T)
(78)
S f((T)) fe(TT)
Σ h-1 Tv, (sh: an)
Σ v log To (((a)))))
V log (a
where we consider the trajectory r' in the sum with the maximum value and upper bound by that and expand the definition of /1, S2 to get expression equation (78).
He
[T2
Tv. (sh, an)
(V) log To (v) - Vă log Tox (w)())))))) || (79)
0=
h-1 Tvc (sn, (sn an)
V log To To
1=0
1-1110 -1 (sh,
(1V3 log To- (o)
v log (og
H:
< h-1 || (8h, an) Hz)l - 0 (v)ll
h=0
= L2 (v) g (v)ll.
where we use Sauchy-Schwartz and triangle inequality repetitively to get to the third inequality. Next, we use Assumption 3 on the Hessian Lipschitzness of the score function and the bounded reward norm max(...) (s, a)ll R to get the next inequality. Finally, we use the upper bound on the geometric series obtain the final expression. Adding equations (77) and (79), we get the
where, L' = LI H (v))
(V
& L' L'(10" (v) - (v)ll
(80)
L2RH
G.2.3 PROOF LEMMA 3 STATEMENT (II)
Proof. We start by considering the term
(e,.V(( V S Epcre - E Eplrox (on)((r))
(81)
29

---

Published as a conference paper at ICLR 2024
where we define
r
Hi
Hr
fa(T) = 7
Vuru(sh
Vo log To (w)(())))))s)
(82)
h=0
[4() Σ 7
(uru(sh,an) an)
Va log (o Σ
(83)
Subsequently, we write the norm of the equation (81) into 2 parts as
VV,,, (v)) Vi,V, (v)) S [ (v)) E
(84)
+ (s)))(TT)) (o(rax(
$ | + [Tall.
where, T3 = Ep(r:e (v))) [3(T) p0 (TT) and T. = E EM (v)) - Ex(r:n (V))(()))
We next, upper-boum the individual terms get the final Lispchitz constant.
First, we focus on the first term of inequality i.e T3 given as
T3 Ep(r:
E =x S SuplE (v)) (e80))-pppittoop (o)t()())((())
(85)
I X3dTV (p(T,) 0- (v)), He L2 21) 8 (v)l
S X3
where convert the incquality first to standard Integral Probability Metric form by taking the supremum. Then we divide and multiply with the norm of the function fa given by [| = X3 H2 BL, from equation (95), and then we get the final expression in terms of Total variation distance (from definition (53)). Then, we upper-bounded the total variation using the results from equation (70) get the final expression. Now, we proceed the second term of the equation T44 and derive an upper bound as
(V))(f((T)- Ta (V) fa(r))
(86)
< -
T
H1
Hr
= Σ
h-1 (sh,
Σ
Vo log (w)
Vo loggor
h=0
where we consider the trajectory r' in the sum with the maximum value and upper bound by that to get equation (86). Next, we upper-bound the norm ||aa|]
f1
[T4|| <
Veru(sn, an)
Vo log (a3( - Vo log (ogg
Vo
h=0
Hr
h-1 Vuru(Sh, alll
Vo log Tg. (v) log
h=0
Hr
h-1
Vurr an an) (k (v)ll
hm
LZ 0* (v)
(87)
where we use Bautch-Schhaare and triangle inequality repetitively to get to the third inequality. Next, Assumption 3 the Lipschitzness of the gradient of the score function and the bounded
30

---

Published as a conference paper at ICLR 2024
reward R (cf. Assumption 2). Finally, we upper-bound sum of this geometric series obtain the final expression. Adding equations (85) and (87), we get the
Vu, (u)) Vo 0 (v)) = (*()))
(88)
where, L" = L Hi LL
H ADDITIONAL SUPPORTING LEMMAS
H.1 PROOF OF LISPCHITZNESS AND BOUNDEDNESS CONDITION FOR Ji(+) DEFINED IN (74)
Here, we prove that the function denoted as fi(0*(v)
THe E Tyn (5hs ah)
(E log log Te- (w)((a)))))) is Lispehitz continuous w.r.t I with Lipschitz constant L,, i.e
Ilf (0 (v)) ((0KK(()))) = Ly (10 (v)1l.
(89)
First, we begin with the different term as
[((0(1))) (i00
E nh h- Te (sn,
V log To. (v) - Volog Volog
A=0
(90)
Subsequently, taking the norm get
(1 -
H4 ? h Tr,
h
(shy
Σ
V log To (w)(())))))))))
h=0
1=0
He
h
A-1 (sh: an)ll
V log (ogms(())(())))) V log log
7
4=0
Hr
Σ 0=0
7 h-1 (sh, an) an)l - 8 (v)l
<
L211 - 0 (v)ll.
(91)
where Cauchy- Schwartz and triangle inequality get the subsequent expressions. In the third inequality, we use the Hessian Lipschitzness assumption of score function of policy parameters from Assumption 3 and finally using the boundedness of the reward values and upper-boundie the Geometric series, we get the final expression. Thus we show that fi()) is Lispchitz continuous w.r.t with Lipschitz constant Ln L.
Similarly, we can derive the boundedness condition on the norm of the function [)] vO as
H Σ
lffil
カ-1
Twe (sh. an)
v log Te(ay)ss))
(92)
h=0
T=0
Hi
Fuc (sn. and
7 h-
v log (a(())))))))))))
h=0
< RT= x1)
where first use Cauchy- Schhwrr and triangle inequality and subsequently the bounded reward assumption (2) and Hessian Lipschitzness assumption of the score function of the policy parameter from assumption (3).
31

---

Published as a conference paper at ICLR 2024
H.2 PROOF or LISPCHITZNESS AND BOUNDEDNESS fa() DEFINED (82)
Here, we prove that the function denoted as
T
Hr
(v))
Vura(Sh. an)
Vo log (o)
h=0
Lispchitz continuous w.r.t 0 with Lipschitz constant I. i.e
Il (v) fa(0* (v)) - 11 11,110011 0k (v)ll.
(93)
First, we begin with the difference term as
fa(0" (v)) fa(O"()) (V))
(94)
2
Hi Σ b- an)
Σ Vo log (w)(s)())ss) Vo log (
Subsequently, taking the norm, we get
|l (v)) - fs(00 (+))1
Hr
T Σ Vo log (w) V Vologmen (ologoor
||
Σ
7 h-1 Vuru(sh,
[1hh aill
(I log oo. (v)(a)(s;) Ve Volog (o
Hr
$ H 8 (v)il
h=
< I., H - 0 (v)ll-
(95)
where we use Cauchy-Schwartz Schwartz and triangle inequality repeatedly to get the subsequent inequalities. In the third inequality, we use the smoothness assumption of the score function of the policy parameters of Assumption 3. Finally, using the Assumption 2 i.e reward Lipschitzness and upper-bounding the Geometric series, we get the final expression. Thus (0 (v)) Lispchitz continuous w.r.t é with Lipschitz constant L5 LH
Similarly, we can derive the boundedness condition on the norm of the function I- vo as
T
Hr
||/a||
Σ
h-1
(err(sh)an))
Ve log To (osl))))))))))
(96)
h=0
Hi
-1
7 h-1 Verr(sh, on)
Vo log To (o)
h=0
< Hi (L, X3)
where, first we use Cauchy- Senehh--cc and triangle inequality and subsequently using the Lipschitzness property in reward function assumption (2) and bounded score function of the policy parameter from assumption (3), we get the final expression.
H.3 PROOF OF SMOOTHNESS CONDITION ON THE VALUE FUNCTION
Here, we prove the smoothness the value function i.c the gradient of the value function is Lispchitz continuous w.r.t 0 with Lipschitz constant L,, We begin with the definition of the gradient difference
32

---

Published as a conference paper at ICLR 2024
of the value function from the equation (15) as:
VoV((u,(())) VoVa 0 (v) (1)) V((7) (n))
(97)
(p)) Vi(T) (e) ((()
Bp(r:0K(()) [Vá(T) V2(T)]
Eg Ez,
where, first we substitute
He
H
V1
Σ
7 b-1 rvu r an) an)
V log To (m)(()))))
(98)
h=0
1/2
Σ
b- rmn 1
(8h, an)
Σ Vo log (g
(99)
k=0
Subsequently, by adding and subtracting E. prr (v)) (T) we get the final expression, where E₁ V2(T)). Now, first, we derive
(p(r: (v)) (T) - (x(r (T) and Σg E
the Lipschitz constant for V1 as
(1) - Vi (V))
H1
/ (Ir,, (sn, an)ll
Vo log (m)((()))))))) Vo To (on)
S H RL 8 (v)ll,
(100)
where we first use Cauchy-Schwartz and triangle inequality get the first inequality. Next, we upper- bound the reward with R from Assumption 2, Lipschitzness of policy gradient from Assumption and finally upper-bounding the Geometric series, we get the final expression. The Lipschitz constant L5 = HH RL1
We can subsequently upper-bound ΣS with the total variation distance
Σ I (up (x)
(101)
< Lşdıy (p(:: 0k (11)
< Ls HL2
2 (v)-0K(v)))
where first we divide by the Lipschitz constant of the function and subsequently upper-bound with the Total Variation distance. Finally, we substitute the total variation distance expression from the equation (70) to get the final expression. Now, the second term can be written as
Σg E (V)) (T) - V2(r)] & Vi(T') V2(7'),
(102)
where we take trajectory with the maximum difference and upper-bound the term. Subsequently, || S [[Vi(r') - [3(r')] = HL,,, (10*(v) 0K (И)l from equation (100).
Finally, the norm of the gradient difference of the value function from equation (97) as
VoVa(u,0'())) - VoVa(u,, 0 (v)) < (e) - 0k (v)l
(103)
where T.g Tog HL2 12 L.s and To5 HHRLO,
33

---

Published as a conference paper at ICLR 2024
H.4 UPPER-BOUND THE NORM HESSIAN THE BILEVEL RL
Here, we prove an upper-bound on the norm of the hessian defined in (16) given as
H
h
(VVa 8 (ur)) = Bp(r:0k(uo)) (ve))
Σ A=0
7th h- 1r (sh,an))
Σ
v log To (om
(104)
He
? h- Tin (5hi an)
V log TOx (v)
[x(T:
h=0
He
He
? 1n-1 (Shr (Sh an)
v log T (x)
h=0
where, first upper-bound the expression by considering the the trajectory which has the maximum lower-value and Σ, p(T; 0K (vt) = Next, we, upper-bound the norm as
He
VV 8* (v+))) S
Σ h=0
h- (8h, an)
V log TOp (m) |I
(105)
He
h (8h5 az)l
1&3 To Σ
h h=
S H RL
where, we first upper-bound with successive application of Cauchy-Schwartz and Triangle inequality get the second inequality. Finally, with the upper bound on (sh; an)ll S R from Assumption (2) and smoothness condition on the policy gradients from Assumption and upper-bounding the geometric series, we get the final expression.
H.5 UPPER-ROUND ON THE NORM OF THE 2ND ORDER MIXED-JACCOBIAN TERM FOR THE BILEVEL RL.
Here, we prove upper-bound the norm of the mixed second-order Jacobian term defined in (17) given as
Hr
Vo (v1)) = E p (
V VeTu (sh: an)
Σ> Vo log T (ox
Hr
h log TOp (os
V w.' (8h,
Vo Vo
(106)
0=
where first upper-bound the expression with the trajectory which has the maximum lower value. Next, we, upper-bound the norm as
H
1/ Vo 80 (v.))l <
V Votu, (sh, an)
Σ Ve log Tor (o.
II
(107)
k=0
V nr (Sh, all
V log To
h 0
H B,
where first upper-bound with the successive application of Cauchy-Schwartz and Triangle inequality to get the second inequality. Finally, with the upper bound on |/V,,, (8), a,)l < L, from smoothness condition on the reward function from Assumption (2), bounded score function of policy parameter from Assumption and upper- bounding the geometric series, we get the final expression. We denote Tyy, HP T,p B for simplicity.
34

---

Published as a conference paper at ICLR 2024
H.6
PROOF oF LEMMA 4
Proof. Let us start by first deriving the upper bounds for the terms Φi and //2 as defined in the equation (54) as follows. For Φ (7), have
h=
(108)
We define the term A which explains the relative conditioning of the two matrix norms. We define the mixed condition number as
V b ( (v))
HLL,B
K
(109)
4(1-7)
Next, upper-bound the second term relating the difference in 1| dbel in the equation, proceed first by upper-bounding the product difference
|||| || A2ll,
(110)
where we define
A V
(
(111)
A2 = v, Vi(u, 0 (V))
(v)).
(112)
Also, for simplicity of notation, let us take
1 = vZ Vo, 0 V3V.
(113)
and و = -V,,V. 8K (v)) VoV. 8* (x))-1
(114)
which thus (110) boils down to upper-bounding
A = 1/ VolA (v) Vo. (+))II
(115)
11 oo (v)) 1/1 (o (v)) ii Vofh((0( 1/ VoSh (w))
S Ve (v) Voln(O (x))) + 1111 - v2 Vell
S (v) (w)]l + Bl[ - 121l.
where, first we expand add and subtract the term 1/ Ve (0K (v)). and subsequently by applying Cauchy-Schwartz and triangle inequality, we get to the third inequality. For the final inequality, we apply equation and Lispchitzness assumptions on the score function of the policy parameter Assumption (3) to get the final expression in equation (115). Next, we focus upper bounding the ا/zll
second term of the expression specifically ||
|| - ا211 VVVi,VVl 0 (V) (v)) 1--1-122 V (V ("))) (116) + (V) (v)) - VVV. 8* (4) (v))
(1) -2N.
+ (V)V,,,((()VVVVV (v)) Vi,Va (1) (z)))
21 + 1/22,
where expand the definition of | 122 || and subseguently apply triangle incquality and Cauchy- Schwartz which then boils to upper-bounding the sum of two terms V2 + 12 For W21, we have
22 - || V V.
(V))
V V. (x))
(117)
< Lv -
= -moll In -,A.
- V (V) (1)
S Twooll (7, - (1) (x))))
Li 110 (10(w)) 8* (v)]l
12
35

---

Published as a conference paper at ICLR 2024
where Cauchy-Schwartz inequality and triangle inequality iteratively to get the final inequality. Next, we use the upper bounds and lower bounds the hessian and mixed hessian matrices defined in Assumptions to get the final expression. Now, Ln,0 = H from equation (107), L' L Xi 1 L2 L2RHi and Ln L2H1 R from equation (80). Finally, the second-term 22 from equation (116) can be upper-bounded. as
He
V
V. V.v, - V Vol,, 8 (V 0 (v))I L" 1 - -00 (v)ll
(118)
where, similarly we use triangle inequality with Cauchy-Schwartz to get the final upper-bound of equation (118). Now, L" = fa He L + LI,, and ns L, HI from equation (88).
Now, combining equations (117) and (118), we get the final upper-bound of the || - -/2l in equation (116) as
|| - w2ll S
LuoL' 12
T (v)
- 0 (v)ll-
(119)
Hence, finally replacing the upper-bound of U2 from equation (119) in equation (115) to obtain the upper-bound on the function difference term A as
Tuu I )100(()) - 8K (v)ll
A S kLI 10 (v) (8((())) (v)ll
+
(120)
12
L
= =m1100(w) - 0 (v)ll,
with 71 = KL + F + + Hence, with the above bounds, we proceed to upper-bound the term equation (51) ie [| ( o2(T))l as
|| [ 22(T)] - (T)) - (I(TT)
(121)
H-1 -U((T) (AI
H-1
H-1
<
u(Sh, an)ll
Σ A=0
(Ai - A2)
H A1
-2ll
H (100"(0) (v) 8 (v)ll.
where first we select the trajectory 7' with the maximum sum and subsequently using the Cauchy- Schwartz inequality we get the second equation. Based on the assumption of bounded utility u(s, a) S ú, v(s, a), get the third equation and finally using the upper bound of A A2 from equation (120), we get the final expression for equation (121).
H.7 PROOF OF LEMMA
Proof. Here, we derive an upper bound on the tracking term due to the use of surrogate gradients (vx) 0K (v.)l.. To begin the proof, we start with the smoothness in the value function shown in equation (103), as
Vo 0 (vx) < Va 0* (vx)) (VoV.(u, ( (kt)), (+())))
(122)
Lo
1 ( -0
2
where Lg = Lg H2 know that
+ Ls and Ls = HiRLe, Now, from the update of from Algorithm 2, we
2
g 8¹ (vx) at 8 6
(123)
36

---

Published as a conference paper at ICLR 2024
Replacing the update in equation (122), we have
Va 00+, (M,, 0² + (x)) (u0
2 az VVV, (x:)))
=Va(v,, 8" (vi) - ae (1- arLo
(1- 2
||VoVa(ve, (v)))ll
(124)
where we expand the expression after replacing the update in equation (122). Next, from Assumption we note that for the value function, it holds that
[V, 0 (v)) 2 (V,(u,00()) - (v)),
(125)
Assumption 4 ensures that the objective satisfies the gradient dominance or the PL condition, which can be satisfied practice for various settings. For instance, Assumption 4 can be satisfied in our setting for softmax policy parametrization Now, replacing the PL condition in equation (124), we have
Volue gh+ (v)) Valu,, (vi)) S -ar(1 acLa 1 (V. (x)) (v))
V=(1,00(M)) (v)))
a3 =-, (v))) V.(u,, (v))))
(126)
where, after replacing the PL condition in equation (124), we substitute 0s ar(1 arhe for 2
simplicity of calculations.
Valu,, gh+ (v)) - V. (v+)) s -1- (V, (v Va 10.000((n)) (ur)) - V. (" (vi)) S (1- (1-aa)* (V, (v:)) - V.(u,, (v:))),
(V,((
(127)
where the first equation comes from algebraic manipulation and applying the equation recursively, we get the second inequality, assuming S 03 S 1. Now, we note that from the smoothness of value function, have the upper bound
LB Vs(pe, 0v:) Volue, 0 (v:)) S ( 0
(128)
where Le = L3 HL2 + Lo. La 1L and we use the Lipschitz smoothness assumption and expand along the point vG, 8", for which the gradient term vanishes. Also, since PL. implies quadratic growth, it holds that
Valu, 0 (vx) - Va (v:)) 2 " -0 (v:))1
(129)
Now, substituting the equations (128), (129) in (127) to obtain
||0 (v.) 8 (1) < (1 az)) LaB 7.
(130)
1
where, Z = max, ||00 (x))) as as(1 a and Ls = Ls Heh2 + Ls and Ls H2 RL.
I DISCUSS OF ASSUMPTION 3 AND ASSUMPTION 4
Assumption 3 ensure certain properties of the policy parametrization such as Lipschitz policy, bounded score function, Lipschitz score function, and Lipschitz Hessian of the log of the policy. We remark that these assumptions are not restrictive and satisfied in practice for practical classes of policies. For example, this assumption is satisfied for softmax policy parametrization.
exp TT o(s. a)
(a|s))
(131)
En exp 0 á(s,a')
37

---

Published as a conference paper at ICLR 2024
where, first write down the expression of the softmax policy gradient parametrization with function approximation ø. Subsequently, taking log and taking the gradient w.r.t to the policy parameterization using chain-rule, get
Ve log To(als) 0(8, a) En exp(#f ((s
Σ exp(0" ((,,
(132)
exp(0" D(8 d'))
-(s a)
Σ
Eadexpi exp(0" 6(8 ( ((s,')
a'
=(s,a) Σ To(d'ls))(s,d))
(( Φ.
where we can denote G. = Ev To(a' (o('''))((ssa))))) Now, taking the norm on the LHS of equation (132), we get
Ve log ne [a|s]] < | a)ll + ((((sa)))
(133)
2(1
where we apply triangle inequality to get the final bound, which imposes certain constraints on the norm of the function approximation specifically [lø(s, a) S Çi which common assumption in various scenarios (Sutton et al., 2009; Maei et al., 2009). Thus this shows how for soft-max policy with function approximations satisfy Assumptions (3). where, we expand Va log Ty (a]s)
V (a)).
*a(a|s)
Assumption 4 ensures that the objective function satisfies certain geometric properties such PL condition. We remark that the value function satisfies PL. condition with softmax policy parametriza- tion (see Lemma8 (Mei al., 2020b)). Further, a property that we need for our analysis hold that the Hessian of the objective function has all non-zero eigenvalues. This assumption holds for softmax parametrizations, Now, in order to show that we first consider the softmax-paran pattaax-parametrizaaton considered in equation (132), we first compute the hessian
V log To (als) Volo(s,
Σ
(134)
Σ (o
= E, V lo
(s) o(s a''.
Now, finally, we substitute this to the equation of hessian of the value function in equation (134)
V3V,(u, (ut) E p(r)))
R((7)
V log nox To)
(135)
(0s)) - dls.))/))) }
0) E
R(T)
Σ
From the above, is evident to ensure non-singular eigenvalues, we need to ensure non-singularity for the function approximation matrix ΦØ² which has been standard assumption in several settings (Sutton et al., 2009; Maei et al., 2009).
J ADDITIONAL. EXPERIMENTAL. DETAILS
Implementation details of our Algorithm For the experiments, we use the same configuration of hyperparameters for all the baselines (Lee al.. 2021: Park et al.. 2022) including learning rate, optimizer, etc. PEBBLE with SURF improves the performance of PEBBLE significantly as also shown in (Park et al., 2022). However, it depends the quality and amount of augmentations used
38

---

Published as a conference paper at ICLR 2024
Hyperparameter
Value
Hyperparameter
Value
Initial temperature Learning rate
0.1
Hidden units per each layer
1024 (DMControl), 256 (Meta-worid)
0.001
Batch Size
1024 (DMControl), 512 (Meta-world)
0.0005 (walker)
Optimizer
Adam
Critic target update freq (51, 52)
2
Critic EMA т
0.005
(.9.999)
Discount 7
.99
Table 2: Hyperparameters of the SAC algorithm. We use similar hyperparameter configurations as in
(Lee et al., 2021; Park et al., 2022)
and the performance of PEBBLE+SURF varies rapidly. We used a limited amount of augmentations and pseudo-labels for a fair comparison. However, increasing the quality and amount significantly can improve the performance of PEBBLE+SURF. Hence, naturally leveraging augmentations in our unified framework with PARL will be an interesting direction of future research. We observed the effect of augmentation much more significant in DM-Control Suite than in MetaWorid. For the implementation, we have leveraged standard repositories like Torchopt (or BOMI Tensorflow) which are widely used to evaluate the meta gradient. We have also leveraged first-order approximate algorithms for performing and replicating our results, which improves the computation traceability, A rigorous and thorough evaluation of multiple other environments remains scope for future study.
K
ADDITIONAL EXPERIMENTAL DESCRIPTIONS
In this section, we describe the environmental setup and configurations leveraged in the experiment with more specific details. To demonstrate the performance of our algorithm we primarily leverage 4 environments (two Locomotion and two manipulation) from DM-control Suite (CTassa et al., 2018) and Meta World (Yu al., 2021) in the human prefrrecc--asse RL setting as also in (Christiano et al., 2017; Lee et al., 2021; Park et al., 2022). First, we describe the environments for the same
Walker (Tassa al., 2018) This a bipedal walker introduced in (Lillicrap et al., 2015) and later leveraged with some modifications in (Tassa et al., 2018) where the objective of the agent is to move forward as quickly as possible without falling down or pitching the torso too far forward or backward and the reward is combination of the above.
Cheetah (Tassa et al., 2018) Cheetah or Cheffhhhhtahhh as introduced by (Wawrzyíski, 2009) is a 6 degrees of freedom planar robot composed of nine links, eight joints, and two paws where angles of the fourth and the fifth joint are fixed while others are controllable. The objective is to make the cheetah run fast as possible and the reward is directly proportional to its forward velocity but only to a speed threshold. Later, this was leveraged in the (Tassa et al., 2018) with minor modifications.
Door Open and Button Press (Yu et al., 2021): These are taken from the (Yu et al., 2021) suite of 50 diverse simulated manipulation tasks all of which are contained in shared, table-top environment with a simulated Sawyer arm. For the Door open environment, the objective of the agent is to control the robotic arm open door with revolving joint for randomized door positions. Similarly, for Button press, the objective of the agent is to control the arm to press a button for randomized button positions. button random
Design Simulated Human Feedback. Although it would be ideal to evaluate the real-world ef- fectiveness of our algorithm based on actual human feedback, for simulation and comparisons on benchmark it is hard to collect large amount of human feedback. Hence, to emulate human feedback, we leverage simulated human teachers as used in prior research (Lee et al., 2021; Park et al., 2022), whose preferences are based on ground-truth reward functions which help to evaluate the agent efficiently. Next, we discuss simulating human preferences using the ground -tuuth reward model as in (Lee et al., 2021).
Let's say (s, a) represents the ground-truth reward function for state-action s, a in the environments as discussed above based the objectives, which are known Now, the perfectly rational and
39

---

Published as a conference paper at ICLR 2024
(a) Walker
(b) Cheetah
(c) Door Open
(d) Button Press
Figure 5: Figure demonstrates the visual representation of the environments considered in the experi- mental setup
deterministic human behavior would result in trajectory preferences (To, TI) ΣE r (s) (sssaa)) at)
(1,0) r a.) >
y
(136)
(0, otherwise,
where, superscript 0, represents the state-action in the trajectory To, respectively. However, human preferences always deterministic rational as discussed in (Lee al., 2021). Hence, the stochastic preference model can be written as
exp B 7 af))
P(ro 71;8,7]
(137)
cxp (B nH ( (s)) + cxp 2M-
where the preference model is the well-known Bradley Terry model (Bradley & Terry, 1952) E [0, 1) is the discount factor and is the rationality constant. For example, rational human, and 3 0 indicates a noisy/sub-optimal human producing random choices. To design further human-like teachers, various human behaviors like myopic behavior, mistakes, etc. integrated while generating preferences as in Lee et al. (2021): Park et al. (2022).
indicates perfectly
Now, the peteerencce-geeraatinn mechanism becomes clear, it is evident that the oracle reward in the plots indicates the ground truth r* generating the preferences. The upper-level objective deals with maximizing the likelihood of the human preferences received on the trajectories generated by the inner optimal policy under the current reward estimate. In all the environments, A-PARL achieves nearl performance framework, which considers the dependence (missing from existing literature) of distribution on the lower-level policy parameter during training the upper-level objective.
much faster time. This highlights the importance of our bi-level
40


Reviews:
[{"review_id": "binFhWCk2e", "reviewer": "Reviewer_fCoY", "summary": "[This review is submitted upon an emergency review request.]\n\nThe paper introduces PARL (Policy Alignment Reinforcement Learning), a bilevel optimization framework for addressing policy alignment in reinforcement learning. It identifies and aims to fill a gap in existing methods by considering the relationship between policy alignment and data generated from policy trajectories. PARL comprises an upper level focused on reward design and a lower level dedicated to policy optimization. The paper also presents a new algorithm, A-PARL, and reports improved sample efficiency in tests conducted in environments like the DeepMind control suite and MetaWorld.", "questions": "- What values of K and N were used in Algorithm 1 for the experiments?\n- Could you elaborate on how these parameters were tuned and the impact of selecting different values?\n- Specifically, how does a larger K value, which implies more accurate solving of the lower problem but at the cost of additional environment trajectories, affect the overall outcomes? What trade-offs are observed with varying K values?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper's approach to formulating preference-based reinforcement learning as a bilevel optimization problem is intuitive and appears well-reasoned. This framework effectively captures the influence of the lower-level policy optimization on the upper-level objective.\n\n- There is a commendable theoretical analysis of the framework and the proposed A-PARL algorithm, which contributes to the understanding of the methodology and its potential impacts.", "weaknesses": "The paper lacks empirical evidence to substantiate the claim that their method effectively handles the shift in policy distribution at the lower level. While it shows improved final policy return performances, more diagnostic evaluations are needed to conclusively attribute these improvements to the framework's ability to manage lower-level distribution shifts and alignment issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "iei2Yxq8tR", "reviewer": "Reviewer_nxvi", "summary": "This paper formulates the policy alignment problem in RL (PARL) as a bi-level optimization, where the upper-level optimization corresponds to reward design while the lower-level optimization corresponds to the policy optimization for the designed reward function. Solving the bilevel optimization is challenging, due to the complicatedness of computing the gradient for the upper-level optimization, requiring information about the optimal policy for the given reward function. A practical algorithm is presented with approximations that use K-step policy gradient updates, and sample-based estimation of Jacobian/Hessian. Convergence analysis is provided, achieving the rate of O(1/T). In the experiments, the proposed A-PARL achieves near-oracle performance in a faster time than the baselines.", "questions": "1. Please see the weaknesses section above.\n2. Though it was interesting to see the corrected gradient updates for the upper-level optimization, it was hard to interpret the terms directly. Could you provide some intuitive interpretation of the additional terms in the upper-level gradient ($\\tilde M^K(\\nu_t)$)?\n3. Without the $U_\\nu(\\tau) \\sum \\tilde M^K(\\nu_t) \\nabla_\\theta f_h(\\theta^K(\\nu_t))$ term in Eq (14), does A-PARL reduce to the existing method or not?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper introduces a mathematical framework for policy alignment in RL as a bilevel optimization, which includes useful applications like RLHF.\n2. A theoretical convergence guarantee is provided for the proposed method.\n3. In the experiments, it outperforms the baselines, showing better sample efficiency.", "weaknesses": "1. Empirical evaluations could have been more thorough. In Figure 2, only three domains were considered (2 manipulation / 1 locomotion), which is much smaller than the ones in the baseline papers. For example, in the PEBBLE/SURF papers, they conducted experiments in 9 domains (6 manipulation / 3 locomotion). I am curious if A-PARL still outperforms the baselines in other domains.\n2. Some part of the algorithm is unclear. For example, it seems that gradient/Jacobian/Hessian estimation (Eq 15-17) requires 'on-policy' samples for their computations. Still, I was first assuming the lower-level policy optimization is done using an off-policy RL algorithm, as in the previous work (e.g. PEBBLE). Then, is my understanding correct that upper-level optimization is done using on-policy samples while the lower-level optimization is done in an off-policy way? Does lower-level optimization also use on-policy updates (Algorithm 1 line 5 seems to perform on-policy updates)? If so, I am curious how the on-policy algorithm could have shown better sample efficiency than the off-policy baselines.\n3. Lack of ablation studies. For example, to see the efficiency of A-PARL more properly, it would be great to see the results using varying the number of feedbacks. In the current form of the paper, it is even unclear how many feedbacks were used or how frequently the feedback was collected in the experiments.\n4. Another concern is the scalability of the algorithm. Given that the method requires Hessians, it seems the complexity of the method is quadratic w.r.t. the number of parameters of the policy network. The method may not be applicable to the setting where the network size is large (e.g. millions of parameters).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gde2fIkAMR", "reviewer": "Reviewer_iimX", "summary": "The paper under review studied policy alignment problem of reinforcement learning.\nThe authors proposed a bilevel framework to improve the efficiency of the alignment and to better evaluate the alignment.\nAn algorithm was derived analytically to optimize this bilevel problem, and convergence to stable point was proved.\nIn addition, simulations was included to demonstrate the capacity of the proposed framework.", "questions": "1. On top of page 4, the author mentioned $\\nu \\in \\mathbb{R}^n$. What does $n$ represent here? \n\n2. In the paper, the authors used $H_l$ to represent the horizon of the lower-level trajectory, and $H_u$ to represent the horizon of the lower-level trajectory. Why there are two different horizons? are trajectories used for upper level resampled?\n\n3. On page 7, in assumption 4, what do $\\mu, \\hat{l}, \\hat{\\mu}$ represent?\n\n4. In Lemma 1, does eq 21 hold for any choice of convex function $f$ or a specific $f$? also $L_{\\pi}$ should be $L_2$?\n\n5. Suggestion: through Lemma 2 and Thm 1, there are too many constant symbols such as $L_1, L_5, L_6$. It might be a good idea to combine some of them together in the main text to make the statement cleaner.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The bilevel formulation of policy alignment problem is novel and interesting.\nThe paper is mostly well written, easy to follow (see questions below). \nThe theoretical derivation is novel and thorough.", "weaknesses": "1. The objective of the paper is somewhat confusing to me. \nWould the authors please clarify the cause of the misalignment that is considered? and what role does the human agent play?\n\n* Is there a fixed RL problem, but the agent can only get some feedback from a human who partially knows the real reward, and such \nfeedback changes over time as human learns more about the reward?  \n\n* or a dynamically changing RL problem is consider i.e. reward (value function) changes over time, \nand one possible cause of such change is due to how the reward is generated (feedback produced by a human's preference).\n\nMore precisely, the authors used $\\nu$ to parameterize the upper level (evaluating the lower level policy). \nWhat is does each $\\nu$ represent?\n\n\n2. My other concern is experiments are not detailed. Descriptions and simulation set up are all missing. For instance, figure 2, \nwhat precisely do 'walker' or 'door open' or 'button press' aim to do? \nhow does the misalignment occur? what does oracle represent? what are the upper level objective functions $G(\\nu, \\theta^*(\\nu))$ for these tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "cDn5CB3bl8", "reviewer": "Reviewer_fXDT", "summary": "This paper studies the policy alignment in reinforcement learning and proposes a unified framework, PARL, which is a new bilevel optimization framework to address existing problems in the previous works. Specifically, the PARL explicitly considers the dependence of the alignment objective on the data generated by policy trajectories (the alignment goal is evaluated on the learned policy, which also generates the data). In the algorithmic side, the authors propose A-PARL, which is provably efficient, to solve the problems under the PARL framework and empirical results are provided.", "questions": "see weakness", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 The paper first identifies a good point on the existing problem of the previous works. The argument that the alignment objective in the upper-level depends on the lower level through the learned policy is convincing and is clearly clarified. These arguments make the proposed PARL framework natural and intuitive. This is the main point I would like to recommend acceptance for the work.\n\n2 The paper further proposes an algorithm named A-PARL to solve the PARL problem, which is with sound mathematical guarantee under suitable assumptions and demonstrate impressive empirical performances. Based on the literature review, I think the baselines in the experiment part are competitive, which further support the advantage of the proposed framework and algorithm.\n\n3 The writing is good and the paper is easy to follow.", "weaknesses": "1 I am not very familiar with the literature of the benchmarks used in this area but I go through the papers along the line and confirm that the experiments conducted by the authors are commonly adopted in the literature so I assume that the experiments are satisfactory (which may need to be further evaluated by other expert reviewers).\n\n2 Could you comment on the generality of the proposed framework? In particular, I am interested in whether this framework can be extended to handle the alignment of language model because the reward model quality is the bottleneck in many cases and most of the existing approaches use only a fixed reward model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)