Research map / Bandits and online learning / Online convex optimization and games
Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Randomize the budget sequence with α sampled from density 1/α | Multi-option ski rental algorithm · Multi-option ski rental | competitive ratio: 4 -> e | Helped |
| Use randomized learning augmentation that can ignore the prediction | Multi-option ski rental · Multi-option ski rental with prediction | robustness: (5+5/\lambda) -> (e^\lambda / \lambda) | Helped |
| Use randomized learning augmentation that can ignore the prediction | Multi-option ski rental · Multi-option ski rental with prediction | consistency: (1+\lambda) -> \chi(\lambda) | Helped |
| Use Our-Rand instead of the deterministic algorithms | Learning-augmented multi-option ski rental · Randomly generated instances; varying prediction error σ | average competitive ratio | Helped |
| Use Our-Det instead of Anand et al. | Learning-augmented multi-option ski rental · Randomly generated instances; varying prediction error σ | average competitive ratio | Hurt |
| Increase the trade-off parameter λ | Our-Det, Our-Rand, and Anand et al. · Randomly generated instances; varying prediction error σ | sensitivity to prediction | Hurt |
Closest papers by meaning
- Combinatorial Ski Rental Problem: Robust and Learning-Augmented Algorithms (NeurIPS 2025 · similarity 0.93)
- Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice (NeurIPS 2020 · similarity 0.93)
- Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem (AAAI 2024 · similarity 0.92)
- Learning-Augmented Algorithms for the Bahncard Problem (NeurIPS 2024 · similarity 0.90)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.84)
- Online Algorithms with Uncertainty-Quantified Predictions (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.