Constrained Bilevel Reinforcement Learning via Approximate Lower-Level Responses

We study constrained bilevel reinforcement learning when the lower-level problem is a constrained Markov decision process with a generally parameterized policy. The exact constrained solution map can be nonunique and need not possess the stability or differentiability required by standard hypergradient analysis. We therefore formulate the bilevel problem through an approximate lower-level response characterized directly by expected reward suboptimality and constraint violation. This response is produced by a finite-sample stochastic primal–dual natural policy-gradient method whose natural-gradient direction is approximated by vanilla stochastic gradient descent. To differentiate the upper objective induced by this approximate response, we introduce an unbiased two-point encoding of every reward and constraint observation and apply a score-function identity to the probability law of the complete lower-level training procedure. The resulting estimator does not differentiate through the projected primal–dual recursion or products of lower-update Jacobians. We establish lower-level reward and feasibility guarantees, upper-level stationarity, and an end-to-end environment-interaction complexity of $\tilde{O}({ϵ}_{\ell }^{-6}{ϵ}_o^{-2})$; setting both accuracies to $ϵ$ gives $\tilde{O}({ϵ}^{-8})$.