acceptodds
Under review as a conference paper at ICLR 2027

Learning State-Dependent Reach-Avoid Bounds with PAC Guarantees

Abstract

Learned control policies can succeed on average yet fail from particular initial states. Existing reach-avoid certificates either require a model of the dynamics with Lipschitz bounds and a grid over the state space, or certify a single success probability. We introduce Reach-Avoid Probability Certification (RAPC), which learns a function that lower-bounds the probability that a policy started at reaches a target before an unsafe set, and certifies it from simulator rollouts alone. With probability at least over learning and certification, a returned overstates the true success probability only on initial states of total probability at most , even when the policy and bound are updated adaptively. The key step links an unobservable event, an overstated bound at a start, to an observable one: a failed binomial confidence check on repeated rollouts from that start. Calibrating to these confidence limits gives a learner-independent lower bound on its acceptance probability and, for a fixed calibration pipeline, certifies without a separate validation batch. On a 12-dimensional Hopper environment and a PointGoal environment with 44-dimensional observations, RAPC certifies bounds in all ten seeds of each task. On a wider Hopper start distribution, the learned bound averages over ten seeds, against for the largest constant accepted by the same test. We release our code at https://anonymous.4open.science/r/iclr-pac-BBBD/.

Primary area:
reinforcement learning
Keywords:
safe reinforcement learning, reach-avoid, statistical verification, PAC guarantees, conformal calibration, certified control

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_LeSeOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents Reach-Avoid Probability Certification (RAPC), a framework for learning and certifying state-dependent lower bounds on reach-avoid success probabilities using simulator rollouts. The method uses repeated rollouts from sampled initial states to construct local binomial confidence checks, followed by an outer statistical test to certify the probability mass of states where the learned bound overestimates the true success probability. It also uses conformal calibration to improve the acceptance of learned bounds and supports adaptive policy updates with PAC guarantees. Experiments on several control environments demonstrate the feasibility of the approach and the benefits of state-dependent bounds over constant bounds.

Critical strengths

The paper provides mathematically rigorous PAC guarantees under clearly stated sampling assumptions. The theoretical analysis appears sound, and the experiments include several control environments and detailed comparisons.

Critical weaknesses
  1. The paper does not clearly establish the novelty of the research problem or the gap in existing work. State-dependent stochastic reachability certification, model-free probabilistic verification, and PAC guarantees have already been extensively studied. For example, Thorpe et al. (2022) study model-free, state-dependent confidence bounds for stochastic reachability, while Cairoli et al. (2025) study conformal predictive monitoring with probabilistic guarantees for stochastic systems. These works do not necessarily provide exactly the same guarantee as RAPC. However, the paper does not clearly explain which important limitations of existing approaches motivate its particular formulation, or what previously unresolved challenge it addresses. The distinction between the proposed guarantee and existing guarantees is not sufficient by itself to establish a new research problem. The paper needs to explain why this particular guarantee is needed and what existing methods cannot achieve.

Thorpe, Adam J., Kendric R. Ortiz, and Meeko MK Oishi. "State-based confidence bounds for data-driven stochastic reachability using Hilbert space embeddings." Automatica 138 (2022): 110146.

Cairoli, Francesca, et al. "Conformal quantitative predictive monitoring of stochastic systems with conditional validity." Nonlinear Analysis: Hybrid Systems 57 (2025): 101606.

  1. The methodological contribution and its scope are unclear. The core certification method does not use the specific structure of reach-avoid problems. Its main theoretical results rely only on repeated Bernoulli observations conditioned on an input. The same method appears applicable to any stochastic program with a binary success outcome, without using Markov dynamics, reach-avoid specifications, or their mathematical properties. This creates an important question about the intended contribution. If RAPC is proposed as a general statistical certification method for unknown conditional probabilities, it should be positioned and evaluated against existing general statistical methods, including nested statistical testing and PAC calibration. The paper needs to identify the specific challenge that these methods cannot address and explain how RAPC resolves it. Alternatively, if the contribution is intended to advance reach-avoid verification, the paper should identify the challenges specific to reach-avoid systems and explain how its method addresses them. Currently, the paper does not convincingly establish either contribution. The main certification procedure appears to follow naturally from classical binomial confidence bounds, statistical testing, and conformal calibration. Using these established techniques is not itself a weakness, but the paper does not clearly identify the new challenge or insight that makes their use here a substantial advance.

  2. The experiments provide limited evidence of practical advantages over existing approaches. The experiments demonstrate that state-dependent bounds can be more informative than constant bounds when success probabilities vary across initial states. However, this is an expected benefit of state-dependent prediction and does not establish the advantage of the proposed certification method over existing state-dependent approaches. The high-dimensional experiments are also less challenging than their stated dimensions suggest. For example, Hopper's initial-state distribution mainly varies along one coordinate, while PointGoal has a six-dimensional physical state despite using 44-dimensional observations. Several evaluated policies already have near-perfect success rates. Furthermore, the certification cost is substantial. The main verification configuration requires 10,000 initial states and 1,000 rollouts per state, amounting to 10 million validation trajectories per round. Although the paper proposes a calibration-only certification approach to reduce this cost, the main experiments rely on separate validation. The experiments do not sufficiently demonstrate the practical efficiency advantage of RAPC over alternative statistical certification approaches under comparable guarantees and computational budgets.

Questions for authors
  1. What is the specific research problem that existing methods cannot solve? How does the proposed formulation differ in motivation and practical requirements from existing model-free stochastic reachability certification methods, particularly Thorpe et al. (2022)?

  2. Is RAPC intended as a general statistical certification method or a reach-avoid-specific method? If it is general, what is its key contribution over existing methods for conditional probability estimation, nested statistical testing, and PAC calibration? If it is specific to reach-avoid, what properties of reach-avoid systems are used to address a challenge that does not arise in general stochastic prediction?

4 comments
AuthorsOpenReview ↗

Response 1

Thank you for the thorough review, the insightful questions on positioning, and the references to Thorpe et al. (2022) and Cairoli et al. (2025), which we will cite. We will revise how the Abstract and Introduction characterize prior certificates to reflect these works.

Existing methods and motivation. RAPC addresses selecting and certifying a learned lower-bound function for latent success probabilities using repeated rollouts from sampled starts. Its guarantee controls overstatement mass without RKHS or dynamics-regularity assumptions and covers adaptive policy updates.

Specifically, prior work targets different guarantees and assumptions:

  • Thorpe et al. give a two-sided, state-based confidence bound at a given state–action pair (x, u) for terminal-hitting reach-avoid probabilities, estimated with conditional kernel mean embeddings from one-step transition samples, assuming the value functions lie in the unit ball of an RKHS. For any bounded continuous kernel, including the Gaussian kernel used in their experiments, RKHS functions are continuous; by the same lemma, an RKHS can contain a discontinuous function only if its kernel is unbounded or discontinuous (Steinwart & Christmann, 2008, Lemma 4.28). Reach-avoid value functions are built from 0/1 indicators of the target and hazard sets and can be discontinuous at set boundaries. A discontinuous kernel could accommodate some discontinuities, but the bound would still require the value functions to lie in that kernel's RKHS within an assumed norm bound (one in Thorpe et al.'s analysis), a prior regularity assumption. For a fixed Gaussian kernel, sufficiently steep transitions can also violate the unit-ball assumption. RAPC requires neither RKHS membership nor a norm bound, and no prior assumption on where or how sharply p varies.
  • Cairoli et al. predict the STL robustness of a future trajectory with conformalized quantile regression under marginal, sign-conditional and localized coverage formulations.

What these works do not provide, and what motivates our formulation, is a certificate for a learned lower-bound function of the latent success probability over the start distribution, with an explicit cap ε on the start mass where the bound may overstate p (exceptional-start mass), obtained from Bernoulli rollouts under iid restartable sampling and valid across adaptive policy updates.

Problem and scope. The certification method is general: it uses repeated Bernoulli outcomes conditioned on an input; reach-avoid supplies the application and the Ratio-TD learner. Conditional-probability estimators supply the candidate q; the certificate holds whatever the candidate's accuracy, which affects only how often a candidate passes and how high the certified bound is. RAPC combines nested statistical testing with order-statistic PAC calibration of an observable rollout score, letting us select and certify a lower-bound function q from a learned family on a single rollout block.

Our goal is to learn which starts meet a required success probability when the relevant regions are not known in advance. Part 2 of the general response explains how the certificate supports all threshold sets of q and subsequently selected regions.

While a nested test can certify a single proposed q, the calibration problem is to select q from a learned family using the same rollout block while controlling overstatement of the latent p(x). Our construction uses an observable rollout residual whose exceedance coincides with a local rejection event, exact-rank PAC calibration, and a zero-output region fixed before calibration to handle infinite residuals at zero-success starts (simply clipping the confidence limits instead violated the guarantee in 2000/2000 replicates; see general response). Part 1 of the general response explains these steps in plain terms, and KTBN Q1 explains the acceptance bound and adaptive confidence allocation.

AuthorsOpenReview ↗

Response 2

Practical comparisons and cost. The follow-ups compare nested verifiers for the same certificate, the learned staircase case against partitions at matched new certification rollouts, and exact-rank against validation-gated synthesis.

  • Verifier comparison: When a separate validation batch verifies a single candidate bound, our fixed 10,000-start test can be replaced by other nested binomial tests for the same certificate. Replaying three such verifiers on saved validation batches under matched confidence budgets, an anytime-valid (sequential) mixture test inspected on average 31–68% of the fixed batch's starts, while accepting the same fraction of candidates that meet the target for the sample-mean bound (height) or up to 14 percentage points fewer; a 661-start test that accepts only if no start fails its local binomial test (zero-rejection) accepted far fewer (.00–.40). All three check the same certificate, so the choice among them is a cost trade-off rather than a change to the guarantee. Details in the follow-up below this reply.
  • Safe-start selection: At matched new certification rollout budgets, a learned set certified as a step bound (the staircase case) retained 98.2% of proxy-safe starts versus 78.9% for the per-seed hindsight-best partition, winning in all ten seeds (see the follow-up under the general response).
  • Synthesis cost: Exact calibration replaces the gated route's 2,048-start calibration block plus 10,000 × 1,000 validation batch with a single 4,096 × 1,000 calibration block that itself supplies the certificate (about 4.6 million versus 12.6 million rollouts per round, including fitting). KTBN Q2 reports output heights, rounds and total costs, including unsuccessful runs, for this route from weak initializations.

Dimensions and policy difficulty. We evaluated RAPC on a broader 11-coordinate Hopper task and synthesized policies from weak initializations (.23–.78 initial success on Hopper, .75–.93 on PointGoal); we will report all varying physical coordinates in the revision.

On the original tasks, as you note, PointGoal's physical state is six-dimensional. The broader Hopper study jointly varies four angles and six velocities in addition to head position (heights and costs in KTBN Q4). To complement the strong initial policies in the original tasks, the weak-initialization synthesis in KTBN Q2 starts from lower success rates. On the broader Hopper task, per-start success under the final policies still varied (empirical standard deviation .14 across starts, with 4.1% of starts below .9 empirical success), so a per-start bound carries information beyond the mean.

We hope these clarifications and new results are helpful for your final assessment.

AuthorsOpenReview ↗

Response 3

Follow-up: comparison with nested statistical tests (Reviewer LeSe)

We replayed three verifiers for the same certificate on saved validation batches (banks; each row is one start with its rollouts), as a retrospective, descriptive comparison. On banks whose candidate met the height target, across all eight task–arm groups in the table below, the sequential (anytime-valid) mixture test read on average 31–68% of the fixed batch's rows and accepted the same fraction or up to 14 percentage points fewer; a 661-start zero-rejection test accepted far fewer (.00 to .40).

We compared three verifiers for the same certificate on banks saved during synthesis: (1) the fixed 10,000-start test, (2) an anytime-valid mixture test that reads starts one at a time and can stop early, and (3) a 661-start zero-rejection test, which accepts only if no start fails its local binomial test. All three use the same local checks and a common confidence allocation δ_t = .05/38 per candidate. The table covers every group whose banks have all 10,000 starts available:

taskroutefixed batch (10,000 starts) acceptanceanytime-valid mixture acceptancemixture rows readzero-rejection (661 starts) acceptance
wide-start Hoppervalidation-gated.75.655,485.10
wide-start Hoppervalidation-gated, masked rank rule.95.953,676.10
wide-start Hopperno feedback.90.803,729.30
wide-start Hopperexact-rank, diagnostic validation batch.80.804,880.00
PointGoalvalidation-gated.92.926,815.00
PointGoalvalidation-gated, masked rank rule.857.7145,956.00
PointGoalno feedback.90.804,658.40
PointGoalexact-rank, diagnostic validation batch1.001.003,073.00

Acceptance is the fraction of height-eligible banks (banks whose candidate meets the height target) accepted, averaged within and then across seeds, with starts read in stored order.

Thank you for explaining how the same rollouts can be used to choose and certify the bound. The new experiments show that this saves rollouts compared with fixed-batch validation. My main question remains: what is the key new idea in exact-rank, beyond combining local binomial tests with standard PAC calibration?

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

The paper proposes RAPC, a framework for learning and certifying state-dependent lower bounds on finite-horizon reach-avoid probabilities. It combines local binomial confidence bounds, a population-level acceptance test, calibration, and confidence allocation across adaptive learning rounds. The guarantee controls the initial-state probability mass on which the learned function overestimates success. Experiments examine certificate validity, informativeness, policy refinement, and computational cost.

Critical strengths
  1. The certification objective distinguishes state-dependent probability bounds from aggregate success estimates and explicitly characterizes the permitted exceptional states.

  2. Independent validation accommodates arbitrary candidate learners without requiring approximation-error guarantees.

  3. The evaluation includes known-probability examples, alternative learners, computational accounting, and unsuccessful refinement outcomes. The distinction between exact calibration and the implemented procedure is acknowledged.

Critical weaknesses
  1. The principal statistical mechanisms have close precedents. Eq. (7) follows the error-propagation structure of Younes (2006), Error Control for Probabilistic Model Checking, as acknowledged in Appendix B.6. Proposition 1 applies Vovk (2012), Conditional Validity of Inductive Conformal Predictors, Proposition 2b, explicitly invoked in Appendix A.4. Theorem 1 extends validity through conditioning on prior history and confidence-budget allocation. Calibration against finite-rollout confidence limits and the learner-independent acceptance bound are useful features, but the significance of the theoretical extension beyond established constructions remains insufficiently demonstrated.

  2. Table 4 compares the routes on 40 previously accepted policy–candidate pairs, without activating the clipping threshold. This supports the approximately fivefold certification-rollout saving for those fixed pipelines. However, the weak-policy experiments do not establish whether exact calibration remains informative and reduces total computation throughout synthesis.

  3. The reported configuration requires approximately 12.57 million rollouts per round with validation, or 2.57 million with exact calibration, excluding additional candidate-learning costs. Reusable state-dependent queries are a legitimate benefit. Nevertheless, Section 6.2 shows that direct Monte Carlo is substantially cheaper for a predetermined region. Because these methods need not certify the same quantity, a convincing comparison should align the decision-relevant guarantees, confidence requirements, and region-selection procedures. The additional functional information has not yet been shown to justify its computational cost for the demonstrated decisions.

  4. The initial distributions of Hopper and PointGoal vary substantially in relatively few physical coordinates. These are legitimate task settings, but they provide limited evidence about informative certification when velocities, configurations, and other dynamically relevant coordinates vary jointly. The statistical test has no explicit dimensional dependence; the unresolved issue is the cost of learning and certifying useful bounds under more demanding distributions.

Questions for authors
  1. Which technical obstacles require new analysis beyond the cited nested-testing and calibration results, including for the learner-independent acceptance bound?

  2. Does exact calibration remain informative throughout synthesis from weak policies? Please report zero-bound frequency, final bound height, refinement rounds, and total cost.

  3. What downstream advantage does RAPC provide over regional estimation under comparable guarantees and computational budgets?

  4. How do the results change under broader initial-state distributions and hazard checks at every simulation substep?

  5. How sensitive are the results to checking hazards at every simulation substep?

4 comments
AuthorsOpenReview ↗

Response 1

Thank you for the careful reading and the precise questions; they led directly to the new experiments below.

Q1. Our contribution is a calibration procedure for learned lower-bound functions of latent success probabilities that handles zero-success starts and adaptive policy updates using only Bernoulli outcomes.

The technical obstacle is that p(x) is never observed: each rollout only reports success or failure.

We subtract a scalar shift c (possibly negative) from a learned predictor's logit. At each calibration start, the residual is the smallest shift at which the shifted bound passes a local binomial test at that start, so the residual exceeds c exactly when that test rejects the shifted bound (the local rejection event). Setting c to an order statistic of the residuals (exact rank) caps the number of local rejections and thereby bounds the start mass where q overstates p. A start with zero observed successes cannot pass the test for any positive bound, so its residual is infinite; a zero-output region (q preset to 0) fixed before calibration can keep such starts from forcing q ≡ 0 when the predictor separates difficult starts, without clipping the confidence limits.

The elements not in the cited results are (1) this residual, whose exceedance coincides exactly with the local rejection event and so makes the unobserved p calibratable, and (2) the zero-output region for infinite residuals at zero-success starts; clipping instead voids the guarantee (2000/2000 violations, general response). The remaining steps are inherited: the bound on the probability that a calibrated candidate passes a later validation batch holds for any learner and follows from Vovk's coupling and binomial-tail monotonicity, and validity across adaptive policy-update rounds follows by conditioning on prior history and splitting the confidence budget δ across rounds.

Q2. In end-to-end synthesis from weak initializations, validation-free exact-rank calibration returned certified bounds meeting the target in 10/10 Hopper and 9/10 PointGoal seeds (vs 10/10 and 8/10 with validation), with 40% (Hopper) and 74% (PointGoal) of the validation-gated route's recorded transitions per useful return (a run returning a certified bound that meets the target); no round returned q ≡ 0.

We ran full synthesis with the MC learner and the exact-rank rule throughout:

  • Zero-output regions and no validation batch.
  • n = 4096 calibration starts per round, for at most 27 rounds (keeping the per-run ceiling on calibration rollouts, including their fitting rollouts, plus validation rollouts within 3% of the 10-round gated route).
  • Weak initializations on wide-start Hopper (mean-bound target 0.8) and PointGoal (0.9), across 10 seeds each.

These certificates hold under the paper's assumptions: fresh iid rollout blocks in each round, conditional on prior history; a candidate family, including the zero-output region, fixed before calibration and monotonically ordered by the shift c (nested in the shift); conservative rounding in the local tests that preserves this ordering; the same bound function for counting rejections and for deployment; and per-round confidence levels fixed before each round's data are drawn (predictable from prior history) and summing to δ.

Median rounds were 2 vs 2.5 (Hopper) and 15 vs 9.5 (PointGoal). Among successful runs, median transitions excluding shared initialization were 43% and 76% of the gated route's. These comparisons are descriptive. The total cost per useful return includes unsuccessful runs:

taskroutereturned mean q (range)transitions per useful return, excl. / incl. initialization
wide-start Hopperexact, no validation.934 (.883–.968)1.81e9 / 2.33e9
wide-start Hoppervalidation-gated.934 (.831–.964)4.55e9 / 5.06e9
PointGoalexact, no validation.917 (.911–.929)1.30e9 / 1.37e9
PointGoalvalidation-gated.919 (.906–.938)1.75e9 / 1.84e9

Mean bounds (heights) are sample means on calibration blocks (exact route) or validation batches (gated). Costs are total recorded transitions over all ten runs divided by useful returns. Capping each run's calibration plus validation rollouts at 10^8, useful returns were 10/10 for both Hopper routes and 7/10 (exact) versus 2/10 (gated) on PointGoal.

AuthorsOpenReview ↗

Response 2

Q3. Certifying a learned set as a step bound (.9 on the set, 0 elsewhere; the staircase case) selects starts without drawing regions in advance: at matched new certification rollout budgets on fresh joint-start Hopper blocks, it retained on average 98.2% of proxy-safe starts versus 78.9% for the per-seed hindsight-best partition (winning in 10/10 seeds).

Direct Monte Carlo estimation, as in Section 6.2, answers the question for a region given in advance. RAPC's downstream advantage arises when the regions are not known in advance: one certificate covers every threshold set of q and every region queried afterwards, with no further rollouts (Part 2 of the general response). The experiment below measures this for selecting safe starts.

The comparison (safe-start selection follow-up, posted under the general response) includes 15 fixed grids and six CART partitions, all fixed before certification. At reliability .9, violation mass .01 and standalone confidence .95, with matched new certification rollouts, the learned step set retained more proxy-safe starts than every tested partition in each seed; grids over all eleven varying coordinates retained under 1%. This tests the practical benefit of learning the selection boundary for one required reliability level.

Q4: broader initial distributions. When we expanded wide-start Hopper to vary four initial angles and all six velocities alongside head position, validation-free synthesis returned certified bounds meeting the 0.8 sample-mean target in all 10 seeds.

To test RAPC beyond the original few-coordinate distributions, the study below varies eleven physical coordinates jointly. Statistical validity has no explicit state-dimension term under the sampling assumptions, but dimension can affect attainable height and learning and simulation costs.

In an exploratory study on wide-start Hopper, we added independent uniform variation to four initial angles (±0.1 rad) and all six velocities (±0.5). Using exact-rank calibration with a zero-output region (rejections counted on the deployed bound values) and a target of .8 for the sample-mean bound, the validation-free route yielded:

  • 10/10 seeds returning certified bounds meeting the target, with sample means 0.809–0.897 (average 0.840).
  • 0.436–2.344 billion new procedure transitions per seed (mean 1.113 billion), or 11.127 billion across all ten runs, excluding inherited initialization.
  • For comparison, the original wide-start runs without the added variation (validation-gated route, 10-round cap, no height target) used 17.1 billion transitions, with mean bound 0.82.

These are per-run certificates and synthesis results with continued policy refinement under broader starts; the mean bounds are sample summaries. The safe-start selection follow-up (under the general response) evaluates the final policies on fresh blocks.

AuthorsOpenReview ↗

Response 3

Q4–Q5: hazard-check resolution. In the submitted experiments, the target and failure conditions were checked after each action repeat: every two base-environment steps in Hopper and every twenty physics steps in PointGoal. Checking more finely changed fewer than 0.2% of rollout success/failure verdicts across 49 audited accepted pairs, and in a preregistered fresh-data follow-up on all 19 wide-start Hopper pairs, 10/10 Ratio-TD and 7/9 MC pairs recertified when checking every Hopper base step. We will state the time resolution of the certified event explicitly.

For the audit, we evaluated 49 previously accepted policy–bound pairs on 10,000 newly sampled starts with 1,000 rollouts each, scoring the same trajectories at the policy-step resolution and at a finer one. The finer event ends at the first observed target entry or failure, with the target taking priority if both occur at the same time. Hopper checks each base-step endpoint, not its four internal physics frames; PointGoal checks each physics frame.

Across the audit:

  • Overall, fewer than 0.2% of rollout success verdicts changed, though single-start estimates differed by up to 0.79 and two of nine wide-start Hopper MC pairs failed the finer-event test.
  • In the 30 main-task evaluations (a separate calibration grid, not Table 1), local rejection counts did not increase under the finer event and all finer-event tests passed. Finer checks can also detect target entries earlier, which raises success counts, so this comparison reflects both target and hazard resolution.
  • On wide-start Hopper, rejection counts increased in all but two of the 19 evaluations. All ten Ratio-TD pairs passed both tests. All nine MC pairs passed the fresh policy-step test, seven passed the finer-event test, and two failed with 85 and 75 local rejections among the 10,000 starts, above the 74 allowed. Every start whose success estimate fell by more than 0.05 lay within 0.13 of the hazard block.

These are fresh-batch sensitivity results; the original certificates concern their stated event resolution.

We also ran a preregistered fresh-data follow-up on all 19 wide-start Hopper pairs, checking each Hopper base step at δ=.005 per pair (19-pair union bound .095). Here, 10/10 Ratio-TD and 7/9 MC pairs recertified. MC seed 5 was not certified (77 rejections, above the 74 allowed), and MC seed 4 has no test decision because its stored candidate failed the reproduction check before testing.

We thank you again for the rigorous feedback and hope these new experiments are helpful for your final assessment.

Overall, the rebuttal could address some of my concerns and their honest acknowledgment of the "clipping" flaw. However, the manuscript itself remains fundamentally unchanged and does not highlight the changes. The flawed clipping heuristic is still explicitly present in Section 5.2, and the critical methodological patches, such as the zero-output region, are confined solely to the OpenReview thread.  Hence, I do not see the paper above the acceptance bar.

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

For reach-avoid problems, policies look good on average but fail at certain starting points. This paper propose RAPC, which learns a state-dependent lower bound q(x)q(x) purely from simulation rollouts. It leverages binomial confidence checks for solid PAC guarantees, works with adaptive updates and needs no dynamics model. On high-dimensional robot environments, its bounds are tighter than old constant certificates.

First, the method connects the unobservable event of overestimating the true success probability to observable failures of local binomial confidence checks. Secnd, The main experiments return certified outputs in all 10 seeds for each task.

Critical strengths

1 It works for high‑dimensional systems where traditional model‑based certificates fail.Unlike RASM and barrier‑certificate methods, RAPC needs no known dynamics model, no Lipschitz assumptions, and no state‑space gridding. It can handle hard high‑dimensional robot tasks like Hopper and PointGoal that cause old methods to time out.

2 It learns a state‑dependent probability lower bound instead of just one single global constant. Instead of outputting one uniform number for all starting states, it produces q(x)q(x) that varies per state. This gives much tighter bounds when starting‑state success rates differ widely, as seen in the wide‑start Hopper experiment.

  1. It supports adaptive policy updates while still maintaining valid PAC guarantees. Many conformal or statistical verification approaches require a fixed policy before validation. RAPC iteratively improve the policy and re‑compute the bound in multiple rounds, by splitting the total error budget across rounds.
Critical weaknesses

W1: This is only a distribution‑level guarantee, not a per‑state guarantee, so the safety guarantee is relatively weak. What this really means: At most an ϵ\epsilon probability mass of starting states will have over‑optimistic bounds. But we cannot tell exactly which individual states are those bad ones. There is no promise that q(x)q(x) will work correctly for any single new state x we pick.

W2: The computational cost is pretty high, and it eats up a huge number of rollouts. In experiments, one round of verification for the Hopper task requires hundreds of millions of simulation transitions. That makes it hardly feasible for real‑world large‑scale systems.

W3: If the true reach‑avoid success probability is pretty similar across all starting states, RAPC’s state‑dependent q(x)q(x) gives only very little improvement over a global constant bound. When there’s only small variance in success rates across different starting points, this method brings limited benefits.

Questions for authors

For the wide-start Hopper and weak-initialization runs you already have — what would exact-rank calibration have actually given you? Like, how often would it have just spat out the zero function, and when it didn't, what kind of bound would it have returned on average?

1 comment

Thank you for the positive assessment, the clear summary of the method's strengths, and the concrete question, which led to a useful new analysis below.

Exact-rank calibration on the stored runs. In the submitted runs, the implemented shift step clamps c at zero, so that step never raises the fitted predictor, and the certificate comes from a separate 10,000-start validation batch. We replayed unclipped exact-rank calibration, which needs no validation batch, on the same candidates. It returned q ≡ 0 in 0% to 37.9% of calibration subsets, depending on the group, and no round accepted by the implemented rule had an estimated collapse probability above 50%. At the final rounds accepted by the implemented rule, averaged across those runs within each of the four groups, exact and implemented mean bounds differed by at most 0.017.

Specifically, we rebuilt each round's candidate from its checkpoint (reconstruction error at most 0.009) and recalibrated it with the exact-rank rule, without the implementation's clamp at zero, on 200 random 2048-start subsets of that round's 10,000-start validation batch, evaluating each result on the remaining 7952 starts. This is a counterfactual along the policy sequence produced by the implemented rule. With n = 2048 calibration starts and rank k = 2039, the rule allows at most 9 starts with infinite residuals, so ten or more zero-success calibration starts force q ≡ 0.

runsrounds with estimated P(q ≡ 0) > 0.5were those rounds accepted by the implemented rule?final accepted rounds: exact vs implemented mean bound
wide-start Hopper, Ratio-TD5 of 28no0.804 vs 0.821 (10 runs)
wide-start Hopper, MC13 of 33 (8 from one seed that never certified)no0.966 vs 0.966 (9 runs)
PointGoal, weak initialization, Feedback3 of 83no0.912 vs 0.918 (7 runs)
PointGoal, weak initialization, Train0 of 84–0.905 vs 0.912 (5 runs)

Pooling 200 calibration subsets per round, collapse occurred in 999/5600 (17.8%), 2504/6600 (37.9%), 600/16600 (3.6%) and 0/16800 subsets for the four rows. Among noncollapsed subsets, the mean bound on the remaining starts averaged .620, .741, .800 and .784, respectively. Among noncollapsed round-one candidates on wide-start Hopper, retrospective exact-rank mean bounds were 0.17–0.66; these initial candidates were calibrated on the original start distribution, so exact-rank calibration on the wide distribution certifies them only at low heights. Synthesis with exact calibration therefore continues until the sample-mean bound meets a height target, rather than stopping at such a valid but low bound (results in KTBN Q2).

W1. Thank you for stating this distinction so clearly. As you note, when certifying from sampled starts without structural assumptions on p, the certificate supports population-level claims under the stated start distribution rather than identifying exceptional starts or establishing safety at a single chosen start. These population-level claims do extend to any region chosen afterwards, including one given by a membership test, with no new rollouts (Part 2 of the general response).

For completeness, the reason is as follows. If starts are sampled iid from a distribution without atoms (no single start has positive probability, so a prespecified x₀ is almost surely never sampled), changing p only at x₀ leaves the distribution of the observed data unchanged. Hence any procedure guaranteeing pointwise coverage at x₀ for every measurable success-probability function must return a non-positive bound there with probability at least 1−δ. This argument does not apply when rollouts are collected at x₀ (which our test supports) or when structural assumptions restrict p.

W2. Thank you for raising the question of simulation cost. In weak-initialization synthesis, excluding shared initialization, the validation-free exact-rank route needed only 43% (wide-start Hopper) and 76% (PointGoal) of the gated route's median transitions among successful runs, and 40% and 74% of its transitions per useful return.

The calibration step itself used 20,480 rollouts: 10 per start on a 2048-start calibration block (local binomial test level β = 0.5). With it, recalibrating a fixed policy reached mean accepted bounds of 0.80 on Hopper (9/10 seeds) and 0.932 on Linear (10/10). This count excludes policy fitting and the separate validation batch that accepted these bounds; exact-rank calibration removes that batch, and KTBN Q2 gives total costs including unsuccessful runs and initialization.

W3. As you note, the gain over a constant is small when per-start success is nearly uniform. RAPC targets heterogeneous start distributions, where the gain is large: on wide-start Hopper the certified function averaged 0.82 against 0.51 for the largest constant the same batch accepts.

Thank you again for your support and for the constructive question.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response

We thank all three reviewers for their careful reading and constructive questions. This general response has two parts. Part 1 (this comment) explains what RAPC certifies and how, and lists the new results together with the reply that reports each. Part 2 (the reply directly below) gives two results that several replies refer to: a validity check of calibration without a validation batch, and why we certify a function rather than regions.

What RAPC certifies. Under a fixed policy, each start x has an unknown success probability p(x), observable only through success/failure rollouts. RAPC learns a function q(x) that lower-bounds p(x) and certifies it: under the stated sampling and numerical-check assumptions, with confidence 1−δ over a run's data across adaptive rounds, every returned policy–bound pair satisfies μ{q > p} ≤ ε, where μ is the start distribution. In words, q may overstate the true success probability only on starts of total probability at most ε. Consequently, μ({q ≥ t} ∩ {p < t}) ≤ ε for every t simultaneously (Theorem 1): among the starts that q places at or above any required level t, those truly below t have total probability at most ε. Mean bounds reported below are sample means, not certified population means.

How the certificate is obtained. The difficulty is that p(x) is never observed, so q cannot be compared with it directly. We start from a learned candidate q(x) = min{σ(z(x))/ρ̃(x), 1}, where z is a learned logit and ρ̃ is a fixed learner-specific denominator (equal to 1 for all but one of our learners), and subtract a scalar shift c from z (c may be negative), giving q_c. For each calibration start, let L be the binomial lower confidence limit on p(x) computed from that start's rollout successes. The residual e = z(x) − logit(ρ̃(x)L) is the smallest shift at which the shifted bound passes the binomial test at that start. A start's residual therefore exceeds c exactly when its test rejects q_c (in exact arithmetic). Setting c to an order statistic of the residuals (exact-rank calibration) caps how many calibration starts fail their test, which controls the start mass where q overstates p. The same rollout block thus both selects and certifies q, with no separate validation batch. (The submitted experiments certified with a separate validation batch; this validation-free route is evaluated in the new experiments below.)

A start with zero observed successes has lower confidence limit 0, so no positive bound passes its test and its residual is infinite; if too many calibration starts are like this, the rule sets c = ∞ and q ≡ 0. To prevent this when the predictor separates difficult starts, we fix before calibration a zero-output region where q is set to 0, which never overstates p. The construction builds on nested testing (Younes, 2006), training-conditional order-statistic calibration (Vovk, 2012) and confidence allocation across adaptive rounds; the new elements are the residual, which exceeds c exactly when the local binomial test rejects q_c and so makes the unobserved p calibratable, and the zero-output region for zero-success starts (details in our reply to KTBN, Q1).

New results and where they are reported.

  • Synthesis from weak initial policies without a separate validation batch (KTBN Q2, 2ZGD W2): certified bounds meeting the sample-mean target in 10/10 Hopper and 9/10 PointGoal seeds (10/10 and 8/10 for the validation-gated route, which uses a separate validation batch), at 40% and 74% of the validation-gated route's transitions per useful return (transitions over all runs, excluding shared initialization, divided by runs returning such a bound).
  • Exact-rank calibration replayed on the submitted runs (reply to 2ZGD): averaged over final accepted runs, its mean bounds were within 0.017 of the implemented ones in each of the four groups.
  • Broader starts (KTBN Q4): four angles and six velocities varied alongside head position; 10/10 Hopper seeds certified, sample-mean bound 0.84.
  • Finer hazard checks (KTBN Q4–Q5): checking every Hopper base step, 17 of 19 wide-start Hopper pairs recertified on fresh data.
  • Selecting safe starts without drawing regions (KTBN Q3, LeSe; follow-up posted under Part 2): a certified learned set retained on average 98.2% of proxy-safe starts (≥900/1000 evaluation successes) versus 78.9% for the per-seed hindsight-best fixed partition, winning in 10/10 seeds.
  • Comparison with nested statistical tests (LeSe; follow-up under our reply to LeSe): replayed on saved validation batches whose candidate bounds met the target for the sample-mean bound (height), an anytime-valid sequential test inspected on average 31–68% of the starts of the fixed 10,000-start batch, while accepting the same fraction of candidates or up to 14 percentage points fewer; a 661-start zero-rejection test accepted far fewer (.00–.40).
  • Positioning relative to Thorpe et al. and Cairoli et al. (reply to LeSe; summarized at the end of Part 2).
AuthorsOpenReview ↗

General response 2

Validity of calibration without a validation batch (referred to by KTBN Q1 and LeSe). We tested the exact-rank rules on a synthetic benchmark where the true success probabilities are known, so every violation can be counted. The exact rules had 0/2000 violations of μ{q > p} ≤ ε in all 156 settings whose parameters satisfy the theorem's certification condition (eligible settings). A tempting shortcut for zero-success starts is to replace their zero lower confidence limit with a small positive floor (clipping), which keeps their residuals finite, instead of using a zero-output region. Clipped variants (rank and interpolation) violated the guarantee in 2000/2000 replicates in settings where starts of total mass ≥ .05 have success probability ≤ 1e-4, so clipping is not a valid substitute for the zero-output region. The certificates in the submitted paper were obtained with an independent validation batch, so they do not rely on clipped calibration.

Why certify a function rather than regions (referred to by LeSe). Certifying q gives a guarantee for all its threshold sets and for regions chosen afterwards. On the event μ{q > p} ≤ ε, for every measurable region A and threshold t,

μ(A ∩ {p ≥ t}) ≥ μ(A ∩ {q ≥ t}) − ε.

This holds simultaneously, including for regions selected after certification, defined from q, or given by a membership test (Appendix A), with no further certification rollouts or confidence allocation. Estimating masses such as μ(A ∩ {q ≥ t}) from samples still needs its own confidence control, including for region selection and multiple comparisons; conditioning the guarantee on a region A of positive mass scales the allowed overstatement fraction within A to ε/μ(A).

This matters because the task is to find which starts meet a required success level t when the relevant regions are not known in advance. A partition-based certificate, like the grid and CART baselines compared here, fixes its cells before certification. The unknown boundary p = t can cut through a cell; if including the whole cell would exceed the allowed violation mass, the cell must be excluded, losing its safe starts, or certified at a lower level. Refining the grid multiplies the cells, and a partition drawn from data must itself be learned. RAPC instead learns q, which can follow the boundary, and one certificate covers all its threshold sets.

For one required level t, certifying a learned set G directly is the special case q = t·1_G (t on G, 0 elsewhere; the staircase case). In the safe-start experiment (follow-up below this comment), at matched new certification rollout budgets on fresh joint-start Hopper blocks, this step bound retained on average 98.2% of proxy-safe starts versus 78.9% for the per-seed hindsight-best of 21 fixed partitions (15 grids and six CART trees), winning in 10/10 seeds.

We will revise the characterization of prior certificates in the Abstract, Introduction and Section 6.2 to reflect Thorpe et al. (model-free, state-based bounds under RKHS assumptions) and Cairoli et al. (conformal predictive monitoring guarantees); unlike these, RAPC certifies a learned lower-bound function over the start distribution from Bernoulli rollouts, without RKHS or dynamics-regularity assumptions, with an explicit exceptional-start mass and validity across adaptive policy updates (details in our reply to LeSe).

AuthorsOpenReview ↗

General response 3

Follow-up: certified safe-start selection (Reviewer KTBN, Q3; Reviewer LeSe)

At matched new certification rollout budgets on joint-start Hopper, certifying a learned step set retained 98.2% of proxy-safe starts on average, beating the per-seed hindsight-best partition (78.9%) in 10/10 seeds.

On Hopper with jointly varied initial positions and velocities, we gave ten frozen policy/score pairs 4,096 starts × 1,000 certification rollouts each, plus an independent evaluation bank of the same size. The step template and exact-rank rule were fixed before these blocks were drawn. The primary endpoint was step recall minus the per-seed hindsight-best recall among 21 partitions fixed before certification:

  • 15 grids over different coordinate subsets and resolutions.
  • Six CART trees fitted on historical data.

We use the same certification machinery with a step template, qτ(x) = .9·1_{Sτ}(x): the bound is .9 on the learned set Sτ = {x: g(x) ≥ τ} and 0 elsewhere, where g is the frozen score and τ is the calibrated threshold. This is the staircase case of certifying a learned function, with no regions drawn in advance. It extends Proposition 1 to this nested family; its proof carries over, and we will state the extension. τ is chosen by exact rank: we lower τ as far as possible while at most 30 of the 4,096 calibration starts inside Sτ fail their (numerically guarded) local binomial test of the bound .9; starts tied at the cutoff score are excluded together. Every seed returned a nonempty set using all 30 allowed rejections. Each standalone route uses δ=.05 for μ(Sτ ∩ {p < .9}) ≤ .01, under fresh iid sampling and accurate-numerics assumptions.

On the independent evaluation banks:

  • Mean safe-start proxy recall was 98.2% for the step (seed range 97.0–99.7%) versus 78.9% for the per-seed hindsight-best partition.
  • The step won in 10/10 seeds, with a mean paired gain of 19.31 percentage points (descriptive sample SD 12.76).
  • All-coordinate grids retained at most 0.54% on average across the tested resolutions.
  • The step's mean selected mass was 94.6%.

Here, recall measures the fraction of starts with at least 900 successes in 1,000 evaluation rollouts that are retained; these are noisy proxy labels. The comparisons are descriptive. Certificates are per run and per standalone route, and selecting between standalone methods is not jointly covered. Picking the best of 21 partitions per seed in hindsight favours the baselines; the step still won in every seed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.