Constrained Bilevel Reinforcement Learning via Approximate Lower-Level Responses
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 over both levels, where is the lower-level accuracy and is the upper-level stationarity error. Setting gives .
Figures & tables
| References | Inner Level | Inner Level Constraints | Hessian Free | Iteration Complexity | Sample Complexity |
| Hong et al. (2023) | Weakly Convex | ✗ | ✗ | ✗ | |
| Chakraborty et al. (2024) | Non-convex | ✗ | ✗ | ✗ | |
| Thoma et al. (2024) | Non-convex | ✗ | ✓ | ✗ | |
| Yang et al. (2025) | Non-convex | ✗ | ✓ | ||
| Shen et al. (2025) | Non-convex | ✗ | ✓ | ✗ | |
| Gaur et al. (2025) | Non-convex | ✗ | ✓ |
| References | Inner Level | Inner Level Constraints | Iteration Complexity | Sample Complexity |
| Tsaknakis et al. (2022) | Strongly convex | Linear | ✗ | |
| Xiao et al. (2023) | Strongly convex | Equality only | ✗ | |
| Xu and Zhu (2023) | Strongly convex | Convex | ✗ | ✗ |
| Khanduri et al. (2023) | Strongly convex | Linear | ✗ | |
| Liu et al. (2023) | Non-convex | Non-convex | ✗ | ✗ |
| Jiang et al. (2024) | Strongly convex | Convex | ✗ |