acceptodds
Withdrawn from ICLR 2027

Online Algorithms with Unreliable Guidance

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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.

Primary area:
optimization
Keywords:
learning-augmented algorithm, online algorithms, online bipartite matching

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_x1H8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Online algorithms with prediction. Predictions describe exactly an optimal solution. Early work in learning augmented online algorithms studied simple combinations of two opposite behaviors, namely following completely the prediction or ignoring the prediction. In literature two approaches were studied:

(1) follow the prediction until either (two different approaches) the prediction appears to be wrong, or the current competitive ratio would exceed some threshold. And in that case switch to the best known algorithm without prediction.

(2) Distribute the resources or the probability space in two parts, and dedicate each to one of the oppositive behavior.

The paper studies the second approach, and claims novelty.

By definition a c-competitive online algorithm needs to be c-competitive on any prefix of the request sequence. The paper studies another measure, where an algorithm is anytime c-competitive iff it is c-competitive on any factor of the request sequence.

Results: for the metrical task system problem, maximum cardinality bipartite matching, paging and more generally the metrical task system problem the paper analyses their algorithm performance for consistency, robustness and any time competitive ratio. The performance is measured as a function of tau, a probability and tradeoff parameter of the algorithm, n or k, parameters of the instance size and beta a parameter describing how bad the prediction is.

Critical strengths

The paper claims a novel framework and applies to 3 important problems.

Critical weaknesses

I cannot make sense of the conclusion of the introduction: does there exist a model whose formal guarantees depend solely on the problem?

The paper claims novelty for the online algorithms with unreliable guidance model. This is a clear oversell, I have seen these models in the past. And calling the combination (referred as (2) above) a compiler is overselling.

An important reference is missing in the introduction. The studied problems fall typically in the primal dual framework, and therefore the paper should compare their contribution with The Primal-Dual method for Learning Augmented Algorithms by Bamas, Maggiori, Svensson.

The prediction model where the a solution is given is easy to analyze but is way to idealized in a machine learning context. I agree that analyzing an algorithm in this model is easier than in a more realistic model, where ML can predict some learnable aspects of the input sequence. I just don't like the studied model.

The notion of anytime competitiveness is interesting, but again the paper oversells it. This kind of measure has been studied in the past and references are missing:

Hazan and Seshadhri (2007) Adaptive Algorithms for Online Decision Problems

Daniely, Gonen, and Shalev-Shwartz (2015) Strongly Adaptive Online Learning

The community on online algorithms with prediction nowadays studies

  • smoothness, i.e. performance as function of prediction error
  • learnable predictions.

The paper does not address those, hence I find it not so interesting.

Questions for authors

The paper does not say if and how AI was used for this work.

In the description of the algorithm you should make clear if the random decision is done once for all from the beginning or for every request.

I don't understand while in line 227 the cost of the algorithm is written as a difference of costs.

Section 2. I am wondering if you can lighten the notation. I feel it obfuscates the key concepts.

I don't agree that beta is the smoothness. It is just the parameter which allows to generate the Pareto-points of the consistency-robustness tradeoff of the algorithm. Smoothness is the performance of the algorithm with the prediction error, and more precisely its slope.

Reviewer_fvVQOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies online algorithms in which each request is accompanied by a recommended action. Independently at each step, the recommendation comes from a benevolent oracle with probability 1−β1-\beta and is adversarially corrupted with probability β\beta. The benevolent oracle knows the entire request sequence and can adapt to the algorithm’s previous actions.

The paper’s main contribution is a Drop-or-Trust-Blindly (DTB) compiler with a trust parameter τ\tau. With probability τ\tau, DTB follows the recommendation, provided it belongs to the base algorithm’s current action support; otherwise, it samples from the base algorithm’s action distribution. For example, for randomized marking in caching, each recommendation specifies a page to evict. On a page fault requiring eviction, the algorithm evicts the recommended page with probability τ\tau if it is unmarked; otherwise, it evicts a uniformly random unmarked page.

The paper analyzes DTB for online bipartite matching, caching, and uniform metrical task systems, establishing consistency, robustness, and β\beta-dependent performance guarantees. It also introduces anytime competitiveness, which requires guarantees over every interval, conditional on the preceding action history, with the offline comparator inheriting that history.

Critical strengths
  • DTB provides a simple and intuitive way to augment classical randomized algorithms with guidance. Its analysis for three classic online problems is useful, and the approach may apply to other problems beyond those studied here.
  • The algorithms do not need to know the corruption probability. In particular, the paging algorithm achieves constant consistency and logarithmic robustness despite allowing adversarial incorrect recommendations.
Critical weaknesses
  • The novelty of the DTB compiler is not fully established relative to closely related work. Emek et al. (2023) already augment classical randomized algorithms through randomly infused advice and study paging and uniform MTS. Gupta et al. (2022) study probabilistically correct recommendations, including results allowing adversarial incorrect recommendations. A more explicit comparison would help identify the new conceptual and technical contributions.
  • Although DTB can be defined broadly, the paper does not provide general conditions under which it yields useful consistency and robustness guarantees. Each application requires its own analysis, and the transformation cannot change the behavior of a deterministic base algorithm whose action support is a singleton. Consequently, the claims of generality seem somewhat overstated.
  • The paper criticizes previous work for assuming fixed prediction accuracy and motivates OAG through changing prediction reliability. However, its formal model also assumes a single corruption probability β\beta throughout the input. It is unclear how far the anytime guarantees overcome this restriction.
Questions for authors
  1. I like the idea of anytime competitiveness, but many existing analyses seem amenable to interval guarantees. For example, bounded-potential arguments can often absorb the initial potential into an additive constant, and phase-based arguments can often bound the two boundary phases separately. What additional difficulties arise from your definition, particularly its conditioning on the preceding action history?

  2. Could you provide an explicit comparison with randomly infused advice? In particular, which paging and uniform-MTS guarantees recover existing results, and which require new arguments to handle adversarial corruption?

  3. Can you identify general conditions on the base algorithm under which DTB provides useful consistency and robustness guarantees?

  4. Do the anytime guarantees extend to varying corruption probabilities? If so, what precise statement holds, and what assumptions are required?

  5. Could you clarify the relationship of your matching result to Learning-Augmented Online Bipartite Fractional Matching by Choo, Jin, and Shin (NeurIPS 2025), accounting for the distinction between fractional and integral matching?

Reviewer_efmDOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies a general setup for learning-augmented online decision making. As I understand it, the setup is as follows:

  • In each step, the algorithm gets a recommendation (a 'suggested decision' or 'advice'). This advice is assumed to be good with probability 1−β1-\beta and can otherwise be arbitrarily corrupted with probability β\beta. Here, "good" depends on the problem at hand, but is generally the decision that an optimal clairvoyant algorithm would make at the current time step. For example, in online matching the advice is the neighbour of the current arriving online vertex in some fixed maximum matching in the full hindsight graph.
  • The algorithm the paper studies is one that, in each step, flips a coin. If the coin lands heads, the algorithm follows the advice. If the coin lands tails, the algorithm falls back to an existing 'robust' algorithm. For example, for online matching the 'robust' algorithm is the RANKING algorithm. τ\tau, the probability the coin flip lands tails, is a hyperparameter of the algorithm. Intuitively, it controls how much the algorithm trusts the advice.

The paper applies this abstract model and algorithm to 3 concrete problems: Online bipartite matching, caching, and online metrical task systems, and derives anytime competitiveness results for each of these 3 problems that are parameterized by τ\tau and β\beta. Here, 'anytime competitiveness' intuitively means that the competitive ratio should hold for any interval of online arrivals conditioned on the past history.

Critical strengths

I think the high level problem that the paper studies is interesting: It's true that most papers in learning-augmented algorithms have a tailored algorithm/analysis/definition of prediction, and it would be cool to have a unified framework that can capture a lot of the results in the area.

I also think that the notion of anytime competitiveness is interesting, and as far I as know, there have not been many papers before that combine this idea with learning augmented algorithms. (As far am I am aware, most papers in learning augmented algorithms work with the traditional, weaker notion of competitive ratio.)

Critical weaknesses

One weakness of the paper is its writing. I found the model and description of the algorithm to be overly complicated and heavy in notation, and because of this I found the paper to be quite difficult to read. I am normally not very picky about writing, but in the case of this paper, I think it really has a negative impact on the quality of the paper.

I am also not convinced that the results of the paper are true. I did not check all proofs carefully, but if I understand the algorithm and model correctly, I don't think it obtains the claimed anytime guarantee, at least for the online matching setting. Please see 'Questions for Authors' for more details about this.

Questions for authors

For your online matching result, suppose β=1\beta = 1 and τ=0\tau = 0. Then the algorithm never follows the advice, and it is just exactly the same as the RANKING algorithm. In this case, the theorem says that the algorithm should be 1−1/e1-1/e anytime-competitive. However, while the RANKING algorithm is 1−1/e1-1/e competitive in the traditional sense, I don't think it satisfies this competitive ratio in the anytime sense.

For example, consider a graph with 4 offline nodes {1,2,3,4}. Suppose the online arrivals have neighborhoods {1,3}, {2,3}, {3,4}, {4}, in that order. Let's condition on the event that the first two online arrivals get matched to nodes 1 and 2, respectively, and let's look at the last two arrivals. Under this event, we know that RANKING must have ranked 3 after both 1 and 2. Therefore, the probability that 3 is ranked before 4 is only 1/4. Thus, on the final two requests, RANKING gets two matches with probability 1/4, and one match with probability 3/4, so its expected value on the last two arrivals is 5/4. Therefore, the competitive ratio on the last two arrivals, conditioned on the history of the first two arrivals, is 5/8 = 0.625 in this case, which is less than 1−1/e1-1/e.

This example seems to contradict the theorem in the paper for online matching, which claims an anytime competitive guarantee. Could the authors comment on this?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.