Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
Authors: Spyros Angelopoulos
Christoph Dürr
Georgii Melidi
Venue: ICLR 2026 Poster (2026)
Keywords: Learning-augmented algorithms
online algorithms
competitive analysis
performance evaluation metrics
decision theory
Primary area: optimization
TL;DR: The paper introduces novel deterministic and stochastic decision-theoretic metrics that guide the development of better learning-augmented online algorithms

Abstract: We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling.

Published as a conference paper at ICLR 2026
DECISION-THEORETIC APPROACHES FOR IMPROVED LEARNING-AUGMENTED ALGORITHMS
Spyros Angelopoulos
Christoph Dürr Sorbonne University, CNRS, LIP6 Paris, France
CNRS and International Laboratory
on Learning Systems
Montreal, Canada
Georgii Melidi
Sorbonne University, CNRS, LIP6 Paris, France
ABSTRACT
We initiate the systematic study of Drcision-thhorele metries in the design and analysis of algorithms with machine-leamee predictions. We introduce ap- proaches based on both deterministic measures such as distance-based evaluation, that help quantify how close the algorithm is to an ideal solution, and stochas- tie measures that balance the trade-off between the algorithm's 's performance and the risk associated with the imperfect oracle. These techniques allow us quan- tify the algorithm's 's performance across the full spectrum of the prediction error, and thus choose the best algorithm within entire class of otherwise incompa- rable ones. We apply our framework to three well-known problems from online decision making, namely ski rental, one-max search, and contract scheduling.
INTRODUCTION
The field of learning-augmenti computation has experienced remarkable growth recently. The focus, in this area, is on algorithms that leverage a machine-learned prediction on some key ele- ments of the input, based on historical data. The objective is to obtain algorithms that outperform the pessimistic, worst-case guarantees that apply in the standard settings. Online algorithms with ML predictions were first studied systematically in Lykouris & Vassilvtiskii (0118) and Purohit ct al. 8a) and since then, the learning- augmmentedd lens has been applied to numerous settings, in- cluding rent-or-buy problems (Gollapudi & Panigrahi] 2019), graph optimization (Azar al. (022))
secretaries (Atonniaiis et al. 2023), packing and covering (Bamas et al. 2020), and scheduling (Lat-
tanzi al. 2020). This only representative list; see the repository (Lindermayr & Megow 2025
major challenge in larmiig--uumenterd algorithms the theoretical analysis, and its interplay with the design considerations. Unlike the standard model, which focuses on the performance on worst- case inputs such as the competitive ratio (Borodin & El-Yaniv 1998), the analysis of algorithms with predictions multi-faceted, and involves objectives in trade-off relations. Typical desiderata require that the algorithm has good consistency (informally, its performance assuming perfect, error-free prediction) as well as robustness (i.e., performance under an arbitrarily bad prediction of unbounded error). Beyond these two extremes, there is an additional natural requirement that the algorithm's 's performance degrades smoothly as a function of the prediction error.
It is unsurprising that not all of the above objectives can always be attained and simultaneously optimized (Lavastida et al.) [222I. Such inherent analysis limitations have an important effect on the algorithm's 's design. One concrete methodology is to design algorithms that optimize the trade-off between consistency and robustness, often called Pareto -orretooptimalll algorithms; e.g. (Sun et al., 2021a
Lee al., 2024 Wei & Zhang] 2020 Christianson et al., (023). Another design approach to enforce smoothness, without quantifying explicitly the loss in terms of consistency or robustness, e.g., (Angelopoulos et al. 2022 Antoniadis et al. 2023).

---

Published as a conference paper at ICLR 2026
Each approach has its own merits, but also certain deficiencies. Pareto-optimalin may lead to al- gorithms that are britle, in that their performance may degrade dramatically even in the presence of imperceptible prediction error (Elenter et al. 2024). From practical standpoint, this drawback renders such algorithms highly inefficient. Even if brittleness can be avoided, one may obtain an entire class of Pareto-optimal algorithms, whose members exhibit incomparable smoothness (Beno- mar & Perchet, (2025). On the other hand, smoothness can often be enforced by assuming an upper bound on the prediction error, which can be considered, informally, the confidence in the predic- tion oracle or the tolerance to prediction errors. The design and the analysis are then both centered around this confidence parameter (Angelopoulos et al.] [022] Antoniadis et al., 2023). However, this approach leads to algorithms that may be inferior for large range of the prediction error, and notably when the prediction is highly accurate (i.e., the error small). It also requires either explicit knowledge or an ad-hoc choice of this confidence value.
We are thus confronted with the following central question: Among the many possible algorithms, each with its own performance function, how to choose the "best"? Here, the performance func- tion is the smoothness that interpolates between the extreme points of consistency and robustness. Answering this question hinges the choice of a principled measure for the comparison of perfor- mance curves, which is typically the purview of decision theory and the focus of this work.
Three classic problems: ski rental, one-max search, and contract scheduling. To demonstrate our framework, we consider three classic problems. Our first problem, namely ski rental, is classic formulation of rent-or-buy settings, and has served as proving grounds for learning-based algorith- mic approaches. Given unknown horizon of days, the decision-makee must decide which day to stop renting, and irrevocably buy the equipment. The best deterministic competitive ratio is the horizon length can help improve the competitive ratio, as has been shown in several works on this problem and its extensions (Angelopoulos et al., 22000 Purohit al. 2018b Wei & Zhang 2020 Khanafer al.) 2013 Gollapudi & Panigrahi| 2019 Wang et al.) 2020aa Zhao et al. 20024) Pareto-optimal algo-
2 (Karlin al. 1988) (assuming continuous setting), however a prediction
rithms were studied in Wei & Zhang (2020); Angelopoulos et al. (2020) Purohit et al. (201 8a). Furthermore, the recent work of Benomar & Perchet (2025) described parameterized class of al- gorithms, all of which are Pareto-optimal, but exhibit different, and incomparable smoothness.
A second problem that is fundamental in sequential decision making is one-max search, in which a trader aims to sell an indivisible asset. Here, the input sequence a of prices, and the trader must accept one of the prices in a irrevocably. The problem and its generalizations have a long history of study, see e.g. EI- Yaniv et al. (2001): Mohr et al. (2014); [lemmett et al. (2016); Dam- aschke et al. (2009); Lee et al. (2024) as well as Chapter 14 in Borodin & El- Yaniy (1998). The learning-augmentee augmented setting in which the algorithm leverages a prediction on the maximum price in was studied in Sun et al. (2021a), la), which gave Pareto-optimal algorithms. However, this algorithm suffers from brittleness (Elenter et al. 2024). AAneloopoloss et al. (2022) gave an algorithm with smooth error degradation, but no consistency/robuttesss guarantees, based tolerance parameter 5. However, this algorithm has inferior performance if the prediction is highly accurate.
Last, consider problem that is fundamental in real-time systems and bounded-resource reason- ing in AI, namely contract scheduling (Russell & Zilberstein 1991 Bernstein et al., 2003 López- Ortiz et 2014). Here, the aim to design a system with interruptible capabilities via executions of a non non- -on-interruptible algorithm. The performance of the system is measured by the acceleration ratio, i.e., the multiplicative loss due the repeated executions. [Angelopoulos & Kamali (2023b) studied the setting in which an oracle predicts the interruption time, and gave a Pareto-optima schedule. However, all Pareto-optimal algorithms are brittle, as shown in Flenter et al. (2024). ). As- suming tolerance 7 on the range of the prediction error, Angee:/Angooooullo & Kamali (2025)(2023b) also gave a schedule that has better smoothness, but is once again inefficient for small prediction error.
1.1 CONTRIBUTIONS
We present the first principled study of decision-theoretic approaches in learning augmented algo- rithms. Our objective is to be able to choose globally best algorithms based on objective, quantifiable methods. We introduce both deterministic and stochastic approaches: the former do not require any assumptions such distributional information on the quality of the prediction, whereas the latter
2

---

Published as a conference paper at ICLR 2026
help capture the notion of risk, which is inherently tied to the stochasticity of the prediction oracle. Specifically, we consider the following measures:
Distance measures We evaluate the distance between the performance of the algorithm, and an ideal solution, i.c. an omniscient algorithm that knows the input, but is constrained by the same robustness requirement the online algorithm. We focus on two distance metrics: i) The weighted maximum distance, which is defined as the weighted -norm distance between the performance function of the algorithm and that of the ideal solution; here, the weight is user-specified function that reflects how much, and what type of importance the designer assigns to prediction errors; and ii) The weighted average distance, which measures the aggregate distance between the algorithm and the ideal solution, averaged over the range of the prediction error.
Distance measures are inspired by tools such as Receiver Operating Characteristic (ROC) graphs (Fawcett 2006),, which describe the tradeoff between the true positive rates (TPR) and the false positive rates (FPR) of classifiers. Distanee metrics between two ROC curves have been used as comparison measure of classifiers. Moreover, weighted distances in ROC graphs can help empha- size critical regions: e.g., a user who is sensitive to false positives when FPR is low. This weighted approach has several applications in medical diagnostic systems (Li & Fine 2010
Risk measures Here, the motivation comes from the realization that Pareto-optimal and tolerance- based algorithms handle the risk of deviating from perfect prediction in totally different ways. Namely, the former maximize the risk, while the latter seek to minimize it. This explains undesir- able characteristics such their brittleness and inefficiency, respectively. To formalize the notion of risk, we first introduce a stochastic prediction setting, where the oracle provides imperfect dis- tributional information the algorithm. We then introduce novel analysis approach based on risk measure that has been influential in decision theory, namely the Conditional Value-at-Rise Risk, de- noted by CVaRa. This value measures, informally, the expectation of a random loss/reward on its (1 a) -frcctin of worst outcomes (Sarykalin et al. 2008). Here, a E [0, 1) is a parameter that measures the risk aversion of the end user. We show how obtain a parameterized analysis based on risk-aversion, which quantifies the trade-off between the performance of the algorithm and its risk.
Our techniques generalize previous approaches in in the context distance measures, by choosing the weight be equal to 1 only at the prediction point and zero otherwise, recover the Pareto-optimal algorithms. For the risk-based analysis, we obtain a generalization of the distributional consistency-robustees tradeoff's of Diakonikolas et al. 22221, by introducing the notion of a-consissenccy, where is the risk parameter.
algorithms. More precisely,
The paper is structured as follows. In Section 2, we formally present the decision decision-theoretie frame- work of our study, which we then apply to various problems. For ski rental (Section we show how to find, among the infinitely many Pareto-optimal algorithms, the one that optimizes our metrics. For one-max search (Section 4 we show how find, for any parameter r, an algorithm that likewise optimizes the metrics, among the infinitely many r-robust strategies. Last, for contract scheduling (Section(5), we show how find, among the infinitely many schedules of optimal acceleration ratio, one that Simultaneously optimizes each of our target metrics. In Section 6 we provide an experi- mental evaluation of our algorithms that demonstrates the attained performance improvements.
Other related work Elenter et al. (0024), addressed brittleness via a user-specified profile. This differs from our approach, in that our measures induce an explicit comparison to an ideal algorithm, and are thus true performance metrics, unlike Elenter et al. (2024) which does not allow for pair- wise comparison of algorithms. The conditional value-at-risk was recently used in Christianson et al. (2024) in the design and analysis of randomized algorithms without predictions; however, no previous work has connected CVaR to the competitive analysis of Baaming-augmenter algorithms.
2 DECISION-THEORREE MODELS
In this section, we formalize our decision-theoreee framework. For definiteness, we assume cost- minimization problems (e.g., ski rental), however note that the definitions can be extended straightforwardly to profit-maximization problems (c.g., one-max search and contract scheduling). We denote by OPT(a) the cost of an optimal offline algorithm input sequence
3

---

Published as a conference paper at ICLR 2026
2.1 DISTANCE- CETTANCE-BASED ANALYSIS
We focus on problems with single-valued predictions. We denote by I, some significant information on the input a, and by y R its predicted value. For instance, in one-max search, d is the maximum price in J. When a is implied from context, we will use æ for simplicity. The prediction error is defined as 7] Ig y). The range of prediction y. denoted by Rg. is defined as an interval Ry = [e. u| C [0, oo) such that Zo E Ry. This formulation allows to study algorithms with tolerance parameter. In particular, if Ry [[1 S)y, (1 + 8)y] where d E [0. 1]. then we refer to algorithms that operate under this assumption as d-tolerant algorithms. We emphasize that this assumption bounded prediction error not necessary in our framework, and unless specified, consider the general case R. [0, oc). Namely, we use this assumption be able to compare against known 6-tolerant algorithms.
Given online algorithm A, input and prediction y, denote by A(a, y) the cost incurred by A on Ø, using y. The performance ratio of A, denoted by pr o, y). is defined as the ratio Ala.s)
opT(a) We define the consistency (resp. robusiness) of A as its worst-case performance ratio given an error-free (resp. adversarial) prediction. Formally, CA) = sup, pr(A, 0,,,) and rob(A) = suPr. (r,A, y). We say that A is r-robust if it has robustness at most r.
To define our distance measures, we introduce the concept of an ideal solution. Given 2 1 and an input we define by (a) the smallest cost that can be achieved on by an online algorithm A that is required to be r-competitive on inputs. We also define pr(l,, σ) as OPT(a)) The definition implies that I, is the best-possibie Pareto-optimal algorithm with prediction Tg. Note that any r-robust online algorithm A with prediction y obeys pr o, y) pr(...
I.(o)
We can now define our distance measures starting with the maximum weighted distance. Here, the user specifies weight function Wy Rg [0, 1), which quantifies the importance that the user assigns to prediction errors, and aims to guarantee smoothness. To reflect this, we require that wy is piecewise monotone. Namely, if R, = [e, u),, then wy is non-decreasing in [f, y] and inniicceasing in [y, u]. The maximum distance an algorithm A, given y is defined as
dmux (A) = sup ((pr(A,o,z) pr([r,o)) (y)) o,EER,
(1)
Thus, the maximum distance measures the weighted maximum deviation from the ideal perfor- mance. We also define the average weighted distance, which measures the average deviation from the ideal performance, across the range of the prediction error. Formally:
1 |Ry JR,
/
dagg( = sup a
(pr(A, pr(Ir, (2)(2d
2.2 RISK-BASER ANALYSIS
Since risk an inherently stochastic concept, we need introduce stochasticity in the prediction model. To this end, we assume that the prediction is in the form of a distribution with support over an interval [e, u] C R. and pdf that is non-decreasing on [f. y] and non-increasing on (y. u). This model has two possible interpretations. First, one may think of fı as distributional prediction, in the lines of stochastic prediction oracles (Diakonikolas et al. 202 I). A second interpretation of μ is that of a prior on the predicted value, based on historical data. We will use R2 to refer to the range of μ. since it is motivated by considerations similar to the notion of range in the distance measures.
Our analysis will rely on the Conditional Value-at Risk (CVaR) measure from the theory of risk management (Rockafellar et al. (200).. Let be a random variable that corresponds to the loss [0, 1) that describes the
(e.g., the cost in the of minimization problem), and parameter risk aversion. The Conditional Value-at-Rin Risk CVaR,, is defined as
1 E[(x F[(x-1)+]] where (x- max ( 1,
CVaR, = inf
In words, (X) is the expectation of X on the a-tail of its distribution, that is, the worst (1 a) fraction of its outcomes. Let F denote the class of input distributions (i.e., distributions
4

---

Published as a conference paper at ICLR 2026
over sequences in which the predicted information has the same distribution μ.. For example, in one-mat max search, F is a distribution of input sequences such that the maximum price is distributed according to j.. Given [0, 1), we define the a-consistency of an algorithm A as
CVaR,, (((o))
a-cons(
sup FEF Eg [OPT()]
where the subscript in the notation of CVaR signifies that o is generated according to F. Our objective is then summarized as follows. Given a robustness requirement r, and risk parameter a, we would like to find an r-robust algorithm of minimum a-consistency.
This measure is risk-inclusive generalization of consistency, and interpolates between treme cases. The first case, when a = 0, describes a risk-seeking algorithm that aims to minimize its expected loss without considering deviations from the distributional prediction. In this case, CVaR,, = (tc=F(((r)) thus (4) is equivalent to the consistency of A in the distributional prediction model of Diakonikolas et (202I). The second case, when a + 1, describes risk averse algorithm: here, it follows that CVaRa,F(A) = SUPresupp(F) A(o). thus (4) describes the performance of A in the adversarial situation in which all the probability mass is concentrated on worst-case point within the prediction range. Note that this risk-based model is an adaptation of risk-sensitive randomized algorithms (Christianson et al. 2024) to
settings.
3 SKI RENTAL
We consider the continuous version, in that skis can be bought at any time in R. We denote by b 2 the buying cost, and by the skiing horizon that is unknown to the online algorithm. We denote by Ay the online algorithm that buys at time T, hence its cost, (r)x), is equal to x, if x < T, and b T. if 2 T. In the horizon. It is known that for r 2 2, Ar is r-robust iff T E [b/(r - 1), b(r - 1)]. Purohit et al. (2188) and Wei & Zhang (2020) showed that r-robust Pareto-optimal algorithms have consistency r/(r - 1). More generally, Benomar & Perchet (2025). gave a class of Pareto-optima algorithms, whose members exhibit different, and incomparable smoothness.
setting. the oracle provides a prediction on the
Objective: Given robustness requirement and prediction y on the number of skiing days, find T E b/(r-
1), b(r 1)] such that Ar minimizes the various objectives defined in Section 2 We will denote by T Taxx T and a the optimal thresholds according to the corresponding measures.
3.1 DISTANCE MEASURES
We begin by expressing the ideal performance.
Lemma (Appendix(A) The performance ratio of the ideal algorithm 1, is
1,
x < b,
pr pr(
if x b. min
r-1: b(r (or-1)}p/ 1)}]
br
- x 2 min
br F-I: b(r b(r-1)} 11}
For some intuition behind the proof, we distinguish between three cases. If x < b, then I, buys at b. If >> b, it buys at min r--1 b(r (1)]: and if 2 min { br TT b(r 1r-1) 1)} it buys at b/(r 1). These choices optimize its cost on input x. while guaranteeing r-robustness on all inputs. Note that (I,,,, has discontinuity at (r 1)6 only if ب 2 r- or < 2.618, approximately. For simplicity, will consider the case 2.618, for which the ideal performance is continuous, and we refer to the Appendix for a discussion of the case r E [2, 2.61818)
br
Figure illustrates the performance of the ideal algorithm (in black, bold line) and various online algorithms Ay. Note that all online algorithms have no better performance than the ideal on all inputs, expected, and that no online algorithm dominates the others.
We will distinguish between online algorithms that buy at times in [b/(r - 1), b), and those that buy at times in [b. b(r 1)]: we denote these classes by Czb and Cze. respectively. This distinction
5

---

Published as a conference paper at ICLR 2026
will be helpful in the computational optimization of the distance measures, namely in the proof of T given a prediction y with range Ry we have that
Theorem
From
(A_ATe) Ar(z) zER, min - pr((,,))) w(x).
dmax (AT)
sup
(5)
To gain some insight into the structure the maximum distance objective in (5). let us first consider the unweighted case, ie., w(x) 1. If Ry is unbounded, then d'max 1, which is attained by all Ar E C2b. Note that among these algorithms, As has the best consistency, so we may choose this algorithm tie-breaker.
That is, if we have no confidence on the quality of the prediction, the best algorithm is the competitively op- timal one, which agrees with intuition. If, however, Rg has known bounds, then the best algorithm depends on this range. For instance, if the right endpoint u of Ry smaller than b, then any algorithm the class C2b is optimal according to d This is consistent with all algorithms the class defined by Benomar Perchet 2025). It is also interesting note that regardless of the range Ry. the best algorithm according to dmax is either single algorithm in Ceb. namely As, choice of algorithms in Czs: this is precisely the set of all algorithms in Benomar & Perchet (2025). The fol- lowing theorem shows how to obtain the best threshold for the weighted distance.
Perfrmance rato
SkI scason longth
Figure 1:
Performance functions of r- robust algorithms for different threshold values. The curve in bold depicts the ideal performance ratio.
Theorem 2 (Appendix Aj. There is an algorithm for computing T Tass that runs in time linear in the number of critical points of the weight fanction w range Ry.
We now turn to the average distance objective, which from (2 equal
Ar(2,y) v) (avg(Ar) |Ryl (min(z,b)
- pI(( w(2) dz.
(6)
In the unweighted case (w 1), and without assumptions on Ry, Ap(--1) minimizes the average distance. This is because, for - its performance ratio matches the ideal, depicted by the blue curve in Figure [ When R, is bounded, the optimal algorithm depends the range, and the problem reduces to minimizing the area between the performance curves of Ar and 4, over Ry. For general weight functions, the integral in (6) is evaluated piecewise, depending on and T.
3.2 RISK-BASED ANALYSIS
We consider the CVaR- based analysis of ski rental. In this setting, the algorithm has access to distributional prediction μ over the skiing horizon æ. Following the discussion in Section 2.2 will evaluate an online algorithm Ar by means of its a-consistency 4
Define ęr Pr[Ar (x)
T
ST p(z)dz. With this definition in place, we obtain the
following result.
Theorem (Appendix A).
Let x ~ a and t" denote the a- a-quantile of μ. i.e., the value satisfying
Jo (x2) de a. Then
(Ar(z))(A(())) min { T-a (==(())) =m((2) dz (T () T+b. dr T T+b], (7) 1-a"
1
(f."
and T CvaR = arg mangmin M)-1)) CVaRa. [A(())]
Theorem capturrs the tradeoff between optimizing for average-case performance, on the one hand, and safeguarding against adversarial prediction, the other hand. Specifically, if 0, the

---

Published as a conference paper at ICLR 2026
objective reduces minimizing the expected cost, since Jpr 2-)((2) dz+ (b+T))-r 9r E Ee~uulAr A In contrast, if a + 1, then we consider two cases: T is such that qr > O, then from C [Ar())] = b + T, whereas if qr O, then C'VaR
(b+T)
(Ar [Ap(a)) = Hence, when CVaRa. ( [2) = min(b + T, u). The proof, and further details on these two extreme cases can
be found in Appendix
ONE-MAX SEARCH
In this problem, the input is a sequence of prices in [1, M), where M is known to the algorithm. We denote by F. the maximum price in a, or simply by x; when implied. Any online algorithm threshold algorithm, in that it selects some T E [1, M] and accepts the first price in that is at least T. such a price does not exist in Ø, then the profit the algorithm is defined to be equal to the smallest price, namely equal 1. We denote by Ar an online algorithm A with threshold setting, the online algorithm has
T. and by (a)) its profit on input ø. In the Barring--ugmeene access prediction y, and the prediction error is defined as 1/ = Dr y/
The optimal competitive ratio of the problem is equal v M El- Yaniv 1998). Moreover, for any VM, it is easy show that Ar is r-robust if and only T [4, /2). where M/r and t2 Thus, for any M,, there an infinite number of r-robust algorithms.
Objective. Given robustness requirement r. find the threshold T' that optimizes the measures of and TovaR the optimal threshold values.
Section We denote by Tmax. Th
4.1 DISTANCE MEASURES
We first describe the ideal solution.
Lemma (Appendix [). Given a robustness requirement v, and a sequence o, the ideal algorithm I, chooses the threshold min(t2, max((1, }o}). Its performance ratio is
To.
x E [1,t1)
pr(
1,
if [2]
i E (t2,
ta
From 1 and Lemma it follows that (Ar)((A)) sup (Ar(O) pr)( w(x).
We first give an analytical solution for unweighted maximum distance. We refer to Appendix for the proof, and some intuition about the following result.
Theorem 5. For uniform weights (w for all x E Ry [f, u]
min (12, max(ti, vūll, ifu Stt t2, min (12, max max(11, T}, otherwise,
T max
where T' = v (u 12 + 483u.
The case of general weight functions much more complex, from a computational standpoint. In Appendix B.2 we obtain formulation two-person zero-sum game between the algorithm (that chooses its threshold T) and the adversary (that chooses x). For instance, R, S (2), then the payoff function of this game max (max,27 (7 1) wxxx). max, (T 1) w(<x) In gen- eral, it is not possible to obtain an analytical expression of the value of this game (over deterministic strategies) for all weight functions, but the game can be solved analytically for relatively simple functions. For instance, in Appendix [B.2] we solve the game analytically assuming linear weight. The average weighted distance, on the other hand, can be optimized by piece- wise evaluation of an integral. We refer to the discussion in Appendix B.3 and example based on linear weights.
4.2 RISK-BASED ANALYSIS
We consider the setting in which the algorithm has access to a distributional prediction with support in [(1 8)y, (1 + 8)y], for some given 5. This assumption is not required, but it allows
7

---

Published as a conference paper at ICLR 2026
us to draw useful conclusions as discuss at the end of the section. Given robustness r, and risk value a E [0, 1), we seek an r-robust algorithm that minimizes the a-consistency. Since this is profit- maximization problem, the definitions of CVaR and a-consistency are slightly different
than (3 and 4 Namely, we have CV) = sup, { E-t [[][t-x)-]]
x) (Rockafellar et al.
2000) and (A) suP
BewF [OP((r)] CVaR,, ((((o)
We first show that the a-consistency is determined by a worst-case distribution F*, Here, F con- sists of sequences of infinitesimally increasing prices from 1 up to y, followed by last price equal to 1, where is drawn according to j..
Benu [ Lemma 6 (Appendix B). For any algorithm Ar it holds that a- c--Con((Ar)) CVuR,, er [Ar(
Since the numerator in the expression of Lemma is independent of the algorithm, it suffices to find the threshold T for which FV [o)) is maximized. This is accomplished in the following theorem. Define 9r = PTo-=- (Ar()- =
From the definition of F* and the fact that T is the threshold of A, it follows that @r [[1-5)y ppp)dp.
Theorem (Appendix Ba. Töva arg maxre(t T(1-a-97 2or)er (1 (1-8)=)
Theorem 7 interpolates between two cases. When O, the algorithm maximizes its expected profit, assuming that the maximum price in the input sequence has distribution μ. In this case, we find an r-robust algorithm of optimal consistency, under the distributional setting of Diakonikolas et al. (202T) which is a novel contribution for the one-max search problem by itself. When a + 1, the online algorithm must choose its threshold under the assumption that the maximum price is chosen adversarially within the support [e, u of p. hence the threshold (and the algorithm's 's profit) is l = d)y. This recovers the analysis of the d-tolerant algorithm in Angelopoulos et al. (002)).
CONTRACT SCHEDULING
We apply framework to the contract scheduling problem, defined in Section I Once again, the starting motivation is that there is an infinite number of schedules, all of which achieve an optimal robustness equal to 4 (Russell & Zilberstein 1991). We how to compute schedules that remain 4-robust, and provably optimize each of our metrics. Specifically, for maximum distance, the schedule is computed by considering the set of critical points (conceptually similar to Theorem 2 for average distance we derive a closed-form expression and optimize it numerically; and for CVaR we obtain an exact formula based on the predicted distribution. We also evaluate our schedules experimentally and observe that they outperform the state-of-th ooffthe-ant art Pareto-optimal and 8-tolerant schedules of Angeeloopsss Kamali (003b). We refer to Appendix for the detailed discussion.
EXPERIMENTAL EVALUATION
We evaluate our algorithms of Sections and which optimize the maximum and average distance as well as the CVaR. We refer to them as MAX, AVG and CVAR..
Baselines For ski rental, we compare to the class of algorithms BP, Benomar Perchet (2225)
BP, buys at time b/(r 1), if y 2 b, and at time p E [b, b(r 1)], otherwise. In our experiments we consider three possible values for the parameter p. namely p E {b, (r - 1)b, b + br o }. For one-max search we compare to two Pareto-optimal algorithms: The one Sf et al. (2021a), denoted by PO₁, and the more straightforward algorithm, denoted by PO, (Angelopoulos & Kamali, 2023a) that sets its threshold to T' = min max t1, y where t = M/rr and to = r. We also compare against the 8-tolerant algorithm of Angelopoulos et al. (2022). denoted by 5-TOL.
Datasets For ski rental, we set = 10 and r = 5. The prediction y is chosen such that ~ Unif b2], where 4. and the prediction range R, is set to [[1 8)g. (1 + 8)y] with 8 0.9. The horizon x is generated u.a.r. in Ry For one- max search, we set M = 1000 and r = 100, with y Unif[z, M/z] and 10, and the same definition of Ry. The input the worst-case sequence
8

---

Published as a conference paper at ICLR 2026
Table Experimental results for ski rental.
MAX
AvG
CVARa
BP
0.5
0.9
b br
Arg perf. ratio
1.344
1.337
1,340
1.349
1.367
1.677
2.187
2.219
CL./CI
+0.03/00.03
+0.03/0..33
+0.03/-0.03
+0.05/-0.05
+0.16/-0.17
+0.171-0.17
Exp. cost
11.241
11.187
11.173
11.215
11.316
16.987
21.234
20.958
+0.48-0.51
+0.49/-0.51
+0.50/-0.52
+0.48/-0.54
+0.48/-0.52
+0.99/-1.09
+2.01/-2.22
+1.951-2.00
Table 2: Experimental results for one-max search.
MAX
AvG
CVAR,
T.Tor.
PO₂
POg
0.5
0.9
Arg perf. ratio
4.394
4.447
9.771
8,144
6,022
10.009
4,630
15.685
CL_/CL_
+0.04/00.05
0.006/00.0
+0.26//D.26
+0.20V-0.20
+0.12//0.12
+0.00/-0.00
+0.06/-0.06
+0.45/-0.45
Exp. profit
15.614
20.528
35,795
34,402
27,500
5,475
13,904
27.986
CL_/CI
+0.30/-0.32
+0.50/-0.48
+1.06/1104
+1.00111.08
+0.81/-0.82
+0.151-0.17
+0.16/-0.17
+0.82/-0.80
of inereasing prices up to the maximum price followed by last price equal to 1, where is chosen u.a.r. in Ry. This is the standard class of inputs for evaluating worst-case performance (Sun) al. 2021a Blenter al. 2024). We refer to Appendix D for experimental results the parameters 2, as well as for experiments on real data for one-max search.
Evaluation For both problems, we compute the average performance ratio, over all Ry, and over 1000 repetitions on the choice of y. For MAX and AVG, we use the (uniquely defined) linear, symmetric function over Ry. whereas CVAR, evaluated under Gaussian distribution μ truncated to Ry and centered at y, with E (0.1, 0.9}. Furthermore, we compute the average expected cost/profit over μ for the two problems, respectively, where the averaging is over the choices of y- Tables [ and 2 show the obtained average performance ratios and expected costs/profits. The tables also report the 95% confidence intervals (CIs).
Discussion For the ski rental problem, all our algorithms achieve better performance ratios and average costs than the baseline BP,, for all choices the parameter, p. The performance ratios and average costs of CVAR, increase with as expected, since the higher the parameter the more the algorithm hedges against unfavorable outcomes.
For max search, the baseline algorithms show marked performance differences. This is due to the choice of thresholds, with 8-ToL and PO₂ tending to have the smallest and largest thresholds, respectively, whereas PO₁ chooses its threshold in between. Thus, PO₂ and 5-TOL. show high- est/lowest brittleness to prediction errors, respectively, whereas PO; is more balanced. MAX and AvG exhibit better performance ratios than all baselines and better expected profits, with the ex- ception of the highly brittle PO2. In regards to the CVAR class, once again the expected profit is decreasing with a, whereas the performance ratio improves as grows. We observe that CVaR algorithms considerably improve upon both 5-TOL and PO, across both metrics. They also have better average profit than РО₁, though worse performance ratio.
The experiments show that even with relatively simple weight functions and distance measures, distance- based algorithms offer considerable improvements over the state of the art. Moreover, CVaR approaches help obtain smooth tradeoffs between the expected cost/profit and the performance ratio, as function the risk parameter a, with improved overall performance the majority of the cases. In Appendix D report further experimental results that allow to reach additional conclusions on the impact of the various parameters in the setting. Specifically, as the prediction range becomes smaller, ments show that the performance of our algorithms improves. This is consistent with the theoretical motivation and analysis, since they better leverage information the quality of the prediction.
the weight function becomes more concentrated around y, the experi-

---

Published as a conference paper at ICLR 2026
7 CONCLUSION
We introduced new decision-theores approaches for optimizing the performance of learning- augmented algorithms, by taking into consideration the entire range of the prediction error. Fu- ture work can address further applications, e.g. generalized rent-or-buy problems such as multi- shop (Wang et al.) (2020b) and multi-option ski rental (Shin et al. (023). knapsack (Daneshvaramoli et al. 2024) and secretary problems (Antoniadis et al. (002)). Another direction involves problems with multi-valued predictions, such packing problems (Im et al. 2021 Our framework can still apply in these more complex settings, since the error is defined by a distance norm between the predicted and the actual vector. A last direction concerns dynamic predictions, in which the oracle is accessed several times during the algorithm's 's execution. An interesting potential application in -aggmeetd power management, given its connections to ski rental as shown
this domain in (Antoniadis et al., ).21).
Ethics Statement. This work introduces and studies theoretical measures for the design and analy- sis of learning-augmentt online algorithms. We do not anticipate any ethical concerns arising from this research.
Reproducibility Statement. Concerning the theoretical results, all complete proofs given in the Appendix. Concerning the experimental results, the full code and datasets can be downloaded at the https: // //o.ymoous. 4open. science w/r/decision theoretic codeeeoodeee 09E7/ The code is also available as supplementary material.
ACKNOWLEDGEMENTS
This work was supported by the grant ANR-23-CE48-0010 PREDICTIONS from the French Na- tional Research Agency (ANR).
REFERENCES
Spyros Angelopoulos and Shahin Kamali. Rényi-ulam games and online computation with im- perfect advice. In 48th International Symposium Mathematical Foundations of Computer Science, MFCS, volume 272 of LIPIcs, pp. 13:1-13:15. Schloss Dagstuhl Leibniz--entrum für Informatik, 2023a.
Spyros Angelopoulos and Shahin Kamali, Contract scheduling with predictions. J. Artif. Intell. Res., 77:395 2023b.
Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In Thomas Vidick (ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pp. 52:1-52:15. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.
Spyros Angelopoulos, Shahin Kamali, and Dehou Zhang. Online search with best-price and query- based predictions. In Proceedings of the 36th AAAI Conference Artificial Intelligence, pp. 9652-9660. AAAI Press, 2022.
Spyros Angelopoulos, Marcin Bienkowski, Christoph Dür,, and Bertrand Simon. Contract schedul- ing with distributional and multiple advice. In Proceedings of the 33rd International Joint Con- ference on Artificial Intelligence (IJCAI), 2024.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Learning- augmented dynamic power management with multiple states via new ski rental bounds. Advances in neural information processing systems,
2021.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online match- ing problems with machine learned advice. Discret. Optim., 48(Part 20:107778, 2023.
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Joseph (Seffi) Naor and Niv Buchbinder (eds.), Proceedings of the 2022 CCM-SIAM Symposium Discrete Algorithms, SODA, pp. 35-66. SIAM, 2022.
10

---

Published as a conference paper at ICLR 2026
Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. Advances in Neural Information Processing Systems, 33:20083 2020.
Ziyad Benomar and Vianney Perchet. On tradcoffs in learning-augmenttn algorithms. CoRR. abs/2501.12770, 2025. doi: 10.8550ARRXI.2501122777 URL https:://oi..rr/ org/10.. 18850/arXiv.250 20t..12211.11111
Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. Pareto-optimality, smoothness, and stochasticity in Saaming-auggenttn max-mch-s..rch. CoRR, abs/2502.05720), 2025. doi: 10-45550ARXX.255000522220 URL 2502. 057201
Daniel S. Bernstein, Lev Finkelstein, and Shlomo Zilberstein. Contract algorithms and robots on rays: Unifying two scheduling problems. Proceedings of the 18th International Joint Confer- ence on Artificial Intelligence (IJCAI), pp. 1211-1217, 2003.
Allan Borodin and Ran El- Ya-Yan.v. Online computation and competitive analysis. Cambridge Uni- versity Press, 1998.
Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistnncyy trade- offs for Baaming-augmente metrical task systems. In AISTATS, volume 206 of Proceedings of Machine Learning Research, pp. 9377-9399. PMLR, 2023.
Nicolas Christianson, Bo Sun, Steven H. Low, and Adam Wierman. Risk-sensitive online algorithms (extended abstract). In Shipra Agrawal and Aaron Roth (eds.), The Thirty Seventh Annual Con- ference on Learning Theory (COLT), volume 247 of Proceedings of Machine Learning Research, pp. 1140-1141. PMLR, 2024.
Jhoirene Clemente, Juraj Hromkovič, Dennis Komm, and Christian Kudahl. Advice complexity of the online search problem. In International Workshop on Combinatorial Algorithms, Springer, 2016.
Clobinatorrallggoorinnn,,, pp. 203-212.
Peter Damaschke, Phuong Hoai Ha, and Philippas Tsigas. Online search with time-varying price bounds. Algorithmica, 5544)6619-642, 2009.
Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowiez, Bo Sun, Cameron Musco, and Mohammad Hajiesmaili. Competitive algorithms for online knapsack with succinct predictions. arXiv preprini arXiv:2406.18753 2024.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning, pp. 2687-2696. PMLR, 2021.
Ran El-Yaniv. Competitive solutions for online financial problems. ACM Computing Surveys, 30 (1):28-69, March 1998. ISSN 0360-0300.
Ran El-Yaniv, Amos Fiat, Richard M Karp, and Gordon Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 3011):101-139 2001.
Alex Elenter, Spyros Angelopoulos, Christoph Dürr, and Yanni Lefki. Overcoming brittleness in pareto-optimal learning- -ugnentd algorithms. Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Tom Fawcett, An introduction to roc analysis. Pattern recognition letters, 27(8):861-87) 2006.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML, volume 97 of Proceedings of Machine Learning Research, pp. 2319-2327. PMLR, 2019.
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems, 34:2733-272 2021.
Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. Competitive snoopy caching. Algorithmica, 3:77-119, 1988. doi: 10.11077BF01762111. URL ://oo.
11

---

Published as a conference paper at ICLR 2026
Ali Khanafer, Murali Kodialam, and Krishna P. N. Puttaswamy. The constrained ski-rental problem and its application to online cloud cost optimization. In 2013 Proceedings IEEE INFOCOM, pp- 1492-1500, 2013. doi: 10.1 (009/NNFCOM.200...55550
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithmss, pp. 1859-1877. SIAM, 2020.
Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance-robust predictions for online matching. flows and load balancing. In 29th Annual European Symposium on Algorithms, ESA), volume 204 of LIPles, pp. 19:1-59:17, 2021.
Russell Lee, Bo Sun, Mohammad Hajiesmaili,, and John S. Lui. Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. In e-Energy, pp. 50-71. ACM, 2024.
Jialiang Li and Jason P Fine. Weighted area under the receiver operating characteristic curve and its application to gene selection. Journal of the Royal Statistical Society Series C: Applied Statistics, 59(4))673-692, 2010.
Alexander Lindermayr and Nicole Megow. Repository of works on algorithms with predictions. 01.
2025. Accessed: 2025-01-
Alejandro López-Ortiz, Spyros Angelopoulos, and Angele Hamel. Optimal scheduling of contract algorithms for anytime problem-solving. J. Artif. Intell. Res., 51:533-554 2014.
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pp. 3296-3305, PMLR, 2018.
Esther Mohr, Iftikhar Ahmad, and Günter Schmidt. Online algorithms for conversion problems:
survey. Surveys in Operations Research and Management Science, 19(2):87-104, 2014.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, volume 31, pp. 9661-9670, 2018a.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018b.
Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21-42, 2000.
Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pp. 212-217, 1991.
Sergey Sarykalin, Gaia Serraino, and Stan Uryasev. Value-at-risk vs. conditional value-at-rist in risk management and optimization. In State-of-the-art decision-making tools in the information- intensive age, pp. 270-294. Informs, 2008.
Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved algorithms for the multi-option ski rental problem via best-possible competitive analysis. In In- ternational Conference on Machine Learning, pp. 31539-33 31561. PMLR, 2023.
Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny H.K. Tsang. Pareto- optimal Barming-augmentt algorithms for online conversion problems. Advances in Neural In- formation Processing Systems, 11110339-13355 2021a.
Bo Sun, Russell Lee, Mohammad H. Hajiesmaili, Adam Wierman, and Danny H.K. Tsang- algorithms for online conversion problems. Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 10339 10339-10350,, 2021b. URL http://pppooeedddnneeeeeee.....p htt
Pareto-optimal
html]
12

---

Published as a conference paper at ICLR 2026
Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with ma- chine learned advice. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6- 12, 2020, virtual, 2020a. URL httppp:::pppcccedddittti neurips wwweerips.ccppppeeeeeee pccppapp//202/
Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances Neural Information Processing Systems, 33:8150 50--8100, 2020b.
Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for bearning-augmente online algorithms. In Proceedings of the 33rd Conference Neural Information Processing Systems (NeurIPS), 2020.
Hailiang Zhao, Xueyan Tang, Peng Chen, and Shuiguang Deng. Learning-augmented algorithms for the bahncard problem. Advances in Neural Information Processing Systems, 37:1 13234-113281 2024.
13

---

Published as a conference paper at ICLR 2026
Appendix
A DETAILS FROM SECTION 3
A.1 OMITTED PROOFS
Proof of Lemmal 7 First, recall that in order be r-robust, any algorithm must buy skis no later
than time b(r 1) and no earlier than b/(r - 1). We consider the following possible cases.
Case 1: < b. In this case. I, rents up to time b. This guarantees r-robustness, and since 1,(x) 2,, we have that pr(Tr, (r(,, 1.
Case 2: (b, min { hr
1--1 b(r 1)})
In this case, I, buys time min { br b(r - 1)} x, (x) z. This guarantees r-robustness, since the buy time lies in [b/(r 1), b(r 1)].
Now consider any r-robust algorithm Ar, then we consider two possible cases on T.
If < b, then Ar buys before b, and its cost is least that of Ab/(r-1), which is
br r
cost(Ab/(r-1) x))
+
If E (6, min { ( b(r 1) J1 then cost(Ar (AT, = '' I.
In both cases, cost( cost(AT, 2 (x) = x. Therefore, pr((,, = x/b is optimal among r-robust algorithms.
Case 3: min - b(r 1 1)}
1))-
In this case, 1, buys at time b/ 1), which satisfies r-robustness and its cost is
(x)
while the offline optimum is 6.
Now consider any other r-robust algorithm Ar. If > b/(r - 1), then cost(AA,2) = T
1-1 (x). If b/(r - 1), then Ar not r-robust.
Therefore, I, (z) has the minimum cost among all r-robust algorithms, and br
pr(Ir, = (r (r- 1)b
This completes the proof.
Proof of Theorem 2 For general weight functions w(x), recall that we assume that w is symmetric and piecewise monotone: i.e., non-decreasing for < y and non-increasing for y. The behavior of the maximum distance objective in (5) depends on the location of relative to b, and also on the buying threshold T. Recall from Lemma that 2r(
and is increasing for x > b. Thus, algorithms in the class Cep incur strictly positive distance in x < b, while algorithms from Os match the ideal in this interval, and may perform better when the weight concentrated around 6.
for
Given this structure, we partition the problem into two subproblems: computing the best threshold T among algorithms in Ces and the best threshold Tī in C. Once the buy times Tí' and T are computed, the final choice is
Tht max
arg min dmax (AT)
TE T
14

---

Published as a conference paper at ICLR 2026
Algorithm 1 Algorithm for computing Th max
Input: Prediction y with range Hy, weight w(x)), robustness buy cost Output: Optimal buy time max minimizing max distance.
Case Ceb
1:
Define critical set
S tv, bj 03 Rg de ((Ar1e) -1)w(z)) =0]
2: for T S1 do
3:
Compute Amax(Ar) t maxsER, ( 1) (2))()))
4:
end for
T < arg minresi (AT)((AA)
Case 2: T E C2b
6:
Define critical sel
t {vs b, br T-T1 b(r Ry ds (( pr((., :)) -00)))))0 =0}
7: for T S2 do
Compute Aana((Ar) t- maxsER, ( AT.2) -
9: end for
10: T2 arg minres, Sq (AT)
11: return Tmax +- arg min denax (Arz), ) diaax (Arz))
Algorithm shows how to compute max- The algorithm evaluates finite set of buy times based critical points, which are values of x where the weighted distance function may reach its maximum. These include the prediction y, the point x b. the values --r and 6(r 1), and all solutions the equation where the derivative of the weighted distance is zero.
Proof of Theorem We use the cost-minimization version of the Conditional Value-at-Risk, given by
| b(r b - 1)} and let μ denote the predicted skiing horizon. Let M(t) ==
Fix T
So ((2)dd de be the cumulative distribution function, and qr M(T) be the probability of the horizon being at least T. The cost of algorithm Ar is
h< T, T b,
I
Ar(x)
T.
We evaluate (Ar(o.)(AArr)) by considering three possible ranges of in the definition above.
Case 1: t < T. this case,
r 1
1 < T x > T I < t.
(x) =
T+b-1 I
0,
Multiplying the CVaR expression by (1 a) gives
(2- (2z L m(z)
(1 - ar) CVaR. inf (1 ax)( +
150
(1 att + 1==
inf t00
(11- 19)
Differentiating p with respect gives
(1 (1 - M() = -M( a
Since the second derivative of 9 equals p(t) > the minimizer is any t" satisfying M(t") = a.
If M is continuous and strictly increasing, then /" M-1(a) is unique. Substituting 1" and using
15

---

Published as a conference paper at ICLR 2026
1 - M(t*) yields
(VaRa(Ar(T)) 1- (1. ==(())d + +oaa++T++0 (T+ qT
(10)
Case 2: T st Here (Ar(x) +)+ for T and (T
for x 2 T. Since 3
is linear in f, the minimum occurs at one of the endpoints of the range of t. As result, we have
(VrRa(Ar(e)) min { T
{
2r
T + b)
(11)
1 1-a"
Case 3: T'+. b. In this range (Ar(x) 0 for all so the infimum is attained at t T + yielding
(AaR)(Ar(=)) = T
Combining the above cases, CVaRo,, (x))))] the minimum between 110) (Case 1) and 11 (Case 2), which completes the proof.
Analysis of extreme cases.
(i) For = O, we have t" = inf supp(u) = From I0
(VrRo(AA(z)) = 1(" - p dz + (T + = [[A)))))
since (x) on fa < T) and Ar(z) T + on fz 2 T}. Moreover, CVaRo(Ar) is equal to (10), because
22(3) (T' b)gr S T(1 qr) + (0+b))r - bqr.
Suppose that a - 1, then we distinguish between cases or and @r If or > 0, both 10 and the first term of (11) contain (1 a)- times positive quantity; the minimum is therefore
the remaining term T + b, so
lim CVaR. = T a=1
or = 0 (equivalently
u == supsupp(u)), then (10) reduces to
1
[ 2 2)(2) dz T-a
J. =2(=) -aa
1
E x 2*),
a
since Pr(r 2 ==]==1 =
and 0 on (u, T As + 1, - u and bounded convergence yields E[r x 2 t²] u. the same regime, 111 becomes min T b} T u, so the minimum
is given by 10 and
lim CVaRa(Ar(z)).
Combining the above obtain that lim (AT max u, T b}.
A.2 IDEAL PERFORMANCE FOR r < 2.618
If 22, 2.618) then the ideal algorithm (x) has discontinuity b(r 1), shown in Figure We note that all results presented in the main paper hold regardless of the value of r, i.., Theorem 2 and Algorithm I remain valid.
16

---

Published as a conference paper at ICLR 2026
Performacce ratle
7-2
1-by-
T-
T Fa
T- 30.1
T-
pr),
b(r-1) Ski season length
Figure 2: Performance of the ideal r-robust algorithm I, compared to several algorithms Ar for different values of T, when < 2.618. In contrast to Figure [ the algorithms that buy at times T 2 (purple curve) and T br
r-I (red curve) not 7-robust anymore, because their thresholds fall outside the interval [b/(r - 1), b(r 1)].
2)r-2)
B DETAILS FROM SECTION
B.1 OMITTED PROOFS
Proof of Lemma 4 First, recall that in order to r-robust, any algorithm must choose a threshold T E t2), where & = M/r and t2 =
Case 1: No tj. In this case, L sets T = t and never accepts, so (o) = 1. The offline optimum is oo, hence
To Tz.
pr(4r.
Any other r-robust algorithm Ay must also have T 2 t,, thus Ar(o) 1, and the performance ratio of Ay is Fo. Therefore, I, is optimal in this interval.
Case 2: So E [tt, t2].
Here I, sets T = Zz. thus Ar(a) Ig and
No = pr(Tr,
Eo
hence T, is optimal in this interval.
Case 3: To > tz. In this case, I, sets T t2 and accepts the first price least 12, Acz(a) t22 and
Ea
pr (T(T a) S
t2
Any r-robust algorithm must have T < l2. IfT l2, consider sequence of the form v l2, where v E [T, (2). In this case, Ar(a) = w and
pr(AT, = Ze 2 Ho
l2
Thus no r-robust algorithm attains a smaller ratio than 7, on a.
Combining the three cases, the optimal threshold is T min(t2, max and the perfor- mance ratio is
Foi 1,
F. [1,
pr(,,,
Io [1,
00/t2,
To E (1.
This completes the proof.
Proof of Theorem The proof is based on a case analysis. First, note that the prediction range Ry u. may not always overlap with the robustness interval [t]. If this is the case, the threshold T must be chosen so as to minimize the maximum distance from the ideal performance.
Namely:
17

---

Published as a conference paper at ICLR 2026
If I t1. then T max 11, since in this case dmax (Ar)) 0.
If 12, then T max 12, since have again d (Ar) 0.
This ensures that the algorithm's performance aligns with the ideal benchmark when predictions fall outside the robustness interval. Furthermore, analyze intersections between Ry and [+1, te] by considering the following cases:
Case 1: l and are within [t,, 12]. Then pr(I,, x) = for all æ E Ry. We consider further subcases:
1. T c: The maximum distance dmax (Ar) is defined by z - 1, with the adversary selecting
x = u to maximize this distance.
2. T E [e, uJ: The distance (max(Ar) calculated as max = - 1,7 - I]. If < x, the
performance ratio is maximized at u; however, when T exceeds æ, it is maximized
I = T for very small E. Hence in this case the performance ratio is arbitrarily close to T
3. T u: this case, x u, and dmax (max((A)= = u- 1.
The second case above, namely T e [e, u]. is the most general one. To minimize dmax ( (Ar), the optimal T max is equal to /u, because minimizes the maximum of two expressions. If v l1, then the threshold must be adjusted to:
max = max (41, vu}
to ensure it resides within the robustness interval.
Case 2: t S l and u 2 f2. Here, the main complication is that pr(I,, .:) may differ from 1. It is sufficient to choose t2], with the maximum distance being
1, 1/
dmaxx (AT) max
T
12
Solving for the optimal T that satisfies
T l2
yields
T= 1/ u / (u - 12)2 + 413u.
However, this value may not belong [t,, t2). hence
T Thax min max (1,T)) T}}.
This concludes the proof.
that in the first case, the algorithm aims minimize the distance from the line y(x) (the ideal performance). In this case, the threshold has de- pendency on vu, as derived from an analysis similar to the competitive ratio (which is equal the square root of the maximum price). In the second case, the algorithm aims to minimize the dis- tance from a more complex ideal performance, which includes two line segments. This explains the dependency on the more complex value T. One can also show that T 2 Vu: this is explained intu- itively, since in the second case, the algorithm has more "leeway", given that the ideal performance ratio attains higher values.
For some intuition behind Theorem 5
Proof of Lemma 6 From the definition of F*, it follows that
Ex~n(P) [p] = Ex
hence the a-consistency of Ar is least the RHS of the equation in Lemma
18

---

Published as a conference paper at ICLR 2026
Let F be distribution that maximizes the a-consisteney, then it must be that
Bp-ulpl cons(Ar)) 2 CVaR [Ar(a)]
We can argue that CVaR, [[ I PVaRo.-([Ar(o]] This follows directly from 3 and the observation that in any sequence in the support of F*, have that Ar(a) if Ta T. and Ar(o) = T. if Ta T. Hence, we also showed that the a-consistency at least the RHS of the equation in Lemma 6 which concludes the proof.
Proof of Theorem Similar ski rental, the computation of (Ar(o) for the one- max search problem requires a case analysis based on the parameter of (3) Define Or = [Ar = 1] as the probability that the algorithm Ar selects the value and 1 gr as the probability it selects the threshold T. Recall that these are the only two possibilities, from the defi- nition of F*, without any assumptions of Rg. Under assumption that Rg = [(1 - d)y, (1 + 8)y). can obtain better lower bound for Ar, i.c., know it ensure minimum profit of (1 8)y. We proceed with the analysis of this setting, and consider the following cases.
Case 1: 1 T. Then
4T (1 T) + T
CVaRa,plAr ssup 12T
-
1-a
In this case, the optimal value of is equal to hence we obtain:
CVaRa.u(Ar(0 T(1 Gr a) + qr
a
Case 2: 5 (1 (1-8)y In this case, (t Ar(o))+ 0, and (A (1-8)y.
Case 3: t [(1 [[1- 8)y, T). Then
(1- (r())) = [0,
w. 1 Gr,
---1, 1, w. p. Qr,
from which we get that
CVaRa,)(Ar(o)1= 1E((1-0yy.1
sup
(1 9T
+ QT
We consider two further subcases. If
0, then we obtain
WaRRa,LAA(O = (1 - 8)y.
In the case, when -a qr > 0, we have that
CVaRa, (A(())] T(1 91 - a) + qr
1-a
Combining all the above cases, if follows that:
T(1 9T a) 7r
CVaRo, max
(1 (1-6)g
a
19

---

Published as a conference paper at ICLR 2026
B.2 WEIGHTED MAXIMUM DISTANCE
The payoff function is defined considering two cases: First, if Ry S [t1,t2]: then the payoff function
T -1)
T w(())) max (T 1) w(xz)
max
max 227
2<T
since, in this case, the ideal performance is equal to 1. In the second case, i.e., Ry is not in [t]. then
max
max TSrStta
1 1) w(x), max 22
7
w(x), max - - 1)w(z))
(12)
#<T
which follows from In general, it is not possible to obtain an analytical expression for the value of this game (under deterministic strategies) for arbitrary weight functions. However, for specific functions, the game can be solvable we demonstrate below.
Example: We will compute Taax for a linear weight function, defined as:
w(x) = -mx { 0,
x yl yd }
(13)
For simplicity, we only show the computation for the case Ry S [1,,4]] The other cases can be handled along similar lines, using (12). In this case (12) is
[
x
i < T and x E [(1 5)y, y).
y
if 2 T and x [(1 5)y, y).
7
yd
max
(x
1)
i and x [y, (1 + 8)y),
yo
I
1)
y
if 2 T and ly, (1+ 8)y].
T
We denote the expressions, for each case in the above maximization, by ez, ea respectively. First we analyze the best response of the adversary for fixed threshold which represents the player's strategy. There are two cases to distinguish, depending on how T compares y.
CASE S y.
Subcase A1: (1 (1- d0y S x T In this case, the value of the game is given by ej. The second derivative E1 with respect to æ is 2/8y, therefore e is concave, and maximized at one of the endpoints of the case range. Considering 61 as function of x have e ((1 d)y) 0 and ej (T) (T I)(T ((1 5)y))/vō > 0. Therefore, the adversary's 's best response is to choose T, yielding game value, which we denote
11 = -T - T ((1 5)v)
yd
Subcase A2: T S S In this case, the value of the game is given by 62. Its second derivative is 2/yOT, therefore 62 is concave. Again we evaluate 62 at the endpoints of the case range, and obtain Therefore, the adversary's best response is choose
(T)) well ez(y) y/T producing game value
y
U/2
T
20

---

Published as a conference paper at ICLR 2026
Subcase A3: // S Σ 11+6)y In this case, the value of the game is given by Eg. The second derivative is -2/ T), hence 6g is concave. Using second order analysis, we find that it is maxi- mized at (T (1 + 8)y)/2. This choice is in the range [y. (1 + 8)y), since T belongs to [11 8)v; (1 + 8)y]- We denote by
((1 8)y T)
64
4y0T
the value of the game for the best adversarial choice this case.
Summary of case A We observe that is always dominated by v4, hence the value of the game case max (1; ).
CASE B: T y.
Similar to the previous case, we break this case further into 3 subcases.
Subcase B1: (1 d)y x S y. As in case A1, the value of the game is given by c1, which is maximized at its right endpoint. Since this is different endpoint than in case Al, we obtain a different value of the game, namely
e1 e = 1.
Subcase B2: y S x S. In this case, the value the game is eg. Its second derivative -2/ hence it is concave. Its derivative at the upper endpoint is 4 - 2T 0, hence eg is maximized at this lower endpoint, and has the value Vi = y - 1. Note this vy happens to be also the value of the game in case B1 and does not depend on T.
Subcase B3: T S x. value of the game is Ug-
The analysis of this case is identical to the analysis of case A4, hence
Summary case B If the algorithm chooses T E [y. (1 + d)y]. then the value of the game is max 3. We observe that is concave function in T, with slope 0 at T = (1 +1+ +8)y, while va
a constant. We show that v3 2 U1, even for the whole range (1 - 8)y I T I (1 + 8)y. For this
purpose evaluate Eg at T (1 d'y. and obtain by the assumption that 1 I (1 5)y that
yd
U3 (a((1 5)1) =y -
(1 8)y
yd
2 ツ
1
2 0.
SUMMARY OF BOTH CASES A, B
We know that if the algorithm chooses T 2 y, then the value of the game 1i3 y 1. We claim that 7' S would be a better choice. We already showed that 04 S v3. To show S 23, we observe that in U1 [T 1) T (y (y-y() yd) the first factor T is upper bounded by y 1. In addition, the second factor
most by T y, from which conclude 01 S Us.
Hence max { 01, 31 $ U3. As result, the algorithm's best strategy is to choose (1 1)- T such that e1 (T) (T). The exact expression of this value can be computed, but does not have simple form. Hence, for the purpose of presentation, we omit its exact expression. See Figure for an illustration.
21

---

dr Published as a conference paper at ICLR 2026
2.5
2.0
Value of the gare
1.5
1.0
0.5
0..0
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
3.00
Threshold 7
Figure 3: Illustration of the different values of the game: on blue, V3 in orange, and e4 in green. The parameters 2 and 5 0.5. The value of the game is obtained for T chosen as the intersection of the green and blue curves.
B.3 AN EXAMPLE FOR COMPUTING THE AVERAGE DISTANCE
In this section, we discuss how to optimize the average distance, which from and 8 is equal to
206 Sh (1881 (x - 1) w(xx dx+
1 [ ( - -1) w(x) dr), T
if (1 + 8)y S 12,
davg(Ar) (AT)
200 Sen (x (x- 1) w(xx dx+
(14)
f ( 1) w(x) dx+
(1 ) w(x) dx),
otherwise.
We illustrate how to compute the average distance for the linear weight function, as defined in 13 We show the calculations only for the first case in (14). i.e.. in the case in which (1 + 8)y S fz- Recall that the linear weight function is increasing for T s y and decreasing for T 2 Due to this behavior, we split the computation of the integral into two expressions, depending on whether T < y or T y, which are given below.
lrd
(x (x-1). (1 y/ - x
davg, (T)
2y
(1-8)p
-1) (1 y - dr
T
(L+5)y
( -1) (1-
x y
dr
h
-- x
2
(x 1).
dx
2yp
h
(1-8)y
T
T 11) (1 1
x x- y/
dx
h
y
(1+6)y
T - 1)
11---ym 2 1)-11
dx
y
The first expression, dagg11 (T), can be simplified to:
22

---

Published as a conference paper at ICLR 2026
davg,1 (T) 12(v6)27
- ( -) -1) 3(y0) 2)T +
+ +y 11 (T² - T²)
+ 1 + 2T)
Similarly, the second expression, dwvg,(()), (T), simplifies to:
davg.2 yd +3y (6 + yō 3y)
12T
To determine the optimal threshold Tayg we apply second-order analysis, solving for each case independently. The final solution is obtained by selecting the value of T that minimizes davg(T), (T).
C APPLICATION IN CONTRACT SCHEDULING
Definitions In this section, we apply our framework to the contract scheduling problem In its standard version (with no predictions), the schedule can be defined an increasing sequence of the form X = (zi)ieN, where 2; is the length of the i-th contract. These lengths correspond to the execution times of an interruptible system, i.e., we repeatedly execute the algorithm with running times 11 22,.... Hence, the completion time of the i-th contract defined as Σ dy.- Given an interruption time T, let 8(X, T) denote the length of the largest contract completed in T. The acceleration ratio of X (Russell & Zilberstein, 1991) is defined
T
acc (X) pr (X, where pr(X,T) E(X,T)
(15)
It is known that the best-possible acceleration ratio is equal to 4, which is attained by any doubling schedule of the form X, = (A2'), ); where À E [1,2). In fact, under very mild assumptions, dou- bling schedules 15 without any assumptions, no schedule can have bounded acceleration ratio the
the unique schedules that optimize the acceleration ratio. Note that according
to Definition interruption time is allowed to be arbitrarily small. To circumvent this problem, it suffices to assume that the schedule is bi-infinite, in that it starts with an infinite number of infinitesimally small con- tracts. For instance, the doubling schedule can be described as (2 KEz, and the completion time of contract 2 is defined as Ej=-x 2 2 We refer to the discussion in Angelopoulos et al. (2024) for further details. We summarize our objective as follows:
Objective: For each of the decision-theoee theoretic models of Section find À E [1,2) such that the schedule X, optimizes the corresponding measure.
We will denote by Xiaax Navg and Xevar the optimal values according to the maximum/average dis- tance, and according to CVaR, respectively. Given a schedule XA, we will use the notation ky (t) to denote the index of the largest contract Xx that completes by time t, hence (x) |log
C.I DISTANCE MEASURES
Here, we consider the setting in which there is prediction the interruption time. We begin with identifying an ideal schedule, which, in the context contract schedule, is a 4-robust schedule X that optimizes the length ((X.y) i.e., the length of the contract completed by the predicted time y- From Angelopoulos Kamali 2023b), we know that such an ideal schedule completes a contract of length 2/2. precisely at time y, and thus has the following property.
Remark 8. The performance ratio of the ideal 4-robust schedule is equal to 2.
'This is problem of incomplete information that can be considered online problem, in the sense that in each time step the scheduler must decide whether continue the current contract, start one.
23

---

Published as a conference paper at ICLR 2026
Algorithm 2 Algorithm for computing Xmax
Input: Prediction y with range Ry. weight function w. Output: The optimal value of the X-parameter, Xmax.
1: Define a set of critical times as = {y. A kkx)), Sh where S' is the set of all solutions to the differential equation (T) + w (T) (T - x 2- 2 T (-2 - -2) (T)).
1ogg k)) = O.
2: For all E S, compute d( ())
3: Return Amax arg min maxTes d( T(.
From [ 11 and Remark it follows that the maximum distance of a schedule Xx can be ex- pressed as
sup TER, (((x,T)) (1(x).7) -2) (T).
dmax (xx)
(16)
where recall that Ry is the range the prediction y-
Algorithm shows how compute Xmaxx- We give the intuition behind the algorithm. We prove, in Theorem that the distance can be maximized only at a discrete set of times, denoted by S. This set includes the prediction y. the last time contract in XA completes prior y, and an additional set of times, denoted by S" which are the roots of a differential equation, defined in step 2 of the algorithm. To show this, we rely on two facts: that w is piece-wise monotone (i.e., bitonic), and that the performance function of any 4-robust schedule Xx is piece-wise linear, with values in [2, 4]. returns an optimal schedule according to dmax-
Theorem 9, Algorithm 2
Proof. Recall that the performance ratio of the schedule X, = (A2"); is expressed as
T
T
pr(Xx, T)
T( A. 2l -1-1"
We observe that pr(Xx, T) is piece-wise linear function. Specifically, if T belongs in the interval (X2), A2i+1J, then pr(Xx.7) ?') is linear increasing function, with value equal to 2, at T = A2 + s, and value equal to 4 at T' = >2 where is an infinitesimally small, positive value. This linear growth arises from the structure of the schedule, which starts interval. For this reason, pr(Xx. T) has a discontinuity at the endpoint of each interval.
contract at the endpoint of each
By definition, y belongs to the interval (v) TK (x)+)) To simplify the notation, in the remainder of the proof we use & to denote (y)). We claim dmax (max(Xx) is maximized for some T E [T Te+ l]. specifically at one of a finite set of critical points S. To establish this claim, we make the following observations:
At Tk, the performance ratio reaches its maximum value equal to 4, for the entire interval Tk..
Any T Th- or T Ti does not need be considered in the computation of dmax- due to the monotonicity of the weight function, and the structural properties of the schedule X3, discussed above.
Given that the bitonic nature of the weight function, we observe that for all < y. w(T) is non- decreasing, hence within the interval [Tk, y). it suffices only consider Tę maximizing candi- date. Furthermore, in the interval [y. Tex+1l. wTT) is con-increasing, while the performance ratio grows linearly. Thus, must find the local maxima for T (y. TRy +1]. by solving d' d'(X,,27 T) 0, or equivalently
A - wTT) + w (T). (T-
2looR FJ 0.
We thus show that suffices to consider the set potential maximizers of the distance, as defindd in Algorithm
Corollary 9.1. For the unit weight function w(t = 1, and R. = (1 8)y, (1 + 8)y], the schedule that minimizes diax is the schedule of Angelopoulos & Kamali 2023h
24

---

Published as a conference paper at ICLR 2026
Proof. The proof is special case of the proof of Theorem In this case, d' x 7) which implies that only local maxima for d(Xx, 7)) can occur at Tx+1 or at (1 + 6)z.
0, First, suppose that 6 1/3. In this case, any schedule Xx is such
We will consider two that dinax (Xx) = 2. This is because X, completes at least one contract within the time interval [(1 111-6) 8) (1 6)y]
For the second case, suppose that 8 I 1/3. Then, in order to minimize dmaxx and without loss of generality, À must be chosen that contract terminates anywhere in [(1- 8)y, (1 8)y]. since otherwise X, would have performance ratio as large as 4, hence distance as large as 2. With this into account, must be further chosen that Xλ completes contract time (1 d)y. This is because, in this case, pr(X,, 22' is increasing in T', for I" E [[1 8)y, (1 + 8)y] Hence the optimal algorithm is precisely the 6-tolerant algorithm.
Next, we show how to optimize the average distance, which from (2) and 15 is equal to
/ ,EER, 2l102 3J-1
T
(x) = 2y0
2 w (T) dT.
(17)
Optimizing requires numerical methods.
C.2 COMPUTING THE AVERAGE DISTANCE OF SCHEDULE
To ensure computational tractability, impose constraint the range Rg of the prediction y- Specifically, assume å S 3. This assumption guarantees that for any schedule of the form X X(2"; there is at most completed contract within Ry-
The length of the largest completed contract in X before (1 5) is then given by (2*x((1-6)))- Using this, we divide the range Ry into two sub-intervals:
1. [[1 - 5)v, x2*x((1-8)))+++++++ In this interval, the performance ratio is
T
T
((X,T)
12
2. (124x((1-8)))+1 (1+ 8)y]: In this interval, the performance ratio is
T
T
()
(1=x(()))
The average distance davg (X) is then expressed as:
(1-
1
T
davg (Xx)
X2 -2) ww(T) df
(18)
2y0
(1-6)
(1+51v
(2 -3) -w(T)aT)
T
(19)
X2
11
Example: linear weight functions. As an example, consider the case in which is a bitonic linear function defined by
w w = max f
1-
T -1
yo
To apply this weight function in the computation of (19). divide the prediction interval R. [[1 8)y, (1 + 6)y] into three subintervals based on the structure of the schedule and function ws:
. 7 E [[1 - 5)v, (2 In this case, pr(X,T) -1
T Then,
A2 ((=
1----T T - dr. yd
T
2)
(1 (8)1
(1-8)z
25

---

Published as a conference paper at ICLR 2026
T [A2ka((1 (1)))))++111))) v]: In this case, pr(X,11) T)
>21"((1-013 Then,
T
X2 S (225)((1-8))) -2) (1- (1-
T
yd dt.
E [g. (1 + 8):]: In this case, pr(X,T)
22-x(010000- Then,
T
(1+6)
T
-2) ( (1-3
y
T
dr.
(2
yd
To summarize, we obtain from the above cases, and 19) that
dxy(()) (X) -((0)) X 4 8)0)+1 x 3 2=x(11-800 y0 1)
3(58)²
2 2-2-M)((1-61w) (- (y0)3 Mvō)3y -(00))-3((0))
3(v8)y + s²)
3(y8)²
Optimizing in terms of À via second-order analysis and solving for the derivative's root gives three solutions, but only real root. Thus the optimized value is:
3(1 301-2x000000000
(4<((11-8)0) y(1 - 8)
Xang 2
16-x((1-6)1) 92 (8- 1)2
1/3 B1 1/3
- 3. 64kx((1-6)v) 4V ((1-6) B1 B2)
3. ((-x((1-)))) A 4V 4096tx((1-0))) B,,
where
A = ((0)) 3 + 3y²
B1 = 5(80)3 - -39(v)) + 15())) 5y
B2 (vO)3 9(10) +( y².
C.3
RISK-BASED ANALYSIS
We now turn our attention to the CVaR analysis. Following the discussion of Section 2.2 the oracle provides the schedule with an imperfect distributional prediction μ.. From 4 and the fact that any distributional prediction concerns only the interruption time (the only unknown in the problem), the a-consistency of schedule Xx is equal to
ET (T)
a-cons(A) oV [X]
We thus seek X, that maximizes the conditional value-at-risk of its largest completed contract by an interruption generated according to μ.. To obtain tractable expression of this quantity, will assume that has support Ry E [[1 (1- (1 + d'yy], where h S y/3. This captures the requirement that the support remains bounded, otherwise the distributional prediction becomes highly inaccurate. This implies that if t is drawn from μ, then in Xx. t) can only have one of two possible values, namely > ((1-6)))1 and x() ((1x(())))))
81))11 (4T) dT, then from the discussion above we have that Pr[e(XX, T) = x2tx((1-510] 9x- With this definition in place, we can find the optimal schedule.
Define = Pr(e(XA, 7) 2 (11-0))-11 (2-) -
26

---

In order to Published as a conference paper at ICLR 2026
Theorem 10. Assuming 1/3, have that
(22 (1)))
CVaRa,u ( T)] = max
(2(1 - a) -2)), ,2)),22
((1 (11111111001111
1-a
where (1) = [log2 1- Hence,
AovaR arg ( (((Xx
Theorem 10 interpolates between two extreme cases. a = 0, then our schedule maximizes the expected contract length assuming T ~ μ., i.e. (2
9A + X (1 9x) =
\25x((1-6)))11 (2 92). This schedule recovers the optimal consistency in the standard case of distributional prediction, as studied in (Angelopoulos et al. 2024), and corrssondds a risk-seeking scheduler. In the other extreme, i.e., when a - 1, the schedule optimizes the length of contract that completes by the time (1 8)y, namely (g5x((166)p)) -1, thus recover the consistency the d-tolerant schedule.
Proof. Recall the definition of the conditional value-at risk comes, as given (3 compute (((X,, we have to apply case analysis, based on the value of the parameter
Case 1: 1 (1-x(()))))) Then
(VaRa,ul(()) T)
t 1 1-a (t- 222x((1-80))1112 }
sup (2-
In this case, the optimal value of is equal to (oka((1-51))11 hence we obtain:
((axx,,(((xx,)))
(2 a) - gx)
1 1-a
Case 2: S 12-x((1-6)0)1 In this case, (t - ((X,T)) 0. and
CVaRa, [xxx,, T)] ((1-)))-11
Case 3: t [12+x((1-8)9)1 (22xx(1-5)9)) Then
S0, ((X,T))*
w. p. 1 Tx
11 22 ((1-))01)))11
W. p. ax
from which we obtain that
(Va
sup te A2 atv 1, (1 du))
22 {1 {1(1-
I-a
+
12 0))
I-o
1.9x
We consider two further subcases, based on whether of 1 - ạx is positive or not. In the former case, we have that
(1-)(111)))
CVaRa, (((x,,
(2(1 a) -xx).
1-a
In the latter case, we obtain
CVaRa. [((x, T)]
(11)((116)))-1
From the above case analysis, it follows that
(11x((1-))))-
CVaRa, [((x,, T)] = max
(2(1 - a) -4x), (
1-
which concludes the proof.
27

---

Published as a conference paper at ICLR 2026
Table 3: Experimental results for contract scheduling (linear weight), å 0.2.
MAX
AVG
CVAR..
PO
8-TOL
0.5
0.9
Avg perf. ratio
2,421
2.413
2.426
24416
2,471
2.960
2,500
CL,/CI
+0.0000
+0.0001/
0.0000
0.0000
0.0002
0.0001
0.0003
0,0000
0,0000
Exp. length
413_303
417.504
420.164
415,274
402,646
373,008
CL//CL_
9983.355/
+8495.2 21/5.21/-
+9123.35/- 8027.55
+8621.83/-
+8679.61/-
+7776.46/-
+8377.655 65/-
8957.96
9051.60
8983.43
8684.86
7024.64
8357.20
Table 4: Experimental results for contract scheduling (linear weight), 8 ==
MAX
AVG
CVARa.
PO
5-TOL
0.1
0.5
0.9
Avg perf. ratio
2.654
CL./CI
+0.0000v.
+0.0000V:
+0.0002/-
+0.0002/
+0.0006/-
+0.0000%
+0,0000
0.0000
0.0000
0.0002
0.0002
0.0006
0.0000
0,0000
Exp. contract length
371.190
387,025
389,927
378.469
344,100
370,414
329,257
CL./CI_
+7982.66/-
+8086.66 65/-
+8739.76/-
+8779.84/-
+7710.75/-
+8252.32/-
+7185.13/-
8892.81
7975.69
C.4 EVALUATION OF CONTRACT SCHEDULES
Baselines We compare our schedules against two 4-robust baselines (Angelopoulos & Kamali 20236): the Pareto-optimal schedule (PO), which completes contract the prediction y, and the d-tolerant schedule (6- (ol),,,, which completes contract at (1 (1-5)y.
Datasets The prediction chosen as y Unif[0.8 10 1.2 10%), and the prediction range is Ry = [11 8)y, (1 + 8)y]. The interruption time T is chosen uniformly at random from Ry.
Evaluation For MAX and AVG, we use weight functions defined on Rg. The first linear symmetric function that decreases from 1 at to 0 at the endpoints of Ry. The second is a Gaussian function
2v exp (-2 (²= if E Rg: 0,
w((x)
otherwise,
where 5y/4. For CVAR,, the predictive distribution μ coincides with the respective weight function, truncated and normalized on Ry with a E {0.1, 0.5, 0.9}.
For each schedule compute the average performance ratio, taken over all T E Ry, with 1000 independent repetttionn on the choice of y. We also compute the expected completed contract length under jr, with the averaging performed over the choices of y. The tables also report the 95% fidence intervals (CIs). Results are presented in six tables: three for the linear weight function (Ta- bles 3 and three for the Gaussian weight function (Tables 6 each corresponding a different value of 8.
The tables show that, in the majority of the considered settings, our schedules achieve better performance ratios and larger expected contract lengths than both PO and 5-Tol. This can be explained by the fact that all Pareto-optimal algorithms brittle, as shown in (Elenter al., 2024), whereas, in contrast, the 8-Tol algorithm is inefficient unless the prediction error is large.
Discussion
For CVAR., the results show that the expected completed contract length decreases as grows, while the performance ratio tends to increase, which is consistent with the tradeoff between risk and robustness. When is smaller, all schedules perform better: this is because the reduced prediction range allows to our algorithms a more accurate positioning of the completion time. In similar vein, for Gaussian weights, the results are consistently stronger than for linear weights, because the distribution is more concentrated around Finally, we note that most confidence intervals the reported objectives collapse to zero. This is consistent with theory because the schedules have the same structure for each prediction y.
28

---

Published as a conference paper at ICLR 2026
Table 5: Experimental results for contract scheduling (linear weight), å 0.4.
MAX
AVG
CVAR..
PO
8-TOL
0.5
0.9
Avg perf. ratio
2,808
2.704
2.711
2.746
3,031
2.920
3.287
CL,/CI
+0.0000y
+0.0001/
+0.0003/
0.0000
0.0000
0.0001
0.0003
0.0003
0,0000
0,0000
Exp. length
385,593
372,668
376,514
CL//CL_
7657.211- 7979.53
+8265.99 97/-
+8415.05/ 8767.30
+8449.57/-
+7200.61/-
+8415.63/-
+7370.45/-
8367,98
8393.17
7299.36
8840.35
8120.64
Table 6: Experimental results for contract scheduling (Gaussian weight), 5 = 0.2.
MAX
AvG
CVAR..
PO
8-Tol.
0.1
Arg perf. ratio
2.267
2.266
2.273
2.266
2,315
2.960
2,500
CL//CI_
+0.0000--
+0.0001/-
+0.0002/-
+0.0000-
+0.0003/-
+0.0000X-
+0,00001-
0,0000
0.0001
0.0002
0.0001
0.0003
0.0000
0,0000
Exp. contract length
442.104
443.434
445,046 8505.70
442,662
430,335
373.008
397,869
CL
+9722.63/-
9586.90
9592.05
9603.26
9245.24
7024.64
8357.07
Table 7: Experimental results for contract scheduling (Gaussian weight), å 33
MAX
AVG
CVAR..
PO
8-ToI.
0.1
0.5
0.9
Arg perf. ratio
2.413
2.415
CL./CI_
+0.0000V-
+0.0001/-
+0.0002/
+0.0001/-
+0.0004/-
+0.0000X
+0.0000
0.0000
0.0001
0.0002
0.0001
0.0004
0.0000
0.0000
Exp. contract length
412.448
416.801
419.095
414,520
392,171
370,414
329,262
CL//CI_
88872.45/-
+8664 99/-
+9395. 10/-
+9623.35/-
+8729.124
+8252,32/-
+7185.244
9576.50
Table 8: Experimental results for contract scheduling (Gaussian weight), 8 0.4.
MAX
AvG
CVAR.,
PO
T.
0.1
0.5
0.9
Arg perf. ratio
2.494
2.478
2,488
2.483
2631
2.920
3.287
CL//CI_
+0.0001/-
D.0000
0.0001
0.0002
0.0002
0.0000
0.0000
0.0000
Exp. length
407.466
413.970
416,511
410.594
382,442
376.514
308.032
CCI
+8625 69/-
58887.56/-
+9024 7VV
+9319.17/-
+8202.655-
+8415.63/-
+6701.11/-
8993.79
8941.28
9400.35
9231.67
8300.45
8840.35
7383.17
D DETAILS FROM SECTION 6
D.1 EVALUATION OF SKI RENTAL ALGORITHMS
We base the experiments on the benchmarks described in Section for varying values of the parameters 8, J,r, 2. For MAX and AvG we consider two classes of weight functions on Ry (1 (1-5)y, (1 + 8)y]: linear symmetric weight decreasing from
the endpoints, and Gaussian weight with mean y and a ōy/4, both truncated and normalized on Rg. For CVAR the distribution μ described by the same linear and Gaussian weight classes (truncated and normalized in Rgy, with (averaged over all E Rg and over 1000 draws of y) and (ii) the expected cost under μ (averaged over the same 1000 draws of y). Each table also includes 95% confidence intervals. We present five tables for linear weights (Tables [3 and five for Gaussian weights (Tables [8.. They correspond to the settings (0, r2 E (00.9, 4), (0.9, 8, 4), (0.5,5, 5,55,,) (0.5, 8, 4), (0.9,5, (0,577) 7)).
{0.1, 0.5, 0.9). As in the main paper, report (i) the average performance ratio
29

---

Published as a conference paper at ICLR 2026
Table 9: Ski rental (linear weight), 0.9, 5, 4.
MAX
AVG
CVARa
BPG
0.5
0.9
b T
Avg perf. ratio
1.3442
1,3368
1,3418
1.3637
1.3930
1.6767
2,1874
2.2189
CL,/CI
+0,0309/-
+0,0297/-
+0.0343/.
+0,0366/
+0.1606/
+0.1706/
0.0345
0.0336
0.0303
0.0342
0,0355
0,0502
0.1668
0.1684
Exp.
11.2501
11.1832
11.1693
11.2758
16.4188
20.6070
20,5024
CL.CCL
+0.4798/-
+0.4866/-
+0.4954/
+0.4787/
+0.46714-
+0.9002/-
+L8565/-
+1.8611/
0.5076
0.5085
0.5201
0,5368
0.4981
0.9968
2,0281
1.8712
Table 10: Ski rental (linear weight), 6 = 0.9, 8, 4.
CVAR,
BP,
0.1
0.5
0.9
b b+ 4
6(r 1)
perf. ratio
1.2879
1,2853
1,3031
1,3343
1.3978
1.6767
2.2417
2.2251
CI /CI
+0.0318/-
+0.0324/-
+0.0338/
+0,043//
+0.0543/
+0.0482/-
+0.1794/-
+0.1748/-
0.0355
0,1831
0.1732
Exp.cost cost
10.4306
10.3880
10.3999
10.4840
10,7296
16,4325
20,8787
20.7540
CL//CL
+0,3959/-
+U.4155/-
+0.4189/-
+0.4035/-
+0.3811/-
+0.9005/-
+1.9688-
+1.9242-
0.4364
0.4321
0.4595
0.4551
0.4256
0.9964
2.1589
1,9548
Table 11: Ski rental (linear weight), 6 0.5, 5, 4.
MAX
AvG
CVAR.
BP
0.5
0.9
8 + 1
Avg perf. ratio
1.2047
1.2034
1,2085
1.2145
1,2287
1.7729
2.2041
2.1976
CL/CL_
+0.0170/-
+0,0216/-
+0.1836/-
+0.1870V
0.0201
0.0204
0,0176
0.0198
0.0223
0.0695
0,1871
0,1844
Exp.
11.1732
11.1751
11.2170
17,0456
21.2944
21,0003
LC/CL_
+0.4695/-
+0.4829/-
+0.4960/
+0.4791A
+0.4821A
+0.99777-
+2.0426/-
+1,9736/
0.5043
0.5080
0.5209
0.5392
0.5183
1.1034
2.2322
2.0155
Table 12: Ski rental (linear weight), 8 = 0.5, r = 8, 4.
CVAR,
BP,
0.1
0.5
0.9
b b+ 4F
6(r 1)
perf. ratio
1.1265
1.1245
1.1334
1.1404
1.1476
1.7729
2,1680
2,1595
CL./CI
+0.0112/-
+0.0108/-
+0.009%/
+0.0133/
+0.0158/
+0.0633/
+0.1825/
+0.1783V
Exp.cost cust CL/CC_
10.3897
10.3880
10.3983
10.4419
10.4889
17.0499
20.7854
20.7519
+0,3918/-
+0.4165/-
+0,4184/-
+0.3959/-
+0-4063/-
+0.9967/-
+1.9364-
+1.9246/-
0.4351
0.4321
0.4550
0.4595
0.4330
1.1027
2.1260
1.9540
Discussion As decreases, our algorithms perform better both terms of the performance ratio and in terms of the average expected cost. This consistent with theory, since R, becomes smaller, and the algorithms can hetter leverage the narrower prediction range. We also note that Gaussian weights generally yield stronger results than linear weights, which is explained by the fact that the Gaussian weight function is more concentrated around
Varying has small effect on the performance of the algorithms. This not only expected, but also an essential feature of the algorithms, since they should perform consistently regardless of the predicted value. A similar observation holds for varying the robustness parameter r.
D.2 EVALUATION OF ONE-MAX SEARCH ALGORITHMS
We base the experiments on the benchmarks described Section 6 for varying values of the pa- rameters 6, r, We evaluate MAX, AVG, and CVAR,, using the linear and Gaussian weight classes
30

---

Published as a conference paper at ICLR 2026
Table 13: Ski rental (linear weight), 8 0.9, 5, 7.
MAX
AVG
CVARa
BPG
0.5
0.9
b T
Avg perf. ratio
1.3103
1,3053
1,3151
1.3295
1.3534
1.7901
2,8509
2,9905
CL,/CI
+0.0229/.
+0,0233/-
+0,0238/
+0.0276/
+0.1914/-
+0.2160V.
0.0222
0.0223
0.0260
0.0275
0,0310
0.0472
0.2102
0.2153
Exp.
11.7081
11.7023
11.7078
11.7775
17.8170
27,2827
27.5432
CL./CL
+0.3917/-
+0.41314-
+0,4053/
+0.3772/
+0.3763V
+0.7726/
+2.0175/-
+2.0996/
0.4533
0.4432
0,4532
0,4741
0.4357
0.8356
2,3302
2.2661
Table 14: Ski rental (Gaussian weight), 0.9, r 5, 4.
MAX
AVG
CVAR
BP,
0.1
a 0.5
a 0.9
b br
b(r 1)
Avg perf. ratio
1.3514
1,3387
1,3397
1.3492
1.3669
1.6767
2,1874
2.2189
CI /CI
+0.0297/-
+0,0307/-
+0.0302/-
+0.0326/-
+0.035//
+0.0482/-
+0.160K/
+0.17
0.0333
0.0337
0.0311
0.0644
0.0358
0,0502
0.1668
0.1684
Exp. cost
11,1765
11.1731
11,1731
11,2151
11,3155
16,9873
21.2338
20,9577
0.4687/-
+0.4829/-
+0.4966/-
+2.0143/-
+1,9520-
0.5039
0,5081
0,5217
0,5398
0,5188
1.0909
2.2246
1.9971
Table 15: Ski rental (Gaussian weight), 5 = 0.5, r= 5, 4.
AvG
CVAR.
BP
0.1
0.5
0.9
b
b + 2
6(r
perf. ratio
1,2097
1,2034
1,2049
1,2049
1,2141
1.7729
2.2041
2.1976
CL/
+0.0184/-
+0.0182/-
+0.0180/-
+0.0185/-
+0.0197/-
+0.0633/-
+0. 18.1836
+0.1870V-
0.0206
0.0204
0.0185
0.0199
0.0221
0.0695
0.1871
0.1844
Exp. cost
11.1740
11.1732
11.1733
11,1733
11,2349
17,1177
21,3451
20.9444
CI CL./CI
+0.4693/
+0.48291-
+0.4966/
+0.4843/
+0.4917%
+102577/
+2.0850V
+1.9824/
2.2479
2.0130
Table 16: Ski rental (Gaussian weight), 0.9, 8, 4.
MAX
AvG
CVAR.
BP
0.1
0.5
0.9
b + 4/
Arg perf. ratio
1.3025
1.2853
1,3002
1.3175
1.6767
2.2417
2.2251
CL/CL_
+0.0324/-
+0.0342/-
+0.0416/-
+0.0507/-
+0.1794/-
+0.1748/
0.0335
0.0334
0.0360
0.0390
0.0444
0.0502
0.1831
0.1732
Exp.
10.3947
10.3880
10.3983
10.4381
10.5760
16.9918
20.7954
20.7520
CI /CT
+0.3933/-
46.4655/-
+0.4198/-
+0.3974/-
-04001//
+0.9841/-
+1.9368/-
+1,9246-
0.4372
0.4321
0.4603
0.4614
0,4385
1.0901
2.1269
1.9540
Table 17: Ski rental (Gaussian weight), 0.5, r
4.
MAX
AvG
CVAR.,
BP
+ 4F
Avg perf. ratio
1.1345
1.1245
1.1288
1.1324
1.1404
1.7729
2.1680
2.1595
CL./CI
+0.0147/.
+0.0108/-
+0.0103/
+0.0123/
+0.0152/-
+0.0633-
+0.1825/
+0.1783V.
0.0149
0.0124
0.0105
0,0122
0.0150
0.0695
0.1828
0.1757
Exp. CL/CL
10.3908
10.3898
10.4073
17.1216
20.7559
20.7519
+0.39201
+0.4165/-
+0,4204--
+0.3986/-
+0.4107/-
+1.0255-
+1.93741-
+1,9246-
0.4354
0.4321
0.4565
0.4622
0.4390
1.1160
2.1215
1.9540
defined in Section D.I As in the main paper, report (i) the average performance ratio (averaged over all E R, and over 1000 draws of y) and (ii) the expected profit under j (averaged over the same 1000 draws). All tables include 95% confidence intervals. We present five tables for lin-
31

---

Published as a conference paper at ICLR 2026
Table 18: Ski rental (Gaussian weight), 0.9, r 5, 7.
MAX
AVG
CVARa
BPG
0.5
0.9
b T
Avg perf. ratio
1.3201
1,3065
1,31
1,3199
1,3383
1.7901
2,8509
2,9905
CL,/CI
+0,0236/-
+0,0238/
+0.0262/
+0.1914/-
+0.2160V.
0.0231
0.0227
0.0262
0.0258
0,0288
0.0472
0.2102
0.2153
Exp.
11,7063
11.7000
11.7051
11.7411
18.2168
30,3389
30,9557
CL.CCL
+/
+0.4139/-
+0,4048/
+0.3831/-
+0.4039/
+0.7890V-
+2.4735/-
+2.6507%.
0.4544
0.4431
0,4595
0,4670
0.4368
0.8573
2,9018
2,7672
Table 19: One-max (linear weight), 0.9, r- 100, = 10.
CVAR.
5-Tol
0.1
a 0.5
a 0.9
Avg perf. ratio
4,3942
4,4469
9,9327
6,7335
5.2429
10.0085
4.6304
15,6848
/CI
+0.04/0..55
+0.06/-0.05
+0.26/-0.26
+0. 15/00.1
10.12/10.11
+0.00/-0.00
+0.06/-0.06
+0.451-0.45
Exp. prolit
15.2276
19.6283
30.7586
27.7794
16.1624
5,4746
13,5565
27.9437
CL_/CI_
+0.30V.0.33
+0.49//0.48
+0.90V-0.89
+0.80V-D.87
+0.49/-0.50
+0.15/.0.17
+0.18/-0.18
+0.82/00.00
Table 20: One-max (linear weight), = 0.5, r 100, 10.
AvG
CVAR.,
PO1
PO2
0.1
0.5
0.9
perf. ratio
2.5877
2.7856
10.0269
6,7880
3.1589
2,0000
3,8718
21,0408
CL./CI
+0.02/-0.02
+0.03/00.01
+0.26// 0.26
+0.16/
+0.04/-0.0
+0.00% 0.00
+0.06/ 0.07
+0.62/0062
Exp. profit
28.6754
29.2159
1414
34.5976
29.7982
27.3730
13.9343
28.0349
CI /CI
+0.79/-0.88
+0.86/-0882
+1.07/1.00
+1.01/11.09
+0.86/-0.87
+0.751-0.83
10.16/00.16
+0.82/-0.81
Table 21: One-max (linear weight), 5 0.9, 80,
10.
MAX
AvG
CVAR.
5-TOL
PO₃
PO2
0.1
0.5
0.9
Arg perf. ratio
4,4865
4,4469
9,9943
6.9624
5.7321
10,0085
4.6516
15.6848
CL /CI
+0.04/-0.04
+0.06/-0.05
+0.26/-0.26
+0.15/-D.15
+0.144-0.14
+0.001-.000
+0.05/-0.05
+0.457-0.45
Exp. profit CI ICI
19.6283
30.7121
27.6555
14.4844
27.9437
+0.28/00.11
+0.49/-0.48
+0.91/-0.89
+0.811-0.88
+0.52/-0.53
+0.151.0.17
+0.17/-0.18
+0.82/-0.80
Table 22: One-max (linear weight), 5= 0.5, 80, 10.
MAX
AvG
CVAR,
5-ToL
PO
PO2
0.1
0.5
0.9
Avg perf. ratio
2.7856
10.0378
3.8570
21.0408
CL./CI
+0.05/-0.05
+0.01/:0.01
+0.26/-026
+0.16/ 0.16
+0.04 0.04
+0.00
0.000
+0.06/-0.07
+0.62/.0.2
Exp. profit CL./CI
28.6082
29.2159
36.0559
34.5122
29.7079
27.3730
14.9631
28.0349
+0.16//0.17
ear weights (Tables 19
28 They correspond to the settings 26) {0.99 100, 10), (0.5, 100, 10), (0.9, 80, 10), (0.5, 80, 10), (0.9, 100, 20)).
23 and five for Gaussian weights (Tables 24
Discussion The results show that algorithms tend improve 5 decreases, whereas they not affected by variations the parameters r and z. This is consistent with theory, and we refer to the discussion in the analysis of the experiments on ski rental (Section D.I) for the justification.
For small values 5-TOL has very small performance ratio: this due to the fact that in this case, the range is extremely small. This advantage disappears, in marked manner, once 8 increases.
32

---

Published as a conference paper at ICLR 2026
Table 23: One-max (linear weight), 0.9, r 100, 20.
MAX
AVG
CVARa
6-ToL
PO1
PO>
0.5
0.9
Arg perf. ratio
3,8763
3.8645
6.7675
4,8622
4,1063
10.0049
3,8668
10.2558
CL,/CI
+0.02/-0.02
+0.09/-0.09
+0.07/-0.07
Exp. profit
11,2099
13.9404
19.7256
17.8093
10,9724
3,4915
11.7401
18,0238
10.1000.10
+0. 18/-077.1
+0.30V-0.30
+0.277-0.29
10/-0510.15
+0.05/-0.06
+0.06/-0.06
+0.28/-0.27
Table 24: One-max (Gaussian weight), 0.9, 100, 10.
MAX
AVG
CVAR.
6-Tor.
PO
PO₂
0.5
0 0.9
Avg perf. ratio
5.0599
5.4540
9,7709
8,1444
6,0222
10.0085
4.6304
15.6848
CL//CL
+0,0728/-
+0,0940/-
+0.2564/-
+0.1988/-
+0.1 +0.1196/-
+0.0008/
+0.0561/-
+0.4526/-
0.0756
0.0909
0,2561
0.1969
0.1205
0.0008
0.0578
0.4530
Exp. prolit
24,9584
27.0416
35.7945
34,4015
27.5003
5.4746
13,9039
27.9858
CL/CI
+0,6259/-
+0.7406/-
+1,0580-
+1.0003/-
+0.8137/-
1503/-
+0.1583/-
+0.8233/
0.7080
0.7242
1.0403
1,0822
0,8119
0.1666
0.1659
0.8022
Table 25: One-max (Gaussian weight), 8 = 0.5, r= 100,
10.
MAX
AVG
CVAR.
5-ToL
PO.
PO₂
= 0.1
= 0.5
0.9
perf. ratio
5,9298
6.1761
12.1837
10.5279
7,4024
2,0000
3.8718
21.0408
CI /CI
1000/
+0.11422
+0.3366/-
+0,2822/-
+0.1767/
+0.0000V
+0.0622/-
+0.6202/-
0.1051
0.1099
0.3318
0,2819
0.1844
0.0000
0.0653
0.6154
Exp. profit
35.2058
35.6679
41.5955
40.8581
37.3962
27,3730
13.9997
28.1314
/CI
2/.961/--
1.03977-
+1.2372/-
1.199///
+1 00.0807/-
+0.7512/-
+4.14
+0.8152/-
1.0665
1.0025
1.2094
1.2908
0.8332
0.1558
0.8127
Table 26: One-max (Gaussian weight), = 0.9, r 80, 10.
MAX
AvG
CVAR.
8-TOL
PO₁
POs
0.5
0.9
Avg perf. ratio
5.1262
5.4540
9,8288
8.3568
6,2563
10.0085
4.6516
15.6848
CL./CI
+0,2528/
+0.1229/
+0.0465/-
+0.4526/-
0.0690
0.0909
0.2506
0.1933
0,1208
0.0008
0.0473
0.4530
Exp. profit
35.6 35.6988
34,2272
27.3657
14,9229
27.9858
CL/CL_
+0.6067/-
+0.7406/-
+1.0671/-
+1.0189/-
+0 -328--0-
+0.1503/-
+0.1671A-
+0.8233/-
0.6877
0.7242
1.0390
1,0926
0.8334
0.1666
0.1722
0.8022
Table 27: One-max (Gaussian weight), = 0.5, r 80,
10.
CVAR.
5-TOL
a 0.1
a 0.5
0.9
Ayg perf. ratio
5.9483
6.1761
12.1798
10.5404
7,3715
2.0000
3,8570
21,0408
CI /CI
+0.8807-
+0.1142/-
+0.3329/-
+0.287
+0.1781A-
+0.0000--
+0.0629/-
+0.6202/-
0.0907
0.1099
0.3376
0.2838
0.0000
0.0660
0.6154
Exp- profit
34.9084
35.6679
41.4923
40.7649
37.2693
27.3730
15.0337
28.1314
CL//CL
+100997-
+1,2443/-
+1.1989/-
-1.08511-
+0.7512/-
+0.1612/-
+0.8152/-
1.0843
1.0025
1.2156
1.3073
1.1117
0.8332
0.1756
0.8127
33

---

Published as a conference paper at ICLR 2026
Table 28: One-max (Gaussian weight), 6 0.9,
100, 20.
MAX
AVG
CVARa
8-ToL
PO1
PO>
0.5
0.9
Avg perf. ratio
4.1276
4,3758
6.6495
5.6691
4,2717
10.0049
3,8668
10.2558
CL./CI
+0.0295/-
+0,0344/-
+0,0853/
+0.0664//
+0.0365/-
+0.0217/-
0.0313
0.0339
0.0854
0.0676
0,0386
0.0004
0.0227
0.1489
Exp. prolit
18.3253
22 22.8969
21.9870
3.4915
12.2219
18.0633
CL/C
+0.2258/-
+0,2575/-
+0.35104-
+0.3316/-
+0.2615/-
+0.0501/-
+0,0495/-
+0.27777-
0,2519
0.2496
0.3484
0.3609
0,2685
0.0555
0,0505
0.2677
D.3 REAL DATA EXPERIMENTS FOR ONE-MAX SEARCH
In this section, we provide a computational evaluation of our algorithms on real-world data, using the same algorithm baselines as in Section We consider two datasets: (i) the exchange rates of EUR four other currencies (CHF, USD, JPY, and GBP), where each series is a sequence of 6672 daily prices over a span of 25 years; and (ii) Bitcoin (USD) data recorded every minute from January 1st 2020 December 31st 2024, comprising total of 2,630,880 prices. This follows the choice of data from Sun et al. (202Tb) and [enomar et al. (0055
Datasets For each sequence a, let
max
denote the maximum price in the input. For generating predictions, consider random value z sampled from a normal distribution with a mean equal to zero, standard deviation 1/2, and truncated to the interval -1,+11, This value is then scaled by the error upper bound 6, generating the predicted value
y + 2ō 22
The error bound is obtained by partitioning the sequence a into eight equal-length segments. In each segment i, we record the maximum price M, The bound is then defined as the difference between the largest and smallest of these maxima:
vz = max Mj- min M4- i=.,..,
Recall that in one-max search, if all prices are below the chosen threshold, the algorithm needs to sell at the lowest price. In this experimental setup, we use the lowest price in the sequence as this final price.
Evaluation We performed 10,000 runs to account for prediction randomness and report the resulting average performance ratio and expected profit, both with 95% confidence intervals. For MAX and AVG, we use the linear symmetric weight function, while CVAR,, is evaluated under a Gaussian distribution truncated to R, [(1 6)g. (1 + 5)y], with {0.1, 0.5, 0.9).
Results The final results are presented in Table 29 Since the input sequences in real-life scenarios are not worst-case and the range of prices varies depending on the currency, determine which algorithm performs best overall. As shown in the table, the performance ratios vary significantly across currencies. For example, MAX and AVG demonstrate better competitive performance for CHF and USD, while CVAR is competitive for GBP. This variability highlights the dependence of algorithm performance on the specific characteristics of the input data. Nevertheless, algorithms such as MAX, AVG and CVARu.s have overall either better, or very similar performance ratios than the state the art algorithms.
challenging to
To help interpret the variation in performance ratios reported in Table 29 include Table 30 which summarizes the range of prices observed in each sequence. As expected, the difference between the smallest and largest prices is particularly significant for BTC, with ratio exceeding 28. This large
re iffference_excchnn__rttttee
https::/ww..kat com htt.g//e..ooo/attttttt//eee/ee inski wtt.:///ittohhhhee
data?
resource-downlcas
34

---

Published as a conference paper at ICLR 2026
Table 29: Real-data evaluation for one-max search: average performance ratios and expected profits with 95% confidence intervals.
Currency
CVARa
PO1
PO2
0.1
0.5
0.9
CHF (Avg. ratio)
1.2617
1,2503
1.3287
1,3178
1,3451
1.5286
1.7824
1.4702
CL../CI
+0.013/-
+0.016/-
+0.0191-
+0,016/-
+0.015/-
+0.015/-
+0.002/
+0.021/-
CHF (Exp.
1.612
1.624
1.587
1.553
1,498
1.372
1.298
1,462
CL./CI
+0,031/-
+0.036/-
+0.0271-
+0.028/-
+0.026/-
+0,0214-
+0,019%
+0.030/-
0,028
0.032
0.029
0.027
0,025
0.020
0.018
0,028
GBP (Avg. ratio)
1.1573
1,1573
1.1342
1,1137
1.0912
1.1474
1.1573
1.1241
CI /CT
+0.00//
+0.001/-
+0.044
+0.004%
+0.004/
+0,02//
+0,001%
+0,004/-
0.001
0.001
00003
0,003
0.008
0.002
0,001
0.003
GBP (Exp. profit)
0,927
0.918
0,944
0.931
0.912
0.856
0,807
0.884
CL_/CL
+0,014/-
+0,012/-
+0,018/-
+0.017%-
+0.016/-
+0.014|-
+0,010--
+0,018/-
0.015
JPY (Avg. ratio)
1,8422
L.842
1.0842
L,8422
1.0842
1.0842
1.0876
1.0741
/CT
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
JPY (Exp. profit)
168.4
168.3
168.7
168.5
168.0
167.2
166.8
169.1
CL.//II
+1.5/-14
+1.6/-1.5
+1.6/-155
+1.5/-1.6
+1.6/-1.5
+1.3/-1.3
+1.2/-1.2
+2.0/-1.9
USD (Avg. ratio)
1.2042
1.1837
1.2289
1,2254
1.2471
1.3582
1.5439
1.3263
/CT
+0.011/-
+0.010%-
+0.012/-
+0.012/-
+0.01
40.116-
+0.001/-
+0.0151-
0.010
0.009
0.011
0.011
0.010
0.013
USD (Exp. profi))
1.451
1.477
1.503
1.469
1.392
1.327
1.213
1.424
CL_/CI
+0.023/-
+0.025/-
+0.0291-
+0.027/-
+0.028/-
+0002/
+0.012/-
+0.031/-
BTC (Avg. ratin)
9.0380
8,8881
9.0380
9.0380
9.0380
9.0380
15.1874
9.4486
+0.381-0.36
+0.37/-0.36
+0.38/-0.37
40.39/-0.38
-0.39/-0.37
+0.37/-0.36
+0.02/-0.02
+0.42/-0.41
BTC (Exp. profit)
24,228
24.180
24,095
23,978
23,842
24,310
CI /CI
+812/-796
+824/-781
+897/-873
+852/8829
+783/-764
+6531-641
+5 +51444487
+947/-932
Table 30: Lowest and highest prices observed in each currency sequence, and their ratio.
Currency
Lowest
Highest
Ratio
CHF
0.9260
L.6803
1.8146
1.7134
JPY
89.3000
175.3900
1.9641
USD 0,8252
1.5990
1.9377
BTC
3805.0
108276.0
28.0145
variation contributes to the substantially higher performance ratios observed for BTC across all algorithms.
35


Reviews:
[{"review_id": "XKAt8CLZkq", "reviewer": "Reviewer_YwzD", "summary": "A learning-augmented online algorithm is an online algorithm (in the Theoretical Computer Science sense) that takes a machine-learned prediction as extra input, uses it to guide decisions, and still guarantees a bounded worst-case loss when the prediction is wrong. The advice can be bad, so the algorithm is designed with two goals: Consistency (near-optimal when the prediction is accurate) and Robustness (provable cap on the competitive ratio even under bad predictions). This dual-goal structure induces a family of Pareto-optimal algorithms that are hard to compare.\n\nThis paper uses decision theory to score an algorithm’s full error-vs-performance curve against a principled yardstick. Given the r-robustness constraint, the decision-theoretic part of this paper concerns how to choose among all r-robust (r-competitive for every input) algorithms using principled objectives. They define \"ideal\" comparator $I_r$ as the omniscient algorithm that knows the input but is forced to be r-competitive too. \n\nFor the first objective they consider, the \"distance to the ideal\", they score any r-robust algorithm $A$ by its weighted max distance and weighted average distance from $I_r$ 's performance curve over the entire prediction-error range. A user-chosen weight function encodes preferences over error regions. Such “pick the action whose loss curve is closest to an ideal benchmark” idea is what they borrow from decision theory.\n\nFor the second objective, they consider risk with CVaR; they also view the prediction as a distribution and minimize $\\alpha$-consistency, which uses Conditional Value-at-Risk to weight the worst fraction of outcomes. $\\alpha=0$ recovers expected performance, $\\alpha \\rightarrow 1$ stresses the worst-case mass in the prediction range. Given r, the goal is to find an r-robust algorithm with minimum $\\alpha$-consistency. So this becomes a constrained risk minimization problem.\n\nThe paper empirically investigates how these ideas play out in classic problems such as ski rental, one-max search, and contract scheduling.", "questions": "Just theoretical questions:\n\nCan one derive lower bounds that show the paper’s optimizers are information-theoretically tight for broad classes?\n\nCan we relax the unimodality assumption on the prediction distribution?\n\nCan you formalize when Pareto-optimal designs are provably brittle near tiny errors and show how distance-to-ideal fixes this? Can you provide sharp transition thresholds?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Pre-existing work centers on consistency/robustness trade-offs and Pareto-optimality (e.g., caching, one-way trading, search) or on tolerance windows and distributional advice. Comparison of algorithms among those Pareto optimal algorithms is a new thing. The frameworks for distance measures and CVaR-based risk are both nice, actionable, and well-posed. \n\nThey benchmark on synthetic and real data and report better average ratios or profits than Pareto-optimal (PO) and $\\delta$-tolerance baselines in ski-rental/one-max/contract scheduling for both distance measures and CVaR-risk.", "weaknesses": "I actually don't understand the benefit of going beyond Pareto, or why we wouldn't just let practitioners choose one algorithm from the Pareto set. Everyone has different preferences for trading off Consistency and Robustness; given the Pareto-optimal algorithms curve, a practitioner's preferences uniquely pinpoint one algorithm (as in economics class, where the optimal consumption position is where the indifference curve is tangent to the budget line).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QqJpY81079", "reviewer": "Reviewer_oU59", "summary": "This paper studies learning augmented algorithms. Algorithms are classically studied by interpolating between consistency and robustness (performance function), and in many cases cannot be compared with each other. The authors provide two measures of quantitatively comparing these algorithms, (i) distance based methods and (ii) risk measures; the latter exploits distributional properties on the quality of prediction. Existing methods include (i) pareto optimality and (ii) tolerance based methods which are special cases of the methods that the authors propose. \n\nThe paper then analyzes 3 problems: ski rental, one-max search and contract scheduling. These examples demonstrate how their measures can practically be computed and how they can be useful in characterizing performance of algorithms.", "questions": "- Computing the performance ratio and optimal solutions (for the authors' metrics) does not appear to be easy, and indeed is one of the key contributions of the paper. Can the authors comment on whether there are general techniques that distance measures and risk based analysis that apply to a broader class of online problems (e.g., k-server)? This would seem to greatly strenghten the paper.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper is generally easy to read and follow; it is well motivated and easy to understand even for someone outside the field. \n-The choice of CVAR is one that is easy to accept, being commonly used in decision theory.\n- For a theory paper, it is nice to see some experiments, though they seem to be slightly contrived.\n\nDisclaimer: I am not from the area and cannot confidently comment on novelty nor quality.", "weaknesses": "- No major issues here from me.\n- Minor criticism : Based on my understanding of the experiments, it seems that the authors are showing that by directly optimizing their metrics, better \"results\" are obtained based on those very metrics. This is of course unsurprising, so claims like \"distance-based algorithms offer considerable improvements over the sota\" aren't that fair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fObrxOlyKB", "reviewer": "Reviewer_dDbN", "summary": "* This paper provided a systematic study of decision-theoretic approaches in learning-augmented algorithms. The system defines a unifying framework, characterizing online algorithms with advice according to their distance and risk measures. An online algorithm is said to be “ideal” if it lies on the robustness-performance Pareto frontier.\n* For the continuous ski rental problem, the paper characterizes the performance ratio of ideal algorithms, and provides a CVaR-based risk analysis. For the one-max problem, the paper characterizes the ideal algorithm, gives an analytical solution for the unweighted maximum distance, and a risk-based analysis. Analysis of contract scheduling is mentioned and deferred to the appendix. \n* Empirical evaluation shows favorable performance on synthetic datasets, and evaluation on empirical data is included in the appendix.", "questions": "* Is it possible to briefly summarize the novel contributions of the paper? (i.e. introduction of a unified framework, new settings previously not investigated, and relation between presented results and existing literature)\n* Which underlying properties of a dataset might guide a practitioner in choosing the right performance criterion for their application?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Systematic approach helps illustrate parallels between related problems, and provides a principled way to choose the \"best\" algorithm from a set of options.\n* Risk-oriented analysis is well-motivated by the increasing application of online learning methods in high-stakes applications.\n* Algorithmic results are evaluated both theoretically and empirically.", "weaknesses": "* Scope of novel contributions is unclear. Apart from the value of a unified perspective, it is not completely clear how algorithmic results compare to existing upper and lower bounds known in the literature.\n* Limitations and practical applicability are not discussed explicitly.\n* Empirical evaluation in the body of the paper is limited to synthetic data. Appendix D.3 seems to provide some empirical evaluation, but analysis does not seem to be conclusive (i.e., there doesn't seem to be an algorithm which performs best on all dataset, but the paper does not seem to provide any further insights regarding the root cause).\n* It seems that graphically illustrating the empirical results would make them easier to interpret.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ig770BXNVb", "reviewer": "Reviewer_aGPc", "summary": "There has been a long misalignment among different standards that are considered in learning-augmented algorithms to model the trade-off between consistency (performance with perfect prediction) and robustness (performance with arbitrarily bad prediction), including Pareto-optimality (direct trade-off between consistency and robustness) and smoothness (performance as a measurement of prediction accuracy). \nThis paper provides two more metrics to resolve the misalignment from the decision-theoretic view, including a distance-based measurement and a risk-based measurement. \nThey are applied to the problems of ski rental, one-max search, and contract scheduling to inspire new algorithms, which seem to perform better than previous methods.", "questions": "See the above \"weakness\" part.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "+ The paper is well-motivated in that existing metrics for learning-augmented algorithms could be brittle in different ways. \n+ Under the given metrics, optimal algorithms behave better than previous SOTA on some datasets.", "weaknesses": "- To me, the major problem is that the intuitions behind the proposed metrics are vague. In fact, these metrics are somehow unnatural and may not extend well to other more complicated problems. E.g., is the \"ideal solution\" defined for distance-based metrics always solvable? Further, is the algorithm that maximizes the three metrics always solvable? \n- The relationship between distance-based and risk-based metrics is not addressed. How are they compared?\n- The optimal algorithms corresponding to each metric are not explicitly provided in the main body. \n- The experiments seem incomplete. It is not clear whether the parameter choices are set to \"exploit\" the baselines. Especially, for the one-max search, why do the authors use the inputs for evaluating only the worst-case performance instead of the average-case? \n\nOverall, I feel that the paper can benefit from justifications on the proposed measures, a better-understandable writing, and more rigorous experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)