Search papers, labs, and topics across Lattice.
This paper studies the online ski rental problem using distributional predictions, where the prediction is a distribution over the number of ski days. They design an algorithm whose expected cost is bounded by OPT + O(min(max({eta}, 1) * sqrt(b), b log b)), where OPT is the optimal expected cost, b is the buying cost, and {eta} is the Wasserstein-1 distance between the predicted and true distributions. The algorithm achieves consistency of O(sqrt(b)) and robustness of O(b log b) without needing to know the prediction error, and the authors prove that these bounds are essentially tight.
Even with arbitrarily inaccurate predictions about ski rental demand, this algorithm guarantees only O(b log b) additive loss compared to the optimal strategy.
We revisit the central online problem of ski rental in the "algorithms with predictions" framework from the point of view of distributional predictions. Ski rental was one of the first problems to be studied with predictions, where a natural prediction is simply the number of ski days. But it is both more natural and potentially more powerful to think of a prediction as a distribution p-hat over the ski days. If the true number of ski days is drawn from some true (but unknown) distribution p, then we show as our main result that there is an algorithm with expected cost at most OPT + O(min(max({eta}, 1) * sqrt(b), b log b)), 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 p-hat. Note that when {eta} < o(sqrt(b)) this gives additive loss less than b (the trivial bound), and when {eta} is arbitrarily large (corresponding to an extremely inaccurate prediction) we still do not pay more than O(b log b) additive loss. An implication of these bounds 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 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.
