- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper asks how much regret must be paid for episode-wise safety in tabular CMDPs when the learner starts from a known safe baseline with slack . The authors propose TRAPEZE, whose main idea is to decouple the two jobs that prior algorithms entangle: a frozen empirical model is used to construct a candidate policy, while deployment is certified separately from fresh trajectory costs, so the policy being deployed is never correlated with the estimate vouching for it. This separation, together with a sharper concentration argument that avoids per-state transition confidence sets, yields regret , improving the best prior rate by a factor and recovering the unconstrained minimax rate when the slack is large. The paper then proves a matching lower bound of the same form, showing that the inverse slack multiplies the full tabular exploration difficulty rather than adding a separate overhead.
Critical strengths
- The matching lower bound, and the mechanism it isolates, closes an explicitly open question.
Critical weaknesses
- The improvement rests entirely on the profile machinery.
- Extreme expositional density combined with no validation.
Questions for authors
- For a single block , please state explicitly which -field is “before block is revealed” in the reverse-stage filtration.
2.Theorem 12 is labelled “baseline-free,” but eq. (13) still uses the exact — so the label appears to apply only to the candidate-learner tuning, not to deployment.
3 comments
Follow-up on our response
We thank the reviewer again for the constructive feedback and positive assessment of our work. As the discussion deadline approaches, we would welcome the reviewer's thoughts on our response, particularly our explanation of the contributions beyond prior profile bounds and our answers to the two technical questions. Please let us know if any questions or concerns remain unresolved. We would be happy to provide further clarification.
Thank you for your clarification. I maintain my rating.
We thank the reviewer for the constructive feedback and for recognizing the significance of our work. We respond to the weakness and questions below.
In our proof, the profile argument is essential to removing the extra S factor, but the profile bounds in prior work do not by themselves yield this improvement under episode-wise safety. Our proof of the near-optimal regret bound requires two novel ingredients beyond the existing profile bounds.
First, our analysis counts each proposal’s budget violation separately. Liu et al.’s Eq. (14) bounds a sum of signed cost estimation errors, so errors from different episodes can cancel. TRAPEZE instead bounds ∑n[V1,cρn−b]+ (Theorem 7): a proposal above budget contributes its full excess, and a proposal below budget contributes zero. A later proposal below budget cannot recover reward already lost from mixing an earlier proposal with the baseline. Our weighted profile analysis and optimism correction together give this bound without an extra inverse-slack factor.
Second, we use fresh trajectory costs to determine how often the current proposal can safely replace the baseline. Theorem 7 gives a cumulative bound, not a cost certificate for the next episode. TRAPEZE holds the proposal fixed and uses the total costs of its subsequent executions to set its mixture weight with the baseline (Eq. (13)). Because the certificate restarts only when the model changes, its cumulative error has the same leading order as the planning error (Eq. (20)). This lets us enforce safety in every episode without reintroducing the extra S.
We thank the reviewer for raising this point. In the final version, Section 4 will follow one episode from start to finish: how TRAPEZE chooses between the proposal and the baseline and, when the proposal is selected, how its transitions enter the model buffers while its total cost updates the safety certificate. The main proof sketch will introduce profiles through a two-stage example showing which data determine the continuation value before we apply concentration.
For q=(s,a,h,ℓ), order all potential blocks by decreasing stage, with a fixed order within each stage. Let Zq,i be the ith observation in block q and nq its size. Writing q′≺q if q′ comes first, the sigma-field is
Rq,0=σ(Zq′,i:q′≺q,1≤i≤nq′).
It contains all later-stage blocks and the preceding blocks at stage h, but no observation from q. This is the proof’s reveal order, not the learner’s collection order. For a fixed profile and multiplier, the later-stage data already determine the continuation value at every possible next state (Lemma 17), while the next state sampled in block q is still unknown.
“Baseline-free” applies only to the candidate learner. A feasible policy must exist at budget b, but the learner need not know it or its cost. Theorem 12 bounds cumulative positive violations rather than guaranteeing that every candidate is safe.
Eq. (13) serves a different purpose: safe deployment. Given an upper bound U on the candidate’s expected cost and the baseline’s known expected cost c0, it chooses the largest candidate weight α∈[0,1] satisfying αU+(1−α)c0≤b. The baseline’s known cost determines how much of the candidate can safely be included. We will retitle Theorem 12 “Candidate guarantees without a known baseline” to make this distinction explicit.