Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
This work addresses online algorithm optimization for resource allocation with machine learning predictions, representing an incremental improvement in combining classic problems with predictive models.
The paper tackles the Ski Rental problem by incorporating soft machine-learned predictions to estimate the probability of ski-days, resulting in the derivation of optimal randomized algorithms that minimize the worst-case expected competitive ratio.
We consider a variant of the classic Ski Rental online algorithm with applications to machine learning. In our variant, we allow the skier access to a black-box machine-learning algorithm that provides an estimate of the probability that there will be at most a threshold number of ski-days. We derive a class of optimal randomized algorithms to determine the strategy that minimizes the worst-case expected competitive ratio for the skier given a prediction from the machine learning algorithm,and analyze the performance and robustness of these algorithms.