Parsimonious advice and tradeoffs in learning-augmented algorithms

Overview & Synopsis

This thesis explores several fundamental questions in the area of learning-augmented algorithms, a paradigm where the decision-maker must operate under uncertainty while being provided with potentially inaccurate predictions about unknown parameters of the decision problem. The central challenge lies in the absence of any guarantees on the quality of these predictions. The goal is to design algorithms that can effectively leverage accurate predictions to improve performance, while remaining robust and competitive when predictions are unreliable.The thesis is structured in two main parts, each addressing distinct facets of this challenge.The first part focuses on scenarios where access to predictions is limited, either due to costs, budget constraints, or partial availability. This restriction necessitates a careful and strategic use of advice. By analyzing classical online problems such as ski rental, secretary selection, job scheduling, and the design of priority queues, this part demonstrates how limited advice can still yield strong performance guarantees. Even when only a subset of predictions is available, the algorithms developed exhibit competitive behavior that interpolates between purely online and offline solutions.The second part examines the fundamental tradeoffs in the design of learning-augmented algorithms. Specifically, it focuses on balancing three key performance criteria: consistency (strong performance when predictions are accurate), robustness (resilience to poor predictions), and smoothness (graceful degradation as prediction quality varies). This part introduces improved algorithms for classical problems such as one-max search and non-clairvoyant scheduling, overcoming weaknesses encountered in prior works on these problems.