Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem

Keyuan Zhang, Zhongdong Liu, Nakjung Choi, Bo JiAAAI 2024 · DOI

Introduction

The classic "ski-rental problem" is a fundamental model in online algorithms, capturing the trade-off between small recurring costs (renting) and a large one-time investment (buying) under uncertainty. In modern cloud computing, this problem evolves into the two-level ski-rental problem. Users must choose between renting resources hourly (on-demand), purchasing a specific instance type (single purchase), or buying a discounted bundle that covers multiple instance types (combo purchase).

This paper addresses two primary challenges in this domain: the inherent uncertainty of future demand and the performance gap between traditional "pessimistic" online algorithms and modern machine learning (ML) models. While ML models offer high average-case performance, they lack the worst-case safety nets required for critical infrastructure. The authors propose LADTSR, a learning-augmented algorithm that bridges this gap.

The Robust Foundation: RDTSR

Before introducing learning augmentations, the authors developed RDTSR (Robust Deterministic Two-level Ski-rental). This pure online algorithm uses "indicative costs" based on accumulated demand to trigger purchases. A critical insight of RDTSR is its prioritization of combo purchases over individual ones when demand thresholds are met. This strategy prevents the "unbounded cost" trap where an algorithm might buy every item individually just before a combo purchase would have been more economical.

Empirical competitive ratio (CR) of RDTSR compared to DTSR for unit and multi-unit demand scenarios.

As shown in the figure above, RDTSR maintains a competitive ratio (CR) of approximately 3, significantly outperforming the previous DTSR baseline, especially as the combo price $C_c$ varies. It provides a stable theoretical floor regardless of demand patterns.

Learning-Augmented Strategy: LADTSR

The core contribution, LADTSR, integrates ML predictions into the RDTSR framework using a "trust parameter" ($\theta$). Instead of blindly following a prediction, LADTSR uses it to adjust its internal purchase thresholds:

  • High Predicted Demand: The algorithm lowers thresholds to "trust" the prediction and buy earlier, capturing potential savings.
  • Low Predicted Demand: The algorithm raises thresholds to avoid premature, wasteful investments.

By tuning $\theta$, users can balance their reliance on the ML model against the safety of the robust online algorithm. The paper proves that LADTSR is $(1+\theta+\theta^2)$-consistent (near-optimal with perfect predictions) and $(1+\theta^{-1}+\theta^{-3})$-robust (maintaining a cost cap even with catastrophic prediction errors).

Experimental Results and Robustness

The researchers evaluated LADTSR across three datasets: synthetic demand, Microsoft Azure VM traces, and mobile app usage data. The results highlight the algorithm's ability to handle prediction bias gracefully.

Performance of LADTSR across synthetic, Azure, and AppUsage datasets as a function of prediction bias $\mu$ and trust parameter $\theta$.

As illustrated in the experimental results, "Follow the Prediction" (FTP, where $\theta=0$) performs exceptionally well when bias is zero but suffers from skyrocketing costs when demand is overestimated (positive bias). In contrast, LADTSR (intermediate $\theta$ values) maintains stable performance. Interestingly, the data suggests that overestimating demand is more costly than underestimating it, as overestimation leads to immediate, irreversible upfront costs.

Conclusion

LADTSR provides a robust framework for the two-level ski-rental problem, offering the benefits of predictive modeling without sacrificing worst-case guarantees. Future work may explore adaptive trust parameters that adjust $\theta$ in real-time based on observed prediction accuracy, further optimizing the balance between consistency and robustness.

Summary updated

BibTeX
@inproceedings{zhang2024learning,
  author = {Keyuan Zhang and Zhongdong Liu and Nakjung Choi and Bo Ji},
  title = {{Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30010},
}
Figure