Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915144385167360 |
|---|---|
| author | Benomar, Ziyad Croissant, Lorenzo Perchet, Vianney Angelopoulos, Spyros |
| author_facet | Benomar, Ziyad Croissant, Lorenzo Perchet, Vianney Angelopoulos, Spyros |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search Benomar, Ziyad Croissant, Lorenzo Perchet, Vianney Angelopoulos, Spyros Data Structures and Algorithms Artificial Intelligence 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. |
| title | Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2502.05720 |