cs.AIFeb 24, 2026

Online Algorithms with Unreliable Guidance

Authors: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid

Organizations: TU Berlin, Germany · Technion, Israel · Reykjavik University, Iceland · TU Berlin and Weizenbaum Institute, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic components, thus offering a single, well-defined analysis framework that depends only on the problem at hand. Formulated through the lens of request-answer games, the OAG model brings multiple concepts (predictions from the answer space, guide, anytime competitiveness) which enable learning-augmented algorithms to be analyzed independently of predictor-specific choices - such as prediction semantics, error functions, or probing strategies - that would otherwise restrict the algorithm's generality and applicability. The clean framework of the OAG model allows to build the first generic compiler, the drop-or-trust-blindly (DTB) compiler, that turns almost any standard, prediction-free online algorithm into a learning-augmented one. Although simple, we show that the DTB compiler produces new learning-augmented algorithms with strong consistency-robustness guarantees for three classic online problems: we achieve new trade-offs for bipartite matching with adversarial arrival order, and obtain optimal solutions for caching and uniform metrical task systems.

Figures & tables

Figure 1: A request sequence along which the predictor’s accuracy varies between request subsequences. Anytime competitiveness ensures that the algorithm has provable performance guarantees for each of those subsequences. A third-party prober that keeps accuracy estimates can detect changes in the predictor’s behavior and use anytime competitive guarantees to take an informed decision in real time.
online problemconsistencyrobustness
bipartite matching1−e−(1−τ)1−τ\frac{1-e^{-(1-\tau)}}{1-\tau}max⁡{12,1−e−(1−τ)}\max\left\{\frac{1}{2},1-e^{-(1-\tau)}\right\}
caching (cache size kk )min⁡{2τ,2Hk}\min\left\{\frac{2}{\tau},2H_{k}\right\}min⁡{2Hk1−τ,k}\min\left\{\frac{2H_{k}}{1-\tau},k\right\}
uniform metrical task system ( nn states)2+2⋅min⁡{1τ,(1−τ)Hn}2+2\cdot\min\left\{\frac{1}{\tau},(1-\tau)H_{n}\right\}2+2⋅min⁡{11−τHn,n−1}2+2\cdot\min\left\{\frac{1}{1-\tau}H_{n},n-1\right\}
Table 1: The consistency and robustness guarantees of our OAG algorithms, expressed in terms of the trust parameter 0<τ<10<\tau<1 .
More in this topic

Learning-Augmented Algorithms

Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.

See all 54 papers

Explore similar work

CardsList

  1. Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

    Sep 4, 2026Hailiang Zhao, Xueyan Tang, Peng Chen +4Learning-Augmented Algorithms

    School of Software Technology, Zhejiang University, Ningbo, China · School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore · College of Computer Science and Technology, Zhejiang University, Hangzhou, China +1

  2. Parsimonious Learning-Augmented Online Metric Matching

    May 26, 2026Yongho Shin, Phanu VajanopathLearning-Augmented Algorithms

    Institute of Computer Science, University of Wrocław, Wrocław, Poland.

  3. Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

    Aug 27, 2026Fredy PokouOnline Resource AllocationLearning-Augmented Algorithms

    MRE, CRIStAL · Inria, University of Lille, CNRS, Centrale Lille Villeneuve-d’Ascq, France