# paretooptimality_smoothness_and_stochasticity_in_learningaugmented_onemaxsearch__b0feb513.pdf Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Ziyad Benomar * 1 2 Lorenzo Croissant * 1 2 Vianney Perchet 1 2 3 Spyros Angelopoulos 4 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 maximize its profit. The problem has been studied both in probabilistic and in worstcase 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. 1. Introduction Recent and rapid advances in machine learning have provided the ability to learn complex patterns in data and time series. These advancements have given rise to a new computational 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 algorithm. The field of learning-augmented algorithms was born out of this emerging requirement to leverage ML techniques towards the development of more efficient algorithms. Learning-augmented algorithms have witnessed remarkable *Equal contribution 1CREST, ENSAE, Palaiseau, France 2INRIA Fairplay joint team, Palaiseau, France 3Criteo AI Lab, Paris, France 4CNRS and International Laboratory on Learning Systems, Montreal, Canada. Correspondence to: Ziyad Benomar . Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s). growth in recent years, starting with the seminal works (Lykouris & Vassilvtiskii, 2018) and (Purohit et al., 2018), particularly 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 inherently imperfect information on the input items, which the algorithm must be able to leverage in a judicious manner. One of the most challenging aspects of learning-augmented (online) algorithms is their theoretical evaluation. Unlike the prediction-free setting, in which worst-case measures such as the competitive ratio (Borodin & El-Yaniv, 2005) evaluate algorithms on a single metric, the analysis of learningaugmented settings is multifaceted and must incorporate the effect of the prediction error to be meaningful. Typical desiderata (Lykouris & Vassilvtiskii, 2018) include: an efficient performance if the prediction is accurate (consistency); a 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 significant departure from the worst-case, and overly pessimistic competitive analysis, and allows for a much more nuanced and beyond worst-case performance evaluation. Achieving all these objectives simultaneously is a challenging task, and is even impossible for certain problems (Elenter et al., 2024). To illustrate such challenges with an example, consider the one-max-search problem, which models a simple, yet fundamental setting in financial trading. Here, the input is a sequence of prices (pi)n i=1 [1, θ], where θ is a known upper bound, and the online algorithm (i.e., the trader) must decide, irrevocably, which price to accept. Under standard competitive analysis, which compares the algorithm s accepted price to the maximum price p := maxi pi on a worst-case instance, the problem admits a simple, yet optimal, algorithm (El-Yaniv, 1998). In contrast, the learning-augmented setting, in which the algorithm has access to a prediction of p , is far more complex. Specifically, Sun et al. (2021) gave a Pareto-optimal algorithm, i.e. one that achieves the best possible trade-off between consistency and robustness. However, this algorithm lacks smoothness, which results in brittleness. Namely, Benomar Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search & Perchet (2025) showed that even if the prediction error is arbitrarily small, the algorithm s performance may degrade dramatically, and collapses to the robustness guarantee. This renders the algorithm unsuitable for any practical applications since perfect oracles do not exist in the real world. Benomar & Perchet (2025) addressed the issue of brittleness by using randomization: this results in an algorithm with smoother behaviour, albeit at the cost of deviating from the consistency-robustness Pareto front. In a similar vein, Angelopoulos et al. (2022) gave a smooth algorithm without any guarantees on the trade-off between consistency and robustness. Sun et al. (2024) studied the problem under a model of uncertainty-quantified predictions, in which the algorithm has access to additional, and more powerful, probabilistic information about the prediction error. The following natural question arises: is there an all-around optimal algorithm, that is simultaneously Pareto-optimal and smooth, and does not rely on randomisation or probabilistic assumptions about the quality of the prediction? 1.1. Main contributions Our main result answers the above question in the affirmative by giving a deterministic Pareto-optimal algorithm with smooth guarantees. Furthermore, we demonstrate how to leverage smoothness so as to extend this analysis to stochastic settings in which the input and prediction are random. In previous works on learning-augmented one-maxsearch (Sun et al., 2021; Benomar & Perchet, 2025), the proposed algorithms select the first price that exceeds a threshold Φ(y), which is a function of the prediction y of the maximum price p in the sequence. We revisit the problem by first characterizing the class Pr of all consistencyrobustness Pareto-optimal thresholds Φ. Next, we focus on a specific family of Pareto-optimal thresholds within Pr which generalise the algorithm of Sun et al. (2021) but also exhibit smoothness guarantees. In particular, our analysis quantifies smoothness in this family, showing it to be inversely proportional to the maximal slope of the corresponding threshold. Guided by this insight, we find the threshold that maximizes smoothness within the class Pr. 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 is commonly used, we show that our algorithm optimises smoothness for all robustness 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- dling the real-world uncertainty of predictions. When predictions and prices are both tied to a random environment (e.g. a 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-quality metrics which help us better capture the notion of the usefulness of a prediction in stochastic environments and give detailed bounds on concrete settings. We also provide a 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. We validate our theoretical results through numerical experiments, in which we compare our algorithm to the state of the art, by testing it under both synthetic and real data. 1.2. Related work Learning-augmented algorithms. Algorithms with predictions have been studied in a large variety of online problems, such as rent-and-buy problems (Gollapudi & Panigrahi, 2019), scheduling (Lattanzi et al., 2020), caching (Lykouris & Vassilvtiskii, 2018), matching (Antoniadis et al., 2020), packing (Im et al., 2021), covering (Bamas et al., 2020) and secretaries D utting 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 as sorting (Bai & Coester, 2023) and graph problems (Azar et al., 2022), as well as 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-robustness trade-offs in learning-augmented algorithms, e.g. (Sun et al., 2021; Wei & Zhang, 2020; Lee et al., 2024; Angelopoulos, 2023; Bamas et 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 Paretooptimal algorithms for problems such as one-way trading was observed by Elenter et al. (2024), who proposed a userdefined approach to smoothness, and by Benomar & Perchet (2025) who relied on randomization. These approaches differ from ours, in that the profile-based framework of Elenter et al. (2024) does not always lead to an objective and measurable notion of consistency. Moreover, we show that randomization is not necessary to achieve Pareto optimality. One-Max Search. El-Yaniv (1998) showed that the optimal competitive ratio of (deterministic) one-max-search is 1/ θ, under the assumption that each price in the se- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search quence is in [1, θ], where θ is a known upper bound on p . This assumption is required in order to achieve a bounded competitive ratio and has remained in all subsequent works on learning-augmented algorithms for this problem, such as (Sun et al., 2021; Angelopoulos et al., 2022; Sun et al., 2024; Benomar & Perchet, 2025). The randomized version of one-max-search is equivalent to the one-way trading problem, in which the trader can sell fractional amounts. The optimal competitive ratio, for this problem, is O(1/ log θ) (El Yaniv, 1998). Pareto-optimal algorithms for one-way trading were given by Sun et al. (2021), however Elenter et al. (2024) 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 survey (Mohr et al., 2014). One must note that worst-case measures such as the competitive ratio aim to model settings 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). 2. Preliminaries In the standard setting of the one-max-search problem, the input consists of a (unknown in advance) sequence of prices p := (pi)n i=1 [1, θ]n, where the maximal range θ is known. At each step i [n], the algorithm must decide irrevocably whether to accept pi, terminating with a payoff of pi, or to forfeit pi and proceed to step i + 1. If no price has been accepted by step n, then the payoff defaults to 1. The competitive ratio of an algorithm is defined as the worstcase ratio (over all sequences p) between the algorithm s payoff and p , the maximum price in the sequence. A natural approach to this problem is to use threshold-based algorithms, which select the first price that exceeds a predetermined threshold Φ [1, θ]. We denote such an algorithm by AΦ. In particular, the optimal deterministic competitive ratio is 1/ θ and it is achieved by A θ (El-Yaniv, 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). In the learning-augmented setting, the decision-maker receives a prediction y of the maximum price in the input p. The payoff of an algorithm ALG in this setting is denoted by ALG(p, y). In this context, threshold rules are defined as mappings Φ : [1, θ] [1, θ] that depend on the prediction. We use again AΦ to denote the corresponding algorithm. We denote by c(ALG) and by r(ALG) the consistency and the robustness of the algorithm, respectively, defined as c(ALG) = inf p ALG(p, p ) p , r(ALG) = inf p,y ALG(p, y) Sun et al. (2021) established the Pareto front of the consistency-robustness trade-off, albeit using a different convention (the inverse ratio p /ALG) for the competitive ratio1. Under our convention, their results show that the Pareto front of consistency and robustness is the curve: n crθ = 1 for (c, r) [θ 1/2, 1] [θ 1, θ 1/2] o . (1) In contrast, we are interested not only in consistencyrobustness Pareto-optimality but also in smoothness, namely in the performance as a function of the prediction error η(p , y) := |p y|. An algorithm is called smooth if the ratio ALG(p, y)/p is lower bounded by a (non-constant) continuous and monotone function of the error η(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 onemax-search. Our approach is outlined as follows. We begin by characterising the class of all thresholds Pr which induce Pareto-optimal algorithms (Theorem 3.1). We then present a family of thresholds in Pr, parametrised by a value ρ [0, 1] ( Eq. (2)) that characterises their smoothness 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 on its smoothness. Before we discuss our algorithms, we note that the randomized algorithm of (Benomar & Perchet, 2025) has a measurable and significant deviation from the Pareto front, even in comparison to deterministic algorithms; see Appendix 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 on randomisation. We now proceed with the technical statements. Theorem 3.1 below provides a 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, θ] such that AΦ has robustness r and consistency 1/rθ is Pr := n Φ : z [1, θ] : rθ Φ(z) 1 z [rθ, θ] : z rθ Φ(z) z o . Figure 1 illustrates the set Pr (shaded). We prove the theorem via a double inclusion. First, if a threshold function Φ belongs to Pr, then we use the bounds 1The convention that the competitive ratio of the maximization problem is in (0, 1] allows for cleaner bounds on the performance as a function of the prediction error. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Prediction y [1,θ] Threshold Φ(y) Φ(y) = y rθ Figure 1. A depiction of the set Pr of Theorem 3.1. A threshold Φ is r-robust and 1/rθ-consistent if and only if it is a function whose graph lies in the shaded area which defines Pr. on Φ defining Pr to prove its Pareto-optimal robustness and consistency. Conversely, for a Pareto-optimal Φ, we analyse the worst-case instances In(q) (Equation (15)), where prices increase uniformly from 1 to q before dropping to 1. By evaluating the ratio ALG(p, y)/p on these instances for well-chosen q, we show that Φ Pr. We now turn to identifying smooth algorithms within the class Pr. 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 rθ if y [1, rθ) φr(y) if y [rθ, 1/r) 1/r if y [1/r, θ] φr : z 7 rθ 1 1 r + 1 r2θ is the line defined by (rθ, rθ) and (θ, 1/r). The function Φ0 r 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 Φ0 r at the point 1/r, as illustrated in Figure 2. This observation suggests that the smoothness of an algorithm AΦ is influenced by the maximal slope of the function z 7 Φ(z). To confirm this intuition, we analyse a family of algorithms {Aρ r}ρ [0,1], associated with the thresholds {Φρ r(y)}ρ defined by rθ if y [1, rθ) φr(y) if y [rθ, 1 r) ρ(1 r) y rθ if y [ 1 1/r if y [ 1 1 rθ 1/r 1 r +ρ(θ 1 r ) θ Prediction y [1,θ] Threshold Φρ r (y) ρ = 0 ρ (0,1) ρ = 1 Figure 2. The threshold functions Φρ r of Aρ r, as defined by Eq. (2). Note that all are equal on [1, r 1). Figure 2 illustrates the threshold functions (Φρ r)ρ [0,1]. Notably, the case ρ = 0 corresponds to the algorithm of Sun et al. (2021), while at the other extreme (ρ = 1) we obtain the threshold Φ1 r : z 7 max(rθ, φr(z)). The standard definition of smoothness involves demonstrating a continuous degradation of algorithm performance as a function of the prediction error η(p , y) := |p y| . A key limitation of η is its sensitivity to rescaling multiplication of the instance by a 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 as is often done in prior work on learning-augmented algorithms. However, this introduces another complication: the asymmetry between y and p . To overcome these issues, we use a multiplicative error measure that retains the desirable properties of scale invariance and symmetry: E : (p , y) 7 min p [θ 1, 1] . (3) This error measure has previously been used in the context of mechanism design with predictions (Balkanski et al., 2024). Note that a perfect prediction corresponds to E(p , y) = 1. We primarily focus on E in the remainder of the paper. However, we also provide smoothness results using the additive error measure η for completeness, in Section 3.2. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search 3.1. Multiplicative error E This first theorem establishes smoothness guarantees of the family {Aρ r}r,ρ with respect to the error measure E. Theorem 3.2. The family {Aρ r}r,ρ satisfies rθE(p , y)sρ , (4) with sρ := max 1, 1 ρ ln θ ln(rθ) 2 , for ρ [0, 1]. For ρ [0, 1], the threshold defining Aρ r lies in Pr, ensuring r-robustness and 1/rθ-consistency (Theorem 3.1). To establish smoothness, we determine the best value of s such that Aρ r/p (1/rθ)Es 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. The smoothness in Theorem 3.2 is quantified by the exponent sρ of E. A smaller value of sρ results in slower degradation of the bound as a function of prediction error, i.e. improved smoothness. In the limit ρ 0, the exponent sρ becomes arbitrarily large, which results in extreme sensitivity to prediction errors, i.e. brittleness. In contrast, the best smoothness is achieved by ρ = 1, yielding an exponent s := s1 = max 1, ln θ ln(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. Theorem 3.3. Let A be any deterministic algorithm with robustness r and consistency 1/rθ. Suppose that A satisfies for all p [1, θ]n and y [1, θ] that rθE(p , y)u (5) for some u R, then necessarily u ln θ ln(rθ) 2. We first prove that, on worst-case instances In(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 Pr. Finally, using the definition of Pr with well-chosen q and y, we derive lower bounds on the smoothness s. This lower bound shows the optimality of the exponent achieved by A1 r for r θ 2/3. Indeed, if this condition is satisfied, then Theorem 3.2 gives rθE(p , y) ln θ ln(rθ) 2 . This implies that, for r [θ 1, θ 2/3], Algorithm A1 r attains the triple Pareto-optimal front for consistency, robustness, and smoothness among all deterministic algorithms for one-max-search. For r [θ 2/3, θ 1/2], A1 r remains smooth and Pareto-optimal; however, its smoothness guarantee might admit further improvement. We conclude this section with some observations. First, note that many learning-augmented algorithms in the literature express consistency and robustness in terms of a parameter λ [0, 1], which reflects the decision-maker s trust in the prediction. A simple yet effective parametrisation of A1 r can be achieved by setting r = θ (1 λ/2). Noting that 1/rθ = θ λ/2, and ln θ ln(rθ) = 2 λ, the result of Theorem 3.2 can be restated, with this parametrization, as p max θ (1 λ 2 E(p , y)max(1, 2 A second observation is that the obtained bounds can be readily adapted to the inverse ratio p /A1 r(p, y), which is also commonly used to define the competitive ratio in onemax-search (El-Yaniv, 1998). Specifically, by defining the inverse error as E = 1/E = max n p p o , we obtain A1 r(p, y) min θ1 λ 2 , θ λ 2 E(p , y)max(1, 2 3.2. Extension to the additive error η While the multiplicative error provides a more natural fit for the problem at hand, we also derive smoothness guarantees for A1 r using the additive error η(p , y) = |p y|. Moreover, we prove that the smoothness it achieves is optimal for η, for all possible values of r [θ 1, θ 1/2]. Theorem 3.4. Let A be any deterministic algorithm with robustness r and consistency 1/rθ. Suppose that A satisfies for all p [1, θ]n and y [1, θ] that rθ β η(p , y) for some β 0, then necessarily β β , where rθ max 1 1 r, 1 rθ 1 Moreover, Algorithm A1 r satisfies (6) with β = β , which shows its optimality. The above theorem establishes that A1 r has the best possible smoothness guarantee amongst all Pareto-optimal algorithms. Consequently, it achieves a triple Pareto-optimal trade-off between consistency, robustness, and smoothness. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search 4. Stochastic One-Max Search One-max-search under competitive analysis is a worst-case abstraction of online selection which is highly skewed towards pessimistic scenarios. This is an approach rooted in theoretical computer science that has the benefit of worstcase guarantees, but does not capture the stochasticity of real markets, e.g. (Cont & Tankov, 2004; Donnelly, 2022). In contrast, in mathematical (and practical) finance, probabilistic analyses such as risk management are preferred, e.g. (Merton, 1975). While reconciling the two approaches remains a very challenging perspective, we aim to narrow the very large gap between the worst-case and stochastic regimes by leveraging a probabilistic approach. This necessitates algorithms that can be robust to the randomness of the market, and to this end, the established smoothness of our algorithm (Section 3) will play a pivotal role, as we will show. A probabilistic analysis can thus yield two main practical benefits: 1) estimate performance under price distributions obtained from financial modelling; 2) leverage the consistency-robustness trade-off to handle risk. In the stochastic formulation of one-max-search, we now consider the prices (Pi)n i=1 to be random variables whose maximum is P F . Since market prices are random, the historical data used to generate a machine-learned prediction should also be random, hence we consider the prediction to be a random variable Y G. As before, we consider that Pi, for i [n], and Y take value in [1, θ]. The trading window unfolds as in the classic one-max-search problem, except that the prices and predictions are now random. We will first give, in Section 4.1, a general probabilistic competitive analysis of the one-max-search problem which shows that the bounds of Section 3 transfer naturally by weighting the bounds of Theorem 3.2 according to the coupling of (P , Y ). In order to better understand the intuition behind these results, in Section 4.2, we instantiate the analysis 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. 4.1. Competitive analysis in the stochastic framework In the stochastic setting, we will evaluate the performance of the algorithm using the ratio of expectations E[ALG(P , Y )]/E[P ], but our results and arguments transfer readily to E[ALG(P , Y )/P ]. 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 coupling π of (P , Y ), yielding E[ALG(P , Y )] := Z ALG(p , y)dπ (p , y) . (7) In consequence, we can identify π and the instance (P , Y ) π without loss of generality, as all such instances are indistinguishable to a probabilistic analysis. 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 {A1 r}r satisfies E[A1 r(P , Y )] E[P ] max r , 1 rθ E [P E(P , Y )s] Proof. Apply Jensen s inequality to Theorem 3.2. As expected, (8) shows that the robustness of {A1 r}r carries over to the stochastic setting through the max{r, } term. 4.2. Instantiations of Lemma 4.1 The coupling π , and Eq. (8) more broadly, encode effects that influence the quality of a 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 = δp (which is to say P = p almost surely), isolates the effect of G. From a 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 Λ : [1, θ] [0, 1] defined by Λ(p ) = E [E(P , Y )s|P = p ] (9) for p [1, θ], directly quantifies the quality of the prediction in terms of the performance, with respect to the true, realised, maximal price p . Indeed, Λ(p ) 1 for all p , and the closer to one, the better the prediction. 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 a maximum with r to any bound on the performance of {A1 r}r. Corollary 4.2. Let F = δp for some p [1, θ], then the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 rθΛ(p ) . (10) Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Viewing Λ as a map (taking G to a real-valued function on [1, θ]) reveals that it quantifies the usefulness of G as a prediction distribution at any p [1, θ]. As an integral functional of G, Λ 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 [1, θ] and G = Unif([p ϵ, p + ϵ]). There is a constant C > 0, dependent only on (s, θ), such that E[A1 r(P , Y )] E[P ] 1 1 s 2p ϵ Cϵ2 , (11) as soon as 0 < ϵ min{θ p , p 1}. Eq. (11) reveals that the performance of {A1 r}r decays from consistency at a rate linear in the uncertainty ϵ, determined by the smoothness s of the algorithm. This captures the scale of the effect of smoothness on a practical example. In Eq. (11) we characterised the rate up to the second order (ϵ2), but higher-order estimates can be obtained similarly. Moreover, this shows that all sufficiently regular distributions can be approximated in terms of Λ using mixtures over the model of Example 4.3, i.e. G = PK k=1 wk Unif(Ik) for wi > 0, P i wi = 1, and (Ik)k disjoint subintervals of [1, θ] (see Corollary C.2). Numerical integration (e.g. Monte Carlo) offers another alternative method to estimate Λ. Deterministic predictions, stochastic prices 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 δy which is deterministic. While this setting appears symmetrical to the previous one, this is not the case as the one-max-search problem itself is highly asymmetrical. Indeed, using a threshold means that predictions too high or too low do not have the same impact. By defining Υ(y) : = E[P E(P , Y )s|Y = y] E[P ] for y [1, θ] , we can establish a quality quantification which mirrors Λ: this functional of F states how good any unique prediction y is at influencing algorithmic performance. This yields the following Corollary 4.4, an analogue of Corollary 4.2. Note that Υ(y) 1 for all y [1, θ]. Corollary 4.4. Let G = δy for some y [1, θ]. The family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 rθΥ(y) . (12) Independent stochastic predictions and prices The theoretical value of the above two models is their isolation of the effect of G into Λ (resp. F into Υ). 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 inaccurate predictions can still induce (on average) good thresholds because of the algorithm s internal mechanics. This effect is captured by the interaction between the functional Λ and the distribution of prices F (resp. Υ and G), as shown by Corollary 4.52. Corollary 4.5. Let π = F G, the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 Z Υ(y)d G(y) E[P ] d F (p ). (13) Since Λ(z) is always smaller than 1 (and again, the closer to one, the better the predictions are), Eq. (13) gives an intuitive bound on the performance of the algorithms. The theoretical benefit of the model transpires in Corollary 4.5: independence separates the integral against π in Eq. (7) into a double integral revealing Υ. 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 C). 4.3. Dependent predictions and optimal transport The previous models successfully isolated the effect of the distributions F and G. Using tools from Optimal Transport (OT) theory, one can generalise this approach. For brevity, we refer simply to (Villani, 2009) for the technicalities and background of this field. The key observation is that the right-hand side of Eq. (7) is a transport functional of π , which can be lower bounded uniformly over the set of couplings Π(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 (Villani, 2009), hence Theorem 4.6. Theorem 4.6. The family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 inf Z p E(p , y)sdπ(p , y) E[P ] . (14) where the infimum is taken over couplings π Π(F , G) ; in particular, this implies the numerator is as most E[P ]. Theorem 4.6 highlights a novel connection between (stochastic) competitive analysis and optimal transport. Con- 2The following result also applies to sampling of distributionvalued predictions (Angelopoulos et al., 2024; Dinitz et al., 2024). Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search trary to most literature in OT, in which the optimal configuration tries to minimise the distance points (p , y) are moved, the infimum in Eq. (14) tries to push them far apart to induce the algorithm to make mistakes. Optimal transport tools have been used before in algorithms with predictions, notably in the distributional predictions setting in which the algorithm is given G itself (Angelopoulos et al., 2024; Dinitz et al., 2024). This analysis, however, is fundamentally different: it 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 E(p , y)s, which is why our OT problem, i.e. Eq. (14), is not symmetric: exchanging the roles of (G, F ) cannot be expected to yield the same performance. The optimal transport problem in Eq. (14) generally has no closed form, but thanks to its (strong) dual form (see Appendix C.2), one can use problem-specific knowledge to derive lower bounds, as demonstrated by Proposition 4.7. Proposition 4.7. The family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 1 p 1+sd F (p )+ Z θ θ 1 2 p 1 sd F (p ) Moreover, the RHS is the infimum over G of Eq. (14). Proposition 4.7 once more highlights the asymmetry of the problem through different contributions of the regions above and below θ, which is the threshold that guarantees 1/ θrobustness. The dual problem provides thus a practical tool for designing lower bounds for the performance of {A1 r}r in the stochastic one-max-search setting. 5. Numerical Experiments To complement our theoretical analysis and evaluate the performance of our algorithm in practice, we present experimental results in this section. We defer additional experimental results to Appendix E. 5.1. Experiments on synthetic data We fix θ = 5, λ = 0.5, and r = θ (1 λ/2). We consider instances {In(q)}q [1,θ], where In(q) is the sequence starting at 1, and increasing by θ 1 n 1 at each step until reaching q, after which the prices drop to 1. A more formal definition of this instance can be found in Equation 15. These instances model worst-case instances with maximum price q, and they are used in general to prove impossibility results in the one-max-search problem. We fix an error level Emin and, for each p [1, θ], we 0.0 0.2 0.4 0.6 0.8 1.0 1 Emin Empirical ratio ρ =0 ρ =0.5 ρ =1 Figure 3. Performance of Aρ r with ρ {0, 0.5, 1}. 0.0 0.2 0.4 0.6 0.8 1.0 α [0,1] Empirical ratio ρ = 0 ρ = 1 Figure 4. Comparison of A1 r and A0 r on the Bitcoin price dataset. generate the prediction y by sampling uniformly at random in the interval [p Emin, p /Emin] = {z : E(p , z) Emin}, then compute the ratio Aρ r(In(p ), y)/p . For Emin (0, 1], Figure 3 illustrates the worst-case ratio infp [1,θ] Ey[Aρ r(p , y)]/p , where the expectation is estimated empirically using 500 independent trials. The figure also shows, with dashed lines, the theoretical worst-case ratio corresponding to the given error level Emin. Figure 3 shows that for the different values of ρ, the worstcase ratio is 1/rθ when the prediction is perfect, i.e. Emin = 1, and degrades to r when the prediction can 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 ρ {0.5, 1} decrease much slower. This is again consistent with the smoothness of Aρ r, as shown in Theorem 3.2. 5.2. Experiments on real data To further validate our algorithm s practicality, we evaluate it on the experimental setting of (Sun et al., 2021). Specifi- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search cally, we use real Bitcoin data (USD) recorded every minute from the beginning of 2020 to the end of 2024. The dataset s prices range from L = 3, 858 USD to U = 108, 946 USD, yielding θ = U/L 28. We randomly sample a 10-week window of prices W0, let W 1 be the 10-week window of prices preceding W0 and take the prediction y = α max W 1 + (1 α) max W0. Here, α captures the prediction error: α = 0 represents perfect foresight, while α = 1 corresponds to a naive prediction equal to the maximum price in W 1. To simulate worst-case scenarios, the last price in W0 is changed to L with a probability of 0.75. For each value of α, we sample m = 100 windows (W j 0 )m j=1 and compute the ratio Rm = minj{Aρ r(W j 0 , y)/ max W j 0 } for ρ {0, 1}. We then empirically estimate E[Rm] by repeating this process 50 times. We choose the robustness r of Aρ r by setting λ [0, 1] and r = θ (1 λ/2). Figure 4 shows the obtained results with λ = 0.5, and compares our algorithm A1 r to the algorithm of (Sun et al., 2021), which corresponds to A0 r. For α = 0, i.e. perfect prediction, they both achieve the consistency 1/rθ. However, as the error increases, A0 r quickly degrades to the robustness guarantee r, whereas A1 r degrades more gradually. 6. Conclusion We provided an intuitive Pareto-optimal and smooth algorithm for a fundamental online decision problem, namely one-max-search. We believe our methodology can be applied to generalizations such as the k-search problem (Lorenz et al., 2009), i.e. multi-unit one-max-search, recently studied in a learning-augmented 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-Yaniv, 2005)) to such realistic learning-augmented 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 a promising direction for both theories. 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. Impact Statement This paper presents a work whose goal is to advance the field of learning-augmented algorithms. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. Acknowledgements This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-0003) and through 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. This work was also partially funded by the project PREDICTIONS, grant ANR-23-CE48-0010 from the French National Research Agency (ANR). Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., and Re, G. Online facility location with multiple advice. Advances in neural information processing systems, 34: 4661 4673, 2021. Angelopoulos, S. Online search with a hint. Inf. Comput., 295(Part B):105091, 2023. Angelopoulos, S., Kamali, S., and Zhang, D. Online search with best-price and query-based predictions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pp. 9652 9660. AAAI Press, 2022. Angelopoulos, S., Bienkowski, M., D urr, 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 Intelligence, IJCAI-24, pp. 3652 3660. International Joint Conferences on Artificial Intelligence Organization, 8 2024. Main Track. Antoniadis, A., Gouleakis, T., Kleer, P., and Kolev, P. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33:7933 7944, 2020. Azar, Y., Panigrahi, D., and Touitou, N. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 35 66. SIAM, 2022. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Bai, X. and Coester, C. Sorting with predictions. Advances in Neural Information Processing Systems, 36:26563 26584, 2023. 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, pp. 1184 1184, 2024. 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. Benomar, Z. and Coester, C. Learning-augmented priority queues. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. Benomar, Z. and Perchet, V. On tradeoffs in learningaugmented algorithms, January 2025. URL https:// arxiv.org/abs/2501.12770. ar Xiv:2501.12770 [cs]. Borodin, A. and El-Yaniv, R. Online computation and competitive analysis. Cambridge university press, 2005. Christianson, N., Shen, J., and Wierman, A. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. In AISTATS, volume 206 of Proceedings of Machine Learning Research, pp. 9377 9399. PMLR, 2023. Cont, R. and Tankov, P. Financial modelling with jump processes. Chapman & Hall/CRC financial mathematics series. Chapman & Hall/CRC, Boca Raton, Fla, 2004. ISBN 978-1-58488-413-2. Dinitz, M., Im, S., Lavastida, T., Moseley, B., Niaparast, A., and Vassilvitskii, S. Binary Search with Distributional Predictions, November 2024. URL http://arxiv. org/abs/2411.16030. ar Xiv:2411.16030 [cs]. Donnelly, R. Optimal Execution: A Review. Applied Mathematical Finance, 29(3):181 212, May 2022. ISSN 1350486X, 1466-4313. D utting, P., Lattanzi, S., Paes Leme, R., and Vassilvitskii, S. Secretaries with advice. Mathematics of Operations Research, 49(2):856 879, 2024. El-Yaniv, R. Competitive solutions for online financial problems. ACM Computing Surveys, 30(1):28 69, March 1998. ISSN 0360-0300. Elenter, A., Angelopoulos, S., D urr, C., and Lefki, Y. Overcoming brittleness in pareto-optimal learning augmented algorithms. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Gollapudi, S. and Panigrahi, D. Online algorithms for rentor-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML, volume 97 of Proceedings of Machine Learning Research, pp. 2319 2327. PMLR, 2019. Im, S., Kumar, R., Montazer Qaem, M., and Purohit, M. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems, 34:2733 2743, 2021. Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859 1877. SIAM, 2020. 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 International Conference on Future and Sustainable Energy Systems, e-Energy 2024, Singapore, June 4-7, 2024, pp. 50 71. ACM, 2024. Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Machine Learning, pp. 13431 13440. PMLR, 2022. Lindermayr, A. and Megow, N. Repository of works on algorithms with predictions. https:// algorithms-with-predictions.github.io, 2025. Accessed: 2025-01-01. Lorenz, J., Panagiotou, K., and Steger, A. Optimal algorithms for k-search with application in option pricing. Algorithmica, 55(2):311 328, 2009. Lykouris, T. and Vassilvtiskii, S. Competitive caching with machine learned advice. In International Conference on Machine Learning, pp. 3296 3305. PMLR, 2018. Merton, R. C. Optimum consumption and portfolio rules in a continuous-time model. In Ziemba, W. and Vickson, R. (eds.), Stochastic Optimization Models in Finance, pp. 621 661. Academic Press, 1975. 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. Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, volume 31, pp. 9661 9670, 2018. Rosenfield, D. B. and Shapiro, R. D. Optimal adaptive price search. Journal of Economic Theory, 25(1):1 20, 1981. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Sun, B., Lee, R., Hajiesmaili, M., Wierman, A., and Tsang, D. Pareto-Optimal Learning-Augmented 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 uncertainty-quantified predictions. In Forty-first International Conference on Machine Learning, ICML, 2024. Villani, C. Optimal Transport, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi: 10.1007/ 978-3-540-71050-9. Wei, A. and Zhang, F. Optimal robustness-consistency tradeoffs for learning-augmented online algorithms. In Proceedings of the 33rd Conference on Neural Information Processing Systems (Neur IPS), 2020. Zeynali, A., Kamali, S., and Hajiesmaili, M. Robust learning-augmented dictionaries. In Forty-first International Conference on Machine Learning, ICML, 2024. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Appendices A. Organisation and Notation A.1. Organisation of Appendices The following appendices are divided in the following way: Appendix B contains 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 is transversal and regroups results in which the error analysis is additive instead of multiplicative. A.2. Notation The space of probability measures over a set S is denoted P(S). The set of couplings between G and F is Π(G, F ) := {π P([1, θ]2) : π( , [1, θ]) = G, π([1, θ], ) = F } For x R, δx denotes the Dirac Delta distribution (i.e. the distribution of a degenerate random variable X satisfying P(X = x) = 1). B. Proofs of Section 3 We present in this appendix the proofs of the results stated in Section 3. Let us introduce some notations and observations that we will use throughout the proofs. For all n 1, we denote by (pn i )n i=1 the sequence of prices defined by i [n] : pn i = 1 + θ 1 and for all q [1, θ], we denote by In(q) the sequence of prices that are equal to pn i while the latter is smaller than q then drops to 1. Formally, the ith price in this sequence is In(q)i = 1 + (pn i 1)1pn i q . (15) On the class of instances {In(q)}q [1,θ], any deterministic learning-augmented algorithm for one-max-search is equivalent to a single-threshold algorithm AΦ. Moreover, observe that the payoff of AΦ satisfies AΦ(In(q), y) = 1 if Φ(y) > q Φ(y) + O( 1 n) otherwise . (16) Indeed, if the threshold exceeds the maximum price q in the sequence, then no price is selected and the algorithm is left with a payoff of 1. On the hand, if the threshold is at most q, then the selected price is min{pn i | pn i Φ(y)}. By definition of the prices pn i , this value is in [Φ(y), Φ(y) + θ 1 n 1]. In particular, for n arbitrarily large, the payoff of an algorithm with threshold Φ(y) q is arbitrarily close Φ(y). 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 r, the set of all thresholds Φ : [1, θ] [1, θ] such that AΦ has robustness r and consistency 1/rθ is Pr := n Φ : z [1, θ] : rθ Φ(z) 1 z [rθ, θ] : z rθ Φ(z) z o . Proof. Let Φ : [1, θ] [1, θ], and consider that AΦ is r-robust and 1/rθ-consistent. We will prove that Φ is necessarily in the set Pr. First inclusion. Let us first prove that Φ(z) [rθ, 1/r] for all z [1, θ]. Let z [1, θ], and consider the sequence of prices In(q). Since AΦ is r-robust, then by Eq. (16), it holds for q = Φ(z) 1 n and y = z that r AΦ(In(q), z) q = 1 Φ(z) 1 Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search On the other hand, for q = θ, we obtain again using Eq. (16) that r AΦ(In(q), z) q = Φ(z) + O( 1 We deduce that Φ(z) satisfies Φ(z) [rθ O( 1 n), 1/r + 1 n], and taking the limit for n gives that Φ(z) [rθ, 1/r]. Consider now z (rθ, θ], and let us prove that Φ(z) [ z rθ, z]. We first prove by contradiction that Φ(z) z. Suppose this is not the case, i.e. Φ(z) > z then using Equation (16) and that the algorithm is 1/rθ-consistent, considering that the maximum price is z and the prediction is perfect, we deduce that 1 rθ AΦ(In(z), z) hence z rθ, which contradicts the initial assumption that z (rθ, θ]. Therefore, Φ(z) z for all z (rθ, θ]. Using this inequality, it follows again by Eq. (16) and 1/r-consistency of the algorithm that 1 rθ AΦ(In(z), z) Consequently, Φ(z) [ z rθ, z] for all z (rθ, θ]. This proves that the set of all thresholds yielding Pareto-optimal levels of robustness and consistency (r, 1/rθ) is included in the set Pr. Second inclusion. The other inclusion is easier to prove. Let Φ Pr, and let us prove that AΦ is r-robust and 1/rθconsistent. Consider an arbitrary sequence of prices p = (pi)n i=1 [1, θ] and a prediction y [1, θ], and let us denote by p the maximum price in the sequence p. The robustness of AΦ follows from the bounding Φ(y) [rθ, 1/r]. Indeed, we obtain using Eq. (16) that if p < Φ(y) then AΦ(p,y) p = 1 p 1 Φ(y) r, if p Φ(y) then AΦ(p,y) which proves that AΦ is r-robust. Now the consistency of the algorithm follows from the bounding Φ(z) [ z rθ, z] for all z (rθ, θ]. Indeed, assume that the prediction is perfect, i.e. y = p , then we have the following: if p rθ then AΦ(p,p ) p = 1 p 1 rθ, if p > rθ then we have that Φ(p ) p , hence AΦ(p,p ) This proves AΦ is 1/rθ-consistent, which concludes the proof. B.2. Smoothness analysis of Aρ r Lemma B.1. Let a > 0, b R, and u < v (0, ) satisfying that z 7 az + b 0 on the interval [u,v], then it holds for all ℓ R that max z [u,v] (az + b)ℓ+1 zℓ = max (au + b)ℓ+1 uℓ , (av + b)ℓ+1 Proof. For all z [u, v], we can write that (az + b)ℓ+1 zℓ = az + b ℓ+1 = az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ+1 Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search hence, computing the derivative gives (az + b)ℓ+1 az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ+1 = (ℓ+ 1) a ℓ+ 1z ℓ/(ℓ+1) bℓ ℓ+ 1z ℓ/(ℓ+1) 1 az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ = az ℓ/(ℓ+1) 1 z bℓ az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ . The monotonicity of z 7 (az+b)ℓ+1 zℓ on the interval [u, v] is therefore determined by the sign of z bℓ a . Indeed, az ℓ/(ℓ+1) 1 0 because a 0 and z u > 0, and the term az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓis also non-negative because we can write that az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ = az1/(ℓ+1) + bz ℓ/(ℓ+1) ℓ+1 ℓ ℓ+1 = (az + b)ℓ+1 and both z and az + b are positive on the interval [u, v]. Consequently, depending on how bℓ a compares to the bounds u, v of the interval, the mapping z 7 (az+b)ℓ+1 zℓ can be either decreasing, increasing, or decreasing then increasing. In the three cases, its maximum is reached in one of the interval limits u or v, thus max z [u,v] (az + b)ℓ+1 zℓ = max (au + b)ℓ+1 uℓ , (av + b)ℓ+1 Corollary B.2. For all ρ (0, 1], for s = 1 ρ ln θ ln(rθ) 2 it holds that r )] Φρ r(z)s+1 Proof. By definition of the threshold Φρ r, we have for z [ 1 Φρ r(z) = φr(z) + which can be written as az + b with a = 1/r φr(z) ρ(θ 1/r) 0 because φr(z) < 1/r for all z θ. Consequently, Lemma B.1 gives that r )] Φρ r(z)s+1 zs = max Φρ r(1/r)s+1 1/rs , Φρ r( 1 = max φr(1/r)s+1 1/rs , 1/rs+1 We will now prove that both terms in the maximum are at most equal to rθ. For all h R, we have the equivalences r))h rθ 1 (1 + ρ(rθ 1))h r2θ h ln 1 + ρ(rθ 1) ln(r2θ) = ln θ 2 ln(rθ) h ln θ 2 ln(rθ) ln 1 + ρ(rθ 1) . Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Moreover, we have by concavity of x 7 ln x that ln 1 + ρ(rθ 1) = ln ρrθ + (1 ρ) ρ ln(rθ) + (1 ρ) ln 1 = ρ ln(rθ) , therefore, s = 1 ρ ln θ ln(rθ) 2 satisfies ln(rθ) 2 = ln θ 2 ln(rθ) ρ ln(rθ) ln θ 2 ln(rθ) ln 1 + ρ(rθ 1) , and we deduce with the previous equivalences that r) s rθ . (18) Let us now prove that φr(1/r)s+1 1/rs rθ. Since φr is a linear mapping with a positive slope, using that 1/r [rθ, θ] and Lemma B.1, we obtain that 1/rs max z [rθ,θ] φr(z)s+1 = max φr(rθ)s+1 (rθ)s , φr(θ)s+1 = max (rθ)s+1 (rθ)s , (1/r)s+1 = max rθ, θ (rθ)s+1 Observing that k = ρs = ln θ ln rθ 2 is the solution of θ (rθ)k+1 = rθ, and given that k s and ρ 1, we have that θ (rθ)s+1 θ (rθ)k+1 = rθ , hence φr(1/r)s+1 1/rs φr(1/r)k+1 1/rk = max rθ, θ (rθ)k+1 = rθ . (19) Finally, using Equations (17), (18), and (19), we deduce that r )] Φρ r(z)s+1 which concludes the proof. Theorem 3.2. The family {Aρ r}r,ρ satisfies rθE(p , y)sρ , (4) with sρ := max 1, 1 ρ ln θ ln(rθ) 2 , for ρ [0, 1]. Proof. Consider r [θ 1, θ 1/2], an instance p = (pi)n i=1, a prediction y of p , and let E = min( y y ). We will prove the smoothness guarantee separately on the intervals [1, rθ), [rθ, 1/r], [1/r, 1/r + ρ(θ 1/r)], and [1/r + ρ(θ 1/r), θ]. To lighten the notation, we simply write s for max 1, 1 ρ( ln θ ln(rθ) 2) instead of sρ. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Case 1. If y [1, rθ), then Φρ r(y) = rθ. If p < rθ then and if p rθ then the payoff of the algorithm is at least equal to the threshold rθ, hence p Φρ r(y) p = rθ We used in the last two inequalities that y p E, rθ 1 and s 1. Case 2. Consider now the case of y [rθ, 1/r], then Φρ r(y) = φr(y) = rθ 1 1 r + 1 r2θ rθ. If p Φρ r(y) then the payoff of the algorithm is at least equal to the threshold. Using that y p E, 1 E and p θ, we obtain p Φρ r(y) p = φr(y) = 1 rθ(1 r) r2θ r + 1 r2θ E rθEs . (20) On the other hand, if p < Φ1 r(y), recalling that Φρ r(z) = φr(z) for z [rθ, 1/r], we can use Inequality (19) from the proof of Corollary B.2, which gives for k = ln θ ln(rθ) 2 that max z [rθ,θ] Φρ r(z)k+1 zk = φr(z)k+1 zk = max rθ, θ (rθ)k+1 and it follows that p 1 Φρ r(y) 1 Φρ r(y) 1 rθ Φρ r(y)k+1 where we used in the last inequality that E 1 and k k Case 3. For y [1/r, 1/r + ρ(θ 1/r)], if p Φρ r(y), then observing that Φρ r(y) φr(y), we obtain with the same computation as Eq. (20) that Aρ r p Φρ r(y) p φr(y) On the other hand, if p < Φρ r(y), then by Corollary B.2, we have for k = ln θ ln(rθ) 2 that r )] Φρ r(z) k ρ +1 Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search therefore, the ratio between the algorithm s payoff and the maximum payoff can be lower bounded as follows p 1 Φρ r(y) 1 Φρ r(y) 1 rθ Φρ r(y) k ρ +1 The last inequality holds because k Case 4. Finally, if y (1/r + ρ(θ 1/r), θ], then Φρ r(y) = 1/r. If p 1/r, then we have immediately that p Φρ r(y) p = 1 rp 1 Now if p < 1/y, let k = ln θ ln(rθ) 2 and zρ = 1/r + ρ(θ 1/r). Observing that s k ρ k, and y zρ, and ry 1, we deduce from Corollary B.2 k/ρ = (1/r) k ρ +1 yk/ρ (1/r) k ρ +1 zk/ρ ρ = Φ(zρ) k ρ +1 zk/ρ ρ max z [ 1 r ,zρ] Φρ r(z) k ρ +1 which yields for p < Φρ r(y) = 1/r that p > 1 1/r 1 Conclusion. All in all, for any y [1, θ], it holds that with s = max 1, 1 ρ( ln θ ln(rθ) 2) . Finally, the threshold function Φρ r is in the class Pr, then we have by Theorem 3.1 that Aρ r is r-robust, and it deduce that which concludes the proof. B.3. Lower Bound on Smoothness Theorem 3.3. Let A be any deterministic algorithm with robustness r and consistency 1/rθ. Suppose that A satisfies for all p [1, θ]n and y [1, θ] that A(p, y) rθE(p , y)u (5) for some u R, then necessarily u ln θ ln(rθ) 2. Proof. Let A be a deterministic algorithm for one-max-search with, and assume that it satisfies for all p and y that rθE(y, p )u . Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search In particular, A has robustness r and consistency 1/rθ. To prove the lower bound, we will use the instances {In(q)}q [1,θ] defined in Eq. (15). On these instances, for a fixed prediction y, any deterministic algorithm behaves as a single threshold algorithm. Therefore, there exists Φ : [1, θ] [1, θ] satisfying that A(In(q), y) = AΦ(In(q), y) for all q, y [1, θ]. The lower bound satisfied by A ensures that it achieves Pareto-optimal consistency 1/(rθ) and robustness r. Consequently, AΦ also attaints them on the sequences of prices {In(q)}q [1,θ]. 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 Φ. In particular, we have that Φ(rθ) = rθ and Φ(θ) = 1/r. Let y = θ and q = Φ(θ) 1+ε for some ε > 0. Since q < Φ(θ), when A is given as input the instance In(q), it does not select the maximum price and ends up selecting a price of 1, hence A(In(q), θ) q = (1 + ε)r . Furthermore, by assumption, this ratio above is at least 1 rθE(q, θ)u = 1 rθE 1 (1 + ε)r, θ u = 1 1 (1 + ε)rθ u = 1 (rθ)u+1 (1 + ε)u , therefore, we have that (1 + ε)r 1 (rθ)u+1 (1 + ε)u . This inequality holds for all ε > 0, which gives in the limit ε 0 that r 1 (rθ)u+1 , and we obtain by equivalences that r 1 (rθ)u+1 , (rθ)u θ (rθ)2 u ln(rθ) ln θ 2 ln(rθ) u ln θ ln(rθ) 2 , which gives the claimed lower bound on u. C. Complements to Section 4 Recall in this section the notations P F for the maximum price, and Y G for the prediction. When considered, their coupling is denoted π . C.1. Complements on Section 4.2 Stochastic predictions, deterministic prices. Corollary 4.2. Let F = δp for some p [1, θ], then the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 rθΛ(p ) . (10) Proof. This is obtained by direct instantiation of Lemma 4.1. In particular, for F = δp the second term of Eq. (8) can be substituted into with E[P E(p , y)s] = E[P E(P , Y )s|P = p ]p = Z min y Computing this integral explicitly reveals it to be Λ(p ). Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Through this section, we will use the following identity Λ(p ) = Z p s d G(y) + Z θ s d G(y) . (21) which is easily derived from the proof above. Inspection of Eq. (21) reveals that Λ contains two different regimes (above and below p ). The mirrored coefficients of (p , y) in each term reflect the inherent asymmetry of a threshold algorithm: performance is highly sensitive to whether p Φ1 r(Y ), which transfers to Eq. (21) via the definition of E. Example 4.3. Let F = δp for some p [1, θ] and G = Unif([p ϵ, p + ϵ]). There is a constant C > 0, dependent only on (s, θ), such that E[A1 r(P , Y )] E[P ] 1 1 s 2p ϵ Cϵ2 , (11) as soon as 0 < ϵ min{θ p , p 1}. Proof of Example 4.3. 1. Consider first s > 1. Compute p Λ for this choice of G, which yields p Λ(p ) = p 1 s p ϵ ysdy + p 1+s 2ϵ p 1+s (p ϵ)1+s 1 + s + p 1+s 2ϵ (p + ϵ)1 s p 1 s Continuous differentiability of p 7 p 1+s and p 7 p 1 s, along with Taylor s theorem, implies the existence of ( ˆp 1, ˆp 2) [p ϵ, p ] [p , p + ϵ] such that: p 1+s (p ϵ)1+s 1 + s = ϵp s ϵ2 2 sp s 1 + ϵ3 6 s(s 1) ˆp s 2 1 , (p + ϵ)1 s p 1 s 1 s = ϵp s ϵ2 2 sp 1 s ϵ3 6 s(s + 1) ˆp (2+s) 2 . Remark that one has the remainder bounds: C1 := s(s 1) 6 θmin{0,2 s} s(s 1) C2 := s(1 + s) 6 ˆp 2+s 2 . Applying these bounds and the Taylor expansions of Φ to Eq. (22), yields p Λ(p ) p s 2ϵ Cp ϵ2 (23) with C = (C1θ s + C2)/2. Finally, injecting Eq. (23) into Corollary 4.2 and recalling that G = δp implies Γ = c/p yields Eq. (10). 2. Now, for s = 1, the computation of Λ reduces to p Λ(p ) = 1 2ϵ p 2 (p + ϵ)2 2ϵ (log(p + ϵ) log(p )) . Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Using a Taylor expansion on log, for some t [0, 1], we have 2ϵ (log(p + ϵ) log(p )) p 2 2 1 p 2 + ϵ3 6 1 2(p + ϵt)3 and thus, we obtain an overall bound matching Eq. (23) up to modifying C. Corollary C.1. Let F = δp for some p [1, θ] and G = Unif([p (1 ϵ ), p (1 + ϵ )]). There is C > 0 dependent only on (s, θ) such that E[A1 r(P , Y )] E[P ] 1 2ϵ C ϵ2 , (24) as soon as 0 < ϵ min{1 p 1, θp 1 1}. Proof. Follow the proof of Example 4.3 with ϵ = ϵ p . Corollary C.2. Let (Ik)K k=1, Ik := [µk ϵk, µk + ϵk] for k [K] be a collection of (w.l.o.g. disjoint) sub-intervals of [1, θ]. Let F = δp and let k=1 wk Unif(Ik) be a mixture of Uniforms of the intervals Ik, i.e. wk > 0 for all k [K] and P k wk = 1. Then, there is a constant C > 0 dependent only on (r, θ) such that E[A1 r(P , Y )] E[P ] 1 rθE[P ] wk 1 s 2p ϵk k =k wk E(p , µk)s + C X k [K] wkϵ2 k . in which k denotes the index (if it exists) such that p Ik . Proof. Note that G has density wk 2ϵk 1{y [µk ϵk,µk+ϵk]} with respect to the Lebesgue measure. We can thus express Λ as a function of Λk its analogues for each Unif(Ik) as k=1 wkΛk(p ) . (25) We will now be able to proceed on each Λk as in the proof of the first part of Example 4.3. Let us remark that the case of k permits a direct application of Example 4.3.1, as p Ik. This readily implies a contribution to the final bound of wk (1 s 2p ϵk Cϵ2 k) , (26) which is the first term of Eq. (25). Let us now fix k = k . Without loss of generality, we will order the intervals, so that k < k implies that x < p for every x Ik and conversely for k > k . Notice that this implies that exactly one integral in each Λk, k = k , may be non-zero, which is to say p Λk(p ) = p 1 s (µk + ϵk)1+s (µk ϵk)1+s 1 + s 1{k < k } + p 1+s (µk + ϵk)1 s (µk ϵk)1 s 1 s 1{k > k } Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search for any k = k . Let us take each term in turn and apply Taylor s theorem following the same methodology as the proof of Example 4.3. By adding and subtracting µ1+s k (resp. µ1 s k ), and using Taylor s theorem yields the existence of (C(1) k , C(2) k )k =k such that (µk + ϵk)1+s (µk ϵk)1+s 1 + s 2ϵkµs k + ϵ3 k 6 C(1) k , (µk + ϵk)1 s (µk ϵk)1 s 1 s 2ϵkµ s k + ϵ3 k 6 C(2) k . Combining these over k [K] yields k =k wkΛk(p ) p 1 s X kk wkµ s k + 1 kk C(2) k wkϵ2 k Now, add together Equations (25) and (26), recalling Eq. (27), and appeal to Corollary 4.2 to obtain E[A1 r(P , Y )] E[P ] Γ wk 1 s 2p ϵk for a suitably chosen constant C 0. To complete the proof, notice that the two sums can be combined using E as µk < p if an only if k < k . Deterministic predictions, stochastic prices Hereafter, we will use the following identity Υ(y) : = 1 E[P ]p Z y s d F (p ) + p Z θ s d F (p) . Stochastic independent predictions and prices Corollary 4.5. Let π = F G, the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 Z Υ(y)d G(y) E[P ] d F (p ). (13) Proof. Starting from Lemma 4.1, this follows from E[A1 r(P , Y )] E[P ] 1 rθE[P ] Z Z p E(p , y)sd G(y)d F (p ) . Corollary C.3. Let π = F G, with F , G having density with respect to the Lebesgue measure, then the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 rθE[P ] 1 p 1 sd F (p ) Z θ 1 y sd G(y) + Z θ 1 p 1+sd F (p ) Z θ 1 p 1 sd F (p ) + y s Z θ y p 1+sd F (p ) Remark C.4. The result of Corollary C.3 can be slightly tweaked to hold even without densities using Lebesgue-Stieltjes integration by parts. We omit these details for the sake of conciseness. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Proof. Starting with Corollary 4.5, decompose the integral as Z θ 1 p Λ(p )d F (p ) = Z θ 1 p 1 s Z p 1 ysd G(y)d F (p ) | {z } A 1 p 1+s Z θ p y sd G(y)d F (p ) | {z } B Using integration by parts, in which the parts for A are x 7 R x 1 p 1 sd F (p ) and x 7 R x 1 ysd G(y) yields 1 p 1 sd F (p ) Z θ 1 y sd G(y) Z θ 1 p 1 sd F (p )d G(y) . (30) Similarly, B can be integrated by parts with parts x 7 R θ x p 1+sd F (p ) and x 7 R θ x y sd G(y), which yields 1 p 1+sd F (p ) Z θ 1 ysd G(y) Z θ y p 1+sd F (p )d G(y) . (31) Combining Equations (30) with (31) completes the proof. Proposition C.5. Let π = F G and F = G = Unif([c1, c2]) the family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] 1 ζ(2 s)ζ(1 s) c2 s 1 ζ(1 + s) 2 s + ζ(2 + s)ζ(1 + s) c2+s 2 ζ(1 s) 2 + s ζ(3) 1 2 s 1 2 + s when s {1, 2}, with ζ : γ (0, + ) 7 (cγ 2 cγ 1)γ 1. Proof. Starting with the decomposition of Corollary C.3, we can compute the terms separately. For the first two, we have Z θ 1 p 1 sd F (p ) Z θ 1 y sd G(y) = C c2 s 2 c2 s 1 2 s m1 s 2 m1 s 1 1 s 1 p αd F (p ) Z θ 1 ysd G(y) = C c2+s 2 c2+s 1 2 + s m1+s 2 m1+s 1 1 + s in which C := 1 (c2 c1)(m2 m1) . Turning now to the second term of Eq. (29), we have Z y 1 p 1 sd F (p ) = 1 c2 c1 y2 s c2 s 1 2 s 1{y [c1,c2]} + c2 s 2 c2 s 1 2 s 1{y>c2} y p αd F (p ) = 1 c2 c1 c2+s 2 y2+s 2 + s 1{y [c1,c2]} + c2+s 2 c2+s 1 2 + s 1{y rθ. It holds that Since rθ 1, we have that (rθ)2 rθ, thus the mapping z 7 z r2θ2 z rθ is non-decreasing on (rθ, θ], and we deduce that rθ max 1 1 r, 1 rθ 1 and successive equivalences, recalling that p > rθ, show that p rθ β(p rθ) 1 Combining this with Eq. (41) and using that y rθ, we obtain rθ β η(p , y) Case 2. For y (rθ, θ], the threshold is Φ1 r(y) = rθ 1 1 r + 1 r2θ Assume that p < Φ1 r(y). Since y > rθ, using the definition of β and Lemma D.1 yields rθ max 1 1 r, 1 rθ 1 rθ φr(y) rθ Using again that y > rθ, we have that the mapping z 7 z rθ y z is non-decreasing on [1, y], and given that y < Φ1 r(y) = φr(y) and both y and φr(y) are within the interval [1, y] (φ(z) z for z rθ), we deduce that and using that y < Φ1 r(y) y, this is equivalent to writing Hence we have the lower-bound rθ β η(y, p ) Assume now that p [Φ1 r(y), y). Since A1 r is r-robust and 1/rθ-consistent, Theorem 3.1 shows that the threshold Φ1 r satisfies Φ1 r(z) z rθ for all z (rθ, θ], which is in particular true for y with the current assumptions. Therefore, we obtain immediately that rθ β η(p , y) Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Finally, assume that p [y, θ]. Using the expression of Φ1 r(y), we have p Φ1 r p = 1 rθ (1 r)rθ 1 r2θ rθ r2 r + 1 r2θ rθ β η(p , y) where we used in the last inequality that β := 1 r2θ rθ max 1 1 r, 1 rθ 1 1 r2θ (1 r)rθ and that η(p , y) = p y since p y. This concludes the proof. D.2. Lower bound on smoothness Lemma D.3. Let A be any algorithm with robustness r and consistency 1/rθ. Suppose that A satisfies for all p [1, θ]n and y [1, θ] that A(p, y) rθ β η(p , y) for some β R, then necessarily β 1 r2θ rθ max 1 1 r, 1 rθ 1 . Proof. Consider an algorithm A and β R satisfying the assumptions of the theorem. To establish the lower bound, we consider the instances {In(q)}q [1,θ] as defined in Eq. (15). On these instances, any deterministic algorithm is equivalent to a threshold-based algorithm. In particular, A is identical to AΦ for some Φ : [1, θ] [1, θ]. The assumption on A ensures that it achieves Pareto-optimal consistency 1/(rθ) and robustness r. Consequently, AΦ also attaints them on the sequences of prices {In(q)}q [1,θ]. 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 Φ. In particular, we have that Φ(rθ) = rθ and Φ(θ) = 1/r. Let us now prove the lower bound on β. Let y = θ and qε = Φ(θ) 1+ε < Φ(θ) for some ε > 0. Using Eq. (16) and the assumed lower bound on A, it holds that A(In(qε), y) p = AΦ(In(qε), y) Taking the limit when ε 0 and recalling that Φ(θ) = 1/r, we obtain that rθ β (rθ 1) , and it follows that rθ 1 = 1 r2θ rθ(rθ 1) . (43) On the other hand, for y = rθ and q = θ, using Eq. (16), the assumed lower bound on A, and that Φ(rθ) = rθ, we have AΦ(In(θ), y) θ = AΦ(In(θ), y) θ = Φ(rθ) + O( 1 n) θ = r + O( 1 rθ β(1 r) . Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Taking the limit for n , we obtain that 1 r = 1 r2θ rθ(1 r). (44) Finally, combining Equations (43) and (44), we deduce that β max 1 r2θ rθ(rθ 1), 1 r2θ rθ max 1 rθ 1, 1 1 r D.3. Comparison with prior smooth algorithms In (Benomar & Perchet, 2025), the authors introduce a randomized family { A ρ}ρ [0,1] of algorithms. For a fixed ρ, the maximum robustness that their algorithm can achieve is at most 1 eρ ρ θ 1/2, hence remains bounded away from θ 1/2. Given any robustness level r [θ 1, 1 eρ ρ θ 1/2], the corresponding consistency achieved by their algorithm is c = 1 eρ rθ. This algorithm ensures smoothness in expectation with respect to the error η(p , y), i.e. that E[ A ρ(p, y)] rθ βρ η(p , y) with βρ a constant proportional to 1/ρ. The major drawbacks of this approach are that 1. the achieved robustness and consistency are not Pareto-optimal, i.e. they deviate from the front defined in Eq. (1), 2. the guarantees of the algorithm only hold in expectation, since the algorithm is randomized. D.4. Probabilistic analysis Corollary D.4. The family {A1 r}r satisfies E[A1 r(P , Y )] E[P ] max r , 1 rθ β E[P η(P , Y )] Corollary D.5. The family {A1 r}r satisfies the worst-case performance ratio bound E[A1 r(P , Y )] E[P ] 1 rθ β sup π Π(F ,G) R p η(p , y)dπ(p , y) E[P ] . (46) One can observe that the bounds of Corollary D.5 represent the supremum version of the transport problem associated with W1 (see below). The supremum is expected due to the additive nature of the analysis, which makes the error term a negative (additive) correction rather than a multiplicative factor. While not a classical optimal transport problem, this supremum can be transformed into an optimal transport problem with cost (y, p ) 7 |y p | and one can recover (parts of) the standard theory from there, see e.g. (Villani, 2009). Note that the Wasserstein-p distance, for p [1, + ), denoted Wp, on the space P([1, θ]) of probability distributions4 over [1, θ] is Wp : (F , G) 7 inf π Π(F ,G) Z |p y|p dπ(p , y) . E. Additional Numerical Experiments We give here an additional experiment made with the same synthetic data described in Section 5. While the first experiment shows the performance of the algorithm as a function of the multiplicative error. Instead of fixing Emin, we set a maximum Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search 0 θ 2θ 3θ ηmax Empirical ratio ρ =0 ρ =0.5 ρ =1 Figure 6. Performance of Aρ r with ρ {0, 0.5, 1}. error level ηmax and sample y uniformly at random from the interval [p ηmax, p + ηmax]. Figure 6 presents the results in this setting. Similarly to the behaviour with respect to the multiplicative error, Figure 6 shows that ρ = 0 yields a significant performance degradation for an arbitrarily small error, which confirms the brittleness of Sun et al. (2021) s algorithm. In contrast, ρ = 1 achieves the best smoothness, having a performance that gracefully degrades with the prediction error. E.1. Experiments on real datasets We use the same experimental setting and Bitcoin data as in Section 5, but we set different values of λ {0.2, 0.8} instead of fixing λ = 0.5 as in Figure 4. This yields different robustness levels, again expressed as r = θ (1 λ/2). The results are shown in Figures 7 and 8 for λ = 0.2 and 0.8, respectively. 0.0 0.2 0.4 0.6 0.8 1.0 α [0,1] Empirical ratio ρ = 0 ρ = 1 Figure 7. Comparison of A1 r and A0 r on the Bitcoin price dataset with λ = 0.2. 0.0 0.2 0.4 0.6 0.8 1.0 α [0,1] Empirical ratio ρ = 0 ρ = 1 Figure 8. Comparison of A1 r and A0 r on the Bitcoin price dataset with λ = 0.8. For λ = 0.2, Figure 7 shows that the performances of A1 r and A0 r are similar when λ is small, i.e., when r is close to 1/θ. This corresponds to a consistency of 1, meaning that the algorithm fully trusts the prediction. Since both algorithms rely heavily on the prediction in this setting, their behaviour is naturally similar. For larger λ, as seen in Figures 4 and 8, the performance gap between the two algorithms increases. However, for λ close to 1, both consistency and robustness approach 1/rθ. While the performance of A1 r degrades significantly more slowly than that of A0 r for λ = 0.8 (Figure 8), the values of r and 1/rθ remain close. Figure 4, presented in Section 5, is an intermediate 4If [1, θ] had been unbounded, Wp would only have been defined for distributions with a a pth-moment. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search setting between these two extremes, where A1 r yields a better smoothness than A0 r, without having the values r and 1/r close to each other.