Ski Rental with Distributional Predictions of Unknown Quality

Abstract

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.