- 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
- 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.
-
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.
-
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
-
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)?
-
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
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.
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:
| task | route | fixed batch (10,000 starts) acceptance | anytime-valid mixture acceptance | mixture rows read | zero-rejection (661 starts) acceptance |
|---|---|---|---|---|---|
| wide-start Hopper | validation-gated | .75 | .65 | 5,485 | .10 |
| wide-start Hopper | validation-gated, masked rank rule | .95 | .95 | 3,676 | .10 |
| wide-start Hopper | no feedback | .90 | .80 | 3,729 | .30 |
| wide-start Hopper | exact-rank, diagnostic validation batch | .80 | .80 | 4,880 | .00 |
| PointGoal | validation-gated | .92 | .92 | 6,815 | .00 |
| PointGoal | validation-gated, masked rank rule | .857 | .714 | 5,956 | .00 |
| PointGoal | no feedback | .90 | .80 | 4,658 | .40 |
| PointGoal | exact-rank, diagnostic validation batch | 1.00 | 1.00 | 3,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?
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:
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.