Prediction Sets for Counterfactual Decisions: Coverage, Optimality, and Conformal Prediction

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Prediction Sets for Counterfactual Decisions: Coverage, Optimality, and Conformal Prediction

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Prediction Sets for Counterfactual Decisions: Coverage, Optimality, and Conformal Prediction Yurui Zheng1 and Ying Jin2 1

arXiv:2607.02206v1 [stat.ML] 2 Jul 2026

School of Mathematical Sciences, Peking University Department of Statistics and Data Science, University of Pennsylvania

Abstract Predictions are increasingly used to guide high-stakes decisions, from treatment selection to policy making. To ensure reliability with imperfect predictions, uncertainty quantification methods such as conformal prediction build prediction sets with coverage guarantees. However, statistical validity alone does not immediately determine the decisions to take, nor the optimality thereof. This gap is especially delicate in counterfactual settings where the outcome that materializes depends on the action taken, so uncertainty cannot be specified independently of the decision rule. We develop a decision-theoretic framework for uncertainty-informed counterfactual decisions. We identify a novel notion of policy-coupled coverage—namely, coverage of the realized outcome under the action induced by the prediction sets themselves—as the optimal and lossless interface between uncertainty and action. It plays three roles. First, it justifies acting via a natural max–min rule as minimax-optimal under distributional ambiguity. Second, optimizing prediction sets under policy-coupled coverage is equivalent both to a stronger universal-coverage formulation and to the direct risk-averse optimization over policies and utility certificates; this equivalence yields the explicit form of the population-optimal prediction sets. Third, it admits a two-stage procedure, PolicyCoupled Risk-Averse Conformal Prediction (PC-RACP), that approximates these optimal sets with rigorous finite-sample coverage. Simulations and a real email-marketing experiment confirm that PC-RACP delivers higher utility than existing approaches while maintaining valid coverage, and that ignoring the counterfactual structure of the decision problem is suboptimal for both validity and utility.1 Keywords: Decision theory, uncertainty quantification, conformal prediction, causal inference, counterfactuals

Introduction

1.1

Prediction, uncertainty, and counterfactual decisions

Predictions are often used to guide decisions whose consequences will only be realized after they are made. A physician choosing among treatments, an online platform selecting product recommendations, or a policymaker allocating interventions may rely on predictions to probe the likely outcomes and guide their actions (Manski, 2004; Li et al., 2010; Athey, 2015; Gao et al., 2024; Feuerriegel et al., 2024). Since predictions are inherently imperfect, a critical challenge in highstakes problems is how to act reliably under predictive uncertainty. A natural starting point is to 1

Reproduction code for the experiments can be found in https://github.com/yurui-zheng/PC-RACP.

quantify such uncertainty, for example by building prediction sets—ranges of values the unknown outcome may take—around the predictions. To ensure reliability, an immediate goal is statistical validity. In particular, conformal prediction offers finite-sample coverage guarantees under minimal assumptions, making it an attractive uncertainty quantification framework (Vovk et al., 2005). However, statistical validity alone does not fully address the role of uncertainty quantification in supporting decision-making. Many existing methods do not explain how to derive downstream decisions based on estimated uncertainty. In general, it is not straightforward how validity (e.g., coverage) may translate to guarantees for downstream actions. If the ultimate goal is to make “better” uncertainty-informed decisions, the fundamental question is decision-theoretic: what decisions do uncertainty guarantees justify, what optimality criterion do they correspond to, and when does uncertainty quantification preserve the right amount of information needed for optimal action? These questions have motivated recent work on decision-theoretic foundations of predictive inference in standard prediction problems, where there is a single realized outcome Y ∈ Y to be predicted (Kiyani et al., 2025; Wang and Dobriban, 2026). In that setting, prediction sets C(X) ⊆ Y obeying the usual marginal coverage Pr(Y ∈ C(X)) ≥ 1−α can serve as a lossless interface between uncertainty and decision: for risk-averse agents that maximize a high-probability bound of realized utility, the policy and utility certificate induced by optimally designed prediction sets attain the same value as those obtained by directly optimizing over policies and utility certificates. This picture provides essential insights on the value of prediction sets for decision-making, but a key premise is that the object to be covered is a fixed outcome Y independent of the action taken. Counterfactual decision-making. Many decision-making problems, however, are counterfactual : the outcome that will be realized depends on the action taken. Such a structure is standard in many tasks spanning clinical trials, marketing, and policy-making, captured by the potentialoutcome framework in causal inference and contextual bandits (Rubin, 2005; Imbens and Rubin, 2015). Let A = {a1 , . . . , a|A| } be a finite set of actions. Each action a ∈ A induces a distinct potential outcome Y (a) ∈ Y, and the potential outcomes {Y (a)}a∈A are treated as separate random variables. With the chosen action A, the realized outcome is Y = Y (A). Accordingly, the realized utility is u(A, Y (A)), where the utility function u : A × Y → R describes the value u(a, y) of taking action a ∈ A and observing outcome y ∈ Y. The setting of Kiyani et al. (2025) is the special case where Y (a) ≡ Y for all a ∈ A. In the counterfactual setting, uncertainty can no longer be specified independently of the decision rule since the latter changes the realized outcome. It is therefore unclear what coverage guarantee to begin with, and whether, and how, uncertainty quantification with such coverage connects to optimal counterfactual decisions. This raises the central question of this paper: What is the right interface between uncertainty quantification and counterfactual decisionmaking where actions determine which potential outcome is realized? Several natural validity notions may come to mind. One could require separate (marginal) coverage of every potential outcome, coverage of the realized outcome under every possible policy, or only coverage of the outcome realized under the policy induced by the prediction sets. Our results reveal the role of policy-coupled coverage (formalized in Section 2) as the decisiontheoretically optimal interface. Figure 1 summarizes both the practical deployment pipeline and the theoretical organization of our framework. The top row shows that our practical procedure Policy-Coupled Risk-Averse Conformal Prediction (PC-RACP) produces a collection of prediction 2

Policy-coupled riskaverse calibration

Prediction sets with policy-coupled coverage

PC-RACP

{Ĉ(x, a)}a2A

Set-induced robust actions <latexit sha1_base64="7Np1TLS+efqUXfBt45dUOm1YvOQ=">AAACB3icbVDLSsNAFJ34rPUVdSlIsAh1UxLxBW6q3bisYh/QhDCZTNqhkwczN2IJ2bnxV9y4UMStv+DOv3H6WGjrgQuHc+7l3nu8hDMJpvmtzc0vLC4tF1aKq2vrG5v61nZTxqkgtEFiHou2hyXlLKINYMBpOxEUhx6nLa9fG/qteyoki6M7GCTUCXE3YgEjGJTk6nt2wtzMBvoA2e1lnpdt4sdwYfcwZLX80NVLZsUcwZgl1oSU0AR1V/+y/ZikIY2AcCxlxzITcDIsgBFO86KdSppg0sdd2lE0wiGVTjb6IzcOlOIbQSxURWCM1N8TGQ6lHISe6gwx9OS0NxT/8zopBOdOxqIkBRqR8aIg5QbExjAUw2eCEuADRTARTN1qkB4WmICKrqhCsKZfniXNo4p1Wjm5OS5VryZxFNAu2kdlZKEzVEXXqI4aiKBH9Ixe0Zv2pL1o79rHuHVOm8zsoD/QPn8AKH6Zfw==</latexit>

<latexit sha1_base64="gQbOM4fbhlcmB2MYtW62PVKwFxE=">AAACDHicbVDLSgMxFM34rPVVdekmWIQKUmbE17LajcsK9gGdodxJ0zY0kxmSjFiG+QA3/oobF4q49QPc+Tdm2i609UDgcM655N7jR5wpbdvf1sLi0vLKam4tv76xubVd2NltqDCWhNZJyEPZ8kFRzgSta6Y5bUWSQuBz2vSH1cxv3lOpWCju9CiiXgB9wXqMgDZSp1B0E3cAOqmmpYdjOHLTTgIuE9gNQA8I8OQqTU3KLttj4HniTEkRTVHrFL7cbkjigApNOCjVduxIewlIzQinad6NFY2ADKFP24YKCKjykvExKT40Shf3Qmme0His/p5IIFBqFPgmme2oZr1M/M9rx7p36SVMRLGmgkw+6sUc6xBnzeAuk5RoPjIEiGRmV0wGIIFo01/elODMnjxPGidl57x8dntarFxP68ihfXSASshBF6iCblAN1RFBj+gZvaI368l6sd6tj0l0wZrO7KE/sD5/AKvzm2c=</latexit>

Deployment pipeline:

<latexit sha1_base64="csXuCwGtq/dG2lMUVNvF0+w4F80=">AAAB+XicbVBNS8NAEN34WetX1KOXxSJ4sSQi1WO1F49R7Ae0oWy2m3bpZhN2J8US+k+8eFDEq//Em//GbZuDtj4YeLw3w8y8IBFcg+N8Wyura+sbm4Wt4vbO7t6+fXDY0HGqKKvTWMSqFRDNBJesDhwEayWKkSgQrBkMa1O/OWJK81g+wjhhfkT6koecEjBS17Y7wJ5A08yrnT/c1LxJ1y45ZWcGvEzcnJRQDq9rf3V6MU0jJoEKonXbdRLwM6KAU8EmxU6qWULokPRZ21BJIqb9bHb5BJ8apYfDWJmSgGfq74mMRFqPo8B0RgQGetGbiv957RTCaz/jMkmBSTpfFKYCQ4ynMeAeV4yCGBtCqOLmVkwHRBEKJqyiCcFdfHmZNC7KbqVcub8sVW/zOAroGJ2gM+SiK1RFd8hDdUTRCD2jV/RmZdaL9W59zFtXrHzmCP2B9fkD3DSTKw==</latexit>

⇡RA (·; Ĉ)

Policy-coupled coverage ↝ decision-theoretically optimal interface Theory Roadmap:

Conformal prediction for finite-sample coverage (Section 4)

Optimal prediction sets design (Section 3)

Optimal action under distributional uncertainty (Section 2)

b a)}a∈A with Figure 1: Top: deployment pipeline. PC-RACP constructs action-indexed prediction sets {C(x,

policy-coupled coverage, and acting on these sets via the counterfactual max–min rule yields set-induced riskaverse decisions. Bottom: theory roadmap. Section 2 characterizes the fixed-set robust decision rule under distributional ambiguity, Section 3 studies optimal prediction-set design, and Section 4 gives the conformal procedure for constructing (nearly) optimal prediction sets with finite-sample coverage.

sets satisfying the coverage guarantee, which further induce actions based on the prediction sets. This pipeline is justified by our theoretical components in the bottom row of Figure 1, which we preview in the next and summarize in Figure 2.

1.2

Preview of results

The first challenge in the counterfactual setting is that there is no single unknown outcome to be “covered” in advance. For a decision rule π : X → A mapping from the feature space to the actions, the realized outcome Y (π(X)) is naturally of primary interest, yet its distribution varies with π. Consequently, the first question is what uncertainty object is being constructed and what coverage guarantee it should satisfy. A natural idea is to consider a collection of prediction sets {C(x, a)}a∈A , one per action’s potential outcome. Our first result identifies the validity notion and decision rule that match risk-averse counterfactual decision-making for a fixed collection of prediction sets. Somewhat surprisingly, rather than the widely-studied per-outcome marginal coverage (Lei and Candès, 2021; Jin et al., 2023), a policy-coupled coverage (Section 2.3) over the realized outcome under the max–min rule πRA (x; C) = argmax a∈A

inf

y∈C(x,a)

u(a, y)

achieves the optimal performance under distributional uncertainty. Specifically, for the risk-averse objective in Kiyani et al. (2025), the policy πRA (·; C) maximizes the worst-case objective among all data distributions inducing the policy-coupled coverage of {C(x, a)}a∈A . Thus, policy-coupled coverage is the decision-relevant notion of validity, and πRA (·; C) is the optimal decision rule. Upon establishing the match between coverage and utility objective for a given set of prediction sets, we study optimal design of prediction sets (Section 3). Our second result reveals that optimizing prediction sets under policy-coupled coverage attains the same utility objective as directly optimizing over policies and utility certificates (Theorem 3.1). This establishes prediction sets as a lossless interface for risk-averse counterfactual decision-making, extending the conclusions in Kiyani et al. (2025). Our third result shows that policy-coupled coverage is equivalent in the decision-theoretic sense to universal coverage, i.e., requiring valid coverage for the realized outcome under any policy, although the former is strictly weaker (Theorem 3.2). Such an equivalence enables us to rely on 3

User-facing

Fixed-set robust decision

Coverage

Optimal prediction-set design

<latexit sha1_base64="Fdk5KCAvrDJIotLtB/pU1IdejXg=">AAAB+HicbVDLSgMxFM34rPXRUZdugkVwVWbE17LYjcsK9gHtUDJppg3NJENyR6xDv8SNC0Xc+inu/BvTdhbaeiBwOOfc5OaEieAGPO/bWVldW9/YLGwVt3d290ru/kHTqFRT1qBKKN0OiWGCS9YADoK1E81IHArWCke1qd96YNpwJe9hnLAgJgPJI04JWKnnlrrAHiGrKRsiAzbpuWWv4s2Al4mfkzLKUe+5X92+omnMJFBBjOn4XgJBRjRwKtik2E0NSwgd2cs7lkoSMxNks8Un+MQqfRwpbY8EPFN/T2QkNmYchzYZExiaRW8q/ud1Uoiug4zLJAUm6fyhKBUYFJ62gPtcMwpibAmhmttdMR0STSjYroq2BH/xy8ukeVbxLysXd+fl6k1eRwEdoWN0inx0haroFtVRA1GUomf0it6cJ+fFeXc+5tEVJ585RH/gfP4AXWuTkA==</latexit>

<latexit sha1_base64="mLGLF/BfCo30SA5zVQQRpw3P/M8=">AAACBXicbVDLSsNAFJ3UV62vqEtdDBahbkoivpbFgrisYB/QhDKZTtqhk0mYmQglZOPGX3HjQhG3/oM7/8ZJmoW2Hhg4c8693HuPFzEqlWV9G6Wl5ZXVtfJ6ZWNza3vH3N3ryDAWmLRxyELR85AkjHLSVlQx0osEQYHHSNebNDO/+0CEpCG/V9OIuAEacepTjJSWBuYhdAKkxp6XtFKH8vyDEUtu0lrzZGBWrbqVAy4SuyBVUKA1ML+cYYjjgHCFGZKyb1uRchMkFMWMpBUnliRCeIJGpK8pRwGRbpJfkcJjrQyhHwr9uIK5+rsjQYGU08DTldmWct7LxP+8fqz8KzehPIoV4Xg2yI8ZVCHMIoFDKghWbKoJwoLqXSEeI4Gw0sFVdAj2/MmLpHNaty/q53dn1cZ1EUcZHIAjUAM2uAQNcAtaoA0weATP4BW8GU/Gi/FufMxKS0bRsw/+wPj8AfJ6mDo=</latexit>

P 2 F(C)

{C(x, a)}a2A

max-min policy policy max-min <latexit sha1_base64="tw61glAc0PeFMloVCl9SO/zlTnA=">AAAB/nicbVDLSgNBEJyNrxhfq+LJy2AQvBh2xdcx6MVjBPOAZAmzk0kyZGZ2memVhCXgr3jxoIhXv8Obf+Mk2YMmFjQUVd10d4Wx4AY879vJLS2vrK7l1wsbm1vbO+7uXs1EiaasSiMR6UZIDBNcsSpwEKwRa0ZkKFg9HNxO/Poj04ZH6gFGMQsk6Sne5ZSAldruQQvYEFJJhqeSKxxHgtPRuO0WvZI3BV4kfkaKKEOl7X61OhFNJFNABTGm6XsxBCnRwKlg40IrMSwmdEB6rGmpIpKZIJ2eP8bHVungbqRtKcBT9fdESqQxIxnaTkmgb+a9ifif10ygex2kXMUJMEVni7qJwBDhSRa4wzWjIEaWEKq5vRXTPtGEgk2sYEPw519eJLWzkn9Zurg/L5Zvsjjy6BAdoRPkoytURneogqqIohQ9o1f05jw5L8678zFrzTnZzD76A+fzB8dBlgc=</latexit>

<latexit sha1_base64="tw61glAc0PeFMloVCl9SO/zlTnA=">AAAB/nicbVDLSgNBEJyNrxhfq+LJy2AQvBh2xdcx6MVjBPOAZAmzk0kyZGZ2memVhCXgr3jxoIhXv8Obf+Mk2YMmFjQUVd10d4Wx4AY879vJLS2vrK7l1wsbm1vbO+7uXs1EiaasSiMR6UZIDBNcsSpwEKwRa0ZkKFg9HNxO/Poj04ZH6gFGMQsk6Sne5ZSAldruQQvYEFJJhqeSKxxHgtPRuO0WvZI3BV4kfkaKKEOl7X61OhFNJFNABTGm6XsxBCnRwKlg40IrMSwmdEB6rGmpIpKZIJ2eP8bHVungbqRtKcBT9fdESqQxIxnaTkmgb+a9ifif10ygex2kXMUJMEVni7qJwBDhSRa4wzWjIEaWEKq5vRXTPtGEgk2sYEPw519eJLWzkn9Zurg/L5Zvsjjy6BAdoRPkoytURneogqqIohQ9o1f05jw5L8678zFrzTnZzD76A+fzB8dBlgc=</latexit>

optimizes

PC-RACP

⌫(⇡, P)

Practical construction

maximize

E[⌫RA (X, C)] <latexit sha1_base64="BUaQswjLAuJgZH8f9u0PA7o8NbA=">AAACCXicbVDJSgNBEO1xjXGLevTSGIQIEmbE7RgNgscoZoHMEHo6naRJT8/QXSOGYa5e/BUvHhTx6h9482/sLAdNfFDweK+Kqnp+JLgG2/625uYXFpeWMyvZ1bX1jc3c1nZNh7GirEpDEaqGTzQTXLIqcBCsESlGAl+wut8vD/36PVOah/IOBhHzAtKVvMMpASO1ctgNCPR8P7lKm66MW4kL7AGS24s0LTQOywdeK5e3i/YIeJY4E5JHE1RauS+3HdI4YBKoIFo3HTsCLyEKOBUszbqxZhGhfdJlTUMlCZj2ktEnKd43Sht3QmVKAh6pvycSEmg9CHzTObxbT3tD8T+vGUPn3Eu4jGJgko4XdWKBIcTDWHCbK0ZBDAwhVHFzK6Y9oggFE17WhOBMvzxLakdF57R4cnOcL11O4sigXbSHCshBZ6iErlEFVRFFj+gZvaI368l6sd6tj3HrnDWZ2UF/YH3+AEZkmg4=</latexit>

<latexit sha1_base64="/9qsFmBtVcCjz3oMP0mVbLjzuQM=">AAAB/HicdVDLSsNAFJ3UV62vaJduBotQQUpSaq27ohuXFewDmlAm00k7dDIJMxMhhPorblwo4tYPceffOGkjqOiBgcM593LPHC9iVCrL+jAKK6tr6xvFzdLW9s7unrl/0JNhLDDp4pCFYuAhSRjlpKuoYmQQCYICj5G+N7vK/P4dEZKG/FYlEXEDNOHUpxgpLY3MssPjqhPRUydAaup5aWd+MjIrVq15YbXsOrRq1gIZsRt1TexcqYAcnZH57oxDHAeEK8yQlEPbipSbIqEoZmRecmJJIoRnaEKGmnIUEOmmi/BzeKyVMfRDoR9XcKF+30hRIGUSeHoyiyh/e5n4lzeMld9yU8qjWBGOl4f8mEEVwqwJOKaCYMUSTRAWVGeFeIoEwkr3VdIlfP0U/k969ZrdrJ3dNCrty7yOIjgER6AKbHAO2uAadEAXYJCAB/AEno1749F4MV6XowUj3ymDHzDePgFV65SX</latexit>

<latexit sha1_base64="5jLRrDEHtg3q5Eq+rHzSbYBIw3Y=">AAACBnicbVDJSgNBEO2JW4zbqEcRGoMQQcKMuB2juXiMYBbIhFDT6SRNenqG7h4xDHPy4q948aCIV7/Bm39jZzlo4oOCx3tVVNXzI86UdpxvK7OwuLS8kl3Nra1vbG7Z2zs1FcaS0CoJeSgbPijKmaBVzTSnjUhSCHxO6/6gPPLr91QqFoo7PYxoK4CeYF1GQBupbe97SbnwcAxHXtpOwGMCewHoPgGeXKVp2847RWcMPE/cKcmjKSpt+8vrhCQOqNCEg1JN14l0KwGpGeE0zXmxohGQAfRo01ABAVWtZPxGig+N0sHdUJoSGo/V3xMJBEoNA990jm5Us95I/M9rxrp72UqYiGJNBZks6sYc6xCPMsEdJinRfGgIEMnMrZj0QQLRJrmcCcGdfXme1E6K7nnx7PY0X7qexpFFe+gAFZCLLlAJ3aAKqiKCHtEzekVv1pP1Yr1bH5PWjDWd2UV/YH3+AJhXmJo=</latexit>

C⇤ <latexit sha1_base64="HxOE7vcMDHaS9ms5v1zyZ7XU3Jk=">AAAB6nicbVDJSgNBEK1xjXGLevTSGATxEGbE7RjMxWNEs0Ayhp5OT9Kkp2forhHCkE/w4kERr36RN//GznLQxAcFj/eqqKoXJFIYdN1vZ2l5ZXVtPbeR39za3tkt7O3XTZxqxmsslrFuBtRwKRSvoUDJm4nmNAokbwSDythvPHFtRKwecJhwP6I9JULBKFrpvvJ42ikU3ZI7AVkk3owUYYZqp/DV7sYsjbhCJqkxLc9N0M+oRsEkH+XbqeEJZQPa4y1LFY248bPJqSNybJUuCWNtSyGZqL8nMhoZM4wC2xlR7Jt5byz+57VSDK/9TKgkRa7YdFGYSoIxGf9NukJzhnJoCWVa2FsJ61NNGdp08jYEb/7lRVI/K3mXpYu782L5ZhZHDg7hCE7Agysowy1UoQYMevAMr/DmSOfFeXc+pq1LzmzmAP7A+fwBsgKNbQ==</latexit>

maximize

<latexit sha1_base64="IhoJuG0Yu+cK81lg4wUak+Hq424=">AAAB+HicbVBNT8JAEN3iF+IHVY9eGomJJ9Iagx6JXjxiIh8JNGS7DLBht212pwZo+CVePGiMV3+KN/+NC/Sg4EsmeXlvJjPzglhwja77beU2Nre2d/K7hb39g8OifXTc0FGiGNRZJCLVCqgGwUOoI0cBrVgBlYGAZjC6m/vNJ1CaR+EjTmLwJR2EvM8ZRSN17WIHYYyppGMu+RRmXbvklt0FnHXiZaREMtS69lenF7FEQohMUK3bnhujn1KFnAmYFTqJhpiyER1A29CQStB+ujh85pwbpef0I2UqRGeh/p5IqdR6IgPTKSkO9ao3F//z2gn2b/yUh3GCELLlon4iHIyceQpOjytgKCaGUKa4udVhQ6ooQ5NVwYTgrb68ThqXZa9Srjxclaq3WRx5ckrOyAXxyDWpkntSI3XCSEKeySt5s6bWi/VufSxbc1Y2c0L+wPr8AbPVk8k=</latexit>

Thm 3.4

<latexit sha1_base64="gQjU1zgYhnwWKet+ezNcTO67kPE=">AAAB+3icbVDLSgNBEJz1GeNrjUcvg0HwFHZFosegF48RzAOSJcxOepMhsw9meiVxya948aCIV3/Em3/jJNmDJhY0FFXddHf5iRQaHefbWlvf2NzaLuwUd/f2Dw7to1JTx6ni0OCxjFXbZxqkiKCBAiW0EwUs9CW0/NHtzG89gtIijh5wkoAXskEkAsEZGqlnlyjtIowxixMUoXgCPe3ZZafizEFXiZuTMslR79lf3X7M0xAi5JJp3XGdBL2MKRRcwrTYTTUkjI/YADqGRiwE7WXz26f0zCh9GsTKVIR0rv6eyFio9ST0TWfIcKiXvZn4n9dJMbj2MhElKULEF4uCVFKM6SwI2hcKOMqJIYwrYW6lfMgU42jiKpoQ3OWXV0nzouJWK9X7y3LtJo+jQE7IKTknLrkiNXJH6qRBOBmTZ/JK3qyp9WK9Wx+L1jUrnzkmf2B9/gBRV5Sn</latexit>

<latexit sha1_base64="ZQ1O5aMAfTvlqBe40WO7fBH/bDI=">AAACDXicbVDLSsNAFJ3UV62vqEs3g1VoQUoivpbFgriMYB/QlDKZTtqhk0mYmQgl5Afc+CtuXCji1r07/8ZJm4W2HhjmcM693HuPFzEqlWV9G4Wl5ZXVteJ6aWNza3vH3N1ryTAWmDRxyELR8ZAkjHLSVFQx0okEQYHHSNsbNzK//UCEpCG/V5OI9AI05NSnGCkt9c0jl3K/nzj6g26A1AgjltyklUY1dXlccSN64lT7ZtmqWVPARWLnpAxyOH3zyx2EOA4IV5ghKbu2FalegoSimJG05MaSRAiP0ZB0NeUoILKXTK9J4bFWBtAPhX5cwan6uyNBgZSTwNOV2cJy3svE/7xurPyrXkJ5FCvC8WyQHzOoQphFAwdUEKzYRBOEBdW7QjxCAmGlAyzpEOz5kxdJ67RmX9TO787K9es8jiI4AIegAmxwCergFjigCTB4BM/gFbwZT8aL8W58zEoLRt6zD/7A+PwBKOqa+Q==</latexit>

inf

P 2F (C)

⌫(⇡, P )

RA-DPO

RA-CPO-1

<latexit sha1_base64="8N7GAknCW13zPGjDLQKqUAeCURE=">AAAB9HicbVDJSgNBEO1xjXGLevTSGAQvhhmR6DEuB29GMQskQ+jp1CRNeha7a4JhyHd48aCIVz/Gm39jZzlo4oOCx3tVVNXzYik02va3tbC4tLyymlnLrm9sbm3ndnarOkoUhwqPZKTqHtMgRQgVFCihHitggSeh5vWuRn6tD0qLKHzAQQxuwDqh8AVnaCS3ifCE6f3F8XX5dtjK5e2CPQadJ86U5MkU5Vbuq9mOeBJAiFwyrRuOHaObMoWCSxhmm4mGmPEe60DD0JAFoN10fPSQHhqlTf1ImQqRjtXfEykLtB4EnukMGHb1rDcS//MaCfrnbirCOEEI+WSRn0iKER0lQNtCAUc5MIRxJcytlHeZYhxNTlkTgjP78jypnhScYqF4d5ovXU7jyJB9ckCOiEPOSInckDKpEE4eyTN5JW9W33qx3q2PSeuCNZ3ZI39gff4AOqmRww==</latexit>

<latexit sha1_base64="0g6sbbo8hM8MzRt6LrTbLsLkFM0=">AAACAXicbVDLSsNAFJ34rPUVdSO4CRahbkoivsBNtRuXVewDmhAmk0k7dPJg5kYsIW78FTcuFHHrX7jzb5w+Ftp64MLhnHu59x4v4UyCaX5rc/MLi0vLhZXi6tr6xqa+td2UcSoIbZCYx6LtYUk5i2gDGHDaTgTFocdpy+vXhn7rngrJ4ugOBgl1QtyNWMAIBiW5+q6dMDezgT5AdnuZ52Wb+DFc1A5dvWRWzBGMWWJNSAlNUHf1L9uPSRrSCAjHUnYsMwEnwwIY4TQv2qmkCSZ93KUdRSMcUulkow9y40ApvhHEQlUExkj9PZHhUMpB6KnOEENPTntD8T+vk0Jw7mQsSlKgERkvClJuQGwM4zB8JigBPlAEE8HUrQbpYYEJqNCKKgRr+uVZ0jyqWKeVk5vjUvVqEkcB7aF9VEYWOkNVdI3qqIEIekTP6BW9aU/ai/aufYxb57TJzA76A+3zByaLlrI=</latexit>

⇡RA (·; C)

<latexit sha1_base64="EQmUNRV/cxz1uW5e0LC8CRiZJfE=">AAAB73icbVDLTsJAFL3FF+Kr6tLNRGLiBtKS+FiibNyJRh4JNGQ6TGHCdFpnpiak4SfcuNAYt/6OO//GAbpQ8CQ3OTnn3tx7jx9zprTjfFu5ldW19Y38ZmFre2d3z94/aKookYQ2SMQj2faxopwJ2tBMc9qOJcWhz2nLH9WmfuuJSsUi8aDHMfVCPBAsYARrI7Xvr0q1+m3J7dlFp+zMgJaJm5EiZKj37K9uPyJJSIUmHCvVcZ1YeymWmhFOJ4VuomiMyQgPaMdQgUOqvHR27wSdGKWPgkiaEhrN1N8TKQ6VGoe+6QyxHqpFbyr+53USHVx6KRNxoqkg80VBwpGO0PR51GeSEs3HhmAimbkVkSGWmGgTUcGE4C6+vEyalbJ7Xj67qxSr11kceTiCYzgFFy6gCjdQhwYQ4PAMr/BmPVov1rv1MW/NWdnMIfyB9fkDRQeO0g==</latexit>

Thm 3.1

Policy-coupled <latexit sha1_base64="B7zuZoR4vcpu0/I1/rXQXJYBp+A=">AAAB9XicbVDLSgNBEJyNrxhfUY9eBoPgxbAb8HEMevEYwTwgWcPsbG8yZHZmmZlVwpL/8OJBEa/+izf/xkmyB00saCiquunuChLOtHHdb6ewsrq2vlHcLG1t7+zulfcPWlqmikKTSi5VJyAaOBPQNMxw6CQKSBxwaAejm6nffgSlmRT3ZpyAH5OBYBGjxFjpoSE5o+MzKtOEQ9gvV9yqOwNeJl5OKihHo1/+6oWSpjEIQznRuuu5ifEzogyjHCalXqohIXREBtC1VJAYtJ/Nrp7gE6uEOJLKljB4pv6eyEis9TgObGdMzFAvelPxP6+bmujKz5hIUgOCzhdFKcdG4mkEOGQKqOFjSwhVzN6K6ZAoQo0NqmRD8BZfXiatWtW7qJ7f1Sr16zyOIjpCx+gUeegS1dEtaqAmokihZ/SK3pwn58V5dz7mrQUnnzlEf+B8/gCawZKX</latexit>

RA-CPO-2 <latexit sha1_base64="lwamgSQT6Y5LMERv3YNmDUd3c7Q=">AAAB73icbVDLTsJAFL3FF+Kr6tLNRGLiBtKS+FiibNyJRh4JNGQ6TGHCdFpnpiak4SfcuNAYt/6OO//GAbpQ8CQ3OTnn3tx7jx9zprTjfFu5ldW19Y38ZmFre2d3z94/aKookYQ2SMQj2faxopwJ2tBMc9qOJcWhz2nLH9WmfuuJSsUi8aDHMfVCPBAsYARrI7Xvr0q1+m2p0rOLTtmZAS0TNyNFyFDv2V/dfkSSkApNOFaq4zqx9lIsNSOcTgrdRNEYkxEe0I6hAodUeens3gk6MUofBZE0JTSaqb8nUhwqNQ590xliPVSL3lT8z+skOrj0UibiRFNB5ouChCMdoenzqM8kJZqPDcFEMnMrIkMsMdEmooIJwV18eZk0K2X3vHx2VylWr7M48nAEx3AKLlxAFW6gDg0gwOEZXuHNerRerHfrY96as7KZQ/gD6/MHRouO0w==</latexit>

Thm 3.2

Universal <latexit sha1_base64="AQefV3cLktFt4ReG4TN6WFQLyjU=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69LBbBU0kKfhyLXjxWMG2lDWWz3bRLdzdhdyOU0F/hxYMiXv053vw3btoctPXBwOO9GWbmhQln2rjut1NaW9/Y3CpvV3Z29/YPqodHbR2nilCfxDxW3RBrypmkvmGG026iKBYhp51wcpv7nSeqNIvlg5kmNBB4JFnECDZWevQly13MB9WaW3fnQKvEK0gNCrQG1a/+MCapoNIQjrXueW5iggwrwwins0o/1TTBZIJHtGepxILqIJsfPENnVhmiKFa2pEFz9fdEhoXWUxHaToHNWC97ufif10tNdB1kTCapoZIsFkUpRyZG+fdoyBQlhk8twUQxeysiY6wwMTaFig3BW355lbQbde+yfnHfqDVvijjKcAKncA4eXEET7qAFPhAQ8Ayv8OYo58V5dz4WrSWnmDmGP3A+fwANvZCV</latexit>

Figure 2: Blue box: the user-facing prediction sets {C(x, a)}a∈A and the induced max–min policy πRA (·; C).

Grey box (Sec. 2): Under policy-coupled coverage, the prediction sets induce an ambiguity class F(C), for which πRA is worst-case optimal for risk objective ν(π, P ). Orange box (Sec. 3): Optimizing prediction sets under policy-coupled coverage (RA-CPO-1) is equivalent both to the stronger universal-coverage formulation (RA-CPO-2) and to direct risk-averse optimization over policies and utility certificates (RA-DPO). Finally, PC-RACP produces conformal prediction sets obeying the policy-coupled coverage in finite samples.

either of them to derive the formulae of the optimal prediction sets and construct prediction sets with finite-sample validity. The universal coverage proves useful in the first task (Theorem 3.4). Finally, we return to the construction of prediction sets obeying the policy-coupled coverage with data (Section 4). We propose a weighted two-stage conformal prediction procedure and prove the coverage guarantee of the resulting prediction sets, i.e., they cover the realized outcome under the induced max–min rule with high probability. In simulation studies and real data case studies in Section 5, we demonstrate the high utility achieved by the max–min policy based on, and the valid coverage of, our prediction sets. In particular, ignoring the counterfactual structure and following the single-outcome recipe is suboptimal in terms of both statistical validity and decision utility.

1.3

Related work

Our work builds on recent decision-theoretic foundations for predictive inference (Kiyani et al., 2025; Wang and Dobriban, 2026; Zhu et al., 2026). This literature complements the classical literature on calibration, where probabilistic forecasts are shown to be optimal for risk-neutral decisionmaking (Foster and Vohra, 1998; Kakade and Foster, 2008; Zhao et al., 2021). In contrast, our work follows the risk-averse framework of Kiyani et al. (2025) to establish optimal decision-making based on prediction sets. Kiyani et al. (2025) show that, in standard single-outcome prediction problems, prediction sets can serve as a lossless interface between uncertainty and risk-averse decision-making; Wang and Dobriban (2026) extend this perspective to expected-loss objectives. The distinguishing feature of the counterfactual setting is that the decision changes the outcome to be covered, which leads to distinct coverage target, decision-theoretic optimality, and construction of prediction sets. The recent concurrent work of Zhu et al. (2026) considers action-conditional coverage in the singleoutcome setting; although they tie the action closely to the coverage, due to the counterfactual setting, we build distinct optimality theory, and we construct a set of per-action prediction sets instead of one for the single realized outcome. Our work is also related to conformal inference for counterfactual and causal quantities under the potential outcome framework in causal inference and data-driven decision-making (Rubin, 2005; Imbens and Rubin, 2015). This framework is standard in our motivating applications such as treatment selection and online marketing. Prior work develops conformal prediction sets for potential outcomes, individual treatment effects, and sensitivity analysis (Lei and Candès, 2021; Jin et al., 2023; Yin et al., 2024; Alaa et al., 2023), whose validity is often per-action or per-potential-outcome 4

coverage guarantees. By contrast, our goal is to connect statistical validity to downstream decision optimality. This leads to the new notion of policy-coupled coverage of the realized outcome under the policy induced by the prediction sets, with different motivations and conformal procedures.

A decision-theoretic framework for counterfactual decisions

We begin by introducing the problem setup and the decision-theoretic framework. Section 2.1 introduces the utility objective studied in this paper. Section 2.2 introduces the notion of prediction sets and set-based decisions. Section 2.3 studies the fixed-set optimal decision problem (grey box in Figure 2) which justifies acting based on prediction sets under distributional ambiguity. Recall that X ∈ X is the observed features, A = {a1 , . . . , a|A| } a finite action set, and {Y (a)}a∈A potential outcomes, where Y (a) ∈ Y is the outcome realized if action a is taken. A bounded utility function u : A × Y → R assigns value u(a, y) to taking action a and observing outcome y. A policy π : X → A maps features to actions; under policy π, the realized outcome is Y (π(X)) and the realized utility is u(π(X), Y (π(X))). The defining feature of our setting is that the outcome that materializes depends on the action taken. We use the notation P to denote a distribution over (X, {Y (a)}a∈A ), and for clarity, let P denote the unknown, true data distribution.

2.1

Risk-averse objective: the population-level problem

The decision-making problem aims to choose actions that optimize certain objectives. Following Kiyani et al. (2025), we study risk-averse agents whose goal is to choose actions that ensure a sufficiently high utility with high probability over the randomness of unknown outcomes. Formally, fix some α ∈ (0, 1) and let umax ≥ maxa∈A supy∈Y u(a, y) be a fixed upper bound on the utility. We call η : X → (−∞, umax ] a utility certificate for π under distribution P if P u(π(X), Y (π(X))) ≥ η(X) ≥ 1 − α. (2.1) Here, (2.1) extends the utility certificate notion in Kiyani et al. (2025) by replacing the standard label Y with the realized outcome Y (π(X)). The feature-dependent certificate thus concerns the realized utility: with probability at least 1 − α, policy π delivers at least η(X) of utility. The larger η(X) is, the better the policy serves a risk-averse agent. This motivates the risk objective n o ν(π, P ) := max EP [η(X)] : P u(π(X), Y (π(X))) ≥ η(X) ≥ 1 − α , (2.2) the highest expected certificate attainable under policy π and distribution P . Such a risk objective is justified (see Kiyani et al. (2025, Section 2)) as a marginalized version of an X-conditional highprobability risk optimization problem. The marginalization is useful since conditional coverage is often intractable in finite samples (Foygel Barber et al., 2021). The direct risk-averse optimization problem maximizes ν(π, P) over π ∈ Π: Maximize ν(π, P) π∈Π

⇔

Maximize E[η(X)] π∈Π, η(·) subject to P u(π(X), Y (π(X))) ≥ η(X) ≥ 1 − α.

Here Π is the collection of all policies π : X → A. 5

(RA-DPO)

2.2

Prediction sets and set-based actions

Since the true joint distribution P of (X, {Y (a)}a∈A ) is typically unknown, the decision-maker needs to rely on partial information about P. We focus on the scenario where such partial information is encapsulated in a collection of prediction sets C = {C(x, a)}a∈A . Intuitively, for each action a ∈ A, the prediction set C(x, a) ⊆ Y quantifies the likely range of the outcome Y (a) when observing feature values X = x ∈ X . Without any formal justification of how to act upon the prediction sets, a natural instinct is to assume Y (a) varies within C(x, a) ⊆ Y and, extending Kiyani et al. (2025), take the action maximizing worst-case utility within its set, πRA (x; C) := argmax a∈A

inf

y∈C(x,a)

u(a, y),

νRA (x; C) := max

inf

a∈A y∈C(x,a)

u(a, y).

(2.3)

While it is common in practice to enforce non-empty prediction sets, to avoid additional assumptions on either the data-generating process or the utility function, we set the convention inf y∈∅ u(a, y) := umax . Intuitively, πRA guards against the worst outcome Y (a) within the likely range C(x, a), representing a risk-averse way of acting based on the prediction sets. At this stage, πRA (·; C) and νRA (·; C) are set-induced quantities only. The remaining question is decision-theoretic: what validity guarantee on C makes this rule justified, and in what sense?

2.3

What coverage guarantee justifies set-induced counterfactual decisions?

Our conceptual basis is coverage-induced distributional ambiguity. A validity guarantee on the prediction sets defines a class of data-generating distributions P consistent with it, and one chooses the policy that maximizes the worst-case risk-averse objective. The question of this section is therefore: which counterfactual validity notion makes a set-induced policy robust-optimal? Unlike the standard prediction problem, the coverage notion for counterfactual decisions is not straightforward since the realized outcome is coupled with the action to be determined. A direct extension of the standard marginal coverage is per-action marginal coverage: P (Y (a) ∈ C(X, a)) ≥ 1 − α

for each a ∈ A,

(2.4)

requiring each set to individually cover its potential outcome with probability 1 − α. This has been the primary focus in predictive inference in counterfactual (causal) problems (Lei and Candès, 2021; Jin et al., 2023; Yin et al., 2024). However, the per-action coverage which constrains each set in isolation appears insufficient for decision-making: it does not by itself determine whether the set for the chosen action covers the realized outcome. That is, (2.4) alone does not imply whether, for a policy π under consideration, P Y (π(X)) ∈ C(X, π(X)) ≥ 1 − α. (2.5) It is therefore unclear how acting based on prediction sets satisfying (2.4) may be justified. Furthermore, even though a “universal” coverage holds—that is, (2.5) holds for all policy π—the decisionmaker may have to compare a collection of stochastically dependent prediction sets {C(X, π(X))}π∈Π , which may not necessarily lead to coverage for the chosen decision-induced outcome. We address this question by identifying the notion of coverage that justifies πRA (·; C). We define the distributional uncertainty set (omitting the dependence on C in πRA for readability) n o F(C) = P = {Pa (x, y)}a∈A : P Y (πRA (X)) ∈ C(X, πRA (X)) ≥ 1 − α , (2.6) 6

and call the corresponding coverage requirement as policy-coupled coverage (PCC for short). It requires the prediction sets corresponding to the action πRA (X) to cover the realized outcome with high probability. This guarantee is decision-aware—and self-referential—in that the sets must cover the realized outcome induced by them. To the best of our knowledge, existing finite-sample methods do not provide this guarantee; we return to this construction problem in Section 4. Theorem 2.1 connects the coverage notion, max–min decision rule, and utility objective in the decision-theoretic sense. Its proof is in Appendix B.1. Theorem 2.1. Let F (C) be defined in (2.6). Then argmax π∈Π

inf

P ∈F (C)

ν(π, P ) = πRA (·; C)

Theorem 2.1 shows that, if the only information available about the underlying distribution is that it belongs to F(C), then πRA (·; C) maximizes the worst-case risk-averse objective over that ambiguity class. In this sense, policy-coupled coverage makes the prediction sets sufficient for deriving the minimax-optimal decision rule for a given collection of prediction sets. This result justifies the following pipeline: for a new instance X with prediction sets {C(X, a)}a∈A obeying the PCC, the decision-maker chooses the action πRA (X) = πRA (X; C); due to the PCC, P u(πRA (X); Y (πRA (X))) ≥ νRA (X; C) ≥ 1 − α. (2.7) That is, νRA (X; C) is now a valid utility certificate (c.f. definition in (2.1)) for the policy πRA (·; C). To summarize, this section resolves the fixed-set decision-making question: once a collection of prediction sets is given, policy-coupled validity justifies acting via πRA . The remaining question is the set-level optimality: Which collections {C(x, a)}a∈A are most useful to a decision-maker among all sets satisfying the PCC? Can they match the value of direct policy-certificate optimization?

Optimal prediction sets for counterfactual decisions

This section completes the theoretical framework by studying the questions above. We shall show that prediction sets are a lossless interface for counterfactual decision-making: optimizing E[νRA (X; C)] with respect to C attains the same optimal value as direct risk-averse optimization over policies and utility certificates. We then leverage an equivalent form of the first optimization problem to establish the explicit form of the optimizer C ∗ which guides practical construction later on.

3.1

Prediction sets as lossless interface: RA-DPO and two versions of RA-CPO

Before studying the prediction sets that are most useful to the decision-maker, let us recall the RADPO problem in Section 2. RA-DPO optimizes directly over policies and utility certificates. We show that optimizing prediction sets under policy-coupled coverage is lossless for this objective: optimally designed prediction sets attain the same objective value as RA-DPO. Consider the following prediction-set optimization problem, named after Kiyani et al. (2025): Maximize E[νRA (X; C)] C(·,·)

subject to P(Y (πRA (X; C)) ∈ C(X, πRA (X; C))) ≥ 1 − α. 7

(RA-CPO-1)

RA-CPO-1 seeks to maximize the expected utility certificate for the policy πRA induced by the prediction sets subject to the PCC. Compared with RA-DPO which optimizes over all policies and their associated utility certificates, a key distinction is that RA-CPO-1 optimizes over a seemingly smaller range: the policies and utility certificates considered must be induced by prediction sets obeying the PCC. In words, RA-CPO-1 uses prediction sets as an interface for risk-averse counterfactual decisions. Somewhat surprisingly, the prediction-set setup is equivalent to the full-range optimization in RA-DPO. Theorem 3.1 formalizes the idea, whose proof is in Appendix B.3. Theorem 3.1 (Equivalence of RA-CPO-1 and RA-DPO). From any optimal solution (π ∗ , ν ∗ ) to RA-DPO, there exists an optimal solution {C1∗ (X, a)}a∈A to RA-CPO-1 so that E[ν ∗ (X)] = E[νRA (X; C1∗ )]. Vice versa, for any optimal solution {C1∗ (X, a)}a∈A to RA-CPO-1, there exists an optimal solution (π ∗ , ν ∗ ) to RA-DPO, such that E[ν ∗ (X)] = E[νRA (X; C1∗ )]. Theorem 3.1 establishes prediction sets with PCC as a lossless interface for counterfactual decision-making. For a decision-maker who is interested in maximizing the risk objective ν(π; P) over all possible policies, it suffices to consider the induced policy of an optimal prediction set with PCC. Formally, for any optimal solution {C1∗ (x, a)}a∈A , by our discussion around (2.7), the induced policy πRA (·; C1∗ ) has a valid certificate νRA (X; C1∗ ). Therefore, by definition (2.2), ν(πRA (·; C1∗ ); P) ≥ E[νRA (X; C1∗ )] = E[ν ∗ (X)], the optimal objective of RA-DPO. As such, πRA (·; C1∗ ) must be an optimal solution to RA-DPO. In other words, finding the optimally designed prediction sets suffices for direct risk-averse optimization. This is the focus of Section 3.2. While RA-CPO-1 provides a sufficient summary, the self-referential nature of the PCC makes it less straightforward to explicitly find the optimal solution. It turns out helpful to consider another RA-CPO-type problem, which we call RA-CPO-2: Maximize E[νRA (X; C)] C(·,·)

subject to P(Y (π(X)) ∈ C(X, π(X))) ≥ 1 − α for any π ∈ Π.

(RA-CPO-2)

The two RA-CPO-type problems pursue the same objective function, yet RA-CPO-2 imposes a stronger coverage condition: the prediction sets need to provide “universal” policy-induced coverage for any policy π ∈ Π, while RA-CPO-1 does so for πRA only. However, RA-CPO-1 and RA-CPO-2 are equivalent for the risk objective. The proof of Theorem 3.2 is in Appendix B.2. Theorem 3.2 (Equivalence of RA-CPO-1 and RA-CPO-2). For any optimal solution {C1∗ (X, a)}a∈A of RA-CPO-1, there exists an optimal solution {C2∗ (X, a)}a∈A to RA-CPO-2 so that E[νRA (X, C1∗ )] = E[νRA (X, C2∗ )]. Moreover, any optimal solution {C2∗ (X, a)}a∈A of RA-CPO-2 must also be an optimal solution to RA-CPO-1. The equivalence of RA-CPO-1 and RA-CPO-2 illustrates that πRA (x; C) is the policy that “scrutinize” the coverage ability of C the most from a risk-averse decision-making perspective. Together, Theorems 3.1 and 3.2 show that RA-DPO, RA-CPO-1 and RA-CPO-2 are all equivalent. Following the discussion below Theorem 3.1, any optimal solution {C2∗ (x, a)} to RA-CPO-2 must also be optimal for RA-CPO-1, which is further an optimal solution to RA-DPO. In words, 8

to solve RA-DPO, it suffices to find the optimal prediction sets that maximize E[νRA (X; C)] while obeying the coverage guarantees imposed in RA-CPO-1 or RA-CPO-2. We shall see that RACPO-2 is convenient for deriving the explicit form of the optimal solutions (Section 3.2), while the coverage constraint of RA-CPO-1 is arguably easier to achieve in finite samples (Section 4). Summary of theoretical results. We have thus far completed the decision-theoretical framework of risk-averse counterfactual decisions, summarized in Figure 2. Our results reveal the key role of policy-coupled coverage: distinct from Kiyani et al. (2025) where the usual marginal coverage P(Y ∈ C(X)) ≥ 1 − α suffices, here, we need stronger coverage guarantees for the prediction sets to be optimal in guiding decision making. The policy-coupled coverage justifies acting based on prediction sets. In addition, optimally designed prediction sets with such coverage attain the same optimal value as direct risk-averse optimization for a risk-averse decision-maker.

3.2

Optimal prediction sets for risk-averse decisions

Finally, we provide an explicit form of the (population-level) optimal prediction sets by solving the RA-CPO-2 problem. As preparation for solving RA-CPO-2, we define some key quantities. For a random variable Z, we define its “upper quantile” as Quantile+ α [Z] := sup{z ∈ R | P(Z ≤ z) ≤ α},

α ∈ [0, 1),

(3.1)

and Quantile+ 1 [Z] := umax . This definition slightly differs from the usual one, i.e., Quantileα [Z] := inf{z ∈ R | P(Z ≤ z) ≥ α}, and one can prove that Quantile+ α [Z] ≥ Quantileα [Z]. The rightcontinuity of the function q(α) = sup{z ∈ R | P(Z ≤ z) ≤ α} makes it convenient to define optimal prediction sets; see a discussion in Appendix B.4. In addition, we define the following quantities: γ(x, t, a) = Quantile+ 1−t [u(a, Y (a)) | X = x],

θ(x, t) = max Quantile+ 1−t [u(a, Y (a)) | X = x], a∈A

a(x, t) = argmax Quantile+ 1−t [u(a, Y (a)) | X = x]. a∈A

Intuitively, γ(x, t, a) is the upper conditional quantile of the utility when taking the action a ∈ A, and θ(x, t) is the optimal quantile over actions, which is achieved by the action a(x, t). Proposition 3.3, which considers a conditional problem, serves as an instrument for defining the optimal prediction sets. A more general result is in Proposition A.5 with proof in Appendix B.5. Proposition 3.3. For any fixed x ∈ X and t ∈ [0, 1], among all the prediction sets {C(x, a)}a∈A obeying mina∈A P(Y (a) ∈ C(x, a) | X = x) ≥ t, the following prediction sets maximize νRA (x; C): C ∗ (x, a) = {y ∈ Y | u(a, y) ≥ γ(x, t, a)} for every action a ∈ A. Further, we have νRA (x; C ∗ ) = θ(x, t). We now proceed to solve RA-CPO-2. For any feasible prediction sets C = {C(x, a)}a∈A in RA-CPO-2, define tC (x) = min P(Y (a) ∈ C(x, a) | X = x). a∈A

Then tC is feasible for RA-CPO-2’ below, and the objective value of C is no larger than EX [θ(X, tC (X))]. Conversely, for any feasible t : X → [0, 1], Proposition 3.3 constructs threshold prediction sets Ct (x, a) = {y ∈ Y | u(a, y) ≥ γ(x, t(x), a)},

a ∈ A,

which are feasible for RA-CPO-2 and attain the same objective value EX [θ(X, t(X))]. RA-CPO-2 is thus equivalent to the following program: Maximize EX [θ(X, t(X))] t:X →[0,1]

subject to EX [t(X)] ≥ 1 − α.

(RA-CPO-2’)

In addition, the above arguments imply that for any optimal solution t∗ (x) to RA-CPO-2’, we can find an optimal solution to RA-CPO-2 given by C ∗ (x, a) = {y ∈ Y | u(a, y) ≥ γ(x, t∗ (x), a)} for every action a ∈ A.

(3.2)

Here, the function t(·) can be viewed as a conditional coverage assignment rule: the constructed prediction sets have action-wise conditional coverage at least t∗ (x), and the constraint in RACPO-2’ ensures the desired marginal universal coverage. Meanwhile, the optimal objective value of RA-CPO-2’ is equal to that of RA-CPO-2, i.e., the expectation of the optimal utility certificate θ(X, t∗ (X)). It then suffices to find the optimal solution t∗ (x) to RA-CPO-2’. Define g(x, β) := argmax {θ(x, s) + βs}.

(3.3)

s∈[0,1]

Since θ(x, t) is left-continuous and non-increasing in t (because γ(x, t, a) is left-continuous in t; c.f. Appendix B.4) and βt is continuous in t, it is straightforward to see that g(x, β) is well-defined. Theorem 3.4 characterizes the optimal prediction sets, assuming that the maximizer of θ(x, s) + βs over [0, 1] is unique. A fully general result that eliminates such conditions via randomization is in Theorem A.6 with proof in Appendix B.6. Theorem 3.4. Suppose the maximizer of θ(x, s) + βs is unique for PX -a.e. x for all β ≥ 0, then there exists some fixed constant β ∗ ≥ 0 such that t∗ (x) = g(x, β ∗ ) is an optimal solution to RA-CPO-2’ and E[g(X, β ∗ )] = 1 − α. Accordingly, the prediction sets C ∗ (x, a) = y ∈ Y : u(a, y) ≥ γ(x, g(x, β ∗ ), a) for every action a ∈ A (3.4) are an optimal solution to RA-CPO-2 and RA-CPO-1. Summary of optimal solutions. The optimal prediction sets now connect all the concepts established before, yielding optimal worst-case utility for a risk-averse agent. By definition, we have inf y∈C ∗ (x,a) u(a, y) = γ(x, g(x, β ∗ ), a) (see Appendix B.9 for a formal proof). The max–min ∗ ∗ ∗ (x) = argmax policy based on C ∗ is then πRA a∈A γ(x, g(x, β ), a). For this policy, ηRA (x) := ∗ ∗ maxa∈A γ(x, g(x, β ), a) is a valid utility certificate because of the PCC of C . By Theorems 3.1 ∗ , η ∗ ) is the optimal solution to RA-DPO, and C ∗ is the optimal solution and 3.2, we know (πRA RA to RA-CPO-1 and RA-CPO-2. 10

Constructing optimal conformal prediction sets

In this section, we present an algorithm for practically constructing the prediction sets. Theorem 3.4 motivates the following approach: estimate the function g(x, β) defined in (3.3), search for β ∗ through the criterion E[g(X, β ∗ )] = 1 − α, and then plug these estimators into (3.4). Throughout this section, we work under the uniqueness assumption in Theorem 3.4, namely that the maximizer of s 7→ θ(x, s)+βs is unique almost surely. Our algorithm estimates these quantities to approximate the optimal solution while retaining a rigorous finite-sample PCC guarantee. Following the standard setups in counterfactual inference (Imbens and Rubin, 2015; Lei and Candès, 2021; Jin et al., 2023), we assume access to a dataset of i.i.d. triplets {(Xi , Yi , Ai )}N i=1 where Xi ∼ PX , and Ai ∼ π(· | Xi ) where π : X → ∆(A) is a behavior policy, and the outcome is from Yi ∼ PY (a) | X for a = Ai . For simplicity, we assume the behavior policy π is known; if it is not, it is natural to estimate it and plug into our procedure (which can be viewed as an extension of weighted conformal prediction (Tibshirani et al., 2019)). There has been extensive literature on the robustness of weighted conformal prediction to estimation error in weights (Lei and Candès, 2021) whose results shall similarly apply here; we thus do not pursue this direction. We are interested in a test point Xtest ∼ PX independent of the labeled data, given which the potential outcomes {Ytest (a)}a∈A are from PY (a) | X=Xtest for each a ∈ A. We aim to output prediction sets Ĉ(Xtest , a) ⊆ Y that attain the PCC (2.6) for the induced policy πRA (X; Ĉ). The policy-coupled coverage introduces the new challenge that both Ĉ and πRA (·; Ĉ) are learned from data and intertwine with each other. To achieve the PCC, we take a two-step approach: we first learn certain preliminary prediction sets to pin down the max–min policy, and then calibrate the final prediction sets that induce the same policy while obeying valid coverage. Data splitting. We partition the labeled data into three disjoint sets Itrain ∪ Ilearn ∪ Icalib = {1, . . . , N }. The training split is used to fit prediction models; the learning split is used to learn the max–min policy; the calibration split is used to construct the final prediction sets. Step 1: model estimation. Recall the definition of the α-upper quantile in (3.1). Using the training fold {(Xi , Yi , Ai )}i∈Itrain , we fit an estimator γ̂(x, t, a) for utility quantiles γ(x, t, a) = + Quantile1−t u(a, Y ) | X = x, A = a for t ∈ [0, 1], x ∈ X , and a ∈ A. Here γ̂(x, t, a) is obtained from an outcome model Pb(· | X = x, A = a), i.e., analogously to Kiyani et al. (2025), b b b γ̂(x, t, a) = Quantile+ 1−t u(a, Y (a)) | Y (a) ∼ P (· | X = x, A = a) . We then define θ̂(x, t) := max γ̂(x, t, a),

â(x, t) := argmax γ̂(x, t, a).

a∈A

To approximate the optimal solution in Theorem 3.3, we begin by estimating the optimal conditional coverage assignment rule t∗ (x) = g(x, β ∗ ). Given a Lagrange parameter β ≥ 0, we define ĝ(x, β) := argmax {θ̂(x, t) + βt}. t∈[0,1]

The value of β will be calibrated twice. In step 2, we will use Ilearn to find some β̂ that approximately satisfy the coverage to induce an reasonable max–min policy. In step 3, we use conformal inference to calibrate β again with Icalib , so the prediction sets satisfy the finite-sample coverage guarantee. 11

Step 2: learning the optimal policy. Using the learning fold {(Xi , Yi , Ai )}i∈Ilearn , we find the smallest β that satisfies an approximate average coverage constraint: o n P 1 ĝ(X , β) ≥ 1 − α . (4.1) β̂ := inf β ≥ 0 : |Ilearn i i∈Ilearn | Here, we set β̂ which estimates β ∗ by enforcing the estimated marginal coverage: E[t∗ (X)] = E[g(X, β)] ≈ Êlearn [ĝ(X, β)] ≥ 1 − α. This typically yields reasonable policies, though it does not necessarily come with any finite-sample guarantee. The resulting learned policy is then â(x) := â x, t̂(x) , where t̂(x) := ĝ(x, β̂). The key idea to disentangle the prediction sets and the induced policy is to fix the latter: in the next step, we calibrate the prediction sets within a class of sets whose max–min rules are â(·). Step 3: weighted conformal calibration. For calibration purposes, we only use labeled data 0 := i ∈ Icalib : Ai = â(Xi ) . For any whose logged action matches the learned policy action: Icalib 0 , we define the calibration score Si (β) := u(Ai , Yi ) − θ̂(Xi , ĝ(Xi , β)). Due to β ≥ 0 and i ∈ Icalib 0 and the test point (see, sampling under the behavior policy, there is a covariate shift from Icalib e.g., Lei and Candès (2021); Tibshirani et al. (2019)). This can be adjusted by the importance weights based on the known behavior policy (which can be estimated and plugged in if unknown): wi := π(â(Xi ) | Xi )−1 = π(Ai | Xi )−1 ,

wtest = π(â(Xtest ) | Xtest )−1 .

We then define the calibrated parameter ( P β ∗ := inf

β ≥ 0:

wi 1{Si (β) ≥ 0} 0 i∈Icalib P

wi + wtest 0 i∈Icalib

) ≥ 1−α .

Finally, the prediction sets are given by n o Ĉ(Xtest , â(Xtest )) = y ∈ Y : u(â(Xtest ), y) ≥ θ̂(Xtest , ĝ(Xtest , β ∗ )) n o Ĉ(Xtest , a) = y ∈ Y : u(a, y) ≥ γ̂(Xtest , ĝ(Xtest , β ∗ ), a) , ∀ a ̸= â(Xtest ).

(4.2)

(4.3)

Note that by definition â(Xtest ) = π̂RA (Xtest ); see Appendix B.9 for a formal proof. The entire procedure is summarized in Algorithm 1. Our method applies to finite and infinite label space. Compared with the usual weighted calibration (Tibshirani et al., 2019), we drop wtest in the numerator; such slight conservativeness avoids the enumeration of the label space y ∈ Y such as in Kiyani et al. (2025) and full conformal prediction (Vovk et al., 2005). When |Y| < ∞, enumeration is feasible and we discuss this below. Remark 4.1 (Exact calibration for finite label space). When |Y| < ∞, one may use n o Ĉ full (Xtest , â(Xtest )) = y ∈ Y : u(â(Xtest ), y) ≥ θ̂(Xtest , ĝ(Xtest , β full (y)) , n o Ĉ full (Xtest , a) = y ∈ Y : u(a, y) ≥ γ̂(Xtest , ĝ(Xtest , β0full ), a) , ∀ a ̸= â(Xtest ),

(4.4)

(y)

where β0full = maxy∈Y β full (y), and for each y ∈ Y, Stest (β) = u(â(Xtest ), y) − θ̂(Xtest , ĝ(Xtest , β)), ( β full (y) := inf

β ≥ 0:

(y) wi 1{Si (β) ≥ 0} + wtest 1{Stest (β) ≥ 0} 0 i∈Icalib

wi + wtest 0 i∈Icalib

) ≥ 1−α .

(4.5)

The theory of weighted conformal prediction (Tibshirani et al., 2019) implies valid coverage of (4.4) for Ytest (â(Xtest )), where â(Xtest ) coincides with the risk-averse policy for Ĉ full ; see Theorem 4.2. Theorem 4.2 shows that both prediction sets constructed above satisfy policy-coupled coverage guarantee. The proof is in Appendix B.9. Theorem 4.2. Denote the realized outcomes Ytest = Ytest (πRA (Xtest ; Ĉ)) for {Ĉ(x, a)}a∈A defined full in (4.3), and Ytest = Ytest (πRA (Xtest ; Ĉ full )) for {Ĉ full (x, a)}a∈A defined in (4.4). Then, we have full P Ytest ∈ Ĉ full (Xtest , πRA (Xtest ; Ĉ full )) ≥ 1 − α, and P Ytest ∈ Ĉ(Xtest , πRA (Xtest ; Ĉ)) ≥ 1 − α. Algorithm 1 Policy-Coupled Risk-Averse Conformal Prediction Input: Miscoverage level α ∈ (0, 1); utility u(·, ·); logged data {(Xi , Yi , Ai )}N i=1 ; test covariate Xtest . 1: Split indices into disjoint sets Itrain , Ilearn , Icalib . 2: Fit γ̂(x, t, a) on Itrain . // Nuisance estimation 3: Compute β̂ on Ilearn following (4.1). // Learn optimal policy // Weighted conformal calibration 0 = {i ∈ Icalib : Ai = â(Xi )} and define Si (β) := u(Ai , Yi ) − θ̂(Xi , ĝ(Xi , β)). 4: Set Icalib 0 5: Set weights wi = π(A 1| X ) for i ∈ Icalib and wtest = π(â(Xtest1) | Xtest ) . i i 6: Compute β ∗ as in (4.2) (or β full (y) in (4.5) if |Y| < ∞).

7: Compute Ĉ(Xtest , a) for a ∈ A based on (4.3) (or Ĉ full (Xtest , a) based on (4.4)).

Output: Risk-averse policy â(·) and prediction sets {Ĉ(Xtest , a)}a∈A (or {Ĉ full (Xtest , a)}a∈A ).

Simulation study

We first evaluate the proposed PC-RACP method on a synthetic decision-making task. The goal is to assess whether modeling the action-conditional outcome distribution improves the decision quality while maintaining the target coverage guarantee. Task and data generation process. The covariates X ∈ Rd are i.i.d. from a multivariate standard Gaussian distribution. Conditional on X, the logged action A is drawn from a softmax behavior policy πb (a | X). The outcome Y is then sampled from an action-dependent conditional distribution PY (a) | X for a = A, also parameterized by a softmax model. See Appendix C.1 for details. We set |A| = 3 and |Y| = 4. The utility function is y=0 y=1 y=2 y=3 a = 0 0.70 0.60 0.35 0.15 . u(a, y) = a = 1 0.95 0.55 0.45 0.15 a = 2 0.80 0.50 0.20 0.20 13

We also set umax = 1.00. This utility specification induces nontrivial trade-offs across actions and labels, making the quality of the prediction set directly relevant to decisions. We generate 30,000 i.i.d. samples in total, partition them into disjoint subsets (30% train, 20% learn, 20% calib, 30% test), and apply the methods to produce the learned actions and prediction sets. The experiments are repeated for N = 20 independent runs. Methods. We compare the proposed PC-RACP procedure with RAC (Kiyani et al. (2025)) and a Plug-in baseline. RAC constructs prediction sets from the marginal predictive distribution P(Y | X), without conditioning on the action. The Plug-in baseline learns the action-conditional model P(Y | X, A), but does not perform any calibration: it directly selects the action by maximizing the plug-in utility quantile and then forms the prediction set; it is detailed in Appendix C.2. Although the true behavior policy is known in the synthetic setup, we use estimated behavior policies whenever behavior-policy information is required, in order to mimic the logged-data setting and examine robustness to behavior-policy estimation error. In PC-RACP, we fit the models on the training split via multinomial regression, including the b | X) and outcome model P(Y b | X, A) which regresses Y on X using the behavior policy model P(A training samples with observed action A = a. In RAC, we ignore the actions and fit the marginal b | X) via a multinomial regression of Y on X using the training split; the predictive model P(Y pooled learn and calibration splits are then used for RAC calibration. The Plug-in method fits multinomial regression for each action a ∈ A in the pooled train, learn, and calib splits. In this way, the three methods use the same set of labeled data. Finally, in addition to the well-specified multinomial regression, we conduct the same set of experiments using the random forest classifier, while keeping the same data splits and model fitting protocol as above. Evaluation metrics. We vary the target miscoverage level over α ∈ {0.02, 0.04, . . . , 0.20}. For each test point Xi , PC-RACP and the Plug-in method output a learned action âi and a prediction set Ĉi = Ĉ(Xi , âi ). For RAC, the method outputs a prediction set Ĉi , and the action is then d = induced by âi = argmaxa∈A miny∈Ĉi u(a, y). We evaluate (i) the empirical coverage by Cov(α) P 1 i∈Itest 1{Yi (âi ) ∈ Ĉi } based on the sampled counterfactual outcomes, and (ii) the utility |Itest | P d min b u(âi , y) which serves as a valid lower bound for the certificate by Util(α) = 1 |Itest |

i∈Itest

realized utility when coverage is satisfied.

y∈Ci

Results. The simulation results are summarized in Figure 3. The empirical coverage in the left panel shows the tight coverage of PC-RACP for the outcomes under set-induced actions. However, RAC falls slightly below the target curve: it ignores the counterfactual nature, so the actions would induce a distinct distribution for the realized outcome compared with the marginal distribution of Y (A) mixed under the behavior policy. On the other hand, the Plug-in baseline fails to provide exact coverage, even though we expect the learned models are more accurate since more samples are used in model fitting; this shows the importance of decision-oriented conformal calibration for finite-sample coverage. The right panel of Figure 3 presents the average utility certificate for each method. PC-RACP consistently achieves the highest average utility certificate across α. Compared with the RAC method, this shows the benefit of policy-coupled inference in counterfactual settings. Compared with the Plug-in baseline which performs the worst, this shows the importance of calibration: even with a well-specified multinomial model, the learning step (which ensures approximate coverage

Utility vs. α

Coverage vs. α

1.00

0.55 0.50

Utility

Coverage

0.95

0.90

0.85

0.80

PC-RACP RAC Plug-in Target 1

0.45 0.40 0.35 0.30

−α

0.25 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

(a) Multinomial model: empirical coverage v.s. α.

(b) Multinomial model: average utility certificate v.s. α. Utility vs. α

Coverage vs. α

1.00

0.55 0.50

0.95

0.80

Utility

Coverage

0.45 0.90 0.85

PC-RACP RAC Plug-in

PC-RACP RAC Plug-in Target 1

PC-RACP RAC Plug-in

0.40 0.35 0.30 0.25

−α

0.20 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

(d) Random forest: average utility certificate v.s. α.

Figure 3: Simulation results across various miscoverage levels α. Top row show results when models are fitted by multinomial regression. Bottom row show results when models are fitted by random forests. Left column: coverage across different values of α, where the dashed line indicating the target level 1 − α. Right column: average utility certificate across different values of α.

before deriving the policy) and conformal calibration (which ensures exact finite-sample coverage) are still instrumental to realize higher utility. Overall, these results confirm the strong empirical performance of PC-RACP in both safety (coverage) and utility.

Hillstrom experiment

We next evaluate the proposed PC-RACP method on the Hillstrom email marketing dataset (Hillstrom, 2008) to investigate whether the utility gains observed in simulation persist in a real-data decision problem. This is a randomized experiment for e-mail merchandise campaign. In online marketing campaigns, different interventions (such as sending a promotion email versus not) lead to distinct customer behavior and downstream purchasing outcomes, so the counterfactual perspective is necessary and commonly adopted as the standard (Varian, 2016).

6.1

Experimental setup

Task, data preprocessing, and model training. The original treatment variable segment has three actions; for easier interpretation, we map it to a binary action space A ∈ {0, 1}, where A = 0 denotes No E-Mail and A = 1 denotes sending an email advertisement (merging Mens E-Mail and Womens E-Mail). The outcome is the binary label Y ∈ {0, 1}, where Y = 1 indicates a website visit and Y = 0 otherwise. We use five user features X = (recency, history, mens, womens, newbie) as the covariates. Here, recency and history are numeric-valued customer-history variables, while mens, womens, and newbie are binary variables for purchasing history of men and women products, and new customer. The behavior policy in Hillstrom is known: P(A = 0 | X) = 13 and P(A = 1 | X) = 23 due to the randomization. We set the utility function y=0 y=1 u(a, y) = a = 0 0.40 0.25 a = 1 0.10 0.90 to encode the objective of the email marketing task: emails should ideally be sent to users who are likely to visit the website after receiving them. Accordingly, the case (a = 1, y = 1) is assigned the highest utility, since it corresponds to a successful email campaign. The case (a = 1, y = 0) is assigned low utility because it represents an unsuccessful email and thus a wastage of resources. The case (a = 0, y = 0) receives relatively high utility, as refraining from sending an email is appropriate for a user who would not visit. The case (a = 0, y = 1) is also undesirable because it reflects insufficient intervention: a potentially responsive user is not contacted. This missed-opportunity case is treated as less harmful than sending an unnecessary email. We also set umax = 1.00. Methods and evaluation. The Hillstrom dataset contains n = 64,000 samples. We split the data into 30% train, 20% learn, 20% calib, and 30% test, following the same protocol as in the simulation study. On the training split, we fit the action-conditional outcome model P̂ (Y | X, A) and the marginal label model P̂ (Y | X) using CatBoost. For P̂ (Y | X, A), we train a separate model for each action a ∈ {0, 1}. We use the known logging policy given above.

We vary the miscoverage level α ∈ {0.02, 0.04, . . . , 0.20}. We report empirical coverage and average utility on the test set for each method. The average utility is computed in the same way as in the simulation study. Although the counterfactual outcomes are unknown, we can still construct an unbiased estimator for coverage; see Appendix C.3. 16

1.00

Utility vs. α

Coverage vs. α PC-RACP

PC-RACP RAC Target 1

0.45

−α Utility

Coverage

0.95

0.90

RAC

0.40

0.85

0.35

0.80

0.30 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

(a) Empirical coverage versus α.

(b) Average utility certificate versus α.

Figure 4: Results on the Hillstrom dataset. Left: empirical coverage across α. Right: estimated average utility certificate across α. PC-RACP consistently achieves higher utility than RAC while both methods keep empirical coverage close to the nominal target 1 − α.

6.2

Main results

The (estimated) empirical coverage and utility certificate are reported in Figure 4. Figure 4a shows that PC-RACP maintains empirical coverage close to the nominal level 1 − α across the full range of α. In contrast, RAC exhibits empirical coverage that is consistently above the target, indicating that it is more conservative than required. Figure 4b shows that PC-RACP consistently achieves higher utility than RAC. Together, these results show that the main simulation takeaway continues to hold on Hillstrom: explicitly modeling action-dependent outcome uncertainty can improve decision quality, while maintaining valid coverage for the realized outcome.

6.3

Where the utility gain comes from

We now zoom into the decisions produced by PC-RACP to analyze the utility gain over RAC. Let Â ∈ {0, 1} denote the decision produced by the methods. Although the general construction allows Ĉ = ∅, empty prediction sets do not occur in this experiment; hence we omit this case from the table below. For the nonempty prediction sets {0, 1}, {0}, and {1}, the above utility function gives the following values of miny∈Ĉ u(a, y) for each configuration of action a and prediction set Ĉ:

min u(a, y) = a = 0 y∈Ĉ a=1

Ĉ = {0} Ĉ = {1} Ĉ = {0, 1} . 0.40 0.25 0.25 0.10 0.90 0.10

(6.1)

Ignoring the counterfactual nature, RAC produces one single prediction set Ĉ, based on which the action is selected. The RAC-selected action is Â = 0, Â = 1, and Â = 0 for the three columns in (6.1). In contrast, PC-RACP constructs separate Ĉ(0) and Ĉ(1) for the two actions, so the selected action Â depends on the comparison of two cells in the two rows of (6.1). First, we examine the form of the prediction sets conditional on the selected action (for PCRACP we examine the prediction set for the selected action). Figure 5a shows that, for both 17

Prediction-set counts given action a=1

Prediction-set counts given action a=0

15000 10000

PC-RACP empty PC-RACP {0} PC-RACP {1} PC-RACP {0,1}

7500 5000

Count on test

12500 RAC empty RAC {0} RAC {1} RAC {0,1}

2500 0 0.025

0.050

0.075

0.100

0.125

0.150

0.175

3500 3000 2500 2000 1500 1000 500 0

PC-RACP empty PC-RACP {0} PC-RACP {1} PC-RACP {0,1}

0.025

0.200

0.050

RAC empty RAC {0} RAC {1} RAC {0,1}

0.075

0.100

0.125

0.150

0.175

0.200

(a) Prediction-set counts among test points with se- (b) Prediction-set counts among test points with selected action Â = 0. lected action Â = 1.

Figure 5: Prediction-set composition conditional on the selected action. For Â = 0, the prediction sets concentrate on {0} and {0, 1}. For Â = 1, the prediction sets are essentially all equal to {1}.

Rate of C = {0, 1} among selected A = 0 vs. α 0.8

Selected action A = 1 count vs. α

PC-RACP RAC

3500 3000

Count on test

Rate

0.6 0.4 0.2

PC-RACP RAC

2500 2000 1500 1000 500 0

0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200

(a) Fraction of Ĉ(X, Â) = {0, 1} among those Â = 0.

(b) Number of test points with final action Â = 1.

Figure 6: Left: in the small-α regime, among test points with Â = 0, PC-RACP produces prediction set {0, 1} for a substantially smaller fraction of cases than RAC. Right: in the large-α regime, PC-RACP selects more Â = 1 cases than RAC. methods, test samples with Â = 0 are assigned with prediction sets of the form {0} or {0, 1}. In contrast, Figure 5b shows that when the selected action is Â = 1, the prediction set always takes the form {1}. Thus, the sharpness of the utility certification relies on two factors: (i) how frequently the test samples are assigned to Â = 1, and (ii) when Â = 0, how frequently the prediction set takes the form {0} instead of {0, 1}. Figure 6 explains these two cases:

• For a small value of α, the comparison is driven mainly by the cases with Â = 0 (very few test points are assigned Â = 1 by both methods; see Figure 6b). Figure 6a shows that for these cases, the fraction of ambiguous sets {0, 1} produced by PC-RACP is substantially smaller than that produced by RAC, which leads to higher utility certificate: for action a = 0, the utility certificate is min{u(0, 0), u(0, 1)} = 0.25 when Ĉ = {0, 1}, whereas Ĉ = {0} gives a sharper utility certificate of u(0, 0) = 0.40.

• When α becomes larger, the mechanism changes. Figure 6b shows that PC-RACP assigns substantially more test points to the action Â = 1 than RAC, and the gap widens as α increases. This improves the utility because, as shown in Figure 5b, the prediction set for those Â = 1 is essentially always {1} with a high utility certificate u(1, 1) = 0.90. Hence, in 18

the large-α regime, action selection plays an important role in sharpness. Taken together, these figures show that the utility gain of PC-RACP comes from reducing conservativeness in two different ways. For small α, it is less conservative in prediction-set construction, more frequently producing sets of the form {0} for the dominant Â = 0 cases. For larger values of α, it is less conservative in action selection, assigning Â = 1 to more users than RAC.

Discussion We developed a decision-theoretic framework for predictive inference in counterfactual decisionmaking. The key challenge is that, when actions determine outcomes, the target of coverage is no longer fixed in advance. This makes ordinary validity notions insufficient for understanding how prediction sets should support downstream decisions. Our results identify policy-coupled coverage as the decision-relevant validity notion, where the coverage is evaluated on the potential outcome realized under the policy induced by the prediction sets themselves. For a given collection of peraction prediction sets, it justifies the counterfactual max–min rule for risk-averse decisions under distributional ambiguity. Furthermore, optimizing prediction sets under policy-coupled coverage is equivalent both to imposing universal policy coverage and to directly optimizing over policies and utility certificates. Thus, policy-coupled prediction sets form a lossless interface between uncertainty and action. Overall, our results suggest that uncertainty quantification in counterfactual problems should be designed around the decisions it supports. We view policy-coupled coverage as a first step toward a broader theory of decision-aware uncertainty quantification for counterfactual settings.

References Alaa, A. M., Ahmad, Z., and van der Laan, M. (2023). Conformal meta-learners for predictive inference of individual treatment effects. Advances in neural information processing systems, 36:47682–47703. Athey, S. (2015). Machine learning and causal inference for policy evaluation. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 5–6. Feuerriegel, S., Frauen, D., Melnychuk, V., Schweisthal, J., Hess, K., Curth, A., Bauer, S., Kilbertus, N., Kohane, I. S., and van der Schaar, M. (2024). Causal machine learning for predicting treatment outcomes. Nature Medicine, 30(4):958–968. Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika, 85(2):379–390. Foygel Barber, R., Candes, E. J., Ramdas, A., and Tibshirani, R. J. (2021). The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455–482. Gao, C., Zheng, Y., Wang, W., Feng, F., He, X., and Li, Y. (2024). Causal inference in recommender systems: A survey and future directions. ACM Transactions on Information Systems, 42(4):1–32. Hillstrom, K. (2008). The minethatdata e-mail analytics and data mining challenge.

Imbens, G. W. and Rubin, D. B. (2015). Causal inference in statistics, social, and biomedical sciences. Cambridge university press. Jin, Y., Ren, Z., and Candès, E. J. (2023). Sensitivity analysis of individual treatment effects: A robust conformal inference approach. Proceedings of the National Academy of Sciences, 120(6):e2214889120. Kakade, S. M. and Foster, D. P. (2008). Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 74(1):115–130. Kiyani, S., Pappas, G., Roth, A., and Hassani, H. (2025). Decision theoretic foundations for conformal prediction: Optimal uncertainty quantification for risk-averse agents. arXiv preprint arXiv:2502.02561. Lei, L. and Candès, E. J. (2021). Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):911–938. Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670. Manski, C. F. (2004). Statistical treatment rules for heterogeneous populations. Econometrica, 72(4):1221–1246. Rubin, D. B. (2005). Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American statistical Association, 100(469):322–331. Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. (2019). Conformal prediction under covariate shift. Advances in neural information processing systems, 32. Varian, H. R. (2016). Causal inference in economics and marketing. Proceedings of the National Academy of Sciences, 113(27):7310–7315. Vovk, V., Gammerman, A., and Shafer, G. (2005). Algorithmic learning in a random world, volume 29. Springer. Wang, T. and Dobriban, E. (2026). Optimal decision-making based on prediction sets. arXiv preprint arXiv:2602.00989. Yin, M., Shi, C., Wang, Y., and Blei, D. M. (2024). Conformal sensitivity analysis for individual treatment effects. Journal of the American Statistical Association, 119(545):122–135. Zhao, S., Kim, M., Sahoo, R., Ma, T., and Ermon, S. (2021). Calibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34:22313–22324. Zhu, Z., Kiyani, S., and Hassani, G. P. H. (2026). Conformal risk-averse decision making with action conditional guarantee.

General results with randomization

In the main text, we discuss the optimization problems for deterministic π, ν, and C under the assumption that the relevant maximizers are unique. Here, we expand the framework to full generality by allowing randomization of π, ν, and C, without assuming such uniqueness. Let Ξ, Ξ1 , Ξ2 ∼ Unif(0, 1) denote exogenous random seeds, independent of (X, {Y (a)}a∈A ). All maps below are assumed measurable. We consider a randomized policy mapping π : X × [0, 1] → A and a randomized utility mapping ν : X × [0, 1] → (−∞, umax ]. The extra randomness aims to smooth up the threshold conditions in the RA-DPO and RA-CPO problems.

A.1

Randomized RA-DPO

First, we introduce the corresponding randomized RA-DPO programs. Randomized RA-DPO (two seeds). max E ν(X, Ξ1 ) ν,π,L(Ξ1 ,Ξ2 )

s.t.

P(u(π(X, Ξ2 ), Y (π(X, Ξ2 ))) ≥ ν(X, Ξ1 )) ≥ 1 − α,

Ξ1 , Ξ2 ∼Unif(0, 1),

(RA-DPO-Rand-2)

(Ξ1 , Ξ2 ) ⊥ (X, {Y (a)}a∈A ).

Here, L(Ξ1 , Ξ2 ) denotes the joint law of the two uniform seeds. All the probabilities are taken over the joint distribution of (X, {Y (a)}a∈A ) and the exogenous random seeds. While it is natural to separately randomize the policy and the utility certificate, the above problem relying on two random seeds is equivalent to the problem with one seed governing both. This can be seen from the fact that a single Unif[0, 1] random variable can simulate any Borel probability distribution on [0, 1]2 , yet we include a formal statement in Theorem A.1 with proof in Appendix B.7. Randomized RA-DPO (single-seed). Consider the following optimization problem with one single seed: max E[ν(X, Ξ)] ν,π

s.t.

P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ) ≥ 1 − α,

Ξ ∼ Unif(0, 1),

(RA-DPO-Rand)

Ξ ⊥ (X, {Y (a)}a∈A ).

Hereafter, we focus on the single-seed RA-DPO-Rand problem as our RA-DPO problem of interest. We call a collection of measurable maps together with exogenous seeds attaining the optimum an optimal realization. Theorem A.1. Randomized RA-DPO (two seeds) and randomized RA-DPO (single-seed) are equivalent with each other. From any optimal realization (ν2 , π2 , Ξ1 , Ξ2 ) of Randomized RA-DPO (two seeds), we can construct an optimal realization (ν1 , π1 , Ξ) of randomized RA-DPO (singleseed) such that E[ν1 (X, Ξ)] = E[ν2 (X, Ξ1 )]. Vice versa, From any optimal realization (ν1 , π1 , Ξ) of randomized RA-DPO (single-seed), we can construct an optimal realization (ν2 , π2 , Ξ1 , Ξ2 ) of randomized RA-DPO (two seeds) such that E[ν1 (X, Ξ)] = E[ν2 (X, Ξ1 )].

Proposition A.2 further shows that for any randomized optimal solution π to RA-DPO-Rand, its dependence on ξ is through the value optimizer ν(x, ξ) paired with it. The proof is in Appendix B.8. Proposition A.2. Assume RA-DPO-Rand admits an optimal solution (ν, π). Then there exists an optimal solution (ν, π̃) such that ν(x, ξ) = ν(x, ξ ′ ) =⇒ π̃(x, ξ) = π̃(x, ξ ′ ),

∀x ∈ X , ∀ξ, ξ ′ ∈ [0, 1].

In particular, π̃(x, ξ) depends on ξ only through the value ν(x, ξ).

A.2

Randomized RA-CPO

Given prediction sets {C(X, a, ξ)}a∈A , we define the (random-seed-dependent) risk-averse policy πRA and reward νRA through πRA (x, ξ; C) := argmax a∈A

min

y∈C(x,a,ξ)

u(a, y),

νRA (x, ξ; C) := max

min

a∈A y∈C(x,a,ξ)

u(a, y).

(A.1)

We then analogously define the randomized versions of RA-CPO-1 and RA-CPO-2. Randomized RA-CPO-2 (uniform coverage over all randomized policies). Let C : X × A × [0, 1] → 2Y be a randomized prediction-set rule. Consider max

EX,Ξ [νRA (X, Ξ; C)]

s.t.

P(Y (π(X, Ξ)) ∈ C(X, π(X, Ξ), Ξ)) ≥ 1 − α, ∀ π : X × [0, 1] → A,

Ξ ∼ Unif(0, 1),

(RA-CPO-2-Rand)

Ξ ⊥ (X, {Y (a)}a∈A ).

Randomized RA-CPO-1 (coverage only along πRA ). max EX,Ξ [νRA (X, Ξ; C)] C

s.t.

P(Y (πRA (X, Ξ; C)) ∈ C(X, πRA (X, Ξ; C), Ξ)) ≥ 1 − α,

Ξ ∼ Unif(0, 1),

(RA-CPO-1-Rand)

Ξ ⊥ (X, {Y (a)}a∈A ).

Note that all these programs strictly generalizes the deterministic formulations.

A.3

Equivalence between randomized optimization problems

With randomization, RA-DPO, RA-CPO-1 and RA-CPO-2 remain equivalent (i.e., with the same optimal values). The following two theorems generalize the results in Section 3.1, with proofs in Appendix B.3 and Appendix B.2, respectively. Theorem A.3. RA-CPO-1-Rand and RA-CPO-2-Rand are equivalent in the sense of Theorem 3.2. Theorem A.4. RA-DPO-Rand and RA-CPO-1-Rand are equivalent in the sense of Theorem 3.1. Proposition A.5 generalizes Proposition 3.3, whose proof is in Appendix B.5. Proposition A.5. For a fixed feature X = x, a fixed seed Ξ = ξ and a coverage value t ∈ [0, 1], among all the prediction sets {C(x, a, ξ)}a∈A that satisfy P(Y (a) ∈ C(x, a, ξ) | X = x) ≥ t for every action a ∈ A, the following prediction sets has the largest risk averse utility νRA (·, ·; C) defined in (A.1): C(x, a, ξ) = {y ∈ Y | u(a, y) ≥ γ(x, t, a)} for every action a ∈ A. Further, we have νRA (x, ξ; C) = θ(x, t).

A.4

Reformulation of randomized RA-CPO

Like the discussion without randomization, RA-CPO-2-Rand is equivalent to the following optimization program: max

EX,Ξ [θ(X, t(X, Ξ))]

t:X ×[0,1]→[0,1]

(RA-CPO-2’-Rand)

s.t. EX,Ξ [t(X, Ξ)] ≥ 1 − α

In particular, if t∗ (x, ξ) is an optimal solution to RA-CPO-2’-Rand, then an optimal solution to RACPO-2-Rand is given by C ∗ (x, a, ξ) = {y ∈ Y | u(a, y) ≥ γ(x, t∗ (x, ξ), a)} for every action a ∈ A. Intuitively, in RA-CPO-2’-Rand, the function t(x, ξ) allocates the conditional (worst-case) coverage lower bounds across the (x, ξ) values so as to satisfy the coverage guarantee while maximizing the corresponding optimal objective θ(x, t(x, ξ)). For β ≥ 0 and x ∈ X , define the pointwise maximizer set n o S(x, β) := s ∈ [0, 1] : θ(x, s) + βs = max (θ(x, t) + βt) , t∈[0,1]

and its endpoints tlow (x, β) := inf S(x, β) and thigh (x, β) := sup S(x, β). The proof of Theorem A.6 is in Appendix B.6. Theorem A.6. Let X ∼ PX and let Ξ ∼ Unif(0, 1) be the independent exogenous random variable. Then there exist β ∗ ≥ 0 and a constant c ∈ [0, 1] such that ( tlow (x, β ∗ ), ξ ≤ c, t∗ (x, ξ) = thigh (x, β ∗ ), ξ > c, is an optimal solution to RA-CPO-2’-Rand and satisfies E[t∗ (X, Ξ)] = 1 − α.

Technical proofs

B.1

Proof of Theorem 2.1

Proof of Theorem 2.1. Write πRA (·) = πRA (·; C) and νRA (·) = νRA (·; C) for convenience. To prove Theorem 2.1, it suffices to show that inf P ∈F (C) ν(πRA , P ) = maxπ∈Π inf P ∈F (C) ν(π, P ). We first show that no policy can achieve a worst-case value larger than inf

x:C(x,πRA (x))̸=∅

νRA (x).

Let S := {x ∈ X : C(x, πRA (x)) ̸= ∅}. Since the prediction sets satisfy the coverage constraint along πRA , the set S is nonempty. Fix an arbitrary policy π ∈ Π. For any δ > 0, choose xδ ∈ S such that νRA (xδ ) ≤ inf νRA (x) + δ. x∈S

∗ ∈ C(x , π(x )) such that Since xδ ∈ S, choose ye ∈ C(xδ , πRA (xδ )). For any ε > 0, choose yπ,ε δ δ ∗ u(π(xδ ), yπ,ε )≤

inf

y∈C(xδ ,π(xδ ))

u(π(xδ ), y) + ε,

∗ whenever C(xδ , π(xδ )) ̸= ∅. If C(xδ , π(xδ )) = ∅, choose yπ,ε arbitrarily; under our convention inf y∈∅ u(π(xδ ), y) = umax , the same inequality holds since u ≤ umax .

∗ , setting Y (π Define Ω∗π,δ,ε by placing all mass on X = xδ , setting Y (π(xδ )) = yπ,ε e, RA (xδ )) = y ∗ and choosing the remaining potential outcomes arbitrarily. When π(xδ ) = πRA (xδ ), take ye = yπ,ε . Then Ω∗π,δ,ε Y (πRA (X)) ∈ C(X, πRA (X)) = 1,

so Ω∗π,δ,ε ∈ F(C). Under this distribution,

∗ ν(π, Ω∗π,δ,ε ) = u(π(xδ ), yπ,ε )

≤

inf

y∈C(xδ ,π(xδ ))

≤ max

u(π(xδ ), y) + ε

inf

a∈A y∈C(xδ ,a)

u(a, y) + ε

= νRA (xδ ) + ε ≤ inf νRA (x) + δ + ε. x∈S

Therefore, inf

P ∈F (C)

ν(π, P ) ≤ inf νRA (x) + δ + ε. x∈S

Letting δ ↓ 0 and ε ↓ 0, we obtain inf

P ∈F (C)

ν(π, P ) ≤

inf

x:C(x,πRA (x))̸=∅

νRA (x).

Since π ∈ Π was arbitrary, taking the maximum over π ∈ Π gives max

inf

π∈Π P ∈F (C)

ν(π, P ) ≤

inf

x:C(x,πRA (x))̸=∅

νRA (x).

(B.1)

In the next, we proceed to prove that the utility of πRA further upper bounds the right-handed side of (B.1). Consider any distribution P ∈ F(C), which obeys P (Y (πRA (X)) ∈ C(X, πRA (X))) ≥ 1 − α. Note that on the event Y (πRA (X)) ∈ C(X, πRA (X)), we have u(πRA , Y (πRA (X))) ≥

inf

y∈C(X,πRA (X))

u(πRA (X), y) = max

inf

a∈A y∈C(X,a)

u(a, y) = νRA (X).

The coverage guarantee P (Y (πRA (X)) ∈ C(X, πRA (X))) ≥ 1 − α thus implies P (u(πRA (X), Y (πRA (X))) ≥ νRA (X)) ≥ 1 − α. As such, νRA (·) is a feasible utility certificate for the policy πRA under P . Therefore, by the definition of ν(πRA , P ) as the maximum expected value over all feasible utility certificates, we have ν(πRA , P ) ≥ EX [νRA (X)] ≥

inf

x:C(x,πRA (x))̸=∅

νRA (x).

Now, by the arbitrariness of P ∈ F (C), we have inf

P ∈F (C)

ν(πRA , P ) ≥

inf

x:C(x,πRA (x))̸=∅

Combining (B.1) and (B.2), we obtain the desired result. 24

νRA (x).

(B.2)

B.2

Proof of Theorem 3.2 and A.3

The same construction proves both the deterministic and randomized statements. We therefore present only the randomized version. Proof of Theorem A.3. We use the function T (·) to denote the risk-averse objective of prediction sets, i.e., T (C) = EX,Ξ [νRA (X, Ξ; C)] for any {C(x, a; ξ)}a∈A . Step 1: From randomized RA-CPO-1 to randomized RA-CPO-2. We first show that for any optimal solution to randomized RA-CPO-1, there exists a feasible solution to randomized RA-CPO-2 with identical objective value. Let {C1∗ (x, a, ξ)}a∈A be an optimal solution to RA-CPO-1-Rand. For each feature x and random seed ξ, we denote the conditional coverage under the policy πRA (x, ξ; C1∗ ) as β(x, ξ) = P Y (πRA (X, Ξ; C1∗ )) ∈ C1∗ (X, πRA (X, Ξ; C1∗ ), Ξ) | X = x, Ξ = ξ . The feasibility of C1∗ implies E[β(X, Ξ)] ≥ 1 − α. We now define the prediction set ( C1∗ (x, a, ξ), if P(Y (a) ∈ C1∗ (x, a, ξ) | X = x, Ξ = ξ) ≥ β(x, ξ), C2 (x, a, ξ) = Y, if P(Y (a) ∈ C1∗ (x, a, ξ) | X = x, Ξ = ξ) < β(x, ξ). It is clear that for any policy π ∈ Π, we must have P(Y (π(X, Ξ)) ∈ C2 (X, π(X, Ξ), Ξ)) ≥ E[β(X, Ξ)] ≥ 1 − α. Therefore, {C2 (x, a, ξ)}a∈A is feasible for randomized RA-CPO-2.

On the other hand, by construction, we know C2 (x, a, ξ) = C1∗ (x, a, ξ) for a = πRA (x, ξ; C1∗ ). Therefore, νRA (x, ξ; C2 ) ≥ νRA (x, ξ; C1∗ ). Moreover, for any a ∈ A, the construction of C2 either keeps C1∗ (x, a, ξ) unchanged or replaces it by Y. In the latter case, inf u(a, y) ≤

y∈Y

inf

y∈C1∗ (x,a,ξ)

u(a, y).

Thus the worst-case utility associated with each action cannot increase when passing from C1∗ to C2 , and hence νRA (x, ξ; C2 ) ≤ νRA (x, ξ; C1∗ ). Combining the two inequalities, we have νRA (x, ξ; C2 ) = νRA (x, ξ; C1∗ ) for any value of (x, ξ). This further implies T (C2 ) = T (C1∗ ) and completes the proof of Step 1.

Step 2. Let OPT1 and OPT2 denote the optimal objective values of randomized RA-CPO-1 and RA-CPO-2, respectively. Note that the feasibility set of randomized RA-CPO-1 is a superset of that of randomized RA-CPO-2 since the constraint is weaker. As such, OPT1 ≥ OPT2 . On the other hand, Step 1 shows that for any optimal solution C1∗ to randomized RA-CPO-1, we can construct a feasible solution C2 to randomized RA-CPO-2 such that T (C2 ) = T (C1∗ ) = OPT1 . Therefore, OPT2 ≥ OPT1 . Combining the two inequalities gives OPT1 = OPT2 . Hence, the constructed C2 is an optimal solution to randomized RA-CPO-2. Moreover, for any optimal solution C2∗ (x, a, ξ) to randomized RA-CPO-2, since it is also feasible for randomized RA-CPO-1 and T (C2∗ ) = OPT2 = OPT1 , it must also be an optimal solution to randomized RA-CPO-1.

B.3

Proof of Theorem 3.1 and A.4

The deterministic proof follows the same argument as the randomized proof. For this reason, we present the randomized version only, since the deterministic formulation is recovered by taking π(x, ξ) = π(x) and ν(x, ξ) = ν(x). Proof of Theorem A.4. We show the equivalence in two steps. Step 1: From randomized RA-DPO to randomized RA-CPO-1. In this part, we aim to show that for any optimal solution (π ∗ , ν ∗ ) to randomized RA-DPO, there exists prediction sets {C1∗ (x, a, ξ)}a∈A feasible in randomized RA-CPO-1 with a no smaller objective value. Consider any feasible solution π ∗ (x, ξ), ν ∗ (x, ξ) to RA-DPO-Rand, which obeys PX,Ξ (u(π ∗ (X, Ξ), Y (π ∗ (X, Ξ))) ≥ ν ∗ (X, Ξ)) ≥ 1 − α, and maximizes the target function EX,Ξ [ν ∗ (X, Ξ)]. Then we build the prediction set ( {y ∈ Y | u(π ∗ (x, ξ), y) ≥ ν ∗ (x, ξ)}, a = π ∗ (x, ξ), ∗ C1 (x, a, ξ) = Y, a ̸= π ∗ (x, ξ). Since C1∗ (x, a, ξ) = Y when a ̸= π ∗ (x, ξ), we have P Y (πRA (X, Ξ; C1∗ )) ∈ C1∗ (X, πRA (X, Ξ; C1∗ ), Ξ) ≥ P Y (π ∗ (X, Ξ)) ∈ C1∗ (X, π ∗ (X, Ξ), Ξ)

= P(u(π ∗ (X, Ξ), Y (π ∗ (X, Ξ))) ≥ ν ∗ (X, Ξ)) ≥ 1 − α,

so C1∗ is feasible solution to randomized RA-CPO-1. On the other hand, note that for any (x, ξ), by definition max

inf

a∈A y∈C1∗ (x,a,ξ)

u(a, y) ≥

inf

y∈C1∗ (x,π ∗ (x,ξ),ξ)

u(π ∗ (x, ξ), y) ≥ ν ∗ (x, ξ).

Taking expectation of both sides, we have i h h ∗ u(π (X, Ξ), y) ≤ E max E[ν ∗ (X, Ξ)] ≤ E inf ∗ y∈C1 (X,π ∗ (X,Ξ),Ξ)

inf ∗

a∈A y∈C1 (X,a,Ξ)

i u(a, y) .

Step 2: From Randomized RA-CPO-1 to randomized RA-DPO. In this part, we show that for any optimal solution {C1∗ (x, a, ξ)}a∈A to randomized RA-CPO-1, there exists a feasible solution (π ∗ , ν ∗ ) to randomized RA-DPO with a no smaller objective value. Consider any optimal solution {C1∗ (x, a, ξ)}a∈A to RA-CPO-1-Rand. Then it must obey P(Y (πRA (X, Ξ; C1∗ )) ∈ C1∗ (X, πRA (X, Ξ; C1∗ ), Ξ)) ≥ 1 − α, and it maximizes the objective E[maxa∈A inf y∈C(X,a,Ξ) u(a, y)]. Define the policy and utility certificate π ∗ (x, ξ) = πRA (x, ξ; C1∗ ),

ν ∗ (x, ξ) = νRA (x, ξ; C1∗ ).

Note that by definition, Y (πRA (X, Ξ; C1∗ )) ∈ C1∗ (X, πRA (X, Ξ; C1∗ ), Ξ) implies u(π ∗ (X, Ξ), Y (π ∗ (X, Ξ))) ≥

inf

y∈C1∗ (X,π ∗ (X,Ξ),Ξ)

u(π ∗ (X, Ξ), y) = ν ∗ (X, Ξ).

This further implies P u(π ∗ (X, Ξ), Y (π ∗ (X, Ξ))) ≥ ν ∗ (X, Ξ) ≥ P Y (πRA (X, Ξ; C1∗ )) ∈ C1∗ (X, πRA (X, Ξ; C1∗ ), Ξ) ≥ 1 − α. As such, we know (π ∗ , ν ∗ ) are feasible solutions to randomized RA-DPO. On the other hand, by definition we know E[ν ∗ (X, Ξ)] = E[maxa∈A miny∈C1∗ (X,a,Ξ) u(a, y)], the (optimal) objective value of RA-CPO-1-Rand, thereby completing the second part. Finally, combining the two parts, we know that RA-DPO-Rand and RA-CPO-1-Rand are equivalent.

B.4

Proof of Property 1

We show that the upper quantile defined in (3.1) is right continuous. Property 1. The function q(α) = sup{z ∈ R | P(Z ≤ z) ≤ α} is right-continuous in α ∈ [0, 1). Proof of property 1. For α ∈ [0, 1) let Aα := {z ∈ R : F (z) ≤ α}, so that q(α) = sup Aα . If α ≤ β, then Aα ⊆ Aβ , hence q(α) = sup Aα ≤ sup Aβ = q(β). 27

Therefore q is nondecreasing. Fix α ∈ [0, 1) and let αn ↓ α. By monotonicity, the sequence q(αn ) is nonincreasing, hence the limit β := lim q(αn ) = inf q(αn ) n→∞

n≥1

exists in [−∞, ∞]. We claim that β = q(α).

First, since αn ≥ α we have Aα ⊆ Aαn for each n, and thus ∀n, q(α) = sup Aα ≤ sup Aαn = q(αn )

Taking the infimum over n yields q(α) ≤ β.

To prove the reverse inequality, assume for contradiction that β > q(α). Choose any z such that q(α) < z < β.

Because q(αn ) ↓ β, we have q(αn ) ≥ β > z for all n. By the definition of supremum, for each n there exists yn ∈ Aαn such that z < yn ≤ q(αn )

and

F (yn ) ≤ αn .

Since F is nondecreasing and z < yn , it follows that ∀n, F (z) ≤ F (yn ) ≤ αn Letting n → ∞ and using αn ↓ α gives F (z) ≤ α, i.e., z ∈ Aα . This contradicts z > sup Aα = q(α). Hence β ≤ q(α). Combining both inequalities, β = q(α), and therefore q(αn ) → q(α) whenever αn ↓ α. This proves that q is right-continuous on [0, 1).

B.5

Proof of Proposition 3.3 and A.5

Since the randomized problem is more general, we prove Proposition A.5 only. Proof of Proposition A.5. Consider any suite of prediction sets {C(x, a, ξ)}a∈A (with x and ξ fixed) that satisfy the coverage constraints P(Y (a) ∈ C(X, a, Ξ) | X = x, Ξ = ξ) ≥ t, This coverage guarantee implies P u(a, Y (a)) ≥

inf

y∈C(X,a,Ξ)

∀a ∈ A.

u(a, y) X = x, Ξ = ξ ≥ t

Then for any constant ϵ > 0, we know P u(a, Y (a)) ≤ inf u(a, y) − ϵ X = x, Ξ = ξ y∈C(X,a,Ξ) ≤ P u(a, Y (a)) < inf u(a, y) X = x, Ξ = ξ ≤ 1 − t, y∈C(X,a,Ξ)

which implies inf

y∈C(x,a,ξ)

u(a, y) ≤ Quantile+ 1−t [u(a, Y (a))|X = x]

by the arbitrariness of ϵ > 0. Taking maximum over a ∈ A on both sides yields max

inf

a∈A y∈C(x,a,ξ)

u(a, y) ≤ max Quantile+ 1−t [u(a, Y (a))|X = x] = θ(x, t), a∈A

which means θ(x, t) is an upper bound of νRA (x, ξ; C) for any prediction sets obeying the coverage constraints. We now define the prediction sets C ∗ (x, a, ξ) = {y ∈ Y | u(a, y) ≥ γ(x, t, a)}, for each a ∈ A. We first show that these sets satisfy the coverage guarantee. For any constant ϵ > 0, we note that P u(a, Y (a)) ≤ Quantile+ 1−t [u(a, Y (a)) | X = x] − ϵ X = x = P u(a, Y (a)) ≤ sup{z ∈ R | P(u(a, Y (a)) ≤ z | X = x) ≤ 1 − t} − ϵ X = x ≤ 1 − t. The arbitrariness of ϵ > 0 implies P(u(a, Y (a)) < Quantile+ 1−t [u(a, Y (a)) | X = x] | X = x) ≤ 1 − t. Equivalently, we have the coverage guarantee: for each a ∈ A, P(Y (a) ∈ C ∗ (x, a, ξ) | X = x) =P(u(a, Y (a)) ≥ Quantile+ 1−t [u(a, Y (a)) | X = x] | X = x) ≥ t. On the other hand, by construction we have νRA (x, ξ; C ∗ ) = max

inf

a∈A y∈C ∗ (x,a,ξ)

u(a, y) ≥ max γ(x, t, a) = θ(x, t). a∈A

Since θ(x, t) is an upper bound for νRA (x, ξ; C) for any prediction sets {C(x, a, ξ)}a∈A obeying the coverage guarantees, we know the above {C ∗ (x, a, ξ)}a∈A attain the optimal utility.

B.6

Proof of Theorem 3.4 and A.6

Here we prove the more general randomized version, Theorem A.6. The only difference is that Theorem 3.4 additionally assumes the maximizer is unique, thus inf S(x, β) = sup S(x, β) for PX a.s. x ∈ X . Theorem 3.4 can thus be proved by simplifying the proof below with tlow (x, β) = thigh (x, β). Intuitively, in RA-CPO-2’-Rand, the function t(x, ξ) allocates the conditional (worst-case) coverage across the (x, ξ) values so as to satisfy the coverage guarantee while maximizing the corresponding optimal objective θ(x, t(x, ξ)). We shall show that the given solution t∗ (x, ξ) is indeed optimal. Proof of Theorem A.6. Fix β ≥ 0 and define mβ (x) := sup {θ(x, s) + βs}. s∈[0,1]

For each x ∈ X , define the pointwise maximizer set n o S(x, β) := s ∈ [0, 1] | θ(x, s) + βs = mβ (x) , and its endpoints tlow (x, β) := inf S(x, β),

thigh (x, β) := sup S(x, β).

Since s 7→ θ(x, s) is left-continuous and nonincreasing on [0, 1], the set S(x, β) is nonempty and compact, so tlow (x, β) and thigh (x, β) are well-defined. Moreover, x 7→ mβ (x) is measurable, and the endpoint mapping x 7→ tlow (x, β) and x 7→ thigh (x, β) can be chosen to be measurable. We denote the optimal objective of RA-CPO-2’-Rand as OPT2 . In the following, we study the subgradients of the objective functions and establish the form of the optimal prediction sets.

Step 1: Weak duality upper bound for the randomized primal. Let T = t(X, Ξ) ∈ [0, 1] be any feasible randomized rule, i.e. E[T ] ≥ 1 − α. For every value of (x, s) we have mβ (x) = max {θ(x, u) + βu} ≥ θ(x, s) + βs. u∈[0,1]

Plugging in s = T and taking expectations on both sides, we have E[θ(X, T )] ≤ E[mβ (X)] − βE[T ] ≤ E[mβ (X)] − β(1 − α) = D(β), where we define D(β) := E[mβ (X)] − β(1 − α),

β ≥ 0.

Therefore, OPT2 ≤ inf D(β).

(B.3)

β≥0

Step 2: Existence of a dual minimizer. because

For each fixed x ∈ X , the map β 7→ mβ (x) is convex

mβ (x) = max {θ(x, s) + βs} s∈[0,1]

is a pointwise maximum of affine functions of β. Hence the function D(·) is convex on [0, ∞). Moreover, since θ(x, s) is bounded, there exists C < ∞ such that |θ(x, s)| ≤ C for all (x, s). Therefore, for any x ∈ X and β ≥ 0, we have mβ (x) ≥ θ(x, 1) + β · 1 ≥ −C + β, and consequently D(β) = E[mβ (X)] − β(1 − α) ≥ (−C + β) − β(1 − α) = −C + αβ −−−→ +∞. β→∞

This implies D is coercive on [0, ∞) and attains its minimum at some β ∗ ≥ 0. 30

Step 3: Subgradient of D and the attainable interval at β ∗ . This step consists of three parts: (3a) derive the pointwise subgradient of the mapping β 7→ mβ (x), (3b) derive the subgradient of the mapping β 7→ E[mβ (X)], and (3c) subdifferential of the mapping β 7→ D(β). (3a) Pointwise subgradient of mβ (x) on [0, ∞). We first show a pointwise Lipschitz bound in β. For every β, β ′ ≥ 0, mβ ′ (x) = max {θ(x, s) + βs + (β ′ − β)s} ≤ mβ (x) + |β ′ − β|, s∈[0,1]

and symmetrically mβ (x) ≤ mβ ′ (x) + |β ′ − β|. Hence |mβ ′ (x) − mβ (x)| ≤ |β ′ − β|.

(B.4)

In particular, β 7→ mβ (x) is continuous on [0, ∞).

We now proceed to study the subgradients of β 7→ mβ (x). By standard convex analysis results, a convex function f on [0, ∞), for every β > 0, the subgradients are given by ∂f (β) = [f−′ (β), f+′ (β)], and at the boundary, the subgradients are given by ∂f (0) = (−∞, f+′ (0)]. We apply this with f (β) = mβ (x), and calculate the one-sided derivatives. Right derivative. For h > 0 define qh+ (x) :=

mβ+h (x) − mβ (x) . h

For any s ∈ S(x, β), mβ+h (x) ≥ θ(x, s) + (β + h)s = mβ (x) + hs, so we have the lower bound qh+ (x) ≥ max s = thigh (x, β). s∈S(x,β)

(B.5)

On the other hand, for each h > 0, pick any element sh ∈ S(x, β + h). Then we have mβ+h (x) = θ(x, sh ) + βsh + hsh ≤ mβ (x) + hsh , because mβ (x) ≥ θ(x, sh ) + βsh . Hence qh+ (x) ≤ sh ≤ 1 for any h > 0.

Now take any sequence hk ↓ 0. By compactness of [0, 1], along a subsequence (still denoted) shk → s̄ ∈ [0, 1]. By (B.4), we have mβ+hk (x) → mβ (x), and clearly hk shk → 0, so θ(x, shk ) + βshk = mβ+hk (x) − hk shk −→ mβ (x). Since s 7→ θ(x, s) is nonincreasing and left continuous, we know lim sup θ(x, shk ) ≤ θ(x, s̄). k→∞

Indeed, if shk ≥ s̄ along a subsequence then monotonicity gives θ(x, shk ) ≤ θ(x, s̄) there; if shk < s̄ along a subsequence, then after taking a further subsequence we may assume shk ↑ s̄ and left continuity yields θ(x, shk ) → θ(x, s̄). Combining the two cases gives the desired inequality above. Since βshk → βs̄, mβ (x) = lim θ(x, shk ) + βshk ≤ θ(x, s̄) + βs̄, k→∞

which means s̄ ∈ S(x, β) is also a maximizer. Hence lim supk→∞ shk ≤ sup S(x, β) = thigh (x, β). Now, since we have shown that qh+k (x) ≤ shk , we get lim supk→∞ qh+k (x) ≤ thigh (x, β). Together with qh+ (x) ≥ thigh (x, β) in (B.5), we know qh+k (x) → thigh (x, β) for any sequence hk ↓ 0, i.e. (mβ (x))′+ (β) = thigh (x, β),

∀β ≥ 0.

Left derivative (interior points only). For any β > 0 and h ∈ (0, β) we define qh− (x) :=

mβ (x) − mβ−h (x) . h

First, for any s ∈ S(x, β), we have mβ−h (x) ≥ θ(x, s) + (β − h)s = mβ (x) − hs, so qh− (x) ≤ s for all s ∈ S(x, β), hence we have the upper bound qh− (x) ≤ tlow (x, β). On the other hand, for any h > 0, pick any element rh ∈ S(x, β − h). Then mβ (x) ≥ θ(x, rh ) + βrh = mβ−h (x) + hrh , so we have qh− (x) ≥ rh ≥ 0.

Now take any sequence hk ↓ 0 and (by compactness) extract a subsequence such that rhk → r̄ ∈ [0, 1]. Using (B.4), we have mβ−hk (x) → mβ (x) and hk rhk → 0 as k → ∞, hence θ(x, rhk ) + βrhk = mβ−hk (x) + hk rhk −→ mβ (x).

The same left-continuity and monotonicity argument as before then implies r̄ ∈ S(x, β). Since rhk ≤ qh−k (x) ≤ tlow (x, β) for all k, taking k → ∞, we get r̄ ≤ tlow (x, β). Meanwhile, as r̄ ∈ S(x, β) also implies r̄ ≥ inf S(x, β) = tlow (x, β), we know r̄ = tlow (x, β). Therefore rhk → tlow (x, β), and by the squeeze rhk ≤ qh−k (x) ≤ tlow (x, β) we conclude qh− (x) → tlow (x, β) as h ↓ 0, i.e. (mβ (x))′− (β) = tlow (x, β),

∀β > 0.

Putting two derivatives together. Putting the above two parts together, we know that for β > 0, the subgradient of β 7→ mβ (x) is given by ∂β mβ (x) = (mβ (x))′− (β), (mβ (x))′+ (β) = tlow (x, β), thigh (x, β) , (B.6) and at β = 0, ∂β m0 (x) = (−∞, (m0 (x))′+ (0)] = (−∞, thigh (x, 0)]. 32

(3b) Subgradient of F (β) := E[mβ (X)]. Fix any β ≥ 0 and define F (β) := E[mβ (X)]. By (B.4), for every h > 0, we have mβ+h (x) − mβ (x) mβ (x) − mβ−h (x) ≤ 1, and 0 ≤ ≤ 1 for h ∈ (0, β) when β > 0. h h Moreover, the pointwise limits of these quantities have been studied in (3a), namely, for β ≥ 0, 0≤

mβ+h (x) − mβ (x) −−→ thigh (x, β), h↓0 h

and for β > 0, mβ (x) − mβ−h (x) −−→ tlow (x, β). h↓0 h Therefore, by dominated convergence theorem, mβ+h (X) − mβ (X) F (β + h) − F (β) ′ F+ (β) = lim = E lim = E[thigh (X, β)], h↓0 h↓0 h h and for β > 0, mβ (X) − mβ−h (X) F (β) − F (β − h) = E lim F−′ (β) = lim h↓0 h↓0 h h

= E[tlow (X, β)].

Since F is one-dimensional convex on [0, ∞), for β > 0 we have ∂F (β) = [F−′ (β), F+′ (β)] = E[tlow (X, β)], E[thigh (X, β)] ,

(B.7)

and at β = 0 (boundary case), ∂F (0) = (−∞, F+′ (0)] = (−∞, E[thigh (X, 0)]].

(B.8)

(3c) Subdifferential of D and the attainable interval. Recall D(β) = F (β) − β(1 − α). Hence ∂D(β) = ∂F (β) − (1 − α). In particular, for β > 0, ∂D(β) = E[tlow (X, β)] − (1 − α), E[thigh (X, β)] − (1 − α) ,

(B.9)

∂D(0) = (−∞, E[thigh (X, 0)] − (1 − α)].

(B.10)

while at β = 0,

Since β ∗ minimizes the convex function D over [0, ∞), the 1D constrained optimality condition gives 0 ∈ ∂D(β ∗ ) + N[0,∞) (β ∗ ),

where we define the normal cone N[0,∞) (β ∗ ) = {0} if β ∗ > 0 and N[0,∞) (0) = (−∞, 0]. Using (B.9)–(B.10): • If β ∗ > 0, then 0 ∈ ∂D(β ∗ ), hence

1 − α ∈ E[tlow (X, β ∗ )], E[thigh (X, β ∗ )] .

• If β ∗ = 0, then ∂D(0) ∩ [0, ∞) ̸= ∅, which is equivalent to E[thigh (X, 0)] ≥ 1 − α. 33

Step 4: Construct an optimal (randomized) solution at β ∗ . solution that attains the optimal value D(β ∗ ).

We now construct an optimal

(4a) Lagrangian identity under pointwise optimality. Fix β ≥ 0 and let T = t(X, Ξ) satisfy T ∈ S(X, β) a.s. Then θ(X, T ) + βT = mβ (X) a.s., hence E[θ(X, T ) + βT ] = E[mβ (X)].

(B.11)

(4b) Achievable means via seed-mixtures of endpoints. Fix β ≥ 0 and write a− (β) := E[tlow (X, β)],

a+ (β) := E[thigh (X, β)].

If a− (β) = a+ (β), then any T with T ∈ S(X, β) a.s. satisfies E[T ] = a− (β) = a+ (β). Otherwise, for any target mean m ∈ [a− (β), a+ (β)], define ( tlow (x, β), ξ ≤ λ, a+ (β) − m ∈ [0, 1], tm (x, ξ) := λ := a+ (β) − a− (β) thigh (x, β), ξ > λ. Then Tm := tm (X, Ξ) satisfies Tm ∈ {tlow (X, β), thigh (X, β)} ⊆ S(X, β) a.s. and E[Tm ] = m. (4c) Apply (4a)–(4b) at β ∗ and prove optimality. By Step 1 and since β ∗ ∈ argminβ≥0 D(β), OPT2 ≤ inf D(β) = D(β ∗ ). β≥0

We now construct a feasible T ∗ that attains D(β ∗ ). First, if β ∗ > 0, then Step 3 gives 1 − α ∈ [a− (β ∗ ), a+ (β ∗ )], so (4b) provides a randomized solution T ∗ with T ∗ ∈ S(X, β ∗ ) a.s. and E[T ∗ ] = 1 − α. Then by (B.11), we have E[θ(X, T ∗ )] = E[mβ ∗ (X)] − β ∗ E[T ∗ ] = E[mβ ∗ (X)] − β ∗ (1 − α) = D(β ∗ ). Thus E[θ(X, T ∗ )] = OPT2 . On the other hand, if β ∗ = 0, then Step 3 gives E[thigh (X, 0)] ≥ 1 − α and we have tlow (X, 0) = 0 a.s., hence 1 − α ∈ [a− (0), a+ (0)] and step (4b) yields a randomized solution T ∗ with E[T ∗ ] = 1 − α and T ∗ ∈ S(X, 0) a.s. Then θ(X, T ∗ ) = m0 (X) a.s., so E[θ(X, T ∗ )] = E[m0 (X)] = D(0) = D(β ∗ ).

B.7

Proof of Theorem A.1

Lemma B.1 (Universal simulation from a single uniform seed). Let µ be any Borel probability measure on [0, 1]2 . There exists a Borel measurable map T : [0, 1] → [0, 1]2 such that if Ξ ∼ Unif(0, 1), then T (Ξ) ∼ µ. Moreover, if Ξ is independent of a random element Z, then T (Ξ) is also independent of Z. We use P1 to denote the single-seed optimization program and P2 to denote the two-seed optimization program, and their optimal objectives are OPT(P1 ) and OPT(P2 ), respectively. We prove the two inequalities OPT(P1 ) ≥ OPT(P2 ) and OPT(P2 ) ≥ OPT(P1 ). Through the proof, we can easily see that from any optimal realization of P1 , we can construct an optimal 34

realization of P2 and from any optimal realization of P2 , we can construct an optimal realization of P1 . Step 1: OPT(P1 ) ≥ OPT(P2 ). Let (ν2 , π2 , Ξ1 , Ξ2 ) be any feasible realization for P2 . Let µ denote the joint distribution of (Ξ1 , Ξ2 ) on [0, 1]2 . By Lemma B.1, there exists a Borel map T = (T1 , T2 ) : [0, 1] → [0, 1]2 such that for Ξ ∼ Unif(0, 1), d

(T1 (Ξ), T2 (Ξ)) = (Ξ1 , Ξ2 ). Since Ξ ⊥ (X, {Y (a)}a∈A ), Lemma B.1 also gives (T1 (Ξ), T2 (Ξ)) ⊥ (X, {Y (a)}a∈A ). Define the single-seed decision rules ν1 (x, ξ) := ν2 (x, T1 (ξ))

π1 (x, ξ) := π2 (x, T2 (ξ)).

Then the objective value is preserved: E[ν1 (X, Ξ)] = E[ν2 (X, T1 (Ξ))] = E[ν2 (X, Ξ1 )]. d

Likewise, the constraint probability is preserved by the distributional identity (T1 (Ξ), T2 (Ξ)) = (Ξ1 , Ξ2 ) together with independence from the data: P(u(π1 (X, Ξ), Y (π1 (X, Ξ))) ≥ ν1 (X, Ξ))

=P(u(π2 (X, T2 (Ξ)), Y (π2 (X, T2 (Ξ)))) ≥ ν2 (X, T1 (Ξ)))

=P(u(π2 (X, Ξ2 ), Y (π2 (X, Ξ2 ))) ≥ ν2 (X, Ξ1 )) ≥ 1 − α.

Hence (ν1 , π1 , Ξ) is a feasible realization for P1 and achieves the same objective value as (ν2 , π2 , Ξ1 , Ξ2 ) in P2 . Taking suprema over all feasible realizations (ν2 , π2 , Ξ1 , Ξ2 ) yields OPT(P1 ) ≥ OPT(P2 ). Step 2: OPT(P2 ) ≥ OPT(P1 ). Let (ν1 , π1 , Ξ) be any feasible realization for P1 . In the twoseed problem P2 , choose the admissible coupling Ξ1 = Ξ2 = Ξ where Ξ ∼ Unif(0, 1) and Ξ ⊥ (X, {Y (a)}a∈A ). This construction is admissible: it satisfies the marginal uniformity requirements for both seeds, and the two-seed program does not require the seeds to be independent of each other. Now define ν2 (x, ξ1 ) := ν1 (x, ξ1 )

π2 (x, ξ2 ) := π1 (x, ξ2 ).

Under Ξ1 = Ξ2 = Ξ, we have E[ν2 (X, Ξ1 )] = E[ν1 (X, Ξ)], and the constraint event coincides pointwise: u(π2 (X, Ξ2 ), Y (π2 (X, Ξ2 ))) ≥ ν2 (X, Ξ1 )

⇐⇒

u(π1 (X, Ξ), Y (π1 (X, Ξ))) ≥ ν1 (X, Ξ).

Therefore (ν2 , π2 , Ξ1 , Ξ2 ) is a feasible realization for P2 and attains the same objective value as (ν1 , π1 , Ξ) in P1 . Taking suprema over all feasible realizations (ν1 , π1 , Ξ) yields OPT(P2 ) ≥ OPT(P1 ). Combining the two inequalities gives OPT(P1 ) = OPT(P2 ). And through the proof, we can construct an optimal realization of P1 from an optimal realization of P2 and construct an optimal realization of P2 from an optimal realization of P1 . 35

B.8

Proof of Proposition A.2

Proof of Proposition A.2. Let (ν, π) be any optimal solution to RA-DPO-Rand. Define, for each x ∈ X , a ∈ A, and t ∈ R, p(x, a, t) := P u(a, Y (a)) ≥ t | X = x . Step 1: construct a non-randomized selector on each (x, t).

For each (x, t), let

a∗ (x, t) ∈ argmax p(x, a, t), a∈A

and break ties deterministically by choosing the smallest index. Then a∗ (x, t) is a deterministic map from X × R to A. Step 2: define a modified policy that is constant on ν-level sets. (x, ξ) ∈ X × [0, 1]. π̃(x, ξ) := a∗ x, ν(x, ξ) ,

Set

By construction, if ν(x, ξ) = ν(x, ξ ′ ), then π̃(x, ξ) = a∗ x, ν(x, ξ) = a∗ x, ν(x, ξ ′ ) = π̃(x, ξ ′ ), so π̃ satisfies the required non-randomization property. Step 3: show feasibility is preserved (coverage constraint not decreased). Consider the coverage probability under (ν, π): h i P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ) = E P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ) | X, Ξ . Fix (X, Ξ) = (x, ξ) and write t = ν(x, ξ) and a = π(x, ξ). Using the assumption Ξ ⊥ (X, {Y (a)}a∈A ), we have P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ) | X = x, Ξ = ξ = P u(a, Y (a)) ≥ t | X = x = p(x, a, t). Hence, P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ) = E p X, π(X, Ξ), ν(X, Ξ) . Similarly, for π̃ we obtain P u(π̃(X, Ξ), Y (π̃(X, Ξ))) ≥ ν(X, Ξ) = E p X, π̃(X, Ξ), ν(X, Ξ) . But by definition of π̃(X, Ξ) = a∗ (X, ν(X, Ξ)), p X, π̃(X, Ξ), ν(X, Ξ) = max p X, a, ν(X, Ξ) ≥ p X, π(X, Ξ), ν(X, Ξ) a∈A

a.s.

Taking expectations yields P u(π̃(X, Ξ), Y (π̃(X, Ξ))) ≥ ν(X, Ξ)

≥ P u(π(X, Ξ), Y (π(X, Ξ))) ≥ ν(X, Ξ)

so (ν, π̃) is feasible whenever (ν, π) is feasible. 36

≥ 1 − α,

Step 4: show optimality is preserved.

The objective in (RA-DPO-Rand) depends only on ν: E[ν(X, Ξ)].

We have not changed ν, so the objective value of (ν, π̃) equals that of (ν, π). Since (ν, π) is optimal and (ν, π̃) is feasible with the same objective value, (ν, π̃) is also optimal.

B.9

Proof of Theorem 4.2

Proof of Theorem 4.2. We first prove the results for Ĉ full (x, a) and β full (y) in Remark 4.1. Step 1: Risk-averse policy πRA (Xtest ; Ĉ full ) = â(Xtest ). y ∈ Y. Since ĝ(x, β) is non-decreasing in β, we have ĝ(Xtest , β0full ) ≥ ĝ(Xtest , β full (y)),

Recall that β0full ≥ β full (y) for all ∀y ∈ Y.

Moreover, by the monotonicity of θ̂(x, ·) (non-increasing in its second argument), it follows that θ̂ Xtest , ĝ(Xtest , β full (y)) ≥ θ̂ Xtest , ĝ(Xtest , β0full ) , ∀y ∈ Y. By the definition of θ̂(·, ·), we have θ̂ Xtest , ĝ(Xtest , β0full ) ≥ γ̂ Xtest , ĝ(Xtest , β0full ), a ,

∀a ∈ A

Therefore, for any a ̸= â(Xtest ), inf y∈Ĉ full (Xtest ,â(Xtest ))

u(â(Xtest ), y) ≥ inf θ̂ Xtest , ĝ(Xtest , β full (y)) y∈Y

= θ̂ Xtest , ĝ(Xtest , β0full ) ≥ γ̂ Xtest , ĝ(Xtest , β0full ), a =

inf

u(a, y),

y∈Ĉ full (Xtest ,a)

which implies πRA (Xtest ; Ĉ full ) = â(Xtest ) by definition. In the next, we prove the last equality: γ̂(Xtest , ĝ(Xtest , β0full ), a) = inf y∈Ĉ full (Xtest ,a) u(a, y). • First, if ĝ(Xtest , β0full ) = 0, then γ̂(Xtest , ĝ(Xtest , β0full ), a) = inf y∈Ĉ full (Xtest ,a) u(a, y) = umax by definition. • It remains to consider the case ĝ(Xtest , β0full ) > 0. Let m = inf y∈Ĉ full (Xtest ,a) u(a, y) and b q = γ̂(Xtest , ĝ(Xtest , β full ), a) = Quantile+ Here, Yb (a) full [u(a, Y (a)) | X = Xtest ]. 0

1−ĝ(Xtest ,β0 )

denotes a random variable generated from the fitted outcome model Pb(· | X = Xtest , A = a). By the definition of Ĉ full , it is straightforward to see that m ≥ q. Let ϵ = m−q 2 . If m > q, then there does not exist any y ∈ Y satisfying u(a, y) ∈ [q, q + ϵ]. In particular, P(u(a, Yb (a)) ≤ q + ϵ | X = Xtest ) = P(u(a, Yb (a)) < q | X = Xtest ) = lim P(u(a, Yb (a)) ≤ s | X = Xtest ). s↑q

By construction, we have q = Quantile+ [u(a, Yb (a)) | X = Xtest ] = sup{z ∈ 1−ĝ(Xtest ,β0full ) R | P(u(a, Yb (a)) ≤ z | X = Xtest ) ≤ 1 − ĝ(Xtest , β full )}. This implies P(u(a, Yb (a)) ≤ s | X = 0

Xtest ) ≤ 1 − ĝ(Xtest , β0full ) for any s < q. Therefore

P(u(a, Yb (a)) ≤ q + ϵ | X = Xtest ) = lim P(u(a, Yb (a)) ≤ s | X = Xtest ) ≤ 1 − ĝ(Xtest , β0full ), s↑q

which implies Quantile+ [u(a, Yb (a)) | X = Xtest ] ≥ q + ϵ, a contradiction. Hence 1−ĝ(Xtest ,β0full ) we must have m = q. Step 2: Coverage guarantee. Since π̂RA (·; Ĉ full ) = â(·) is obtained independent of the data in Icalib and Xtest , we view it as fixed hereafter. For notational simplicity, relabel {(Xi , Yi , wi ) : i ∈ 0 Icalib } as (X1 , Y1 , w1 ), . . . , (Xn , Yn , wn ), and set Xn+1 = Xtest , Yn+1 = Ytest (â(Xtest )), and wn+1 = (Yn+1 ) wtest . When the candidate label equals the true test label, abbreviate Sn+1 (β) := Sn+1 (β). Define the normalized weights wi pi := Pn+1

j=1 wj

i = 1, . . . , n + 1,

and the conformity scores Vi := 1 − 1{Si (β full (Yn+1 )) ≥ 0},

i = 1, . . . , n + 1.

0 , the samples First, under the known behavior policy π, conditional on the membership in Icalib {(Xi , Yi )}i∈I 0 are from the conditional distribution P(X, Y (â(X)) | A = â(X)). By Bayes’ rule, calib the density ratio between (Xtest , Y (â(Xtest ))) and these calibration samples is given by

dPXtest ,Y (â(Xtest )) 1 1 1 = = . (x, y) ∝ dPX,Y (â(X)) | A=â(X) P(A = â(X) | X = x, Y (â(X)) = y) P(A = â(X) | X = x) π(â(x) | x) That is, the samples {(Xi , Yi (â(Xi )))}n+1 i=1 are subject to a covariate shift with density ratio 1/π(â(x) | x). Therefore, they obey weighted exchangeability with weights given by {pi }n+1 i=1 (Tibshirani et al., 2019). We now proceed to show the desired coverage guarantee. By the definition of β full (y) in (4.2), we have Pn+1 n+1 full (Y X n+1 )) ≥ 0} i=1 wi 1{Si (β ≥ 1 − α, ⇐⇒ Quantile 1 − α; p δ Pn+1 i Vi = 0, i=1 wi i=1 where Quantile(β; P )= inf{z : P (Z ≤ z) ≥ β} is the quantile of a distribution P , and the “=” is because Vi ∈ {0, 1}. Consequently, by construction in (4.4), P Yn+1 ∈ Ĉ full (Xn+1 , â(Xn+1 )) = P(Vn+1 = 0) ! n+1 X = P Vn+1 ≤ Quantile 1 − α; pi δVi i=1

n X = P Vn+1 ≤ Quantile 1 − α; pi δVi + pn+1 δ+∞ i=1

≥ 1 − α, where the last inequality follows from Theorem 2 in Tibshirani et al. (2019). We thus complete the proof of the first part of Theorem 4.2. We now proceed to prove the second part of Theorem 4.2, i.e., the coverage guarantee of Ĉ in (4.3). Again, we first derive the risk-averse policy and then prove the coverage guarantee. Step 3: Risk-averse policy πRA (Xtest ; Ĉ) = â(Xtest ). We show that the risk-averse policy under Ĉ in (4.3) also coincides with â(·). Note that in (4.3), we have θ̂(Xtest , ĝ(Xtest , β ∗ )) ≥ γ̂(Xtest , ĝ(Xtest , β ∗ ), a) for any a ̸= â(Xtest ) by the definition of θ̂(·, ·). Therefore inf u(â(Xtest ), y) ≥ θ̂ Xtest , ĝ(Xtest , β ∗ ) y∈Ĉ(Xtest ,â(Xtest ))

≥ γ̂ Xtest , ĝ(Xtest , β ∗ ), a =

inf

u(a, y),

y∈Ĉ(Xtest ,a)

where the last equality follows by the same argument in Step 1. This implies the worst-case utility among Ĉ(Xtest , a) must be attained by a = â(Xtest ), thus πRA (Xtest ; Ĉ) = â(Xtest ). Step 4: Coverage guarantee via Ĉ(x, a) ⊇ Ĉ full (x, a). defined as in (4.5). Since P

wi 1{Si (β 0 i∈Icalib

(y) full (y)) ≥ 0} + w full (y)) ≥ 0} test 1{Stest (β

wi + wtest 0 i∈Icalib

For any fixed y ∈ Y, let β full (y) be P ≥

wi 1{Si (β 0 i∈Icalib P

full (y)) ≥ 0}

wi + wtest 0 i∈Icalib

we must have β ∗ ≥ β full (y) for all y ∈ Y by the definition of β full (y). Since ĝ(x, β) is non-decreasing in β for any x ∈ X , we know ĝ(Xtest , β ∗ ) ≥ ĝ(Xtest , β full (y)),

∀ y ∈ Y.

By the monotonicity (non-increasing) of θ̂(x, t) in the argument t, and the monotonicity (nonincreasing) of γ̂(x, t, β) in the argument t, this implies θ̂ Xtest , ĝ(Xtest , β ∗ ) ≤ θ̂ Xtest , ĝ(Xtest , β full (y)) , and γ̂ Xtest , ĝ(Xtest , β ∗ ), a ≤ γ̂ Xtest , ĝ(Xtest , β full (y)), a . Therefore, we know Ĉ full (Xtest , â(Xtest )) ⊆ Ĉ(Xtest , â(Xtest )). Since the risk-averse policies of the two suites of prediction sets coincide, we obtain the desired coverage guarantee for Ĉ(x, a) as well. This completes the proof of Theorem 4.2.

Numerical experiment details

C.1

Simulation data-generating process

We generate data from a linear-softmax environment with covariate space X = Rd , action space A = {0, 1, 2}, and label space Y = {0, 1, 2, 3}. In our experiments, we use d = 10. 39

First, the covariate vector is sampled as X ∼ N (0, Id ). Next, the logged action A is drawn from a behavior policy πb (a | X) defined by a multinomial softmax model. For each action a ∈ A, let ℓa (X) =

va⊤ X + ca √ , d

where the behavior-policy parameters are sampled independently as i.i.d.

i.i.d.

ca ∼ N (0, 0.52 ).

va ∼ N (0, Id ), Then πb (a | X) = P

exp(ℓa (X)) , a′ ∈A exp(ℓa′ (X))

A | X ∼ πb (· | X).

Finally, conditional on (X, A), the outcome Y is generated from an action-dependent multinomial softmax model. For each action a ∈ A and label y ∈ Y, define ⊤ ra,y (X) = 1.2 wa,y X + ba,y , where the outcome-model parameters are sampled independently as 1 i.i.d. i.i.d. wa,y ∼ N 0, Id , ba,y ∼ N (0, 0.52 ). d The conditional outcome distribution is exp(ra,y (X)) , y ′ ∈Y exp(ra,y ′ (X))

P(Y = y | X, A = a) = P

Y | X, A ∼ P(· | X, A).

For each simulation replicate, all behavior-policy and outcome-model parameters are sampled once using the replicate-specific random seed and then held fixed for all observations within that replicate.

C.2

Plug-in baseline

We describe the plug-in baseline used in the simulation. Unlike PC-RACP, this baseline does not include a learning step for a global coverage-allocation parameter and does not perform any conformal calibration for finite-sample exact coverage. Instead, it directly uses the fitted actionconditional outcome model Pb(Y | X, A) to choose an action and construct a prediction set based on the optimal formula in Theorem 3.3. Fix a target miscoverage level α ∈ (0, 1). After fitting the outcome model Pb(· | x, a) for the distribution of Y (a) conditional on X = x, the method computes the utility threshold: b b b γ̂(x, 1 − α, a) := Quantile+ α u(a, Y (a)) | Y (a) ∼ P (· | X = x, A = a) . 40

The baseline then chooses the action with the largest plug-in utility quantile: âplug (x, 1 − α) ∈ argmax γ̂(x, 1 − α, a), a∈A

and sets θ̂plug (x, 1 − α) := max γ̂(x, 1 − α, a). a∈A

The resulting plug-in prediction set is bplug (x, a) := y ∈ Y : u(a, y) ≥ γ̂(x, 1 − α, a) . C bplug ) = By the same argument as in Appendix B.9, the associated risk-averse policy is πRA (X; C âplug (X, 1 − α).

C.3

Evaluation in real data

Here we outline the consistent estimator for coverage and utility in the randomized experiment data in Section 6. Suppose our policy is â(X) and associated selected-action prediction set is Ĉ(X). Due to randomization, we know PXtest ,Ytest (t) | Ttest =t = PXtest ,Ytest (t) for t ∈ {0, 1}. The coverage can then be written as (viewing â and Ĉ as fixed) P(Ytest (â(Xtest )) ∈ Ĉ(Xtest )) h i = E 1{â(Xtest ) = 1, Ytest (1) ∈ Ĉ(Xtest )} + 1{â(Xtest ) = 0, Ytest (0) ∈ Ĉ(Xtest )} h i = E 1{â(Xtest ) = 1, Ytest (1) ∈ Ĉ(Xtest )} Ttest = 1 h i + E 1{â(Xtest ) = 0, Ytest (0) ∈ Ĉ(Xtest )} Ttest = 0 h i = E 1{â(Xtest ) = 1, Ytest ∈ Ĉ(Xtest )} Ttest = 1 h i + E 1{â(Xtest ) = 0, Ytest ∈ Ĉ(Xtest )} Ttest = 0 The last two quantities can now be estimated by sample averages in actually treated and actually control units in the test samples.

C.4

CatBoost Hyperparameters for the Hillstrom Experiment

For the Hillstrom experiment, we use CatBoost classifiers to estimate the conditional outcome distribution Pb(Y | X, A) and the marginal label distribution Pb(Y | X). The conditional outcome model Pb(Y | X, A) is fitted separately within each action group, using one CatBoost classifier for each value of A. The marginal label model Pb(Y | X) is fitted once on the pooled training data. All CatBoost classifiers are implemented using CatBoostClassifier from the Python library catboost. The CatBoost classifiers use the following hyperparameters: loss function = Logloss,

eval metric = Logloss,

depth = 6,

learning rate = 0.03,

iterations = 500, random seed = 0,

with verbose=False and allow writing files=False. No additional hyperparameter tuning is performed in the reported experiments. For the Hillstrom CatBoost experiment, we set the parameter standardize=False, since CatBoost can handle mixed numeric and categorical covariates directly and does not require feature standardization. 41

C.5

Random Forest Hyperparameters for the Simulation Experiments

In the experiments using Random Forests, we implement the base probabilistic classifiers with RandomForestClassifier from scikit-learn. For the simulation experiments, Random Forests are used to estimate the conditional outcome model, the behavior policy model, and the marginal label model. For the simulation experiments, the Random Forest classifiers use the following hyperparameters: n estimators = 200,

max depth = 14,

min samples leaf = 2,

n jobs = 1.

The random seed of each Random Forest model is matched to the seed of the corresponding experimental run. All Random Forest hyperparameters not explicitly specified, including the split criterion, feature subsampling rule, bootstrap sampling, and the minimum number of samples required for an internal split, are kept at their default scikit-learn values. No additional hyperparameter tuning is performed within the simulation scripts.

Record · ID 332539 · SHA-256 cf9cf06f363cec2b
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.