Research map / Learning theory and algorithms / Prediction and decision losses

Online Algorithms with Uncertainty-Quantified Predictions

ICML 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Algorithms with explicit predictors · 0 citations (OpenAlex)

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 distributionally-robust competitive ratio (DRCR) and optimization-based/online-learning methods for designing ski rental and online search algorithms that use uncertainty-quantified probabilistic interval predictions.

Problem

How to incorporate uncertainty-quantified (UQ) predictions, such as probabilistic prediction intervals from conformal inference, into online algorithms to improve competitive ratio beyond worst-case and point-prediction approaches.

Approach

Model UQ as a probabilistic interval prediction defining an ambiguity set over instances, minimize the distributionally-robust competitive ratio (a convex combination of consistency and robustness) via an ancillary optimization over hard instances, and use an epsilon-net online learning approach over UQ predictions for multi-instance settings.

Key results

• Deterministic DSR and randomized RSR achieve optimal DRCR for ski rental with probabilistic interval predictions; for point prediction with confidence delta, the DRCR is 1+2sqrt(delta(1-delta)) for delta<=1/2 versus 2 for the worst-case algorithm.
• Online learning algorithm OL-Dynamic achieves sublinear policy regret, Õ(T^{2/3}) for ski rental and Õ(T^{4/5}) for general and online search settings.
• In simulated multi-instance ski rental, OL-Dynamic outperforms RSR over the long run when instance distribution is not worst-case.

Measured effects reported in the paper

Surprising findings

• Even with low prediction quality (delta > 1/2), the DSR deterministic algorithm can still improve the DRCR when the prediction is below about 2.618B.

Limitations

• Results depend on the assumption that the UQ (probabilistic interval) is valid under exchangeability; imprecise UQ may break guarantees.
• Online learning regret bounds rely on Lipschitzness of cost upper bounds and general regret rates are weaker (T^{4/5}).

Experimental setup

Benchmarks: simulated multiple-instance ski rental

Metrics: competitive ratio DRCR policy regret

Baselines: meta-algorithm LA_P(lambda) WOA (worst-case optimized algorithm) FTP (follow the prediction) OL-Static

Builds on: algorithms with predictions conformal prediction learning-augmented ski rental epsilon-net policy regret online learning

Closest papers by meaning

• Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.90)
• Stochastic Online Conformal Prediction with Semi-Bandit Feedback (ICML 2025 · similarity 0.87)
• Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models (NeurIPS 2025 · similarity 0.86)
• Uncertainty Quantification with the Empirical Neural Tangent Kernel (NeurIPS 2025 · similarity 0.85)
• Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.85)
• Online Classification with Predictions (NeurIPS 2024 · similarity 0.85)