cs.LGMar 31, 2026

Robust and Consistent Ski Rental with Distributional Advice

Authors: Jihwan Kim, Chenglin Fan

Organizations: Seoul National University, Seoul 08826, South Korea.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The ski rental problem is a canonical model for online decision-making under uncertainty, capturing the fundamental trade-off between repeated rental costs and a one-time purchase. While classical algorithms focus on worst-case competitive ratios and recent "learning-augmented" methods leverage point-estimate predictions, neither approach fully exploits the richness of full distributional predictions while maintaining rigorous robustness guarantees. We address this gap by establishing a systematic framework that integrates distributional advice of unknown quality into both deterministic and randomized algorithms. For the deterministic setting, we formalize the problem under perfect distributional prediction and derive an efficient algorithm to compute the optimal threshold-buy day. We provide a rigorous performance analysis, identifying sufficient conditions on the predicted distribution under which the expected competitive ratio (ECR) matches the classic optimal randomized bound. To handle imperfect predictions, we propose the Clamp Policy, which restricts the buying threshold to a safe range controlled by a tunable parameter. We show that this policy is both robust, maintaining good performance even with large prediction errors, and consistent, approaching the optimal performance as predictions become accurate. For the randomized setting, we characterize the stopping distribution via a Water-Filling Algorithm, which optimizes expected cost while strictly satisfying robustness constraints. Experimental results across diverse distributions (Gaussian, geometric, and bi-modal) demonstrate that our framework improves consistency significantly over existing point-prediction baselines while maintaining comparable robustness.

Figures & tables

tt∑d<tp(d) d\sum_{d<t}p(d)\,d∑d≥tp(d)\sum_{d\geq t}p(d)b+t−1b+t-1f(t)f(t)
101.033.0
20.8⋅1=0.80.8\cdot 1=0.80.241.6
30.8⋅1=0.80.8\cdot 1=0.80.251.8
40.8⋅1=0.80.8\cdot 1=0.80.262.0
50.8⋅1=0.80.8\cdot 1=0.80.272.2
≥6\geq 60.8⋅1+0.2⋅5=1.80.8\cdot 1+0.2\cdot 5=1.80—1.8
Table 1: Example computation of f(t)f(t) for discrete distribution.
 ei=min⁡{⌊h−biai⌋,di+1,b}.e_{i}=\min\left\{\left\lfloor\frac{h-b_{i}}{a_{i}}\right\rfloor,d_{i+1},b\right\}. 
Algorithm 2 Water-Filling for Randomized Robust Ski Rental
pp familyOursPurohit (maj)Purohit (mix)
unif1001.16121.17821.1866
unif2001.33311.34921.3643
gauss1.33751.41951.4169
geom1.28791.41141.4183
twopoint1.04151.24481.2547
Table 2: Consistency comparison (smaller is better) at (b,R)=(50,1.7)(b,R)=(50,1.7) .
Figure 1: Consistency under prediction error. The x-axis is the Wasserstein perturbation budget η\eta used to generate p^\widehat{p} from the true pp ; policies are computed from p^\widehat{p} , but the consistency is evaluated under pp . The plot reports the mean over 2525 random transports per η\eta .
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

 e=min⁡{⌊h−bkak⌋, dk+1, b}.e=\min\left\{\left\lfloor\frac{h-b_{k}}{a_{k}}\right\rfloor,\ d_{k+1},\ b\right\}. 
Appendix
Algorithm 3 Water-Filling for Randomized Robust Ski Rental
More in this topic

Learning-Augmented Algorithms

Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.

See all 54 papers

Explore similar work

CardsList
Feb 24, 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. 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.

Qiming Cui, Michael Dinitz

Johns Hopkins University, Baltimore, MD USA

Learning-Augmented Algorithms
AskPDF
Aug 27, 2026

Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

Learning-augmented algorithms improve online decisions using predictions, but unreliable advice may harm efficiency and fairness. We study an online allocation problem with finite candidate sets, irreversible decisions, and exposure constraints. We propose a robust and fair rule combining advice with a conservative fallback and fairness correction. Under bounded-error assumptions, we prove consistency and robustness with loss proportional to prediction error. Experiments show stability under adversarial advice and significant reductions in exposure disparity.

Fredy Pokou

MRE, CRIStAL · Inria, University of Lille, CNRS, Centrale Lille Villeneuve-d’Ascq, France

Online Resource AllocationLearning-Augmented AlgorithmsFair Resource AllocationAlgorithmic FairnessDistribution Shift Robustness
AskPDF
Oct 27, 2026

Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff

We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency under finite strict robustness is d=(3+5)/2d=(3+\sqrt5)/2 when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above dd at every robustness budget below 4φ+3≈9.4724\varphi+3\approx9.472, whereas our deterministic algorithm attains dd with exact robustness φ5≈11.090\varphi^5\approx11.090, where φ=(1+5)/2\varphi=(1+\sqrt5)/2. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. A tunable replacement cost gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including (C,R)=(25/9,10)(C,R)=(25/9,10) and (4,7)(4,7). Randomization permits expected consistency approaching one with finite expected robustness, whereas almost-sure robustness forces expected consistency strictly above two at every finite budget.

Zhong Han

Department of Biomedical Engineering, College of Design and Engineering, National University of Singapore.

Sequential Decision Making
AskPDF