RISK-AVERSE DECISION MAKING WITH MULTI-LEVEL RELIABILITY GUARANTEES Amirmohammad Farzaneh and Osvaldo Simeone
ABSTRACT Many applications in engineering, including wireless broadcasting, require designs that provide performance certificates at different target outage levels. This paper studies the problem of maximizing the weighted average of such certificates in the presence of uncertainty about the true system state. The problem is shown to be equivalent to an optimization over nested prediction sets, connecting to the literature on conformal prediction and extending prior art on single-level risk-averse decision making. Furthermore, we derive a dual formulation that decouples optimization across input values. Numerical experiments on a diversity-based wireless transmission system illustrate the cost of enforcing multi-level certificates with a single shared policy and trace the Pareto trade-off between multiple reliability levels. Index Terms— Risk-averse decision making, conformal prediction, value at risk, graceful degradation, Lagrangian duality. 1. INTRODUCTION Decisions under uncertainty require not only good nominal performance, but also predictable behavior as conditions deteriorate. For example, a wireless broadcast system may need to serve users whose connecting conditions range from line-of-sight to blocked propagation [1]; a control system may face unexpected load spikes [2]; and a learned classifier may encounter distributionally shifted inputs [3]. The standard formulation for optimal decision making includes an agent that observes features X, selects an action a(X) without knowing the true state Y , and receives utility u(a(X), Y ). A risk-neutral policy maximizes expected utility, whereas a riskaverse policy also controls unfavorable outcomes, certifying a single utility level that is attained with probability at least 1 − α [4]. However, a certificate at a single outage level does not control the shape of the tail of the utility distribution. For example, as illustrated in Fig. 1, two policies that are indistinguishable at level α may behave very differently at a more stringent level, e.g., α/10. Taking inspiration from differentiated quality of service in telecommunications [5, 6], we study a single policy that supports K utility certificates ν1 (X) ≥ · · · ≥ νK (X) at outage levels α1 ≥ · · · ≥ αK . Each pair (νk , αk ) guarantees that utility νk (X) is attained in all but an αk -fraction of conditions. The ordering pairs stronger utility guarantees νk with more permissive outage levels αk and weaker guarantees νk with more stringent reliability requirements αk . Together, these certificates can enforce a form of graceful degradation in utility levels: the policy moves through
1.00
α2 = 0.02 α1 = 0.2
0.75 Certificate for policy B at level α2 = 0.02 Certificate for policy A at level α2 = 0.02
Pr[u ∏ v]
arXiv:2609.11524v1 [stat.ML] 10 Sep 2026
Institute for Intelligent Networked Systems (INSI), Northeastern University London, London, UK {a.farzaneh, o.simeone}@nulondon.ac.uk
0.50 0.25
Certificate for policies A and B at level α1 = 0.2
policy A policy B
0.00 0
1
2
utility u v
3
4
Fig. 1. Two utility distributions with matching utility certificates at outage level α1 = 0.2 but different utility certificates at the more stringent level α2 = α1 /10 = 0.02.
progressively relaxed, but still certified, service levels as conditions worsen. The single-level instance, i.e., K = 1, of the multi-level design problem described above was studied in [4], where value-at-risk optimization is shown to lead naturally to prediction sets and max–min decision rules. The role of prediction sets in the problem provides a formal justification for the use of conformal prediction as an uncertainty quantification strategy [7,8], as already proposed for a number of engineering applications [9, 10]. The framework in [4], however, does not extend directly to a setting with K > 1 levels, as applying it independently at each of the K outage levels would generally produce K different actions {ak (X)}K k=1 , and therefore would not define one deployable policy a(X) with graded guarantees. In Section 2, we formulate the multi-level risk-averse decision problem, and Section 3 derives a dual characterization decoupling optimization across input values. In Section 4, we establish an equivalent formulation based on K nested prediction sets, extending the single-level equivalence of [4] and providing a formal motivation for the use of nested conformal prediction [11–13]. Finally, Section 5 uses a diversity-based wireless transmission example to illustrate the compromise between certificates at different service levels.
2. PROBLEM FORMULATION Let (X, Y ) ∼ PXY denote the pair of agent’s observation X ∈ X and unobserved state Y ∈ Y. After observing X = x, the agent chooses an action a(x) ∈ A and receives utility u(a(x), Y ) ∈ [0, umax ] with umax < ∞. Assuming K service levels, fix maximum tolerated outage probabilities {αk }K k=1 satisfying the inequal-
ities 1 > α1 ≥ · · · ≥ αK > 0,
(1)
so that the required reliability 1 − αk increases with the service level k. For each service level k, we wish to identify a utility certificate νk : X → [0, umax ] meeting the target reliability 1 − αk , i.e., Pr[u(a(X), Y ) ≥ νk (X)] ≥ 1 − αk ,
(2)
where the certificates naturally obey the pointwise ordering ν1 (x) ≥ ν2 (x) ≥ · · · ≥ νK (x)
for all x ∈ X
(3)
By condition (3), larger utility certificates νk (x) are assigned to more permissive outage requirements αk . Definition 1 (RA-DPO(α)). For a vector of target outage probabilities α = (α1 , . . . , αK ) satisfying the inequalities (1), given a vector PK of non-negative weights {wk }K k=1 with wk ≥ 0 and k=1 wk = 1, the K-level risk-averse decision policy optimization (RA-DPO) problem is defined as
We then show that this problem can be addressed via a dual formulation that decouples across values of x. To start, define tk (x) = Pr[u(a(x), Y ) ≥ νk (x) | X = x]
as the reliability at service level k and input x, so that the constraint in (2) can be written as EX [tk (X)] ≥ 1 − αk , and the constraint (3) enforces the pointwise ordering t1 (x) ≤ · · · ≤ tK (x). For a given allocation tk (x) of outage levels, the largest utility that can be certified for action a is the conditional quantile Qtk (x) (x; a) = sup v ∈ [0, umax ] : Pr[u(a, Y ) ≥ v | X = x] ≥ tk (x) .
K X
a(·), ν1 (·),...,νK (·)
K X
s.t.
a(·), t1 (·),...,tK (·)
wk EX [νk (X)]
s.t.
k=1
Pr[u(a(X), Y ) ≥ νk (X)] ≥ 1 − αk , k = 1, . . . , K,
(4)
ν1 (x) ≥ ν2 (x) ≥ · · · ≥ νK (x), x ∈ X, and its optimal value is denoted as OPT(α). When K = 1 and w1 = 1, problem (4) corresponds to the single-level RA-DPO problem studied in [4]. For K > 1, the certificates {νk (x)}K k=1 cannot generally be optimized in isolation, since they all depend on the same action a(x) that needs to cater to all service levels. The next basic result connects problem (4) to its singlelevel counterpart, whose optimal value at outage level α is denoted as OPT(α). Lemma 1. The optimal value OPT(α) for RA-DPO(α) can be bounded as OPT(αK ) ≤ OPT(α) ≤
K X
wk OPT(αk ),
(5)
k=1
where OPT(α) is the optimal value of RA-DPO(α) with K = 1. The lower bound in (5) is the optimal value for the policy designed for the strictest reliability level αK only. In contrast, the upper bound allows every service level k to select its own action policy ak (X) and is therefore generally unattainable when one common policy a(X) must serve all levels. The next sections elaborate on the optimization of problem (4).
wk EX Qtk (X) (X; a(X))
k=1
EX [tk (X)] ≥ 1 − αk , k = 1, . . . , K,
(8)
0 ≤ t1 (x) ≤ · · · ≤ tK (x) ≤ 1, x ∈ X. Dualizing the constraints in (8), we now demonstrate that the maximization in (8) can be solved independently at each input x. To see this, let T = {t(x) ∈ [0, 1]K : t1 (x) ≤ · · · ≤ tK (x)}, so that the dual problem [14] for (8) can be written as K X wk Qtk (X) (X; a(X)) k=1 d(β) = EX max K a(X)∈A X t(X)∈T + β t (X) . min k k β≥0 k=1 K X − β (1 − α ) k k k=1
(9) Generalizing [4, Theorem 3.2], solving problem (9) is shown next to yield a solution also for problem (8). Theorem 1. Under the stated regularity conditions detailed in Appendix B, the dual problem (9) admits an optimal solution β ∗ ≥ 0, and an optimal solution for problem (8) can be found separately for each input x ∈ X as
3. DUAL FORMULATION Problem (8) jointly optimizes the K + 1 functions a(·), t1 (·), . . ., tK (·), whose values at different inputs are coupled by the expected coverage constraints. In this section, we recast (4) as a joint optimization over an action and a vector of local reliability allocations.
(7)
Substituting these expressions in the objective of (4), RA-DPO(α) can be equivalently stated as
max max
(6)
(a∗ (x), t∗ (x)) ∈ arg max a(x)∈A t(x)∈T
X K
wk Qtk (x) (x; a(x))
k=1
+
K X k=1
(10)
βk∗ tk (x)
.
4. PREDICTION-SET FORMULATION In this section, we show that problem (4) admits an equivalent formulation expressed in terms of K nested prediction sets Ck (x) ⊆ Y with C1 (x) ⊆ . . . ⊆ CK (x) (11) in the space of states Y. This view connects RA-DPO to nested conformal prediction [11–13], and gives the optimal decision rule produced by RA-DPO a worst-case, robust-optimization interpretation. Specifically, extending [4, Theorem 2.3], we have the following result. Proposition 1. RA-DPO(α) is equivalent to the problem " EX max
max
a∈A
C1 (·)⊆···⊆CK (·)
s.t.
K X
# wk
k=1
inf
u(a, y)
y∈Ck (X)
Pr[Y ∈ Ck (X)] ≥ 1 − αk ,
k = 1, . . . , K (12) in the sense that problems (4) and (12) have the same optimal value and optimal solutions for one problem yield optimal solutions for ∗ (x)) solves the other problem. Specifically, if (a∗ (x), ν1∗ (x), . . . , νK RA-DPO(α), then Ck∗ (x) = {y ∈ Y : u(a∗ (x), y) ≥ νk∗ (x)}
(13)
∗ (x)) solves (12), is optimal for (12). Conversely, if (C1∗ (x), . . . , CK then
a∗ (x) ∈ arg max a∈A
νk∗ (x) =
inf
∗ (x) y∈Ck
K X
wk
k=1 ∗
inf
∗ (x) y∈Ck
u(a, y),
u(a (x), y)
(14) (15)
solve RA-DPO(α). By (13), each optimal prediction set is a utility superlevel set, and the ordering of certificates makes these sets nested. Moreover, the optimal policy (14) selects an action that maximizes the weighted sum of its worst-case utilities over all K sets, with (15) providing the corresponding utility certificates. The proof is provided in Appendix A. 5. NUMERICAL EXAMPLE We illustrate the impact of graceful-degradation requirements on a wireless communication problem consisting of a two-channel diversity transmission system [15, 16]. The first channel is characterized by a power gain G1 ∼ Exp(1), corresponding to Rayleigh fading [16], while the second channel has power gain G2 ∼ Gamma(6, 1/6), corresponding to Nakagami-6 fading [16] and is occasionally blocked. The blockage indicator Z is partially known and distributed as Z | X = x ∼ Bern(q(x)) with q(x) = 0.85 + 0.05x, where X ∼ Unif[−1, 1] is side information about link availability. The variables X, G1 , and G2 are mutually independent, and the unobserved state is Y = (Z, G1 , G2 ). The action a(x) ∈ [0, 1] is the fraction of the power budget assigned
to the second channel. Upon maximum ratio combining [15], the combined channel gain is thus H(a, Y ) = (1 − a)G1 + κaZG2 ,
(16)
where κ = 11 dB reflects the higher nominal gain of the second channel, and the utility is given by the transmission rate u(a, Y ) = min log2 (1 + ρH(a, Y )), umax , (17) with ρ = 10 dB and umax = 8 bit/s/Hz. Overall, this setting models an always-available lower-gain channel, supplemented by a faster but blockage-prone channel. Conditional on the blockage Z, the channel gain H(a, Y ) is either a scaled exponential (Z = 0) or the sum of an exponential and an integer-shape Gamma variable (Z = 1). Based on this, the conditional quantile Qt (x; a) can be obtained by monotone numerical inversion for any fixed pair (x, a). To solve the dual problem (9), we approximate the continuous domains of x, a, and t using uniform grids containing 2001, 401, and 201 points, respectively, and pre-compute Qt (x; a) on the resulting grid. For each multiplier vector (β1 , β2 ), the pointwise maximization in (9) is solved exactly on these discrete grids. The ordering t1 ≤ t2 is handled using a cumulative maximization over the admissible values of t1 , avoiding explicit enumeration of every pair (t1 , t2 ). The multipliers are obtained by coordinate bisection over finite intervals whose upper endpoints were verified to satisfy EX [t∗k (X)] ≥ 1 − αk . We fix the first outage probability α1 = 0.15, corresponding to 85% coverage, and vary the second outage probability α2 ∈ {0.15, 0.10, 0.05, 0.03, 0.01}, corresponding to second-level coverages from 85% to 99%. We first set equal weights w1 = w2 to isolate the effect of tightening the second-level reliability requirement. As shown in Fig. 2, lowering the outage probability α2 tightens this requirement and therefore decreases the expected certificates EX [ν1 (X)] and EX [ν2 (X)]. We also show the independently optimized values OPT(α1 ) and OPT(α2 ), quantifying the cost of using one action to support both reliability levels, rather than optimizing either certificate in isolation (see Lemma 1). Varying the weights w1 and w2 traces the trade-off between the two expected certificates EX [ν1 (X)] and EX [ν2 (X)]. In Fig. 3, we fix the first outage probability α1 = 0.2, corresponding to 80% coverage, and fix different values for the second outage probability α2 ∈ {0.2, 0.15, 0.10, 0.05, 0.03, 0.01}. The figure highlights the price paid in terms of certificate EX [ν1 (X)] in order to increase the second level certificate EX [ν2 (X)]. Moreover, decreasing the outage probability α2 shifts each frontier downward, since the second certificate must hold at higher reliability. 6. CONCLUSION In this work, we have introduced a risk-averse decision framework in which a single action policy supports an ordered hierarchy of utility certificates. The formulation is shown to be equivalent to an optimization over nested prediction sets and admits a dual characterization with one scalar multiplier per service level. The resulting optimal policy lies between the strictest single-level solution and the weighted collection of independently optimized single-level solutions. A numerical example involving a diversity-based communication system illustrates how the shared action couples the two
The same inequality holds for an empty set under our convention, since νk (x) ≤ umax . Evaluating the objective in (12) at the original action a(x) therefore gives a value at least as large as the RA-DPO value. It follows that the RA-CPO optimum is no smaller than the RA-DPO optimum. Conversely, take any feasible nested family (C1 , . . . , CK ) and define a∗ and νk∗ by (14)–(15). Since Ck (x) ⊆ Ck+1 (x), taking the infimum over the larger set cannot increase the result; hence the induced certificates are ordered. Furthermore,
certificate (bit/s/Hz)
3.5 3.0 E[ν1 (X)] E[ν2 (X)] OPT(α1 ) OPT(α2 )
2.5 2.0 1.5 1.0 0.5 10−2
{Y ∈ Ck (X)} ⊆ {u(a∗ (X), Y ) ≥ νk∗ (X)}.
10−1
α2
Fig. 2. Expected certificates EX [ν1 (X)] and EX [ν2 (X)] at equal weights w1 = w2 for fixed outage probability α1 = 0.15 and varying α2 . The logarithmic horizontal axis increases from the most stringent second-level requirement α2 = 0.01 on the left to the equal-outage case α2 = α1 = 0.15 on the right. The dotted gray curve is the independently optimized single-level value OPT(α2 )
(20)
Thus the induced policy and certificates are feasible for RA-DPO. Their RA-DPO objective is exactly the RA-CPO objective of the original sets. The RA-DPO optimum is therefore no smaller than the RA-CPO optimum. Combining the two inequalities proves equality, and applying the constructions to optimal solutions gives the stated correspondences. B. PROOF OF THEOREM 1
EX [n2 (X)] (bit/s/Hz)
2.5
We proceed under the following regularity conditions: (i) X is a standard Borel space and PX is non-atomic; (ii) A ⊂ Rd is compact; and (iii) for PX -almost every x, the mapping (a, t) 7→ P k wk Qtk (x) (x; a) is upper semicontinuous on A × T and jointly measurable in (x, a, t). The utility u : A × Y → [0, umax ] is bounded as in Section 2. The argument follows the convexify–dualize–recover proof of [4, Theorem 3.2 and Appendix A.4], applied jointly to the ordered alP location vector. Write G(x, a(x), t(x)) = k wk Qtk (x) (x; a(x)) and introduce the hypograph correspondence [ Γ(x) = (t(x), r) : t(x) ∈ T,
a2 = 0.05 a2 = 0.03 a2 = 0.01
2.0
1.5
1.0
increasin
g w1
4.5
5.0
0.5 3.0
3.5
4.0
5.5
EX [n1 (X)] (bit/s/Hz)
a(x)∈A
Fig. 3. Supported Pareto frontiers of the expected certificates for fixed outage probability α1 = 0.20 and selected values of α2 . Along each frontier, the weight w1 increases from left to right. expected certificates. Developing more efficient methods for solving the pointwise problems, particularly for higher-dimensional applications, and constructing a distribution-free finite-sample calibration procedure for the full hierarchy are natural directions for future work. A. PROOF OF PROPOSITION 1 We prove equality of the optimal values in both directions. First, take a feasible RA-DPO solution (a, ν1 , . . . , νK ) and define Ck as in (13). The certificate ordering makes these sets nested, and {Y ∈ Ck (X)} = {u(a(X), Y ) ≥ νk (X)},
(18)
so every set satisfies the required marginal coverage. If Ck (x) is nonempty, then inf y∈Ck (x)
u(a(x), y) ≥ νk (x).
(19)
0 ≤ r ≤ G(x, a(x), t(x)) . Joint upper semicontinuity and compactness of A × T make Γ(x) compact-valued, while the stated measurability conditions ensure measurable selections [17, Theorem 14.37]. Its Aumann integral R S = Γ(x) dPX (x) is compact and, because PX is non-atomic, convex [18, Theorems 1, 3, and 4]. The reduced problem (8) is therefore equivalent to maximizing r over (m, r) ∈ S subject to m ≥ 1 − α. Every policy gives such a point, and a measurable action realizing the upper boundary can be selected in the reverse direction. Thus including the hypograph only adds dominated objective values and does not change the optimum. For any ε ∈ (0, mink αk ), the ordered constant allocation tk (x) = 1 − αk + ε is strictly feasible. Strong duality for this finitedimensional convex problem therefore yields multipliers β ∗ ≥ 0, primal feasibility EX [t∗k (X)] ≥ 1 − αk , and the complementaryslackness conditions βk∗ EX [t∗k (X)] − (1 − αk ) = 0 for k = 1, . . . , K. Maximizing the corresponding Lagrangian over S is equivalent to maximizing its integrand pointwise, and a measurable maximizing selection exists by the same regularity conditions. Selecting an action that attains the upper boundary of Γ(x) gives exactly (10). Finally, setting νk (x) = Qt∗k (x) (x; a∗ (x)) recovers the certificates that solve RA-DPO(α).
Acknowledgments This work was supported by the European Research Council (ERC) under the European Union’s Horizon Europe program (grant agreement No. 101198347). The work of O. Simeone was also supported by an EPSRC Open Fellowship (EP/W024101/1) and by the EPSRC project EP/X011852/1. C. REFERENCES [1] Roy Karasik, Osvaldo Simeone, and Shlomo Shamai Shitz, “Learning to broadcast with layered division multiplexing,” in 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 2696–2701. [2] Karl Johan Åström and Richard M. Murray, Feedback Systems: An Introduction for Scientists and Engineers, Princeton University Press, Princeton, NJ, 2008. [3] Joaquin Quiñonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence, Eds., Dataset Shift in Machine Learning, The MIT Press, 12 2008. [4] Shayan Kiyani, George J. Pappas, Aaron Roth, and Hamed Hassani, “Decision theoretic foundations for conformal prediction: Optimal uncertainty quantification for risk-averse agents,” in Forty-second International Conference on Machine Learning, 2025. [5] Dapeng Wu and Rohit Negi, “Effective capacity: a wireless link model for support of quality of service,” IEEE Transactions on wireless communications, vol. 2, no. 4, pp. 630–643, 2003. [6] Petar Popovski, Jimmy J Nielsen, Cedomir Stefanovic, Elisabeth De Carvalho, Erik Strom, Kasper F Trillingsgaard, Alexandru-Sabin Bana, Dong Min Kim, Radoslaw Kotaba, Jihong Park, et al., “Wireless access for ultra-reliable lowlatency communication: Principles and building blocks,” IEEE Network, vol. 32, no. 2, pp. 16–23, 2018. [7] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer, Algorithmic learning in a random world, Springer, 2005.
[8] Anastasios N Angelopoulos and Stephen Bates, “Conformal prediction: A gentle introduction,” Foundations and Trends in Machine Learning, vol. 16, no. 4, pp. 494–591, 2023. [9] Osvaldo Simeone, Sangwoo Park, and Matteo Zecchin, “Conformal calibration: Ensuring the reliability of black-box ai in wireless systems,” IEEE Communications Magazine, 2026. [10] Lars Lindemann, Yiqi Zhao, Xinyi Yu, George J Pappas, and Jyotirmoy V Deshmukh, “Formal verification and control with conformal prediction: Practical safety guarantees for autonomous systems,” IEEE Control Systems, vol. 45, no. 6, pp. 72–122, 2025. [11] Arun K Kuchibhotla and Richard A Berk, “Nested conformal prediction sets for classification with applications to probation data,” The Annals of Applied Statistics, vol. 17, no. 1, pp. 761– 785, 2023. [12] Eduardo Ochoa Rivera and Ambuj Tewari, “Online conformal prediction: Enforcing monotonicity via online optimization,” arXiv preprint arXiv:2605.12668, 2026. [13] Tiffany Ding, Isaac Gibbs, and Ryan J Tibshirani, “Calibrated multi-level quantile forecasting,” arXiv preprint arXiv:2512.23671, 2025. [14] Lieven Vandenberghe and Stephen Boyd, Convex optimization, vol. 1, Cambridge university press Cambridge, 2004. [15] David Tse and Pramod Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, Cambridge, UK, 2005. [16] Andrea Goldsmith, Wireless Communications, Cambridge University Press, Cambridge, UK, 2005. [17] R Tyrrell Rockafellar and Roger JB Wets, Variational analysis, Springer, 1998. [18] Robert J Aumann, “Integrals of set-valued functions,” Journal of mathematical analysis and applications, vol. 12, no. 1, pp. 1–12, 1965.