Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
This work addresses a gap in online decision-making for traders, providing a more robust and adaptable solution, though it is incremental as it builds on existing learning-augmented frameworks.
The paper tackles the problem of achieving optimal trade-offs between consistency and robustness in learning-augmented one-max search, presenting the first algorithm that simultaneously attains smoothness and optimal worst-case guarantees, and extends this to stochastic settings with randomness in prices and predictions.
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.