Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
This work addresses online decision problems with imperfect predictions, offering a practical Bayesian method for scenarios like resource allocation, but it is incremental as it builds on existing learning-augmented and worst-case frameworks.
The paper tackled the ski rental problem by proposing a discrete Bayesian framework that unifies worst-case and learning-augmented approaches, achieving near-optimal results with accurate priors while maintaining robust worst-case guarantees.
We revisit the classic ski rental problem through the lens of Bayesian decision-making and machine-learned predictions. While traditional algorithms minimize worst-case cost without assumptions, and recent learning-augmented approaches leverage noisy forecasts with robustness guarantees, our work unifies these perspectives. We propose a discrete Bayesian framework that maintains exact posterior distributions over the time horizon, enabling principled uncertainty quantification and seamless incorporation of expert priors. Our algorithm achieves prior-dependent competitive guarantees and gracefully interpolates between worst-case and fully-informed settings. Our extensive experimental evaluation demonstrates superior empirical performance across diverse scenarios, achieving near-optimal results under accurate priors while maintaining robust worst-case guarantees. This framework naturally extends to incorporate multiple predictions, non-uniform priors, and contextual information, highlighting the practical advantages of Bayesian reasoning in online decision problems with imperfect predictions.