Abstract
This paper introduces a framework for the "Multi-shop Ski Rental" (MSSR) problem, where a decision-maker must choose not just when to buy, but where to buy among multiple shops with different prices. By integrating machine-learned (ML) predictions with a "trust" hyperparameter, the authors develop algorithms that perform exceptionally well when predictions are accurate (consistency) while remaining safe even when the AI is completely wrong (robustness).
Introduction
The classic "Ski Rental" problem is a cornerstone of online algorithm theory: do you keep renting skis for $10/day, or buy them for $100? If you knew you’d ski for 20 days, you’d buy immediately; if only 2 days, you’d rent. In the real world, you don't know the future, so you use an online algorithm to minimize the "competitive ratio" (the cost compared to the perfect offline choice).
This paper tackles two major gaps in the traditional formulation:
- The Multi-shop Extension: In reality, you have choices. Shop A might have cheap rentals but expensive gear, while Shop B has expensive rentals but a great sale on boots. This adds a "where" dimension to the "when" decision.
- Integrating ML Advice: Pure online algorithms are pessimistic—they assume the worst-case scenario. Modern ML can predict the future (e.g., how many days you'll ski), but ML can be wrong. The challenge is designing algorithms that benefit from good advice without being ruined by bad advice.
Methodology
The authors propose a suite of algorithms (both deterministic and randomized) for the MSSR problem. Their core innovation lies in using a hyperparameter $\lambda \in (0, 1)$ to act as a "trust dial."
- Deterministic Approach: The algorithm sets a "break-even" point based on the ML prediction and the trust parameter $\lambda$. If $\lambda$ is near 0, the algorithm follows the ML advice closely. If $\lambda$ is near 1, it ignores the advice and acts like a standard conservative online algorithm.
- Randomized Approach: Instead of a single break-even day, the algorithm chooses a day to buy based on a probability distribution. The authors carefully customized these distributions to account for the varying prices across different shops.
- Multiple Predictors: The paper extends the logic to scenarios with $m$ different ML models. It uses a "majority-style" threshold: if most models suggest you'll ski for a long time, the algorithm adjusts its buying strategy accordingly.
The performance is evaluated using two metrics:
- Consistency: How close the algorithm gets to the optimal cost when the ML prediction is perfect.
- Robustness: The worst-case performance when the ML prediction is intentionally misleading.
Datasets
The authors validated their algorithms using two types of data:
- Synthetic Dataset: A simulated environment with 6 shops featuring varying buying costs ($75–$100) and renting costs ($1–$1.25). They tested these against various levels of prediction error (noise and bias).
- Real-world Dataset (The Big Bang Theory): They modeled the decision of a viewer watching Season 12 of the show. A viewer can "rent" episodes one by one or "buy" the whole season on platforms like Google Play or Amazon Prime. They used viewing data from Season 11 to "train" predictions for Season 12.
Key Insights and Results
- The "Trust Dial" is Essential: You cannot naively follow ML advice. The paper proves that a "simple" learning-aided algorithm has an unbounded competitive ratio—meaning a single bad prediction could make your costs infinitely worse than the optimal.
- The Two-Fold Decision: In MSSR, the "where" is often decided by the "when." If you plan to buy early, you go to the shop with the lowest purchase price. If you plan to rent for a long time before buying, you might choose a shop with lower rental fees even if the purchase price is higher.
- Robustness to "Bad" Experts: When using multiple ML models, the algorithms are designed so that a few "hallucinating" models won't tank the performance, provided the majority or the general trend of the advice is handled via the trust parameter.
- Superiority over Pure Online: The proposed algorithms significantly outperformed the Best Deterministic Online Algorithm (BDOA) whenever the ML prediction had reasonable accuracy.
- Theoretical Bounds: The authors provided provable bounds for the competitive ratio. For example, their deterministic algorithm is shown to be $(( \lambda + 1)r_n + b_1/b_n)$-consistent.
- Empirical Success: In the Big Bang Theory experiment, even with "bad" predictors (models designed to give wrong advice), the algorithm could be tuned via $\lambda$ to still outperform or match the standard non-ML approach.
- Randomized > Deterministic: As is common in online algorithms, the randomized versions generally achieved a better average competitive ratio than the deterministic ones across all tested error levels.
Limitations and Future Work
- Switching Costs: The primary model assumes that once you pick a shop to rent from, you stick with it until you buy. While the authors briefly mention "MSSR with switching costs" (where you can move from Shop A to Shop B), it is treated as an extension rather than the core focus.
- Static Trust: The hyperparameter $\lambda$ is fixed. A promising future direction would be an algorithm that learns to adjust $\lambda$ dynamically as it observes the accuracy of the ML advice over time.
- Prediction Costs: The model assumes ML advice is "free." In some systems, generating a high-quality prediction might have its own computational or financial cost, which isn't factored into the current competitive ratio.
Summary updated