Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
  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.
