# Online Algorithms with Multiple Predictions

arXiv: https://arxiv.org/abs/2205.03921 · HTML: https://mlsanity.com/paper/2205.03921/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 60 references that are in the map.
- First posted on arXiv 8 May 2022.

## Builds on (most cited first, 23 of 23)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [k-Servers with a Smile: Online Algorithms via Projections](https://mlsanity.com/paper/1810.07508/) (2018)
- [On Approximating (Sparse) Covering Integer Programs](https://mlsanity.com/paper/1807.11538/) (2018)
- [Online metric allocation](https://mlsanity.com/paper/2111.15169/) (2021)

## Built on by (most cited first, 22 of 22)

- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Contract Scheduling with Distributional and Multiple Advice](https://mlsanity.com/paper/2404.12485/) (2024)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Out-of-Distribution-Aware Electric Vehicle Charging](https://mlsanity.com/paper/2311.05941/) (2023)
- [Online Covering with Multiple Experts](https://mlsanity.com/paper/2312.14564/) (2023)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)

## Abstract (arXiv)

This paper studies online algorithms augmented with multiple machine-learned predictions. While online algorithms augmented with a single prediction have been extensively studied in recent years, the literature for the multiple predictions setting is sparse. In this paper, we give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best predictor. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting. Our algorithm can also be robustified, i.e., the algorithm can be simultaneously made competitive against the best prediction and the performance of the best online algorithm (without prediction).