Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions

Abstract

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.

References in corpus (2)

• Improving Online Algorithms via ML Predictions
• Revenue Optimization with Approximate Bid Predictions

Cited by in corpus (5)

• The Primal-Dual method for Learning Augmented Algorithms
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• Learning Augmented Energy Minimization via Speed Scaling
• Learning-Assisted Competitive Algorithms for Peak-Aware Energy Scheduling
• Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice