This paper introduces a Bayesian framework for the ski rental problem, integrating machine-learned predictions with principled uncertainty quantification. The core idea is to maintain an exact posterior distribution over the unknown time horizon, updating it daily based on observed survival, and making decisions based on expected utility rather than point forecasts. The main empirical claim is that this approach achieves superior empirical performance across diverse scenarios, including noisy or adversarial conditions, yielding near-optimal results under accurate priors while maintaining robust worst-case guarantees.
Problem
The paper addresses several bottlenecks in existing ski rental problem solutions:
Traditional algorithms minimize worst-case cost without leveraging prior information: Classical algorithms for the ski rental problem, such as deterministic strategies with a competitive ratio of 2 or randomized strategies with a ratio of approximately 1.582, provide worst-case guarantees but fail to utilize any structure or prior information about the underlying demand.
Existing learning-augmented approaches rely on brittle point estimates or heuristics: Recent learning-augmented algorithms integrate machine-learned predictions but often depend on point estimates, regime heuristics, or hand-crafted thresholds. These methods are described as brittle in the face of prediction noise and difficult to analyze rigorously.
Lack of principled uncertainty quantification: Current approaches often do not provide a principled mechanism for incorporating prior knowledge, whether empirical, structured, or even adversarially incorrect, nor do they offer robust analysis in the face of prediction noise.
Key Contributions
Introduction of the first learning-augmented ski rental algorithm based on exact discrete Bayesian inference, eliminating the need for point estimates or regime switching.
Establishment of theoretical guarantees on competitive ratio and regret under classical priors, demonstrating robustness to prior misspecification.
Extensive experiments on synthetic and real-world priors confirming consistent outperformance over deterministic, randomized, and prediction-based baselines, even under noisy or adversarial conditions.
Development of a modular and extensible Bayesian formulation that supports multiple priors, structured uncertainty, and continuous-time variants, and adapts to multi-modal priors via decisions informed by mode weights and positions.
Method
The proposed method is a discrete Bayesian framework for the ski rental problem. It operates by making a daily decision to either rent for the day or buy the item outright.
Method Flow:
Initialization: The algorithm starts with a known buy cost b > 1, a finite horizon bound M, and a prior mass function πκ = Pr[T = k] for k = 1,..., M, representing the probability of the unknown season length T.
Daily Update: On each day t, the algorithm updates its posterior distribution over the unknown time horizon T, conditioned on survival (T ≥ t). The posterior probability for T = k given T ≥ t is calculated as:
Pr(T = k | T ≥ t) = πκ / (Σj=t^M πj) for k ≥ t.
Expected Rental Cost Calculation: The algorithm then computes the expected remaining rental cost, Erent(t), if it continues to rent from day t onward. This is defined as:
Erent(t) = Σk=t^M Pr[T = k | T ≥ t] · (k - t + 1).
Decision Rule: The algorithm compares the known one-time buy cost b with the calculated expected remaining rental cost Erent(t).
If b < Erent(t), the algorithm decides to buy the item on day t.
Otherwise, it decides to rent for day t and proceeds to day t + 1, reassessing daily.
Termination: This process continues until a purchase is made or the horizon M is reached without a purchase.
This fully Bayesian strategy quantifies uncertainty, makes decisions by expected-utility maximization, and seamlessly integrates prior information.
Technical Details
Horizon: The unknown season length T ∈ {1,..., M} is assumed to be bounded by a known M.
Costs: The per-day rental cost is normalized to 1, and the one-time buy cost b > 1.
Prior Distribution: A prior mass function πκ = Pr[T = k] for k = 1,..., M, with Σk=1^M πk = 1, is used.
Key Equations (from Algorithm 1):
Zt = Σk=t^M πk (Normalization factor for posterior)
Pt,k = πk / Zt (k = t,..., M) (Posterior probability Pr[T = k | T ≥ t])
Time: Computing the normalization factor and the expected-cost sum each day takes O(M) time, resulting in a worst-case total time complexity of O(M²).
Space: Storing the prior and posterior distributions requires O(M) memory.
Sparse-Support Implementation: For priors with n (with n ≤ M) nonzero entries, the algorithm can be optimized by indexing support points using a balanced BST or hash map, maintaining prefix sums for O(log n) query time, and computing Erent(t) by iterating only over n support points. This reduces overall runtime to O(n log n).
Algorithmic Extensions:
Multiple Predictions: Integrates multiple independent predictions T1,...,Tn, each with an associated uncertainty level σi, by sequentially updating the posterior using Bayes' rule, starting from a uniform prior.
Adaptive Prior Learning: An adaptive algorithm learns the prior online over R rounds, starting from a uniform initialization and updating it each round using the observed buying time Tr via an exponential moving average with learning rate α. The update rule is πk^(r+1) = (1 - αr) πk^(r) + αr · 1[k = Tr].
Contextual Prior: The prior can be conditioned on contextual information x through a softmax parameterization: πk(x) = exp(θk · φ(x)) / (Σj=1^M exp(θj · φ(x))), where φ(x) is a feature map and θk is the parameter associated with horizon k.
Results
Experimental Setup:
Buy cost: b = 100
Horizon bound: M = 500
Trials: 10,000 Monte Carlo trials per configuration
Metrics: Competitive Ratio (CR) and Success Rate
Baselines: Deterministic thresholding, optimal randomized strategy, point-prediction purchase, and the learning-augmented strategy of Kumar et al. (2024).
Q1. Robustness to Prior Misspecification:
Uncertainty Regimes: σ/μ ∈ {0.42, 0.33, 0.31}
Performance Degradation: Average cost increase is 5.3%, and worst-case degradation reaches 18.7% under extreme mean errors. Variance and model-form errors have negligible impact.
Q2. Performance Under Perfect Prior Knowledge:
Priors Tested: Unif[1,500], N(100,30²), Exp(0.01)
Bayesian Algorithm: Mean CR = 1.023, 95% CI = [1.021, 1.025], Success Rate = 98.7%
Baselines:
Randomized: Mean CR = 1.582, 95% CI = [1.577, 1.587], Success Rate = 67.3%
Deterministic: Mean CR = 1.847, 95% CI = [1.839, 1.855], Success Rate = 52.1%
Prediction-based: Mean CR = 1.156, 95% CI = [1.150, 1.162], Success Rate = 81.4%
Q3. Noisy Single Predictions:
Prediction Model: ↑ ~ N(αT, (βT)²), with true horizon T = 100, noise level β = 0.3, and bias α ∈ [0.5, 2.0].
Performance: Competitive ratio rises smoothly from 1.05 (α=0.5) to 1.43 (α=2.0).
Comparison: Bayesian method consistently outperforms the point-prediction baseline by 15-30% across all bias levels.
The algorithm adapts to complex, multi-peaked distributions without explicit mode identification, as decisions are governed by the integrated survival function.
Weaknesses / Limitations
Discrete, finite horizon and stationary costs: The framework assumes a discrete, finite horizon and stationary costs, which may limit real-world applicability.
Extensions needed for continuous time and dynamic pricing: Extensions to continuous time and dynamic pricing would require new techniques.
Independent episodes: Episodes are treated as independent, ignoring temporal correlations.
Perfect observability of horizon end: Perfect observability of the horizon end is assumed; more realistic settings with partial or delayed feedback would need belief tracking or filtering.
Evidence
Method evidence: "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." (section: Abstract)
Result evidence: "The Bayesian method achieves near-optimal CR ≈ 1.02 with a 98.7% success rate, significantly outperforming classical baselines." (section: Q2. Performance Under Perfect Prior Knowledge)
Limitation evidence: "We assume a discrete, finite horizon and stationary costs, which may limit real-world applicability. Extensions to continuous time and dynamic pricing would require new techniques. Episodes are treated as independent, ignoring temporal correlations. Perfect observability of the horizon end is assumed; more realistic settings with partial or delayed feedback would need belief tracking or filtering." (section: Limitations and Assumptions)
Additional Figures
Figure 1: Robustness under prior misspecification. (a) Performance degradation across uncertainty regimes remains small even at high total variation (TV) distances. (b) Mean errors have the largest impact, while variance and model errors are negligible. (c) CR distribution remains stable across TV bins.
Figure 2: Competitive ratio under perfect prior knowledge. The Bayesian method achieves CR ≈ 1.02 across all priors, significantly outperforming classical algorithms.