Ski Rental with Distributional Predictions of Unknown Quality

We revisit the central online problem of *ski rental* in the "algorithms with predictions" framework from the point of view of *distributional* predictions. If we are given as a prediction a *distribution* $\hat p$ over the ski days, and the true number of ski days comes from some (unknown) distribution $p$, then we show as our main result that there is an algorithm with expected cost at most $OPT + O\left(\min \left(\max(\eta,1) \cdot \sqrt{b},\ b \log b \right) \right)$, where $OPT$ is the expected cost of the optimal policy for the true distribution $p$, $b$ is the cost of buying, and $\eta$ is the Earth Mover's (Wasserstein-1) distance between $p$ and $\hat p$. An implication of this bound is that our algorithm has *consistency* $O(\sqrt{b})$ (additive loss when the prediction error is $0$) and *robustness* $O(b \log b)$ (additive loss when the prediction error is arbitrarily large). Moreover, we do not need to assume that we know (or have any bound on) the prediction error $\eta$, in contrast with previous work in robust optimization which assumes that we know this error. We also complement this upper bound with a variety of lower bounds showing that it is essentially tight: not only can the consistency/robustness tradeoff not be improved, but our particular loss function cannot be meaningfully improved.

Suppose you go skiing for the winter. Every day, you face a choice: rent skis for a small daily fee, or buy them for a large upfront cost. If you buy, you never pay again. Since buying is more expensive than renting, you would like to buy at the beginning of the season if you will ski many days, but rent every day if you will not ski many days. The catch is that you do not know how many ski days you will get. This is a classical online decision problem known as "ski rental", which models and exemplifies a common "rent-or-buy" question which arises in many important online decision-making scenarios (e.g., renting or buying infrastructure or equipment). Due to its combination of importance and simplicity it has been studied for over 40 years. We consider a variant of this problem which has "predictions": what if the true number of ski days is drawn from an unknown distribution, but we are given a "predicted" distribution (possibly based on past data)? If our prediction is highly accurate then we want our algorithmic performance to be nearly optimal, but if the prediction is wildly incorrect then we still need a guarantee that our costs won't be arbitrarily bad. We design new algorithms which we prove achieve the best of both worlds: smoothly degrading performance as prediction error increases, but also robust guarantees in the worst case.