- 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, , where 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 . 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 , where is the lower-level accuracy and the upper-level tolerance. There are no experiments.
Critical strengths
- 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 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.
- The encoding is novel. The two-point encoding replaces each reward and constraint sample with an unbiased Bernoulli variable whose probability depends on . After the encoding, enters only through these probabilities. As a result, is differentiable in , and its gradient follows from a likelihood-ratio identity without Jacobians or inverse Hessians.
- 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 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 and the score 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 -best response, i.e., any -optimal and -feasible policy.
- The "therefore" skips the step that does the work. Approximation alone does not help: the set of -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 (direct/softmax) are tabular, which Assumption 4 excludes; tabular softmax also has a singular Fisher matrix.
- The uniform Slater condition over all 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.
- uses two nearly identical symbols.
- is introduced as an "abstract response tolerance" and later redefined as .
- is defined as in Sec. 5.2 but is a prescribed input in Thm. 3.
- In Lemma 2, the step "weakly compact tight" needs a Polish state space; take closed or .
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
- 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.
- Zhou et al. (ICML 2022) relax a bilevel problem to with . They update with (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?
- When is unique and smooth, does the gradient given in Thm. 1 (Eq. 11) converge to as , and at what rate? When the solution is nonunique, which selection does implement?
- Is there a finite-action policy class that satisfies Assumptions 5–7? What is the explicit 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
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, , 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 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.
We thank the reviewer for the detailed comments. All changes are marked in blue in the revised manuscript
W1 (Presentation).
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): minvG(v,θ⋆(v))s.t.θ⋆(v)∈S(v):=argmaxθ{Jr(θ,x):Jc(θ,y)≥0}.
Terminology. We now use one name for each object throughout the paper, replacing the alternative names noted by the reviewer:
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".
"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.
Contribution list (Section 1). The headings now use only previously defined terms.
Minor comments. Cr,Cc are renamed Dr,Dc; ϵℓ is introduced as a response accuracy instantiated in Section 5; δℓ is a prescribed input throughout, with K=⌈δℓ−2⌉; and the state space is a closed, hence Polish, subset of Rds.
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
We added three concrete examples to the introduction and state each in our notation in the new Appendix E.1.3.
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)] for any baseline 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.
Our formulation optimizes the algorithm-induced upper objective rather than approximating the exact bilevel hypergradient. Consequently, we do not claim hypergradient convergence as δℓ→0. 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.
See W3 (Appendix C.1.6). The discount-factor dependence is retained explicitly through the problem-dependent constants and Qℓ=K(N+1)/(1−γ).