Abstract
We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the 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.
Introduction
The Multi-Shop Ski Rental (MSSR) problem generalizes the classic rent-or-buy dilemma to scenarios with multiple vendors offering varying price points. This model is highly relevant to modern cloud computing, where users must decide between pay-as-you-go and reserved instances across different providers like AWS or Azure. Traditional online algorithms focus on worst-case "competitive analysis," which provides safety but is often overly pessimistic. Conversely, pure machine learning (ML) approaches can offer high performance based on historical data but risk catastrophic costs if predictions fail. This paper proposes a framework to bridge these two paradigms.
Methodology: The Trust Parameter $\lambda$
The core of the proposed approach is the introduction of a "trust" hyperparameter, $\lambda \in (0, 1)$, which balances two key metrics:
- Consistency: The algorithm's performance when ML predictions are perfectly accurate.
- Robustness: The worst-case performance bound regardless of prediction error.
A low $\lambda$ signifies high trust in the ML model, prioritizing consistency, while a $\lambda$ closer to 1 prioritizes robustness. For instance, the deterministic algorithm with a single prediction achieves a consistency of $((\lambda + 1)r_n + b_1/b_n)$ and a robustness of $(\max\{r_n, b_1/b_n\} + 1/\lambda)$, where $r_n$ and $b_n$ relate to shop rental and buying costs.
Experimental Evaluation
The algorithms were tested on both synthetic and real-world datasets. The synthetic tests used simulated shop prices and varied the standard deviation of prediction errors. The real-world evaluation utilized viewer data from The Big Bang Theory, modeling the choice between renting or buying episodes across streaming platforms.
Key Insights
- Safety First: Blindly trusting an ML prediction in rent-or-buy scenarios can lead to an unbounded competitive ratio. The trust parameter $\lambda$ provides a mathematical safety net.
- Randomization Advantage: Randomized strategies, which sample buying days from a probability distribution, consistently yield better competitive ratios than deterministic ones, even when augmented with ML advice.
- Ensemble Dynamics: While multiple ML predictions can be used, larger ensembles only improve performance if the underlying models are generally accurate; otherwise, they can degrade robustness.
Conclusion
This work demonstrates that ML predictions can be safely integrated into online decision-making for the MSSR problem. By tuning the trust parameter, practitioners can achieve a balance between optimistic performance and pessimistic safety. Future research may explore "switching costs" between shops and the computational costs of generating ML predictions.
Summary updated