Robust and Consistent Ski Rental with Distributional Advice

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 introducing algorithms that systematically integrate distributional predictions 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 by significantly over existing point-prediction baselines while maintaining comparable robustness.

This paper studies a simple decision-making question: when should someone stop renting and buy instead? The classic example is ski rental, but similar trade-offs appear in cloud computing, subscriptions, and equipment leasing. Traditional methods protect against the worst case, while newer prediction-based methods often rely on a single predicted value. We instead use a full predicted distribution, which captures many possible future outcomes and their probabilities. Our algorithms use this richer information when it is reliable, but remain safe when the prediction is inaccurate or misleading. We prove performance guarantees and show experimentally that our approach can make better decisions than methods based only on a single prediction, while preserving worst-case reliability.