Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms

We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust, meaning that the algorithm performs well when predictions are accurate and maintains worst-case guarantees. Such algorithms have been studied in a recent line of work initiated by Lykouris and V assilvit-skii (ICML '18) and Kumar, Purohit and Svitkina (NeurIPS '18).