Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Ziyad Benomar * CREST, ENSAE, Ecole Polytechnique, Fairplay joint team, Palaiseau, France Vianney Perchet CREST, ENSAE, Criteo AI LAB Fairplay joint team, Paris, France and Lorenzo Croissant CREST, ENSAE Fairplay joint team, Palaiseau, France Spyros Angelopoulos CNRS and International Laboratory on · 2025
Read Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search by Ziyad Benomar * CREST, ENSAE, Ecole Polytechnique, Fairplay joint team, Palaiseau, France Vianney Perchet CREST, ENSAE, Criteo AI LAB Fairplay joint team, Paris, France and Lorenzo Croissant CREST, ENSAE Fairplay joint team, Palaiseau, France Spyros Angelopoulos CNRS and International Laboratory on (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05720.txt.
Description
Benomar and co-authors (2025) close a gap in the theory of a classic trading problem. In one-max search, a trader watches prices arrive one by one and must accept exactly one, for good, trying to land the highest. Modern versions give the trader a prediction of what is coming. Good algorithms should do well when the prediction is right, stay safe when it is wrong, and shift smoothly between the two. Earlier methods could not manage all three at their best.
The authors present the first algorithm that hits the optimal trade-off between consistency and robustness while varying smoothly as prediction error grows. They then extend the analysis to settings where both the prices and the prediction carry randomness. The work rounds out the learning-augmented theory of the problem.
Catalog record
| CREATOR | Ziyad Benomar * CREST, ENSAE, Ecole Polytechnique, Fairplay joint team, Palaiseau, France Vianney Perchet CREST, ENSAE, Criteo AI LAB Fairplay joint team, Paris, France and Lorenzo Croissant CREST, ENSAE Fairplay joint team, Palaiseau, France Spyros Angelopoulos CNRS and International Laboratory on |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-05720