# Mixing predictions for online metric algorithms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 4 Apr 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [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 Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Metrical task systems on trees via mirror descent and unfair gluing](https://mlsanity.com/paper/1807.04404/) (2018)
- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [Online Paging with a Vanishing Regret](https://mlsanity.com/paper/2011.09439/) (2020)
- [Shortest Paths without a Map, but with an Entropic Regularizer](https://mlsanity.com/paper/2202.04551/) (2022)
- [A Hitting Set Relaxation for k-Server and an Extension to Time-Windows](https://mlsanity.com/paper/2111.09255/) (2021)

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

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (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)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Online Covering with Multiple Experts](https://mlsanity.com/paper/2312.14564/) (2023)
- [Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach](https://mlsanity.com/paper/2512.07313/) (2025)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors](https://mlsanity.com/paper/2509.26511/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)
- [Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment](https://mlsanity.com/paper/2610.13571/) (2026)

## Abstract (arXiv)

A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of ℓ predictors, we obtain a competitive ratio of O(ℓ2), and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a (1+ε)-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the k-server problem.