用分布预测提升滑雪租赁决策,兼顾鲁棒性与一致性。
Robust and Consistent Ski Rental with Distributional Advice
- 引入未知质量的分布预测,优化购买时机阈值
- 在高斯、几何等分布上一致性能显著优于点预测基线
- 适合需要可靠在线决策的场景,如资源调度
滑雪租赁问题是一个经典的在线决策模型,体现了重复租赁与一次性购买之间的权衡。传统算法关注最坏情况下的竞争比,而近期学习增强方法依赖点估计预测,均未能充分利用完整分布预测并保持严格鲁棒性。本文建立系统性框架,将未知质量的分布预测融入确定性和随机性算法。针对确定性情形,形式化完美分布预测下的问题,并提出高效算法计算最优阈值购买日;提供严格性能分析,识别出预测分布满足特定条件时,期望竞争比(ECR)可达经典最优随机算法边界。为应对预测不准确,提出钳制策略(Clamp Policy),通过可调参数控制购买阈值的安全范围,兼具鲁棒性与一致性:预测越准,性能越接近最优。在随机情形中,通过水灌算法(Water-Filling Algorithm)刻画停止分布,在严格满足鲁棒约束下最小化期望成本。在高斯、几何和双峰分布上的实验表明,本框架在保持可比鲁棒性的前提下,显著提升一致性表现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。