betaFeedback

WorksComputer Science

Improved Sample Complexity Analysis For First Order Bilevel Reinforcement Learning

Abstract

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)\widetilde{\mathcal O}(\varepsilon^{-2}) sample complexity for O(ε)O(\varepsilon) expected squared gradient norm of the upper objective induced by the selected regularized policy response, including critic training.

Introduction

Bilevel reinforcement learning (BRL) couples reward learning with policy adaptation: changing a reward changes both the responding policy and the trajectories used to evaluate the upper objective. This dependence underlies reward design and reinforcement learning from human feedback. Establishing convergence requires justifying the policy-optimization geometry and controlling value estimation while rewards, policies, and sampling distributions evolve together.

Tabular analyses exploit finite policy and value representations [24, 30]. In particular, Yang et al. [30] use soft Bellman structure to obtain first-order upper-gradient calculations for a global regularized response. Zeng et al. [31] establish a single-loop first-order tabular actor–critic guarantee under regularization-dependent PL and additional Hessian conditions. Extending these guarantees beyond finite state–action representations requires controlling actor and critic approximation and learning errors.

Beyond tabular formulations, PARL [5] studies policy alignment with parameterized policies and accounts for the dependence of the upper sampling distribution on the lower response. Its formulation accommodates continuous states, but its A-PARL algorithm uses implicit hypergradient calculations involving mixed derivatives and an inverse lower-level Hessian. It is therefore not fully first order, and its convergence analysis assumes access to the required derivative oracles. Gaur et al. [10] establish a first-order O~(ε−3)\widetilde{O}(\varepsilon^{-3}) sample-complexity bound for continuous state–action spaces under a uniform lower-level Polyak–Łojasiewicz (PL) condition.

Uniform PL does not follow from smooth policy parameterization alone. Our counterexample in Proposition C.52 has smooth positive action probabilities and exactly representable values, yet admits a suboptimal stationary point, violating PL. This motivates specifying an actor construction, deriving its required local geometry, and proving that the learning dynamics remain in the region where that geometry holds. Additionally, PL conditions in general do not hold for arbitrary RL setups. Thus works which rely on PL assumptions are not applicable for arbitrary actor and critic classes.

Additionally, critic learning introduces a distinct difficulty. The value targets change with both the reward and the policy, and the response correction uses differences between nearby policies divided by their separation. Separate bounds on the two critic errors do not directly control their difference after this normalization as the separation shrinks. A coupled guarantee must therefore establish persistent critic stability and track both the individual value errors and their normalized endpoint differences. Thus we have the following question.

Can we obtain improved sample-complexity guarantees for single-loop, first-order bilevel reinforcement learning beyond tabular settings, using explicit neural actors and nonlinear critics, while deriving the required local geometry and controlling their coupled learning errors?

We answer this question in the affirmative and address these challenges with explicit tied multilayer actors and a nonlinear critic built from fixed features. An initialization covariance condition, architectural derivative bounds, and fixed reference-policy KL regularization yield local curvature; a joint containment proof makes this geometry valid throughout training with high probability. Shared trajectories control the noise in the response correction. Under feature excitation and realizability of the regularized value family, our paired critic analysis establishes stability and tracking of the required normalized errors. Residual-controlled actor solves complete the finite, first-order implementation. Together, these ingredients yield O~(ε−2)\widetilde{O}(\varepsilon^{-2}) sample complexity for O(ε)O(\varepsilon) expected squared upper-gradient norm, including persistent critic training, preference sampling, and metric initialization. The guarantee covers continuous states and finite actions. under the stated architecture, initialization, regularity, and value-representation conditions.

  • Variance control for coupled response estimation. We estimate the policy-response correction by evaluating nearby policies on shared, appropriately weighted trajectories. This coupling keeps sampling variance controlled as the policies being compared become closer, allowing the response approximation to become more accurate without amplifying sampling noise. Together with paired critic-error control and persistent actor–critic tracking, this mechanism supports our improved sample complexity relative to Gaur et al. [10].

  • Improved interaction complexity with single-loop first-order learning. We establish the O~(ε−2)\widetilde{O}(\varepsilon^{-2}) interaction bound while reward, actor, and critic updates proceed together. Shared trajectory sampling controls response-estimation noise as the perturbation shrinks, and a combined descent and tracking potential accounts for all three learning processes and their sampling costs.

  • Explicit actor–critic architectures with coupled learning guarantees. We specify multilayer neural actors and a nonlinear critic built from fixed features. We show that smooth policies and exact value realizability do not imply uniform PL, and derive local actor curvature from initialization identifiability and fixed reference-KL regularization. We prove containment of the coupled iterates and stability of persistent critic learning, controlling critic errors as rewards, policies change. A continuous-state construction verifies the actor and critic conditions (Appendix § 10.11).

Problem Formulation

MDP and sampling access. For a reward parameter x∈Ox=Rdxx \in\mathcal{O}_x = \mathbb{R}^{d_x}, let Mx=(S,A,P,rx,ρ,γ)\mathcal{M}_x = (\mathcal{S}, \mathcal{A}, P, r_x, \rho, \gamma) be a discounted Markov decision process: S\mathcal{S} is compact and possibly continuous, A\mathcal{A} is finite, P(ds′∣s,a)P(ds' \mid s,a) is the transition law, rx(s,a)r_x(s,a) is the reward, ρ\rho is the reset distribution, and γ∈(0,1)\gamma\in(0,1) is the discount. Only the reward and upper sample loss depend explicitly on xx. We can independently reset from ρ\rho, generate trajectories under the current policies, and query feedback on trajectory tuples. The reward and its first derivatives are evaluable; the transition kernel need not be known.

Multilayer neural actor. Let LL be the hidden depth, m=(m1,…,mL)\mathbf{m} = (m_1,\ldots,m_L) the hidden widths, and α∈Rr\alpha\in\mathbb{R}^r the trainable coordinates. A scalar score Fm,αF_{\mathbf{m},\alpha} tilts a fixed strictly positive reference policy:

πm,α(a∣s)=πref(a∣s)eFm,α(s,a)∑b∈Aπref(b∣s)eFm,α(s,b).(1)\pi_{\mathbf{m},\alpha}(a \mid s) = \frac{\pi_{\mathrm{ref}}(a \mid s)e^{F_{\mathbf{m},\alpha}(s,a)}}{\sum_{b\in\mathcal{A}}\pi_{\mathrm{ref}}(b \mid s)e^{F_{\mathbf{m},\alpha}(s,b)}}. \tag*{(1)}

Two coupled smooth multilayer networks define the score. Their weights vary through a fixed map of the same rr coordinates around initialization; we call this map the retained actor chart. Depth LL and dimension rr remain fixed as widths vary, and Fm,0=0F_{\mathbf{m},0}=0 gives πm,0=πref\pi_{\mathbf{m},0}=\pi_{\mathrm{ref}}. Appendix § 10.§ 1 specifies the chart, normalization, inputs, and activations.

Lower and upper objectives. Let Pm,α\mathbb{P}_{\mathbf{m},\alpha} be the trajectory law under reset s0∼ρs_0 \sim\rho, actions at∼πm,α(⋅∣st)a_t \sim\pi_{\mathbf{m},\alpha}(\cdot\mid s_t), and transitions PP; write Em,α\mathbb{E}_{\mathbf{m},\alpha} for its expectation. Fix tuple size II and trajectory length KK independently of accuracy. The tuple ξ=(ξ1,…,ξI)\xi= (\xi^1,\ldots,\xi^I) contains independent length-KK state–action trajectories, with product law (Pm,αK)⊗I(\mathbb{P}_{\mathbf{m},\alpha}^{K})^{\otimes I}. Feedback follows a fixed conditional law D(⋅∣ξ)\mathcal{D}(\cdot\mid\xi), independent of (x,α)(x,\alpha) given the tuple. For sample loss L(x;ξ,Y)L(x;\xi,Y) and fixed Kullback–Leibler (KL) regularization coefficient τ>0\tau> 0, define

gτ,m(x,α)=(1−γ)Em,α∑t≥0γt[−rx(st,at)+τlog⁡πm,α(at∣st)πref(at∣st)],(2)g_{\tau,\mathbf{m}}(x,\alpha) = (1-\gamma)\mathbb{E}_{\mathbf{m},\alpha}\sum_{t\geq0}\gamma^t\left[-r_x(s_t,a_t)+\tau\log\frac{\pi_{\mathbf{m},\alpha}(a_t \mid s_t)}{\pi_{\mathrm{ref}}(a_t \mid s_t)}\right], \tag*{(2)}
fm(x,α)=Eξ∼(Pm,αK)⊗I, Y∼D(⋅∣ξ)L(x;ξ,Y).(3)f_{\mathbf{m}}(x,\alpha) = \mathbb{E}_{\xi\sim(\mathbb{P}_{\mathbf{m},\alpha}^{K})^{\otimes I},\,Y\sim\mathcal{D}(\cdot\mid\xi)}L(x;\xi,Y). \tag*{(3)}

Thus lower minimization maximizes regularized return, while the upper loss depends on the policy through its trajectory distribution. For Bradley–Terry comparisons, I=2I=2 and Y∈{0,1}Y\in\{0,1\}, with Y=1Y=1 favoring ξ1\xi^1.

Writing (sti,ati)(s_t^i, a_t^i) for trajectory ii, the loss is

Δx=∑t=0K−1[rx(st1,at1)−rx(st2,at2)],L(x;ξ,Y)=log⁡(1+eΔx)−YΔx.(4)\Delta_x = \sum_{t=0}^{K-1} [r_x(s_t^1, a_t^1) - r_x(s_t^2, a_t^2)], \qquad L(x; \xi, Y) = \log(1 + e^{\Delta_x}) - Y\Delta_x. \tag*{(4)}

Correct specification of the preference model is unnecessary (Appendix § 10.§ 2).

Bilevel problem and stationarity target. Let Bgeom={α:∥α∥2<Rgeom}\mathcal{B}_{\mathrm{geom}} = \{\alpha: \|\alpha\|_2 < R_{\mathrm{geom}}\}. For the fixed τ\tau and radius supplied by § 4, we study

min⁡x∈RdxΦτ,m(x):=fm(x,α0,m∗(x)),where α0,m∗(x)∈arg⁡min⁡α∈Bgeomgτ,m(x,α).(5)\min_{x\in\mathbb{R}^{d_x}} \Phi_{\tau,m}(x) := f_m(x, \alpha_{0,m}^*(x)), \qquad \text{where }\alpha_{0,m}^*(x) \in\arg\min_{\alpha\in\mathcal{B}_{\mathrm{geom}}} g_{\tau,m}(x,\alpha). \tag*{(5)}

The later conditions make this minimizer unique, interior, and smooth in xx, with ∇αgτ,m(x,α0,m∗)=0\nabla_\alpha g_{\tau,m}(x,\alpha_{0,m}^*) = 0. The ball selects a local response in the full actor space Rr\mathbb{R}^r; subscript 0 denotes the unperturbed response. For accuracy ε>0\varepsilon> 0, our goal is an output satisfying E∥∇Φτ,m(xout)∥2=O(ε)\mathbb{E}\|\nabla\Phi_{\tau,m}(x_{\mathrm{out}})\|^2 = O(\varepsilon).

Value function and nonlinear critic. Hereafter suppress actor widths, write g=gτg = g_\tau, and use hxh_x, hαh_\alpha for partial gradients of a function hh. Define qx,α=−rx+τlog⁡(πα/πref)q_{x,\alpha} = -r_x + \tau\log(\pi_\alpha/\pi_{\mathrm{ref}}) and the unnormalized discounted action value

Qx,αtrue(s,a)=Eαs,a[∑t≥0γtqx,α(st,at)],Q_{x,\alpha}^{\mathrm{true}}(s,a) = \mathbb{E}_{\alpha}^{s,a}\left[\sum_{t\geq0}\gamma^t q_{x,\alpha}(s_t,a_t)\right],

where Eαs,a\mathbb{E}_{\alpha}^{s,a} starts the process at (s0,a0)=(s,a)(s_0,a_0) = (s,a). For a fixed bounded feature map ϕQ:S×A→RdQ\phi_Q : \mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d_Q}, coordinates θ∈RdQ\theta\in\mathbb{R}^{d_Q}, and scale mQ≥1m_Q\geq1, use

QmQ,θ(s,a)=mQtanh⁡(ϕQ(s,a)⊤θ/mQ).(6)Q_{m_Q,\theta}(s,a) = \sqrt{m_Q}\tanh\left(\phi_Q(s,a)^\top\theta/\sqrt{m_Q}\right). \tag*{(6)}

The scale controls nonlinearity at fixed dimension. § 3 trains this critic persistently; Appendix § 10.11 jointly verifies the actor and critic assumptions in a continuous-state instance.

Response-chain correction. With response Jacobian Dxα0∗(x)∈Rr×dxD_x\alpha_0^*(x)\in\mathbb{R}^{r\times d_x},

References

  1. [1]Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 (98):1–76, 2021.
  2. [2]Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. Advances in Neural Information Processing Systems, 35:8013–8026, 2022.arxiv.org/abs/2207.04888
  3. [3]Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3):950–973, 2021.arxiv.org/abs/1806.02450
  4. [4]Shalabh Bhatnagar, Richard S. Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor–critic algorithms. Automatica, 45(11):2471–2482, 2009.DOI
  5. [5]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 from human feedback. In International Conference on Learning Representations, volume 2024, pages 24410–24449, 2024.arxiv.org/abs/2308.02585
  6. [6]Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning, pages 9827–9869. PMLR, 2023.arxiv.org/abs/2302.01734
  7. [7]Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages 1568–1577. PMLR, 2018.
  8. [8]Mudit Gaur, Vaneet Aggarwal, and Mridul Agarwal. On 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 of Proceedings of Machine Learning Research, pages 11013–11049. PMLR, 23–29 Jul 2023.arxiv.org/abs/2211.07675
  9. [9]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 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 15153–15179. PMLR, 21–27 Jul 2024.arxiv.org/abs/2405.01843
  10. [10]Mudit Gaur, Utsav Singh, Amrit Singh Bedi, Raghu Pasupathy, and Vaneet Aggarwal. On the sample complexity bounds of bilevel reinforcement learning. In 39th Conference on Neural Information Processing Systems (NeurIPS 2025), 2025.DOI
  11. [11]Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020.
  12. [12]Kaiyi Ji. Lower complexity bounds for nonconvex-strongly-convex bilevel optimization with first-order oracles. In International Conference on Machine Learning, 2026.arxiv.org/abs/2511.19656
  13. [13]Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882–4892. PMLR, 2021.arxiv.org/abs/2010.07962
  14. [14]Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Probably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137–2143. PMLR, 2020.arxiv.org/abs/1907.05388
  15. [15]Sham M. Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, volume 14, 2001.
  16. [16]Zhifa Ke, Zaiwen Wen, and Junyu Zhang. An improved finite-time analysis of temporal difference learning with deep neural networks. In Forty-first International Conference on Machine Learning, 2024.arxiv.org/abs/2405.04017
  17. [17]Vijay R. Konda and John N. Tsitsiklis. Actor–critic algorithms. In Advances in Neural Information Processing Systems, volume 12, 2000.
  18. [18]Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference on Learning Representations, volume 2024, pages 47473–47518, 2024.arxiv.org/abs/2309.01753
  19. [19]Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International conference on machine learning, pages 6305–6315. PMLR, 2020a.arxiv.org/abs/2006.04045
  20. [20]Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-based interior-point method for non-convex bi-level optimization. In International conference on machine learning, pages 6882–6892. PMLR, 2021.arxiv.org/abs/2106.07991
  21. [21]Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33: 7624–7636, 2020b.
  22. [22]P. Marbach and J.N. Tsitsiklis. Simulation-based optimization of markov reward processes. IEEE Transactions on Automatic Control, 46(2):191–209, 2001.
  23. [23]John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889–1897. Pmlr, 2015.arxiv.org/abs/1502.05477
  24. [24]Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty-based methods for bilevel reinforcement learning and rlhf. Journal of Machine Learning Research, 26(114):1–49, 2025.arxiv.org/abs/2402.06886
  25. [25]Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, pages 1057–1063, 1999. URL https://proceedings.neurips.cc/paper/1999/hash/464d828b85b0bed98e80ade0a5c43b0f–Abstract.html.
  26. [26]Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389–434, 2012.
  27. [27]Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=BJgQfkSYDS.arxiv.org/abs/1909.01150
  28. [28]Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229–256, 1992.
  29. [29]Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/2e1b24a664f5e9c18f407b2f9c73e821–Abstract.html.arxiv.org/abs/2004.12956
  30. [30]Yan Yang, Bin Gao, and Ya-xiang Yuan. Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 4780–4788. PMLR, 03–05 May 2025.arxiv.org/abs/2405.19697
  31. [31]Sihan Zeng, Sujay Bhatt, Sumitra Ganesh, and Alec Koppel. A hessian-free actor-critic algorithm for bi-level reinforcement learning with applications to llm fine-tuning. arXiv preprint arXiv:2601.16399, 2026.arxiv.org/abs/2601.16399

Paper details

vlnc:W_eqxyuj9j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Generative AI tools

View statement
Looking for related papers…
Contents