Ski Rental with Distributional Predictions of Unknown Quality

Qiming Cui, Michael Dinitz
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:21805-21828, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-cui26a, title = {Ski Rental with Distributional Predictions of Unknown Quality}, author = {Cui, Qiming and Dinitz, Michael}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {21805--21828}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/cui26a/cui26a.pdf}, url = {https://proceedings.mlr.press/v306/cui26a.html}, 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.} }
Endnote
%0 Conference Paper %T Ski Rental with Distributional Predictions of Unknown Quality %A Qiming Cui %A Michael Dinitz %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-cui26a %I PMLR %P 21805--21828 %U https://proceedings.mlr.press/v306/cui26a.html %V 306 %X 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.
APA
Cui, Q. & Dinitz, M.. (2026). Ski Rental with Distributional Predictions of Unknown Quality. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:21805-21828 Available from https://proceedings.mlr.press/v306/cui26a.html.

Related Material