Skip to content
conftrace_
2026 ICML ICML 2026

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.

More from ICML 2026

All ICML 2026 papers →