acceptodds
Under review as a conference paper at ICLR 2027

Constrained Bilevel Reinforcement Learning via Approximate Lower-Level Responses

Abstract

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 ; setting both accuracies to gives .

Primary area:
reinforcement learning
Keywords:
Bilevel optimization, constrained, reinforcement learning, MDP, sample complexity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_w8QhOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies bilevel RL in which the upper variable parameterizes the reward and constraint functions of a lower-level CMDP with a general policy class. To avoid the possibly nonunique and nonsmooth constrained solution map, the upper objective is defined as the expected upper loss at the random output of a specific stochastic primal–dual natural policy gradient subroutine, Φ(v)=EZ∼Pv[G(v,θ(Z))]\Phi(v)=\mathbb{E}_{Z\sim P_v}[G(v,\theta(Z))], where ZZ denotes the full lower-level training trace. Every reward and constraint sample used in the run is replaced by an unbiased two-point random encoding whose probabilities depend on vv. The upper variable then affects the run only through these probabilities, and a likelihood-ratio identity gives an unbiased hypergradient without differentiating through the lower-level updates (Thm. 1). The paper proves lower-level reward and feasibility bounds, upper-level stationarity, and a sample complexity of O~(δℓ−6ϵo−2)\tilde O(\delta_\ell^{-6}\epsilon_o^{-2}), where δℓ\delta_\ell is the lower-level accuracy and ϵo\epsilon_o the upper-level tolerance. There are no experiments.

Critical strengths
  1. A new reformulation of bilevel RL. The paper does not work with the solution map of the constrained lower level, which can be nonunique and nonsmooth. Instead, it models the lower-level response as the law PvP_v of a stochastic solver's output and optimizes the expected upper loss under this law. This perspective is interesting because it requires no uniqueness of the lower-level solution set.
  2. The encoding is novel. The two-point encoding replaces each reward and constraint sample with an unbiased Bernoulli variable whose probability depends on vv. After the encoding, vv enters only through these probabilities. As a result, Φ\Phi is differentiable in vv, and its gradient follows from a likelihood-ratio identity without Jacobians or inverse Hessians.
  3. Convergence and complexity analysis. The smoothness and variance of the estimator are derived from the bounded encoding scores rather than assumed. The sample complexity counts both the lower-level runs and the upper-level oracle calls. The proofs I checked (Lemmas 3–10, 13, 16–19) appear correct.
Critical weaknesses

W1. The paper is carelessly written and hard to read. This is my main concern, even though I think the main ideas of this paper are very interesting. Specifically, the formulation is hard to follow because the original bilevel problem is never defined mathematically. Sec. 3.2 only describes it in words before replacing it with Eq. (4). I suggest first writing the original bilevel problem as an equation, and then explaining how it is reformulated into Eq. (4). The terminology also drifts. For instance, the law PvP_v is called the trace law, the training law, the encoded training law, the "distribution of the complete training procedure", and the "probability law of the complete lower-level training procedure". The output θ(Z)\theta(Z) and the score SS also have several different names. The reader must keep checking whether "this law" or "this response" refers to the same object as before.

The abstract shows the problem most clearly. The AI-use statement says that the title and abstract were drafted with generative AI, and the abstract indeed reads that way. It introduces several strange terms without explaining them, some of which may not be necessary at all, and its writing is hard to follow:

  • "…need not possess the stability or differentiability required by conventional hypergradient formulas." "Stability" is not explained and adds nothing to the abstract. If it cannot be made precise there, it should be dropped.
  • "We therefore formulate the bilevel problem through an approximate lower-level response characterized directly by expected reward suboptimality and constraint violation."
    • "Approximate lower-level response" reads as an ϵ\epsilon-best response, i.e., any ϵ\epsilon-optimal and ϵ\epsilon-feasible policy.
    • The "therefore" skips the step that does the work. Approximation alone does not help: the set of ϵ\epsilon-optimal policies contains every exact solution, so it is still not single-valued.
  • "This response is produced by a finite-sample stochastic primal–dual natural policy-gradient method…" If I understand correctly, the specific lower-level solver is not essential to the approach and could in principle be replaced by another one. If so, the abstract need not describe it in such detail. The key step is never stated: the upper objective is an expectation over the solver's random output. The abstract only says "the upper objective induced by this approximate response".
  • "an unbiased two-point encoding … a score-function identity to the probability law of the complete lower-level training procedure."
    • In optimization, "two-point" usually means a two-point zeroth-order gradient estimator.
    • The abstract does not say what the encoding is: each sample is replaced by a scaled random sign whose probability depends on the upper variable. Therefore, the word "two-point encoding" makes readers confusing.
    • It is also unclear from the abstract what "the probability law of the complete lower-level training procedure" refers to.
  • "end-to-end environment-interaction complexity … controllable numerical lower-level accuracy."
    • "End-to-end environment-interaction complexity" is not a standard term in the RL or optimization literature. The usual term is sample complexity, which the paper itself uses in the title of Sec. 5.5.
    • It is unclear what "controllable" means here, and the word is not commonly used for an accuracy.

The contribution list in Sec. 1 has the same problem. Its bold headings, such as "Two-point encoding and training-law gradient" and "End-to-end convergence", rely on terms that have not been explained at that point. As a result, they do not help the reader.

Overall, I recommend that the authors carefully rewrite the paper rather than rely heavily on AI tools.

W2. There are no experiments. An RL topic like this is worth studying mainly for its applications, so the paper needs experiments that show its practical value. Theory alone is not enough: with today's AI tools, proofs are no longer the hardest part.

W3. The assumptions are strong.

  • No policy class is shown to satisfy Assumptions 4–7 together. The example given for Assumption 6 (Gaussian policies with fixed covariance) has continuous actions, which contradicts Assumption 4. The examples given for vanishing ϵbias\epsilon_{\rm bias} (direct/softmax) are tabular, which Assumption 4 excludes; tabular softmax also has a singular Fisher matrix.
  • The uniform Slater condition over all y∈Rdyy\in\mathbb{R}^{d_y} is strong. The only construction given is a bounded perturbation of a strictly safe baseline (App. C.1.5).
  • Algorithm 3 needs to reset the simulator to sampled continuous states.

Nevertheless, from the view of theoretical analysis, adding such assumptions is somewhat understandable, and I do not consider this a major issue.

Minor.

  • Cr:=1+Cr\mathcal{C}_r:=1+C_r uses two nearly identical symbols.
  • ϵℓ\epsilon_\ell is introduced as an "abstract response tolerance" and later redefined as max⁡ϵbias,δℓ\max\\{\sqrt{\epsilon_{\rm bias}},\delta_\ell\\}.
  • δℓ\delta_\ell is defined as K−1/2K^{-1/2} in Sec. 5.2 but is a prescribed input in Thm. 3.
  • In Lemma 2, the step "weakly compact ⇒\Rightarrow tight" needs a Polish state space; take SS closed or S=RdsS=\mathbb{R}^{d_s}.

Summary. I find the insights of this paper interesting (see Strengths 1~2). However, the authors need to present their ideas more carefully so that readers can understand them. Moreover, for this RL paper, experiments appear more important than the developed theory.

Questions for authors
  1. Could you add several concrete application examples of your formulation of bilevel RL with lower-level constraints? Such examples are crucial for demonstrating the practical value of this paper, and in my view even more important than the convergence theory.
  2. Zhou et al. (ICML 2022) relax a bilevel problem to Φ(s)=Em∼p(m∣s)[L(θ∗(m))]\Phi(s)=\mathbb{E}_{m\sim p(m|s)}[L(\theta^*(m))] with mi∼Bern(si)m_i\sim\mathrm{Bern}(s_i). They update ss with L(θ∗(m))∇sln⁡p(m∣s)L(\theta^*(m))\nabla_s\ln p(m|s) (their Eq. 6 and update "PGE"), explicitly to avoid implicit differentiation. Thm. 1 is the same identity with an RL lower level. Beyond the encoding and the sequential trace, how does Thm. 1 differ from their PGE?
  3. When θ⋆(v)\theta^\star(v) is unique and smooth, does the gradient ∇Φ\nabla\Phi given in Thm. 1 (Eq. 11) converge to ddvG(v,θ⋆(v))\frac{d}{dv}G(v,\theta^\star(v)) as δℓ→0\delta_\ell\to0, and at what rate? When the solution is nonunique, which selection does Φ\Phi implement?
  4. Is there a finite-action policy class that satisfies Assumptions 5–7? What is the explicit (1−γ)(1-\gamma) dependence of the final bound?

References

  • Xiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin, Zonghao Chen, and Tong Zhang. Probabilistic bilevel coreset selection. In Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR 162:27287–27302, 2022.
3 comments

We thank the reviewer for the detailed comments. All changes are marked in blue in the revised manuscript

W1 (Presentation).

  1. Original bilevel problem (Section 3.2). Section 3.2 now begins by stating the exact constrained bilevel problem as Eq. (2) and then motivates the approximate formulation, now Eq. (5): min⁡vG(v,θ⋆(v))s.t.θ⋆(v)∈S(v):=arg⁡max⁡θ{Jr(θ,x):Jc(θ,y)≥0}.\min_{v} G\big(v,\theta^\star(v)\big)\quad\text{s.t.}\quad\theta^\star(v)\in\mathcal S(v):=\arg\max_{\theta}\{J_r(\theta,x):J_c(\theta,y)\ge 0\}.

  2. Terminology. We now use one name for each object throughout the paper, replacing the alternative names noted by the reviewer:

    • PvP_v is the lower-level training distribution, or training distribution after first use;
    • ZZ is the training trace;
    • θ(Z)\theta(Z) is the returned policy parameter, which we call the approximate response;
    • S(Z;v)S(Z;v) is the training-distribution score.
  3. Abstract. We rewrote the abstract to state the step the reviewer noted was missing: since approximately optimal policies still form a set, we define the upper objective as the expected upper-level loss of the policy returned by a fixed stochastic lower-level algorithm. We replaced "stability" with the precise condition that fails (Lipschitz continuity of the solution map), removed the solver details, described the encoding in plain words, and replaced "end-to-end environment-interaction complexity" with "total sample complexity".

  4. "Two-point encoding." We agree that the name suggests two-point zeroth-order estimators. It is now called the randomized binary encoding throughout the paper, and it is defined where it is first introduced in the introduction.

  5. Contribution list (Section 1). The headings now use only previously defined terms.

  6. Minor comments. C‾r,C‾c\overline C_r,\overline C_c are renamed Dr,DcD_r,D_c; ϵℓ\epsilon_\ell is introduced as a response accuracy instantiated in Section 5; δℓ\delta_\ell is a prescribed input throughout, with K=⌈δℓ−2⌉K=\lceil\delta_\ell^{-2}\rceil; and the state space is a closed, hence Polish, subset of Rds\mathbb R^{d_s}.

W2. Our contribution is primarily theoretical. The technical contribution is not limited to proving a pre-specified result: it includes formulating the algorithm-induced approximate response, constructing the randomized reward and constraint encoding that makes the induced upper objective differentiable, deriving an unbiased gradient estimator for the complete lower-level training distribution, and establishing the resulting end-to-end convergence and sample-complexity guarantees. The availability of LLM tools does not remove the need to formulate these objects or establish their correctness. We agree that experiments would provide complementary evidence regarding practical performance, but we do not make claims of empirical superiority.

W3. We have added a sufficient construction in the Appendix C.1.6 showing that Assumptions 4–7 can hold jointly in a finite-action setting. We agree that the uniform Slater condition restricts the admissible family of parameterized constraints. It is required in our analysis to maintain a common bounded dual interval as the upper-level parameter changes; Appendix C.1.5 provides a sufficient construction rather than claiming that the condition holds for arbitrary constraint parameterizations. Algorithm 3 also explicitly assumes simulator reset access for the independent continuations used by the critic estimator.

Questions

  1. We added three concrete examples to the introduction and state each in our notation in the new Appendix E.1.3.

  2. Zhou et al. (2022) apply the same likelihood-ratio identity to a Bernoulli coreset mask with an exact inner optimizer. Our Theorem 1 applies it to the output of a finite-sample stochastic constrained-RL algorithm, ∇Φϵℓ(v)=EZ[∇vG(v,θ(Z))+(G(v,θ(Z))−c(v))S(Z;v)]\nabla\Phi_{\epsilon_\ell}(v)=\mathbb E_Z[\nabla_vG(v,\theta(Z))+(G(v,\theta(Z))-c(v))S(Z;v)] for any baseline c(v)c(v). The difference is the object the identity is applied to, not the identity itself. Moreover, Zhou et al. assume smoothness and bounded estimator variance, whereas we derive both and combine them with lower-level reward and feasibility guarantees and sample complexity.

  3. Our formulation optimizes the algorithm-induced upper objective rather than approximating the exact bilevel hypergradient. Consequently, we do not claim hypergradient convergence as δℓ→0\delta_\ell\to0. When the constrained lower-level solution is nonunique, the stochastic lower-level algorithm induces a distribution over returned policies rather than selecting a prescribed optimizer. Our guarantees concern the resulting expected upper objective, together with lower-level reward and feasibility bounds.

  4. See W3 (Appendix C.1.6). The discount-factor dependence is retained explicitly through the problem-dependent constants and Qℓ=K(N+1)/(1−γ)Q_\ell=K(N+1)/(1-\gamma).

Thank you for the detailed response and the revised manuscript. I acknowledge the novelty of this work, in particular the formulation based on the algorithm-induced response and the randomized binary encoding, as I said in the submitted review. However, the revised pdf contains substantial changes, including the new statement of the bilevel problem in Section 3.2, the rewritten abstract, the renamed terminology and several new appendices, which in my view call for a new round of evaluation.

More importantly, I still think that a paper on (bilevel) constrained bilevel reinforcement learning should not be purely theoretical. Experiments are needed to show that the method works in practice (test on some Gym environments, at least). Therefore, I will keep my score.

We thank the reviewer for acknowledging the novelty of the algorithm-induced response formulation and the randomized binary encoding.

On the scope of the revision. The revision improves the presentation and adds supporting material. It does not change the formulation, the algorithm, or the theoretical results:

  • Section 3.2. We now state the exact constrained bilevel problem before the approximate formulation, to make the motivation explicit. The approximate problem we analyze, min⁡vΦϵℓ(v)=EZ∼Pv[G(v,θ(Z))]\min_v \Phi_{\epsilon_\ell}(v) = \mathbb E_{Z\sim P_v}[G(v,\theta(Z))], is the same as in the submission.
  • Abstract and terminology. The abstract describes the same contributions in plainer language, and some terms were renamed for clarity, for example "two-point encoding" (now "randomized binary encoding") and "end-to-end environment-interaction complexity" (now "sample complexity"). These are changes of wording only.
  • New appendices. These provide supporting material without modifying any result: application examples (Appendix E.1.3), a concrete finite-action policy class satisfying the policy assumptions (Appendix C.1.6), and experiments (Appendix F).

The algorithm and the guarantees, including the O~(δℓ−6ϵo−2)\widetilde{\mathcal O}(\delta_\ell^{-6}\epsilon_o^{-2}) sample complexity, are unchanged.

Experiments. We added experiments in Appendix F on three velocity-constrained MuJoCo locomotion tasks from Safety-Gymnasium (a Gymnasium-based benchmark): HalfCheetah, Walker2d, and Ant. The agent never observes the environment reward or cost. Both the reward and the safety signal are learned from pairwise preference feedback, and the lower-level constrained MDP is solved using only these learned signals. Across 10 seeds per task, our method satisfies the cost budget at the end of training in all 30 runs. For comparison, the same algorithm given the true environment cost satisfies it in 27 of 30 runs. On every task, the reward increases during training while the cost settles below the budget. This shows that the method works in practice, including when both the objective and the constraint must be learned.

We hope this clarifies that the revision preserves the contributions the reviewer evaluated and adds experiments demonstrating practical performance, and we would be grateful if the reviewer would reconsider the score.

Reviewer_w8WROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Problem context: In bilevel RL where the lower problem is a constrained MDP, the exact constrained solution mapping may be undetermined and unstable or nonsmooth

Proposed: a reformulation of the bilevel problem using a an approximate lower-level response defined by the sub optimality and constraint violation, namely:

  • Response is given by a finite-sample stochastic primal-dual PG method
  • The approximation comes from using the gradient of vanilla stochastic gradient descent
  • To handle the approximation at the upper level, the authors use a two-point ending of the rewards and constraints
Critical strengths

Strengths:

  • The authors propose a method to sidestep the nonuniqueness and nonsmoothness by optimizing the expected upper loss of whatever a specific alg returns
  • The authors cleanly characterize lower-level reward and feasibility and upper “stationarity” (thms 1-3)
  • The authors also derive an end-to-end complexity as a function of a tunable lower accuracy and tunable upper stationarity error
  • The ultimately complexity is characterized when both knobs are set to epsilon: epsilon^-8
  • They offer a nice example with the Bradley-Terry preference
Critical weaknesses

Weaknesses:

  • The paper lacks any experimentation (not even a toy CMDP), leaving the potential downsides of the proposed method (mentioned below) untested/characterized, especially compared with existing methods
  • The score sums over every signal in the run, so variance and smoothness both grow with run length
  • The paper assumes a twice-smooth reward and constraint in v, which are often unmet in many practical RL usages (sparse rewards/penalties)
  • The reported rate is significantly slower than rates for unconstrained bilevel RL, and this is also wort a surrogate target

The paper proposes a novel algorithm to handling bilevel CMDP problems and the analysis is clean, however, the assumptions are strong and uniform, the authors offer no empirical evidence as to performance, and the use of stochastic programs is classical, meaning said novelty is narrow.

Questions for authors

No additional questions

2 comments

Thank you so for taking the time to review the paper and providing feedbacks to improve the work.

  1. Our work is primarily theoretical, focusing on an approximate-response formulation, an unbiased upper-level gradient estimator, and end-to-end sample-complexity guarantees for constrained bilevel RL. These contributions are established analytically and do not depend on empirical validation. Furthermore, existing bilevel RL methods largely address unconstrained lower-level problems, limiting direct comparisons with our setting.

  2. The dependence on lower-level training length is explicitly quantified in our analysis. Lemmas 17–18 establish that the upper-objective smoothness constant and stochastic hypergradient variance are bounded by O(1+K(N+1)/(1−γ))O(1+K(N+1)/(1-\gamma)), where the variance bound follows from the second-moment bound. An alternative is differentiating through the lower-level algorithm iterates, which involves products of update Jacobians and can exhibit exponential growth with training length. Avoiding this exponential growth generally requires additional restrictive assumption which are not satisfied for RL. In contrast, our approach avoids Jacobian propagation and establishes polynomial dependence on the lower-level training length, as reflected in our end-to-end sample-complexity guarantee.

  3. Assumption 1 requires smoothness only with respect to the upper-level reward and constraint parameters, not the state or action variables. Consequently, sparse or discontinuous state-action rewards are not excluded. For example, r(s,a;x)=x⊤ϕ(s,a)r(s,a;x)=x^\top\phi(s,a) with bounded, potentially sparse features satisfies the derivative requirements, since ∇xx2r=0\nabla_{xx}^2r=0. The same applies to parameterized constraints. Thus, the assumption restricts nonsmooth parameter dependence rather than sparse rewards or penalties themselves.

  4. The O~(ϵ−8)\widetilde O(\epsilon^{-8}) complexity should be interpreted in light of the more challenging constrained lower-level setting, where the exact lower-level solution map may be nonunique and nonsmooth. Existing unconstrained bilevel RL rates typically rely on structural assumptions such as PL condition that do not directly extend to this setting. Our formulation instead optimizes the expected upper objective induced by a stochastic approximate lower-level response, avoiding solution-map differentiability assumptions while providing explicit reward-suboptimality, feasibility, and upper-level stationarity guarantees. Improving the complexity dependence remains an important direction for future work.

Our novelty lies in combining the approximate lower-level response formulation with randomized reward and constraint encoding. The exact formulation requires differentiability of the constrained solution map, which is not generally guaranteed. Direct differentiation through approximate lower-level iterates can exhibit exponential growth in variance and smoothness constants without restrictive stability assumptions. Our encoding avoids this issue, establishing linear dependence on training length and end-to-end convergence guarantees.

We thank the reviewer again for the time spent on our submission. We would like to follow up on our earlier response and share an update on the experiments.

Update on experiments. In addition to the theoretical contributions discussed in our earlier response, we have now added experiments in Appendix F of the revised manuscript. We evaluate the method on three velocity-constrained MuJoCo locomotion tasks from Safety-Gymnasium: HalfCheetah, Walker2d, and Ant. The agent never observes the environment reward or cost. Both the reward and the safety signal are learned from pairwise preference feedback, and the lower-level constrained MDP is solved using only these learned signals. Across 10 seeds per task, our method satisfies the cost budget at the end of training in all 30 runs. For comparison, the same algorithm given the true environment cost satisfies it in 27 of 30 runs. On every task, the reward increases during training while the cost settles below the budget. These results show that the proposed method works in practice, including when both the objective and the constraint must be learned.

We would be grateful if the reviewer could let us know whether our responses have addressed the concerns raised in the review. We would be happy to clarify any remaining questions during the discussion period.

Reviewer_GVd7OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies constrained bilevel reinforcement learning (RL) when the lower-level problem is a constrained Markov decision process (CMDP), and the authors establish end-to-end environment-interaction complexity. However, the presentation is difficult to follow and theoretical results depend on strong assumptions.

Critical strengths

The paper addresses the relevant problem of constrained bilevel RL when the lower-level problem is a CMDP with a generally parameterized policy.

Critical weaknesses
  1. The presentation is difficult to follow, making it challenging to identify the paper’s novelty and understand the proposed algorithm. In particular:

(i) For the sentence "For each upper-level parameter v, let Z ∼ Pv denote the complete random trace generated by the specified lower-level stochastic procedure, including all training randomness and the final random iterate selection. The trace law Pv depends on v, whereas θ(Z) denotes the deterministic policy parameter returned for a realized trace Z and has no additional explicit dependence on v. Thus the lower-level dependence is represented as v −→ Pv(Z) −→ Z −→ θ(Z), rather than as a deterministic differentiable response map." The relationship between the trace distribution PvP_v, the sampled trace ZZ, and the returned parameter θ(Z)\theta(Z) is unclear. Why is the dependence represented by this sequence of mappings, and what does each arrow mean? From the sentence, it feels like theta(Z) is already decided by P_v(Z).

(ii) Section 4, which presents the proposed approach, is difficult to follow. It begins with: "Two-point encoding defines the lower-level estimators that drive the primal–dual algorithm. The resulting trace defines a training-distribution score and hence an upper gradient obtained from the law of the complete training procedure, rather than from derivatives of its individual updates."" However, “two-point encoding,” “training-distribution score,” “the law of the complete training procedure,” and “individual updates” have not yet been explained before this sentence or immediately afterwards. Moreover, what signals are being encoded, and which updates are being referenced? Introducing these concepts before using them, or providing an intuitive overview, would help readers understand the purpose of this paragraph and the approach that follows. A similar issue also happens to "Direct differentiation through the projected dual update would require differentiating the projection operator." What quantity is being differentiated, and with respect to which variable? The dual update has not yet been introduced at this point, and it is unclear which projection operator the sentence refers to. Likewise, the statement: "Let Ir(Z) and Ic(Z) denote the sets of reward- and constraint-encoding events in the trace," What are in the encoding event, and what elements belong to Ir(Z)I_r(Z) and Ic(Z)I_c(Z)?

  1. Theoretical results depend on strong assumptions that require further explanation and justification.

(i) Assumption 2 requires every parameterized CMDPs are feasible with a positive uniform margin, which is independent of the parameterization. This is stronger than the usual Slater's condition, which allows the feasibility margin to depend on the particular CMDP.

(ii) Assumption 5 requires every policy in the policy class to have full action support π(a∣s)>0\pi(a|s) >0, which is not naturally guaranteed by algorithm design.

(iii) Theorem 3 requires Eq. (21) to hold uniformly over vv. What does this uniformity requirement mean, and why is it necessary?

Questions for authors
  1. Convergence guarantees for CMDP are well studied. What are the additional challenges in constrained bilevel RL when the lower-level problem is a CMDP?

  2. Existing work on CMDPs (like [1]) also uses the PL condition to establish convergence guarantees. As mentioned in the introduction, "Existing nonconvex bilevel analyses obtain hypergradient formulas under Polyak–Łojasiewicz conditions." Could the results in [1] be combined with these bilevel analyses and directly applied to constrained bilevel RL?

  3. Experiments are missing.

[1]. Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning.

6 comments

We thank the reviewer for their time and valuable feedback. All changes are marked in blue in the revised manuscript

Presentation Concerns

  1. Section 3.2: We replaced the arrow notation with Z∼PvZ\sim P_v and defined PvP_v as the lower-level training distribution, i.e., the probability distribution of the complete trace of one lower-level run. We clarified that θ(Z)\theta(Z) is the policy parameter returned by that run, determined by the realized training trace, and that the dependence on vv enters only through PvP_v. We refer to θ(Z)\theta(Z) as the approximate response and use this term consistently in the rest of the paper.

  2. Section 4, opening paragraph: We rewrote the opening paragraph so that it only outlines what the section introduces, namely the two-point encoding of the sampled reward and constraint signals and the lower-level algorithm that uses them, without relying on terms that are defined later. We also stated that the upper gradient is obtained from the training distribution rather than through differentiation of the lower-level algorithm iterates.

  3. Section 4.1: We revised the sentence on direct differentiation to state explicitly that the quantity being differentiated is the upper objective, and that direct differentiation would pass through the iterates of the lower-level algorithm introduced in Section 4.2. The projection in the original sentence referred to the projection of the dual variable onto [0,λmax⁡][0,\lambda_{\max}] in that algorithm; since the algorithm is introduced only in Section 4.2, we removed this forward reference from Section 4.1. We also expressed the alternative in terms of the training distribution PvP_v, consistent with the terminology defined in Section 3.2.

  4. Section 4.3: We clarified that Ir(Z)\mathcal I_r(Z) and Ic(Z)\mathcal I_c(Z) index every instance in which a sampled reward r(s,a;x)r(s,a;x) or constraint c(s,a;y)c(s,a;y) is replaced by its randomized encoding 2RBr2RB^r or 2CBc2CB^c, respectively, across all trajectory samples used by the lower-level algorithm.

Assumption related concerns

  1. Assumption 2: The uniform Slater condition is supported by a sufficient construction provided in Appendix C.1.5, rather than being imposed without justification. Uniformity is required in our analysis because the upper-level parameters change during optimization.

  2. Assumption 5: For finite action spaces, a softmax policy parameterization guarantees πθ(a∣s)>0\pi_\theta(a\mid s)>0 for every action and every finite parameter vector θ\theta. We added this clarification immediately after Assumption 5 to explain how the full-support condition can be ensured.

  3. Uniformity of Eq. (21): This means that the same second-moment bound VΦV_\Phi holds for every vv. Lemma 18 establishes this from the uniform reward/constraint regularity in Assumption 1 and the uniform upper-objective and oracle bounds in Assumption 3. This uniformity is required because the upper-level parameter changes across iterations.

Question for Author

  1. Existing CMDP convergence guarantees do not establish differentiability of the lower-level solution map, which may be non-unique and nonsmooth. Further, direct differentiation through the lower-level algorithm iterates can also involve products of update Jacobians whose norms may grow rapidly with the training length. Our approximate-response formulation and randomized reward and constraint encoding address these challenges.

  2. The cited work assumes weak ψ\psi-gradient domination only with respect to the primal policy variable for each fixed dual variable,

\ge \alpha_1\!\left(\mathcal L_0(\theta,\lambda)-\min_{\theta'}\mathcal L_0(\theta',\lambda)\right)-\beta_1.$$ Thus, it controls primal Lagrangian suboptimality for fixed $\lambda$, rather than regularity of the complete constrained solution map. In particular, for the primal-dual solution correspondence $\mathcal S(v)$, it does not imply uniqueness, a differentiable selector, or stability such as $$d_H(\mathcal S(v),\mathcal S(v'))\le L\|v-v'\|$$ as the upper-level parameter changes, which is required for hypergradient expression. 3. Our work is primarily theoretical, focusing on an approximate-response formulation, an unbiased upper-level gradient estimator, and end-to-end sample-complexity guarantees. These contributions are established analytically and do not depend on empirical validation.

(i) The algorithm design section of the revised manuscript is still hard to follow, and the authors keep referring to results in the appendix without providing intuition or introducing what is discussed in the referenced appendix. For example:

  1. The authors use "encode" a lot, but it is hard to understand what it means in phrases like "For the j-th encoded signal", "independent encoded estimate", "encoded oracle", and "encoded reward and constraint signals". The authors also keep using "upper-gradient oracle calls" and "fresh upper-gradient oracle calls". Where are these terms defined, and what does fresh mean?

  2. The sentence "The critic estimator uses reset access: the simulator can start a trajectory from ρ\rho, reset to a state visited by that trajectory, and from there generate the independent continuations required by Appendix Algorithm 3." should be highlighted or marked as an assumption about access to the CMDP model.

  3. "Appendix Algorithms 2–3 give the complete lower-level algorithm, encoded oracle, score accumulation, and sampling details". What does score accumulation mean?

  4. "The additional uniform boundedness conditions control the direct-gradient and score-function terms in the upper estimator constructed in Section 4.4; a concrete oracle construction and detailed verification are given in Appendix E.1.2." What do "score function" and "upper estimator " mean? The authors cannot keep referring to the appendix without giving insights into how it works. In this case, how is it constructed, and what is being verified?

  5. "S(Z; v) is the sum of the score functions of all reward and constraint encoding variables generated during the lower-level run." Do the score functions have the same definition throughout the section?

  6. "each upper-level iteration uses O(δℓ−2)O(\delta_\ell^{−2}) upper θ\theta-gradient calls in expectation, in addition to one v-gradient call. For the trajectory based Bradley–Terry upper objective of Appendix E.1.2, every oracle call uses two trajectories of length at most H;" What does "θ\theta-gradient calls " mean? The term "Bradley–Terry upper objective" comes out of nowhere. What is its connection to this paragraph?

(ii) Theoretical results still require experiments to demonstrate their practical relevance and validate the theory guarantees.

(iii) The choice of softmax policy parameterization satisfies Assumption 5 but not Assumption 6, as the Fisher information matrix is positive semidefinite but not positive definite. The authors should specify or give examples of policy parameterizations that satisfy all the assumptions (like 5,6,7, the conditions of Theorem 2 and Lemma 1). Also, the definition of the Fisher information matrix used in Assumption 6 should be introduced.

We thank the reviewer for the follow-up comments. All changes are highlighted in blue in the revised manuscript.

(i) Presentation of the algorithm design section

  1. "Encode" and "oracle" terminology. Section 4.1 now defines the encoded signal a~=2AB\tilde a = 2AB, the encoded reward 2RBr2RB^r, and the encoded constraint 2CBc2CB^c; the sentence on "the jj-th encoded signal" has been removed. The terms "encoded oracle", "upper-gradient oracle calls", and "fresh" no longer appear in Section 4. We also clarified the term "upper gradient": we use partial gradients for the gradients ∇vG\nabla_v G and ∇θG\nabla_\theta G of the upper-level objective GG, whose stochastic estimates ∇^vG\widehat\nabla_v G and ∇^θG\widehat\nabla_\theta G satisfy Assumption 3, and hypergradient for the gradient of the hyper-objective Φϵℓ\Phi_{\epsilon_\ell}, as defined in Section 3.2. Section 4.4 states that the stochastic estimates are drawn independently of each other and of the lower-level run, which is what "fresh" meant.
  2. Reset access is now stated as Assumption A in Section 4.2. It is used only in Appendix Algorithm 3, to estimate the Lagrangian advantage.
  3. Score accumulation. This term referred to summing the scores sa(B;v)s_a(B;v) of all encoded rewards and constraints generated during a lower-level run, which gives the training-distribution score S(Z;v)S(Z;v) in Section 4.3. Section 4.2 now states this directly, and terms such as "score accumulation" and "encoded oracle" have been removed.
  4. Score function and upper estimator. We no longer use the term "upper estimator". It referred to the hypergradient estimator g^(v)=∇^vG+δ^G S(Z;v)\widehat g(v) = \widehat\nabla_v G + \widehat\delta_G\, S(Z;v) in Section 4.4, whose "score-function term" δ^G S(Z;v)\widehat\delta_G\, S(Z;v) uses the training-distribution score to capture how vv affects lower-level training. Section 4.4 now places both terms in the context of Assumption 3, stating that its bounds keep ∇^vG\widehat\nabla_v G and δ^G\widehat\delta_G bounded in second moment. The concrete construction referred to in Appendix E.1.2 is a Bradley–Terry preference objective computed from pairs of sampled trajectories, for which Assumption 3 is verified; this is now stated in Section 4.3.
  5. Score functions. Section 4 now defines the two score functions explicitly and refers to each by its name rather than as "the score": the score of an encoded signal, sa(B;v)s_a(B;v) (Section 4.1), and the training-distribution score S(Z;v)S(Z;v), the sum of these scores over a lower-level run (Section 4.3). For example, Theorem 1 now refers to S(Z;v)S(Z;v) as the training-distribution score instead of re-describing it.
  6. θ\theta-gradient calls and Bradley–Terry objective. "θ\theta-gradient calls" are now "samples of ∇^θG\widehat\nabla_\theta G". The Bradley–Terry objective is introduced in Section 4.3, before its cost is discussed in Section 4.4.

(ii) Experiments

We added experiments in Appendix F on three velocity-constrained locomotion tasks from Safety-Gymnasium: HalfCheetah, Walker2d, and Ant. In this setting the agent never observes the environment reward or cost. Both the reward rxr_x and the safety signal cyc_y are learned from pairwise preference feedback, and the lower-level constrained MDP is solved using only these learned signals.

Across 10 seeds per task, our method satisfies the cost budget at the end of training in all 30 runs. For comparison, the same algorithm given the true environment cost satisfies it in 27 of 30 runs. On every task, the reward increases during training while the evaluated cost settles below the budget. These results show that the proposed approach can learn both the objective and the constraint from preference feedback and reliably produces policies that satisfy the constraint.

(iii) Assumptions

We agree that the softmax parameterization satisfies Assumption 5 but not Assumption 6. We removed the softmax remark after Assumption 5 and now refer to Appendix C.1.6, which gives a finite-action policy class satisfying Assumptions 4–7 simultaneously, with explicit constants GπG_\pi, LπL_\pi, μF\mu_F, and ϵbias\epsilon_{\rm bias}. A new paragraph at the end of Appendix C.1.6 shows how these constants provide the bound RωR_\omega and the critic step-size condition required by Theorem 2, and the constants of Assumption 3 required by Lemma 1.

The Fisher matrix Fρ(θ)=E(s,a)∼νρπθ[ψθ(s,a)ψθ(s,a)⊤]F_\rho(\theta) = \mathbb E_{(s,a)\sim\nu_\rho^{\pi_\theta}}[\psi_\theta(s,a)\psi_\theta(s,a)^\top] is defined in Section 4.2, where it is used to define the natural-gradient direction. To make Assumption 6 self-contained, we now also state this definition within the assumption.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.