Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a deterministic robust online algorithm (RDTSR) with competitive ratio 3 - 1/Cs - (2-1/Cs)/Cc for the two-level ski-rental problem, and a learning-augmented variant (LADTSR) with trust parameter balancing consistency and robustness, evaluated on synthetic, Azure VM, and app-usage traces.
Problem
Online decision-making for the two-level ski-rental problem, where a user fulfilling demands for multiple items chooses among rent, single purchase, and combo purchase without knowing future demand; existing deterministic algorithms have unbounded CR with multi-unit demands, and ML predictions lack
Approach
Redefine the indicative cost so the combo purchase has highest priority and is not skipped after single purchases, yielding an improved and multi-unit-valid competitive ratio; then integrate per-item and combo ML predictions by scaling purchase thresholds (theta for trusted purchases, 1/theta for others, theta^2 for combo), giving consistency-robustness trade-off.
Key results
- RDTSR's empirical CR stays below its theoretical bound and is lower than DTSR's; DTSR's empirical CR exceeds its claimed bound in multi-unit demand settings.
- The robust online algorithm RDTSR has CR 3 - 1/Cs - (2-1/Cs)/Cc, improving on the (3-1/Cs) bound of DTSR even for unit demands.
- LADTSR with theta in {0.25, 0.5, 0.75} outperforms RDTSR on average cost when predictions are accurate, and degrades less than FTP under large prediction bias.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Integrate predictions with RDTSR using trust parameter θ ∈ (0, 1) | LADTSR · Two-level ski-rental with perfect predictions | competitive ratio: 1 + θ + θ^2 | Helped |
| Integrate predictions with RDTSR using trust parameter θ ∈ (0, 1) | LADTSR · Two-level ski-rental under arbitrary prediction error | competitive ratio: 1 + θ^{-1} + θ^{-3} | Helped |
| Use θ=0, fully following predictions (ablation) | LADTSR · Synthetic, Azure, and AppUsage traces with accurate predictions | average cost ratio | Helped |
| Use θ=0, fully following predictions (ablation) | LADTSR · Synthetic, Azure, and AppUsage traces as prediction bias increases | average cost ratio | Hurt |
| Use θ ∈ {0.25, 0.5, 0.75} instead of θ=1 (ablation) | LADTSR · Synthetic, Azure, and AppUsage traces with accurate predictions | average cost ratio | Helped |
| Use θ ∈ {0.25, 0.5, 0.75} instead of θ=1 (ablation) | LADTSR · Synthetic, Azure, and AppUsage traces with large prediction bias | average cost ratio | Hurt |
| Use λ_c=θ² C_c instead of λ_c=θ C_c (ablation) | LADTSR · Perfect-prediction constructed demand sequence | competitive ratio: 2 - \frac{1}{C_c} | Helped |
| Redefine the indicative cost and prioritize combo purchase | RDTSR · Two-level ski-rental with multi-unit demands | competitive ratio: 3 - \frac{1}{C_s} - \frac{1}{C_c}(2 - \frac{1}{C_s}) vs. (3 - \frac{1}{C_s}) | Helped |
| Replace RDTSR with DTSR | DTSR · Synthetic and real-world traces | empirical competitive ratio | Hurt |
| Allow multi-unit demand arrivals | DTSR · Two-level ski-rental with multi-unit demands | competitive ratio: KC_s/C_c | Hurt |
| Increase the prediction bias toward overestimation | LADTSR · Synthetic, Azure, and AppUsage traces | average cost ratio | Hurt |
Surprising findings
- DTSR's empirical competitive ratio exceeds its theoretical bound under multi-unit demand arrivals, and its CR can be unbounded in that setting.
- Following predictions directly (FTP) is not robust: it can have unbounded competitive ratio despite being consistent.
Limitations
- Robust CR is a worst-case bound; average performance of RDTSR is similar to DTSR.
- Assumes same single purchase cost and threshold across items, integer costs and thresholds, and fully provided predictions at t=0.
- Fixed global trust parameter theta; no adaptive choice; asymmetric effects of over- vs under-estimation not handled.
Experimental setup
Datasets: Synthetic demand sequences (uniform and long-tailed) Microsoft Azure VM workload traces Mobile app data usage traces
Benchmarks: Synthetic dataset Azure VM workload traces AppUsage dataset
Metrics: empirical competitive ratio average cost ratio theoretical competitive ratio
Baselines: DTSR Follow the Prediction (FTP) RDTSR
Builds on: ski-rental problem deterministic two-level ski-rental (DTSR) learning-augmented online algorithms with predictions
Closest papers by meaning
- Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice (NeurIPS 2020 · similarity 0.94)
- Combinatorial Ski Rental Problem: Robust and Learning-Augmented Algorithms (NeurIPS 2025 · similarity 0.93)
- Learning-Augmented Algorithms for the Bahncard Problem (NeurIPS 2024 · similarity 0.89)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.84)
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.84)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.