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 works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary. In this paper, we provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.

Summary and Contributions: The paper considers the problem of designing online algorithms that utilize machine learning predictions for the ski rental and non-clairvoyant scheduling problem. In the learning augmented setup, the consistency of an algorithm is defined to be its competitive ratio given perfect predictions whereas the robustness of an algorithm is defined to be its competitive ratio when the predictions are arbitrarily erroneous. Unlike most recent work in this area, the paper focuses on providing lower bounds on the tradeoffs between robustness and consistency in this framework. In particular, they show that for the ski rental problem the learning augmented algorithms of [42] actually yield the optimum tradeoff between robustness and consistency (for both deterministic and randomized algorithms). The proofs of these lower bounds are non-trivial but not surprising.

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 works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary.