Optimal Decision-Making Based on Prediction Sets

Tao Wang, Edgar Dobriban

Machine learning models are increasingly deployed in high-stakes domains like medical diagnosis and autonomous driving. To manage uncertainty, practitioners often rely on Conformal Prediction, which outputs a "prediction set"—a list of possible outcomes guaranteed to contain the ground truth with a user-specified probability (e.g., 95%).

However, a set of possibilities is not an actionable decision. If a model outputs a prediction set containing both "Normal" and "Pneumonia," how should a clinician proceed? This paper bridges the gap between distribution-free uncertainty sets and classical decision theory, providing a provably robust way to turn machine learning predictions into safe actions.

The Flaw in Standard Max-Min Strategies

A standard approach to decision-making under uncertainty is the "max-min" strategy: choosing the action that minimizes the loss for the worst-case outcome inside the prediction set.

The authors identify a critical vulnerability in this logic: it completely ignores the remaining 5% (the error budget, $\alpha$) where the true outcome falls outside the set. In high-stakes environments, being wrong in this 5% tail can lead to catastrophic consequences. Standard methods lack the incentive to hedge against these rare but severe out-of-set events, making them dangerously optimistic as the error budget grows.

Methodology: Risk-Optimal Conformal Prediction (ROCP)

To address this vulnerability, the authors introduce Risk-Optimal Conformal Prediction (ROCP). They frame the problem as a two-player minimax game between a decision-maker and "nature." Nature selects a distribution that maximizes expected loss while remaining consistent with the prediction set's coverage guarantee.

  1. The Optimal Policy: The authors derive a closed-form expression for "robust risk." The optimal action balances the worst-case loss inside the prediction set with a penalty for the worst-case loss outside the set, weighted by the error budget ($\alpha$).
  2. Optimal Set Design: Rather than treating the prediction set as a fixed prior, the framework uses Fenchel-Rockafellar duality to determine how to construct the prediction set itself to minimize this robust risk.
  3. The ROCP Algorithm: ROCP translates this theory into practice. It uses a black-box model to estimate potential losses and leverages a small calibration dataset to find a single scalar parameter ($\beta$). This one-dimensional search ensures the final sets meet the required coverage guarantee while remaining computationally efficient.

Key Insights

  • The "Tail" Matters: The robust loss formula explicitly forces the decision-maker to account for the unconstrained mass outside the prediction set: $L \approx (\text{In-set Loss}) + \alpha \times (\text{Out-of-set Penalty})$.
  • Brittleness of Max-Min: Pure max-min rules assume the truth must be in the set. As $\alpha$ increases, this assumption breaks down, leading to spikes in critical mistakes.
  • Model Agnosticism: ROCP works with any underlying ML model. Even if the base model's probability estimates are imperfect, the conformal calibration step ensures the $1-\alpha$ safety guarantee strictly holds.

Empirical Results

The researchers evaluated ROCP on two high-stakes benchmarks:

  • Medical Diagnosis (COVID-19 Radiography Database): In a simulated treatment task where missing a pathological condition carries a heavy penalty, ROCP almost entirely eliminated critical mistakes (e.g., taking "No Action" for a patient with COVID-19). In contrast, standard baselines suffered mistake rates of 10-30% as the error budget increased.
  • Autonomous Driving (BDD100K): In a toy hazard-detection task requiring stop/turn/go decisions, ROCP remained stable and safe even with non-negligible miscoverage probabilities. Competing baselines, such as Risk-Averse Calibration (RAC), deteriorated sharply under the same conditions.

Limitations and Future Directions

While ROCP provides robust, distribution-free coverage guarantees, the efficiency (size and shape) of the prediction sets still depends on the underlying model's quality. Poor base models will yield unnecessarily large sets.

Currently, the ROCP algorithm is tailored for discrete outcome spaces (classification). Extending it to continuous spaces (regression) will require new computational approaches for conformalization. Finally, future iterations could incorporate group-conditional guarantees, ensuring equitable safety across different subpopulations rather than relying solely on marginal, dataset-wide averages.

Summary updated

Abstract

Prediction sets can wrap around any ML model to cover unknown test outcomes with a guaranteed probability. Yet, it remains unclear how to use them optimally for downstream decision-making. Here, we propose a decision-theoretic framework that seeks to minimize the expected loss (risk) against a worst-case distribution consistent with the prediction set's coverage guarantee. We first characterize the minimax optimal policy for a fixed prediction set, showing that it balances the worst-case loss inside the set with a penalty for potential losses outside the set. Building on this, we derive the optimal prediction set construction that minimizes the resulting robust risk subject to a coverage constraint. Finally, we introduce Risk-Optimal Conformal Prediction (ROCP), a practical algorithm that targets these risk-minimizing sets while maintaining finite-sample distribution-free marginal coverage. Empirical evaluations on medical diagnosis and a toy static hazard-decision benchmark demonstrate that ROCP reduces critical mistakes compared to baselines, particularly when out-of-set errors are costly. The source code to reproduce our experiments is available at https://github.com/TaoWangPenn/Risk-Optimal-Conformal-Prediction.
BibTeX
@inproceedings{wang2026optimal,
  author = {Tao Wang and Edgar Dobriban},
  title = {{Optimal Decision-Making Based on Prediction Sets}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=VAXW59dyfk},
}
Figure