Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice

Shufan Wang, Jian Li, Shiqiang Wang

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:

  1. 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.
  2. 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:

  1. 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).
  2. 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.
Deterministic Competitive Ratio with different lambda
  • 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.
Randomized Competitive Ratio with different lambda
  • 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

Abstract

We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the \emph{multi-shop ski rental} (MSSR) problem, which is a generalization of the classical ski rental problem. In MSSR, each shop has different prices for buying and renting a pair of skis, and a skier has to make decisions on when and where to buy. We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions. These online algorithms have no knowledge about the quality or the prediction error type of the ML prediction. The performance of these online algorithms are robust to the poor performance of the predictors, but improve with better predictions. Extensive experiments using both synthetic and real world data traces verify our theoretical observations and show better performance against algorithms that purely rely on online decision making.
BibTeX
@inproceedings{wang2020online,
  author = {Shufan Wang and Jian Li and Shiqiang Wang},
  title = {{Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=o75Iqzpe3kf},
}
Figure