cs.LGNov 1, 2026

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

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.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

    Jul 30, 2026Naman Saxena, Mudit Gaur, Vaneet AggarwalReinforcement LearningHypergradient Optimization

  2. Reward-Estimated Hypergradient for Bilevel Reinforcement Learning with Black-Box Follower

    Nov 9, 2026Shigeki Kusaka, Mikoto Kudo, Takumi Tanabe +2Reinforcement Learning