On the Sample Complexity Bounds of Bilevel Reinforcement Learning
Authors: Mudit Gaur
Utsav Singh
Amrit Singh Bedi
Raghu Pasupathy
Vaneet Aggarwal
Venue: NeurIPS 2025 poster ()
Keywords: Bilevel Reinforcement Learning
Sample Complexity
Gradient Descent
Bilevel Optimization
Primary area: reinforcement_learning
TL;DR: Provide First Ever Sample complexity bounds for a first order bi-level algorithm.

Abstract: Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models, yet its theoretical foundations, especially sample complexity bounds, remain relatively underexplored. In this work, we present the first sample complexity bound for BRL, establishing a rate of $\tilde{\mathcal{O}}(\epsilon^{-3})$ in continuous state-action spaces. Traditional MDP analysis techniques do not extend to BRL due to its nested structure and non-convex lower-level problems. We overcome these challenges by leveraging the Polyak-Łojasiewicz (PL) condition and the MDP structure to obtain closed-form gradients, enabling tight sample complexity analysis. Our analysis also extends to general bi-level optimization settings with non-convex lower levels, where we achieve state-of-the-art sample complexity results of $\tilde{\mathcal{O}}(\epsilon^{-3})$ improving upon existing bounds of  $\tilde{\mathcal{O}}(\epsilon^{-6})$. Additionally, we address the computational bottleneck of hypergradient estimation by proposing a fully first-order, Hessian-free algorithm suitable for large-scale problems.

On the Sample Complexity Bounds of Bilevel Reinforcement Learning
Mudit Gaur Purdue University
Utsav Singh ITT Kanpur
Amrit Singh Bedi' University Of Central Florida
Raghu Pasupathy" Purdue University
Vaneet Aggarwal*
Purdue University
Abstract
Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models, yet its theoretical foundations, especially sample complexity bounds, remain relatively underexplored. In this work, we present the first sample complexity bound for BRL, establishing a rate of Ō(e-3) " in continuous state-action spaces. Traditional MDP analysis techniques do not extend BRL due to its nested structure and non-convex lower-level problems. We overcome these challenges by leveraging the Dolyak-Lojasiewiee. (PL) condition and the MDP structure to obtain closed-form gradients, enabling tight sample complexity analysis. Our analysis also extends general bi-level optimization settings with non-convex lower levels, where we achieve state-of-the-art sample complexity results of Ōc--3) improving upon existing bounds of Ó(c-9). Additionally, we address the computational bottleneck of hypergradient estimation by proposing a fully first-order, Hessian-fres -free algorithm suitable for acage-scale problems.
Introduction
Bilevel reinforcement learning (BRL) has emerged as powerful framework for modeling hierarchical decision-making processes, particularly in the context of artificial intelligence (Al) alignment. Recent works, such those by [1, 30, 35], have demonstrated the potential of bilevel formulations to address challenges in reinforcement learning from human feedback (RLHF) and inverse reinforcement learning. Despite these advancements, the theoretical understanding of BRL remains limited, especially concerning sample complexity in parameterized settings. Most existing theoretical analyses such [40] confined to tabular settings due their analytical tractability, while empirical studies [9] are conducted in parameterized environments, leading to a disconnect between theory and practice.
A significant challenge in bridging this gap is the computational complexity associated with the hicrarchical structure of BRL. Practical algorithms often circumvent the need for second-order gradient evaluations to solve bilevel problems by employing first-order approximations [1]. However, these simplification raises critical questions about the theoretical performance loss incurred by such approximations in BRL. Therefore, understanding and deriving tight sample complexity bounds for BRL are crucial for guiding the development of more efficient algorithms and for assessing the trade-offss between theoretical rigor and practical applicability. To this end, present the first sample complexity result for BRL in continuous state action settings, achieving bound of ( This result extends to standard bilevel optimization problems, providing a significant theoretical contribution wixth practical implications.
Equul contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Key challenges and our approach. The theoretical analysis of BRL is not possible using the existing theoretical frameworks [15, 29, 11. 12, 13] used to analyze MDP algorithms with a known reward function. Existing bi-level algorithms are also ill-suited to the BRL setup since they require unbiased gradients [3. 18], which are not available in the BRL setup. Many bi-level algorithms [4, 19] also require the estimation of second-order terms such as Hessian, which make them computationally infeasible as well in high-dimensional setups. Some works in the field of BRL do employ the approximation of the second-order Hessian [1, 40J. However, these works are limited to tabular state spaces, Other approaches such as [30] use a penalty based reformulation of the BRL problem. This work is still restricted to the tabular setup. From theoretical standpoint, none of the works develop a method to analyze the sample complexity of the work for continuous state action space, works that have sample complexity such as [40] only do so for tabular state space. We overcome this challenge by (i) proposing a first-order BRL algorithm that works for continuous state-action spaces, (ii) providing the first-ever sample complexity results for BRL algorithm. We use a penalized bi-level framework with non-convex lower level initially proposed in [22] for standard optimization, but it is not straightforward to apply reinforcement learning settings, which is the main focus of our work.
In order to obtain our sample complexity result, we use the insight that the gradient parameter estimation step in the algorithm laid out in [2] (lines 3-8 of Algorithm 1) are an SGD step on a loss function that satisfies the Polyak-Lojasiewiie. (PL) property. We combine this insight with novel recursive analysis of the optimality gap (lemma 1) for stochastic gradient descent (SGD) with biased gradient estimate to obtain the first ever sample complexity result for BRL. We also demonstrate that our analysis holds for the standard bi-level penalty- -aase formulation of [22] with unbiased gradient estimates and provides state-of-the-art sample complexity results for the same (Theorem 1).
We obtain this result with our unique insight that the parameter estimation steps of the algorithm provided in [2], are gradient descent steps on a loss function that satisfies the Polyak-Lojasieww (PL) property. Additionally, we use the MDP structure to obtain closed form expressions of the gradients. This allows to obtain the first ever sample complexity of BRL. Our analysis also applies to the general bi-level setup as a special case where we obtaín state of the art sample complexity results of e 4.
We summarize our main contributions as follows.
Novel sample complexity bounds in BRL: We derive the first sample complexity bounds for BRL with parameterized settings, achieving bound of Ö(e-s). Our analysis addresses the challenges posed by non-convex lower-level problems and does not rely on computationally expensive second-order derivatives.
Generalization to standard bilevel optimization: Our theoretical results extend beyond reinforcement learning standard bilevel optimization problems, assuming access unbiased gradients for the upper and lower level objectives. For setups with non-convex lower-level problems, our method achieves a state-of of-thh-rrt sample complexity of Ō(E
We perform proof of concept experiments on Mujoco Tasks to demonstrate that the proposed first order algorithm works in practice.
2 Related Works
We first go over the prevailing literature the field of bilevel optimization. Once we have established a broad overview of the existing results in the field, we will lay out the existing results in the field of BRL and how they compare to the bilevel optimization results.
Bilevel optimization problems have been studied extensively from the theoretical perspective in recent years. Approaches such as [19] have been shown to achieve convergence, but with expensive evaluations of Hessian / Jacobian matrices and Hessian / Jacobian vector products. Works such as [33, 41] forgo the use of exact Hessian/lacobian matrices but instead approximate them. Works such as [21] do not require even the approximation of the second-order terms. However, in all of the aforementioned works, the lower level is restricted to be convex. In general, bilevel optimization with non-convex lower-level objectives is not computationally tractable without further assumptions, even for the special case of min-max optimization [7]. Therefore, additional assumptions are necessary for the lower-level problem. The work in [22] established penalty- based framework for solving bilevel

---

Table 1: This table shows a comparison of state-of- th-the--rt sample complexity results for bilevel reinforcement learning (BRL). Our result is among the first to establish sample complexity bounds for continuous state-action spaces.
Continuous Space
Iteration Complexity
Sample Complexity
References
[31]
X
X
[1]
x
(
X
[40]
x
O(c-1.b)
[30]
x
(
X
This Work
V
(
Ō(c-)
optimizations with possible non-convex lower levels with the PL assumption the lower-level function. The work in [2] obtained convergence in the bilevel setup with non-convex lower level with an improved sample complexity with respect to [22], where it obtained compared e Note that PL assumption has been used previously in fields such as optimization [20], RL [16, 14] as well as analysis of modern ML methods such as flow matching [17] and diffusion models [17, 34].
Bilevel reinforcement learning has been used in several applications such as RLHF [6, 39), reward shaping [45], Stackelberg Markov game [25, 32], Al-economics with two-level deep RL [43], social environment design [42], incentive design [5], etc. Another recent work [1] studies the policy alignment problem and introduces a corrected reward learning objective for RLHF that leads strong performance gain. There are a very limited number of theoretical convergence results for such a setup. The PARL algorithm [1] achieves convergence of the BRL setup using the implicit gradient method that requires not only the strong convexity of the lower-level objective but also necessitates the use of second-order derivatives. Note that in general the lower level of BRL the discounted reward which is not convex. The work of [31] employs a penalty- framework to achieve convergence for BRL setup using a first-order algorithm. Similarly, [40] establishes convergence by deriving an expression for the hypergradient without assuming convexity of the lower-level problem. However, it is important to note that all existing convergence results in BRL thus far do not provide sample complexity for continuous state action spaces. Despite the existence of sample complexity results for bilevel optimization with non-convex lower-level objectives in the broader bilevel literature without tabular state space restriction, such results remain absent in the context of BRL.
3 Problem Formulation
Markoy Decision Process (MDP). We consider a discounted MDP defined by the tuple M (S,A, Prr 7). where S is a bounded measurable state space and A is a bounded measurable action space. We remark that in our setup, both the state and action spaces can be infinite, though they remain bounded. In the MDP, P S x A P(S) is the probability transition function and To : S x A + [0, 1] represents the parameterized reward function, (ø E θ) where θ is a compact space. In order to encourage exploration, in many cases additional KL-regularization term is preferred. This can be accounted for by defining the reward function as
(s(s,a) ro(ss a) + (s,,
(1)
where hr (8t, = log
[x)) is the KL regularization term where मet is the reference
Rerrlas (s:)
policy. This form of the KL penalty is used in RLHF works such as in [44]. Note that our analysis works for any regularization term that is uniformly bounded. Finally, 0 7 is the discount factor. A policy म S + ((A) maps each state to a probability distribution over the action space. The state-action value function Q function defined as follows:
(3 =E
Σ r as = a0 =
(2)
For discounted MDP, we define the optimal action value functions as (3 a) sup (3, V(s,a) e A
(3)
x
3

---

We have the expected average return given by
J[b A) = Ran QTa (s, a)},
where the policy is parameterized as { A E A} and a compact set.
Bilevel reinforcement learning (BRL). With the above notation in place, we can formulate the BRL problem as
min G(ó, (=))
where X (²) = arg min - ((), X
(5)
where the upper-level objective G(Ø, A (o)) is a function of the reward parameter ó, while the lower-level objective is function of the policy parameter A. We denote the lower level loss function as -J( A) as opposed to [Ø, A) to keep our notation in line with the bi-level literature; a similar
notation is followed in [31].
Existing approaches and limitations. To solve the problem in (5), one popular approach to rewrite the problem in (5) in the following manner
min 4 ()) = G(Ø, (6))
where X ('(() arg min - ((),))
(6)
which is known as the hyper-objectivve approach, where is the hyper-objective. To solve it, we need the calculation of the hyper- greeiegt given by
V (6) = V G( (0)) v
where the term apart from the gradient of O is given as
v [V J(b Vo
(8)
This approach has been used in the existing literature [41, 33, 1]. Apart from having calculate the Hessian and its inverse, this technique requires that the lower-level objective J be convex. One solution, which is employed in [41,33], is to estimate first-order approximations of the Hessian. This because the calculation of second-order terms, which in many cases can get prohibitively expensive from computational perspective.
4 Proposed Approach
To avoid computationally expensive Hessians and for situations where the lower levels are not necessarily convex, penalty-based methods such as those developed in [22] have been proposed. Based on that, in this paper, we consider the proxy objective
=iimn min ((O) A) + J( (o)) )
2 =
(9)
σ
where a is positive constant. The gradient of (d) is given by
+ VoJ( (o)) V
V V. (o)
(10)
where X²(Ø) - A) and (Ø) arg miny - (J -) (G A)). For future notational convenience, we define the penalty function ho X) J( A) oGilo, A). key advantage of this formulation is the fact that, unlike the method involving the Hlyper-gaddeet,, it does not require the calculation of costly second-order terms. It is also applicable to setups where the lower level is non-convex. Despite these advantages, the theoretical analysis of this setup (even for the standard bi-level framework) is not well explored.
Remark (differences with [22, 2D). Existing analyses in standard bilevel optimization settings have achieved sample complexities of (c=- and Ö()- in [22] and [2], respectively. These results apply to bilevel problems without an MDP structure, where the lower-level objective non-convex but it is reasonable to assume access to unbiased gradient estimates with bounded variance for both

---

upper- and lower-level objectives. However, such assumptions do not hold in bilevel reinforcement learning (BRL), where gradient estimates are inherently biased due the underlying MDP dynamics. In this work, we develop a sample complexity analysis tailored to the BRI, setting. We also specialize our analysis to the standard bilevel optimization setup and demonstrate that our approach yields improved sample complexity bounds compared to prior work (see Table 2).
Algorithm development. We will describe the algorithm solve the problem described in Equation (9). We achieve this by implementing a gradient descent step in which the gradient is given by the expression in Equation (10). In order to estimate this gradient, we have to estimate the three terms VoG( (o)), V Vo X" (o)) and [Ø X (6)). In turn, these terms require the estimation of the terms X* (o) and (o).
For the gradient of J(ó, A) with respect to the upper level variable and reward parameter Φ, note that there was no existing closed-form expression. We show in Lemma 6 in the Appendix A that closed form of V [Ø,
(6,A) A) is given by
V (o)(
Σ 1=1
i- EV (8,,
(11)
Here, the expectation is over the state action distribution induced by the policy A. This expression is obtained by following argument similar the proof of the policy gradient theorem in [36]. Note that we can only obtain a truncated estimate for VoJ(ó, A), which will also lead to bias. In take average of this truncated estimate over B batches for more stable estimate. We define the sample-based average here as
Algorithm
B V (
Ao = B
Σ
(12)
1=1
where V (0, = Σド= Vero(sja, aj,). Here, ($),s, aj,)) are the 7th state-action pair of the jth trajectory sampled from the policy πΛ.
For the gradient for the lower-level loss function gradient JØ, A) with respect the lower-level variable À we use the policy gradient function to obtain
(o)( B(saa)aa' (Valoga(aals
+ E 3
Viltraa (Si, as)
(13)
Here d denotes the stationary distribution of the state action space induced by the policy zy- The second term the right-hand side is due to the presence of the KI. regularization term in the reward r()). Note that real-world applications of RL algorithms, such as actor-critic, the estimate of Q3 is not an unbiased estimate, but instead a parametrized function, such as neural network, is used to approximate it, leading to bias. Additionally we cannot sample the infinite sum ((e.,..oA)) Eisl VahTaarres (8i, 0s) but have to get a finite truncated estimate, which also leads to bias. We denote by VoJ X, n, B) the estimate of V V A)
VAJ(a, A, B) = V log (als) a:)
im
B
H
V Valte (8).in
(14)
B
Note that the estimate of () a) denoted by (s, a) is estimated using samples. For lever- loss functions, unbiased gradient estimates can be calculated, as demonstrated in [1]. For notational
5

---

convenience, we define
1 (o,(0, B
VG A, B)
(15)
where B is the size of the gradient sample dataset and VG; (0. A) the gradient estimate sample eth Note here that the batch size B and horizon length H can vary across the different gradients. We keep this notation the same across gradients with respect
and for notational convenience.
Now that we have expressions for the gradients of the upper and lower level function, we now move onto the estimation of (Ø, (o)) and [ (+)). Consider the term A (() which is minimizer of the function given by (0, X). Thus, it is obtained by performing a gradient descent on ho (Ø. A) with respect to A. Similarly, A (Ø) is the minimizer of the function given by [ A) and can be obtained by gradient descent. Note that these steps are performed on lines 4-7 of Algorithm 1.
The gradient descent step for the proxy loss function & P is performed on line 11. We estimate the gradients of G( A) and (Ø, A) with respect to & using the expression in Equations (11) and (15).
Algorithm 1 A first-order approach to bilevel RL
1: Input: S, A. Time Horizon T E Z. Number of gradient estimation updates for lower level E Z, sample batch size n E Z, gradient batch size E Z, Horizon length I 2, starting policy parameters Xg. 2 starting reward parameter du
2: for orrt {0..... ,T - do
3: for k E (0, ... 1- do
4:
d₂ = VAj(A, B.
5:
df VAJ(A c n, B) - a. o.V()
6:
A = N +
de
X sk+ ik
A + + d
7:
[d
8:
end for
di = V Vo KK B) 1 (Vol(or, MK, - Vo B))
9:
10: Φt+1 Φi - d.
11: end for
5 Theoretical Analysis
We begin by outlining the assumptions required for our analysis, followed by the presentation of our convergence results. We then provide a detailed theoretical analysis, explaining the derivation of these results.
Assumption 1. For any & E O, A E A and a E RR, we have the following assumptions
1. For all 0 < 5 ou. the function ha (ő, X) satisfies the inequality
[[Vho 2) ((, ho
(16)
where X; arg minxEA (hr (Ø, A)) and oo a positive constant.
2. The functions (sp. X) and J J(Ø, X) are Lipschitz and smooth in variables & and
3. The functions ha (p. A) and J( X) have Lipschitz and smooth Hessians in both & and X.
In [22], the first Assumption in Equation (16) was shown ensure that the proxy objective Φx (d) is differentiable. This assumption also exists in the literature [2] to ensure the existence of the gradient given in Equation (10). thus key for the setup given in Equation (9) to be solvable using gradient descent. The Assumption 1.2 is a standard assumption in bi-level literature used for convergence analyses [18, 2]. The Assumption 1.3 ensures that solving for the optimal point of the proxy objective L brings close the optimal point of the true objective db

---

Assumption 2. For any fixed À E A, o E o and 0 E ④ be the parameters of the neural network class used parametrize the Q, where is compact set, and i is a distribution over A. Then holds that
- (,,(,,)))Q"",,11))) S Capprox
min EE aaw DEG
Assumption 2 ensures that class of neural networks is able approximate the function obtained by applying the Bellman operator to a neural network of the same class. Similar assumptions are also considered in [10. 38, 15]. This assumption ensures that we are able find an accurate estimate of the Q function. This assumption accounts for the bias in gradient estimation, something not present in the standard bi-level setup. In works such [30] similar constant denoted by Coracle is used Assumption 3 (For upper level). For any fixed X, X1, X2 E A. o, Φ1, 02 E θ and (s, a) E S x A, we have the following properties
1. Vro(s,a)]1 C1
2. (logTx C2
3. Vrri (3, - (r a)ll S Calløi - Φ211
4. VlogTA, (s, a)- - VlogTx, (s, a)ll S CallA1- - -1ll
where C - C3 and C2 2 are positive constants. Additionally, there exist 6, E (0, 1] such that xa 8) E for all A and À A, and [ [ |) 2 for all E A
Similar assumptions have been utilized in prior policy gradient-based works [26, 29], well as actor critic algorithms, such as [10, 15, 11].
Assumption 4 (For upper level). For any fixed X E A and Φ E θ we have access to unbiased gradients
E[VŌ(0, -GG
(17)
and the gradient estimates have bounded variance
E| - E[V()) ]]][²² S <
(18)
The assumption for an unbiased gradient with bounded variance is present both in bilevel literature [22, 2] as well as BRL literature [1]. Works such as [31] simply assume access exact gradients of the upper loss function.
Main Result: With all the assumptions in place, we now ready to present the main theoretical results of this work. First, we will state the convergence result for Algorithm 1. This result establishes the sample complexity bounds for BRL which are the first such results of it's kind. Then, will go into detail about how these results are obtained, by providing a brief overview the techniques and lemmas used in establishing the convergence result.
Theorem 1. Suppose Assumptions 1-4 hold and we have O < <n EL OSTS t + where L, LJ, Lo are the smoothness constants of J and h respectively. Then from Algorithm 1, we obtain
T Σ (2()))) =o
(
+ +
(xp-x)
+0
+0
+
1 2H
+
+0
(19)
0²
02n
o2
+ ÖCCopprez)
(20)
set o² Ö(e). B Ō 2), n Ō T =( K Ö(log (?)) and H
Ólog (t)) then we obtain
T
(+ <Ō(c) + Õ (ppproz)
(21)
T
t=1
This gives sample complexity n.T.K.T + B.K.H.T + B.H.T 0
Thus we have obtained the first ever sample complexity result for BRL setup. Notably, this result improves on works such as [1, 31] in that our result does not require the state or action space to be finite, while also providing sample complexity and not just iteration complexity results.
7

---

5.1 Proof sketch of Theorem 1:
The proof is divided into two main parts. The first part is where we establish the local convergence bound of the upper loss function in terms of the error in estimating the gradient of o as given in Equation (13). This done using the smoothness assumption on Q. The next step is to upper bound the error incurred in estimating the gradient of Φ;, The gradient estimation error is shown to be composed of estimating the three terms on the right-hand side of Equation (9). The error in estimating each term is shown to be composed in estimating (Ø) (or X" (()) and the error due to having access to an empirical estimate of the gradient. the estimation of X (Φ) (or X (o)). A key insight here is to recognize that in the inner loop of Algorithm 1 we are performing gradient descent with respect to the parameter on the functions ( A) and ho (0, A). We use this insight in combination with the PL property from Assumption I to upper bound the error in estimating (6) (or X (Φ)).
Establishing local convergence bound for Φ: Under Assumption 1, from the smoothness of D, we have
(((++1) { + ((r)) 0+1 - di) + L - 2el..
(22)
Now, with step size
where an is the smoothness parameter of Φ, get
2L
T
(1))
Σ E - δ (
T
(23)
Note that V denotes the empirical estimate of the gradient of the proxy loss function o.. Note that we get the term (o²²) using Lemma 4.3 from [2].
Gradient estimation error: The enror in the estimation of the gradient at each iteration A of Algorithm 1 given by VV (((()) V (o:))). which is the error between the gradient of the upper objective V (Ø))) and our estimate of the gradient of the pseudo-objective V ( This error is decomposed as follows.
VoG(or, K B)]
2 < V -
A
+
E V V [br, (²) V J XK,BII B)ll
0
El/V 2J (0r, X (o) V Jor x B)|l
(24)
Thus, the error incurred in the estimation of the gradient terms can be broken into the error in estimation of the three terms, (G Xg (ot)), J X ((x)) and Jo (o.)). We first focus on the estimation error for the term VoJ , X (Ø)) where the error in estimation can be decomposed as
E J (2 Vo ( B) S Vo (z V X XT)I
+ V X;) - J(, X B)]]
(25)
The second term on the right-hand side of Equation (25) is the error incurred due to the difference between the gradient of J and its empirical estimate. This error is upper bounded using the defintion of the gradient given in Equation (11).
The first term on the right-hand side is the error incurred due to the error in estimating (o). In order show this, we write the following
E (or. (2 (o)))) - VoJ( X 112 < L.E - X 112
(26)
S Lo Lo hh (0r. (x():) - h ho X K ))
(27)
We get Equation (26) from the smoothness of [[ A) assumed Assumption We get Equation (27) from Equation (26) by using the quadratic growth property of PL. functions applied h (db A) also assumed in Assumption 1.
In order to bound the right hand side of Equation (27), we establish the following result.
8

---

Lemma 1. Consider an Lmoothhh differentiable function denoted by f(A) satisfying the PL property with PL constant μ. If we apply the stochastic gradient descent with step size 0 S 1j S +. then we obtain the sollowing
(f(A)) -
(28)
where AA E A, ((n) satisfies
E VIV(()) Vaf(Ae)) 3(,,, H)
(29)
and V (A) denotes the estimate of xx)( and X = ff
This result is obtained using recursive analysis of the optimality gap when performing SGD in the presence of biased gradient estimates. Using this lemma, we can bound the right-hand side of Equation (27) in terms of error in estimating the gradient of ho with respect to A. Thus, obtain
B/ha (0t. (o)) - ha (pr, X K s Ô (c-*) O(3(n, B, H))
(30)
where AA A, 3(n, B, HH) satisfies E V (dr, A) V Vhho AI(12 S 8(n, B, H). Using the expression for gradients of J( A) and G(o, )) we are able obtain the following result
2H
1
V V x I|2 sŌ(e +
+ Ô
δ (Capproz))
(31)
where is the number of samples used to estimate the Q function. The details of this are given in Lemma of the Appendix. For upper bounding the other two terms on the right-hand side of Equation (24), we use a similar decomposition and analysis. These are described in detail in Lemma 3 and Lemma of the Appendix. Finally, plugging the obtained expressions back into the right-hand side of Equation (24) and the resulting expression into the right- hand side of Equation (23) gives us Theorem 1. We provide an evaluation of Algorithm in Appendix F.
Standard Bilevel Optimization: A Special Case
In this section, show how the techniques used establish Theorem can also yield state-of-the-ar sample complexity result for standard bilevel optimization with a non-convex lower level (where the lower level is not an RL problem). The key distinction between our BRL setup and standard bilevel optimization is that is assumed that we have access to unbiased gradients with bounded variance [22, 2]. This is not the case in the BRL setup discussed in Section 4. We show that assuming access to unbiased gradients with bounded variance enables achieving a state-of-the-art sample complexity result for bilevel optimization.
The bilevel optimization problem is similar to (6), and is given as
min (Φ) == G( X E (o))..
where A E arg min - ( A).
(32)
As before, we solve the proxy problem in Equation (9) using gradient descent with the gradient expression from Equation (10). The key difference here is the availability of unbiased gradients for both the upper- and lower-level loss functions, captured in the following assumption. Assumption 5. For any fixed X E A and & E θ we have access to unbiased gradients
VV, A)] = VG(d, [ =.)] A)
(33)
(34)
and the gradient estimates have bounded variance
(V( E - 2)[l² s 2o0 E E - - 50
(35)
(36)

---

Table 2: If we assume access unbiased gradients, we obtain state of the sample complexity of e 3 for bilevel optimization without lower level convexity restriction.
Without second order
Iteration complexity
Sample complexity
References
Non-convex LL
[19]
O
(
[33]
O(e
O(e
[21]
Ö
[41]
Ō
Ö B)
[22]
Ō(c5)
Ō(c²)
[2]
O
Ō(e
This Work
Ō ((c3)
This provides the gradient estimate for the lower-level loss function, and Equation (15) is the gradient estimate for the upper-level loss function. Here, [ A) are independent sampled unbiased estimates of J A), and B represents the batch size. We assume that these samples of the estimate can be independently sampled. Additionally, we assume that this can be done for the gradient with respect to both À and ø. This is in line with other BRL works such as [1, 31j. We also define the following term
1 E (j.( B 1=1
VJ(Ó, B)
(37)
which is what we use instead of (J A, n, B) in Algorithm for the standard bi-level setup. For a bi-level optimization with non-convex lower level, obtain
Theorem 2. Suppose Assumptions and 5 hold and have 0 < मI
S +
S Tk S 1 where L, Ies, T are the smoothness constants of Vo.J and ha respectively. We farther La replace V (o, B) with [o, X, B) as defined in (37). Then, from Algorithm we obtain
T
T
1
(+))) < Ô
1 T
+
+
exp 0²
+
OBB
1
+
(38)
1=1
o² B Ö(E -2), T Ö(E -1), K =O(log (t)).
T
| (V |2 s Oc()
(39)
This gives sample complexity of B.K.T + B.T = Ō
Note the absence of the term ((Eappexx) as we have assumed access to unbiased gradient estimates for both upper and lower loss functions. As noted earlier, our result advances previous analyses of bi-level optimization with non-convex lower levels. [22] established a sample complexity of ((e-)) later improved O(c-0) ") by [2]. Table 2 highlights how our approach enhances existing results in bi-level optimization and brings convergence results from non-convex lower level setups to those of convex lower level setups such as [18, 41].
7 Conclusion
This paper established the first sample complexity bounds for bilevel reinforcement learning (BRL) in parameterized settings, achieving O(c-3). Our approach, leveraging penalty- based formulations and first-order methods, improves scalability without requiring costly Hessian computations. These results extend to standard bilevel optimization, setting a new state-of-the-art for non-convex lower-level problems. Our work provides foundation for more efficient BRL algorithms with applications in AI alignment and RLHE. Future direction include improving the theoretical bounds in this paper, and evaluating the proposed algorithm in different applications.
10

---

8 Acknowledgment
The work was supported in part by the National Science Foundation under grant CCF-2149588 and Cisco Systems, Inc.
References
[1] Souradip Chakraborty, Amrit Bedi, Alec Koppel, Huazheng Wang, Dinesh Manocha, Mengdi Wang, and Furong Huang. Parl: A unified framework for policy alignment in reinforcement learning. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
[2] Lesi Chen, Jing Xu, and Jingzhao Zhang- On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory, pages 947-980, 2024.
[3] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A timescale method for stochastic bilevel optimization. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 2488,2488, 2022.
[4] Xuxing Chen, Minhui Huang, Shiqian Ma, and Krishna Balasubramanian, Decentralized stochastic bilevel optimization with improved per-iteration complexity. In International Conference Machine Learning, pages 4641-4671 2023.
[5] Zhuoqun Chen, Yangyang Liu, Bo Zhou, and Meixia Tao. Caching incentive design in wireless d2d networks: A stackelberg game approach. In 20/6 IEEE International Conference on Communications (ICC), pages 1-6, 2016.
[6] 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.
[7] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
[8] Mucong Ding, Souradip Chakraborty, Vibhu Agrawal, Zora Che, Alec Koppel, Mengdi Wang, Amrit Bedi, and Furong Huang. Sail: Self-improving efficient online alignment of large language models. arXiv preprint arXiv:2406. 15567, 2024.
[9] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference on Learning Representations, 2018.
[10] Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy, In International Conference Learning Representations, 2021.
[11] Swetha Ganesh, Jiayu Chen, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. The 41st Conference on Uncertainty in Artificial Intelligence, 2025.
[12] Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal regret with novel policy gradient approaches in infinite-horizon average reward mdps. In International Conference on Artificial Intelligence and Statistics, pages 3421-3429. PMLR, 2025.
[13] Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach. In Forty-second International Conference on Machine Learning. 2025.
[14] Mudit Gaur, Vaneet Aggarwal, and Mridul Agarwal. the global convergence of fitted q-iteration with two-layer neural network parametrization. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 11013-11049, PMLR, 23-29 Jul 2023.
11

---

[15] Mudit Gaur, Amrit Bedi, Di Wang, and Vaneet Aggarwal. Closing the gap: Achieving global convergence (Last iterate) of actor-critic under Markovian sampling with neural network parametrization. In Proceedings of the 41 International Conference on Machine Learning, pages 15153-15179, 2024.
[16] Mudit Gaur, Amrit Singh Bedi, Di Wang, and Vaneet Aggarwal. On the global convergence of natural actor-critic with two-layer neural network parametrization. arXiv preprint arXiv:2306. /0486, 2023.
[17] Mudit Gaur, Prashant Trivedi, Shuchin Aeron, Amrit Singh Bedi, George K Atia, and Vaneet Aggarwal. Generative modeling with continuous flows: Sample complexity of flow matching. arXiv preprint arXiv:25/2.0/2266 2025.
[18] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Research, 24(167):1-37, 2023.
[19] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882-4892, 2021.
[20] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewicr condition. In Joint European conference on machine learning and knowledge discovery in databases, pages 795-811. Springer, 2016.
[21] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18113, PMLR, 2023.
[22] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In The Twelfth International Conference on Learning Representations, 2024.
[23] Kimin Lee, Laura Smith, Anca Dragan, and Pieter Abbeel. B-pref: Benchmarking preference-based reinforcement learning. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
[24] Kimin Lee, Laura M Smith, and Pieter Abbeel. Pebble: bredback-efficieer interactive reinforcement learning via relabeling experience and unsupervised pre-training. In Proceedings of the 38th International Conference on Machine Learning, pages 6152-6163, 2021.
[25] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001 2021.
[26] Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic second-order methods improve best-known sample complexity of SGD for gradient-dominated functions. In Advances in Neural Information Processing Systems, 2022.
[27] Reginald McLean, Evangelos Chatzaroulas, Luc McCutcheon, Frank Röder, Tianhe Yu, Zhanpeng He, K. R. Zentner, Ryan Julian, K Terry, Isaac Woungang, Nariman Farsad, and Pablo Samuel Castro. Meta-world+: An improved, standardized, rl benchmark. arXiv preprint arXiv:2505. 2025.
(28) Katherine Metcalf, Miguel Sarabia, Natalie Mackraz, and Barry-John Theobald. Sample-efficient preference-based reinforcement learning with dynamies aware rewards. In Proceedings of The 7th Conference on Robot Learning, pages 1484-1532, 2023.
[29] Washim Mondal and Vaneet Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. International Conference on Artificial Intelligence and Statistics, pages 3097-3105, 2024.
12

---

[30] Han Shen and Tianyi Chen. On penalty- bilevel gradient descent method. In International Conference on Machine Learning, pages 30992-31015, 2023.
[31] Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty-based methods for bilevel reinforcement learning and rlhf. Journal of Machine Learning Research, 26(1 14):1-49, 2025.
[32] Zhuoqing Song, Jason D. Lee, and Zhuoran Yang. Can find nash equilibria linear rate in markov games? In The Eleventh International Conference on Learning Representations, 2023.
[33] Daouda Sow, Kaiyi Ji, and Yingbin Liang. On the convergence theory for hessian-free bilevel algorithms. Advances Neural Information Processing Systems, 35:4136-4149, 2022.
[34] Audithya Srikanth, Mudit Gaur, and Vaneet Aggarwal. Discrete state diffusion models: A sample complexity perspective. arXiv preprint arXiv:2510.1085. 2025.
[35] Saksham Sahai Srivastava and Vaneet Aggarwal. A technical survey of reinforcement learning techniques for large language models. arXiv preprini arXiv:2507.04138 2025.
[36] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[37] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq. Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite. arXiv preprint arXiv: 1801.00690, 2018.
[38] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. International Conference on Learning Representations, 2020.
[39] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-basee reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 11118884--8994 2020.
[40] Yan Yang, Bin Gao, and Ya-xiang Yuan. Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity. In Proceedings of The 28th International Conference Artificial Intelligence and Statistics, pages 4780-4788, 2025.
[41] Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Achieving $1mathcal (O10essilo0))))l (-155) complexity in hessian/jacoobaan free stochastic bilevel optimization. In seirrh- Conference on Neural Information Processing Systems, 2023.
[42] Edwin Zhang, Sadie Zhao, Tonghan Wang, Safwan Hossain, Henry Gasztowtt, Stephan Zheng, David C Parkes, Milind Tambe, and Yiling Chen. Social environment design. arXiv preprint arXiv:2402. 14090, 2024.
[43] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C Parkes, and Richard Socher. The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science advances, 8( 8(18):eabk2607 2022.
[44] Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 190900899,, 2019.
[45] Haosheng Zou, Tongzheng Ren, Dong Yan, Hang Su, and Jun Zhu. Learning task-distribution reward shaping with leta-nnn Proceedings of the AAAI Conference on Artificial Intelligence, 35(12): 1218 May 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims are demonstrated in the key results Lemmas and Theorems, with explanations next to them.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The assumptions given in the paper give the limitations of this work. Further, future work direction in the conclusions describe another limitation of this work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: We have provided the assumptions used in the work at one place, which are used in all the results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Details provided in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp..cc. hwtp:c/cppwlccggiicccoeeoo
/CodeSubmia (isoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Details provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Details provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Details provided in Appendix F.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips: httpps/s//errppssscpcpppc/c/iiie cctpublicc/chhiccccueeellellllll delin
Answer: [Yes]
Justification:
All the points mentioned in the NeurlPS Code of Ethics are taken into
considcration.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make consideration due to laws or regulations in their jurisdiction).
preserve anonymity (e.g.. if there is special
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since the work is primarily theoretical in nature, no potential negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All existing works used are properly credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Details provided in Appendix F
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does neither involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19

---

A Proof of Lemma 1 Proof.
A0t1 = d - vf(e))).
where the biased stochastic gradient
by = F [<(((A))] vS(a),,
- - =o.-
By L-smoothness, for y - A4t1 = 22 - -VV(().
I. 2
f(A(11) s(Ae) + (VS(A)) - || - dell
-f(AA)-((fCA) vf(Ae)) -/¹
L
Taking expectation and using the bias notation,
L 1" E ||
B[f(A++1]] S f(A.) (V)(),, vf(A) + b.)
2
L n [[
-((A) - - ||V]( =//
b.)
Apply Cauchy-Schward Schwarz and Young's inequality to the bias inner product:
-7 (VS(A)))))) s n \ S |VS(221 + 2 2 |bell
For the second moment, decompose around the (biased) mean: Combining the bounds yields
B[(()++1]
(40)
S(()) + ( - + TT) [[)( + ||x,1] "²"
L 1 (2b + 0²).
(41)
$ f(A) + ( + Ln² [/(A)) (1bb11 + + + 2 n²² (2b) + 201).
(42)
< S(()) + (- + Tm/ [ (EIV)(A)) - vS(A)13)
(43)
+ 2 1/² 2(EI|Vf(()) - vf(A)))
(44)
s s(A)) + ( + - | + ! (3(n, B, B,)
L - n² (23(n, (, B)
(45)
We obtain equation (43) from equation 42 by using the identity that the square of the bias plus variance is equal to the mean square error. We obtain (45) from equation 43 from the definition of 3(n, B, H).
( (0000-(1-40 (n-L1²)
L.1² IVS(A))1 + (L.1²² + m)8(n, ()H
(46)
2
Now applying the PL inequality (Assumption 1), |V 2p (f(ee) f*), substitute in the above inequality to get
[(++1) - S (1-2// 210 (n 11
( 2 )) (1(2)) 5+) + (L.7² + n)8(n, H)
Lnn)
-+)
(47)
2
Define the contraction factor
La
P = 1 - 24
(48)
20

---

we get the recursion:
(L.T² + 1)).B(n B3 H)
de+1 S.
(49)
2
When E 7, we have
Taf² 11
p 5 pm-
(50)
2
Unrolling the recursion we have
(L.1² + n) B, H
t-1
8t S (1 um) 80 +
pm)
(51)
2
1=0
Using the geometric series bound:
1-1 E - un) S
1
(52)
pm
1=0
we conclude that
8, S (1 (07) + (L.rp2 + n)),(n B, H)
(53)
2/1-17
Hence, we have the convergence result
f(x)) - 5" s (1 (1- um)' (L.T) + 1). H)
(54)
241-11
Lemma (Uniform bound for a sample-bast based KL gradient estimator). Let A be a action space and, for fixed state let Tx(. s) and (--- s) be policies on A. with parameter X E A. Assume:
8](l < B for all E A and (i) (Bounded score) There exists < oo such that V log (a(a
0 EEC O.
(ii) (Common support bounded away from 0) There exist e, (0, 1] such that Tx(a s) 2 for all E A and E A, and Trer s) 2 a for all E A.
Define the per-sample contribution
V Vx To s) log Te(a s) log Kre ss). so that V DxDKL(n (Tg Fres) Buwnotllo) a)). Then, with Glog == log(1/e) + log(1/8), for all a E A and 0 E θ
go a)
(s, a)ll < B (1++ Clog)
and consequently, for any n 2 1 and i.i.d. draws a1...., an ~ TT s). the Monte-Carld estimator Ôn = 1 > (st a;) satisfies || < B (1 Clog).
Proof. (i) and (ii) are satisfied from Assumption 3, for every a E A and 0 E θ Te(a s) E [s, 1] and ( s) [E, 1), hence log ae(a s) E [loge, 0] and log Fres(a s) e [log 0]. Therefore
log (a(a s) - log Frep (a
s)] < log(1/=) + log(1/2) Clog.
and thus 1 + log (a log Tree (a
s) + Clog. By (i).
lge (s, a)l = V log (a s) | log (a s) log Tre (a s) S B (1 Clog).
This bound is deterministic (independent of the sample index) and holds for all a, so taking averages over samples preserves it: |l < B Clog).
21

---

B Proof of Theorem 1
Proof. Using same steps for Lemma A we get
(3) L.n²
7 Loß
(0r+1) 5 (()))
[+)))))
V
(
2
(55)
Now rearranging terms, summing Equation (55) over T and dividing by T both sides get
t= ((x)) (0)6 +0 (
[V(())) <
(56)
We now bound A, as follows
V V (o:))) = V Vo (ot)( Vod (o:))ll
(57)
V (6:) (obo(
2 (0:) -
(58)
O(a) E V (o (obo()
(59)
The first term on the right-hand side denotes the gap between the gradient of the objective function and the gradient of the pseudo-objectivy 4., We get the upper bound on this term from Lemma 4.3 of [2]. The term A, denotes the eπror incurred in estimating the true gradient of the pseudo-objective.
+ Voi VoC(0)
- (,),
E B (o
V (0))11)
<
E
AK) -
X (Ø)), B
VeGlor, 1k B)+
(60)
< V -V K B)|
V (o)) VoJ( 1x B)]l²
E V (o.)) - V [ K B)1
+
(61)
As stated in the main text, the enror in estimation of the gradient of the pseudo objective is split into the error estimating (; VaJ( X (0)) and VoJ(Ø, (x)) whose respective
sample based estimates are denoted by VoG(d, X ). JAK( Φ)) and VaJ x respectively. From Lemmas 3, 4, and 5 we have
2 2H
eexp-A
(. - Ved (o)))) < δ
+
+ +
+ (Capprozz)
o2
o²
02n
(62)
Plugging Equation (62) into Equation (61), then plugging the result into Equation (56) and squaring both sides we get.
(0:(11)1 s +0 + +
+0(22))
22
eep -K|
+ + +0(1))
+
((Eappro))
BBB
72
22

---

(63)
Here T' is the number of iterations of the outer loop of Algorithm 1, K is the number of iterations of the inner loop of Algorithm n is the number of samples required for the gradients J with respect to A. B is the number of samples used to evaluate the gradients of G with respect to À and Φ respectively and the gradients of J with respect Φ.
C
Supplementary Lemmas For Theorem 1
Lemma 3. For a fixed Φe O and iteration t. Algorithm 1 under Assumptions 1-4 we have
7 2H
E| VC - VoG(o, B)I < δ
+ +6 (exp + +
B
((Eapproz).
Proof.
E V. 1((1))
(
VoG(or, B)1 x G X2 - VoG(or,
VoG(o, VoG(o,, B)]l (64)
x Vo (2()) - VoG(o,, ) )|
VoG X Go ,B]] (65)
B'g
A represents the enror incurred in due to difference between ((x)) and our estimate X B represents the difference between the true gradient V. and its sample-based estimate. We first bound Ag as follows
E v VoG(or V
LB]AA(0))
(66)
LG.''Ellho (0r, (5(dr)) ho (0r, X ()6
Here LG is the smoothness constant of G(X, @). We get Equation (67) from Equation (66) by the quadratic growth property applied to (o, A)) using Assumption 1. Now, consider the function ha (Ø, A). We know from Assumption that satisfies the PL. condition, therefore using Lemma obtain
Ellha (or, X* (d.)) - ( A < (exp x) + 088n,, B, H)),
(exp
(68)
Where ((n, B, H) is such that E with respect to the state action pairs sampled to estimate (d)(d,))
V,h, v 2) < 3(n, B.H. Here, the expectation
Now have Vyha(a A)
8
H
Viho A) =
Vlog(m(alls))
V M (8i.j, Oi.j)
B
i=1
B
+ B
(69)
Thus, in order to bound V - Axh we decompose E| V (o.,(or.A)) V (or, follows
V A) (or,
23

---

Vlog(Ts(aa(s:)) (si a;))
H1
4 3
E2 (si V Va Pxless ()), - - L
V Vahantree (8ijj ais)ll
j=1 i=1
04
[E] (AI ViG B)l)
① (exp- K)
(70)
Now consider the terms in A. if we define И (a (s, and d Σ Vlog(Tx(a|s::)).u (ss, a:)) then we decompose follows
E
JJ ( A) d H H|| J , X) H|I +EIld HIl VJ A) HII
(71)
VlogTA (a:ss) (11)
(72)
J(b. A)
H|I+
2
d
E
d.
Σ
Σ
Vlogma (logrs(albs))ooossaa) (H)p
(73)
p=1
[( A) - d))
V A) H|I+
d
VlogTA (aylss) (H)
E
(74)
s ((((a) - HI| + dd,VVmar maa
(75)
Vn
1 a0(
dd,, Vmaz
(76)
Vn
From [15] have that
(11))
E|QTA (s,a) - [o( $ (12) + + (Capprozz
(77)
Thus, we obtain
A δ (1) 17
((Cppproz)
(78)
We obtain Equation (73) from Equation (72) by noting that norm is upper bounded by the norm multiplied by the square root of the dimensions. Here (Vlogæx (a, |s; Q.) (st, a;))p and (H) in Equation (73) are the th co-ordinates of the gradients. We obtain Equation (74) from Equation (73) by applying Jensen's 's inequality on the final term the right hand side. We obtain Equation (75) from Equation (74) by noting that the variance of the random variable VlogTA, (Q)s) a) is bounded

---

from Assumption 3 and Assumption 2 which implies that θ is a compact set. We combine this with the fact that the variance of the mean is the variance divided by the number of samples, which in this case is n. We obtain Equation (76) from Equation (75) by using the policy gradient identity which states that [ X) = X
(8, a) where M is such that ||VlogT>, (a|s)]l S Mg for all E A. We know that Vl (a|s)]| are upper bounded by Assumption
We now bound B as follows
B|IB Ei= 70 -i-IEV h A (st, 8 H -i=1 E==1 V ViliTA (o.g 21))
B
(79)
s 3B Σ
EV x Are (8),a.) 1/ Ei= 2j=1 1 VAlLa (oag) الاي)
+ 3E Ei=H EVV h (8,, a:)ll
(80)
S 3 2i=1
- H
B V Bli BAi r,,/
, (85, 0z))
E==ı Vallanitn (64g. النية
+B>:n H 7"
(8 dng)l::s
(81)
0
(/1 + O(
(82)
Note that ( 2.,)) are the sample estimates of (s;, a.). We obtain Equation (80) from Equation (79) by splitting the first term on the left hand side of Equation (80) at the point = H. We get Equation
(82) from Equation (81) by considering the fact that the first term on the right hand side Equation (81) is a variance term bounded by a factor of V since the overall variance of the term is bounded by Lemma 2. The second term on the right hand side of Equation (81) is bounded since the term
V Valaa (s. d(.)) is bounded from Lemma 2. Thus, we obtain
2H n1 B BSO
+ #)
(83)
We now bound C' as follows
E
VAG(on, X,K - VAG(or; B)ll
B (
(VACH(OnN??),
=
E
d:
EV
B
p=1
(84)
d
B
2
Σ (V.Gr -,,%))-EVV,,,, E, (A X15 (.1)),
E
(85)
B
p=1
B.B.oc
(86)
B²
OG
d.
(87)
B
1
(88)
VB
Here, the right-hand side of Equation (84) comes from writing out the definition of the & norm where the subseript of denotes the pt co-ordinate of the gradient. Equation (86) is obtained from Equation (85) by using Jensen's Inequality, and Equation (88) is obtained from 86 using Assumption 4 which states that the variance of VG estimator is bounded.
This gives us
C <
(89)
B
25

---

Combining Equation (82) and (77) we have that
B Vxho Vaho 50
7
+
0
1
-(=")+0+
+ O Capproz)
B
72H
1
$ 0
+
Ö
Ö (Capproz)
(90)
B
11
Which in turn gives us
Ellha )x lol (6)))) & Ö (+)) + + (exp- + +0 (?2t + Ô (Capprod))1)
We can bound B in the exact same manner as C' where the gradient with respect instead of to get
Bxx S 0
1
(92)
B
Thus we obtain
E A5) BII S Ô (
(93)
Substituting Equation (91) into Equation (67). Then put the result from Equation (67) and Equation (93) in Equation (65) to get the required result.
Lemma 4. For fixed oi O and iteration L. of Algorithm I under Assumptions 1-4 we have
2 2H
K) + (1)
E (o, (o (o) (o), s δ
+ (exp (exp=-)
B
+ ((Cappro))
(94)
Proof.
E V (' (Q) BII
E V J( X' (bx)) Vo,
E V (or - VoJ(o, (
(95)
X V X (Ø), B)I (96)
(A' (2 )1 B// X VoJ Xx B)
(97)
[ J J M11
E V V 2K) V J (Ø. (0), B) (98)
B
We get Equation (97) from Equation (96) by the smoothness of J(ó, X) using Assumption 1. We get
Equation (98) from (97) by the quadratic growth inequality on J(b, A). The first term A is upper bounded using the same way as is done for A'g Lemma 3, with the only difference being the absence of the term C in Equation (70). Thus, we have
Ô (exp (opp-KK-- + +0(+) +0
(22H
[( J(br Joh
Õ (Copprea) (99)
B
We bound By as follows
3l Va.lor X (0), (b), B)l
26

---

B
H
o (s,,
oT (6 (وي))
;=1 i=1
Vo (5 a:)l
V
oT (Si.) 0i
j=1
+
1 E
(100)
1=
H
0
(101)
vB
Thus have
12 B + O,.
J(r, - VoJ(or AR B) s Ô
(102)
We get Equation (101) from Equation (100) since the first term on the right hand side of Equation (100) is variance term with a sample size of B. The last term on the right hand side Equation (100) is upper bounded by 7 since the term V Vorass, a,) is upper bounded by Assumption 3.
Plugging the result of Equation (102) and Equation (99) into Equation (98) gives us the required result..
Lemma 5. For a fixed 6: O and iteration t of Algorithm 1 under Assumptions 1-4 we have
Jo,( ((())) - .k (0), B)
7
2H
+ +O - -k) + [1
B
((Caprooz)
(103)
Proof.
V B ( K (b),
V (ot1))
VoJ( VoJ(a,
VoJ(on,)" VoJ(EN) X (0), B)I (104)
E| V V 12 (or)) VoJ(on 111 + (0r, VoJ(on, X (0), B][((105)
L,.B (X 11 + E V (0. ( VoJ X K B)
(106)
Ly L ho (dr. X (o:)) ho (Ø. + E J X K
v J X K B)ll (107)
A
B
We get Equation (107) from Equation (106) using Assumption 1. Note that B here is the same as
B% in Lemma 4. Thus we have
V (or, VoJ K (0)) < δ
2H
+ ")
(108)
Further, we have
< δ ( + Ô (exp xx++0
2
ho (de, (o:)) to (0r, Xx)I ||
+ Ö (pppro(199)
(B)
This is the same result as for A'g in Lemma 3.
Plugging Equations (108) and (109) into Equation (107) given us the required result.
27

---

Lemma 6. For a given À E A and Φ E θ we have
1o = Σ
E
EV ())
(110)
Proof. We start by writing the gradient of J(b, A) with respect follows
V
(0,
= V [ 61,01
Q3(s),
(111)
(arp(siaa))x(((sssdd()
+ V
02)
(112)
82.02
J1
+
02,02 J1,a1
+ 2² V
$1.01 02.00 53.03
(113)
Vor(())
/ 23.03
+ 9. Vo + +
82.02
(114)
We get Equation (112) from Equation (11I) by noting that ()) Sa (8 )d(s' (a)xx(a (s'). We repeat the same process on the second term on the right hand side of Equation (112) to obtain Equation (113), Continuing this sequence, we get
20
V
(115)
Here, 8i, 81,0; ag belong the distribution of the 5th state action pair induced by following the policy X.
D Proof of Theorem 2
Proof. As is done for the proof of Theorem we obtain the following from the smoothness assumption
on d.
1
[+(0))11 <
T
BlI a vob.
T
(116)
A.
We now bound A, as follows
E (())) V & (d:)))1
= E volo(dr) + Volo
&o
(117)
E (bt) (o
E (0.) Vodo(6)))
(118)
28

---

x O(o) + ( - Vo (ofo(
(119)
A
The first term on the right hand side denotes the gap between the gradient of the objective function and the gradient of the pseudo-objective 4, We get the upper bound on this term form [2]. The term A, denotes the error incurred in estimating the true gradient of the pseudo-objective.
-o)
E V a (
Vo (
E V ((O
A
VoJ( 2/ (0r), VoJ(or X (0), B)
2
VeG Xx B)
(120)
< - B)l
+ 2 (6.)) VoJ(o,, K B)1l
V \3 (o:)) V ) B)1|
(121)
As stated in the main text, the error in estimation of the gradient of the pseudo objective is split into the error in estimating V, X2 (d.)), (oJ A (d()) and V ( Xa (dx)) whose respective
sample based estimates are denoted by VaG(on, X V (dr and Vori x respectively. From Lemmas 7, and we have
V (o)oll I δ (
exp exp-
+ +
(122)
o2
0²
Plugging Equation (122) into Equation (121), then plugging the result into Equation (116) we get
Σ (0)(1 S δ
( ( + Ö
exp
+ Ö
1 O² + O(o²)
(123)
Here T is the number of iterations the outer loop of Algorithm 1, is the number of iterations of the inner loop of Algorithm 1. B is the number of samples required for the all the gradient evaluations.
E
Supplementary Lemmas For Theorem 2
Lemma 7. For a fixed de e and iteration t of Algorithm 1 under Assumptions 1-2 and Assumptions
5 we have
s δ ((²)) + + (exp-KK
(124)
B
Proof.
E G(0 V.G(O,, B) < -VC
VoG(o,, X VoG(or, X B)I1, (125)
V. (o)) VoG(o,, N1
Axx + V V.G( Xx) VeG(or (B)]6) B)(
B'x
29

---

We first bound Ag-
LE (o)) X )|
(127)
ch Li |Ill ho (òr, (o=)) - ho (0r, x))l- (128)
Here L, the smoothness constant G(A, We get Equation (128) from Equation (127) by Assumption Now, consider the function [( A). We know from Lemma that it satisfies the weak gradient condition, therefore, applying the same logic for J(ó, X) that we did for (or). Using Assumption I, and Lemma we obtain
((r, - (or X 211 5 3(B) + (exp-K).
(129)
where B(n. B. H) satisfies V 2) - (dr, 1])l|² < 5(B). Note we changed notation from B(n, B, H) 3(B) since samples are used evaluate the gradients. Now in this case, we have an unbiased estimate of hh, (0r, A ())))) Therefore, from assumption 5 we have that.
Now, the term E (hr A) (ho A)1 it can be decomposed as follows
V Vhho 2) Voho 1)
E| (or, A) VvG( A) VAJ B) B)
(130)
E V A) Ade B)1l E VAGGL B)I (131)
Note that both A" and B" can be bounded same C' in Lemma 3. thus have
A " I Ō
1
(132)
B
B" " s Ô
(133)
B
Thus we have B(B) = Ô (+). Which gives
E |/ (0r,, x²) to X x III
Ô (exp- (osp-K)-o +
(134)
B
Similarly B here bounded the same way as C in Lemma 3 to get
1 B
E V G Glo X B)Il o
(135)
Plugging Equation (134) and (135) into Equation (126) gives us the required result.
Lemma For a fixed &e and iteration t of Algorithm I under Assumptions 1-2 and Assumptions
5 we have
E V X²) (o (6), < δ (( B
+ Ō (exp -k)
(136)
Proof.
E V \o,(o,, - V 1 B)I
E VoJ( (*)))) - VoJ(Ch, 1 + VoJ( 1K J (0), B)1
(137)
E
(or (0)) Vol(d,, ||| + V V 23 VoJ(d, X B)]l (138)
30

---

L (+)( - (A/))2 V| [or A - [o B)1
(139)
L' pEll (o))) J( X || V -oo B)Il (140)
B"
We get Equation (139) form Equation (138) by using Assumption 1. The first term A" is upper the same way starting from Equation (129) as in Lemma 7 to give
- J(,r, J(b & Ô (()
E|
+ O (exp-x)
(141)
B
B" is bounded in the same manner as Bg in Lemma 3 to give
< δ 1
V A - V J (0), B)l
(142)
B
Plugging Equation (141) and (142) into Equation (140) given us the required result.
Lemma 9. For fixed de E O and iteration I. of Algorithm I under Assumptions 1-2 and Assumptions
5 we have
V -
B111 BI12 s ō 1 B
(())
+ Ô (exp-x)
(143)
Proof.
V (; - Vol( KK B)11
< E/ & (o1) - VeJ(Ør. A VoJ(nnd VoJ(on KK (0). B)Il, (144)
S ( (2,, - VoJ(Ør, > KK )l1 + V ad (0r,) 1K VoJ(on, X K
(0), (145)
< 1. - (A
K 1122 + E V [ X K
VoJ X (0), B)1
(146)
s Ly. (0, No (o)) ho (0,, X B V J ( v VoJ B)Ll (147)
B"
We get Equation (147) from Equation (146) using Assumption Note that B can be bounded same
as Bg in Lemma 3. Thus we have
El d x
K VaJ(Øn,
[)) ( < Ô
1 B
(148)
For A" note that now the gradient descent is happening on the objective given by ho = (() Φ) - oG( A). Applying the same logic as we did for ( A), from Assumption I and Lemma we get
E| lh (6r, (d:)) tr (0r, X33
(oxp-K) Ô (exp K) + 5(B)
(149)
where 5(B) such that V A) Vxho (p., 2)ll2 S 5(B)
Now, consider the term E| Vh (0,, A) Vha 1) it can decomposed as follows
E Vh (#,, A) (h 2)1
< ( A) V.G( A) (. oVV
(150)
A) V ViJ A, to E A) VAG(
(151)
n
8"
Note that both A" and B" can be bounded same B' in Lemma 3. thus we have
31

---

A " sō
1 B
(152)
B" Ō
(153)
B
Thus have 8(B) = - ) Which gives us
B| 0r, - (o X All
x
Ô (exp k) + 0
(154)
B
Plugging Equation (154) and (148) into Equation (147) gives us the required result.
Experiments
F.1
Setup
The upper objective function to evaluate the reward is defined as follows
PO(To G(\, Φ) -Egg,,,rr-n (A) (y- PT > r) + (1 - 1)-(1))111 - >T)))
(155)
Where PH (A) is the distribution of trajectory of length preference which is 1 if trajectory 1 is preferred and ( if Trajectory 0 is preferred which is drawn from some unknown distribution p. Also, PT(TO 71) is defined as
by following the policy and y the
exp 0 no (5%
10%, ag)
Pa >T)=
(156)
exp Σi= ro ( a%) exp DH ro()
The objective to be minimized given in Equation (9) as follows:
(6) = min G( A) _ (J(o -(() J(o.
where (² = arg maxa [Ø, A) (noting the sign convention for the lower-level maximization of the return J).
To make this more implementable in an RL context, we reformulate the lower-level optimality using value functions. Let (o X) denote the value function under policy лュ (i.e., (( Eywe, amxx [V( A)], where v is the initial state distribution). The optimal lower-level policy should maximize the value function, and should therefore satisfy
Vi (o)) = (Ø) = max (o
Substituting this into the penalty form yields:
1 (V (0))))((0)---))))) - V().)) = G( 1 -V) V))
G A)
Directly minimizing the objective in Equation 9 is difficult in practice. Thus, for implementation. we make practical approximation by dropping the V(Ø, A) term (which is non-negative under the assumption of non-negative rewards, common setup in discounted MDPs where V(Ø, 2 0). This provides an upper bound on the objective while simplifying computation:
G(o, A) -)
In the code, this manifests as the regularization term added to the upper-level loss G, effectively encouraging the outer optimization (over Φ) to maximize the optimal value V scaled by 1/a. This aligns with the bi-level structure by implicitly penalizing deviations from lower-level optimality without explicit inner-loop solving for X at every step. We demonstrate improved performance over the PEBBLE [24] baseline in the two benchmarks using this approximation. We leave the implementation of the full Algorithm as well as obtaining tighter upper bound on Equation (9) to future work.
32

---

F.2 Implementation Details
We evaluate the effectiveness of this method, which solves the simplified objective, on two distinet environments: the Walker locomotion task from the Deep.Mind Control Suite [37] and the Door Open manipulation task from Meta-world [27]. These environments are chosen as representative benchmarks for robotic locomotion and manipulation, respectively, and both present the challenge of learning from limited, preference-
feedback rather than direct access to ground-truth rewards.
To demonstrate the efficacy of this approach, we compare against PEBBLE [24] baseline, which also uses preference-basee feedback for solving complex tasks. Both PEBBLE well the proposed method utilize unsupervised exploration as proposed in PEBBLE [24], with dilsgreeement-basee sampling for query selection, standard approach in preference-based reinforcement learning [28]. For the PEBBLE baseline, we employ the publicly released code from B-Pred [23], maintaining identical hyper paper--arameters and network architectures, such as the number of layers, learning rate, and the frequency of supervised reward learning. Our method builds on the PEBBLE framework, leveraging its core components while introducing our core contributions. We provide each task with fixed budget of human preference labels: 100 labels for the Walker task and 1,000) labels for the Door Open task. All experiments are conducted on single machine with an NVIDIA RTX 1080 Ti GPU, and we report results averaged over multiple independent runs with different random seeds.
F.3 Results
The training curves Figure illustrate the performance improvement of this approach against PEBBLE on both the Walker and Door Open tasks. In the Walker environment, the agent is rewarded for moving forward, and in our setting, the agent receives only preference-basee feedback. The proposed method demonstrates improvements over the PEBBLE baseline, achieving higher average velocities and more stable learning trajectories with few preference labels. On the Door Open manipulation task, this approach similarly outperforms the baseline, successfully opening the door more consistently and efficiently.
These results highlight the effectiveness of this method in improving feedback efficiency and task performance, even settings with limited preference-feddbace It is be noted that this approach improves over the PEBBLE baseline without the need for second-order terms. unlike [1]. Other bi-level works such as [31] do demonstrate improvement over state-of-the-ar bi-level algorithms. Overall, these experiments validate the advantages of this proposed approach in both locomotion and manipulation scenarios, underscoring its potential for real-world robotic applications. The code can be found at attpps:// /gggtttt......./// com/Mum Mudi tGaur /Neur ips 2025_0222________ 1er22_Bileeel__.. RL.
Walker
Door Open
Episode Reward
800
700
Episode Reward
300
350
OURS
PEBBLE
600
250
500
200
400
150
300
100
PEBBLE OURS
50
100
5dk
100k
150k
200k
250k
50k
100k
150k
200k
250k
Environment Steps
Environment Steps
Figure 1: Training curves Walker locomotion task (left) from the DeepMind Control Suite [37] and the Door Open manipulation task (right) from Meta-world [27]. The solid line and shaded regions respectively, denote mean and standard deviation of the success rate, across multiple seeds. Blue curve: PEBBLE, Red curve: OURS.
33


Reviews:
[{"review_id": "8hgDo7fXvH", "reviewer": "Reviewer_o7dV", "summary": "This paper studies first-order, Hessian-free algorithm for bilevel reinforcement learning. The authors consider two settings, with and without access to unbiased gradients, and for both the settings they establish 1/\\epsilon^{-4} sample complexity. All analysis relies on a PL condition for the lower-level objective and Lipschitz–smoothness of gradients and Hessians.", "questions": "-\tWhat are s_i , a_i in Eq. (1)?\n-\tIn both Theorems 1 and 2 you assume Assumption 2, which specifies an upper bound on the representation power of the neural network, which models the Q-function. It is not clear for me why the approximation error appears in Theorem 1, but not Theorem 2. Can you elaborate?\n-\tWhat is the implications of your results for the RLHF theory? What is the query complexity of RLHF when studied under the umbrella of Bilevel optimization? How is the query complexity of RLHF affected by the structure of the underlying MDP?\n-\tIn the conclusion section the authors suggest a \\epsilon^{-4} sample complexity, which is in contrast to the rest of the paper. Can you please clarify?\n-\tAre there any known lower bounds for bilevel optimization?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \n-\tThe authors claim to have improved the sample complexity of Bilevel optimization in the case of Non-convex LL and without second order operations, from already known \\epsilon^{-6} to \\epsilon^{-3}.\nWeakness:\n-\tThe convergence results are only to the stationary point. There are no discussions on what is necessary to guarantee global convergence of this algorithm.\n-\tThe analysis is only for a fixed value of \\sigma and step size \\eta, B, N, and T. Hence, the algorithm does not have asymptotic convergence. \n-\tThe final result is only in terms of \\epsilon, and constants which depend on the problem structure are missing in the statement of the theorem. These constants can be specifically important when studying settings like RLHF, where the underlying structure (state, action, and 1-\\gamma dependency) is important.\n-\tSatisfying PL condition for RL problem is not necessarily true. Can you justify this condition for RL setting? Can you provide concrete function approximation settings where all the assumption are satisfied?\n-\tThere are no implementations justifying the sample complexity that is achieved in the theory.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I believe this is a strong paper which deserves higher score.", "rebuttal": "> **Weakness 1:**- The convergence results are only to the stationary point. There are no discussions on what is necessary to guarantee global convergence of this algorithm.\n\n**Response to Weakness 1:** Thank you for your observation.\n\n-  We did not discuss global optimality because our upper-level objective is non-convex, and in such settings, convergence to a stationary point is the standard and, in general, the best attainable guarantee. This is consistent with existing results in both bilevel reinforcement learning (Chakraborty et al. 2024) and general bilevel optimization literature (Chen et al. 2024) \n- **Global convergence:** While one could obtain global convergence by imposing stronger conditions such as the Polyak–Łojasiewicz (PL) condition on the upper loss function, we chose not to include such assumptions, as they would lead to a more restricted and less realistic setting, as well as making our result not comparable to other works.\n\n> **Weakness 2:** The analysis is only for a fixed value of \\sigma and step size \\eta, B, N, and T. Hence, the algorithm does not have asymptotic convergence.\n\n**Response to Weakness 2:**  Thank you for pointing this out. Our analysis focuses on finite-time convergence, explicitly characterizing how the rate depends on parameters such as batch size B, number of samples N, and total steps T. ***This provides a more practical and informative guarantee than asymptotic convergence, which does not offer explicit rates.*** While we use a fixed step size in our analysis, we validate its effectiveness empirically through the results presented in the paper.\n\n> **Weakness 3:** The final result is only in terms of \\epsilon, and ...... when studying settings like RLHF, where the underlying structure (state, action, and 1-\\gamma dependency) is important. \n\n**Response to Weakness 3:** It is correct that our convergence result is in the Big O notation and does not specifically account for every possible constant that can affect the convergence. However, we would like to point out that we are focused on the **sample complexity**, which focuses on how many samples are needed to get the convergence of a given order of magnitude $\\epsilon$. This is standard in Bilevel RL works such as Shen et al.(2024) (See table 1) and  Yang et al.(2025) (See table 1), which report their convergence rates in terms of Big-O notation. Works such as Chakraborty et al.(2024) report their rates in terms of problem-dependent constants (See constants $ c_1$  and $L_{g}$  in Theorem 1). Thus, we are following standard practice when we report our results in Big-O notation.\n\n> **Weakness 4:** Satisfying PL condition for RL problem .... where all the assumptions are satisfied? \n\n**Response to Weakness 4:**  The PL (gradient‑dominance) assumption is not imposed arbitrarily; it is known to hold in several reinforcement‑learning settings.  \n\n- For example, Bhandari et al. (2021) show that if the one‑step policy‑improvement objective is convex, then the full policy‑gradient objective is gradient dominated.  \n- In continuous control, the LQR cost is proven to satisfy a PL inequality (Fazel et al. 2018)\n-  Mei et al.(2022) demonstrates that SoftMax policy‑gradient objectives satisfy a Łojasiewicz (PL‑like) inequality, and entropy regularization turns it into a full PL condition, leading to linear convergence.  \n-  Wang et al.(2022)  established that the robust RL objective under R‑contamination uncertainty satisfies the PL condition, and Montenegro et al.(2025) show that regularized Lagrangians in constrained RL are PL when using natural or SoftMax parameterizations.  \n\nBecause our bilevel loss includes a regularization term similar to these works, it enjoys the same gradient‑dominance property.  Moreover, in tabular, SoftMax, or linear‑quadratic settings, the PL condition holds exactly, and our analysis covers these function‑approximation cases.\n\nWe provide additional justification for the use of the PL condition by implementing the algorithm in the Appendix F of the Supplementary Material.\n\n> **Weakness 5:** no implementations are justifying the sample complexity that is achieved in the theory.\n\n**Response to Weakness 5:**  In Appendix F of the Supplementary Material, we have implemented our algorithm in two RLHF simulations, namely Walker (Deep Mind Control Suite (2013)) and Door Open (Meta World + (2025)). These are RLHF (reinforcement Learning from Human Feedback) benchmarks that have been used to demonstrate the effectiveness of prior bilevel RL works such as Chakraborty et al (2024). We evaluate our algorithm against [PEBBLE] (Lee et al. 2021), which is a state-of-the-art RLHF algorithm, and show performance improvement.\n\n> **Question 1:** What are s_i , a_i in Eq. (1)?\n\n**Response to Question 1:** That's a typo; it should just be (s,a). We will correct this in the final version.\n\n> **Question 2:** In both Theorems 1 and 2, you assume ...  Can you elaborate?\n\n**Response to Question 2:** \nThank you for pointing this out. For Theorem 2, we do not need Assumption 2. That is a typo in the statement of Theorem 2. We only need assumptions 1 and 4 for Theorem 2, and we will correct this mistake in the final version of the paper. The reason for this is as follows:\n\n- Theorem 1 tackles the bilevel RL setup, which requires the use of a neural network to approximate the Q function. Thus, we do not have access to an unbiased estimate of the Q function. Hence, we need to account for this bias that has been introduced. Assumption 2 thus defines the constant $\\epsilon_{error}$, which upper bounds the representation power of the neural network class. This assumption, along with Lemma 1, is used to account for the biased estimate of the Q function. Consequently, $\\epsilon_{error}$ shows up in the final theorem statement.\n\n- In contrast, Theorem 2 tackles the standard bi-level setup where it is common practice to assume unbiased and bounded gradient access for both the upper and lower gradient. Such an assumption is used in existing bilevel works, such as Kwon et al. (2020)  (See Assumption 3), Chen et al. (2024) (See Assumption 4.2). Thus, we do not need Assumption 2 or Lemma 1, and hence $\\epsilon_{error}$ does not show up in the statement of Theorem 2.\n\n> **Question 3:** What is the implications of your ....underlying MDP?\n\n**Response to Question 3:**  \n- **Query complexity of RLHF.** In our setup, for an RLHF implementation, the query complexity is given by the batch size, B, which is the number of samples used at each iteration of the algorithm to estimate the gradient of the proxy objective ${\\nabla}{\\Phi}_{\\sigma}(\\phi)$. For an RLHF setup, this corresponds to the number of queries from the human labeler. In the experiment we conducted, the queries corresponded to the demonstrations we queried from the environments, walker, and door open. \n- **Query complexity and the structure of the underlying MDP.**  The query complexity decides how well we estimate the gradient of the proxy objective ${\\nabla}{\\Phi}_{\\sigma}(\\phi)$, the closed form expression for which is given in Equation (10). On the right-hand side of Equation (10), note the presence of the term $\\lambda^{*}(\\phi)$. This term is the policy parameter for the optimal policy of the expected return $J(\\phi,\\lambda)$, which is closely related to the underlying structure of the MDP. This in turn relates query complexity to the underlying MDP structure.\n\n> **Question 4:** In the conclusion....Can you please clarify?\n\n**Response to Question 4:**  That is a typo. It should be $\\mathcal{O}(\\epsilon^{-3})$ in the conclusion. We apologize for the typo and will fix it in the final version.\n\n>  **Question 5:** Are there any known lower bounds for bilevel optimization?\n\nWe are not aware of any when the lower level is non-convex, which is the case in bi-level RL.\n\n---\n**References**\n\n- Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Dinesh Manocha, Huazheng Wang, Mengdi Wang, Furong Huang. \"PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback\". ICLR 2024\n\n- Lesi Chen, Jing Xu, Jingzhao Zhang \"On Finding Small Hyper-Gradients in Bilevel Optimization:Hardness Results and Improved Analysis\" COLT 2024.\n\n- Han Shen, Zhuoran Yang, Tianyi Chen. \"Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF\", ICML 2024.\n\n- Yan Yang, Bin Gao, Ya-xiang Yuan \"Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity\". AISTATS 2025\n\n- Jalaj Bhandari and Daniel Russo. \"Global Optimality Guarantees For Policy Gradient Methods\". Operations Research 2024.\n\n- Maryam Fazel, Rong Ge, Sham M. Kakade, Mehran Mesbahi. \"Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator\". ICML 2018.\n\n- Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, Dale Schuurmans. \"On the Global Convergence Rates of Softmax Policy Gradient Methods\". ICML 2020\n\n- Yue Wang, Shaofeng Zou. \"Policy Gradient Method For Robust Reinforcement Learning\". ICML 2022\n\n- Alessandro Montenegro · Marco Mussi · Matteo Papini · Alberto Maria Metelli. \"Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity\". ICML 2025.\n\n- Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, Martin Riedmiller. \"Deep Mind Control Suite\". arxiv,2018\n \n- Reginald McLean, Evangelos Chatzaroulas, Luc McCutcheon, Frank Röder, Tianhe Yu, Zhanpeng He, K.R. Zentner, Ryan Julian, J K Terry, Isaac Woungang, Nariman Farsad, Pablo Samuel Castro. \"Meta-World+: An Improved, Standardized, RL Benchmark\". arxiv,2025\n\n- Kimin Lee, Laura Smith, Pieter Abbeel. \"PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training\" .ICML 2021\n\n- Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak. \"A Fully First-Order Method for Stochastic Bilevel Optimization\". ICML 2020."}, {"review_id": "vDthwYbnwr", "reviewer": "Reviewer_aCd4", "summary": "This paper studies the sample complexity of bilevel RL. In bilevel RL, the goal is to minimize an objective function $G(\\phi, \\lambda^\\*)$, where $\\phi$ is the parameter of the reward model, and $\\lambda^*$ is the parameter of the optimal policy induced by the reward model represented by $\\phi$. Prior work on this problem requires (approximately) evaluating the Hessian/Jacobian matrices and Hessian / Jacobian vector products, or focuses on the tabular setting. In this paper, the authors propose a new first-order algorithm for bilevel RL that works for continuous state-action spaces,  and provide a sample complexity results for their algorithm.", "questions": "See Weaknesses above.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nThis paper gives the first sample complexity result for bilevel RL. Moreover, the algorithm could handle continuous space. Moreover, even for the standard bilevel optimization setup, the proposed algorithm yields improved sample complexity. \n\nWeaknesses: \n1. I would suggest adding a more detailed introduction on bilevel RL. In particular, I would suggest adding more discussion on the connection between bilevel RL and other topics in RL (like inverse RL and RLHF). Currently, bilevel RL is defined in a very abstract manner, and it would be hard for readers (especially those who haven't worked on bilevel RL) to understand its connection to other RL problems.\n2. A more details comparison with [17], especially in terms of technical aspects, should be added. In particular, it is clear that the result in [17] applies only to bilevel optimization problems without an MDP structure, where for bilevel RL, gradient estimates are inherently biased. However, it is unclear to me why the analysis in the paper, when specialized to the standard bilevel optimization setup, yields improved sample complexity bounds. What are the new technical ideas that allow such an improvement?", "was_revised": true, "final_justification": "The authors' response resolved my concerns, and therefore I would like to keep my positive score.", "rebuttal": "> **Weakness 1:**- I would suggest adding a more detailed introduction on bilevel RL. In particular, I would suggest adding more discussion on the connection between bilevel RL and other topics in RL (like inverse RL and RLHF). Currently, bilevel RL is defined in a very abstract manner, and it would be hard for readers (especially those who haven't worked on bilevel RL) to understand its connection to other RL problems.\n\n**Response to Weakness 1:** Thank you for this helpful suggestion. We agree that a clearer exposition of bilevel RL and its relationship to other RL frameworks, such as inverse RL and RLHF, would improve accessibility for a broader audience. In the final version, we will expand the introduction to better contextualize bilevel RL. Specifically, we will highlight how it differs from standard RL (where the reward is typically known or fixed a priori) and clarify its relevance in settings where the reward function must be inferred or adapted through nested optimization.\n\n\nWe give a brief overview of the difference between them here\n\n**Standard RL:** In a standard RL setup, an agent has to learn a policy that maximizes the cumulative reward over a finite or infinite horizon. In such a setup, it is assumed that the reward function is known to the agent and fixed. This includes applications such as ATARI games (Minh et al. 2013). The function to be optimized is denoted by the expected cumulative reward, denoted by $J(\\lambda)$. Here $\\lambda$ is the policy parameter.\n\n**Bi-level RL:** In a bilevel RL, the reward function is not known. An example of such a situation is a situation where a robotic agent has to appear humanlike. The reward function in such a case is a parametrized function $r_{\\phi}$ which is updated using demonstrations from a human. \nThese demonstrations are used to update the reward parameter by minimizing a loss function denoted by $G(\\phi,\\lambda)$, known as the upper loss function. The learned reward parameter is used to maximize the expected cumulative reward now given to us $J(\\phi,\\lambda)$. Thus, we have two loss functions to optimize, and this problem is cast as a bilevel optimization.\n\nFor example, in Appendix F of the Supplementary Material, we implement our algorithm for two simulated environments, namely Walker (Deep Mind Control Suite (2013) ) and Door Open (Meta World+ (2025)). In both these environments, the true reward function is unknown to us. We can only query a pair of trajectories from the environment and a label that indicates which of the two trajectories is preferred. Using this data, we learn a reward function that is then used to learn a policy that maximizes the cumulative reward. This process is repeated sequentially (as we have laid out in Algorithm 1). We evaluate our algorithm against  [PEBBLE] (Lee et al. 2021), which is a state-of-the-art RLHF algorithm, and show an improvement in performance.\n\n---\n\n> **Weakness 2:**- A more detailed comparison with [17], especially in terms of technical aspects, should be added. In particular, it is clear that the result in [17] applies only to bilevel optimization problems without an MDP structure, where for bilevel RL, gradient estimates are inherently biased. However, it is unclear to me why the analysis in the paper, when specialized to the standard bilevel optimization setup, yields improved sample complexity bounds. What are the new technical ideas that allow such an improvement?\n\n**Response to Weakness 2:** \n\n **Technical ideas that allow improvement.** \nThe key idea behind the improved sample complexity in the bilevel RL setup is the decomposition of the gradient estimation error laid out in section 5.1 in the part titled **Gradient Estimation Error**. This decomposition is novel and allows us to obtain improved sample complexity. For the bi-level RL case, we also need Lemma 1 and Assumption 2 to account for the additional bias incurred in estimating the gradient ${\\nabla}_{\\lambda}J(\\phi,\\lambda)$. In the standard bi-level case, Lemma 1 and Assumption 2 are not needed. This is because it is a common assumption that we have access to unbiased and bounded variance estimates for the gradient of both upper and lower loss functions. This stronger assumption is justified in cases such as Hyperparameter optimization (Franceschi et al. 2017). This assumption is also present in bi-level optimization analyses such as Kwon et al. (2020) (See Assumption 3), Chen et al. (2024) (See Assumption 4.2).\n\nThus, the standard bi-level case is thus a simplified case of the bilevel-RL setup, and has the same sample complexity result. We also note that we have incorrectly stated in the statement of Theorem 2 that Assumption 2 is needed. That is a typo, and we will correct it in the final version. Theorem 2 only needs Assumptions 1 and 4.\n\n---\n**References**\n\n- Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, Martin Riedmiller. \"Playing Atari with Deep Reinforcement Learning\". NeurIPS 2013.\n\n- Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, Martin Riedmiller. \"Deep Mind Control Suite\". arxiv,2018\n\n- Reginald McLean, Evangelos Chatzaroulas, Luc McCutcheon, Frank Röder, Tianhe Yu, Zhanpeng He, K.R. Zentner, Ryan Julian, J K Terry, Isaac Woungang, Nariman Farsad, Pablo Samuel Castro. \"Meta-World+: An Improved, Standardized, RL Benchmark\". arxiv,2025\n\n- Kimin Lee, Laura Smith, Pieter Abbeel. \"PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training\" .ICML 2021\n\n- Luca Franceschi, Michele Donini, Paolo Frasconi, Massimiliano Pontil. \"Forward and Reverse Gradient-Based Hyperparameter Optimization\". ICML 2017.\n\n- Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak. \"A Fully First-Order Method for Stochastic Bilevel Optimization\". ICML 2020.\n\n- Lesi Chen, Jing Xu, Jingzhao Zhang \"On Finding Small Hyper-Gradients in Bilevel Optimization:Hardness Results and Improved Analysis\" COLT 2024."}, {"review_id": "6A525TDX3N", "reviewer": "Reviewer_m28U", "summary": "This paper presents the first finite-sample analysis of BRL, establishing a sample complexity of $\\mathcal{O}(\\epsilon^{-3})$ in continuous state-action spaces. The contribution is both clear and sound.", "questions": "My primary concern pertains to the technical contribution of this work.\n\nCould you elaborate further on Assumption 1.3? Why is it necessary, and has it appeared in prior work? If not, please clarify how this new assumption relates to existing assumptions in the literature.\n\nFurthermore, what limitations in prior work prevented the establishment of sample complexity bounds for continuous state-action spaces? What specific techniques were developed in this paper to overcome these challenges and enable the extension?", "limitations": "This work requires strong assumptions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- This paper is well-written and easy to follow.\n- The contribution is clear and significant.\n- Establishing sample complexity bounds for continuous state-action spaces is an important advancement.\n\n**Weaknesses**\n- Assumption 1.3 requires Lipschitz and smooth Hessians, which is a strong condition.\n- While the authors emphasize the contribution of extending from the tabular setting to continuous spaces, it remains unclear what specific technique was developed to enable this extension.\n- There are a few typos in the paper. For example, in the conclusion, the sample complexity should be stated as $\\mathcal{O}(\\epsilon^{-3})$ rather than $\\mathcal{O}(\\epsilon^{-4})$.", "was_revised": true, "final_justification": "All my questions have been answered, and I'm convinced of the contribution of this work.", "rebuttal": "> **Weakness 1/Question 1:**- Assumption 1.3 requires Lipschitz and smooth Hessians, which is a strong condition. Could you elaborate further on Assumption 1.3? Why is it necessary, and has it appeared in prior work? If not, please clarify how this new assumption relates to existing assumptions in the literature.\n\n**Response to Weakness 1/Question 1:** Thank you for the thoughtful question and the opportunity to clarify Assumption 1.3.\n\nThe confusion around Assumption 1.3 appears to stem from a wording oversight in our current draft. We had inadvertently described the Hessians as “smooth,” whereas our intended assumption is that the Hessians of $G(\\phi, \\lambda)$ (with respect to $\\lambda$) and $J(\\phi, \\lambda)$ (with respect to both $\\phi$ and $\\lambda$) are Lipschitz continuous. We will revise the assumption statement accordingly (mentioned below for quick reference) in the final version to ensure clarity.\n\n - **Assumption  1.3:**  The function $G(\\phi,\\lambda)$ has Lipschitz Hessians with respect to $\\lambda$. The function $J(\\phi,\\lambda)$ has Lipschitz Hessians with respect to both $\\lambda$  and $\\phi$.  \n\n**The assumption is well established in the existing literature.** This Lipschitz condition on the Hessians is well-established in the bilevel optimization literature. In particular, Chen et al.(2024) (See Assumption 4.1) show that such assumptions are necessary for convergence in the bilevel setting introduced in Kwon et al. (2024), which deals with non-convex lower-level problems. Additionally, similar assumptions appear in bilevel works like Ji et al. 2021 (See Assumption 3) and  Yang et al. (2023) (See Assumption 2), which assume convex lower-level problems. They are also assumed in bilevel RL literature, such as Chakraborty et al. (2024) (Assumption 3).\n\n---\n> **Weakness 2/Question 2:**- While the authors emphasize the contribution of extending from the tabular setting to continuous spaces, it remains unclear what specific technique was developed to enable this extension.? Furthermore, what limitations in prior work prevented the establishment of sample complexity bounds for continuous state-action spaces? What specific techniques were developed in this paper to overcome these challenges and enable the extension?\n\n**Response to Weakness 2/Question 2:**\n\n### Limitations of prior works - and how we improve\n\n| **Reference** | **Assumed setting** | **Blocking limitation** |\n|---------------|--------------------|-------------------------|\n| **Chakraborty et al.(2024)** Hypergradient w/ SoftMax policy | Discrete action (tabular or SoftMax) | Can be extended to continuous state action space but involves computing 2nd-order terms (impractical for real-world usage) |\n| **Yang$^{1}$ et al.(2025)** Closed-form hypergradient | Tabular | Closed-form expressions for hypergradients obtained assuming tabular setup(See Equations 5-8). Cannot be extended to a continuous setup.|\n| **Shen et al. (2024)** Penalty-based bilevel | Tabular | Strongly-convex penalty is defined for tabular setup(See section 3.2); Strongly convex property of penalty term required for convergence. Cannot be extended to a continuous setup |\n| **All above** | — | Provide **iteration** complexity only — no sample-efficiency guarantees |\n\n---\n\n **Our contributions:**\n\n- Continuous state–action space,  \n- Using first-order information only: no Hessian or hyper-Hessian inversion needed,  \n- Sample complexity bounds: tight bound of  $\\mathcal{O}\\bigl(\\epsilon^{-3}\\bigr)$ (see Theorem 1).\n\n\n**Our Key technical ideas:**\n\n1. **Bias-aware decomposition of gradient estimation error** \nWe use the bi-level optimization framework of Kwon et al. (2024) since it provides first-order gradient expressions without being limited to tabular settings and allows for a non-convex lower loss. However, in bi-level RL, we have to use a biased estimate of ${\\nabla}_{\\lambda}J(\\phi,\\lambda)$; this bias is a key property of bi-level RL that needs to be accounted for in order to perform convergence analysis. In contrast, the convergence analysis of standard bi-level works such as Kwon et al. (2024) assumes this bias to be zero (See Assumption 11 in Kwon et al. (2024)).  In Section 5.1, \"**Gradient Estimation Error**\" introduces a novel method for separating estimation bias   from stochastic noise in the gradient estimation error for the proxy objective defined in Kwon et al. (2024). This novel decomposition allows convergence analysis within the framework of Kwon et al. (2024) in the presence of biased gradient estimates. \n\n2. **Lemma 1:**  specifically upper bounds the component of gradient estimation error which arises due to the estimation bias for $\\nabla_{\\lambda}J(\\phi,\\lambda)$. We obtain sample complexity bounds of $\\mathcal{O}(\\epsilon^{-3})$ within the framework of Kwon et al. (2024), where previous bounds were $\\mathcal{O}(\\epsilon^{-7})$ (Kwon et al., 2024) and $\\mathcal{O}(\\epsilon^{-6})$ (Chen et al., 2024). Lemma 1 allows us to obtain these improved bounds in the presence of biased estimates for $\\nabla_{\\lambda}J(\\phi,\\lambda)$.\n\n3. **Unified first-order analysis** We thus obtain the first provable sample complexity for bilevel RL *without* tabular or second-order assumptions.\n\n**Empirical Demonstration:**\n\n In Appendix F of the Supplementary Material, we have implemented our algorithm in two RLHF(Reinforcement Learning From Human Feedback) simulations, namely Walker (Deep Mind Control Suite (2013)) and Door Open (Meta World + (2025)). We evaluate our algorithm against [PEBBLE] (Lee et al. 2021), which is a state-of-the-art RLHF algorithm, and show performance improvement.\n\n---\n\n>**Weakness 3** - There are a few typos in the paper. For example, in the conclusion, the sample complexity should be stated as $\\mathcal{O}(\\epsilon^{-3})$ rather than $\\mathcal{O}(\\epsilon^{-4})$.\n\n**Response to Weakness 3:**\n\nThanks a lot, we will revise the typos in the final version, including the one mentioned.\n\n---\n**References**\n\n- Lesi Chen, Jing Xu, Jingzhao Zhang \"On Finding Small Hyper-Gradients in Bilevel Optimization:Hardness Results and Improved Analysis\" COLT 2024.\n\n- Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak. \"On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation\". ICLR 2024\n\n- Kaiyi Ji, Junjie Yang, Yingbin Liang. \"Bilevel Optimization: Convergence Analysis and Enhanced Design\". ICML 2021.\n\n- Yifan Yang, Peiyao Xiao, Kaiyi Ji. \"Achieving $\\mathcal{O}(\\epsilon^{−1.5})$ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization\".  NeurIPS 2023\n\n- Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Dinesh Manocha, Huazheng Wang, Mengdi Wang, Furong Huang. \"PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback\". ICLR 2024\n\n- Yan Yang$^{1}$, Bin Gao, Ya-xiang Yuan \"Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity\". AISTATS 2025\n\n- Han Shen, Zhuoran Yang, Tianyi Chen. \"Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF\", ICML 2024.\n\n- Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, Martin Riedmiller. \"Deep Mind Control Suite\". arxiv,2018\n\n- Reginald McLean, Evangelos Chatzaroulas, Luc McCutcheon, Frank Röder, Tianhe Yu, Zhanpeng He, K.R. Zentner, Ryan Julian, J K Terry, Isaac Woungang, Nariman Farsad, Pablo Samuel Castro. \"Meta-World+: An Improved, Standardized, RL Benchmark\". arxiv,2025\n\n- Kimin Lee, Laura Smith, Pieter Abbeel. \"PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training\" .ICML 2021"}, {"review_id": "HIOG3nVbZ4", "reviewer": "Reviewer_XAuT", "summary": "This paper investigates bilevel RL from a theoretical lens. Their algorithm uses penalty based methods and they prove that their algorithm admits a sample complexity of $O(\\epsilon^{-3})$.", "questions": "What is the purpose of the KL term in the reward function? This seems like a very contrived way of tying BRL to RLHF. Do the results still hold without the KL regularization term?\n\nCan you prove a lower bound in this setting?\n\n\nI think these may be typos, but disregard if they are not:\n- Page 9 line 296, should it be $\\eps^{-3}$ instead of $\\eps^{-4}$?\n- It seems some of the references are duplicated, e.g. 1 and 2, 21 and 22, etc.", "limitations": "The limitations are discussed in the paper.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThey the first sample complexity bound for bilevel RL.\n\nThey improve the sample complexity for general bilevel optimization from $\\epsilon^{-6}$ to $\\epsilon^{-3}$.\n\n\nWeaknesses:\n\nThey do not prove a lower bound to show that their upper bound is tight.\n\nWhat are some examples of $G(\\theta, \\lambda)$? While Assumption 3 is present in [1], it seems this is a strong assumption and not reasonable in RL. Line 133-134 states ``However, such assumptions (unbiased estimates of the upper and lower level objectives) do not hold in BRL, where gradient estimates are inherently biased due to the underlying MDP dynamics.'', which seems to contradict Assumption 3.", "was_revised": true, "final_justification": "My recommended score would be a 3.5, but this is not a option. While they do improve the dependence on \\epsilon, they do not give a good justification on why the bound is good, i.e., no lower bound. Even though related works do not provide lower bounds, they do not give intuition or an explanation on the difficulties of improving their bound.", "rebuttal": "> **Weakness 1** They do not prove a lower bound to show that their upper bound is tight.\n\n**Response to Weakness 1:** Thank you for noting this point.  Establishing lower bounds for bilevel problems with non-convex lower levels ***remains open*** to our knowledge, the only sample-complexity lower bound currently available is for the convex-lower-level setting (Ji et al., 2024).  In the non-convex regime we study, no general lower-bound technique has yet been developed, and recent surveys list it as an active research challenge.  Consequently, none of the works we benchmark against, including Chakraborty et al.(2024), Shen et al. (2024), and  Yang et al. (2025), provide lower bounds either.\n\nWhile a formal tightness result is therefore out of reach at present, our upper bound improves on prior rates (from $\\mathcal{O}(\\varepsilon^{-6}) / \\mathcal{O}(\\varepsilon^{-7})$ to $\\mathcal{O}(\\varepsilon^{-3}))$ and, we hope, will help guide future efforts toward proving lower bounds in the non-convex bilevel setting.  We will add this context to the paper to clarify why a lower-bound analysis is not yet available and to highlight it as an important direction for future work.\n\n---\n> **Weakness 2**  What are some examples of  $G(\\phi,\\lambda)$?\n\n**Response to Weakness 2:** An example of $G(\\phi,\\lambda)$ is the preference function defined as \n\n$$G(\\phi,\\lambda) = \\mathbb{E}_{(\\sigma_1,\\sigma_2) \\sim \\pi.({\\lambda}) ,y} (y{\\cdot}P^{\\phi}( \\sigma_1 > \\sigma_2   ) + (1-y){\\cdot}P^{\\phi}( \\sigma_1 < \\sigma_2  ))$$\n\nHere $P^{\\phi}(\\sigma_{1} \\ge \\sigma_{2})$ is defined as\n\n$$P^{\\phi}(\\sigma_{1} \\ge \\sigma_{2}) = \\frac{  exp( Q(\\sigma^1)) }{    exp( Q(\\sigma^1)) +   exp( Q(\\sigma^2))  }$$\n\nWhere $exp( Q(\\sigma^k))  =  \\sum_{i=1}^{H} r^{\\phi}(s^k_i, a^k_i)  $  represents the cumulative reward of the trajectory $\\sigma_{k} = (s^k_i, a^k_i)_{i \\in (1,H)}$\n\nHere $G(\\phi,\\lambda)$ is a loss function that optimizes the reward function $r^{\\phi}$ such that it aligns with human preferences. The inputs for $G(\\phi,\\lambda)$ are in the form of a tuple $(y,\\sigma_{1},\\sigma_{2})$. Here, $\\sigma_{1},\\sigma_{2}$ are two pairs of trajectories generated by a policy $\\pi(\\lambda)$ and $y$ is a label which is 1, if trajectory $\\sigma_{1}$ is preferred over $\\sigma_{2}$ by a human and 0 if vice-versa.\n\nWe have used this $G(\\phi,\\lambda)$ loss function in our empirical demonstration in Appendix F of the Supplementary Material. We implement our algorithm for two simulated environments, namely Walker (Deep Mind Control Suite (2013)) and Door Open (Meta World Control Suite (2025)). In both these environments, we can query the system for tuples $(y,\\sigma_{1},\\sigma_{2})$ to calculate the gradient of the upper loss function. We evaluate our algorithm against the [PEBBLE] (Lee et al. 2021), which is a state-of-the-art RLHF algorithm, and show a performance improvement.\n\n---\n > **Weakness 3:** While Assumption 3 is present in [1], it seems this is a strong assumption and not reasonable in RL. Line 133-134 states ``However, such assumptions (unbiased estimates of the upper and lower level objectives) do not hold in BRL, where gradient estimates are inherently biased due to the underlying MDP dynamics.'', which seems to contradict Assumption 3\n\n**Response to Weakness 3:** Thank you for pointing out this ambiguity. We intended to distinguish between the two gradients in the bilevel objective:\n\n- **Upper-level gradient** ($\\nabla_\\phi G(\\phi,\\lambda)$): can be estimated unbiasedly from sampled trajectories.\n- **Lower-level gradient** ($\\nabla_\\lambda J(\\phi,\\lambda)$): generally biased in practical RL because the critic $Q_{\\lambda}(s,a)$ is only an approximation of the true $Q^{\\pi}$.\n\nAssumption 3 therefore, applies only to the upper objective. We will revise the text on lines 133–134 to read:\n\n“***The assumption of unbiased upper-level gradients holds, but for the lower level in BRL, the gradient estimator is inherently biased due to function-approximation error in the critic.***”\n\nEquation (12) in the manuscript already shows how this bias enters the analysis; we will cross-reference it explicitly and add citations to standard results on biased critic gradients in actor–critic methods.\n\nWe appreciate the reviewer’s careful reading and will ensure the final version makes this distinction clear.\n\n---\n> **Question 1** What is the purpose of the KL term in the reward function? This seems like a very contrived way of tying BRL to RLHF. Do the results still hold without the KL regularization term? \n\n\n**Response to Question 1:**  The KL-divergence term serves two complementary roles: \n - **Practical regularization in RLHF.** In reinforcement learning from human feedback (RLHF), it is customary to penalize deviation from a reference policy via a KL term (e.g., PPO-RLHF, DPO).  This stabilizes training, limits reward-hacking, and keeps the updated policy close to the supervised baseline.  We include the same term so that our theoretical analysis matches the algorithms widely used in practice.\n- **Generality of the theory.** Treating the KL weight $\\beta$ as a parameter lets us cover both the RLHF regime ($\\beta>0$) and pure reinforcement learning ($\\beta=0$) within a single framework.\n\n**Do the guarantees depend on $\\beta>0?$**\nNo.  All convergence and sample-complexity results remain valid when $\\beta=0$.  Setting $\\beta=0$ simply drops the regularizer from the reward; the proofs require no additional modifications, because the KL term is handled as an additive, Lipschitz-smooth component that can be zeroed out.  We will add a remark to the paper to state this explicitly and to clarify that the KL term is optional rather than essential.\n\n---\n> **Question 2** Can you prove a lower bound in this setting?\n\n**Response to Question 2:**  The question of a lower bound on the bilevel optimization with a non-convex lower level is still an open question. We will mention this in future work directions. \n\n---\n\n**Typos**: Thank you for pointing out the typos. We will fix them in the final version.\n\n---\n**References**\n\nKaiyi Ji, Yingbin Liang.  \"Lower Bounds and Accelerated Algorithms for Bilevel Optimization\". JMLR, 2022\n\nSouradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Dinesh Manocha, Huazheng Wang, Mengdi Wang, Furong Huang. \"PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback\". ICLR 2024\n\nHan Shen, Zhuoran Yang, Tianyi Chen. \"Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF\", ICML 2024.\n\nYan Yang, Bin Gao, Ya-xiang Yuan \"Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity\". AISTATS 2025\n\nKimin Lee, Laura Smith, Pieter Abbeel. \"PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training\" .ICML 2021\n\nYuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, Martin Riedmiller. \"Deep Mind Control Suite\". arxiv,2018\n\nReginald McLean, Evangelos Chatzaroulas, Luc McCutcheon, Frank Röder, Tianhe Yu, Zhanpeng He, K.R. Zentner, Ryan Julian, J K Terry, Isaac Woungang, Nariman Farsad, Pablo Samuel Castro. \"Meta-World+: An Improved, Standardized, RL Benchmark\". arxiv,2025"}]

Author rebuttal:

Meta-review: This paper tackles the sample complexity of bilevel reinforcement learning (BRL), a framework relevant to settings such as inverse RL and RLHF. The authors propose a first-order, Hessian-free algorithm and establish what they claim to be the first sample complexity bounds for BRL in continuous state-action spaces. The key enabling technique in their analysis is the decomposition of the gradient estimation error arising in RL. Nevertheless, the capability of handling coninuous state-action space stems from the adoption of the first-order gradient expression in existing literature Kwon et al. (2024). Their results extends to general bi-level optimization settings with non-convex lower levels, and improved the existing sample complexity results. The paper also provides finite-time rates, a bias-aware gradient error decomposition, and an implementation demonstrating empirical gains over a strong RLHF baseline (PEBBLE).

Reviewers generally found the paper technically sound and has meaningful contributions. Strengths include the novelty of providing the first explicit sample complexity bounds for BRL in continuous domains, the practical relevance of the first-order Hessian-free approach, and a clear theoretical contribution that improves known rates for general bilevel optimization. The rebuttal clarified key points, including the role of the PL condition in RL settings, the precise assumptions (Lipschitz Hessians rather than “smooth”), unbiasedness vs. bias in gradient estimators, and the query complexity in RLHF scenarios. Concerns centered on (i) reliance on the PL condition, which may not hold broadly across RL settings; (ii) the absence of matching lower bounds to demonstrate tightness; (iii) some initial lack of clarity in assumptions and connections to prior bilevel RL, bilevel optimization, and RLHF work; and (iv) the need for a clearer presentation of technical novelties, especially in relation to prior analyses. Reviewers also noted that the paper’s exposition could better contextualize bilevel RL relative to standard RL, inverse RL, and RLHF. These issues were largely addressed in the rebuttal, with promised revisions to clarify assumptions, correct typos, and expand related work.

Overall, this paper makes a meaningful contribution with rich results that advancing the understanding of bilevel RL.
Decision: Accept (poster)