Technical Summary: Online Algorithms with Unreliable Guidance

Problem Statement

The paper addresses the challenge of designing learning-augmented online algorithms—algorithms that utilize machine learning predictions to improve performance while maintaining worst-case guarantees. Existing frameworks for analyzing these algorithms suffer from a lack of generality. They typically rely on specific prediction semantics (defining what a prediction represents), error functions (quantifying prediction quality relative to problem instances or optimal solutions), or probing strategies (estimating predictor accuracy). These dependencies restrict the applicability of theoretical guarantees, making results incomparable across different problems and preventing the derivation of assumption-free impossibility results.

The core problem is to establish a model for online decision-making with predictions where the formal guarantees depend solely on the problem structure rather than on predictor-specific choices (such as the nature of the error or the semantics of the prediction).

Methodology: The OAG Model

The authors introduce Online Algorithms with Unreliable Guidance (OAG), a model formulated through the lens of request-answer games. This model separates the predictive and algorithmic components cleanly by introducing three key innovations:

1. Guidance (Prediction Semantics): Instead of defining abstract prediction types, the model assumes predictions are guidance drawn directly from the problem's answer space. For a request $\rho_t$, the guidance $\gamma_t$ is a potential answer the predictor suggests. This unifies semantics across different problems (e.g., suggesting a cache page to evict or a node to match).
2. The Guide and Bad Guidance (Error Modeling): The model introduces a "guide" that generates guidance. Ideally, the guide knows the entire input sequence and provides the optimal answer. However, the model accounts for unreliability: at each step, the guidance provided to the algorithm is either the optimal guidance (with probability $1-\beta$) or an adversarially corrupted guidance (with probability $\beta$). The parameter $\beta$ represents the "bad guidance" probability. This replaces error functions with a probabilistic model of failure that is independent of specific error metrics.
3. Anytime Competitiveness: To address the issue of varying predictor accuracy over time (which breaks static probing strategies), the authors define anytime competitiveness. An algorithm is anytime $c$-competitive if its performance ratio holds for every subsequence of the input, conditioned on the history of answers. This ensures that algorithms do not need to probe or estimate $\beta$ dynamically; they perform well regardless of how $\beta$ fluctuates over time.

The DTB Compiler

A central contribution is the Drop-or-Trust-Blindly (DTB) compiler. This is a generic, black-box transformation that converts any standard, prediction-free randomized online algorithm ($Alg$) into a learning-augmented OAG algorithm ($Alg^*$).

The DTB mechanism operates as follows for each incoming request:

• Let $D_t$ be the probability distribution from which the original algorithm $Alg$ selects an answer.
• Let $\gamma_t$ be the incoming guidance.
• With probability $\tau$ (the trust parameter), $Alg^*$ blindly adopts $\gamma_t$ (provided $\gamma_t$ is a valid answer in the support of $D_t$).
• With probability $1-\tau$, $Alg^*$ ignores the guidance and samples an answer from $D_t$.

This simple rule allows the algorithm to leverage accurate predictions while falling back to the robustness of the original algorithm when predictions are unreliable.

Key Contributions and Results

The paper applies the DTB compiler to three classic online problems, deriving new trade-offs between consistency (performance when $\beta=0$) and robustness (performance when $\beta=1$), as well as smoothness guarantees for intermediate $\beta$.

1. Online Bipartite Matching (Adversarial Arrival)

• Context: The authors apply DTB to the Ranking algorithm (Karp, Vazirani, Vazirani).
• Significance: This is the first non-trivial learning-augmented algorithm for online bipartite matching under adversarial arrival order. Previous works focused on random arrival or specific graph models.
• Result: The Ranking-DTB algorithm achieves an anytime competitive ratio of:
  $$\max \left\{ \frac{1}{2}, (1 - \beta\tau) \cdot \frac{1 - e^{-(1-\tau)}}{1-\tau} \right\}$$
  This provides a smooth interpolation between the standard competitive ratio ($1 - 1/e$ when $\tau \to 0, \beta=0$) and the robustness bound ($1/2$ when $\beta=1$).

2. Online Caching

• Context: The authors apply DTB to the Random Mark algorithm.
• Result: The Marking-DTB algorithm achieves an anytime competitive ratio of:
  $$\min \left\{ \frac{2}{\tau(1-\beta)}, \frac{2H_k}{1-\tau\beta}, k \right\}$$
  where $H_k$ is the $k$-th harmonic number.
• Significance: The algorithm achieves asymptotically optimal constant consistency and logarithmic robustness. The authors note that while the bounds match state-of-the-art results, the algorithm is arguably simpler than existing learning-augmented solutions.

3. Uniform Metrical Task Systems (MTS)

• Context: The authors extend the classical algorithm by Borodin, Linial, and Saks to the OAG model.
• Result: The MTS-DTB algorithm achieves an anytime competitive ratio of:
  $$2 \cdot \min \left\{ \frac{1}{\tau(1-\beta)} + 1, \frac{1-\tau}{(1-\tau\beta)^2} H_n + 1, n \right\}$$
• Significance: This provides optimal consistency and robustness trade-offs for the uniform metric case.

Significance and Claims

The paper claims that the OAG model offers a clean, generic framework that decouples the algorithmic design from the specifics of the predictor. By treating predictions as "guidance" from the answer space and modeling errors via a probabilistic "bad guidance" parameter, the model avoids the inconsistencies of previous approaches regarding error functions and prediction semantics.

The authors emphasize that the DTB compiler serves as a systematic method to generate new learning-augmented algorithms, acting as a "canonical reference point." The results demonstrate that even a simple "trust or drop" strategy can yield strong theoretical guarantees across diverse problem domains.

Limitations

The authors acknowledge two primary limitations of the OAG model:

1. Probabilistic Assumption: The model assumes independent coin tosses for the "bad guidance" parameter $\beta$ at each step. While designed to avoid predictor-specific assumptions, this still imposes a probabilistic structure on the predictor's behavior.
2. Quantitative vs. Qualitative Errors: The model captures quantitative errors (via the probability $\beta$) but cannot express qualitative errors (e.g., specific types of mislabeling) as effectively as error-function-based models. The authors suggest the OAG model is best suited for problems with long input sequences, whereas "one-shot" problems might benefit more from quantitative error characterizations.