acceptodds
Under review as a conference paper at ICLR 2027

TRAPEZE: Minimax-Optimal Episode-Wise Safe Exploration in Tabular CMDPs

Abstract

We study online learning in finite-horizon tabular constrained Markov decision processes, where every adaptively deployed randomized policy must have conditional expected episode cost at most a prescribed budget. The learner is given a baseline policy with known cost value and safety slack . We introduce TRAPEZE, which separates model-based candidate learning from deployment certification. At each model update, scalar optimistic planning over a finite grid of dual multipliers and a deficit-routing rule produce a candidate distribution over policies. While this candidate remains frozen, TRAPEZE directly certifies its cost from subsequent whole-trajectory returns and deploys the largest certified episode-level mixture of the candidate and the baseline. A profile-based Bernstein analysis controls the adaptively selected continuation values without coordinatewise transition confidence. For episodes, with probability at least , every deployed policy is feasible and the regret is . We also prove a matching lower bound \Omega \left( \min\left\\{ HK, \left(1+\frac{H}{\kappa}\right)\sqrt{SAH^3K} \right\\} \right) under the same baseline information and episode-wise safety requirement. These results establish minimax optimality up to logarithmic and lower-order terms and show that the inverse safety slack multiplies the full tabular exploration difficulty. Safety concerns conditional expected episode cost, not the cost of every realized trajectory.

Primary area:
learning theory
Keywords:
Constrained MDPs, safe exploration, minimax optimal regret, lower bound

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PM6GOpenReview ↗
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 κ\kappa. 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 O~((1+H/κ)SAH3K)\widetilde O\big((1+H/\kappa)\sqrt{SAH^3K}\big), improving the best prior rate by a S\sqrt S 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
  1. The matching lower bound, and the mechanism it isolates, closes an explicitly open question.
Critical weaknesses
  1. The S\sqrt S improvement rests entirely on the profile machinery.
  2. Extreme expositional density combined with no validation.
Questions for authors
  1. For a single block q=(s,a,h,ℓ)q=(s,a,h,\ell), please state explicitly which σ\sigma-field is “before block qq is revealed” in the reverse-stage filtration.

2.Theorem 12 is labelled “baseline-free,” but eq. (13) still uses the exact V1,cπ0V^{\pi_0}_{1,c} — so the label appears to apply only to the candidate-learner tuning, not to deployment.

3 comments

We thank the reviewer for the constructive feedback and for recognizing the significance of our work. We respond to the weakness and questions below.


Weakness 1. The role of profiles in the S\sqrt S improvement.

In our proof, the profile argument is essential to removing the extra S\sqrt 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]+\sum_n [V_{1,c}^{\rho_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\sqrt S.


Weakness 2. Expositional density and validation.

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.


Q1. Which sigma-field represents “before block qq is revealed”?

For q=(s,a,h,ℓ)q=(s,a,h,\ell), order all potential blocks by decreasing stage, with a fixed order within each stage. Let Zq,iZ_{q,i} be the iith observation in block qq and nqn_q its size. Writing q′≺qq'\prec q if q′q' comes first, the sigma-field is

Rq,0=σ(Zq′,i:q′≺q,1≤i≤nq′).\mathcal R_{q,0}=\sigma\bigl(Z_{q',i}: q'\prec q,\\ 1\le i\le n_{q'}\bigr).

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.


Q2. What does “baseline-free” mean in Theorem 12?

“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 UU on the candidate’s expected cost and the baseline’s known expected cost c0c_0, it chooses the largest candidate weight α∈[0,1]\alpha\in[0,1] satisfying αU+(1−α)c0≤b\alpha U+(1-\alpha)c_0\le 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.

AuthorsOpenReview ↗

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.

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

The paper studies tabular CMDPs with S states, A actions, horizon H, and unknown transitions, rewards, and costs. The learner knows a baseline policy and its exact expected cost, with positive safety margin κ. It seeks low regret while every deployed policy satisfies the conditional expected episode-cost constraint with high probability. This guarantee does not ensure safety of every realized trajectory.

TRAPEZE combines frozen disjoint data blocks, scalar optimistic planning, coordinate-deficit routing, weighted profile concentration, and direct trajectory-cost certification. A baseline mixture enforces deployment safety while candidate-policy executions supply learning data.

Critical strengths

Theorem 2 establishes simultaneous episode-wise safety and regret of the following order, for K episodes and confidence 1 - δ:

O~((1+H/κ)[SAH3K+SAH2]).\widetilde O\left((1+H/\kappa)\left[\sqrt{SAH^3K}+SAH^2\right]\right).

Theorem 9 provides a roughly matching lower bound.

Critical weaknesses

This paper suffers from poor readability in its presentation of the algorithm design. Section 4.1 introduces many concepts. They are even unfamiliar to RL researchers. Moreover, the description relies only on natural language rather than using notation to refer to the actual collected data. This subsection also assumes that readers are already familiar with many important components of the algorithm, such as blocks. Next, the algorithm description does not rely on observations indexed by k but instead uses separately defined notations whose rigorous relationship to the observations is not provided.

Questions for authors

Mathematical correctness

  • Theorem 12 should explicitly assume feasibility at the original budget when dropping baseline knowledge (p. 12, lines 610-615). Feasibility is already implicit in Section 3's optimal-policy definition, so this clarification preserves the intended theorem and rate.

Novelty and related work

  • The inverse-slack necessity discussion omits Stradi et al., ICML 2025 [1], distinct from their cited ICLR paper (p. 26, lines 1382-1384 and 1399-1403). Its fixed two-action construction already establishes relevant inverse-slack difficulty; the exact-safety specialization was independently checked. Narrow the priority claim to growing-action and, especially, joint tabular dependence. The prior result does not subsume Theorem 9's joint S, A, H, κ bound.
  • “Adds fixed-multiplier planning” overstates novelty relative to Chang Liu et al., NeurIPS 2025 [2] (p. 3, lines 121-124). Their Eqs. (7)-(9) and Algorithm 1 already use fixed-dual planning and a dual grid. Emphasize the normalized scalar planner, routing, and deployment certification; their returned-policy feasibility differs from safety of every learning episode.

Exposition and citation accuracy

  • The introduction incorrectly associates Müller et al. (2024) [3] with cancellation-permitting violation metrics (p. 1, lines 42-45). Their strong cumulative metric does not permit cancellation, although it can allow individual unsafe episodes. Correct the comparison without changing TRAPEZE's stronger deployment-safety claim.

[1] Stradi et al. Learning Adversarial MDPs with Stochastic Hard Constraints. ICML 2025, Theorem 6.6 and Appendix F. Official proceedings.

[2] Liu, Li, and Yang. Near-Optimal Sample Complexity for Online Constrained MDPs. NeurIPS 2025, printed pp. 5-6. Published paper.

[3] Müller et al. Truly No-Regret Learning in Constrained MDPs. ICML 2024. Official proceedings.

3 comments

We thank the reviewer for the constructive feedback on the presentation of the paper and for recognizing our contributions of the matching bounds. We respond to the weakness and questions below.


Weakness: Readability and connecting Algorithm 1 to the observations in episode k

We agree that Section 4.1 would be clearer if it started from the observed trajectory. In episode k, TRAPEZE either executes the safe baseline or draws one policy from its current proposal and follows it for the entire episode. Let Zk=1 if it selects the proposal and 0 otherwise. Then n(k)=∑j=1kZjn(k)=\sum_{j=1}^k Z_j counts proposal executions. Each such execution supplies data for two estimates:

  1. Updating the model from individual steps. If the learner takes action a in state s at stage h, it records the next state, reward, and cost (Sk,h+1,Rk,h,Ck,h) for the cell (s,a,h). For each cell, we group these records in order of arrival into disjoint blocks of sizes 1, 2, 4, and so on. Suppose the first three proposal executions that visit this cell occur in episodes 2, 5, and 9. The record from episode 2 forms the first block. Episode 5 starts the second block but does not update the cell. Episode 9 completes it. The learner now uses just the records from episodes 5 and 9 to estimate the next-state probabilities and the mean reward and cost at this cell. At the end of any episode that completes a block, TRAPEZE updates all affected cells and computes a new proposal offline. The dual iterations t collect no data, and unfinished blocks retain their records.

  2. Estimating the proposal's cost from whole trajectories. The proposal stays fixed between model updates, an interval we call segment e. If its ith execution in that segment occurs in episode ke(i), the observed total cost is Ye,i=∑h=1HCke(i),hY_{e,i}=\sum_{h=1}^H C_{k_e(i),h}. The upper bound on expected cost starts at H. After each proposal execution, it is the mean of the segment's observed totals plus a confidence radius, capped at H. This bound sets the probability of using the proposal rather than the baseline. It does not change the proposal itself. A new segment starts with a fresh bound.

Baseline episodes update neither estimate. We will improve clarity in Section 4.1 and identify both uses of the episode observations in Algorithm 1.


Q1. Add explicit feasibility assumption.

We thank the reviewer for the suggestion. A feasible policy exists at budget b, but the learner need not know it or its cost. We will make this assumption explicit. Meanwhile, the theorems and rate remain unchanged.


Q2. Lower-bound contribution relative to Stradi et al. (ICML 2025).

We thank the reviewer for suggesting a more precise statement of our contribution. Stradi et al. (ICML 2025)'s theorem 6.6 establishes an Ω(K/ρ)\Omega(\sqrt K/\rho) regret lower bound with two actions, where ρ\rho equals the baseline slack on their hard instances.

Our contribution is a matching regret lower bound that captures the joint dependence on S, A, H, and κ\kappa. Theorem 9 shows that as the numbers of states, actions, and stages grow, the safety factor H/κH/\kappa multiplies the full tabular exploration rate SAH3K\sqrt{SAH^3K}. The resulting bound, Ω(min⁡HK,(1+H/κ)SAH3K)\Omega(\min\\{HK,(1+H/\kappa)\sqrt{SAH^3K}\\}), matches TRAPEZE’s leading upper bound up to logarithmic factors under the same episode-wise safety and known-baseline assumptions. We will emphasize this joint dependence in the revised discussion.


Q3. Contribution relative to Liu et al. (NeurIPS 2025).

We thank the reviewer for the suggestion. We will revise and clarify our contributions relative to Liu et al. in Section 2:

Algorithmic design: TRAPEZE uses a normalized reward–utility score and assigns its optimism correction to the term with the larger weight. We use fresh rollouts of the fixed proposal to certify every deployed mixture, while Liu et al. certify the final policy returned after learning.

Analysis technique: Liu et al.'s Eq. (14) bounds a sum of signed cost estimation errors, so errors can cancel. When several policies reuse one transition block, our weighted profile argument (Lemma 5) weights each continuation value by how often it was used. The dual analysis then bounds positive proposal violations without an extra H/κH/\kappa factor before baseline mixing.

Together, these advances in algorithm design and analysis yield near-optimal regret while guaranteeing safety in every episode.


Q4. Citation correction.

We thank the reviewer for catching this citation error. We will correct the introduction to cite Müller et al. (ICML 2024) for strong cumulative violation, with no cancellation. As the reviewer notes, their bound still permits individual episodes to exceed the budget in expectation. TRAPEZE guarantees, with high probability, that every deployed policy satisfies the expected-cost constraint while attaining minimax-optimal regret up to logarithmic and lower-order terms.

Reviewer_nqHPOpenReview ↗

Response to authors

Thanks to the authors for the detailed response and for improving the paper. I believe that CMDP is an important research question and appreciate the effort to improve readability; the current manuscript seems to be much better. However, the remaining discussion period is relatively limited for me to check the new organization in detail. I will temporarily maintain my current rating and will revisit if necessary during the reviewer-AC discussion period. Readability seems to be a common concern for multiple reviewers. Thus, if I have not provided deterministic feedback then and other reviewers can confirm that the issue is solved, the AC and reviewers can disregard my negative comment on readability.

We sincerely thank the reviewer for following up and for noting the improvement in the revised manuscript. Our main contribution is to close the regret gap for episode-wise safe learning in tabular CMDPs through matching upper and lower bounds. Given this contribution and the improved presentation, we would be grateful if the reviewer could reconsider their overall assessment when revisiting the paper during the discussion with the AC. We understand the time constraints and we remain available to clarify any outstanding concern.

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

The paper studies episodic tabular CMDPs with a known strictly feasible baseline policy. It requires the conditional expected cost of the randomized policy used in each episode to remain below the budget, simultaneously with high probability. The proposed algorithm constructs an exploratory candidate using optimistic planning and primal-dual updates, estimates its cost from fresh trajectories while keeping it fixed, and mixes it with the baseline to ensure feasibility. The paper establishes a regret upper bound and a matching minimax lower bound, up to logarithmic factors.

Critical strengths
  • Matching upper and lower bounds under an episode-wise expected-cost constraint is a meaningful contribution.
  • The improvement over DOPE+ is notable. The lower bound is also informative: it shows that the inverse baseline slack multiplies the tabular exploration difficulty.
  • Separating candidate construction from safety certification is useful. Estimating the cost of a frozen candidate and using that estimate to set its mixture weight with the baseline is a natural, interpretable approach.
Critical weaknesses
  • The presentation obscures a relatively simple algorithm. The paper introduces several named mechanisms (“mosaic,” “deficit routing,” “weighted profiles,” “predictable thinning”) before giving intuition for their roles. Each term is formally defined, but I repeatedly had to translate them back into familiar operations before I could assess the argument. Section 4.1 gives an operational overview, but the motivation for the central design choices remains too compressed. I suggest first describing the candidate learner and the baseline mixture in plain terms, then explaining precisely why each additional ingredient is needed.
  • The distinction from Liu et al. (2025) is insufficiently precise. That work already uses fixed-multiplier planning, discretized dual updates, policy mixtures, doubling batches, and profile-based concentration. The claim in Section 2 that TRAPEZE “adds fixed-multiplier planning” therefore needs more details. The present paper does address a stronger deployment requirement, but that alone does not identify a new methodological contribution. The paper should state which parts of the prior construction are insufficient and which new argument is essential for the claimed rate.
Questions for authors
  • What prevents combining the candidate learner of Liu et al. (2025) with the proposed trajectory-based safety certificate? Which step would fail, and which new ingredient of TRAPEZE fixes it?
  • Section 4.3 claims that Bellman optimization fails when each policy has its own Bernstein objective. Can you give a concrete example of this failure?
  • Can you explain the independence and adaptive-selection argument behind Lemmas 5 and 17 directly in the main text?
2 comments

We thank the reviewer for the constructive review and for recognizing the significance of our contribution. We respond to the weaknesses and questions below.


Weakness 1. Dense terms and notations

The notation distinguishes two decisions that TRAPEZE makes at different times:

  1. Planning: how do we build the proposal? TRAPEZE batches observations by state, action, and stage. When a batch fills, it finishes the episode and updates its model using the latest completed batch at each cell (the “mosaic”). Offline dual iterations tt produce the proposal: a distribution over policies.

  2. Deployment: how often can we use the proposal instead of the baseline? The proposal stays fixed between model updates, an interval we call segment ee. Before each episode kk, an upper bound on its expected cost determines the probability of choosing it over the safe baseline. If it selects the proposal, TRAPEZE draws one policy for the whole episode. The observed total cost updates the bound, not the proposal. Only these executions count toward nn.

“Routing” adjusts planning estimates. Weighted profiles and predictable thinning are proof tools for data reuse and baseline episodes, respectively. We thank the reviewer for the suggestion and will improve clarity in the final version.


Weakness 2. What is new relative to Liu et al. (2025)?

What carries over. Fixed-multiplier planning, the dual grid, policy mixtures, doubling batches, and profile analysis are already in Liu et al. We will correct “adds fixed-multiplier planning” in Section 2.

What does not carry over. Their strict feasibility guarantee is for the returned policy. Their eq. (14) bounds only the sum of signed cost estimation errors, and the next display bounds only positive empirical constraint violation. Neither bounds positive true violation. Consider two proposals. Both estimates equal the budget, 5. True costs are 6 and 4, giving 1−1=01-1=0 in Eq. (14). Yet the first proposal requires baseline mixing, which can cost reward that the second cannot recover.

What gives the rate. Liu et al. use separate reward and cost bonuses. TRAPEZE uses one bonus for (r+λd)/(1+λ)(r+\lambda d)/(1+\lambda), d=1−cd=1-c, then evaluates reward and utility without bonuses. Routing assigns the gap between the optimistic score and the weighted estimates to the term with the larger weight, avoiding amplification by the multiplier (Lemma 4).

Our Eq. (45) bounds errors before cancellation. In the proof, we multiply each sampled policy’s Bellman identity by the sign of its starting value error ene_n before summing. Each error now contributes ∣en∣|e_n|. Lemma 5 groups the transition errors by batch and weights each continuation by how often it was used. With Eq. (27), this gives Theorem 7: total positive true overruns are at most O~(SAH3N+SAH2)\widetilde O(\sqrt{SAH^3N}+SAH^2) after NN proposal executions, with no H/κH/\kappa factor. Baseline mixing already charges up to H/κH/\kappa in regret per unit of overrun. Paying that factor here too would lose the matching rate.


Q1. Could Liu et al.’s learner use our certificate?

Yes for safety. Hold its proposal fixed and apply the certificate to fresh trajectories. However, regret remains a problem. The certificate controls estimation error (Lemma 8). Even with exact costs, an over-budget proposal needs baseline mixing. Their published bound does not establish the matching regret rate after mixing.

Q2. Why can backward maximization fail?

The root leads to states xx or yy with equal probability. At xx the only action gives reward 1. At yy, action AA gives 1 and BB gives 0. Score both policies at the root by mean reward plus twice its standard deviation.

  • Policy 1, π1(A∣y)=1\pi_1(A\mid y)=1: reward is 1 in either state. Score: 1+2×0=11+2\times 0=1.
  • Policy 2, π2(B∣y)=1\pi_2(B\mid y)=1: reward is 1 at xx and 0 at yy. Score: 0.5+2×0.5=1.50.5+2\times 0.5=1.5.

Backward maximization chooses AA at yy, but the root score favors policy 2. Switching to policy 1 gains 0.5 in mean reward and loses 1 in bonus. TRAPEZE puts a floor on its bonus (Eq. 31). Lemma 14 shows that a statewise improvement can reduce the bonus by at most the gain in empirical mean. Thus policy 1 cannot score below policy 2 under our backup.


Q3. Why is adaptive selection valid in Lemmas 17 and 5?

  1. Fix a batch schedule and choose which execution, multiplier, and value estimate to inspect for each batch. Revealing later-stage data fixes the next-stage values without changing the current batch’s sampling law (Lemma 17).
  2. Prove the bound for all such choices and reuse counts. Only then substitute the learner’s actual choices (Lemma 5). We do not condition on the observed schedule.
  3. If one batch served several continuations, average the bound using their observed frequencies. Jensen’s inequality keeps the average variance inside the square root. The frequencies need not be independent of the batch.

We will add this proof sketch to Section 5.

AuthorsOpenReview ↗

Follow-up on our response

We thank the reviewer again for the constructive feedback. As the discussion deadline approaches, we would welcome the reviewer's thoughts on our response, particularly whether our explanations clarify the algorithm and its contributions beyond Liu et al. If our response has adequately addressed the questions and concerns, we would be grateful if the reviewer could reconsider their overall assessment and rating. Please let us know if any point remains unresolved. We would be happy to provide further clarification.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.