Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Authors: Ziyad Benomar
Lorenzo Croissant
Vianney Perchet
Spyros Angelopoulos
Venue: ICML 2025 poster (2025)
Keywords: Learning-augmented algorithms
algorithms with predictions
online algorithms
competitive ratio
one-max search
Primary area: theory->everything_else

Abstract: One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has been studied both in probabilistic and in worst-case settings, notably through competitive analysis, and more recently in learning-augmented settings in which the trader has access to a prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultaneously achieves both of these important objectives. Furthermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic learning-augmented settings which capture randomness in both the observed prices and the prediction.

Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Ziyad Benomar" 12
Lorenzo Croissant 12 Vianney Perchet 123 Spyros Angelopoulos
Abstract
growth in recent years, starting with the seminal works (Lyk ouris & Vassilvtiskii 2018) and (Purohit al. 2018), partic- ularly in online decision making, In this class of problems, the input is a sequence of items, which are revealed one by one, with the algorithm making an irrevocable decision on each. Here, the prediction oracle provides some inher- ently imperfect information on the input items, which the algorithm must be able leverage in a judicious manner.
One-max search is a classic problem in online decision-making, in which trader acts on se- quence of revealed prices and accepts one of them irrevocably to maximize its profit. The problem has been studied both probabilistic and in worst- case settings, notably through competitive analy- set-
sis, and more recently in tings in which the trader has access to prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultancously achieves both of these important objectives. Fur- thermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic bearnig--augmenter settings which capture randomness in both the observed prices and the prediction.
One of the most challenging aspects of poariing-augmenter (online) algorithms is their theoretical evaluation. Unlike the prediction-ffee setting, in which worst-case measures such as the competitive ratio (Borodin & EI- Yaniv 2005) evalu- ate algorithms on a single metric, the analysis of learning- augmented settings multifaceted and must incorporate the effect of the prediction error be meaningful. Typical desiderata (Lykouris & Vassilvtiskii, 2018) include: an effi- cient performance if the prediction is accurate (consistency); performance that is not much worse than the competitive ratio if the predictions are arbitrarily inaccurate (robustness); and between these, a smooth decay of performance as the prediction error grows (smoothness). This marks a signifi- cant departure from the worst-case, and overly pessimistic competitive analysis, and allows for much more nuanced and beyond worst-case performance evaluation.
1. Introduction
Recent and rapid advances in machine learning have pro- vided the ability to learn complex patterns in data and time series. These advancements have given rise to a new compu- tational paradigm, in which the algorithm designer has the capacity to incorporate a prediction oracle in the design, the theoretical analysis, and the empirical evaluation of an algo- rithm. The field of out of this emerging requirement to leverage ML techniques towards the development of more efficient algorithms.
Achieving all these objectives simultancously is a challeng- ing task, and is even impossible for certain problems (Elen ter et al. 2024). To illustrate such challenges with an exam- plc, consider the one-max-search problem, which models a simple, yet fundamental setting in financial trading. Here, the input is sequence of prices (p:) E [1,0], where O is known upper bound, and the online algorithm (i.e., the trader) must decide, irrevocably, which price to accept.
algorithms was born
Under standard competitive analysis, which compares the algorithm's 's accepted price to the maximum price p" := max, P; on worst-case instance, the problem admits a sim- ple, yet optimal, algorithm (EI-Yaniv) 1998). In contrast, the Saariing-augmente access to prediction of p", is far more complex. Specif- ically. Sun et al. (021) gave a Pareto-optimal algorithm, i.c. one that achieves the best possible trade-off between consistency and robustness. However, this algorithm lacks smoothness, which results in brittleness. Namely, Benomar
Learning-augmente algorithms have witnessed remarkable
'Equal contribution I 'CREST, ENSAE, Palaiseau, France "INRIA Fairplay joint team, Palaiseau, France "Criteo AI Lab, Paris, France 'CNRS and International Laboratory on Learning Systems, Montreal, Canada. Correspondence to: Ziyad Benomar Eziyad.benomaree ensac.fr>.
setting, in which the algorithm has
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Pareto-Optimality. Smoothness, and Stochasticity in Learning-Augmentted One-Max-Search
showed that even if the prediction error is arbitrarily small, the algorithm's 's performance may degrade dramatically, and collapses to the robustness guarantee. This renders the algorithm unsuitable for any practical applica- tions since perfect oracles do not exist in the real world. Benomar& & Perchet (2025) addressed the issue of brittle- ness by using randomization: this results in an algorithm with smoother behaviour, albeit at the cost of deviating from the consistency- robustness measisstecc--obustnesss Pareto front. In similar vein, Angelopoulos et al. (2022) gave smooth algorithm without any guarantees on the trade-off between consistency and robustness. [Sun et al. (2024) studied the problem un- der a model of uncertainty-quantt quantified predictions, in which the algorithm has access to additional, and more powerful, probabilistic information about the prediction error.
& Perchet 2025)
dling the real-world uncertainty of predictions. When pre- dictions and prices are both tied to random environment (e.g, financial market), we show how to derive general form bounds in expectation as a function of the distributions of predictions and prices and, for the first time, of their coupling. We provide prediction-qualee us better capture the notion of the "usefulness" of a predic- tion in stochastic environments and give detailed bounds concrete settings. We also provide general framework of analysis based on optimal transport. The use of optimal transport for competitive analysis in stochastic contexts is novel and opens new and interesting research perspectives.
metrics which help
We validate our theoretical results through numerical exper- iments, in which we compare our algorithm to the state of the art, by testing it under both synthetic and real data.
The following natural question arises: is there all-around optimal algorithm, that is simultaneously Pareto-optimas and smooth, and does not rely on randomisation or proba- bilistic assumptions about the quality of the prediction?
1.2. Related work
Learning-augmenter algorithms. Algorithms with pre- dictions have been studied in a large variety of on- line problems, such as rent-and-buy problems (Gollapudi & Panigrahi| 2019), scheduling (Lattanzi et al. 20200)
1.1. Main contributions
Our main result answers the above question in the affirma- tive by giving a deterministic Pareto-optimal algorithm with smooth guarantees. Furthermore, we demonstrate how to leverage smoothness so as to extend this analysis to stochas- tic settings in which the input and prediction are random.
caching (Lykouris & Vassilvtiskii 2018), matching (Anto- niadis et al. 2020), packing (Im et al. 2021), covering (Ba-
mas et al., (020) and secretaries Dütting et al. (2024). This
paradigm also has applications beyond online computation,
and has been used to improve the runtime of algorithms for
classical problems such sorting (Bai & Coester 2023)
learning- augmented one-max- search (Sun et al. 202T [enomar & Perchei, 2025). ) the proposed algorithms select the first price that exceeds a threshold (yy) which is a function of the prediction of the maximum price p" in the sequence. We revisit the prob- lem by first characterizing the class P, of all consistency- robustness Pareto-optimal thresholds 4. Next, we focus on specific family of Pareto-optimal thresholds within Pr which generalise the algorithm Sun et al. (2021) but also exhibit smoothness guarantees. In particular, our anal- ysis quantifies smoothness in this family, showing it to be inversely proportional to the maximal slope of the corre- sponding threshold. Guided by this insight, we find the threshold that maximizes smoothness within the class P,.
In previous works
and graph problems (Azar et al. 2022), as well for the design of data structures such as search trees (Lin et al., 2022). dictionaries (Zeynali et al. 2024). and priority queues (Benomar & Coester). We emphasize that the above lists only some representative works, and we refer to the online repository of Lindermayr Megow (2025).
Pareto-optimal algorithms. Several studies have focused on consistency-robustee trade-offs in Wei & Zhang 2020
augmented
algorithms, e.g. (Sun et al. 2021
Lee et al. 2024 Angelopoulos
2023
B Bamas ct al. 2020
Christianson et al. 2023 Almanza et al. 2021). However,
Pareto-optimality imposes constraints which may, in certain cases, compromise smoothness. The brittleness of Pareto- optimal algorithms for problems such as one-way trading was observed by |Elenter et al.) (2024), who proposed a user- defined approach smoothness, and by [Benomar & Perchet (2025) who relied on randomization. These approaches dif- fer from ours, in that the profile-based framework of Elenter et al. (2024) does not always lead to an objective and mea- surable notion of consistency. Moreover, we show that randomization is not necessary to achieve Pareto optimality.
Furthermore, this quantification of smoothness allows to establish a near-matching lower bound. Specifically, we show that, for a multiplicative definition of the error, no Pareto-optimal algorithm can guarantee better smoothness than our algorithm, for a large range of robustness values. For the additive definition of the prediction error, which commonly used, we show that our algorithm optimises smoothness for all robustmess values, thus attaining the triple Pareto front of consistency, robustness and smoothness.
The combination of smoothness and Pareto-optimality of our family of thresholds has direct practical benefits in han-
One-Max Search. EI- Yaniv 19988) showed that the op- timal competitive ratio of (deterministic) one-max-seare is 1/V0, under the assumption that each price in the se-
2

---

Pareto-Optimality. Smoothness, and Stochasticity in Learning-Augmentted One-Max-Search
quence is in [1,0], where 0 is a known upper bound on p". This assumption is required in order to achieve bounded competitive ratio and has remained in all subsequent works on -agmmnetedd algorithms for this problem, such as (Sun et al. 2021 Angelopoulos et al. 2022 Sun et al. 2024; Benomar & Perchet, 2025). The randomized version equivalent to the one-way trading prob- lem, in which the trader can sell fractional amounts. The op- timal competitive ratio, for this problem, is ((1/ log () (El Yaniv 1998). Pareto-optimal algorithms for one-way trad- ing were given by Sun et al. (2021), [ewever[Flenter et al. (0024) showed that any Pareto-optimal algorithm for this problem is brittle and thus cannot guarantee smoothness. One-max-search and one-way trading model fundamental settings of trading, and many variants and generalizations have been studied under the competitive ratio, see the sur- vey (Mohr et al.] 2014). One must note that worst-case measures such as the competitive ratio aim to model set- tings in which no Bayesian assumptions are known to the algorithm designer. There is a very rich literature on optimal Bayesian search, see, e.g. (Rosenfield & Shapiro 1981).
Sun et al. (021) established the Pareto front of the consisiency-robusteess trade-off, albeit using different convention (the inverse ratio p²/ /ALG) for the competitive ratid] Under our convention, their results show that the Pareto front of consistency and robustness is the curve:
{ cro = for (c, r) E [0-1/2
1/2 1] x 00120-112) } (1)
of one-max-seardee
In contrast, we are interested not only in consistency- robustness Pareto-optimality but also in smoothness, namely in the performance as a function of the prediction error "(p", y) == lp* - yl. An algorithm is called smooth if the ratio (L (p. y)/p" is lower bounded by a mon-constant) continuous and monotone function of the error n(p", ,y).
3. Pareto-Optimal and Smooth Algorithms
In this section, we present our main result in regards to deterministic learning augmented algorithms,, namely a Pareto-optimal and smooth family of algorithms for one- max-search. Our approach is outlined as follows. We begin by characterising the class of all thresholds P, which in- duce Pareto-optimal algorithms (Theorem 3.I) We then present family of thresholds in Pr. parametrised by a value E [0, 1] Bg. 2)) that characterises their smooth- ness and we show that = 1 yields the best smoothness guarantees. We complement this result with Theorem 3.3 which shows that not only is our algorithm smooth, but any Pareto-optimal algorithm cannot improve its smoothness.
2. Preliminaries
In the standard setting of the one-max-search problem, the input consists of (unknown in advance) sequence of prices p== (p:) E [1, 0", where the maximal range 0 is known. At each step i E [n]] the algorithm must decide irrevocably whether to accept pt, terminating with payoff of pi, or to forfeit p; and proceed to step i + 1. If no price has been accepted by step n. then the payoff defaults to 1.
Before we discuss our algorithms, we note that the ran- domized algorithm of (Benomar & Perchet 2025) has a measurable and significant deviation from the Pareto front, even in comparison to deterministic algorithms; see Ap- pendix D.3 for the expression of the deviation. Furthermore, the guarantees of their algorithm hold in expectation only, whereas the results we obtain do not rely randomisation.
The competitive ratio of an algorithm is defined as the worst- case ratio (over all sequences p) between the algorithm's 's payoff and p", the maximum price in the sequence. A natu- ral approach to this problem is to use threshold- algo- rithms, which select the first price that exceeds a predeter- mined threshold & E [1, 0). We denote such an algorithm by Ag. In particular, the optimal deterministic competitive ratio is 1/ v and it is achieved by A YaniYaniv 1998). Focusing on this class of algorithms is not restrictive, as in worst-case instances any deterministic algorithm performs equivalently to a threshold algorithm (see Appendix B)
We now proceed with the technical statements. Theorem 3. below provides characterization of all thresholds that yield Pareto-optimal levels of consistency and robustness.
Theorem 3.1. For any fixed of robustness r, the set of all thresholds & [1, + [1,0] such that As has robustness and consistency 1/r0 is
In the Bamming-augmenter ceives a prediction y of the maximum price in the input p. The payoff of an algorithm ALG in this setting is denoted by AL y)- In this context, threshold rules are defined as mappings Φ. [1, 0] + [1, 8) that depend on the prediction. We use again Aa to denote the corresponding algorithm. We denote by c(ALG) and by r(AGG) the consistency and the robustness of the algorithm, respectively, defined as
setting, the decision-maker re-
Pr = + : Vz E [1, 6] : r0 S <0{)) 1
V2 E [r0, B : r0
2
s (2)) S sz)
Figure 1 Iillustrates the set P, (shaded).
We prove the theorem via double inclusion. First, if a threshold function &b belongs to Pr. then we use the bounds
'The convention that the competitive ratio of the maximization problem is in (0, 1] allows for eleaner bounds the performance as a function of the prediction error.
c(ALG) = inf ALG
ALG(p. v) P p* r(AAG) = inf
P.V
p*
3

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmented One-Max-Scarch
1/r
1/r
P (0,1)
Threshold sxyy)
Threshold of (y)
(
r0-
r0
1/r
70
1/r + F)
Prediction c [1,0]
Prediction y (1,0]
Figure 1. depiction of the Pr of Theorem A threshold + is r-robust and 1/rê-cconsie consiseett if and only if it is function whose graph lies the shaded area which defines P...
Figure 2. The threshold functions $f of Af, defined by Eq. Note that all are equal on [1, ().
Figure illustrates the threshold functions pElo)) No- tably, the case = corresponds to the algorithm of Sun et al. (202I), while at the other extreme (p = 1) we obtain the threshold b + max(r0, (r)).
on defining P, to prove its Pareto-optimal robustness and consistency. Conversely, for Pareto-optimal & we anal- yse the worst-case instances Z,, (q) (Equation (15). where prices increase uniformly from 1 to q before dropping to 1. By evaluating the ratio AL y) v)/p' these instances for well-chosen q. we show that 4 E P,.
The standard definition of smoothness involves demonstrat- ing continuous degradation of algorithm performance as function of the prediction eтror
We now turn to identifying smooth algorithms within the class P,. Let us begin by giving the intuition behind our approach. Our starting observation is that the algorithm of Sun et al. (2021) uses the threshold
nppp v) = yl
A key limitation of 17 is its sensitivity to rescaling multiplication of the instance by constant factor-which makes it less suitable in the context of competitive analysis. A common solution is to express bounds in terms of the relative error
r0
if E [1,
(v)
(v)
y E [r0, 1/r)
1/r
y E [1/r,0]
<p y)
y/
wherein
p"
r0 - 1
1 - 220
2 1-r +
is often done in prior work on rithms. However, this introduces another complication: the asymmetry between and p²
algo-
r r0
the line defined by (r8, r0) and (8, 1/r). The function Φ is illustrated in Figure 2] in dashed orange. The analysis of Benomar Perchet (2025) revealed that the brittleness of this algorithm arises from the discontinuity of Φ the point 1/r, illustrated in Figure 2 This observation suggests that the smoothness of an algorithm A. is influenced by the maximal slope of the function - o(2). To confirm this intuition, we analyse a family of algorithms {Ef)PE) associated with the thresholds (*)(w)) defined by
overcome these issues, we use a multiplicative error mea- sure that retains the desirable properties of scale invariance and symmetry:
(p',v) ( + min {
pp -r y ppppp 1
y
E:
(3)
This error measure has previously been used in the con- text of mechanism design with predictions (Balkanski et al. 2024). Note that perfect prediction corresponds to E(p".v) .)) 1. We primarily focus on & in the remain- der the paper. However, we also provide smoothness results using the additive error measure 17 for completeness, in Section 3.2
re
y y E (1)
(r(())
if (r0,
- (x(
(2)
(r())+ p(1 r()-r)
y
if [ + +p0 ((0-1)) 1))
r
1/r
if E [ + p(0 0)

---

Pareto-Optimality. Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
3.1. Multiplicative error &
This implies that, for r E [0-1,0-2/a], Algorithm A, at- tains the triple Pareto-optimal front for consistency, robust- ness, and smoothness among all deterministic algorithms for one-mane mee-maax--eheee For E [0-2/3, 0 0-/1/1, A, remains smooth and Pareto-optimal; however, its smoothness guar- antee might admit further improvement.
This first theorem establishes smoothness guarantees of the family {Af tr.p with respect to the error measure E.
Theorem 3.2. The family {A.tr.p satisfies
(0,
2 max
r. (0 E(-" .0)²))
1
(4)
pr
We conclude this section with some observations. First, note that many
algorithms in the literature express consistency and robustness in terms of a parameter À E [0, 1). which reflects the recision-maked trust in the prediction. A simple yet effective parametrisation of A can be achieved by setting r = 0 (1- Noting that I 1/r0- = 8 A/2 and In(ro) = A. the result of Theorem 3.2 can be restated, with this paramctrization, as
with 8p :- max (I.
l In(re) (m(o)
- 2) for P E [0, 11.
For P E [0, 1], the threshold defining AC lies in Pr, en- suring r-robustness and 1/r8-consistenge (Theorem 3.1). To establish smoothness, we determine the best value of s such that AL/p" 2 (1/r0)E* across all price sequences and predictions. Since the threshold is piecewise-defindd, it suf- fices to analyse cases based y and whether the maximum price is above or below the threshold, The final smoothness guarantee is then determined by the worst such case.
A, v) p'
2 max (0-1-2), 0 "x""" m))ma(113-22)
A second observation is that the obtained bounds can be readily adapted to the inverse ratio p" /A, y), which is also commonly used to define the competitive ratio in one- max mex-search (EI- Yaniv 1998). Specifically, by defining the inverse error as E 1/E max {
The smoothness in Theorem 3.2 is quantified by the ex- ponent 8p of E. A smaller value of sp results in slower degradation of the bound as function of prediction error, i.e. improved smoothness. In the limit p~ O, the exponent 8p becomes arbitrarily large, which results in extreme sen- sitivity to prediction errors, i.e. brittleness. In contrast, the best smoothness is achieved by 1, yielding an exponent
we obtain p" y pp"
p S min (0- (0'-3,0EE()) E(p",, (
(p.
== $1 max (I. 1n [n(r
- 2)
The above positive result naturally raises the question: is the smoothness guarantee of Theorem 3.2 optimal among Pareto-optimal algorithms? This question is addressed by Theorem 3.3 which gives a lower bound on the smoothness achievable by any Pareto-optimal algorithm.
3.2. Extension to the additive error r]
While the multiplicative error provides a more natural fit for the problem at hand, we also derive smoothness guarantees for A using the additive error nypp,, y) = -p" y/- More- over, we prove that the smoothness it achieves is optimal for r7, for all possible values of r E
Theorem 3.3. Let A be any deterministic algorithm with robustness and consistency 1/r0.. Suppose that A satisfies for all p E [1,0]m and y E [1,0) that
Theorem 3.4. Let A be any deterministic algorithm with robustness and consistency 1/r0. Suppose that A satisfies for all E [1, 0)" and y [1, 0] that
A(p. v) pr
2 max (r, E00", ,))²
(5)
A(p.v) pr
2 max (1. r. r0 - 3 np(p")))
for some R. then necessarily u
In 0 In[ro]
2.
p"
(6)
We first prove that, on worst-case instances I, (g). any Pareto-optimal algorithm behaves like a threshold algorithm. Using results from Theorem 3.T we establish that its thresh- old function must belong to P,. Finally, using the definition of P, with well-chosen q and y, we derive lower bounds on the smoothness s.
for some 3 2 0, then necessarily B > B", where
8r 1 7-0
1
1
max
T- r0
r0
Moreover, Algorithm A, satisfies 66) with 3 = 8", which shows its optimality.
This lower bound shows the optimality of the exponent achieved by A for r < 0 2/3, Indeed, if this condition is satisfied, then Theorem 3.2 gives
The above theorem establishes that A has the best possi- ble smoothness guarantee amongst all Pareto-optimal algo- rithms. Consequently, achieves a triple Pareto-optimal trade-off between consistency, robustness, and smoothness.
(p.v)) p*
1 r. r
In o
2 max
Elp", y) In(ro)
5

---

Parcto-Optimality Smoothness, and Stochasticity in Learning-Augmenntd One-Max-Scarch
4. Stochastic One-Max Search
coupling x² of (P*, (P",,),,, yielding
One-max-searts under competitive analysis is a worst-case abstraction of online selection which is highly skewed to- wards pessimistic scenarios. This is an approach rooted in theoretical computer science that has the benefit of worst-
EJALG(P", .Y) := / |LGG(p", (uG(p",y)dd" yydx" (p",)).
(7)
In consequence, we can identify π'' and the instance (P", Y) ~ n²' without loss of generality, as all such in- stances are indistinguishable to probabilistic analysis.
case guarantees, but does not capture the stochasticity of real markets, c.g. (Cont& & Tankov 2004; Donnelly 2022). In contrast, in mathematical (and practical) finance, prob- abilistic analyses such as risk management are preferred, e.g. (Merton 1975). While reconciling the two approaches remains very challenging perspective, we aim to narrow the very large gap between the worst-case and stochastic regimes by leveraging a probabilistic approach. This ne- cessitates algorithms that can be robust to the randomness of the market, and to this end, the established smoothness of our algorithm (Section(3 B will play a pivotal role, as we will show. probabilistic analysis can thus yield two main practical benefits: 1) estimate performance under price dis- tributions obtained from financial modelling: 2) leverage the consistency-rroustness trade-off to handle risk.
Taking into account the coupling, the bound of Theorem 3.4 adapts to the stochastic setting to yield Lemma 4.1
Lemma 4.1. The family {Ar)r satisfies
(P,, max { 1 E EE YY E|P
{". r0 E[P
(8)
Proef. Apply Jensen's inequality to Theorem 3.2
As expected, (8) shows that the robustness of {A.) carries over to the stochastic setting through the max(r, . term.
4.2. Instantiations of Lemma 4.1
In the stochastic formulation of one-max-see maa-hh, we now consider the prices (P:) to be random variables whose maximum is P ~ F Since market prices are random, the historical data used to generate machine-learne prediction should also be random, hence we consider the prediction to be random variable Y ~ G. As before, we consider that P., for i E [ni] and Y take value in [1, 0). The trading window unfolds as in the classic one-max- max-search problem, except that the prices and predictions are now random.
The coupling x", and Eq. (8) more broadly, encode effects that influence the quality of prediction from two different sources: the relationship of G and F* and the relationship between Y and P themselves (e.g. correlation). In this section, we aim to isolate the effect of G and F*.
Stochastic predictions, deterministic prices
This semi-deterministic model, in which F = 6p- (which is to say p = p" almost surely), isolates the effect of G. From practical standpoint, it can also be used to model predictions which are noisy measurements of deterministic, but unknown, quantities. Its theoretical interest comes from the fact that it simplifies Eq. 7 into an integral over F*. This allows us to derive Corollary 4.2 from Lemma 4.1 in which the function A
We will first give, in Section 4.1 a general probabilistic competitive analysis of the seee-max-searde problem which transfer naturally by according to the cou- pling of (P*, Y). In order to better understand the intuition behind these results, in Section 4.2. we instantiate the analy- sis with three insightful models. Finally, in Section 4.3 we analyse the effects of F* and G, first in isolation, and then jointly using analytical tools from optimal transport theory, to characterize how their interaction influences the outcome beyond their individual effects.
shows that the bounds of Section 3
weighting the bounds of Theorem
[1, 8] - [0, 1] defined by
A(p") ) = E [E( Y> =p"]
for p" E [1, directly quantifies the quality of the predic- tion in terms of the performance, with respect to the true, realised, maximal price p'. Indeed, A(p") I 1 for all p". and the closer to one, the better the prediction.
4.1. Competitive analysis in the stochastic framework
In particular, if the maximal price is deterministic, but the prediction is stochastic, this yields the following guarantees. Note that, for the sake of clarity of the results, we will no longer specify the term coming from the robustness, with the understanding that one can add maximum with to any bound on the performance of (A!
In the stochastic setting, we will evaluate the perfor- mance of the algorithm using the ratio of expectations B|ALG(P* {))/E(P*). but our results and arguments transfer readily to ())
Because any algorithm must operate on the realisation of Y, its performance becomes a random variable depending on the specific relationship of P* and Y. This is captured the
Corollary 4.2. Let F = 5p. for some p" E [1, 0). then the family (A2 satisfies
E'A, Y)
1
10 A(P').
(10)
E P1P*
6

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Viewing A as map (taking G real-valued function on [1, f) reveals that it quantifies the usefulness of G as prediction distribution at any p² [1.0].
Independent stochastic predictions and prices
The theoretical value of the above two models is their isola- tion of the effect of G into A (resp. F" into T). We now turn to a model in which Y and P are independent (denoted by " = F & G) which will illustrate that predictions can be useful even without any correlation. The intuition is simple: some inaceurate predictions can still induce (on average) good thresholds because of the algorithm's 's internal mechan- ies. This effect is captured by the interaction between the functional A and the distribution of prices F* (resp. Y and
As an integral functional of G. A may not admit a closed form. Nevertheless, it can be estimated to capture subtle stochastic phenomena as demonstrated by Example 4.3
Example 4.3. Let F = =ōp- for some p' E [1,0] and G = Unif([p" - e.p + e]). There is a constant C > 0, dependent only on (s, f), such that
EJA, P YI E
1
1 8 c- ) (11)
G), as shown by Corollary 4.5
Corollary 4.5. Let = F @ &G the family {A]]r satisfies
P*
rf
2p"
as soon O <E S min pp, 1}.
BIA P"
.Y
1
/ (())aG())
2
E PM
r0
Eq. reveals that the performance of {A,), decays from consistency at a rate linear in the uncertainty e, determined by the smoothness 8 of the algorithm. This captures the scale of the effect of smoothness on a practical example. In Eq. T we characterised the rate up to the second order (e"), but higher-order estimates can be obtained similarly.
[>-Ne' r E[P*]
1
/
(F"
(13)
Since A(2) is always smaller than 1 (and again, the closer to one, the better the predictions are), Eq. [3 gives an intuitive bound on the performance of the algorithms.
Moreover, this shows that all sufficiently regular distribu- tions can be approximated in terms of A using mixtures over the model of Example 4.3 i.e. G G= Wi. Unif(/+)) for w; > 0, Σ, w/ = 1, and (7x) disjoint subintervals of [1, 8] (see Corollary C.2). Numerical integration (e.g. Monte- Carlo) offers another alternative method to estimate A.
The theoretical benefit of the model transpires in Corol-
lary 4.5 independence separates the integral against x* in
Eq. 7 into a double integral revealing T. Unfortunately, it is often difficult to obtain a closed form for the resulting expression (see, e.g., Proposition C.5). but one can rely on numerical integration instead (see Figure 5 in Appendix Cl.
Deterministic predictions, stochastic prices
4.3. Dependent predictions and optimal transport
The performances of our family of algorithms can also be computed if the prices are stochastic, but the prediction is deterministic. This model swaps the randomness: now the prices are random so that p² ~ F is generic and it is Y ~ 6y which is deterministic.
The previous models successfully isolated the effect of the distributions F and G. Using tools from Optimal Trans- port (OT) theory, one can generalise this approach. For brevity, we refer simply [Villani 2009) for the technical- ities and background of this field. The key observation is that the right-hand side of Eq. 77) is a transpori functional of π², which can be lower bounded uniformly over the set of couplings II(F" G) of F* and G. This set is exactly the set of joint distributions for (P*, Y) when p ~ F and Y G. Minimising a transport functional over couplings is the classic OT problem (Villanil 2009), hence Theorem 4.6
While this setting appears symmetrical to the previous one, this is not the case as the one-max-sen search problem itself is highly asymmetrical. Indeed, using threshold means that predictions too high or too low do not have the same impact. By defining
T(v) E(P' ,Y = for y E O), E[P*]
Theorem 4.6. The family (AL)r satisfies
we can establish a quality quantification which mirrors A: this functional of F* states how good any unique prediction y is at influencing algorithmic performance. This yields the following Corollary 4.4 analogue of Corollary 4.2 Note that Tvy < 1 for all y [1.6].
1 inf p² E(p (""(("")"dmm ,v)
E EIA .Y1 EE E
(14)
r
E[Pa]
where the infimum is taken over couplings и E [T G) in particular, this implies the numerator is as most B[P').
Corollary 4.4. Let G 8y for some y E (1. The family (A satisfies
Theorem
highlights a novel connection between (stochastic) competitive analysis and optimal transport. Con-
4.6
E (P' Y) 1
'The following result also applies to sampling of distribution- valued predictions (Angelopoulos et al. 2024 Dinitz et al. 2024).
T()).
(12)
E[Pa]
E
r0
7

---

Pareto-Optimality Smoothness, and Stochasticity in Learning-Augmentte One-Max--ee One-Max-Scarch
trary most literature in OT, in which the optimal configura- tion tries minimise the distance points (f", .y) moved, the infimum in Eq. (14) tries to push them far apart to induce the algorithm to make mistakes.
p =0
1/r8-
p U.5
Empirical ratio
0.6
p
Optimal transport tools have been used before algorithms with predictions, notably the distributional predictions setting in which the algorithm given G itself (Angelopou los et al. 2024 Dinitz et al., 2024). This analysis, however, is fundamentally different: uses Wasserstein distances (see Appendix D.4) in place of in quantifying the error of the distributional prediction G of F* Our stochastic framework ties its error metric closely to the asymmetric nature of the problem through p" (p"" which why our OT problem, i.e. Eq. (14), not symmetrie: exchanging the roles of (G, F²)) cannot be expected to yield the same performance.
0.5
0.4
0.0
0.2
0.4
0.6
6min
Figure 3. Performance of AC with p E {0, 0.5, 1}.
The optimal transport problem in Eq. (4) generally has no closed form, but thanks to its (strong) dual form (see Appendix C one can use problem-specific knowledge to derive lower bounds, as demonstrated by Proposition 4.7
1/r0
=
Empirical ratio
0.5
Proposition 4.7. The family {r satisfies
0.4
0.3
F (p")
(p*)
(P Y) E[P']
P'
Moreover, the RHS is the infimum over G of Eq. 14p
0.0
0.2
0.4
0.6
0.8
a
[0,
Proposition 4.7 once more highlights the asymmetry of the problem through different contributions of the regions above and below ve, which the threshold that guarantees 1 1/v0- robustness. The dual problem provides thus practical tool for designing lower bounds for the performance of {A.), in the stochastic one-max search setting.
Figure 4. Comparison of A} and A, the Bitcoin price dataset.
generate the prediction y by sampling uniformly at ran- dom in the interval [p* Emin p" /Emin] (2 E(p" 2) 2 For Emin E (0, 1], Figure 3 illustrates the worst-case ratio inf infp-=11. Eyy (A, wu)l/p", where the expectation is es- timated empirically using 500 independent trials. The figure also shows, with dashed lines, the theoretical worst-case ratio corresponding to the given error level Emin-
Emin.. then compute the ratio (FI((
5. Numerical Experiments
To complement our theoretical analysis and evaluate the performance of our algorithm in practice, we present exper- imental results in this section. We defer additional experi- mental results Appendix
Figure 3 Jhoows that for the different values of p. the worst- case ratio 1/r0 when the prediction is perfect, i.e. Emin 1, and degrades to when the prediction be arbitrarily bad, which is consistent with Theorem 3.1 However, the ratio achieved for = 0 drops significantly even with a slight perturbation in the prediction, while the ratios with p {0.5, 1} decrease much slower. This is again consistent with the smoothness of AG, as shown Theorem 3.2
5.1. Experiments on synthetic data
We fix 0 À 0.5, and (1112)/2) We consider instances (4) pej. where In(g) is the sequence start- ing 1, and increasing by n-1 at each step until reaching g. after which the prices drop 1. A more formal defini- tion of this instance can be found in Equation [5] These instances model worst-case instances with maximum price and they are used in general to prove impossibility results in the one-max-see sea-sh problem.
5.2. Experiments on real data
further validate our algorithm's 's practicality, we evaluate on the experimental setting of (Sun et al.] (022). Specifi-
We fix an error level Emin and, for each p* E [1,0], we
8

---

Pareto-Optimalit,. Smoothnes,, and Stochasticity in Learning-Augmeetted One-Max-Search
cally, we real Bitcoin data (USD) recorded every minute from the beginning of 2020 the end of 2024. The dataset's prices range from L = 3, 858 USD to U = 108, 946 USD, yielding 0 = U/L = 28.
Impact Statement
This paper presents a work whose goal is to advance the field of rearing-auggmente algorithms. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
We randomly sample a 10-week window of prices Wo, let W-1 be the 10-week window of prices preceding Wo and take the prediction y = a max -1 + (1 a) max Wo- Here, a captures the prediction error: a 0 represents perfect foresight, while a 1 corresponds to a naive pre- diction equal to the maximum price in W-1. To simulate worst-case scenarios, the last price in Wo is changed to L with a probability of 0.75. For each value of a, we sam- ple m = 100 windows (W:))m and compute the ratio Rm = min, (Aj /)/ max W for p 10, We then empirically estimate B[Rm] by repeating this process 50 times. We choose the robustness r of AG, by setting 1 [0, 0]
A Acknowledgements
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project the grant DOOM ANR23-CE23-0002 It was also funded by the European Union (ERC, Ocean, 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
and through
and r = 0 (1-2//2)
Figure 4 shows the obtained results with x A= 0.5, and com- pares our algorithm A, to the algorithm of (Sun et al. (202)) which corresponds A.. For a = O, i.e. perfect predic- tion, they both achieve the consistency 1/r0.. However, the error increases, A quickly degrades to the robustness guarantee r, whereas A, degrades more gradually.
This work was also partially funded by the project PRE- DICTIONS, grant ANR-23-CE48-0010 from the French National Research Agency (ANR).
References
Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A.,
6. Conclusion
and Re, G. Online facility location with multiple advice. Advances in neural information processing systems, 34: 4661-4673, 2021.
We provided an intuitive Pareto-optimal and smooth algo- rithm for a fundamental online decision problem, namely one-max-search We believe our methodology can be applied to generalizations such as the k-search prob- lem Lorenz et al.) 2009). i.c. multi-unit one- mne-max-search recently studied in a learning-augmente
Angelopoulos, S. Online search with a hint. Inf. Comput., 295(Part 1):1050 2023.
setting (Lee et al. 2024). More broadly, we believe our framework can help bring competitive analysis much closer to the analysis of real financial markets since it combines three essential aspects: worst-case analysis, adaptivity to stochastic settings, and smooth performance relative to the error. A broader research direction is thus to extend the study of competitive financial optimization (see, e.g., Chapter 14 in (Borodin& & El-Yaniy 2005)) to such realistic learning-auss augnenned settings. This work also sheds light on connections between competitive analysis and optimal transport, suggesting the study of the geometry of OT problems induced by competitive analysis as promising direction for both theories.
Angelopoulos, S., Kamali, S., and Zhang, D. Online search with best-price and query-based predictions. In Proceed- ings of the 36th AAAI Conference on Artificial Intelli- gence, pp. 9652-9660. AAAI Press, 2022.
Angelopoulos, S., Bienkowski, M., Dür,, C., and Simon, B. Contract scheduling with distributional and multiple advice. In Larson, K. (ed.), Proceedings of the Thirty- Third International Joint Conference on Artificial Intel- ligence. IJCAI-24, pp. (652-3660. International Joint Conferences on Artificial Intelligence Organization, 8 2024. Main Track.
Our work also lays the groundwork for exploring triple Pareto-optimal frontiers among consistency, robustness, and smoothness. While our results establish optimal worst-case smoothness guarantees for both multiplicative and additive prediction errors, an intriguing direction for future research is to investigate how these bounds improve under additional assumptions, such as when the prediction error is known to be bounded.
Antoniadis, A., Gouleakis, T., Kleer, P., and Kolev, P. Secre- tary and online matching problems with machine learned advice. Advances in Neural Information Processing Sys- tems, 33:7933-7944, 2020.
Azar, Y., Panigrahi, D.,, and Touitou, N. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ALCM-SIAM Symposium on Discrete Algoritimms (SODA), pp. 35-66. 66. SIAM, 2022.

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmennte One-Max-Scarch
Bai, X. and Coester, C. Sorting with predictions. Advances in Neural Information Processing Systems, 36:26563- 26584, 2023.
Gollapudi, S. and Panigrahi, D. Online algorithms for rent- or-buy with expert advice. In Proceedings of the 36th International Conference Machine Learning, ICML, volume 97 of Proceedings of Machine Learning Research, pp. 2319-2327. PMLR, 2019.
Balkanski, E., Gkatzelis, V. Tan, X., and Zhu, C. Online mechanism design with predictions. In Proceedings of the 25th ACM Conference on Economics and Computation, 2024.
Im, S., Kumar, R., Montazer Qaem, M., and Purohit, M. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems, 14:2733-2743, 2021.
pp.
Bamas, E., Maggiori, A., and Svensson, O. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083- 20094, 2020.
Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, Online scheduling via learned weights. In Pruceed- ings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859-1877. SIAM, 2020.
Benomar, Z. and Coester, C.
Learning- auggnnnte prior- ity queues. The eiihty-eighth Annual Conference on Neural Information Processing Systems.
Lee, R., Sun, B., Hajiesmaili, M., and Lui. J. C. S. Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. In The 15th ACM Inter- national Conference on Future and Sustainable Energy Systems, e-Energy 2024, Singapore. June 4-7, 2024, pp. 50-71. ACM, 2024.
Benomar, Z. and Perchet, V. On tradeoffs in learning- augmented algorithms, January 2025. arxiv. org/ /tbs//5501.. 12770 arXiv:2501.12770
[es].
Borodin, A. and El-Yaniv, R. Online computation and competitive analysis. Cambridge university press, 2005.
Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Ma- chine Learning, pp. 13431-13440. PMLR, 2022.
Christianson, N., Shen, J., and Wierman, A. Optimal robustness- comsssttessecnsssteenyyy tradcoffs for metrical task systems. In AISTATS, volume 206 of Pro- ceedings of Machine Learning Research, pp. 9377-9399. PMLR. 2023.
Lindermayr, A. and Megow, N. Repository of
works on algorithms with predictions. https:// a sigorit tarrtthmswwtte womms-withee www.hhhhhheicecco ions. witn....thu..i... 2025. Accessed: 2025-01-01.
Cont, R. and Tankov, Financial modelling with jump processes. Chapman & Hall/CRC financial mathematics series. Chapman & Hall/CRC, Boca Raton, Fla, 2004. ISBN 978- 1-88488-413-2.
Lorenz, J., Panagiotou, K., and Steger, A. Optimal algo- rithms for k-search with application in option pricing. Algorithnica, 55(2):311-328, 2009.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., Niaparast, A., and Vassilvitskii, S. Binary Search with Distributional Predictions, November 2024. URL tictt:///axiy org/ abtpa/as///11.11 16030 arXiv:2411.16033 [es].
Lykouris, T. and Vassilvtiskii, S. Competitive caching with machine learned advice. In International Conference on Machine Learning, pp. -3055. PMLR, 2018.
Merton, R. C. Optimum consumption and portfolio rules in a continuous-timg time model. In Ziemba, W. and Vickson, R. (eds.), Stochastic Optimization Models in Finance, pp.
Donnelly, R. Optimal Execution: A Review. Applied Mathe- matical Finance, 2932)188--21,, May 2022. ISSN 1350- 486X, 1466-4313.
621 621-661. Academic Press, 1975.
Dütting. P., Lattanzi, S., Paes Leme, R., and Vassilvitskii, S. Secretaries with advice. Mathematics of Operations Research, 49(2):856-879, 2024.
Mohr, E., Ahmad, I., and Schmidt, G. Online algorithms for conversion problems: a survey. Surveys in Operations Research and Management Science, 19(2):87-104, 2014.
El- El-Yaniv, R. Competitive solutions for online financial problems. ACM Computing Surveys, 30(():08 (:22:)966,,,) March 1998. ISSN 0360-0300.
Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via MI. predictions. In Advances in Neural Information Processing Systems, volume 31, pp. 9661 9670, 2018.
Elenter, A., Angelopoulos, S., Dür,, C., and Lefki, Y. Over- coming brittleness in ppreto-optimal learning augmented algorithms. In The eighth- Annual Conference on Neural Information Processing Systems, 2024.
Rosenfield, D. B. and Shapiro, R. D. Optimal adaptive price search. Journal of Economic Theory, 25(1):1-20, 1981.
10

---

Parclo-OptimaliySSmonn Smoothness,, and Stochasticity in Learning-Augmentedd One-Max-Scarch
Sun, B., Lee, R., Hajiesmaili, M., Wierman, A., and Tsang, D. Pareto-Optimal -aanningg-uumeeeted Algorithms for Online Conversion Problems. In Advances in Neural Information Processing Systems, volume 34, pp. 10339- 10350. Curran Associates, Inc., 2021.
Sun, B., Huang, J., Christianson, N., Hajiesmaili, M., Wierman, A., and Boutaba, R. Online algorithms with pnceetainty--uanniine predictions. In Forty-first Interna tional Conference on Machine Learning, ICML, 2024.
Villani, C.
Optimal Transport, volume 338 of Grundlehren der mathemaatschen Wissenschaften. Springer Berlin Heidellbrg, Berlin, Heidelberg, 2009. doi: 10.1007/ 978-3-540-71050-9.
Wei, A. and Zhang, Optimal robustnnss-consistennyy trade- offs for learning- augmented online algorithms. In Pro- ceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2020.
Zeynali, A., Kamali, S., and Hajiesmaili, M. Robust coemiing-augmentee dictionaries. In Forty-first Interna lional Conference on Machine Learning, ICMI, 2024.

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmenter One-Max-Scarch
Appendices
A. Organisation and Notation
A.1. Organisation of Appendices
The following appendices are divided in the following way: Appendix Bonttainss the proofs of Section 3 while Appendix C
contains proofs of Section 4 In both cases, they follow the order of the main text. Appendix E provides further experiments
not included in Section 5 After these sections which are ordered according to the text, Appendix D transversal and regroups results in which the error analysis is additive instead of multiplicative.
A.2. Notation
The space of probability measures over set denoted (S). The set of couplings between G and F* [TG,, F*) == {π ([1, 0} [1, G, <{[1, -) F*} } For R. dg denotes the Dirac Delta distribution (i.e. the distribution of degenerate random variable X satisfying P(X x) = 1).
B. Proofs of Section
We present in this appendix the proofs of the results stated in Section that we will use throughout the proofs. For all n 2 1, we denote by (p >== the sequence of prices defined by
3 Let us introduce some notations and observations
vi E [n]
p. =
1),
and for all E (1, we denote by In (g) the sequence of prices that equal p while the latter is smaller than g then drops to 1. Formally, the 7th price in this sequence is
[.(g): = 1 + (p) 1)
(15)
On the class of instances {In ge) any deterministic -ugginnted algorithm for one-max mex-search equivalent to single-threshold algorithm Ag. Moreover, observe that the payoff of As satisfies
1 Ao (In (g).)) = (vv) +
if (()) > otherwise
(16)
Indeed, if the threshold exceeds the maximum price g in the sequence, then price is selected and the algorithm is left with payoff of 1. On the hand, if the threshold is at most g. then the selected price is min(p; p 2 ( By definition
of the prices yf. this value is in {v)), (v)) + --Tl.
@-11 In particular, for arbitrarily large, the payoff of an algorithm with
threshold (y) S is arbitrarily close (yy) This observation will be useful in our proofs.
B.1. The class of all Pareto-optimal thresholds
Theorem 3.1. For any fixed of robustness the set of all thresholds 4 [1, + [1, 0] such that As has robustness r and consistency 1/r0 is
P. = Φ V2 E [1,0] 10 +(=)
E [r0,0] < <())) 5}
Proof. Let क: (1 + (1, and consider that As r-robust and 1 1/r0-consistent, We will prove that t is necessarily in the set P,..
First inclusion. prices (.) Since Ag is r-robust, then by Eq. (16). it holds for (02) and that
Let us first prove that (2) [r0, 1/r] for all E [1, 0). Let 2 E [1, 0], and consider the sequence of
A (Q)) 2)
1
((2)
12

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
On the other hand, for q 0, obtain again using Eq. (T6) that
Ap (In 2)
+(2)+
0
We deduce that (2) satisfies (2)) [r0- - -( 1/r + H.1. and taking the limit for n + oo gives that ((z) E |r0, 1/r].
Consider now (r0, f). and let us prove that (2) [ 2]. We first prove by contradiction that +(2) S 2. Suppose this is not the case, i.e. ((=) then using Equation (T6) and that the algorithm is 1/r0-coosissent,, considering that the maximum price is and the prediction is perfect, deduce that
As (I),
2
hence S r0, which contradicts the initial assumption that E (r0, 0). Therefore, +(2) S for all E (r0, 0). Using this inequality, it follows again by Eq. (16) and 1/r-consistency of the algorithm that
As (In
((z)
r
Consequently, (2) E 1- 2] for all E (r0,0). This proves that the set of all thresholds yielding Pareto-optimal levels of robustness and consistency (r, 1/rr) included the set P,.
Second inclusion. The other inclusion is easier to prove. Let & P,, and let prove that As is r-robust and 1/r0- consistent. Consider arbitrary sequence of prices (p:) E [1,0) and prediction E [1,0), and let us denote by p* the maximum price in the sequence p.
The robustness of Ag follows from the bounding (yy) E [ro, 1/r]. Indeed, we obtain using Eq. 16 that
pf <y( then Ao(p.))
(y)
r,
pf 2 (y) then (p(p.))
[(y)
rr,
which proves that Aq is r-robust. Now the consistency of the algorithm follows from the bounding ((2) 1,5 2] for all E (r0, 0). Indeed, assume that the prediction is perfect, i.e. y", then we have the following:
pf rr then Aulp,p") 1 48
pf > r0 then we have that (pp)) p², hence Au(p.r) T(p")
p²
This proves Aq is 1/r0-consissent, which concludes the proof.
B.2. Smoothness analysis of AC
Lemma B.1. Let 0, b E and oo) satisfying that ++ az + b 2 on the interval [u,v], then holds for all E R that
(az + 6)
(au + +6 (av b) c+1
max
max
#E [[
ve
Proof. For all z E [u, v). we can write that
(az + b)et1
az +b E+1
=(221/(+3)) + bz -e-eett)) e+1
2
/1((E+1)
13

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
hence, computing the derivative gives
d
az + b)(+1
[
(ast/let)) + be +b=-8/(et))
L+1
dz
2
dz
bl - (az-/(e-1) + bz b(-ett)) e
(l (e+ e+1
-((et1)
L E+12
az 1/(41))---11
bb (=-
(z-a) a
(az1/(+1)) + ba te-tRett)e
The monotonicity of H fa on the interval [u, v] is therefore determined by the sign of = b Indeed,
a=-t/((+)-- 2 0 because 2 0 and 2 u 0, and the term (az1/(e+1) + be bz-e(((1))) is also non-negative be- cause we can write that
(a2M/EDD) + bz be=e/())))
[[ (asV/Ctt + b2 (((ttt)
6+1 241
(az bb) क
and both z and az + are positive on the interval [u, v]]
(az+b) be either
Consequently, depending how compares to the bounds u, v of the interval, the mapping z + decreasing, increasing, decreasing then increasing. In the three cases, its maximum is reached in one of the interval limits v, thus
(az + b)et1
(au + 6)tt1 (av + b) ve
max. =E(u,0]
2t
max
ot
Corollary B.2. For all p E (0, 1). 8 = ( Ine
2)
holds that
In(ro)
+2(2))+1
max SEl +
2a 00.
Proof. By definition of the threshold Df,, we have for = E [ 1 + p(0 - }]
+ 1 - (z)
1
= (r)(2))
p(0 ) 2
which can be written as az + with gives that
2/r-pr(z) ((-1//3)
0 because (2) < 1/r for all 2 < 9. Consequently, Lemma B.1
@2)200+1
ΦP(1/r)ot1 L + p(0 1))=+1
=El 1 +p00- !!
max
2a
max
1/ra
( p(0 - f))
(1/r))0+
1/r041
max
(17)
1/r"
( + p(0 0 - 7))0
p(0
We will now prove that both terms in the maximum are most equal r0.
For all h I. we have the equivalences
111
1
510
p1+p(r0- 1)) I r20
( + p(0 - 1))²
+ hn (1+ p(r0 1)) S In((r2) = -Inn 1l(()))
In - 221((00)
h
In (1 + p(r0 1))
14

---

Pareto-Optimality Smoothness, and Stochasticity in Learning-Augmenteed One-Max-Scarch Moreover, have by concavity of ++ In that
+ p(r0 - 1)) = In (pr0 + (1 (1-p)) p)) 2 plu(r0) + (1 - p) In = -ll(pt))n)))))
therefore,
In In(rd) -2) satisfies
1 In -2) In 21n(r0) plm(r0)
In 21n(r8) In (1 p(rO 1))
(n(rr)
and we deduce with the previous equivalences that
1/r041 ( + p - 2))²
S r0.
(18)
Let us now prove that (-(1/r)==1 1/r" S r0. Since for is linear mapping with positive slope, using that 1/r E [r0, and
Lemma B.I
we obtain that
(r(1/r)ot1
(x(2)=+1
S max =E(r0,0)
1/rs
2²
yr (10)
(0) spr
max
(r0)s
(1/r)at1 0r
(rd))t1
max
(r0)*
0=
r0, θ
max
(r0))+I
Observing that 1c ps =
is the solution of (ro)a+) rf, and given that h: S and p S 1, we have that
In re
0
(r0)a+I S (r0) r0,
hence
pr (1/r))at
Pr (1/r)/+++
max { r0, (ro)att =r
(19)
1/73
1/rk
Finally, using Equations
17 and
we deduce that
(f(2))+1 x+1
max = + b S r0
which concludes the proof.
Theorem 3.2. The family (AC) satisfies
Ap(
2 max r, ((p -))²)))
(4)
p*
2)) ) for pe [0, with sp == max (1, ( In(r0]
lng
Proof. Consider E 10-1.0-11/ 112]] an instance p == (p:) prediction y of p", and let E min( P²). We will prove p";
the smoothness guarantee separately on the intervals r0), (r0, 1/r], [1/r, 1/r p(0 1 1/r)], and [1/r + p(0 1/r),
To lighten the notation, we simply write for max (1, _ in
(n(r() 2)) instead of sp-
15

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
1. 1. If y E (,, then (f(y) v00 pf < r0 then
vp p*
p
r0
r0
and if p" 2 r0 then the payoff of the algorithm is at least equal the threshold r8, hence
(p)
rf
1
1
3
p
p
p
p
r0
r0
We used in the last two incqualities that 1. r0 2 1 and s 2 I.
p- 2 E,
Case 2. Consider now the case of E [r0, 1/rl, of the algorithm is at least equal to the threshold. Using that 2 2 E, 2 and p S 0, we obtain
then (3( = (r( = r0
I-r + 1-1a0 M 1f 2 +b(()) then the payoff'
I-T
r0
p
AC v) pa
BC(1)
(r(())
p
pr
r - 1
1
1 - r20
1 y
1-r
pº
1-r
r0 pd
r0 - 1
1
1
1-
1
+
3
1-
pa
1-r
r0 E
r0
- 1
1- r20
1-r
1-r
(120 - r + 1-) E
r0(1
1 3 2 E0
1
(20)
r
r0
On the other hand, pf (v). recalling that (x(;) (z) for E [r6, 1/rl, we can use Inequality (19) from the proof
of Corollary B.2 which gives for l In
In(re) 2 that
(2)))++1
(2) A+1
max { r0, (r0))+I r
max * xE(r8,0]
zb
zb
and it follows that
AC. y)
1
p
p³
1
(f())++1
1
(ff(y)
(1)
70
yk
r0
y
1
Ek
E0
r0
9
r
r0
where we used in the last inequality that & < 1 and k < max(1, k) =s.
Case 3. For y E [1/r,1/r + p(0 - 1/r)]/ if 2 (y)) then observing that (b(()) 2 (v), we obtain with the same
computation as Eq. (20 that
A.
(y)
(v(
p
p"
p
r
On the other hand, if pf < (v()), then by Corollary
B.2
we have for h In e ln[re]
2 that
(=))) # k+1
max
S
$0
=EIL 1
+p Fi
2
4
16

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmeented One-Max-Search
therefore, the ratio between the algorithm's 's payoff and the maximum payoff be lower bounded follows
(p, y)
p
p
D
(y)
(2(y)
1
(v)
k
r0
r0
y
1
p
1
r0
y
r0
r0
The last inequality holds because //4 S max (1, ) = 8.
Case 4. Finally, if y (1/r + p( - 1/r), f), then (.(() = 1/r. If
2
1/r, then we have immediately that
(p. v)
1
p
rp
r8
r
Now if 1/y, let k: deduce from Corollary B.2
lu In(rd)
and
2p 1/r p0 1/r). Observing that 2 k, and y 2p. and ry 2
B/P
(1/r)
1/rr)+1
2(zp)
(f(2)² ++1
10/1
k/P
max =c [.p)
zbip S r0
ry
2p
2p
which yields for p* (1)
1/r that
AC u)
p'
1
p"
p
1/r
rf
ry
>
r8
=
r0
E
Conclusion.
All in all, for any y [1, 0] holds that
AC
v) 1
E9
D
r
with s = max ( in - 2)).
Finally, the threshold function D6. is in the class Pr, then we have by Theorem 3.1 that AC is r-robust, and deduce that
A₂ (p.
(1, r, -+)
1
max
p
which concludes the proof.
B.3. Lower Bound on Smoothness
Theorem 3.3. Let be any deterministic algorithm with robustness r and consistency 1/r0. Suppose that A satisfies for all Pe [1, 0)" and [1,0] that
A(p.v) max (1 ((p")))))))))
(5)
p
for some E R. then necessarily
In Intro]
2.
Proof. Let A be deterministic algorithm for one-max-search with, and assume that it satisfies for p and y that
A(p,y)
2 max (r. r:. (r.
pr
17

---

Pareto-Optimalty. Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
In partieular, A has robustness and consistency 1/r0.
To prove the lower bound, we will use the instances (g) ( defined in Eq. 13) On these instances, for fixed prediction y, any deterministic algorithm behaves as single threshold algorithm. Therefore, there exists + [1, 0] + [1, 0)
satisfying that A(In (g). v) = As (In (q), y) for all q, [1, 0).
The lower bound satisfied by ensures that it achieves Pareto-optimal consistency 1/(r0) and robustness r. Consequently, As also attaints them on the sequences of prices {Tn 9g) These instances are precisely those used to establish the constraints on Pareto-optimal thresholds in Theorem 3.1 which implies that the theorem's constraints hold for 2. In
particular, we have that (rrf) rf and (()) 1/r.
for some ε > 0. Since y < (0), when is given input the instance I, (4), it does not select the maximum price and ends up selecting price of 1, hence
Let and (0) Ite I+e
A (q), 0) = (1 + terr
q
Furthermore, by assumption, this ratio above is at least
1 - Elg. 0)" r
1 - ( ((++ 0
1
(r0)ut] (1 =)"
r0
(1+ E)ro
therefore, we have that
(1+e)r 2 (10)at1 (1 + E)4
This incquality holds for all 0, which gives in the limit - that
(r0)u+I
and we obtain by equivalences that
1 r 2 (r0)utI
(10))² 2 (r0)²
uln(r0) 2 In - 2 In(r0)
In
u ln(r 2
which gives the claimed lower bound on u.
C. Complements to Section
Recall in this section the notations P ~ F* for the maximum price, and Y ~ G for the prediction. When considered, their coupling is denoted T².
C.1. Complements on Section 4.2
Stochastic predictions, deterministic prices.
Corollary 4.2. Let F+ = óp for some pd [1, O), then the family {
satisfies
(PA
Y)
A(p*).
(10)
P
r0
Proof. This is obtained by direct instantiation of Lemma 4.1 In particular, for F 8p- the second term of Eq. substituted into with
g
be
= Y)* v'lp" / min
p
dG(w).
p y
Computing this integral explicitly reveals be A(p*).
18

---

Pareto-Optimality Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch Through this section, will use the following identity
M(p') App)=11 - S- ( /. y/ p
dG(y) + | (() dG(y).
(21)
which is easily derived from the proof above.
Inspection Eq. 2T reveals that A contains two different regimes (above and below p²). The mirrored coefficients of (p", in each term reflect the inherent asymmetry of threshold algorithm: performance is highly sensitive to whether p" S (Y),. which transfers to Eq. (2T) via the definition of E.
Example 4.3. Let F 6p- for some p E [1 and G
Unif((p* -e,p" +e)) There is constant C 0, dependent
only (s, 0), such that
E P Y)] E
1
2p t Ce2
(11)
P
rB
as soon as < m p=.p" 1}.
Proof of Example 4.3
1. Consider first s > 1. Compute p" A for this choice of G, which yields
A"p")") 1"
pp'
p'
1+s
pD tc
y ydy
y "dy
26
2c
p
pr
p 1-
p pelts - (p"
e)
p polto (p- + +e)1- ppl-
+
(22)
2c
1 s
2c
1
Continuous differentiability p* + p -+ and p² + 1-s along with Taylor's theorem, implies the existence of
(p)), [p" e,p²l x 1p" .p" + such that:
pz (p* Its
2
= =p
5 sp
3(3
1)p" 2-2 1
1 +
2
(p' c) 1-5 p p=1-s
2
3
cp"
sp
1-
8(8 1)p² 2
(2++)
1
Remark that one has the remainder bounds:
s(8 - 1) gminn(0.2-5)
8(8 11--1) 1) 3-
C1
6 p
6
s(1 + s(1 +
C2 ==
6
2+s 6p 2
Applying these bounds and the Taylor expansions of Ob Eq.
22 yields
p² A'A(p')
2
Cp
(23)
with -= (C,0** C2)/2. Finally, injecting Eq. yields Eq. (10).
23 into Corollary 4.2 and recalling that G = 5p. implies r = c/p'
2. Now, for 1, the computation of A reduces to
p²
(p"
cc)
p¹² 1o0 pp'+e
+
dy
2c
2
2c 4"
p²
+ n²
(log(p" + +e) log(p")
19

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmeented One-Max-Scarch
Using a Taylor expansion on log, for some / [0, have
x2
p²2
c²
3
(log(r" + - -log(r)) 2
+
2c
20
p
2
pr²
6 2(p" + ct)3
p
6²
24
and thus, we obtain an overall bound matching Eq. (23)
up modifying C.
Corollary C.I. Let F 6p for some p" [1,00 and G Unif([p"(1 -'),,"'' + t()). There is C' > dependent only on (s,0) such that
(P [[Pa]
(P' Vi 1 8
2 r0
(1
2 c- --
(24)
as soon as min(1 p" pp--pp"00 0p 1}.
Proof. Follow the proof of Example 4.3 with c = c'p'.
Corollary C.2. Let (In) Is == [1x CRIHe + cx) for l E [K] be a collection of (w.l.o.g. disjoint) sub-interr intervals of
[1,0]. Let F = 6p- and let
K
G
Σ
we Unif(T&)
be mixture Uniforms the intervals Ix, Le. wk for all [K] and Ex wk = 1. Then, there is constant C" dependent only (r, 0) such that
(P. Y)
WFk= (1-
8
+ Σ
(nE((";11)) + C"
Σ w
Pd
PM]
2p
kE[K]
in which k- denotes the index (if it exists) such that p³ E Tg..
Proof. Note that G has density
K
[1,
H
1 (velm
2ck
with respect to the Lebesgue measure. We can thus express as function of Aş its analogues for each Unif(Is) as
A(p') Σ wkAx(p").
(25)
k=
We will now be able proceed on each Ag in the proof of the first part of Example 4.3
Let remark that the of k permits direct application of Example contribution to the final bound of
p* It. This readily implies
Wk- (1
2 Ex - Cce) 2p"
(26)
rO P*]
which is the first term of Eq.
Let us now fix + k* Without loss of generality, we will order the intervals, so that k < k- implies that x < p* for every e Ig and conversely for k k*, Notice that this implies that exactly one integral in each Ag. k # k², may be non-zero, which is to say
p² 11s (Nx + )
(ux - ++* 1+
p 1+s (us + Ex) 1- (14 Ex) 1-
p' >'A)"""
1ik < k* +
11 (k: > k*}
2ck
1 1
2c
1
20

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Auugmented One-Max-Search
for any k + k" Let us take each term in turn and apply Taylor's theorem following the methodology the proof of Example 4.3 By adding and subtracting 1k (resp. M4 "),, and using Taylor's theorem yields the existence of
(c ( )ayk such that
(mt + Ex) (Hkk - Ex)1ts 1s
2 2EAliL +
(ux (k) 1
6
(14k (k) 1x)1-
2EkF4K
c(2) (2)
8
6
Combining these over [K] yields
(pAA(pp))
2 Σ
WkK + +pp 1+
WkMe
Σ
w
+
Σ
(2)
(27)
12
Reck*
k
Nack"
kO*k
Now, add together Equations
25
and
26
recalling Eq.
27
and appeal to Corollary
4.2 to obtain
E E (P", Y)]
E[P*]
r
Wk
1
2p
EK
+
Σ k<
Wk
Pk D"
Σ
WR
p
Pk
+
C"
kE(K]
Σ
&
(28)
for suitably chosen constant C" 2 0. To complete the proof, notice that the two sums can be combined using & 14 if an only if k < k*.
p
Deterministic predictions, stochastic prices
Hereafter, we will use the following identity
T EPP'' I" (())
(x) 0 ) dp) (8²)) dF (p") +
Stochastic independent predictions and prices
Corollary 4.5. Let π¹ = Ft x G, the family {A]]r satisfies
E E P
Y)
2 r0 / T(y)dG()
E P*
r0 / 1p 'p'(pp') B[PA]
(F*)
(13)
Proof. Starting from Lemma 4.1 this follows from
(PA Y)l
[DW ((l00))a)))))F
E[P*]
P
Corollary C.3. Let nT" = F @ G, with F", G having density with respect to the Lebesgue measure, then the family {A.
satisfies
BAA
PM Y) E P
p. (F1-"dF (p') 1 x-do() ( pF f. (rac()))
P
1 v² ["" 1- aF ( (G(o)
(
(29)
Remark C.4. The result of Corollary C.3 can be slightly tweaked to hold even without densities using Lebesgue-Stiie Stieltjes integration by parts. We omit these details for the sake of conciseness.
21

---

Parcto-OptimaliyySSmnnne and Stochasticity in Learning-Augmeented One-Max-Scarch
Proof. Starting with Corollary 4.5 decompose the integral
J p" p'A(p")) dF (p))
S p pxlme J" y'dG())dF( (p))+ f.
o ptlts [[ ('d()))dF"())
Using integration by parts, in which the parts for A are x ++ J (pll=dFF(p") and x + J yddl(y) yields
A 1 p² dF (D*) ( ('''G(()
1 "n dF* (d"))G(y))
(30)
Similarly. B can be integrated by parts with parts - - 1e pplttdFF and x + l ddG(y), which yields
p (F)""))((")) S s'dG(y) - 1 1. 16 p (F
(31)
Combining Equations with (31 completes the proof.
Proposition C.5. Let F @ and F G Unif([c,, cal) the family {A,). satisfies
E(A Y)
1 2
((2 - 5)5(1 -s) 1 <(- +
P
r0 {(1)3
2 -
2+s (2+5((1= s)
+ ((2 + s)((1 + +)
2
-((3)
2 - 2 +
when s & [1,2}, with Ç: y E (0, +00) + (c} - c
Proof. Starting with the decomposition of Corollary C.3 we can compute the terms separately. For the first two, we have
L p (' [ y dGG()) C
6
m2
m
(32)
2 - 8
1 1
J ( ( y'd(()) C
G2
2+ 2+
m2
1+s
mi 1+s
(33)
1+5
in which
C
(02 c1)(m2 - m1)
Turning now to the second term of Eq.
22 we have
L 1 dF
1
1 1
- 2-8 2-s
+ C2
2-3 - Gi
2-s
1 (2202)
02 ci
2-s
and
2ts y
2ts 22t 2t8
pp pp"dF"(w"))
G
2 [xlle
+
[yycart
C2 Ci
2+ 8
so that, by integrating according to Eq.
29
yields
1, o va I" pf C
1
y
2-
11
+s
c2AmaVes
2- 2-8
c
y
1ts Vm2
(34)
2 -
3
1
2 -
02/m1
(, y 1 pe p pF = C
1
2+
y
y
02Am2Ves
c
2+a
y
C1Am2
(35)
2 +
2
3
2+8
Vmm
Am
Recombining Equations
32 35
yields the result, up to simplifying for m; = c; i (1,2).
22

---

Pareto-Optimality Smoothness, and Stochasticity in Learning-Augmenter One-Max-Scarch
1.5
10
0.5
2
Figure 5. Numerical quadrature of Proposition C.5 for 01 1, (for 0 E [1, 10) as a function of 8 E [1,5].
C.2. Complements to section 4.3
Since it holds regardless of the coupling x², the bound Eq. (4 has two direct benefits. First, it provides notion of robustness for uncertainty in the coupling which is relevant for risk-assessment in practical applications. Second, it isolates the influence of the marginal distributions on the prediction from the coupling of Y and pa. Consequently, we can return to (8) and isolate the contribution of the coupling, either through its transport sub-optimality
E| EIP
inf E\P''(Y, xEII(GFF))
or through multiplicative analogue
ELP* inf =e.(,,)) EY E(Y
The geometry of these objects is highly intricate and unfortunately doesn't appear to have been studied previously. This highlights an interesting direction of research in the competitive analysis of optimal transport.
Duality. The Kantorovich problem Eq. [4 admits a dual problem under general conditions (see c.g. Thm. 5.10 in (Villani 2009 In our case, the cost function is = (p".v) 3) E [1, 8 + p E(p", yy) E [o, 0). This duality strong, meaning that
inf = o f p² "("""")'=(("
v(G)dG(v) + ((D")dF"()) (A.))E
sup
(36)
which
E ((1, vb [1, [1, + (0, +00) bounded and measurable V(p', y) [1, x(0") + (v)) s c(p'.))))
Given bounded measurable function f. let fc denote its c-transform, i.e. the operator " such that maps
f
inf p" E'ppp, y)" :p(y).
(37)
vE[1,8]
The definition Eq. (37) shows that any bounded measurable function & [1, 0] + R forms an admissible (v,, po E with its c-transform (this is symmetrical in the sense that (z/ xb) is admissible if is bounded and measurable).
From the perspective of competitive analysis, the dual problem offers an appealing tool, as it suffices to propose potential sp, compute its c-transform, and integrate it to obtain a bound. Of course, guessing the optimal potential is as hard as solving the primal, but sub-optimal proposals can effectively leverage insights about the problem. Proposition 4.7 gives an example this methodology. Note that is possible to improve the potential yp again by proposing (v which we omit for brevity.
23

---

Pareto-Optimalli Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
Proposition 4.7. The family (Arrr satisfies
(
9 (p')
(P,, Y)
1
p
dF
(p")+
dF
r0
EP
Moreover, the RHS is the infimum over G of Eq.
(14)
Proof. We split the proof into two parts, starting with the bound, and then the equality.
1. We start with the potential
0,, whose c-transform (see Eq. (37) is
<(p") (1²))
inf p Ep'", ,9)*
xE[1,9)
1 p³
min
p 0 p'
(v220)) + tp +
Inserting into Eq. (36) yields the result.
2. By duality of the optimal transport problem,
inf GEL((LL)) xEI(F-.G)) .0) / "lp",))d((p",r .))
inf sup GEL((1.) (A.0)ss / ((p")dF ((o)do())
inf
(wwaaclo)) (38) GE
sup
inf
(A.i)E
The inner infimum in Eq. (38 is equal to == (v) : E 0] R. Consequently, the constraint E can be replaced without changing the value of the problem by
S: ((.,(1)))))))) (0,+00) x RR: Vy* [1,0² v(w")
inf c(p", .)) 1) wEl1,0]
so that
{ ((D")dFF + inf (p.))E
{ //0D"))FF(0'+ sup
sup
GE
(x.))S
ER w.es. / ((0"))F'''" + +
sup sup
(39)
in which S. : (vh: vh S infygenoo c(pp.clp.... v) -
As F* is positive, the inner maximisation over vb, in Eq. 33 saturates the constraints, whereafter, since f idFt and by combining with Eq. 38 one has the result.
D. Additive Prediction Error
Theorem 3.4. Let A be any deterministic algorithm with robustness and consistency 1/r0. Suppose that A satisfies for all p E [1, 0) and E [1,0] that
A(p.v) v) 2 max
(r;
1
nlp .y)"
-
(6)
r0
D"
for some 2 0, then necessarily 2 8", where
20 max
8" =
r0
1-
r0
Moreover, Algorithm A,, satisfies )6) with 3 33, which shows its optimality.
Hereafter, all optimisation problems over functions (ye, v/) which bounded and measurable. We omit this line by line reduce notational clutter.
24

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-AAugmented One-Max-Search
We separately prove the lower and upper bounds stated in the theorem. First, in Lemma D.2 on the performance of A.
we establish the lower bound
Ap. v)
(r, 1 - 3" (ri r0
7Pp' v))
2 max
p
p
Next, in Lemma D.3 we show that 3*t is the best possible constant.
D.I. Smoothness guarantee on A
We begin by proving a lemma that will be useful for establishing the smoothness of A..
Lemma D.I. The function @r 22 T-r
1-r-0
to satisfies for all that
1- (= - (2)) r0
p(2)
r0
Proof. This lemma can be proved with immediate computation. For all 2 R. holds that
r0 - r20
2 - (2(2))
1 r
1 - r r8
r - -22 = 1 + r20
r0 - 1
--r
r0
r
r0 - 1 (3
1-r r (10 1)
On the other hand, we have that
r0 1 - 2²0
px(2)
1 - + 1 -
r8
r0
r0- 1 - r0 + -00
1 - 12 2
1-r r
r
r0
1 20 2
r0 -1) 1)
r
1 1- 120
r0 1
2 -
1)
r0 1
1
r0
1 2
2 - (x
r0 1
which concludes the proof.
Lemma D.2. Algorithm A,, satisfies
(p.9) v) p
2 max (r, 1 MD''
r. T: - B
(40)
p
where 3 =
1_-20 1- r0
max
1- r0-1)
Proof. By Theorem 3.1 and by definition of A,, we have that A!, is r-robust, hence it satisfies for all p E (1,0) and A.
y [1,0] that p 2 r. It remains to prove the second lower bound that characterizes smoothness. We will prove separately for y E [1, r8] and e 100.0.
Case 1. For E [1, rd), the acceptance threshold is (v) = re. If p < r0 then
(p, 1
1
Up v) p
B
p
p
r
r0
25

---

Pareto-Optimality Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
Assume now that p" r0. It holds that
Ap(p.r) p²
r0
2
(41)
Since r0 2 1, we have that (r0)² 2 r0, thus the mapping 2 by 2-120²
is non-decreasing on (rO,, 0). and we deduce that
z-r0
r
(1-
1 1- r20
1 0 -
r20
1 p' - r2
B
(1 1-r r'rr r0
2
r8
r0
1-r
r
0
r0
r8
D" r0
and successive equivalences, recalling that px > r0, show that
1 8- - 228
B 2 r0 D" r0
= 3(p" -r0) 2 r0
(p- - -200
> 3 1 - r0
(1
,²02
2 r0
/"
r0
z r0
3
p
p"
Combining this with Eq.
41
and using that y S rl, we obtain
A, r)
2
3 (1
r8
2
3
1
y
=
1
3
p"
rf
rf
r0
p
Case 2. For y E (r0, 0J, the threshold is (1)
rb-1
--r² 2 I-r
I-
r0
Assume that p* < (v). Since y > r0, using the definition of 3 and Lemma D.1 yields
1 - 220
1 ( r0 (
1-
20
1 pr(y) - r0
3
max
2 r0 r0
r0
r0 y (v(
Using again that y r0, we have that the mapping 2 + z-r0 is non-decreasing [1, vl. and given that y < (+) (p) and both y and (y) are within the interval [1,y] (sp(2) S z for = 2 r0), we deduce that
w-
r0
B r y D*
and using that y < (v) S y. this is equivalent to writing
8
Dz
1
>
p
r0
p*
Hence we have the lower-bound
A y) p"
3 91
p
3 vy.
2
2
p
r0
p'
r0
Assume now that p" E [b). satisfies (+( 2 to for all z E (r0, OJ. which is in particular true for with the current assumptions. Therefore, we obtain immediately that
v). Since A,, is r-robust and 1/ré //rO-consistent, Theorem 3.1 shows that the threshold T
(p. v) p
1
1
n(p" v)
p
r
r0
p
26

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-AAggmented One-Max-Scarch
Finally, assume that p* E 1y, Using the expression of (v),), we have
(p, v)
$
1 - rB
1 - r20 y
+
p
p
1
pº (1 r)r0 p
2 1 - r0
1
1 - r y
0 +
1 -
(1 r)r8 D"
1 1-rrt r0
1 1-
1 - 2²
1
1
0 (1- r)r8
(1 r r)r
p
1 p
r
-
1
1 700
r0
1
r)r
pd
1
1 r20
1 y
r
(1 - r)rg
p
1
8 7P VP)
r0
p
where used in the last inequality that 3 = 1-r max This concludes the proof.
1-r! 1 2
1-720 (1-r)r0
and that mypp,,)) p" y since p" y.
D.2. Lower bound on smoothness
Lemma D.3. Let A be any algorithm with robustness r and consistency 1/r0. Suppose that A satisfies for all p E [1,0] and y E [1,0] that
A(p.y) v)
1
max
[i r0
-3
(42)
p¹
p¹
for some E R, then necessarily 3 >
2 r8
max
-
Proof. Consider an algorithm A and 3 E R satisfying the assumptions of the theorem. To establish the lower bound, we consider the instances (I) (e)))) as defined in Eq. (15). On these instances, any deterministic algorithm is equivalent threshold-based algorithm. In particular, A is identical As for some + [1, 0] - [1, 0].
The assumption on A ensures that it achieves Pareto-optimal consistency (r(r)) and robustness r. Consequently, As also attaints them on the sequences of prices [In (4)]gE(1.0)- These instances are precisely those used to establish the constraints on Pareto-optimal thresholds in Theorem 3.1 which implies that the theorem's 's constraints hold for O. In particular, we have that & (r0) = r0 and (0) 1/r.
Let us now prove the lower bound on B. Let y = and 4(0) lower bound on A, it holds that
4(0) for some >> 0. Using Eq. 16 and the assumed
T+E
A(In (g-), (In((
1
1
ge
B
p
as
r0
gs
Taking the limit when e and recalling that (())= 1/r, we obtain that
0 1/r
1
8
1/r r0 -
-3. (r0 1).
r0
and it follows that On the other hand, for y r and q = 0, using Eq. (6), the assumed lower bound on A, and that 4(r0) r0, we have
1/r0-
1- 28
3 2
(43)
r0 -
r0(r0- 1]
Ao (I,,())))
Ao (O).())))
T(r0) + O
8 0 r0
0 =r + + >
3(1 r)
0
0
r
r0
27

---

recover (parts of) the standard Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmentted One-Max-Scarch
Taking the limit for oo, we obtain that
1/r0 - 1 720 1 --
8
(44)
r0(1 r)
Finally, combining Equations (43) and (44) we deduce that
r0((r0 - 1)' r0(1 - -0(1-)))
12
1 1-r20
1-
r20
2 max
max
r0
r0 1 11-1
D.3. Comparison with prior smooth algorithms
In (Benomar & Perchet 2025). the authors introduce a randomized family {Ä" pe of algorithms. For a fixed p. the maximum robustness that their algorithm can achieve is at most 1-e" 0-1/2, hence remains bounded away from 0-1/2, Given
any robustness level r E [0-1 --e" 0/1))) the corresponding consistency achieved by their algorithm is c = (1-e" 0
This algorithm ensures smoothness in expectation with respect to the error n(p", 3). i.e. that
A (p. v)1
eP p
1
" v)
B
r
p'
with 3p constant proportional to 1/p. The major drawbacks of this approach that
1. the achieved robustness and consistency are not Pareto-optimal, i.e. they deviate from the front defined in Eq. ①..
2. the guarantees of the algorithm only hold in expectation, since the algorithm is randomized.
D.4. Probabilistic analysis
Corollary D.4. The family (A, satisfies
EJA, (P" Y)] E[P*]
E[P" (1P''(P') (P', Y) E[P
2 max
(", r0
r
(45)
Corollary D.5. The family {A satisfies the worst-case performance ratio bound
(PA Y)]
1
pp'n(p" v)dr(pp, E[P*]
sup RETT(F".G) .G)
(46)
P
One can observe that the bounds of Corollary D.3 represent the supremum version of the transport problem associated with Wi (see below). The supremum expected due to the additive nature of the analysis, which makes the error term negative (additive) correction rather than multiplicative factor. While not classical optimal transport problem, this supremum can be transformed into optimal transport problem with cost (y. p²) - -ly p" and theory from there, see e.g. (Villani 2009).
Note that the Wasserstein-p distance, for [1, +0o), denoted wp, on the space ((,, of probability distribution
over [1, 0 is
=ETT(F .a) /w'-w/ vl dm(p","))
Wo : (F*,)) G)
inf
E. Additional Numerical Experiments
We give here an additional experiment made with the same synthetic data described Section While the first experiment shows the performance of the algorithm function of the multiplicative error. Instead of fixing Emin, we set a maximum
28

---

Pareto-Optimalit, Smoothness, and Stochasticity in Learning-Augmentee One-Max-Scarch
0
1/r0-
=0.5
Empirical ratio
=1
0.6
0.5
0.4
20
30
Mmax
Figure 6. Performance of with p (0,0.5, 13.
error level maax and sample y uniformly at random from the interval 'p" Mmas p + Muax] Figure 6 presents the results in this setting.
Similarly to the behaviour with respect to the multiplicative error, Figure shows that p = yields a significant performance degradation for an arbitrarily small error, which confirms the brittleness [unn al. (2021) algorithm. In contrast, / = 1 achieves the best smoothness, having performance that gracefully degrades with the prediction error.
E.1. Experiments on real datasets
We use the same experimental setting and Bitcoin data as Section 5 but we different values of À E f0.2, instead of fixing À 0.5 in Figure 4 This yields different robustness levels, again expressed 0-(1-1/2), The results
shown in Figures 7 and 8 for À 0.2 and 0.8, respectively.
1/r0-
p
0
p
Empirical ratio
Empirical ratio
1/r0
0.7-
0.4
0.3
0.35
0.0
0.2
0.4
0.66
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
E (0,
a
[0, I]
Figure 7. Comparison of A, and A, on the Bitcoin price dataset
Figure 8. Comparison of A,, and A the Bitcoin price dataset with À 0.8.
with À = 0.2.
For x = 0.2, Figure shows that the performances of A, and A are similar when À is small, i.e., when r is close to 1 1/0. This corresponds to a consistency of 1, meaning that the algorithm fully trusts the prediction. Since both algorithms rely heavily on the prediction this setting, their behaviour naturally similar.
For larger X, as seen in Figures and g performance gap between the two algorithms increases. However, for À close to both consistency and robustness approach 1/r0. While the performance of A degrades significantly more slowly than that of A., for À 0.8 (Figure 8) the values of and 1 1/r0 remain close. Figure 4 presented in Section is intermediate
*If [1,0] had been unhounded, W would only have heen defined for distributions with a a -omment.
29

---

Parclo-OptimaliyySSnnnii and Stochasticity in Learning-AAugmntted One-Max-Search
setting between these extremes, where A,, yields better smoothness than A,, without having the values and 1/r close each other.
30


Reviews:
[{"review_id": "iJjC2bmkZV", "reviewer": "Reviewer_S3x7", "summary": "This paper studies one-max-search problem in the learning-augmented setting and develops an algorithm that is both Pareto-optimal and smooth to the multiplicative prediction error.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission, and for their positive feedback.\n\nIn proposing a stochastic formulation of the one-max-search problem with predictions, we aimed to introduce the concept of a stochastic notion of accuracy for predictions. We gave bounds in expectation, but, as the reviewer suggests, one can also consider high-probability bounds. However, these bounds would concern the joint tail probabilities of $P^*$ and $Y$, which are difficult objects to conceptualise. In contrast, bounds in expectation naturally give rise to a characterisation of the worst case as an optimal transport problem.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and/or evaluation criteria (e.g., benchmark datasets) make sense for the problem or application at hand. The experiments clearly demonstrate the improvements of the proposal algorithm compared to existing methods.", "theoretical_claims": "I checked the correctness of the arguments appeared in the main paper.", "experimental_designs_or_analyses": "I checked the soundness/validity of experimental designs or analyses.", "relation_to_broader_scientific_literature": "The key contributions of the paper is related to general ML.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper characterizes all Pareto-optimal thresholds in a general class which captures many previous works. This result seems to be fundamental to the one-max-search problem.", "other_comments_or_suggestions": "NA", "questions_for_authors": "In the stochastic setting, can we have high-probability guarantees on ALG?", "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": "u4mSZHdQtQ", "reviewer": "Reviewer_hcYC", "summary": "The authors study the one-max-search problem where the decision maker is presented with a stream of value within a range $[1, \\theta]$. The decision maker has to irrevocably select and end the process, or forfeit a value in the stream. The authors study the consistency, and robustness tradeoff of a Pareto optimal algorithm that relies on a prediction of the optimal value.  Consistency refers to the approximation ratio of an algorithm when it is supplied with the correct prediction. Robustness refers to the approximation ratio of an algorithm supplied with incorrect prediction. The authors study the tradeoff as a function of the smoothness of the threshold function, where smoothness is defined using a symmetric and scale invariant multiplicative prediction error. They establish consistency of a specific class of threshold function that satisfies a given robustness $r$ and smoothness $\\rho$. Furthermore, they show that their guarantees are nearly tight for any Pareto Optimal algorithm.  The authors also study the competitive analysis under multiple stochastic frameworks where price and/or prediction exhibit stochasticity.  Interestingly, when both exhibit stochasticity they show the authors establish performance guarantees using optimal transport.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission, and for their positive feedback. We address their comments below.\n\n- The objective of the robustness term is to give a valid guarantee even under arbitrarily inaccurate predictions, since no assumption is made on the quality of the prediction. This is why the robustness term should not depend on the prediction error.\n-  It might be possible to improve the bound if the error is known to be at most $\\mathcal{E}_{\\max}$. However, our main objective is to design an algorithm that is able to leverage a prediction without any additional assumptions on its quality.  More generally, in any learning-augmented problem, if the error is assumed to be bounded, then the consistency, robustness, and smoothness guarantees might all be improved. While this question is out of the scope of our work, it constitutes a very interesting research direction.\n- Along a single trajectory of prices, it is impossible to learn the coupling as the whole trajectory provides only a single sample of the maximum price and a single prediction, which is statistically meaningless. However, it is possible to learn the coupling if the game is repeated several times using standard density estimation techniques, see e.g. (Silverman, 2018; Chen, 2017). Studying a repeated version of the one-max-search problem (whether on-- or offline) is a significantly methodologically different task. This raises an interesting further direction of research.\n\n**References.**   \nSilverman, Bernard W. Density estimation for statistics and data analysis. Routledge, 2018.     \nChen, Yen-Chi. A tutorial on kernel density estimation and recent advances. Biostatistics \\& Epidemiology 1.1 (2017): 161-187.", "claims_and_evidence": "The theoretical results stated in the paper is supported by proofs.", "methods_and_evaluation_criteria": "The methods are standard for a theoretical paper.", "theoretical_claims": "I have checked the theoretical claims. I am reasonably certain about the correctness, but may have missed details (e.g. algebraic derivations of inequalities).", "experimental_designs_or_analyses": "Numerical evaluations are presented. The results look good to me.", "relation_to_broader_scientific_literature": "This paper establishes almost tight relationship between the consistency, robustness, and smoothness of an algorithm. This is a good addition to the understanding of the one-max-search problem.", "essential_references_not_discussed": "The important references seem present in my understanding.", "other_strengths_and_weaknesses": "Strengths:\n- This paper establishes a near optimal smoothness guarantees for Pareto optimal algorithms, and provides a simple threshold based algorithm that attains the nearly tight bounds.\n- This paper studies the performance of the proposed algorithm, and establishes performance guarantees through optimal transport.\n\nWeakness: Please check comments and suggestions.", "other_comments_or_suggestions": "Possible Improvements/Discussions:\n- The current paper claims to establish a three-way Pareto optimality. However, in my understanding, for proper three-way relation the robustness should depend on the multiplicative error $\\mathcal{E}$. \n- On a related note to the above, the lower bound established relies on A being Pareto optimal for all $y$. What happens if we restrict the prediction to have bounded error  $\\mathcal{E}_{\\max}$.\n- What is the relation of the optimal transport specified from a learning perspective? Can we discover the coupling in a offline and online learning manner?", "questions_for_authors": "Please check comments and suggestions.", "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": "dskJ0YnJsh", "reviewer": "Reviewer_qsuL", "summary": "This paper studies one-max search with prediction: Given a sequence of prices $p_1, \\ldots, p_n$ in an online fashion and a prediction $y$ of the maximum price $p^*$, pick a price irrevocably to compete with $p^*$.  Previous algorithms with prediction can simultaneously achieve _consistency_ (when the prediction is correct, the performance is optimal) and _robustness_ (when the prediction is arbitrary, still achieves the worst-case-optimal competitive ratio).  There are also previous algorithms (Sun et al, 2021) achieving the optimal consistency-robustness tradeoff (_pareto-optimal_ in the two extreme cases).  However, those algorithms are not _smooth_: when the prediction accuracy degrades smoothly, the performance of the algorithm should change smoothly.  The authors provide the first Pareto-optimal and smooth algorithms for the problem of one-max search with predictions.  Moreover, this algorithm does not need randomization.\n\nThe technique is to fully characterize the class of _threshold algorithms_ that are Pareto-optimal, and then within this class find the best smooth algorithm.  The authors also show that the smoothness guarantee of the found algorithm is tight. \n\nThe authors then apply the main results to a setting where the prediction and the maximum price are sampled from some joint distribution, and study the impact of the distribution on the algorithmic performance.  They also provide experiments to show the advantage of their algorithm over a previous one.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission and for their positive feedback. We address their questions below.\n\n**Minor weakness.**     \nThe $k$-search problem generalizes the one-max search problem, requiring a trader to sell $k$ items instead of one, with arbitrary prices in a bounded range $[p_{\\min}, p_{\\max}]$. Lee et al. studied this problem in a learning-augmented setting with a prediction of the maximum price, proposing a threshold-based policy that achieves a Pareto-optimal tradeoff between consistency and robustness, but lacks smoothness guarantees. Given the Pareto-optimal consistency and robustness values, we can aim to characterize all algorithms achieving them. Building on the intuition we established for one-max search, the smoothness of such algorithms depends on the maximum slope of their thresholds. We can then analyse the algorithm within this family with the smallest maximum slope, which we expect to have good smoothness guarantees.\n\n**Other Comments Or Suggestions**.     \n(1) We thank the reviewer for pointing out the typo. We have corrected it.    \n(2) We agree with the reviewer's observation and apologise for the confusing formulation. We meant to highlight the way that Optimal transport was used to characterise the effect of the interaction between $G$ and $F^*$ beyond their own effect. We will clarify this point. \n\n**Questions**.  \n(Q1) The bound holds for deterministic algorithms. In the presence of randomization, the problem is equivalent to the one-way trading problem, in which fractions of an item can be bought. The interplay between smoothness and Pareto-optimality for one-way trading has been fully studied in \"Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms\" (Elenter et al., NeurIPS '24), where the authors proved that any algorithm achieving Pareto-optimal consistency and robustness is necessarily brittle (i.e., it cannot have any smoothness guarantees). This gives further evidence that, unlike many decision problems, the deterministic and randomized versions of one-max search are significantly different.", "claims_and_evidence": "The claims are supported by clear and convincing evidence, both theoretically and experimentally.", "methods_and_evaluation_criteria": "The theoretical approach to this problem -- fully characterizing the class of Pareto-optimal algorithms and then selecting the best smooth algorithm among them -- is non-trivial and interesting.", "theoretical_claims": "I checked the proof of Theorem 3.1 and briefly went over other proofs and didn't find any issues.", "experimental_designs_or_analyses": "I didn't find any issues in the experiments. \n\n**(Strength 1)** On the positive side, the experiment with real-world Bitcoin data, showing that the proposed algorithm ($\\rho = 1$) performs better than previous algorithm ($\\rho = 0$), is interesting and strengthens this paper a lot in my opinion.", "relation_to_broader_scientific_literature": "**(Strength 2)** Previous algorithms for one-max search with predictions (Sun et al, 2021) achieve the optimal consistency-robustness tradeoff (_pareto-optimal_ in the two extreme cases).  However, those algorithms are not _smooth_.  Even though one-max search is such a fundamental question, it is still open whether a doubly optimal algorithm (Pareto-optimal and smooth) exists.  This work successfully answers this question by providing a doubly optimal algorithm.  Moreover, this algorithm is deterministic, which is even better. So, I think this is a significant contribution to the literature.   \n\n**(Strength 3)** The technical part of this work fully characterizes the class of Pareto-optimal algorithms for the one-max search problem with predictions.  This technical contribution might be of independent interest.", "essential_references_not_discussed": "I don't know of essential missing references.", "other_strengths_and_weaknesses": "I have mentioned three strengths above.  \n\nA **minor weakness**, in my opinion, is that this work is restricted to the one-max search problem.  The authors \"believe their methodology can be applied to generalization such as the $k$-search problem\" (Conclusion), but didn't give any theoretical evidence.  \n\nBut since the one-max search problem is fundamental and this work gives an almost complete characterization for the Pareto-optimal and smooth algorithms for this problem, I am overall positive towards this work.", "other_comments_or_suggestions": "(1) Page 6, second column of line 320: \"this functional of $G$\" -> \"this functional of $F^*$\" ? \n\n(2) The last sentence before Section 4.1 \"Finally, we show how to isolate the interaction of $G$ and $F^*$ using analytical tools from optimal transport theory\" is confusing.  In Section 4.2, you isolate the effect of $G$ in Corollary 4.2 and isolate the effect of $F^*$ in Corollary 4.4, not using optimal transport theory.  Then in Section 4.3, you consider the joint effect of $G$ and $F$ -- you use the optimal transport theory here to find the worst coupling between $G$ and $F$ such that the competitive ratio attains the infimum.  I don't think you are using the optimal transport theory to \"isolate the interaction of $G$ and $F$\".", "questions_for_authors": "(Q1) Does tight lower bound result (Theorem 3.3) hold for all randomized algorithms or just for deterministic algorithms?", "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": "AQojOdFaBI", "reviewer": "Reviewer_oFaD", "summary": "This paper studies the learning-augmented one-max-search problem. In the classic one-max-search problem, the input of an algorithm is a sequence of prices $(p_i)_{i=1}^{n}\\in [1,\\theta]^n$. At each $i$, the algorithm must decide whether to accept a price $p_i$ and terminate, or to reject $p_i$ and proceed. In the learning augmented one-max-search problem, the algorithm has access to a prediction $y$ of the maximum price in $p$.\n\nThe objective of the algorithm is to achieve the best trade-off between consistency (the competitive ratio of the algo. if the given prediction $y$ is accurate), robustness (the competitive ratio of the algo. if the given prediction $y$ is arbitrarily inaccurate), and smoothness (the competitive ratio of the algo. as a function of the prediction error). This paper designs a pareto-optimal algorithm (w.r.t. the consistency and robustness tradeoff) that is also smooth, and prove that the smoothness of the algorithm matches the lower bound of any Pareto-optimal algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission and for the positive feedback. We address their questions and comments below.\n\n### **Weakness**\nDue to page limitations, we could not always give detailed proof methodologies in the main paper. However, if the paper is accepted, we will use the additional page to enhance this aspect, as suggested by the reviewer. For instance, please see our response below for some specific paragraphs that we will add in regard to Section 3.    \n\n**Technical Novelty.** Our techniques fundamentally differ from those used by Sun et al. While their work aims to determine the Pareto-optimal tradeoffs between consistency and robustness, our work extends their results by leveraging the knowledge of the Pareto-optimal frontier for consistency-robustness, and establishes smoothness guarantees, which is not addressed in the previous work. Specifically, we characterize all threshold algorithms that achieve this frontier and further analyze the optimal smoothness within this class of algorithms using two distinct notions of smoothness: multiplicative and additive.\n\n**High level overview of proof techniques.**\n- **Theorem 3.1**: If a threshold function $\\Phi$ belongs to $\\mathcal{P}_r$, then we use the bounds on $\\Phi$ defining $\\mathcal{P}_r$ to prove its Pareto-optimal robustness and consistency. Conversely, for a Pareto-optimal $\\Phi$, we analyze the worst-case instances $I_n(q)$ (Equation 15), where prices increase uniformly from 1 to $q$ before dropping to 1. By evaluating $\\text{ALG}/\\text{OPT}$ on these instances for well-chosen $q$, we derive the bounds on $\\Phi(y)$ that define $\\mathcal{P}_r$.\n- **Theorem 3.2**: For any $\\rho \\in [0,1]$, the threshold of Algorithm $A^\\rho_r$ lies in $\\mathcal{P}_r$, ensuring $r$-robustness and $1/r\\theta$-consistency (Theorem 3.1). To establish smoothness, we determine the best value of $s$ such that $\\text{ALG}/\\text{OPT} \\geq (1/r\\theta) \\mathcal{E}^s$ across all price sequences and predictions. Since the threshold is piecewise-defined, it suffices to analyse cases based on $y$ and whether the maximum price is above or below the threshold. The final smoothness guarantee is then determined by the worst such case.\n- **Theorem 3.3**: We first prove that, on worst-case instances $I_n(q)$, any Pareto-optimal algorithm behaves like a threshold algorithm. Using results from Theorem 3.1, we establish that its threshold function must belong to $\\mathcal{P}_r$. Finally, by applying the defining inequalities of $\\mathcal{P}_r$ with well-chosen $q$ and $y$, we derive lower bounds on the smoothness $s$.\n\n### **Questions**\n- **Confidence fluctuation.** The confidence fluctuation in Figure 2 is indeed a result of the randomness of the environment. \n- **Relative performance.** Could the reviewer clarify what they mean by the \"win-rate\" of $\\rho=1$ against $\\rho=0$? We interpret this as the ratio $CR(A^1)/CR(A^0)$, indicating how much $A^1$ gains compared to $A^0$. Both the empirical (solid line) and theoretical (dashed line) worst-case ratios are shown in the following figure (https://imgur.com/a/PmnrYOn). The figure shows that the empirical ratio is 1 when the prediction is perfect (i.e. $1-\\mathcal{E} = 0$), as expected, since both algorithms have the same consistency. The ratio then increases abruptly to approximately $1.3$, for an arbitrarily small error, which is due to $A^0$'s brittleness. It then increases, up to a value of 1.5 approximately, after which it decreases down to 1, as the prediction becomes highly inaccurate.\n    This is explained, respectively, by the fact that $A^0$ remains inefficient for relatively small values of error, and by the fact that both algorithms have the same robustness.\n- **Theoretical bounds in the figure.** Thank you for the suggestion. We included the theoretical worst-case ratio (dashed lines) for $\\rho \\in$ {0, 0.5, 1} alongside the empirical ratios from Figure 2. The updated figure is available here (https://imgur.com/a/87xE5Qv). For the three values of $\\rho$, the figure shows that the empirical ratio is better than the theoretical one because the latter represents the worst case over all predictions with error at most $\\mathcal{E}$, while the empirical ratio is based on random predictions, explaining the observed gap. Note that, for $\\rho < 1$, there is a sharp degradation in performance; for example, for $\\rho=0$, this degradation occurs at infinitesimally small prediction error. In contrast, for $\\rho=1$, the degradation is smooth, which aligns with our objectives and the intuition given in Section 3.", "claims_and_evidence": "The claims are supported by the theoretical analysis.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I only checked the first 8 pages of this paper.", "experimental_designs_or_analyses": "I checked the experiments in Section 5.", "relation_to_broader_scientific_literature": "The closest related works is Sun et al. (2021), which characterized the Pareto front of consistency and robustness. The idea of designing algorithms that have smooth performance w.r.t. the prediction error is an important question in learning-augmented algorithms.", "essential_references_not_discussed": "This paper discussed essential related works.", "other_strengths_and_weaknesses": "Strengths:\n\n-\tThe theoretical results in this paper are neat and solid. \n-\tThe paper is well-written and self-contained. \n\nWeakness:\n\n-\tThe organization of this paper could be improved to include some high-level overview of proof techniques. While the difference between the algorithms proposed in this paper and prior algorithms is clear in Figure 1, the technical novelty in the analysis is not addressed.", "other_comments_or_suggestions": "I have no other comments.", "questions_for_authors": "-\tWhile Figure 2 clearly shows that the average performance when $\\rho=1$ is better than $\\rho=0$ (the algorithm discussed in prior work), the confidence fluctuation (shaded area) of the ratio also significantly overlaps. Is it because of the randomness of the environment? In addition, what is the relative performance of $\\rho=1$ compared with $\\rho=0$? E.g., for the same randomly generated environment, what is the win-rate of $\\rho=1$ against $\\rho=0$?\n-\tCan you also draw the theoretical bound given by Theorem 3.2 (or Theorem 4.6) in Figure 2? How well is the empirical performance of the algorithm characterized by the theoretical analysis?", "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:

Meta-review: The paper studies the one-max search problem in the presense of machine-learned predictions or advice. Without advice, the stopping problem of picking the (approximately) maximum value in a sequence of revealed values, when the values are known to be in the interval $[1,\theta]$ is known to admit a deterministic algorithm with a tight $1/\sqrt{\theta}$ approximation. In the presence of advice, prior work established the Pareto frontier between two important quantities of interest in such problems, namely, consistency and robustness, and the value of $\theta$ for this problem. What this paper is interested in is, to not only have the best tradeoff between consistency and robustness, but also have a "smooth" algorithm, namely, one whose performance decays smoothly as the prediction error grows. Prior to this work, the existence of an algorithm that is simultaneously Pareto-optimal and smooth was open, and this work answers that question positively.

The committee appreciated (a) the tight results in this work, (b) the applications to the stochastic setting where the predictions and prices both stem from a random environment and this paper shows how the performance depends on the distributions of predictions and prices, and their coupling and (c) the technical content of this work, bringing in techniques from optimal transport.

Overall, this is a solid contribution to ICML.
Decision: Accept (poster)