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.