Online Algorithms with Uncertainty-Quantified Predictions
Bo Sun Jerry Huang Nicolas Christianson Mohammad Hajiesmaili Adam Wierman
Online algorithms with predictions have become a trending topic in the field
of beyond worst-case analysis of algorithms. These algorithms incorporate
predictions about the future to obtain performance guarantees that are of high
quality when the predictions are good, while still maintaining bounded
worst-case guarantees when predictions are arbitrarily poor. In general, the
algorithm is assumed to be unaware of the prediction's quality. However, recent
developments in the machine learning literature have studied techniques for
providing uncertainty quantification on machine-learned predictions, which
describes how certain a model is about its quality. This paper examines the
question of how to optimally utilize uncertainty-quantified predictions in the
design of online algorithms. In particular, we consider predictions augmented
with uncertainty quantification describing the likelihood of the ground truth
falling in a certain range, designing online algorithms with these
probabilistic predictions for two classic online problems: ski rental and
online search. In each case, we demonstrate that non-trivial modifications to
algorithm design are needed to fully leverage the probabilistic predictions.
Moreover, we consider how to utilize more general forms of uncertainty
quantification, proposing a framework based on online learning that learns to
exploit uncertainty quantification to make optimal decisions in multi-instance
settings.