Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents

We thank the reviewer for their valuable feedback and thoughtful questions, which will help us significantly improve the clarity and contribution of our manuscript.

Question 1: Our contributions are twofold, as outlined below: (1) we introduce a novel question within the conformal prediction literature, and (2) we develop mathematical techniques to provide meaningful answers.

Regarding the novel question: Despite extensive literature on conformal prediction (CP) as uncertainty quantification beneficial for downstream decisions, little was previously known about whether prediction sets are the ideal means to communicate uncertainty within decision-making pipelines and how decisions should optimally incorporate them. We hope our findings bring new insights to the community in this regard.

Regarding mathematical and technical contributions: A key contribution is deriving an explicit solution to RA-CPO (Section 2.2), accomplished in Proposition 3.1 and Theorem 3.2. To highlight the challenges, note that RA-CPO is a non-convex optimization over the set function $C(.)$, lying outside conventional duality-based analysis. We first reparametrize RA-CPO equivalently (Eq. 12), maintaining non-convexity. Next, in the proof of Theorem 3.2, through another reparametrization to a mixed-integer program, followed by a convex relaxation over function spaces, we use a key technical lemma (Lemma B.1, Appendix) to show this relaxation exactly solves RA-CPO. This approach is novel, and we will emphasize these contributions further in the revision.

Additionally, our manuscript includes: Theorem 2.3 (prediction sets as sufficient statistics), Proposition 2.2 (optimality of max-min decision rule given marginally valid sets), and Theorem 4.1 (finite-sample statistical validity of our algorithm).

Question 2: This is an excellent point. Two distinct estimation steps exist in the finite-sample algorithm: calibration-data-based and model-output-based (softmax probabilities). The only parameter influenced by calibration data (thus sensitive to sample size $n$) is the scalar parameter $\beta$. Similar to standard CP, the sensitivity to $n$ is minimal, stabilizing once $n$ reaches a few thousand samples. Under mild smoothness conditions on the conditional distribution of $Y|X$, finite-sample upper bounds scale as $1 - \alpha + O(1/n)$ (Theorem 4.1), a standard assumption in CP literature.

Remaining computations, notably quantiles (Eq. 15), rely solely on softmax probabilities and are independent of calibration data and $n$, preserving statistical guarantees. We will further clarify this point by expanding the paragraph after Corollary 4.2.

Regarding group-conditional validity claims: Although briefly noted in Remark 2.1, our original discussion was limited by space constraints. To clarify: the theoretical results in Sections 2 and 3—such as the characterization of optimal decision rules and prediction sets—extend naturally to the group-conditional setting, resulting in an $m$-dimensional formulation (where $m$ is the number of groups). However, the finite-sample algorithm in Section 4 poses greater challenges, as it requires calibrating an $m$-dimensional vector, which introduces both computational and statistical complexity. In the revised manuscript:

• We have expanded Remark 2.1 to explicitly distinguish between the components that extend systematically and those that present additional challenges.

• We have enhanced the “Future Work” section to outline potential approaches for addressing the difficulties in the finite-sample setting and to motivate further investigation of this important extension.

Regrading bayesian methods: We thank the reviewer for highlighting relevant Bayesian literature. We emphasize our approach is complementary—not competitive—with Bayesian methods:

Main theoretical contributions up to Section 3 (two-thirds of the paper) remain neutral regarding Bayesian or frequentist approaches, focusing instead on general roles of prediction sets in risk-averse decision-making. The equivalence formulation (Theorem 2.3) and optimal prediction set characterization (Theorem 3.2) assume complete knowledge of underlying distributions, applicable equally to Bayesian posterior distributions (e.g., from Gaussian Processes).

In scenarios where Bayesian models (e.g., Gaussian Processes) approximate the distributions well enough, one can directly use our theoretical results without employing the finite-sample calibration of Section 4. Alternatively, even when Bayesian assumptions' precision is uncertain, one can still start from Bayesian posteriors and further calibrate prediction sets using our approach, ensuring robust safety guarantees.

We will explicitly clarify these points in the revised manuscript, along with a discussion about the existing bayesian approaches, including the ones suggested by the reviewer.

We sincerely thank the reviewer for their careful and detailed evaluation, their supportive stance toward our work, and their insightful and constructive questions, which allow us to clarify and deepen our results significantly.

Questions 1, 3, and 4: Thank you for these great questions! As the reviewer rightly points out, the most practically meaningful objective is the per-instance optimization (Eq. 2), which ensures optimal value-at-risk guarantees conditional on each individual instance $x$. However, there are two main considerations justifying our chosen marginal approach (RA-DPO):

Distribution-free, finite-sample methods generally cannot produce simultaneous per-$x$ guarantees without additional assumptions. Hence, some form of marginalization is inevitable. Our specific choice, $E[\nu(X)]$, is indeed a deliberate choice we made, as there is no canonical choice and we had to fix an objective. We also agree with your observation that marginal guarantees might indeed result in uneven coverage across individual instances. To address precisely this issue, we included Remark 2.1, pointing toward extensions involving group-conditional guarantees, where validity can be enforced within predefined groups of covariates (e.g., patient demographics). Such group-based guarantees enable practitioners to ensure that important covariate subgroups retain meaningful coverage\risk. In the revised version, we will:

1. Extend Remark 2.1 to clearly show which parts of our theory can be systematically extended to group-conditional scenarios and which present challenges.

2. Expand our "Future Work" section to highlight that while Sections 2 and 3 extend naturally to $m$-groups setting (yielding an m-dimensional characterization), the finite-sample algorithm in Section 4 faces additional challenges due to the complexity of calibrating an m-dimensional vector (along with potential approaches to address these challenges).

It is also worth mentioning that moving to group-conditional guarantees, also makes our framework less sensitive to the choice of $E[\nu(X)]$, as eventually in the fully conditional setup, the problem reduces to per-x problems.

We will explicitly clarify these points, naming the deliberate choice of $E[\nu(X)]$ compared to alternatives and the important role of group conditional guarantees for a more meaningful decision making pipeline, in Section 2 of our revised version.

Question 2: To clarify, we focus on deterministic prediction sets in this paper, meaning a deterministic map from X to sets. Also in CP, prediction sets are deterministic when calibration data is fixed (which is the case in practice). Although, due to their mathematical convenience, the CP guarantees are usually formulated as an expectation over calibration data (similar to our Theorem 4.1), but one can also derive PAC guarantees for the same algorithm, which provides coverage guarantees conditional on the calibration data. We will discuss this important matter in the revised version.

Question 5: Thank you for highlighting this important practical question. Indeed, in Section 4, our current algorithm assumes a predictive model providing softmax probabilities, implicitly targeting classification tasks. Several promising approaches can be adopted in practice:

As you suggest, one natural approach would involve training separate quantile-prediction models for each action and then choosing among them. Alternatively, a single regression model predicting the maximum quantile over all actions (as defined in Eq. 9) could also be learned directly. Both of these are similar ideas to Conformalized Quantile Regression (CQR). Other methods, such as regression-diffusion models that generate multiple samples per instance, could also approximate the quantiles in Eq. 9. We will leverage the additional two pages allowed to discuss explicitly these practical regression approaches and provide guidelines for practitioners.

Thanks again for providing an interesting approach for handling regression.

Question 6: We are grateful for bringing up this valuable literature. We see selection conditional conformal prediction as a complementary line of works to ours.

In the revised version, we will include a paragraph discussing this direction including the works you pointed out ([1-4]). Briefly, selective inference addresses scenarios where multiple prediction sets are constructed, and one selects a subset of these sets (e.g. choosing proteins with high predicted affinity), which then creates selection bias that one has to account for. In contrast, our current formulation constructs a single prediction set per instance $x$, with the action directly derived via a max-min strategy from that set, thereby avoiding selection bias.

An interesting future work could be to look at the intersection of these works where one might want to select a subset of actions, while both remaining statistically valid and optimizing for a form of value at risk.

We sincerely thank the reviewer for their insightful comments, constructive feedback, and positive evaluations of our paper.

On the motivation for minimax optimality: This is an important point, and we appreciate the opportunity to clarify our choice. As you correctly pointed out, minimax optimality is indeed not the only conceivable approach. However, our rationale for selecting it is both intuitive and theory-backed, which can be summarized as follows:

1. From an intuitive standpoint, minimax optimality aligns well with the perspective of a risk-averse decision maker. Specifically, the set $\Omega$ captures all plausible scenarios faced by the decision maker, and a risk-averse agent would reasonably seek actions that are robustly optimal in the worst-case realization among these scenarios. This conservative stance naturally leads to the adoption of a minimax criterion.

2. Perhaps a more complete picture emerges by looking at Theorem 2.3. There we prove the max-min rule (introduced in Section 2.1), combined with optimized prediction sets, matches the optimal solution to the risk-averse decision problem (RA-DPO). In light of that, the minimax optimality of the max-min rule (proved in Proposition 2.2) states that for any fixed marginally valid prediction set, even if the prediction sets are not optimally derived, the max-min rule is still a natural choice. This is particularly important as in practice, due to the limitations of finite sample data, we can only have "approximately" optimal prediction sets.

Nevertheless, we fully acknowledge your remark that alternative decision-theoretic approaches (such as those discussed in the paper you mentioned, which we will cite in the revised version) are also valuable and potentially yield interesting complementary results. We will incorporate a remark explicitly addressing this.

On the comment regarding improvements in presentation: We completely agree that the clarity and intuitive presentation of our results could significantly benefit from additional explanations. Indeed, this has largely been limited by the strict page constraints. To address this, we will leverage the two extra pages allowed for the revised version to provide detailed intuition and clearer explanations, especially regarding:

1. The duality derivations and additional implications arising in Section 3.

2. Intuitive justification and step-by-step reasoning behind Algorithm 1 in Section 4.

Regarding Algorithm 1's connection to utility, the utility function enters through the definition of $\hat{C}$ just before Algorithm 1. To summarize the intuition briefly here: Algorithm 1 uses the predictive model to approximate key quantities required for deriving optimal prediction sets, up to a scalar calibration parameter obtained from calibration data. As highlighted in the paragraph following Corollary 4.2, the safety guarantees of actions produced by our framework hold regardless of predictive model quality. Nonetheless, higher-quality models produce actions closer to the optimal choices among the safe ones.

On RAC’s coverage alignment: We believe this phenomenon arises due to finite-sample effects. For instance, in the same Figure 2(d) on the left, one can see that RAC's miscoverage is sometimes better and sometimes worse. Moreover, it is important to emphasize that RAC differs algorithmically from conventional CP methods, which rely primarily on thresholding conformity scores. Consequently, finite-sample behaviors may differ across these approaches. However, as the data size grows sufficiently large, we anticipate these differences will diminish, and coverage behaviors will become comparable across all CP methods, given their common coverage guarantees.

On tuning the miscoverage level $\alpha$: Thank you for this insightful question—this is indeed a critical practical concern. In our framework, the value of $\alpha$ is treated as a given, provided alongside the utility function. Accordingly, RAC takes $\alpha$ as an input. As you pointed out, this value should be selected by the decision maker to reflect their degree of risk aversion, and choosing an appropriate $\alpha$—much like specifying a utility function—can be non-trivial in some applications.

From a practical standpoint, one can evaluate several candidate values of $\alpha$ using validation data, and the decision maker can select the one that offers the best trade-off between risk aversion and utility. This process can involve inspecting plots similar to those presented in our paper. For example, in the context of medical treatment recommendations, one could tune $\alpha$ by jointly examining Figures 2(b) and 2(c), and choosing a value that strikes the desired balance between maximizing average utility and minimizing critically harmful treatment decisions.

We will add a remark in the revised version to clarify this point.

We sincerely thank the reviewer for their detailed and insightful feedback. We are grateful for the positive recognition of our core contributions—especially the novel linkage between prediction sets and risk-averse decision-making. In what follows, we detail the concrete actions we have taken to address the reviewer’s concerns.

References: The reviewer’s comment on expanding the references is extremely valuable. We agree that including prior work from the economics literature on risk aversion is crucial to understanding the challenges and collective effort in risk-sensitive decision making. In the revised version:

1. We have expanded the Related Work section by adding two new paragraphs. One discusses the economics and game theory literature (including all the suggested references) to highlight classical approaches to risk aversion. The other covers additional works, including the ones mentioned by the reviewer, in CP that address decision making beyond risk control.

2. We fully acknowledge that we are by no means claiming to have invented the topic of risk-averse decision-making, but rather are drawing on concepts developed in the economics literature. To better reflect this, we have renamed the section “Fundamentals of Risk-Averse Decision Making” to “Preliminaries of Risk-Averse Decision Making.” In this section, we now include an additional paragraph—along with appropriate citations to the economics literature—that briefly outlines alternative formulations of risk aversion.

We again thank the reviewer for highlighting relevant work from the literature, which has been very helpful in improving our presentation. While space constraints prevent us from discussing detailed connections to these works, we would be happy to explore them further in follow-up rounds.

Marginal and Conditional Objectives: We thank the reviewer for emphasizing this important issue. Although Remark 2.1 highlighted this gap, space constraints limited our discussion in the original submission. In finite sample settings it is impossible to learn an optimal action for every individual scenario without some type of averaging over the covariate space. A common approach in CP is to use group-conditional guarantees, where validity is ensured on average over pre-specified groups (e.g., based on patient age or sex). We have:

1. Extended Remark 2.1 to clearly delineate which parts of our theory can be systematically extended to group-conditional scenarios and which present challenges.

2. Expanded the Future Work section to discuss these issues in detail. Specifically, we explain that while the results in Sections 2 and 3 extend naturally to the group-conditional setting (resulting in an m-dimensional characterization), the finite sample algorithm in Section 4 becomes more challenging due to the need to calibrate an m-dimensional vector.

Conformity Scores and Selection Bias: We appreciate the reviewer’s thoughtful questions on these topics. Regarding the connection to conformity scores, it is crucial to note that our optimal prediction sets are not derived from calibrating a threshold for a conformity score. As shown in Section 3, the optimal sets do not form a nested sequence as the miscoverage threshold varies. In contrast, optimal sets for objectives like minimizing average set size are typically characterized by a threshold rule (e.g., $p(y∣x)≥q$). We will add a remark to clarify this technical difference, which is crucial for deriving optimal actions for risk-averse agents.

We do not suffer from selection bias. We construct one prediction set per test instance and apply the max-min rule directly—rather than selecting among multiple candidate sets. The calibration procedure involves a one-dimensional parameter, $\beta$, which is determined using calibration data to ensure valid coverage (see Theorem 4.1). Although our calibration phase involves computing a quantile for each action (as in eq. (15)), these computations rely on the softmax outputs from the model and remain independent of the calibration data, preserving the statistical guarantees.

Notational Clarity: Note that $\nu$ and $\nu_\alpha$ are distinct: $\nu_\alpha$ is defined in Eq.(2) while $\nu$ is the optimization variable in RA-DPO. In RA-DPO, the decision maker jointly optimizes for a utility certificate ($\nu$) and an action policy ($a$). This distinction clarifies why Theorem 2.3 is non-trivial, as it is not obvious that the optimal utility certificate can be obtained as the max-min value of a prediction set.

Regarding the notations $\theta$ and $\nu_\alpha$, while they are equivalent when $1-t = \alpha$, it is important to note that $t$ and $\alpha$ play different roles. Here, $\alpha$ is the fixed miscoverage threshold (as in standard CP), whereas $t$ is a tunable variable during calibration to ensure that the final prediction sets achieve the desired coverage. We will clarify this point in the revised version to prevent confusion.