Robust and Consistent Ski Rental with Distributional Advice

• URL: http://arxiv.org/abs/2603.29233v1
• Date: Tue, 31 Mar 2026 04:04:21 GMT
• Title: Robust and Consistent Ski Rental with Distributional Advice
• Abstract summary: 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.
• Score: 13.811651343801579
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

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)
• Prediction Sets for Counterfactual Decisions: Coverage, Optimality, and Conformal Prediction [7.899668963928307]
  We develop a decision-theoretic framework for uncertainty-informed counterfactual decisions.<n>We identify a novel notion of emphpolicy-coupled coverage -- namely, coverage of the realized outcome under the action induced by the prediction sets themselves.
  arXiv  Detail & Related papers  (2026-07-02T14:13:08Z)
• Deadline-Aware Online Scheduling for LLM Fine-Tuning with Spot Market Predictions [11.849924812127371]
  We show the power of prediction in enabling cost-efficient scheduling and its sensitivity to estimation errors.<n>We propose an online allocation algorithm with prediction based on the committed horizon control approach.<n>An online policy selection algorithm is developed that learns the best policy from a pool constructed by varying the parameters of both algorithms.
  arXiv  Detail & Related papers  (2025-12-24T05:47:27Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach [4.702729080310267]
  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.
  arXiv  Detail & Related papers  (2025-12-08T08:56:25Z)
• Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints [9.77322868877488]
  We introduce a framework for distributionally robust optimal regularization.<n>We show how the resulting robust regularizers interpolate between computation of the training distribution and uniform priors.
  arXiv  Detail & Related papers  (2025-10-03T19:35:38Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions.<n>We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance.<n>Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• 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)
• Conformal Contextual Robust Optimization [21.2737854880866]
  Data-driven approaches to predict probabilistic decision-making problems seek to mitigate the risk of uncertainty region mis robustness in safety-critical settings. We propose a Conformal-Then-Predict (CPO) framework for. probability-then-optimize decision-making problems.
  arXiv  Detail & Related papers  (2023-10-16T01:58:27Z)
• CovarianceNet: Conditional Generative Model for Correct Covariance Prediction in Human Motion Prediction [71.31516599226606]
  We present a new method to correctly predict the uncertainty associated with the predicted distribution of future trajectories. Our approach, CovariaceNet, is based on a Conditional Generative Model with Gaussian latent variables.
  arXiv  Detail & Related papers  (2021-09-07T09:38:24Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)

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.