Description

This project aims to establish the theory and to design and study algorithms for decision-making processes that integrate AI-generated predictions into classical algorithms, ensuring they are more powerful when predictions are accurate and provably reliable when predictions are poor. Rather than motivating this by revisiting the limitations of end-to-end AI systems (as outlined before), we focus on what this integration requires in practice and how we will evaluate success.

From this perspective, the objective is to develop and analyse learning and to leverage stochastic structures in this setting, as showed possible by early works

Skills required

Prophet Inequality

Bibliography

[VP1] Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. Pareto-optimality, smooth-
ness, and stochasticity in learning-augmented one-max-search. In ICML 2025-42nd International Conference
on Machine Learning, 2025.
[VP2] Ziyad Benomar and Vianney Perchet. On tradeoffs in learning-augmented algorithms. arXiv preprint
arXiv:2501.12770, 2025.
[VP3] Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. On
preemption and learning in stochastic scheduling. In International Conference on Machine Learning, pages
24478–24516. PMLR, 2023.
[VP4] Nathan Noiry, Vianney Perchet, and Flore Sentenac. Online matching in sparse random graphs: Non-
asymptotic performances of greedy algorithm. Advances in Neural Information Processing Systems,
34:21400–21412, 2021.
[VP5] Flore Sentenac, Nathan Noiry, Matthieu Lerasle, Laurent M´ enard, and Vian

Keywords

Lerarning, Prophet Inequality