• Computer Science > Artificial Intelligence [Submitted on 24 Feb 2026] Title:Online Algorithms with Unreliable Guidance View PDF HTML (experimental)Abstract:This paper introduces a new model for ML-augmented online decision making, called online algorithms with unreliable guidance (OAG). • This model completely separates between the predictive and algorithmic components, thus offering a single well-defined analysis framework that relies solely on the considered problem. • Formulated through the lens of request-answer games, an OAG algorithm receives, with each incoming request, a piece of guidance which is taken from the problem’s answer space; ideally, this guidance is the optimal answer for the current request, however with probability $\beta$, the guidance is adversarially corrupted. • The goal is to develop OAG algorithms that admit good competitiveness when $\beta = 0$ (a.k.a. • consistency) as well as when $\beta = 1$ (a.k.a. • robustness); the appealing notion of smoothness, that in most prior work required a dedicated loss function, now arises naturally as $\beta$ shifts from $0$ to $1$.

Article Summaries:

  • A new paper on arXiv proposes “online algorithms with unreliable guidance” (OAG), a framework that cleanly separates predictive input from the algorithmic decision‑making in online problems. In OAG, each request comes with a guidance value that is correct with probability 1 - β but may be adversarially corrupted with probability β. The authors introduce the “drop or trust blindly” (DTB) compiler, which turns any prediction‑oblivious online algorithm into a learning‑augmented version that either follows the guidance or ignores it, chosen by a biased coin toss. Using DTB, they achieve optimal consistency‑robustness trade‑offs for caching and uniform metrical task systems, and surpass the best known results for bipartite matching under adversarial arrival.

Sources: