Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

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 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. 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 growth in recent years, starting with the seminal works [Lykouris and 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 and El-Yaniv, 2005 ] evaluate algorithms on a single metric, the analysis of learning-augmented settings is multifaceted and must incorporate the effect of the prediction error to be meaningful. Typical desiderata [Lykouris and 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.