arXiv:2602.00282 · v2

Constrained Bilevel Reinforcement Learning via Approximate Lower-Level Responses

首次提交 2026-01-31 04:10

版本更新 2026-11-12 10:54

雷达观测 2026-11-13 14:16

摘要

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