cs.LGJan 30, 2026

Constrained Bilevel Reinforcement Learning via Approximate Lower-Level Responses

Authors: Naman Saxena, Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, US

Abstract

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)\widetilde{\mathcal{O}}(δ_\ell^{-6}ε_o^{-2}) over both levels, where δℓδ_\ell is the lower-level accuracy and εoε_o is the upper-level stationarity error. Setting δℓ=εo=εδ_\ell=ε_o=ε gives O~(ε−8)\widetilde{\mathcal{O}}(ε^{-8}).

Figures & tables

Explore similar work

CardsList
  1. Improved Sample Complexity Analysis For First Order Bilevel Reinforcement Learning

    Nov 1, 2026Mudit Gaur, Naman Saxena, Vaneet AggarwalReinforcement LearningSample-Efficient RL

  2. Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

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

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

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