The Many Shapes of Advice in Online Algorithms

Abstract

Learning-augmented algorithms combine classical online algorithms with predictions supplied by machine learning models. They aim to exploit accurate predictor forecasts while retaining worst-case guarantees when predictions are wrong. Most foundational literature assumes a black-box point prediction model, in which the algorithm receives a single predicted value and its competitive ratio is analyzed as a function of some global error η. This model is broadly applicable but obscures important structure about the predictor. This thesis surveys and extends the growing body of work on learning-augmented algorithms with nonstandard prediction models. We organize the literature into various families and trace how each axis changes the algorithmic questions being asked, from what a prediction conveys in the first place to how predictions are interpreted and evaluated. We then contribute new theoretical and experimental results for ε-accurate paging. On the theoretical side, we study an adaptive-request variant and show that the achievable competitive ratio is Θ(min{k,1/ε}). Experimentally, we compare two policies BlindOracle and TwoStrikes-LRU across various prediction regimes, illustrating the tradeoffs between immediate trust and strike-based filtering.