Choosing a few robust algorithms or schedules often requires evaluating every candidate under many adverse scenarios, even though an agent only needs to identify the winners. A predictor can suggest likely winners but cannot rule out surprises in unevaluated scenarios. We introduce Certified Adaptive Selection (CAS), which returns the exact top‑$k$ set as soon as the remaining uncertainty cannot alter it. CAS maintains provable lower and upper bounds on Expected Shortfall (ES), the average loss in the worst scenarios. The stopping test compares the worst admissible selected candidate with the best admissible excluded one; for information‑disjoint Cartesian intervals this one‑cut test is both necessary and sufficient. Prediction plays a separate role: it selects the next outcome to evaluate and never authorizes the decision itself. For unit‑cost exact ES queries we compute in polynomial time the fewest evaluations that could have proved the realized decision in hindsight. The prediction‑guided agent CAS‑PG is exact for any predictor, including adversarial ones. On two public algorithm‑selection matrices, CAS‑PG certifies the exact top three after 630 of 3150 and 981 of 2200 replayed queries, i.e., $1.14$ and $1.18$ times the hindsight minimum. Its transcript‑only variant, without historical outcomes, needs $1.28$ and $1.37$ times the minimum, still outperforming tested non‑predictive certified policies. Separately, a prediction‑free CAS policy avoids $93.0\%$ of exact recourse solves in synthetic energy scheduling. One certificate thus supports several acquisition policies and independently proved risk/cost extensions: prediction changes the work, not the justified choice.
Review