Online Algorithms with Uncertainty-Quantified Predictions
This work addresses the challenge of enhancing online algorithm performance for decision-makers by incorporating uncertainty information from machine learning predictions, representing an incremental advance in the algorithms-with-predictions field.
The paper tackles the problem of designing online algorithms that can optimally use uncertainty-quantified (UQ) predictions to improve performance, focusing on classic problems like ski rental and online search, and shows that non-trivial algorithm modifications are needed to leverage UQ effectively.
The burgeoning field of algorithms with predictions studies the problem of using possibly imperfect machine learning predictions to improve online algorithm performance. While nearly all existing algorithms in this framework make no assumptions on prediction quality, a number of methods providing uncertainty quantification (UQ) on machine learning models have been developed in recent years, which could enable additional information about prediction quality at decision time. In this work, we investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ describing the likelihood of the ground truth falling within a particular range of values. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions. Moreover, we consider how to utilize more general forms of UQ, proposing an online learning framework that learns to exploit UQ to make decisions in multi-instance settings.