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
Sep 4, 2026

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

Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency--robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data structures, graph problems, and mechanism design. An orthogonal theorem-level axis distinguishes achieved upper bounds from matched asymptotic dependence. Formal guarantees are separated from empirical systems evidence, with explicit treatment of prediction cost, feedback, and composition. The resulting synthesis states sufficient conditions for limited end-to-end reasoning and delineates open problems in cost-aware prediction, endogenous error, semantic predictors, and benchmarking.

Hailiang Zhao, Xueyan Tang, Peng Chen +4

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

Learning-Augmented Algorithms
AskPDF
May 26, 2026

Parsimonious Learning-Augmented Online Metric Matching

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Yongho Shin, Phanu Vajanopath

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

Learning-Augmented Algorithms
AskPDF
Aug 27, 2026

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

Learning-augmented algorithms improve online decisions using predictions, but unreliable advice may harm efficiency and fairness. We study an online allocation problem with finite candidate sets, irreversible decisions, and exposure constraints. We propose a robust and fair rule combining advice with a conservative fallback and fairness correction. Under bounded-error assumptions, we prove consistency and robustness with loss proportional to prediction error. Experiments show stability under adversarial advice and significant reductions in exposure disparity.

Fredy Pokou

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

Online Resource AllocationLearning-Augmented AlgorithmsFair Resource AllocationAlgorithmic FairnessDistribution Shift Robustness
AskPDF