Search or Refresh? Candidate-Exposure Certificates for Offline Policy Extraction

Increasing action-search computation changes the continuation policy that an offline critic must evaluate. We study which unresolved rankings matter for this change through candidate exposure: an error affects selection only when competing actions appear together without being screened by a higher-ranked candidate. We derive an interval envelope, relate it to fixed-vector robust regret within a factor of four, and obtain equality for two supported actions. We provide a certified threshold approximation for larger candidate budgets, while using an exact near-linear algorithm for two draws. An exact moment-tree alternative is near-linear in action count at fixed budget. Model confidence sets built from trajectories support adaptive stopping and policy replacement. Our replacement test lower-bounds shared-model baseline regret and is exact for a common uncertain prefix followed by a known suffix. A stepwise analysis separates marginal-value uncertainty, residual inflation, visitation bounds, and numerical approximation. A certificate-matched study charges every schedule for final verification and uses identical sequential replacement gates. Across 192 trajectory datasets, exposure and robust root-value checks have complementary yields; fixed-episode confidence improves graph certification but does not establish broad computational superiority. The results identify what decision-sensitive certification adds, what it costs, and where its uncertainty relaxations lose useful information.