On Tradeoffs in Learning-Augmented Algorithms

Many decision-making problems under uncertainty are commonly studied using competitive analysis. In this context, the performance of online algorithms, operating under uncertainty, is compared to that of the optimal offline algorithm, which has full knowledge of the problem instance. While competitive analysis provides a rigorous method for evaluating online algorithms, it is often overly pessimistic. In real-world scenarios, decision-makers can have some prior knowledge, though possibly imperfect, about the complete problem instance. For example, predictions of unknown variables might be obtained via machine learning models, or an expert might provide advice on the best course of action. This more realistic setting was formalized by Lykouris and Vassilvtiskii [2018] and Purohit et al. [2018] leading to the development of what is now known as learning-augmented algorithms. In this paradigm, the algorithm receives predictions about the current problem instance, but without any guarantees on their accuracy, and must satisfy three main properties: Consistency: perform almost as well as the optimal offline algorithm if the predictions are perfect. Robustness: maintain a performance level close to the worst-case scenario without predictions when the predictions are arbitrarily bad.