Algorithms with predictions (also called learningâaugmented or predictionâaugmented algorithms) augment classical algorithmic procedures with side information about the future, which could be predictions produced by ML models, domain experts, or simple heuristics. The basic philosophy is pragmatic: predictions are available in many real systems (forecasted demand, estimated user behavior, model outputs used by human operators), and algorithms that can use these signals profit from improved average performance while still providing safeguards against bad forecasts.
While this problem is primarily studied in the computer science algorithms community, it should interest learning theorists and statisticians, especially those interested in the interface between learning and decision-making. Indeed, informing traditional decision-making is the main way statistical learning is applied in practice. Whether our concern (as an accademic community) is the quality of decision making by policymakers or how to correctly train students to use ML models, it is crucial to expand our understanding of this aspect of decision-making under uncertainty.
What are the core problems?
Of course, aspects of algorithm design for specific problems are not within the scope of statistical learning theory. However, several conceptual and technical questions arise naturally at the intersection of learning and decision-making that should interest learning theorists. These stem from the key properties that learning-augmented algorithms aim to achieve:
Consistency: when predictions are accurate (or calibrated), a good algorithm should (almost) match the performance of an ideal clairvoyant method (fast, high performance, low regret, etc.).
Robustness: when predictions are catastrophically wrong (worst-case), the algorithm should not be much worse than the classical worstâcase algorithms' guarantees.
Smoothness: in between these two extremes, an algorithm's performance should degrade smoothly: small prediction error should cause only small performance loss. Smoothness is a necessary condition for actual deployability, as real predictors will never be perfect.
Naturally, each criterion individually is trivial to optimise: always trust the predictor (perfect consistency) or always ignore it (perfect robustness, and smoothness). The challenge is in the multi-objective problem. The opposition between consistency and robustness for example, is quite self-evident: the heart of the question is in characterising, for a given problem, the shape of the Pareto frontier of achievable trade-offs. Most early work focused only on achieving consistency and robustness, with smoothness being a more recent (but already widely accepted) goal.
Further reading and a curated overview are available at the Algorithms with Predictions initiative website.
Example: The one-max-search problem
As an illustration of the concepts of algorithms with predictions, this section sumarises the contents of on the problem of one-max-search.
The one-max-search problem is a simple online decision problem, but despite its simplicity the prediction augmented problem is already very rich in challenges. One-max-search is an optimal stopping problem generally presented as an optimal execution problem: we have a single asset to sell over a time horizon of $T$ periods, and at each period $t\in[T]$ we observe a price $X_t$ which we can either accept or forfeit to move to $t+1$.
This problem is very similar to the Prophet and Secretary problems, so to clear up any confusion, letâs contrast these optimal stopping problems before moving on. A Prophet problem is characterised by the independent between the prices $X_t$. A Secretary problem is characterised by the randomisation of arrival order of the prices $X_t$, which are otherwise adversarially chosen. In contrast, the prices in one-max-search are adversarially chosen, including their order of arrival. Still, these problems are analysed by similar techniques, including the competitive ratio of an algorithm, defined as the worst-case ratio between the algorithmâs performance and that of a clairvoyant (a.k.a. offline) planner who knows all prices in advanceNote that the expectation may be outside the ratio in some analyses, see e.g. ,, and references therein. This is a design choice. \(\begin{align} \text{CR} = \inf_{X_1,\ldots,X_T} \frac{\mathbb{E}[\text{ALG}(X_1,\ldots,X_T)]}{\mathbb{E}[\text{OPT}(X_1,\ldots,X_T)]}. \end{align}\)
The notations $\text{ALG}(X_1,\ldots,X_T)$ and $\text{OPT}(X_1,\ldots,X_T)$ are left intentionally vague in this literature to emphasise that the competitive ratio is a very general concept that can be applied to many different problems and performance metrics (e.g., the value $X_t$ chosen for prophets and one-max-search, vs. the probability of selecting the maximum value in secretary problems). Due to independence, the optimal competitive ratio for Prophet problems is $1/2$, see , while for Secretary problems it is $1/e$, see . In one-max-search, one must assume that the prices are bounded in $[1,\theta]$ for some $\theta>1$ to get non-trivial guarantees, and the optimal competitive ratio is $\theta^{-1/2}$, see .
What about predictions? How much can they improve this $\theta^{-1/2}$ ratio? The robust algorithm of El-Yaniv, in , buys the first price above $\sqrt{\theta}$, and gives us a bound on the robustness achievable. At the other end, given a prediction $Y$ of the maximum price $\max_{t\in[T]} X_t$, a consistent algorithm sets its threhold price at $Y$, achieving a consistency of $1$. In between, Sun et al. already gave, in , the Pareto frontier of achievable trade-offs between consistency and robustness. I will spare you the equations for the front, which arenât very enlightening.
However, the algorithm of Sun et al. is not smooth: a small error in the prediction $Y$ can cause a large drop in performance. In order to obtain smoothness, my coauthors and I (chiefly Ziyad Benomar) reanalysed the Pareto front to characterise all smooth threshold algorithms through the geometry of the set of Pareto-optimal threshold functions. This formalism allowed us to then study the smoothness of these functions to derive competitive ratio bounds in terms of the prediction error \(\begin{align} \Ec(Y,X^*):= \min\left\{\frac Y{X^*}, \frac{X^*}{Y}\right\}, \end{align}\)
where \(X^*:=\max_{t\in[T]} X_t\) is the maximum price. Precisely, we show that the competitive ratio degrades as a power of the prediction error $\Ec(Y,X^*)$ which relates directly to the smoothness of the algorithm. Finding the optimal smoothness can then be characterised through a triple consistency-robustness-smoothness Pareto front.
I will leave technical details to the paper, the instructive conclusions in my view are that:
answering the multi-objective problem of consistency, robustness, and smoothness is quite difficult even on simple problems,
that, instead of searching for a single optimal algorithm, a keener understanding of the problem's constraints and geometry is needed to conclusively answer the trade-offs,
and that, while the high-level ideas transfer well, the nitty-gritty of analysis is ad-hoc and problem dependent and it's not clear if a general form akin to dynamic programming can be found.
Open questions for learning theorists
This leaves us with an awkward feeling: the problem of algorithms with predictions is cool, challenging, and highly relevant for practical applications, but its ungeneralisability leaves an unpleasant aftertaste. Perhaps a new perspective is needed, and learning theorists and statisticians are well equiped to provide it. In my view, there are several conceptual and technical questions that are particularly natural for learning theorists and statisticians.
Bridging prediction error and generalisation guarantees. In algorithms with predictions, analysis is generally worst-case and purely deterministic: the predictor is just some scalar. In contrast, learning theory has cut its teeth on stochastic generalisation frameworks. Can we bring these together to obtain meaningful performance guarantees?
From static predictions to control and dynamic programming. Many decision problems are inherently sequential and can be solved via the general dynamic programming principle. The generality of this framework is a huge achievement and a powerful tool. Can we find an analogue general decision framework for algorithms with predictions? In the context of control, this has been studied a bitSee, e.g., papers on lookahead in control and reinforcement learning such as and ., but a general theory is still missing.
Classifying brittleness and stability of problems. There's an interesting question going around in the community: which problems are inherently brittle, i.e., for which no algorithm can be both robust and consistent, while being smooth? See for example for a recent example. On the one hand, classifying problems into brittle and stable families is an interesting theoretical question, but perhaps one ill suited to statistics. But, on the other hand, us learning theorists should probably be considering the consequences of this brittleness when predicting information for decision-making problems.
Distributional predictions. On many problems, point predictions are not the most natural output of a predictor. One would be better served by a prediction about the whole distribution of a key variable, such as $X^*$ in one-max-search. There is a strong demand for the study of this problem from computer scientists, who often find their tools inadequate for the task. There's strong potential for statisticians and applied mathematicials to contribute here. One might hasard to guess conections to questions of calibration in learning theory
This area is still new and emerging, but already very active. If you are interested in any of the above questions, feel free to reach out, I can put you in contact with other researchers in the area. If you want to learn more about algorithms with predictions, I highly recomend the curated Algorithms with Predictions initiative website, every research field should have one!