mlsanityData to 14 Oct 2026

Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors

arXiv 2506.05479 ↗First posted 5 Jun 2025cs.LG cs.DScited by 2

Not on the map. Why?

Abstract (arXiv)

We consider the following problem: We are given ℓ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time t cannot be estimated unless the same heuristic was also queried at time t-1. This is related to Bandit Learning against memory bounded adversaries (Arora et al., 2012). We show how to achieve regret of O(OPT2/3) and prove a tight lower bound based on the construction of Dekel et al. (2013).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 30 of its 47 references that are in the map. First posted on arXiv 5 Jun 2025.

Builds on

30 of 47 references.

References · 30

  1. 2019Introduction to Multi-Armed Banditscited by 481
  2. 2018Competitive caching with machine learned advicecited by 195
  3. 2017The Case for Learned Index Structurescited by 188
  4. 2020Algorithms with Predictionscited by 153
  5. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  6. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  7. 2013Bandits with Switching Costs: T^{2/3} Regretcited by 39
  8. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  9. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  10. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  11. 2022Online Algorithms with Multiple Predictionscited by 22
  12. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
18 more
  1. 2023Predictive Flows for Faster Ford-Fulkersoncited by 20
  2. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 19
  3. 2022Parsimonious Learning-Augmented Cachingcited by 19
  4. 2022Algorithms with Prediction Portfolioscited by 19
  5. 2020Online Linear Optimization with Many Hintscited by 16
  6. 2022A Universal Error Measure for Input Predictions Applied to Online Graph Problemscited by 14
  7. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  8. 2023Mixing predictions for online metric algorithmscited by 13
  9. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  10. 2018Metrical task systems on trees via mirror descent and unfair gluingcited by 11
  11. 2021Robustification of Online Graph Exploration Methodscited by 10
  12. 2022The Randomized k-Server Conjecture is False!cited by 8
  13. 2024Learning-Augmented Streaming Algorithms for Approximating MAX-CUTcited by 8
  14. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  15. 2020Online Paging with a Vanishing Regretcited by 5
  16. 2022Shortest Paths without a Map, but with an Entropic Regularizercited by 4
  17. 2013Randomized online computation with high probability guaranteescited by 1
  18. 2024Energy-Efficient Scheduling with Predictionscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  2. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0