Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach

• URL: http://arxiv.org/abs/2512.07313v1
• Date: Mon, 08 Dec 2025 08:56:25 GMT
• Title: Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
• Abstract summary: We propose a discrete Bayesian framework that maintains exact posterior distributions over the time horizon.<n>Our algorithm achieves prior-dependent competitive guarantees and gracefully interpolates between worst-case and fully-informed settings.<n>This framework naturally extends to incorporate multiple predictions, non-uniform priors, and contextual information.
• Score: 4.702729080310267
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Smart predict-then-robustly-optimize [0.5161531917413708]
  We propose and study a robust variant of the smart predict-then-optimize approach.<n>Our framework consistently yields significant performance improvements over standard methods.
  arXiv  Detail & Related papers  (2026-07-23T19:37:17Z)
• Possibilistic Predictive Uncertainty for Deep Learning [75.00607359322863]
  We introduce Dirichlet-approximated possibilistic posterior predictions (DAPPr)<n>DAPPr is a principled framework leveraging possibility theory.<n>This projection-and-approximation strategy yields a simple training objective with closed-form solutions.
  arXiv  Detail & Related papers  (2026-05-01T12:14:01Z)
• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  The ski rental problem is a canonical model for online decision-making under uncertainty.<n>We propose a framework that integrates distributional advice of unknown quality into both deterministic and randomized algorithms.<n>We show that our framework improves consistency significantly over existing point-prediction baselines while maintaining comparable robustness.
  arXiv  Detail & Related papers  (2026-03-31T04:04:21Z)
• Optimal Decision-Making Based on Prediction Sets [18.860889057545467]
  Prediction sets can wrap around any ML model to cover unknown test outcomes with a guaranteed probability.<n>We propose a decision-theoretic framework that seeks to minimize the expected loss (risk) against a worst-case distribution consistent with the prediction set's coverage guarantee.
  arXiv  Detail & Related papers  (2026-02-01T03:02:44Z)
• Forests of Uncertaint(r)ees: Using tree-based ensembles to estimate probability distributions of future conflict [0.0]
  We develop a strategy to quantify uncertainty in conflict forecasting, shifting from traditional point predictions to full predictive distributions.<n>Models are able to consistently outperform a suite of benchmarks derived from conflict history in predictions up to one year in advance.<n>We emphasize the need to understand how a metric behaves for a given prediction problem, in our case characterized by extremely high zero-inflatedness.
  arXiv  Detail & Related papers  (2025-12-05T23:10:16Z)
• Bridging the Gap Between Bayesian Deep Learning and Ensemble Weather Forecasts [100.26854618129039]
  Weather forecasting is fundamentally challenged by the chaotic nature of the atmosphere.<n>Recent advances in Bayesian Deep Learning (BDL) offer a promising but often disconnected alternative.<n>We bridge these paradigms through a unified hybrid BDL framework for ensemble weather forecasting.
  arXiv  Detail & Related papers  (2025-11-18T07:49:52Z)
• When Robustness Meets Conservativeness: Conformalized Uncertainty Calibration for Balanced Decision Making [8.234618636958462]
  We propose a new framework that provides distribution-free, finite-sample guarantees on miscoverage and regret.<n>Our method constructs valid estimators that trace out the mis-regret frontier.<n>These results offer the first principled data-driven methodology for guiding robustness selection.
  arXiv  Detail & Related papers  (2025-10-09T03:38:17Z)
• Bin-Conditional Conformal Prediction of Fatalities from Armed Conflict [0.5312303275762104]
  We introduce bin-conditional conformal prediction (BCCP), which enhances standard conformal prediction by ensuring consistent coverage rates across user-defined subsets.<n>Compared to standard conformal prediction, BCCP offers improved local coverage, though this comes at the cost of slightly wider prediction intervals.
  arXiv  Detail & Related papers  (2024-10-18T14:41:42Z)
• Calibrated Probabilistic Forecasts for Arbitrary Sequences [58.54729945445505]
  Real-world data streams can change unpredictably due to distribution shifts, feedback loops and adversarial actors.<n>We present a forecasting framework ensuring valid uncertainty estimates regardless of how data evolves.
  arXiv  Detail & Related papers  (2024-09-27T21:46:42Z)
• Efficient Training of Probabilistic Neural Networks for Survival Analysis [0.6437284704257459]
  Variational Inference (VI) is a commonly used technique for approximate Bayesian inference and uncertainty estimation in deep learning models. It comes at a computational cost, as it doubles the number of trainable parameters to represent uncertainty. We investigate how to train deep probabilistic survival models in large datasets without introducing additional overhead in model complexity.
  arXiv  Detail & Related papers  (2024-04-09T16:10:39Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Calibrating Neural Simulation-Based Inference with Differentiable Coverage Probability [50.44439018155837]
  We propose to include a calibration term directly into the training objective of the neural model. By introducing a relaxation of the classical formulation of calibration error we enable end-to-end backpropagation. It is directly applicable to existing computational pipelines allowing reliable black-box posterior inference.
  arXiv  Detail & Related papers  (2023-10-20T10:20:45Z)
• Rockafellian Relaxation and Stochastic Optimization under Perturbations [0.056247917037481096]
  We develop an optimistic" framework based on Rockafellian relaxations in which optimization is conducted not only over the original decision space but also jointly with a choice of model. The framework centers on the novel concepts of exact and limit-exact Rockafellians, with interpretations of negative'' regularization emerging in certain settings.
  arXiv  Detail & Related papers  (2022-04-10T20:02:41Z)
• Private Prediction Sets [72.75711776601973]
  Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. We evaluate the method on large-scale computer vision datasets.
  arXiv  Detail & Related papers  (2021-02-11T18:59:11Z)
• Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks [65.24701908364383]
  We show that a sufficient condition for a uncertainty on a ReLU network is "to be a bit Bayesian calibrated" We further validate these findings empirically via various standard experiments using common deep ReLU networks and Laplace approximations.
  arXiv  Detail & Related papers  (2020-02-24T08:52:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.