Improved Sample Complexity Analysis For First Order Bilevel Reinforcement Learning
Authors: Mudit Gaur, Naman Saxena, Vaneet Aggarwal
Organizations: Department of Electrical and Computer Engineering, Ohio State Univeristy · Edwardson School of Industrial Engineering, Purdue University
Bilevel reinforcement learning optimizes an upper-level objective through the policy response to a lower-level reinforcement learning problem. Such problems arise when learning a reward model while adapting a policy to that reward. However, a gap remains between sample-complexity guarantees and practical actor--critic training. Tabular analyses restrict applicability to finite spaces, while continuous-state analyses often impose a uniform Polyak--Łojasiewicz (PL) condition. We show that this condition need not hold even for smooth positive policies with exactly representable values. We develop a single-loop, fully first-order method for continuous states and finite actions with specified multilayer neural actors and a persistently trained nonlinear critic built from fixed features. Under explicit initialization, regularity, feature-excitation, and value-realizability conditions, fixed reference-KL regularization yields local curvature, and we prove containment of the coupled iterates. Shared trajectories control sampling noise, while paired critic analysis controls normalized critic-error differences as the response perturbation shrinks. A joint descent and tracking argument establishes an improved O(ε−2) sample complexity for O(ε) expected squared gradient norm of the upper objective induced by the selected regularized policy response, including critic training.
Figures & tables
Work
Continuous State Space
Lower geometry
Nonlinear A–C analysis
SL
FO
Sample complexity
Chakraborty et al. (2024)
✓
PL; Hessian conditions
×
×
×
×
Shen et al. (2025)
×
Policy-space structure
×
×
✓
×
Yang et al. (2025) †
×
Soft Bellman structure
×
×
✓
O(ε−3.5)
Gaur et al. (2025)
✓
Uniform PL
×
×
✓
O(ε−3)
Zeng et al. (2026) ‡
×
Reg.-dependent PL; Hessian conditions
×
✓
✓
O(ε−3)
This work
✓
Derived local curvature
✓
✓
✓
O(ε−2)
Table 1: Analyzed BRL guarantees. SL: single-loop stochastic tracking; FO: first-order implementation. Nonlinear A–C analysis requires explicit nonlinear actors and critics with coupled training and critic-error control. Dashes mark unestablished guarantees or unreported comparable sample complexitys. Rates use O(ε) squared stationarity under distinct targets and assumptions. † Stoc-SoBiRL; its deterministic model-based variant uses O(1) inner updates. ‡ Fixed regularization, Theorem 2 of version 6; best-iterate output. Our uniform-output bound concerns a selected local regularized response, globally optimal on D under additional PL ( Corollary A.2 ).
Figure 1: Interaction scaling and continuous control. (a) Average squared upper-gradient norm, GT=T−1∑t<T∣Φ′(xt)∣2 , versus total training cost N , for zero and displaced critic initialization. Error bars show 95% t intervals over ten seeds; the dashed line is an N−1/2 reference. (b) Walker Walk evaluation returns: means and one-standard-deviation bands across five matched training seeds.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
x
A2(x)
C2(x)
Φ2′(x)
∣C2∣/∣A2∣
0
−0.15561048
0
−0.15561048
0
0.25
−0.07068856
0.00057120
−0.07011736
0.008081
0.50
−0.00814360
0.00116961
−0.00697399
0.143623
xˉ
−0.00120485
0.00120485
≈0
1
x†
0
0.00120937
0.00120937
—
0.75
0.02048602
0.00113742
0.02162344
0.055522
Appendix
Table 2: Population gradient decomposition for κ=1/2,τ=2 . The ratio at x† is undefined because its denominator is zero.
Figure 2: Population quantities evaluated by deterministic quadrature. Left: upper objective. Middle: full, direct, and response derivatives. Right: the same derivatives near the minimum, with the vertical scale multiplied by 103 . The dashed line is xˉ and the dotted line is x† . These curves illustrate the response mechanism; they are not stochastic convergence results.
τ
Interior minimizer xˉ
Cτ(xˉ)
2
0.5414613800
1.204848558×10−3
4
0.5473047717
3.064773816×10−4
10
0.5489840685
4.927812863×10−5
100
0.5493029200
4.932401058×10−7
Appendix
Table 3: The finite stationary point and its nonzero correction persist as τ increases, with κ=1/2 .
Critic error metric
Initial mean
Final mean
Weighted parameter tracking
416
0.1904
Squared base value error
5.8796
1.141×10−3
Squared normalized paired value error
23.7719
4.437×10−4
Appendix
Table 4: Critic recovery from displaced initialization. Entries are means over ten training seeds; population reference calculations are used only for evaluation.
Seed
Secant
Gaur et al.
Known-reward SAC
1
1682
1800
0
3
1712
1607
0
4
1800
1734
0
5
1612
1591
0
6
1704
1578
0
Appendix
Table 5: Highway-fast auxiliary interactions, in addition to 100,000 main interactions per run.
Figure 3: End-to-end deterministic evaluation returns: mean and one sample SD across five matched training seeds, each contributing a ten-episode mean. The horizontal axis includes cumulative auxiliary response interactions; checkpoint costs are averaged across seeds. Walker Walk starts at its first measured checkpoint, and Highway-fast is shown after exploration warm-up.
Setting
Value
Main environment interactions / replay capacity
100,000 / 100,000
Random / intrinsic warm-up interactions
1000 / 9000
Discount / SAC minibatch size
0.99 / 1024
Actor and critic learning rates / Adam betas
5×10−4 / (0.9,0.999)
Temperature learning rate / initial temperature
10−4 / 0.1 (learned)
Actor / critic-target update frequencies
1 / 2
Appendix
Table 6: Common SAC and collection settings. Feedback settings apply to the two preference methods. Evaluation schedules are specified below.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
Bilevel reinforcement learning (RL) is an important framework within the literature of RL that can be used to formalize various categories of problems, such as meta-learning, hierarchical task decomposition, and reinforcement learning from human feedback (RL-HF). Most of the bilevel RL algorithms are either not scalable because of using hypergradient with Hessian, or they suffer from high sample complexity because of using penalty-based approximation methods. In this work, we propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function. Our proposed algorithm is Hessian-free and obtains an iteration complexity of O(ε−1) and state-of-the-art sample complexity of O~(ε−2) under mild regularity conditions. Further, in our convergence analysis, we are able to remove the assumption of the Polyak-Lojasiewicz (PL) condition on the outer-level objective function present in the prior state-of-the-art sample complexity work.
We study constrained bilevel reinforcement learning in which the lower-level problem is a constrained Markov decision process with a generally parameterized policy. The lower-level solution map can be set-valued and need not be Lipschitz continuous in the upper-level variable, so standard hypergradient analyses do not apply. We therefore define the upper-level objective as the expected upper-level loss of the policy returned by a fixed stochastic lower-level algorithm, which we call the approximate response. This objective is well defined without uniqueness of the lower-level solution. To compute its gradient, we randomize the reward and constraint values used during lower-level training without changing their means, so that the upper-level variable affects training only through known probabilities. This yields an unbiased estimator of the upper-level objective's gradient that does not differentiate through the lower-level updates. We establish lower-level reward and feasibility guarantees, upper-level stationarity, and a total sample complexity of O(δℓ−6εo−2) over both levels, where δℓ is the lower-level accuracy and εo is the upper-level stationarity error. Setting δℓ=εo=ε gives O(ε−8).
Hypergradient (HG) methods for bilevel reinforcement learning (RL) typically assume a white-box follower whose reward is known. In practice, however, the leader rarely knows the follower's reward function and can only observe its trajectories. We address this black-box setting and propose Reward-Estimated Hypergradients (RE-HG), which recovers the follower's reward from these trajectories via inverse RL (IRL). Yet IRL identifies the reward only up to potential-based shaping, a transformation that leaves the follower's behavior unchanged but biases the HG. We prove that, for linear rewards, this bias cancels when IRL estimates are aggregated across sufficiently diverse dynamics, which the leader's own updates naturally supply. To handle finite samples, RE-HG truncates small eigenvalues of the aggregated feature covariance, restoring the identifiable subspace and stabilizing the estimation. Experiments show that RE-HG estimates gradients aligned with a white-box Oracle and achieves comparable performance; empirically, the truncation also suppresses HG explosions, letting RE-HG avoid local optima that trap the Oracle in sharp reward landscapes.
Shigeki Kusaka, Mikoto Kudo, Takumi Tanabe +2
University of Tsukuba · RIKEN AIP · Institute of Science Tokyo +1