Safe Policy Selection: When to Stop and What It Costs

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.