acceptodds
Under review as a conference paper at ICLR 2027

Safe Policy Selection: When to Stop and What It Costs

Abstract

Testing a trained policy can reveal whether it is safe, but the test itself can cause a safety violation. We study how to search a fixed policy library with predetermined preference scores under a per-episode risk limit. We combine candidate tests with known-safe fallback episodes, guided by risk bounds that remain valid throughout testing. Joint Anytime Certification and Exploration (JACE) certifies a safe recommendation with high probability. Its score is at least that of the fallback and every candidate whose risk lies below the limit by a prescribed margin. We separate the evidence needed for this decision from the extra episodes required to gather it safely. Upper and worst-case lower bounds from the same baseline-only start match up to logarithmic factors. On PointGoal1, JACE uses 37% fewer episodes on average than matched safe round-robin allocation to reach its stopping condition. Controlled experiments show how prioritization gains depend on whether search can focus on a promising candidate or must collect exclusion evidence for every alternative.

Primary area:
learning theory
Keywords:
Safe policy selection, Safe exploration, Anytime-valid inference, Sample complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_wtCNOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies sequential testing of a fixed policy library when executing an unverified candidate can itself violate a safety constraint. JACE maintains time-uniform risk bounds, mixes candidate episodes with a known-safe baseline, prioritizes unresolved candidates, and stops when it can certify a recommendation satisfying the risk limit and matching the frozen utility of all candidates safely below the limit by a prescribed margin. The paper proves joint safety of data collection and deployment, derives upper bounds on the number of episodes needed to complete the decision, and gives a worst-case lower bound with matching parameter dependence up to logarithmic factors. Experiments on PointGoal1, CarPush1, and synthetic libraries examine completion cost and when prioritization is useful.

Critical strengths

The paper addresses the right combined problem rather than treating safe exploration and stopping independently. Controlling risk during data acquisition while still obtaining enough evidence to rule out higher-utility competitors is genuinely different from merely identifying one safe candidate. The matching upper and lower analyses give the resulting cost decomposition real theoretical weight.

The experiments support the mechanism and do not only showcase the favorable case. PointGoal1 exhibits a sizeable reduction in completion cost, while CarPush1 demonstrates how a near-threshold higher-utility competitor can make completion much harder than initial certification. This is useful evidence that the authors understand the limits of prioritization rather than presenting it as uniformly superior.

Critical weaknesses

The utility guarantee is deliberately weaker than selection of the best safe policy. Because the comparison class excludes policies near the safety boundary, JACE may omit a higher-utility policy that is in fact safe. The paper is transparent about this, but the practical consequence can be significant if utility varies sharply in the margin band.

The theory relies on a relatively restrictive deployment model. The policy library, utility scores, episode laws, thresholds, and baseline guarantee are frozen before online collection. In many realistic settings, both utility estimates and environment risk drift, and obtaining a sufficiently certified fallback policy can itself be expensive. The current guarantees do not directly cover those cases.

Questions for authors

How should a practitioner choose the safety margin when the utilities of policies near the risk threshold differ substantially? Can you report a utility-versus-completion-cost curve rather than fixing a single margin?

Do the reported sample-efficiency comparisons include the episodes needed for baseline qualification and library preparation? If not, how does the ranking change when all data-collection costs required by the procedure are included?

Which parts of the guarantee survive if utility estimates are updated online or if policy risk changes slowly over time?

3 comments
AuthorsOpenReview ↗

Response to reviewer on quality–cost tradeoffs and deployment assumptions

We sincerely thank the reviewer for asking how the margin affects deployment quality, how preparation changes the cost comparison, and which guarantees survive changes in scores or risks.

W1 + Q1. How does the margin affect completion cost and the score returned?

Choose the margin according to how close to the risk limit the score guarantee must extend. Even a narrow margin can omit a high-scoring safe policy. On CarPush1, widening the margin from 0.02 to 0.03 reduced JACE's mean capped cost by 23.1% and raised completion from 7/10 to 10/10. Two runs that completed at both margins returned a lower score at 0.03. All four methods reached the 40,000-episode cap at each of the three smallest margins. The table shows JACE on ten paired seeds (Appendix C.8, Table 8).

Margin η\etaDeclaredMean capped episodesMean frozen score at declaration
0.004, 0.006, 0.01 (each)0/1040,000.0—
0.027/1035,351.22.8004
0.0310/1027,186.92.6839

At 0.03, 6 runs scored 2.8004 and 4 scored 2.5091. At 0.02, 2 of those 4 hit the cap and 2 were among the 7 scoring 2.8004. On PointGoal1, all methods scored 16.6130 (10/10 per margin). JACE averaged 5,792.0 episodes at 0.004 and 5,372.0 at 0.03. Independent assessment supported all declarations.

When the target is the best safe policy, compatible historical data can settle the decision directly. Using simultaneous risk intervals for all policies, including the qualified baseline, subtract the highest certified safe score from the highest score still compatible with safety. This bounds the frozen-score loss of the selected policy. If none qualifies, we withhold certification. On CarPush1, the 320,000 existing assessment episodes gave an upper bound below 0.008674, meeting a tolerance of 0.01 with no new collection and joint safety or score error at most 0.005 (Proposition B.2).

For a cold start, let ϵ\epsilon be the largest acceptable score loss. Suppose external evidence establishes that every safe policy scoring more than ϵ\epsilon above the baseline has risk at least Δ>0\Delta>0 below the safety limit. Choosing a positive margin no larger than Δ\Delta preserves the score tolerance at exact completion on joint coverage, provided the certificates have the required resolution. The sufficient deadline must also fit the remaining budget. Without information separating risks near the boundary, this guarantee has no uniform finite deadline (Appendix B.6).

For a separately requested fresh run at margin 0.02, the sufficient deadlines are 37,716 episodes for PointGoal1 and 124,031 for CarPush1. The corresponding frozen-score loss bounds against the best safe policy are 0 and 0.3001 (Table 9). None of the tested CarPush1 deadlines fits 40,000 episodes. The direct historical check is at least as tight on the same data.

Proposition B.5 allows the planning data to guide the choice among a predefined finite list of configurations. Once a configuration is chosen, we fix it and collect fresh episodes independently of the planning data. The policies and scores remain fixed, the planning intervals must cover all risks simultaneously, and baseline qualification must remain valid after selection. Policy streams are independent, with the same i.i.d. episode law for each policy across stages. With error allowances of 0.005 for planning, 0.045 for the deadline conditional on valid planning information and 0.05 for safety and valid completion, the unconditional probability of issuing a promise and violating it is at most 0.10. Newly commissioned preparation and reserved validation also count toward the total budget.

W2 + Q2. How do preparation costs and historical data affect the ranking?

On PointGoal1, JACE and Safe-RR averaged 5,412.8 and 8,615.5 online episodes, respectively. Adding the same preparation cost preserves that ranking but reduces the relative saving. Actually reusing candidate-risk observations can instead eliminate differences between allocation rules.

PointGoal1 cost accountingJACE savings relative to Safe-RR
Online collection only37.17%
One deployment omitting separate assessment of the other 15 policies1.45%
One deployment with all preparation0.62%
Ten deployments sharing all preparation5.35%

Pilot selection, scoring and baseline qualification used 32,000, 160,000 and 20,000 episodes. PointGoal1 pilot counts use archived summaries. The 1.45% scenario charges these 212,000 episodes and omits the benchmark's 300,000 assessments of other policies. Public offline-data acquisition and training costs were unmeasured and excluded. With a more conservative baseline risk cap, 40 paired replays still gave JACE a 36.9% online saving over Safe-RR (Appendices C.8–C.9).

With 10,000 historical episodes per policy and ten paired future runs, all four methods finished immediately on PointGoal1 and had identical CarPush1 costs on each seed, averaging 15,801.8 additional episodes. With ten disjoint 1,000-episode blocks per policy, CarPush1 means ranged from 22,338.4 to 22,366.7. Every method improved over its cold start in every pair and completed 10/10 with independent assessment support. These blocks share frozen development scores and measure sensitivity to the reused history. Table 7 reports fully observed settings. Appendix C.8 bounds missing costs for incomplete 100-episode-history replays.

Valid reuse continues each policy's risk test from its complete historical sequence under the original error budget. Policies, tests and error allocations are fixed before the first retained observation, sampling decisions precede outcomes, and independent policy streams retain their i.i.d. laws. Rewards from those same episodes can supply the scores even when risk and reward are dependent (Appendix B.4).

Supplemental CarPush1 assessment used 1,716,537 episodes, including 65,237 baseline episodes. The sequential procedure specified before collection gave fixed-output expected-return loss bounds of 0.011480 for the margin set and 0.308232 for the full-safe set. The terminal test was designed afterwards on these data and is exploratory, not a joint 0.05 certification of both 0.01 targets. The sequential bounds remain reusable for unchanged policies, output, targets and episode laws (Appendix C.9, Table 10).

W2 + Q3. What survives changes in scores or risks?

When risks are stationary, updating scores using observations already collected preserves both collection and recommendation safety. Whenever the stopping test passes on joint risk coverage, the recommendation's current score matches or exceeds those of the baseline and all margin-safe policies. Later score changes can reopen the search, so permanent completion and the original time bound need additional assumptions. Expected-return quality also requires score-error control or direct assessment (Corollary A.4, Appendix B.8).

Our experiments use stationary risks. Appendix B.9 extends the guarantee over a fixed horizon when a known bound limits how far each policy's conditional risk can change between any two rounds. We fix the observation window in advance and use fresh randomization for each draw. For each policy, we widen the confidence interval based on recent observations by the average allowed drift since those observations. A policy with no observations in the window receives the full interval [0,1][0,1]. Under adaptive sampling, all these intervals cover the current nonbaseline risks throughout the horizon with probability at least 1−α1-\alpha.

If the baseline also has a valid upper bound uniformly below the safety limit throughout the horizon, with failure probability at most δ0\delta_0, collection safety, recommendation safety and validity of each current margin comparison hold jointly with probability at least 1−α−δ01-\alpha-\delta_0. With fixed scores, a recommendation can remain in force for a specified period if the bounds widened for that period still certify its safety and exclude every higher-scoring candidate from the margin-safe set. Once that certificate expires, sampling must resume and previously excluded candidates can reenter.

AuthorsOpenReview ↗

Summary of our responses

Dear Reviewer wtCN,

Thank you again for your time and questions. To facilitate your review, we briefly summarize our responses:

  • Q1 (choosing the margin): Table 8 reports completion cost and returned score across margins. On CarPush1, widening the margin from 0.02 to 0.03 reduced JACE's mean capped cost by 23.1% and raised completion from 7/10 to 10/10, at a lower mean score. Existing held-out data already certify a CarPush1 policy within a 0.01 score tolerance with no new collection (Proposition B.2).
  • Q2 (preparation costs): On PointGoal1, JACE's saving over Safe-RR is 37.17% for online collection only, 0.62% when one deployment bears all preparation and 5.35% when ten deployments share it. The ranking is unchanged.
  • Q3 (changing scores or risks): With stationary risks, updating scores with collected observations preserves collection and recommendation safety. Appendix B.9 extends the guarantee over a fixed horizon when a known bound limits risk drift between rounds.

If our responses have resolved your questions, we would greatly appreciate it if you could consider updating your evaluation. We welcome any further questions.

Best regards,

The Authors

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

This paper studies how to select a safe policy from a fixed library when evaluation episodes can themselves cause safety violations. Policy preference scores are fixed in advance, while catastrophe probabilities are unknown. The proposed method, JACE, uses anytime-valid risk bounds to guide candidate testing, allocation between candidates and a safe baseline, and the decision to stop. With high probability, it controls each round’s conditional collection risk and certifies an individually safe recommendation whose score is at least that of the baseline and every candidate with a prescribed safety margin. The authors analyze the total collection cost, separating the evidence needed for the decision from the additional episodes required to collect it safely, and establish matching worst-case upper and lower bounds up to logarithmic factors. Experiments on two control tasks and synthetic instances show that prioritization can reduce completion cost, with gains depending on the composition of the policy library.

Critical strengths

The paper clearly formulates the problem and provides a solid and comprehensive theoretical analysis. The experimental evaluation is extensive, and the authors openly report unsuccessful runs and settings in which the method offers limited gains.

Critical weaknesses

The paper assumes a preference ranking that is fixed before online data collection. In practice, safely and accurately evaluating a policy’s true performance may be no easier than assessing its catastrophe risk. Establishing a meaningful uniform utility-error bound, as required by Corollary A.4, may also be challenging in practice. Freezing empirical scores does not establish that their ranking reflects true expected returns; without such an error bound, the theoretical results do not provide a corresponding guarantee on the selected policy’s true expected return. This issue is particularly salient in the experimental protocol: before online data collection, each policy undergoes 2,000 pilot episodes and 10,000 development episodes. Since data collection during these preparatory evaluations falls outside the stated online guarantee, how is safety controlled at this stage? Furthermore, if these trajectories contain the cost observations needed to determine catastrophe indicators, they should also provide information about candidate-policy risks. Retaining the estimated utility ranking while initializing candidate risk certificates from scratch, without using any pre-online risk evidence, is therefore difficult to justify.

Questions for authors

How should the margin η\eta be chosen for a new policy library before online collection? Its effect on completion time and recommendation quality may differ substantially across policy libraries, while the relevant risks are initially unknown. Appendix B.5 illustrates the trade-off, but I am still unsure how to make this choice in practice. When online evaluations are costly and may themselves cause safety violations, repeatedly running the procedure with different margins may not be feasible.

4 comments
AuthorsOpenReview ↗

Response to reviewer on return quality, safe preparation and evidence reuse

We sincerely thank the reviewer for the questions about return accuracy, preparation safety and reuse of existing risk evidence.

1. Frozen scores and expected returns

JACE's online guarantee concerns frozen scores. For expected returns, submitted Corollary A.4 adds at most 2ζ2\zeta when every policy's score error is simultaneously bounded by ζ\zeta. We also assessed the fixed CarPush1 output c40_BC-safe directly, without requiring the full library's expected-return ranking to be correct.

Using the same 1,716,537 supplemental episodes, the sequential procedure specified before collection gave loss upper bounds of 0.011480 against the best of the baseline and policies with risk at most 0.18, and 0.308232 against all policies with risk at most 0.20. The latter bound reflects the unresolved risk of c80_BC-safe. We designed a terminal test after inspecting those results on the same data. Its results are exploratory. Proposition B.7 protects selection between fixed assessment rules, but does not establish validity for this data-dependent construction. We therefore withdraw the joint 0.05 guarantee previously stated for the two 0.01 targets (Appendix B.8, Table 10).

The output, tolerance, quotas and sample order were fixed before supplemental collection. Sample counts depend only on prior history and independent allocation coins. Returns must be bounded and the output and baseline qualified. Conditional on the pilot and frozen policies, policy streams are mutually independent, with i.i.d. episodes under the same law across included stages and machines. Boundary evaluation and fallback mixing account for 70.5% of the added episodes, including 65,237 baseline episodes. The sequential bounds remain reusable for the same output and targets under unchanged laws, charging acquisition once (Appendices B.8 and C.9).

2. Safety during preparation and baseline qualification

The original pilot and development episodes ran in simulation before the online safety guarantee began. Preparation can meet a risk limit β\beta if it starts from a fallback with a valid pre-existing bound β0<β\beta_0<\beta. Drawing an uncertified candidate with probability at most (β−β0)/(1−β0)(\beta-\beta_0)/(1-\beta_0) and the fallback otherwise keeps the mixture's risk before each draw at most β\beta. Our supplemental CarPush1 evaluation used existing risk upper bounds for both policies, allowing a fixed boundary-candidate probability of approximately 0.9462. Each episode used a fresh independent draw, with the fallback selected otherwise. Certified policies were evaluated directly. The safety guarantee accounts for qualification and certificate-coverage errors (Appendix B.7).

On both tasks, the records support pilot selection followed by independent baseline qualification. On PointGoal1, the pilot selected c80_CPQ. Independent assessment gave 1,171 catastrophes in 20,000 episodes and a one-sided risk cap of approximately 0.063855 at error 0.001. An independent holdout under unchanged laws gave an upper endpoint below 0.062750 even at error 0.001/16. In a separate robustness check, replacing only the baseline cap with the more conservative simultaneous bound of 0.065170 for the selected policy gave 40 completed, audited replays with assessment-supported outputs. JACE still saved 36.9% on average over Safe-RR (Proposition B.6, Appendix C.9).

3. Reusing preparation trajectories

We held candidate-risk observations out of the benchmark to compare allocation rules from a common starting point. In deployment, each policy's risk test can continue from its complete observed history under its original error budget. The policies, tests and error allocations must be fixed before the first retained observation, each sampling decision must precede its outcome, and each policy must retain the same i.i.d. episode law across stages, with independent streams across policies. These conditions allow the same episodes to supply reward scores even when risk and reward are dependent (Appendix B.4).

With 10,000 historical observations per policy and ten paired future runs, all four methods completed immediately on PointGoal1. Their costs also coincided on CarPush1, where JACE's mean additional cost fell from 35,351.2 to 15,801.8 episodes with 10/10 declarations. PointGoal1 used an independent holdout and CarPush1 used development trajectories. History was charged separately, and baseline episodes counted toward the 40,000-episode online cap.

We also checked whether the result depended on which history was reused. Across ten disjoint CarPush1 development blocks of 1,000 observations per policy, each paired with one future run, JACE improved over its cold start in every pair. Its mean additional cost was 22,364.9 episodes, with 10/10 assessment-supported declarations (Table 7). The blocks share scores estimated from the full development archive. For the shorter histories where the archive did not contain enough later episodes to finish a replay, Appendix C.8 bounds the missing cost using the 40,000-episode cap.

Q1. How can the margin be chosen for a single deployment?

Choose the margin before collection according to how close to the safety limit the score guarantee must extend. With risk limit β\beta and margin η\eta, one run compares the output with the baseline and all policies whose risk is at most β−η\beta-\eta. If the requirement is a score within a tolerance ϵ\epsilon of the best safe policy, existing evidence determines what can be promised before spending the online budget.

When compatible history is available, first select the highest-scoring policy certified safe by simultaneous risk intervals for the full library, including the qualified baseline. Subtract its score from the highest score still compatible with safety. The difference bounds the selected policy's loss against the best safe policy. If no policy qualifies, we withhold certification. On CarPush1, 320,000 existing assessment episodes put this bound below 0.008674. This meets a 0.01 frozen-score target with no additional collection and joint error at most 0.005. Historical acquisition is counted once.

For a cold start, suppose external evidence establishes that every safe policy scoring more than ϵ\epsilon above the baseline has risk at least Δ>0\Delta>0 below the limit. Choose 0<η≤Δ0<\eta\le\Delta satisfying the certificate resolution conditions. Exact completion then meets the score target on joint coverage. With a qualified baseline and independent policy streams having unchanged i.i.d. laws, Corollary 4.2 bounds expected cost by MM. Require ⌈M/κ⌉\lceil M/\kappa\rceil to fit the remaining budget for a deadline-error allowance 0<κ<10<\kappa<1. Joint error is at most δ+κ\delta+\kappa, where δ\delta covers safety and valid completion. At η=0.02\eta=0.02, this generic MM exceeds 101010^{10} episodes on both tasks and is too loose for deployment planning. The smaller deadlines in Table 9 use independent planning data. An estimated gap needs its own error allowance. Without evidence separating risks near the limit, no finite deadline guarantees this quality uniformly (Appendix B.6).

If a fresh run is required despite existing history, its own output must meet the target. At margin 0.02, the sufficient online deadline and frozen-score loss bound are 37,716 episodes and 0 on PointGoal1, and 124,031 episodes and 0.3001 on CarPush1. The latter calculation does not certify 0.01 within 40,000 episodes. The total budget must also cover new preparation and reserved validation (Table 9). On the same evidence, the direct historical quality check is at least as tight as the fresh-run bound.

For this calculation we use planning data to select from a predefined finite list and fix the configuration before independent fresh sampling. Proposition B.5 requires fixed policies and scores, simultaneous planning coverage, baseline qualification valid after selection, and independent policy streams with unchanged i.i.d. laws. Planning error 0.005, conditional deadline error 0.045 and the original joint error allowance of 0.05, including baseline qualification, bound the unconditional probability of issuing and violating a promise by 0.10. A prospective expected-return promise also needs return evidence whose acquisition cost and uncertainty fit the budget and loss tolerance.

If the run reaches the cap, its observed risk bounds still give an answer about a smaller comparison set. On joint coverage the certified incumbent remains safe. If every higher-scoring candidate's risk lower bound strictly exceeds qq, the incumbent matches or exceeds every policy with risk at most qq. All three CarPush1 runs capped at 40,000 episodes passed this check at 0.168, below the original comparison threshold of 0.180. This uses the same run and requires no sweep over margins.

Thank you for the detailed response and additional experiments. Your response addresses most of my concerns. I will maintain my score of 3.

Thank you for your reply and for your positive assessment. Your comments on true expected returns, preparation safety, reuse of pre-online risk evidence and the choice of margin helped us improve the paper.

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

This paper studies safe selection from a fixed library of KK candidate policies and a known-safe baseline. Each policy has a frozen utility score and an unknown per-episode catastrophe probability. During data collection, at every time step, the learner must choose sampling mixtures whose risk remains below a prescribed threshold β\beta. The final recommendation should also be safe. They propose the algorithm JACE, which constructs time-uniform Bernoulli risk certificates. It mixes a candidate with the baseline at the largest weight allowed by the certificates. It maintains small sampling floors for other active candidates basically for exploration. It stops when every candidate with higher utility than the incumbent is ruled out as sufficiently safe relative to a margin η\eta. This margin permits the algorithm to ignore candidates close to the safety threshold.

The theoretical analysis establishes collection and deployment safety. They also establish bounds on expected completion cost by separating evidence acquisition from safety-induced waiting. Finally, they provide a lower bound with matching worst-case scaling up to logarithmic factors. They experiment on Safety-Gymnasium tasks with 16 offline-RL policies to validate their claim.

Critical strengths

The paper has the following strengths:

  1. The paper made a useful distinction between certification and completion. It makes sure that it finds a safe policy as its final recommendation before deciding that no sufficiently better policy is being missed. I feel that the margin-based comparison criterion is quite common in this type of safe policy paper. Still, the margin-based comparison criterion makes completion well-defined.

  2. The theoretical analysis prima facie looks correct. I have not gone deep into the proofs to verify the claims. The safety argument is nice, and they avoid a union bound over the grid. The lower-bound derivation appears consistent with the stated KL arguments.

  3. The empirical results are fine. The results make clear that the distinction between finding a safe policy and completing the identification task can affect sample costs significantly.

  4. The paper explicitly acknowledges that its margin does not bound utility loss relative to the best safe policy.

Critical weaknesses

The paper has the following weaknesses:

  1. The upper bound in Theorem 4.1 and the lower bound in Theorem 4.3 may be quite far apart. The lower bound applies to a broad class of priority rules that retain the same certificates, filters, and sampling floors. Also, the theory does not explain why JACE’s evidence-based priority should outperform JACE-UCB.

  2. There is a tension in the cost-utility trade-off. The margin can permit substantial utility loss, while reducing it can make completion very expensive. The authors briefly delve into this in Appendix B.5.

  3. In the three unfinished CarPush1 runs, the unresolved competitor has a frozen-utility advantage of 0.0087 over the certified output. Its estimated risk is 0.2008, just above the threshold β=0.20\beta=0.20. Note that the difference is negligible. I think the objective does not accommodate utility indifference, potentially forcing expensive resolution of negligible differences.

  4. In what deployment scenario are utility scores available while risk estimates remain unknown, and how much of the reported online cost could be avoided by reusing historical risk data?

  5. The paper explains that η\eta must be fixed before collection, but there is no guarantee for selecting it given a desired utility-loss tolerance or a finite collection budget.

Questions for authors

Here are the questions for the authors. If they are addressed, I am willing to raise my score.

  1. Since the upper and lower bounds apply to any predictable priority rule within the specified class, what theoretical guarantee distinguishes JACE from JACE-UCB or Safe-RR? Can the authors derive an instance-dependent bound?

  2. At η=0.02\eta=0.02, Appendix B.5 reports a mean declaration loss of 0.368 relative to the best safe policy. Smaller tested margins have low completion rates, and the added candidate with risk 0.145 enters the comparison class only at η=0.004\eta=0.004. How to choose η\eta more methodically/principally given a target utility-loss tolerance and a finite data-collection budget?

  3. Could the completion objective include a utility-indifference parameter so that candidates within the parameter of the incumbent need not be resolved? I guess this would change Theorems 4.1 and 4.3, but might help to resolve some of the experiments.

  4. In what realistic setting are utilities known but risks unknown, given that the experimental pipeline runs every policy, including unsafe ones, during preparation? How much could reusing historical risk data reduce online collection cost?

6 comments
AuthorsOpenReview ↗

Response to reviewer on evidence ordering and budget–quality guarantees

We sincerely thank the reviewer for asking what the priority rule itself contributes. We have added a rule-dependent bound for general instances and an example where the choice of rule changes how expected completion cost grows with the number of candidates.

W1 + Q1. When does evidence ordering reduce completion cost?

Submitted Theorem 4.1 already accounts for each candidate's risk gap and variance, but it gives the same guarantee whichever eligible candidate receives priority. Proposition B.1 makes that distinction explicit. Consider a candidate after nn observations on its own stream. An alternative whose risk is at least the prescribed margin below the safety limit and whose score, fixed before collection, is at least as high can prevent that candidate from receiving priority. Given the candidate's local evidence, Proposition B.1 uses these alternatives to upper-bound the probability that the candidate is actually drawn as the priority before completion while its count is still nn. The resulting bound on expected cost includes paths on which certificates fail (Appendix B.1).

On the following family, revised Theorem 4.3 shows that JACE has lower-order expected completion cost than both JACE-UCB with ties broken by index and Safe-RR with priority rotated by round. Among KK candidates, the safe target has risk 0 and score 2 and occupies a uniformly random position. Each other candidate has risk 1 and score 1. The baseline has risk, certified risk cap and score zero. All three rules use the same certificates, risk limit 0.20, margin 0.10, exploration parameter 0.10 and error budget 0.05. Writing TT for episodes until completion, including baseline episodes, we obtain

\mathbb E T_{\rm UCB}=\Theta(K\log K),\qquad \mathbb E T_{\rm RR}=\Theta(K\log K).$$ On this family, one catastrophe puts an unsafe candidate below every unobserved candidate in JACE's evidence ranking. Each unsafe candidate therefore uses at most one priority execution before the target receives the $\Theta(\log K)$ observations needed for certification. The priority candidate has a probability bounded away from zero of being drawn each round. With JACE-UCB, an earlier unsafe candidate can stay tied with the target at a risk lower bound of zero for $\Theta(\log K)$ observations when ties are broken by index. Safe-RR instead rotates priority across candidates by round. Both comparisons allow for early certification through ordinary exploration (Appendix B.2). The information-theoretic lower bound (submitted Theorem 4.3, now 4.4) concerns any jointly safe and correct method starting with the same information. It matches the upper bound up to logarithmic factors in the stated worst-case parameter range. The table counts the 48 synthetic settings in which JACE had a lower, equal or higher mean cost over 50 paired seeds. These settings span risks at 0 or 1 and risks between those endpoints. Figure 9 gives the means and Appendix C.7 reports the adjusted paired comparisons. | Comparator | JACE lower | Tied | JACE higher | |---|---:|---:|---:| | Safe-RR, Safe-Uniform (each) | 48 | 0 | 0 | | Rotating-tie, random-tie UCB (each) | 48 | 0 | 0 | | Index-tie UCB | 32 | 4 | 12 | | Utility-first UCB | 0 | 4 | 44 | Utility-first UCB benefits here because the highest-scoring candidate is the safe target. PointGoal1 illustrates why we separate the two decisions. All six policies scoring above the selected policy have independent risk intervals above the safety limit (Table 3). Scores tell us which improvements are worth pursuing, while risk evidence helps decide where to spend the next certification episode. Table 1 reports the matched comparison with index-tie UCB, and Appendix B.3 gives a family favoring that rule.

W2 + W5 + Q2. How should we choose the margin for a given quality target and budget?

The margin fixes the risk range of the score guarantee, not the size of the omitted score advantage. In the submitted boundary test, the risk-0.145 candidate enters the comparison set only for margins at most 0.005 under safety limit 0.15. At margin 0.02, the mean full-safe score loss among declared runs was 0.368. We therefore start from a frozen-score tolerance and collection budget.

First check existing evidence. Using simultaneous risk intervals for the full library, including the baseline, choose the highest-scoring policy whose upper risk bound meets the safety limit. Subtract its score from the highest score among policies whose lower risk bound meets that limit. On joint coverage, this bounds its loss against the best safe policy. Certify only if a policy qualifies and the bound meets the tolerance. On CarPush1, 320,000 assessment episodes held out of the online comparison give c40_BC-safe a bound below 0.008674, meeting 0.01 with no new collection and joint safety or score error at most 0.005. Reuse requires coverage for the same policies' deployment risks, including the baseline. We count historical acquisition once (Proposition B.2, Appendix C.8).

For a new run, check quality and budget together. Suppose external evidence gives a risk gap Δ>0\Delta>0 below the limit for every safe policy scoring more than ϵ\epsilon above the baseline. Choose 0<η≤Δ0<\eta\le\Delta satisfying the certificate resolution conditions. Under the paper's baseline and independent i.i.d. stream assumptions, exact completion gives score loss at most ϵ\epsilon on joint coverage. Corollary 4.2 bounds expected cost by MM, so requiring ⌈M/κ⌉\lceil M/\kappa\rceil to fit the budget gives joint error at most δ+κ\delta+\kappa, where δ\delta covers safety and valid completion and 0<κ<10<\kappa<1 is the deadline allowance. Estimated gaps need a separate error allowance. This generic bound is too loose for practical planning. Table 9 uses independent planning data. Without risk separation, no uniform finite deadline guarantees this quality (Appendix B.6).

With historical planning data, Proposition B.5 also gives a score-loss bound for a separately requested fresh run. Subtract the highest score certified safe by the chosen margin from the highest score still compatible with safety, including the qualified baseline in both sets. This bound plus any allowed score tolerance at stopping must meet the target. The direct historical check is at least as tight on the same data.

Task at margin 0.02Sufficient online episodesScore-loss bound against the best safe policy
PointGoal137,7160
CarPush1124,0310.3001

For PointGoal1, both the 40,000-episode online budget and the 0.01 score target pass this check. For CarPush1, the available bound does not establish either requirement at this margin (Table 9). We use the planning data to choose a configuration from a predefined finite list. We then fix that choice and draw fresh episodes independently of the planning data. Policies and scores are fixed, planning intervals must cover simultaneously, and baseline qualification must remain valid after selection. Policy streams are independent, and each retains the same i.i.d. episode law across stages. With error allowances of 0.005 for planning, 0.045 for the deadline conditional on valid planning information and 0.05 for safety and valid completion, the unconditional probability of issuing a promise and violating it is at most 0.10. The total budget must also cover new preparation and reserved validation, counting shared episodes once.

At the budget cap, report the comparison the data support. If every higher-scoring candidate has an online risk lower bound strictly above qq, the certified incumbent matches or exceeds every policy with risk at most qq on joint coverage. Three CarPush1 runs reached 40,000 episodes at the original target q=0.180q=0.180. All three passed this check at q=0.168q=0.168 (margin 0.032), and only one passed at q=0.170q=0.170.

These guarantees concern frozen scores. For expected returns, twice a simultaneous score-error bound must fit the loss tolerance, with its own error allowance, or the output can be assessed directly. Using 1,716,537 supplemental CarPush1 episodes, the sequential analysis specified before collection gave loss bounds of 0.011480 (margin) and 0.308232 (full-safe). The terminal analysis developed after inspecting these results is exploratory and does not establish a joint 0.05 certificate of both 0.01 targets (Appendix B.8).

W3 + Q3. Can JACE stop when the remaining score difference is negligible?

Yes. Proposition B.3 lets the practitioner specify a frozen-score tolerance ϵ\epsilon before collection. JACE keeps its sampling rule and can stop once every candidate scoring more than ϵ\epsilon above the best certified policy has an online risk lower bound above the comparison threshold β−η\beta-\eta. On the original joint coverage event, the output is safe, its score is at least the baseline score, and it is within ϵ\epsilon of the best score among the baseline and margin-safe policies. The relaxed rule stops no later than exact completion on every trajectory, so Theorem 4.1 still bounds expected cost. On the lower-bound family, where the score gap is one, the lower bound (now Theorem 4.4) still applies for ϵ<1\epsilon<1 (Appendix B.4).

The CarPush1 example in the review explains why this change matters. The frozen score of c80_BC-safe exceeds the incumbent's by only 0.0087. Its risk estimate of 0.2008 came from independent assessment, whereas online risk exclusion requires the candidate's online lower confidence bound to exceed 0.18. At a score tolerance of 0.01, this candidate no longer blocks completion. Replaying all 80 control trajectories at that tolerance raised CarPush1/JACE declarations from 7/10 to 9/10 and reduced mean capped cost by 6.6%, from 35,351.2 to 33,002.4 episodes. All nine outputs scored 2.8004 and had independent assessment support.

In the remaining run, a different candidate, c20_BEARL, scored 3.1096. Its advantage of 0.3092 over the incumbent exceeded the tolerance, and its online risk lower bound was only 0.174 at the cap. Tolerances of 0.0025 and 0.005 gave the same mean cost as exact completion. Tolerances of 0.02 and 0.05 gave the same mean cost as 0.01. PointGoal1 was unchanged across these tolerances (Appendix C.8).

W4 + Q4. When are scores available first, and how much does reusing risk data save?

A deployment team can rank controllers by a known engineering cost, such as memory footprint, before measuring their failure probabilities in the field. In our control experiments, the scores came from empirical returns. We used preparation to fix those scores and qualify the baseline, then held out candidate-risk observations so all four allocation rules began with the same baseline certificate. In deployment those observations can be reused.

With one history of 10,000 observations per policy and ten paired future runs, all four methods completed immediately on PointGoal1. On CarPush1, JACE's mean additional cost fell by 55.3%, from 35,351.2 to 15,801.8 episodes. All four methods then had the same costs and completed 10/10. These runs excluded the independent assessment data from initialization. With ten disjoint histories of 1,000 observations per policy, CarPush1/JACE averaged 22,364.9 additional episodes and again completed 10/10. The frozen scores use the full development archive, so this comparison measures sensitivity to the choice of history. Appendix C.8 reports the fully observed settings in Table 7 and bounds costs for the shorter histories where the archive ended before replay could finish.

Valid reuse continues each policy's risk test from its full sequence of observed outcomes, preserving the test statistic, rejected thresholds, sample count and original error budget. The policies, tests and error allocations are fixed before the first retained observation, sampling decisions precede their outcomes, and the independent policy streams retain their i.i.d. episode laws across stages. Simultaneous coverage allows rewards from the same episodes to determine scores even when reward and risk are dependent (Appendix B.4).

The original preparation ran in simulation before the online guarantee began. The supplemental CarPush1 evaluation used a qualified fallback to control collection risk. On PointGoal1, charging all 512,000 shared preparation episodes reduced JACE's roughly 37% online saving over Safe-RR to 0.62% for one deployment. Records support pilot selection followed by independent qualification. In 40 audited replays with a more conservative baseline risk cap, JACE still saved 36.9% of online episodes on average over Safe-RR (Appendices B.7 and C.8–C.9).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.