Paper deep dive
Online Algorithms with Unreliable Guidance
Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 2:13:07 PM
Summary
The paper introduces Online Algorithms with Unreliable Guidance (OAG), a framework for ML-augmented online decision-making that separates predictive and algorithmic components. It proposes the 'drop-or-trust-blindly' (DTB) compiler to transform standard online algorithms into learning-augmented ones with strong consistency-robustness guarantees. The authors demonstrate this approach on bipartite matching, caching, and uniform metrical task systems, achieving new or optimal trade-offs.
Entities (7)
Relation Signals (6)
DTB Compiler → transforms → Standard Online Algorithms
confidence 95% · the DTB compiler... turns almost any standard, prediction-free online algorithm into a learning-augmented one
OAG → separates → Predictive and Algorithmic Components
confidence 93% · a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic components
DTB Compiler → appliedto → Bipartite Matching
confidence 92% · we apply the DTB compiler to... the ranking algorithm... for the bipartite matching problem
DTB Compiler → appliedto → Caching
confidence 92% · we apply the DTB compiler to... the random marking algorithm... for the caching problem
DTB Compiler → appliedto → Uniform Metrical Task Systems
confidence 92% · we apply the DTB compiler to... the algorithm... for the uniform metrical task system problem
OAG → introduces → Anytime Competitiveness
confidence 90% · The OAG model brings multiple concepts... including anytime competitiveness
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2602.20706v2
- Canonical: https://arxiv.org/abs/2602.20706v2
Trouble viewing inline? Open PDF directly →
Full Text
73,308 characters extracted from source content.
Expand or collapse full text
TU Berlin, Germany Technion, Israel Reykjavik University, Iceland TU Berlin, Germany TU Berlin and Weizenbaum Institute, Germany CCSXML<ccs2012> <concept> <concept_id>10003752.10003809.10010047.10010048</concept_id> <concept_desc>Theory of computation Online learning algorithms</concept_desc> <concept_significance>500</concept_significance> </concept> <concept> <concept_id>10003752.10010070.10010071</concept_id> <concept_desc>Theory of computation Machine learning theory</concept_desc> <concept_significance>500</concept_significance> </concept> </ccs2012> [500]Theory of computation Machine learning theory [500]Theory of computation Online learning algorithms research of J. Dallot and S. Schmid is supported by the German Research Foundation (DFG), Schwerpunktprogramm SPP 35 2378, ReNO-2 (511099228), 2025-2029. The research of Y. Emek is partially supported by the Israel Science Foundation (ISF), grant 730/24. Online Algorithms with Unreliable Guidance Julien Dallot Yuval Emek Yuval Gil Maciej Pacut Stefan Schmid 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. keywords: Learning-Augmented Algorithms, Online Algorithms, Online Bipartite Matching 1 Introduction Introduced in the influential ICML 2018 paper of Lykouris and Vassilvitskii [lykouris2021competitive], Learning-Augmented online algorithms refer to online algorithms which accept an additional argument, the prediction; the goal is to outperform traditional online algorithms in case of accurate predictions and still provide provable performance guarantees regardless of prediction accuracy. At their core, learning-augmented algorithms seek for the proper use of “guessing machines” — typically an ML predictor — to solve concrete problems, especially when the predictor is a complete black-box and the prediction is therefore unreliable by nature. Since their introduction, this framework gathered significant attention and was applied to multiple problems — the literature on learning-augmnented online algorithms is too extensive to list here; see [OnlineAlgorithmsPredictionsWebsite] for a comprehensive record. Over the years, multiple models have been proposed to describe and analyze learning-augmented algorithms. In essence, those models seek to optimize the same three goals: (1) consistency, the competitive ratio when the predictions are perfect; (2) robustness, the competitive ratio when the predictions are arbitrarily bad; and (3) smoothness, the function describing the decline in the competitive ratio as predictions’ quality degrades. While the community agrees on these three metrics (what to measure), their concrete implementations (how to measure) remain debated and differ across models. The key question is: how can one measure the accuracy of a prediction while treating the predictor as a black box? We review below how existing models interact with the predictor and the issues this raises. Prediction semantics. Before designing a learning-augmented algorithm, one must fix a prediction semantic — that is, decide what a prediction represents and how many distinct predictions are possible. This choice is consequential: it can affect the power of a learning-augmented algorithm, as shown in [DBLP:journals/iandc/Angelopoulos23] for the line search problem, where three different prediction semantics yield different optimal results. Yet no standard way to choose a prediction semantic exists, and the choice is left to the analyst’s judgment. As a result, semantics vary across problems and sometimes even across algorithms for the same problem (e.g., predicting nodes’ degrees [DBLP:conf/nips/AamandCI22] or the matched node [DBLP:conf/icml/ChooGL024] for online bipartite matching, predicting the cache content [antoniadis2023online] or the page to evict [lykouris2021competitive] for caching). This inconsistency makes results for the same problem incomparable. Error functions. Most existing learning-augmented online algorithms are analyzed using an error function [lykouris2021competitive], which acts as an intermediary metric to assess the quality of a prediction given a problem instance. Initially motivated by the loss function optimized during ML training, the error function is now widely used for analysis purposes, especially to derive crucial smoothness results, i.e., the competitive ratio for specific error values. As of today, no consensus exists on how to choose an error function for a given problem; in practice, the choice of how to assess errors is largely left to the analyzer’s judgment and justified by intuitive considerations. Consequently, a wide variety of error functions appear in the literature: some compare predictions against aspects of the problem instance [DBLP:conf/podc/Ben-DavidDEG25, DBLP:conf/nips/PurohitSK18], others against an optimal offline algorithm [DBLP:conf/nips/AamandCI22, bansal2022learning], and different functions are sometimes used for similar problems (e.g., for bipartite matching, sanctioning any error [DBLP:conf/icml/ChooGL024] and counting the number of matches that differ from the optimal solution [DBLP:conf/nips/AntoniadisGKK20], or for online caching, the absolute distance between real and predicted requests for each page [lykouris2021competitive] and the size of the xor between optimal and predicted cache contents [antoniadis2023online]). This lack of a common ground poses multiple issues: it prevents adequate comparisons between results or transfers of algorithmic ideas, leaves room for analysis-driven error functions that artificially advantage certain algorithms or do not properly account for realistic errors, and prevents the emergence of assumption-free impossibility results on the smoothness metric. Predictor probing. In part to address the limitations of error functions, quantitative models were introduced, notably ϵε-Accurate Predictions [gupta2022augmenting] and Infused Advice [EmekGP023]. Those models replace the error function with a probability of failure inspired by the success rate metric of ML predictors: each prediction is independently good or bad decided with coin tosses of a fixed probability. While more systematic and both problem- and predictor-agnostic, these models share two restrictive assumptions. First, bad predictions are random rather than adversarial111As assumed in [gupta2022augmenting] for the caching problem., which cannot model structured errors such as mislabeling or representation errors. Second, the failure probability is fixed over the entire input sequence, which is unrealistic when predictor accuracy varies over time. Together, these assumptions incentivize probing strategies [gupta2022augmenting] that sample predictions to estimate the failure rate, and then exploit it — a strategy that breaks down if accuracy changes mid-sequence. The starting point of this paper is that existing learning-augmented algorithms rely on non-general assumptions about the predictor, restricting the applicability of their guarantees. We therefore ask: does there exist a model whose formal guarantees depend solely on the problem? 1.1 The OAG Model We answer the aforementioned question in the affirmative by introducing a new model, called online algorithms with unreliable guidance (OAG), that stems directly from the formulation of online problems as request-answer games [BorodinEY1998book] and does not involve any “external ingredients” such as prediction semantics, error functions or probing strategies. The OAG model brings three main innovations: a systematic manner to model predictions, a new manner to model the predictor’s accuracy with the guide, and a new manner to evaluate the algorithm’s performance called the anytime-competitive ratio; refer to Section 2 for a formal definition of the OAG model. Modeling predictions with guidance. We propose a universal standard for prediction semantics: predictions should take the form of answers the predictor would give if it were in the algorithm’s place. We call this prediction semantic guidance. Concretely, this means predictions are drawn directly from the answer space of the problem — a natural choice, since (almost) all useful online problems can be modeled as request-answer games [BorodinEY1998book]. Modeling errors with a guide. Inspired by the success rate of an ML predictor, we model good and (adversarially) bad predictions with a guide. An OAG algorithm for an online problem P receives, with each incoming request ρt _t, a guidance γt _t taken from the answer space of P. Ideally, γt _t is a good guidance that was generated knowing the entire request sequence and aiming to help the algorithm by selecting the optimal answer for ρt _t, however, γt _t may also be a bad guidance that selects the answer adversarially knowing the whole input sequence. The choice between the two guidance at time t is made by nature based on an independent β-biased coin toss, where 0≤β≤10≤β≤ 1 is a model bad guidance parameter, so that γt _t is bad with probability β and good with probability 1−β1-β. Similarly to the approach of [gupta2022augmenting] (where β is analogous to 1−ϵ1-ε), consistency and robustness are obtained by setting β=0β=0 and β=1β=1, respectively, whereas smoothness arises naturally as β shifts from 0 to 11. Modeling predictor’s changes with anytime competitiveness. We introduce anytime-competitiveness, a metric that bounds performance against the offline optimum on every subsequence of the input sequence. Since guarantees hold for all subsequences and all values of β, algorithms have no incentive to probe the predictor: tuning the algorithm’s behavior according to an estimated β would only hurt performance on the current interval for other predictor accuracies. This cleanly decouples the predictive and algorithmic parts by separating the acts of estimating the predictor’s accuracy from the act of analyzing the algorithms’ performance — a third party may still probe and, upon detecting a change in accuracy, adjust the influence of predictions in real time (e.g., by changing the trust parameter τ, see next Subsection 1.2), with our framework directly supplying the relevant guarantees to take informed decisions. timeβ=0.1β=0.1β=0.9β=0.9β=0.4β=0.4 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. 1.2 Drop or Trust Blindly: Augmenting Any Algorithm with Predictions Beyond its elegant analytical framework, the OAG model opens the gate for a generic method, referred to as the drop or trust blindly (DTB) compiler, that transforms, in a blackbox manner, any “standard” (a.k.a. prediction-free) online algorithm into a learning-augmented algorithm in the OAG model. In addition to the excellent performances of some of its output learning-augmented algorithms (see Subsection 1.3), the DTB compiler is the first proposal for a systematic manner to generate new learning-augmented algorithms to serve as a canonical reference point. To see how the DTB compiler works, consider a prediction-free algorithm Alg and an incoming request ρt _t and let DtD_t be the distribution from which Alg picks the answer for ρt _t. Assuming that the incoming guidance γt _t belongs to the support of DtD_t, the OAG algorithm produced by the DTB compiler employs the following simple rule, where 0<τ<10<τ<1 is the compiler’s trust parameter: with probability τ, ∗ Alg^* adopts γt _t blindly; with probability 1−τ1-τ, ∗ Alg^* picks the answer from DtD_t (ignoring γt _t). Refer to Section 2 for a formal exposition of the DTB compiler. On the face of it, the approach taken by the DTB compiler may be seen as “too simple”, however, we prove that the resulting OAG algorithms actually provide attractive consistency-robustness guarantees for some classic and extensively studied online problems. 1.3 Our Technical Contributions In addition to our conceptual contributions, we develop OAG algorithms for classic online problems by applying the DTB compiler to the following well known prediction-free online algorithms: the ranking algorithm of [DBLP:conf/stoc/KarpVV90] for the bipartite matching problem with adversarial arrival order (Section 3); the random marking algorithm of [Fiat1991CompetitivePA] for the caching problem (Section 4); and the algorithm of [BorodinLS92] for the uniform metrical task system problem (Section 5). We analyze those algorithms in the OAG model and anytime competitiveness guarantees expressed with the bad guidance parameter β and the trust parameter τ. The consistency and robustness of our algorithms are obtained by setting β=0β=0 and β=1β=1, respectively; see Table 1. By modifying τ, our algorithms can be made more risky or more prudent with respect to trusting the guidance they receive. online problem consistency robustness bipartite matching 1−e−(1−τ)1−τ 1-e^-(1-τ)1-τ max12,1−e−(1−τ) \ 12,1-e^-(1-τ) \ caching (cache size k) min2τ,2Hk \ 2τ,2H_k \ min2Hk1−τ,k \ 2H_k1-τ,k \ uniform metrical task system (n states) 2+2⋅min1τ,(1−τ)Hn2+2· \ 1τ,(1-τ)H_n \ 2+2⋅min11−τHn,n−12+2· \ 11-τH_n,n-1 \ Table 1: The consistency and robustness guarantees of our OAG algorithms, expressed in terms of the trust parameter 0<τ<10<τ<1. Our results for online bipartite matching give the first non-trivial trade-off between consistency and robustness under adversarial arrival order [DBLP:conf/stoc/KarpVV90]. Due to its many applications (most notably ads allocation), online bipartite matching has been intensively studied in the learning-augmented framework in multiple variants: random arrival order [DBLP:conf/icml/ChooGL024, DBLP:conf/nips/AntoniadisGKK20], random graph [DBLP:conf/nips/AamandCI22], and two-stage arrival [DBLP:conf/nips/JinM22]. We are the first to derive non-trivial points on the consistency-robustness Pareto frontier for the original version of the problem. For the online caching and uniform metrical task system problems, our algorithms (with constant 0<τ<10<τ<1) admit asymptotically optimal constant consistency and logarithmic robustness, while being arguably simpler than the existing algorithms that have such guarantees (see, e.g.,[lykouris2021competitive]). 1.4 Model limitations We see two limitations of the OAG model. First, it still assumes a probabilistic predictor (independent coin tosses per request) while the model was designed to avoid predictor-specific assumptions. Second, it only captures quantitative errors and cannot express qualitative ones as error functions do. Despite their drawbacks, error functions offer finer-grained error characterization — particularly for “one-shot” problems (e.g., ski rental [KumarPS2018improving]) where quantitative approaches give deceptively simple guarantees; the OAG model is best suited for problems with long input sequences. 2 Model Request-Answer Games. Consider an online minimization (resp., maximization) problem P defined over a request space ℛR and an answer space A. An instance of P is given by a finite request sequence ρ∈ℛ∗ρ ^*; a solution for ρ is an answer sequence σ∈∗σ ^* satisfying |σ|=|ρ||σ|=|ρ|. The quality of the solutions is measured by a cost function f:⋃ℓ≥0ℛℓ×ℓ→ℝ≥0∪∞f_P: _ ≥ 0R ×A _≥ 0∪\∞\ (resp., a payoff function f:⋃ℓ≥0ℛℓ×ℓ→ℝ≥0∪−∞f_P: _ ≥ 0R ×A _≥ 0∪\-∞\) that determines the cost (resp., payoff) f(ρ,σ)f_P(ρ,σ) associated with applying the solution σ∈ℓσ to the request sequence ρ∈ℛℓρ . On an input request sequence ρ=(ρ1,…,ρℓ)∈ℛℓρ=( _1,…, _ ) , a (randomized) online algorithm Alg for P constructs the solution σ=(σ1,…,σℓ)∈ℓσ=( _1,…, _ ) in an online fashion so that request ρt _t is revealed to Alg at (discrete) time t=1,…,ℓt=1,…, and in response, Alg (probabilistically) decides on the answer σt _t irrevocably. Formally, an online algorithm Alg is a family =tt≥1 Alg= \ Alg_t \_t≥ 1 of functions t:ℛt−1×t−1×ℛ×0,1∞→ Alg_t:R^t-1×A^t-1×R×\0,1\^∞ that construct the answer σt=t((ρ1,…,ρt−1),(σ1,…,σt−1),ρt,r)∈ _t= Alg_t (( _1,…, _t-1),( _1,…, _t-1), _t,r ) at time t based on the request history (ρ1,…,ρt−1)∈ℛt−1( _1,…, _t-1) ^t-1, the answer history (σ1,…,σt−1)∈t−1( _1,…, _t-1) ^t-1, the incoming request ρt∈ℛ _t , and the current random coin tosses r∈0,1∞r∈\0,1\^∞.222For the sake of simplifying some of the discussions in the sequel, our formulation assumes (without loss of generality) that the online algorithm has no access to past coin tosses. Anytime Competitiveness. The gold standard for evaluating the performance of online algorithms is competitive analysis that compares the cost/payoff of the algorithm on the entire request sequence to that of an optimal offline algorithm. In this paper, we enhance this classic notion and introduce the notion of anytime competitive analysis, requiring that the competitiveness of the online algorithm holds for any time interval of the request sequence. To this end, consider a request sequence ρ=(ρ1,…,ρℓ)∈ℛℓρ=( _1,…, _ ) and times 0≤t0<t1≤ℓ0≤ t^0<t^1≤ . Let S(ρ,t0)⊆t0S(ρ,t^0) ^t^0 be the set of answer sequences σ0=(σ10,…,σt00)σ^0=(σ^0_1,…,σ^0_t^0) such that when Alg runs on ρ, it constructs σ0σ^0 at times t=1,…,t0t=1,…,t^0 with a positive probability (that is, S(ρ,t0)S(ρ,t^0) is the support of the probability distribution from which the answer prefix of Alg is picked when Alg runs on ρ). Fix some answer sequence σ0=(σ10,…,σt00)∈S(ρ,t0)σ^0=(σ^0_1,…,σ^0_t^0)∈ S(ρ,t^0) and let (σt0+1,…,σt1)∈t1−t0( _t^0+1,…, _t^1) ^t^1-t^0 be the answer sequence constructed by Alg when it runs on ρ at times t=t0+1,…,t1t=t^0+1,…,t^1, conditioned on the event that Alg constructs the request sequence σ0σ^0 at times t=1,…,t0t=1,…,t^0; notice that (σt0+1,…,σt1)( _t^0+1,…, _t^1) is a random variable that depends on the coin tosses of Alg at times t=t0+1,…,t1t=t^0+1,…,t^1. Define the cost (resp., payoff) of Alg on ρ during the time interval (t0,t1](t^0,t^1] given the answer prefix σ0σ^0, denoted by (ρ,t0,t1,σ0) Alg(ρ,t^0,t^1,σ^0), as (ρ,t0,t1,σ0)=(f(ρ,(σ10,…,σt00σt0+1,…,σt1)))−f((ρ1,…,ρt0),σ0). Alg (ρ,t^0,t^1,σ^0 )\,=\,E (f_P (ρ, (σ^0_1,…,σ^0_t^0 _t^0+1,…, _t^1 ) ) )-f_P (( _1,…, _t^0),σ^0 )\,. Let (σt0+1∗,…,σt1∗)∈t1−t0(σ^*_t^0+1,…,σ^*_t^1) ^t^1-t^0 be a request sequence that minimizes (resp., maximizes) f(ρ,(σ10,…,σt00,σt0+1∗,…,σt1∗))f_P (ρ,(σ^0_1,…,σ^0_t^0,σ^*_t^0+1,…,σ^*_t^1) ), that is, a request sequence constructed by an omnipotent optimal algorithm that knows the entire request sequence ρ in advance (i.e., an optimal offline algorithm), given the answer prefix σ0σ^0. Denote (ρ,t0,t1,σ0)=f(ρ,(σ10,…,σt00σt0+1∗,…,σt1∗))−f((ρ1,…,ρt0),σ0). Opt (ρ,t^0,t^1,σ^0 )\,=\,f_P (ρ, (σ^0_1,…,σ^0_t^0σ^*_t^0+1,…,σ^*_t^1 ) )-f_P (( _1,…, _t^0),σ^0 )\,. Online algorithm Alg is said to be anytime c-competitive if there exists a constant d such that for every integer ℓ≥0 ≥ 0, request sequence ρ=(ρ1,…,ρℓ)∈ℛℓρ=( _1,…, _ ) , times 0≤t0<t1≤ℓ0≤ t^0<t^1≤ , and answer sequence σ0=(σ10,…,σt00)∈S(ρ,t0)σ^0=(σ^0_1,…,σ^0_t^0)∈ S(ρ,t^0), it is guaranteed that (ρ,t0,t1,σ0)≤c⋅(ρ,t0,t1,σ0)+d Alg(ρ,t^0,t^1,σ^0)≤ c· Opt(ρ,t^0,t^1,σ^0)+d (resp., (ρ,t0,t1,σ0)≥c⋅(ρ,t0,t1,σ0)−d Alg(ρ,t^0,t^1,σ^0)≥ c· Opt(ρ,t^0,t^1,σ^0)-d).333Notice that the classic definition of competitiveness is obtained as a special case of anytime competitiveness by fixing t0=0t^0=0 and t1=ℓt^1= . The OAG Model. An online algorithm with unreliable guidance (OAG) Alg for P is an online algorithm augmented with a guidance sequence γ=(γ1,…,γℓ)∈ℓγ=( _1,…, _ ) , where ℓ is the length of the request sequence, that ideally provides the optimal answers to Alg, but should be regarded with caution as it is not fully trustworthy. Formally, an OAG algorithm Alg is a family =tt≥1 Alg= \ Alg_t \_t≥ 1 of functions t:ℛt−1×t−1×ℛ×0,1∞→ Alg_t:R^t-1×A^t-1×R×A×\0,1\^∞ that construct the answer σt=t((ρ1,…,ρt−1),(σ1,…,σt−1),ρt,γt,r)∈ _t= Alg_t (( _1,…, _t-1),( _1,…, _t-1), _t, _t,r ) at time t based on the request history (ρ1,…,ρt−1)∈ℛt−1( _1,…, _t-1) ^t-1, the answer history (σ1,…,σt−1)∈t−1( _1,…, _t-1) ^t-1, the incoming request ρt∈ℛ _t , the incoming guidance γt∈γ^t , and the current random coin tosses r∈0,1∞r∈\0,1\^∞. Ideally, the guidance sequence γ is constructed by a guide G that aims to minimize Alg’s cost (resp., maximize Alg’s payoff). Formally, the guide is a family =ℓ,tℓ≥1,1≤t≤ℓG= \G_ ,t \_ ≥ 1,1≤ t≤ of functions ℓ,t:ℛℓ×t−1→G_ ,t:R ×A^t-1 that generate a guidance γt=ℓ,t(ρ,(σ1,…,σt−1))∈γ g_t=G_ ,t (ρ,( _1,…, _t-1) ) at time t based on the entire request sequence ρ∈ℛℓρ and the answer history (σ1,…,σt−1)∈t−1( _1,…, _t-1) ^t-1. The crux of the OAG model is that at each time 1≤t≤ℓ1≤ t≤ , the guidance generated by the guide is replaced with an adversarially corrupted guidance γt∈γ c_t independently with probability β, where 0≤β≤10≤β≤ 1 is a model bad guidance parameter; that is, the guidance γt _t provided to Alg is set to γtγ g_t with probability 1−β1-β, and to γtγ c_t with probability β. To make the model formulation precise, given a function c:[0,1]→ℝ>0c:[0,1] _>0, an OAG algorithm Alg is said to be anytime c(β)c(β)-competitive if there exists a guide G such that for every bad guidance parameter 0≤β≤10≤β≤ 1 and for every corrupted guidance sequence (γ1,…,γℓ)∈ℓ(γ c_1,…,γ c_ ) , the algorithm is guaranteed to be anytime c(β)c(β)-competitive assuming that γt←γt _t←γ g_t with probability 1−β1-β and γt←γt _t←γ c_t with probability β for each time 1≤t≤ℓ1≤ t≤ , independently. The function c=c(β)c=c(β) that optimizes the anytime competitiveness of Alg for each 0≤β≤10≤β≤ 1 is referred to as Alg’s smoothness, whereas c(0)c(0) and c(1)c(1) are referred to as Alg’s consistency and robustness, respectively. The DTB Compiler. In this paper, we restrict our attention to a class of OAG algorithms that are derived from (prediction-free) online algorithms via a blackbox transformation. This transformation, referred to as the drop or trust blindly (DTB) compiler, is parameterized by a trust parameter 0≤τ≤10≤τ≤ 1 (we may occasionally restrict to non-extreme values of τ for simplicity). Given an online algorithm =tt≥1 Alg=\ Alg_t\_t≥ 1, the OAG algorithm ∗=t∗t≥1 Alg^*=\ Alg^*_t\_t≥ 1 obtained from Alg by applying the DTB compiler with trust parameter τ is defined as follows. Consider time t≥1t≥ 1 and fix some request history (ρ1,…,ρt−1)∈ℛt−1( _1,…, _t-1) ^t-1, answer history (σ1,…,σt−1)∈t−1( _1,…, _t-1) ^t-1, and incoming request ρt∈ℛ _t . Let Dt∈Δ()D_t∈ (A) be the probability distribution from which t((ρ1,…,ρt−1),(σ1,…,σt−1),ρt,r) Alg_t(( _1,…, _t-1),( _1,…, _t-1), _t,r) is picked and let Vt=support(Dt)V_t=support(D_t) be the set of answers in the support of DtD_t, referred to as valid answers.444Depending on Alg, we may wish to change the description of the DTB compiler so that the valid action set VtV_t includes all answers σ∈σ that are legal for the incoming request ρt _t in the sense that they do not lead to ∞ cost (resp., −∞-∞ payoff). This is without loss of generality as Alg can be modified so that support(Dt)support(D_t) consists of all such legal answers while changing the overall cost (resp., payoff) by a negligible amount. Let γt _t be the incoming guidance and let φtrust _trust be the outcome of a fresh Bernoulli trial with success probability τ. Denoting the answer of ∗ Alg^* at time t by σt _t, the function σt=t∗((ρ1,…,ρt−1),(σ1,…,σt−1),ρt,γt,r) _t= Alg^*_t(( _1,…, _t-1),( _1,…, _t-1), _t, _t,r) is constructed by setting σt=γt _t= _t if γt∈Vt _t∈ V_t and φtrust=success _trust=success; and by picking σt _t from DtD_t otherwise (i.e., if γt∉Vt _t∉ V_t or φtrust=failure _trust=failure). 3 Online Bipartite Matching An instance of the online bipartite matching problem consists of a bipartite graph G=(U,V,E)G=(U,V,E) and a permutation π of the nodes of U. The nodes in U arrive one by one in the order π, potentially adversarial. Each time a node u∈Uu∈ U arrives, its incident edges are revealed. The online algorithm must then decide to match u right away and in an irrevocable manner with one of its neighbors in V that was not already matched. The goal is to maximize the size of the obtained matching. The online bipartite matching problem was first solved in 1990 by Karp, Vazirani and Vazirani [DBLP:conf/stoc/KarpVV90] who presented the well-known Ranking algorithm and proved it achieves a competitive ratio always greater than 1−e−11-e^-1 against an oblivious adversary. They also showed that this competitive ratio is optimal up to lower-order factors in the number of nodes. To the best of our knowledge, and despite multiple works on related problems [DBLP:conf/nips/AamandCI22, DBLP:conf/icml/ChooGL024, DBLP:conf/nips/AntoniadisGKK20, DBLP:conf/nips/JinM22], there exists no learning-augmented algorithm for the online bipartite matching problem. This section presents the DTB variant of the Ranking algorithm, Ranking-DTB, whose pseudo-code can be found in appendix (Algorithm 1). We derive an anytime-competitive ratio for Ranking-DTB which interpolates smoothly around the optimal, prediction-free competitive ratio of 1−e−11-e^-1 and depends on the values of β and τ: Theorem 3.1. Ranking-DTB is max12,(1−βτ)⋅1−e−(1−τ)1−τ \ 12,\; (1-βτ )· 1-e^-(1-τ)1-τ \-competitive anytime in the OAG model. Proof 3.2. Proof in Appendix (Subsection B.6). From now on, we call M∗M^* a maximum matching (the optimal offline solution); let x∈U∪Vx∈ U∪ V, we call m∗(u)∈Vm^*(u)∈ V the match of x according to M∗M^*. To fix a guide, we assume that a good guidance suggests to match according to M∗M^*. When u∈Uu∈ U is revealed, we call N(u)N(u) the set of neighbors of u that were not already matched by the considered algorithm. The proof of Theorem 3.1 is inspired by the work of Birnbaum and Mathieu [DBLP:journals/sigact/BirnbaumM08]. The perfect matching hypothesis. As in prior work [DBLP:conf/stoc/KarpVV90, DBLP:journals/sigact/BirnbaumM08], we restrict to graphs admitting a perfect matching: this ensures positive matching probabilities and fixes the optimal payoff at n (for a graph with 2n2n nodes). In the prediction-free setting this is natural since Ranking’s worst cases are perfect-matching graphs. This assumption is no more true in the OAG model — bad guidance could in principle make other graphs harder for Ranking-DTB—but our first claim (Lemma 3.3) shows that perfect-matching graphs remain worst cases provided that bad guidance plays optimally to minimize our anytime competitive ratio. We assume henceforth that G admits a perfect matching, with n=|V|=|U|n=|V|=|U|. Lemma 3.3 (Node Removal). Fix a graph G, an arrival order π. Let badG^bad be the bad function that minimizes the expected competitive ratio of Ranking-DTB in this context. Assume there exists a node x∈U∪Vx∈ U∪ V that is not matched by the maximum matching M∗M^* and define G′G the graph G where x was removed. Then there exists a bad guidance so that the expected competitive ratio of Ranking-DTB on G′G is no greater that the expected competitive ratio on G. Proof 3.4. Proof in Appendix (Subsection B.2). Independence under the guide’s influence. The original Ranking analysis [DBLP:conf/stoc/KarpVV90] exploits correlations across decisions: since all nodes share the same ranking, the probability that a node is unmatched can be bounded via the expected number of nodes matched so far: matching few nodes increases the chances to match more nodes later. Lemma 3.10 adapts this argument to the OAG model. Establishing this requires a key independence property in order to contain the guide’s influence. To see this, let t∈⟦n⟧t∈ n , let v∈Vv∈ V be the (random) node of rank t. Assume v is not matched. We call u=m∗(v)u=m^*(v) the optimal match of v, and Rt−1⊆UR_t-1 U the set of nodes already matched to some v′∈Vv ∈ V of rank less than t. Since by assumption the ranking algorithm (not the guide) matched u, we have u∈Rt−1u∈ R_t-1—otherwise u would have been matched to v. Deriving Lemma 3.10 would require u and Rt−1R_t-1 to be independent, which unfortunately fails in general [DBLP:journals/sigact/BirnbaumM08]. Both [DBLP:conf/stoc/KarpVV90, DBLP:journals/sigact/BirnbaumM08] resolve this by replacing u with a node drawn uniformly at random, which is independent of Rt−1R_t-1. This requires first verifying that permuting node ranks leaves the distribution of output matchings unchanged—which holds in the OAG model, since relabeling ranks carries the guide’s behavior with it. We introduce the following notation for replaced ranking: Definition 3.5 (Replaced Ranking). Let t∈⟦n⟧t∈ n and let σ be a ranking of the nodes in V. We define σt,i _t,i as the ranking σ where the node with rank t was removed and put back in with rank i. We then show the core of our proof: even under the guide’s influence, transforming a ranking into a replaced ranking incurs at most a difference of one alternating chain between the two output matchings. Unique alternating chain despite the guide. We want to show that, for any bad guidance, replacing a node in a ranking always has a small effect on the output matching; more precisely, executing Ranking-DTB on a replaced ranking outputs a matching that differs by at most one alternating chain. We show that, despite the influence of the guide, a similar claim holds in the OAG model. Intuitively we show that, (1) an alternating chain cannot start when Ranking-DTB uses the guidance to make its decisions — the guide has no access to the algorithms’ random seed — and (2) if an alternating chain has already started in the past, we use the fact that both executions of Ranking-DTB (with and without replacement in the ranking) receive the same guidance, implying that the guide either does not interfere with the chain (if the suggested match is possible in both executions) or else makes the chain longer (if the suggested match is possible in only one execution, hence following the guidance implies to match with a node at the end of an alternating chain). Lemma 3.6 (Unique Alternating Chain). Let t,i∈⟦n⟧t,i∈ n . Let σ be a ranking and let M be the output matching of Ranking-DTB using ranking σ. We call Ranking-DTBt,i Ranking-DTB_t,i the same algorithm as Ranking-DTB except it uses the replaced ranking σt,i _t,i, let Mt,iM_t,i be the output matching. Then assuming that M and Mt,iM_t,i are not equal and that M does not match some node v∈Vv∈ V, then M and Mt,iM_t,i differ by one single alternating chain starting at v. Proof 3.7. Proof in Appendix (Subsection B.3). Once we established the uniqueness of the alternating chain, we can efficiently isolate the influence of the guide from our Ranking logic and deduce our independence result in Lemma 3.8. Intuitively this states that, provided that the ranking (not the guide) is used, the probability that a node v with rank t is not matched is upper-bounded by the probability that any node of U (i is free of choice, thus the desired independence property) is in RtR_t using the replaced ranking σt,i _t,i. Lemma 3.8 (Higher Rank). Let G, π be a problem instance, let γ be a guidance sequence, let σ be a ranking. Let u∈Uu∈ U and let v=m∗(u)v=m^*(u), let t be the rank of v in σ. Assuming that the ranking (not the guide) is used to match u then, if v is not matched under σ, for all i∈⟦n⟧i∈ n , u is matched under σt,i _t,i to a node with rank at most t in σt,i _t,i. Proof 3.9. Proof in Appendix (Subsection B.4). We finally derive our induction lemma which directly implies the main claim (Theorem 3.1) using an inductive reasoning. The fact that an alternating chain is unique whatever the bad guidance allowed us to decouple the losses in payoff generated by the guidance (left term βτβτ) from those generated by the Ranking algorithm (right term 1−τn⋅∑1≤s≤txs 1-τn· _1≤ s≤ tx_s) using simple conditional probabilities. Lemma 3.10 (Induction Lemma). Let t∈⟦n⟧t∈ n . Given a problem instance and a prediction, let xtx_t be the probability that the node of rank t is matched. It holds: 1−xt≤βτ+1−τn⋅∑1≤s≤txs 1-x_t ≤ βτ\ +\ 1-τn· _1≤ s≤ tx_s Proof 3.11. Proof in Appendix (Subsection B.5). 4 Online Caching The online caching problem considers a set of pages and a memory (cache) which can store up to k pages. A sequence of pages (requests) arrives in an online manner. Each time a page arrives, it must be cached, that is, the page must be fetched into the cache in case it was not cached already. An algorithm which solves the caching problem must maintain the cache over time so that each page is cached when it was requested and ensure that the cache never contains more than k pages. Fetching a page costs 11 and the goal of the algorithm is to minimize the overall cost. The online caching problem [Fiat1991CompetitivePA] is the most studied online problem in the learning-augmented framework. The seminal paper from Lykouris and Vassilvitskii [lykouris2018] already focused on randomized caching and gave (asymptotic) optimal robustness and consistency bounds. Most notable follow-up works solved more general variants such as the weighted case [bansal2022learning, jiang2022online] while others focused on improving the smoothness bound [rohatgi2020near, DBLP:conf/approx/Wei20]. In this section, we present the DTB variant of the well-known Random Mark algorithm [Fiat1991CompetitivePA] to solve the online caching problem. We call our algorithm Marking-DTB (Algorithm 2, pseudocode in appendix C.1) and show it achieves the (asymptotic) optimal trade-off between consistency and robustness (β=0β=0 and β=1β=1, respectively) while its competitive ratio smoothly degrades as the predictive errors become greater (Theorem 4.1): Theorem 4.1. Marking-DTB (Algorithm 2) is min2τ(1−β),2Hk1−τβ,k \ 2τ(1-β), 2H_k1-τβ,k \-competitive anytime in the OAG model with an additive constant of 2k2k. Proof 4.2. Proof in Appendix (Subsection C.4). Efficiently solving the caching problem amounts to evicting the pages that will be requested the furthest in time. Hence, we assume that a good guidance suggests to evict such an (unmarked) page; here guidance overlaps with literature standars [lykouris2021competitive]. blame chains. Our proof works on blame chains. A blame chain is a sequence of pages r(1)…r(n)r(1)… r(n) that were evicted by Marking-DTBsuch that, for all i∈⟦n−1⟧i∈ n-1 , r(i+1)r(i+1) was evicted because r(i)r(i) was requested. In addition, all pages of a blame chain are pages that should not have been evicted, except the last one. As a result, each page that is not the last incurs a non-optimal cost for Marking-DTB. Our proof reasons on the length of blame chains. For i∈[0,n]i∈[0,n], let XiX_i be the random variable equal to the remaining number of pages in the blame chain starting from page r(n−i)r(n-i) (conditioned on the event that r(n−i)r(n-i) is part of the blame chain). We now state the core of our proof with Lemma 4.3 which states that, whatever its strategy, a bad guidance can only shorten the expected remaining length of a blame chain: Lemma 4.3. Let i,s∈[0,n]i,s∈[0,n] be two nodes such that i and s are successive nodes in the blame chain in case the bad guidance was used. It holds: [Xi]≥[Xs]. [X_i] [X_s]. Proof 4.4. Proof in Appendix (Subsection C.2). This result directly enable us to contain the nuisance of the bad guidance. We comply with the anytime competitive ratio by simply upper-bounding the costs of the first and last phases of the considered interval by k. Using induction reasonings, we can now derive a result on the expected length of a blame chain and obtain our main claim: Lemma 4.5. Assuming that βτ<1βτ<1, a blame chain has an expected length of at most Hk/(1−βτ)H_k/(1-βτ). Proof 4.6. Proof in Appendix (Subsection C.3). 5 Uniform Metrical Task Systems In metrical task systems (MTS), a metric space (S,d)(S,d) is given, where S is a set of n states and d:S2→ℝ≥0d:S^2 _≥ 0 is a metric distance function. A task is a function r:S→ℝ≥0r:S _≥ 0 that associates each state s∈Ss∈ S with a processing cost r(s)r(s). For a sequence ℛ=r1,…,rmR=r_1,…,r_m of m tasks, we define a solution as a sequence =s1,…,smA=s_1,…,s_m of states si∈Ss_i∈ S, where the solution A is said to serve the task rir_i at state sis_i. We define the cost of a solution A naturally as the sum between the total processing cost and the total transition cost incurred by A, i.e., ()=∑i∈[m]ri(si)+∑i∈[m−1]d(si,si+1) cost(A)= _i∈[m]r_i(s_i)+ _i∈[m-1]d(s_i,s_i+1). In the online problem, the tasks rir_i are given one by one in an online manner and a solution needs to serve task rir_i immediately as it arrives. In this section, we focus on MTS on the uniform metric, i.e., a metric where d satisfies d(s,s′)=1d(s,s )=1 for every pair of distinct states s,s′∈Ss,s ∈ S. We will present an algorithm MTS-DTB that extends the classical online algorithm of Borodin, Linial, and Saks [BorodinLS92] to the OAG model. Before describing MTS-DTB, we recall the notions of phases and saturation from [BorodinLS92]. Towards that goal, we extend the definition of processing cost to continuous time. Concretely, for each discrete time i, we naturally define the processing cost of task rir_i in a (continuous) time interval [t,t′]⊆[i,i+1][t,t ] [i,i+1] as (t′−t)⋅ri(s)(t -t)· r_i(s) for each state s∈Ss∈ S. Consider an MTS instance ℛ=r1,…,rmR=r_1,…,r_m. We define a partition of the (continuous) interval [1,m+1][1,m+1] into sub-intervals [t0=1,t1],[t1,t2],…,[tℓ−1,tℓ=m+1][t_0=1,t_1],[t_1,t_2],…,[t_ -1,t_ =m+1] referred to as phases. Each phase begins with all states being unsaturated. Consider some phase p=[tj,tj+1]p=[t_j,t_j+1]. A state s is said to be saturated for p at time t∈pt∈ p if the total processing cost associated with s during the time interval [tj,t][t_j,t] is at least 11. The phase ends immediately after all states become saturated. Observe that upon the arrival of a task rir_i at (discrete) time i, the algorithm can determine which states will become saturated for the current phase by time i+1i+1. The algorithm. Consider the task rir_i arriving at time i. Let p be the current phase, and let s be the current state of MTS-DTB. We denote by ViV_i the set of valid states in time i and initialize Vi=∅V_i= . If s does not become saturated for p by time i+1i+1, then MTS-DTB sets Vi=sV_i=\s\ (i.e., MTS-DTB stays in state s). Otherwise, if p does not end by time i+1i+1, then MTS-DTB sets ViV_i to be the set of all states that are not saturated at time i+1i+1 (notice that it is guaranteed that Vi≠∅V_i≠ since p does not end by time i+1i+1). Finally, if p ends by time i+1i+1, then MTS-DTB sets Vi=sminV_i=\s_ \ where smins_ is a state that minimizes the processing cost rir_i. Let γi _i be the guidance given to MTS-DTB at time i. If γi∉Vi _i∉ V_i, then MTS-DTB simply chooses a state uniformly at random from ViV_i. Suppose now that γi∉Vi _i∉ V_i. Then, MTS-DTB moves to γi _i with probability τ; and moves to a state chosen uniformly at random from ViV_i otherwise. This completes the description of MTS-DTB. We now analyze its performance. For a trust parameter τ and a bad guidance parameter β, we establish the following. Theorem 5.1. MTS-DTB is 2⋅min1τ(1−β)+1,1−τ(1−τβ)2Hn+1,n2· \ 1τ(1-β)+1, 1-τ(1-τβ)^2H_n+1,n\-competitive anytime in the OAG model. Proof 5.2. Proof in Appendix (Subsection D.1). 6 Conclusion This paper presents advances in our understanding of the usage of machine-learned predictions to reliably solve a given task. We show that any online algorithms can be adapted in a systematic, canonical manner to integrate input predictions. While general, this transformation naturally provides the usual desired properties of learning-augmented algorithms: consistency, robustness, and smoothness. We analyze this transformation on three well-studied problems and show they match, or even beat, state-of-the-art performances. We envision that this framework will be used as a reference point in the future to evaluate learning-augmented algorithms. References Appendix A Related Works A.1 Model Comparison Beyond the aforementioned online algorithms with predictions model of [lykouris2021competitive] and ϵε-accurate predictions model of [gupta2022augmenting], the literature on online decision making includes various other models that also bear certain relations to our OAG model. In particular, the popular online algorithms with advice model, introduced by Emek et al. [EmekFKR2011advice] and Böckenhauer et al. [BoeckenhauerKKKM2017advice] (see [boyar2017online] for a survey), considers online algorithms that receive advice from a fully trustworthy oracle, aiming to minimize the size of the advice. Angelopoulos et al. [angelopoulos2024online] introduced a generalization of the online algorithms with advice model in which the advice may come from an adversarial source, with the objective of optimizing (the equivalent of) the algorithm’s consistency and robustness, while still aiming for small advice. There are also various works on algorithms with “noisy advice”, i.e., the advice is generated by a trusted oracle, however, it is perturbed by some random noise. The problems studied within this framework include maximum independent set [BravermanDSW24], max cut [Cohen-Addadd0LP24], searching in a tree [BoczkowskiFKR21, BoczkowskiFKR25], and spectral clustering [DBLP:journals/corr/abs-2511-17326]. Slightly further away from the current work, the randomly infused advice model of Emek et al. [EmekGP023] performs beyond worst-case analysis of online algorithms by “infusing” an advice generated by a (trusted) oracle into the online algorithm’s random bits; this is related to our OAG model as the advice is infused for each incoming request independently based on a (biased) random coin toss. Elias et al. [EliasKMM2024learning] take an opposite approach from ours and integrate the predictor in the learning problem, so it is no longer a blackbox and can also learn from the input. Finally, Bateni et al. [BateniDJW24] study a setting with queries that can be directed to either an expensive trusted oracle or to a cheaper untrusted oracle. A.2 Problem-Specific Related Work The online bipartite matching problem [DBLP:conf/stoc/KarpVV90] has been intensively studied by the learning-augmented community. So far, the existing literature focused on problem variants such as the random arrival model, initiated in [DBLP:conf/nips/AntoniadisGKK20], and later improved in [DBLP:conf/icml/ChooGL024], the random graph model [DBLP:conf/nips/AamandCI22] or the two-stage arrival model [DBLP:conf/nips/JinM22]. In this paper, we focus on the standard variant as introduced in [DBLP:conf/stoc/KarpVV90] where both the graph and the nodes’ arrivals are adversarial. The online caching problem [Fiat1991CompetitivePA] is probably the most studied online problem in the learning-augmented framework. The seminal paper from Lykouris and Vassilvitskii [lykouris2018] already focused on randomized caching and gave (asymptotic) optimal robustness and consistency bounds. Most notable follow-up works solved more general variants such as the weighted case [bansal2022learning, jiang2022online] while others focused on improving the smoothness bound [rohatgi2020near, DBLP:conf/approx/Wei20]. While our consistency and robustness bounds match the state-of-the-art, our smoothness measure is however not comparable with those existing works. The online metrical task system problem with uniform costs was first introduced and optimaly solved by [BorodinLS92]. It later received the attention of the learning-augmented community in [DBLP:conf/aistats/ChristiansonSW23] who presented optimal robustness and consistency trade-offs for the problem in its general version. Appendix B Proofs and Algorithms for Online Bipartite Matching B.1 Algorithm’s Pseudocode for Online Bipartite Matching Algorithm 1 Ranking-DTB Input: the set V, trust parameter τ∈[0,1]τ∈[0,1] σ←σ← a permutation on V chosen uniformly at random when u∈Uu∈ U and N(u)⊆VN(u) V are revealed do: if |N(u)|>0|N(u)|>0 then r←r← a random number in [0,1][0,1] g←g← the node the guide suggests to match with u if r≤τr≤τ and g∈N(u)g∈ N(u) then Match u with g else Match u with v∈N(u)v∈ N(u) with lowest rank in σ end if end if B.2 Proof of Lemma 3.3 See 3.3 Proof B.1. Fix a ranking σ and fix a guidance sequence γ where the guide thinks the problem instance is (G,π)(G,π). We consider two runs: Ranking-DTB(τ,G,π,σ) Ranking-DTB(τ,G,π,σ) and Ranking-DTB(τ,G′,π,σ) Ranking-DTB(τ,G ,π,σ) under the exact same guidance sequence γ, call M and M′M their respective output matchings. We will show that M′M has a size no greater than M. If M and M′M have equal sizes then the subclaim holds. Otherwise, let C be an alternating chain between M and M′M . We will now show that x is an extremity of C. We define the node u such that “u is the node in U∩CU∩ C with earliest arrival time” (1) We now distinguish between two cases and show that x is an extremity of C in both: either (1) u is matched in both M and M′M or (2) u is matched in one of them and not in the other. We first consider case (1). Then call v∈Vv∈ V and v′∈Vv ∈ V the nodes such that u,v∈M\u,v\∈ M and u,v′∈M′\u,v \∈ M , it holds v≠v′v≠ v by assumption. One of v or v′v was not available to match for one of the matchings M and M′M . Assuming that both v and v′v are nodes of G′G (i.e., v≠xv≠ x and v′≠xv ≠ x), we obtain that one of v or v′v was already matched earlier, contradicting the assumption that u is the node of C∩UC∩ U with earliest arrival time. We deduce that v=xv=x, proving the claim in case (1). We now consider case (2) where u is matched in only one of M or M′M but not in the other. Assuming that u is a node in both G and G′G , then N(u)N(u) was empty at the time u was revealed for the matching that did not match u; calling v∈Vv∈ V the node that is matched with u in the other matching, v was therefore matched earlier which contradicts the assumption that u is the node with earliest arrival time in C. We deduce that u is not in both G and G′G , therefore u=xu=x and x is an extremity of C. As x is an extremity of C, we deduce that |M′∩C|≤|M∩C||M ∩ C|≤|M∩ C|. Finally, we proved that x is an extremity of any alternating chain which implies that there is at most one alternating chain, proving that |M′|≤|M||M |≤|M|. We just showed that for a constant ranking σ and constant guidance sequence γ, the output matching for G′G is no greater than for G. Hence for a constant guidance sequence γ, the expected competitive ratio for G′G is no greater than for G — notice the size of a maximum matching is the same for G and G′G . Finally notice that, going from G to G′G , the good guidance (which we assume blindly suggests to match like M∗M^*) does not change and the bad guidance either does not change (as we assumed so far) or incurs a payoff even lower, the claim follows. B.3 Proof of Lemma 3.6 See 3.6 Proof B.2. Assume that M and Mt,iM_t,i are not equal and that M does not match v. We first show that the first alternating chain (chronologically) starts with v. Let u be the first node of U in the arrival order π that is matched differently in M and Mt,iM_t,i. If the algorithms were following the guidance to match u then they would both match u to the same node as the matchings so far are the same — note that the guide gave the same guidance for both algorithms since they do not have direct access to the rankings. The algorithms therefore do not follow the guidance at the time u arrives, instead they both match according to their respective rankings. Ranking-DTBt,i Ranking-DTB_t,i thus has v as its candidate with lowest rank in N(u)N(u) since it would match u to the same node as Ranking-DTB otherwise: Mt,iM_t,i therefore matches u with v. As M does not match v, v is at an end of an alternating chain, proving the subclaim. We then show that no more than one alternating chain can appear. Let u∈Uu∈ U and assume that an alternating chain has already started when u is revealed. In the case where both algorithm’s executions use the ranking to match u, either both executions match u to the same node, not interfering with the alternating chain, or u is matched in two different ways (possibly matched or not matched) which implies that, in one execution, u is matched to a node that is already part of the alternating chain— except v, all nodes in V have the same pairwise ordering in both rankings, thus only a node that is matched in one ranking but not in the other (hence, the end of an alternating chain) may incur different decisions. Otherwise in the case where both algorithm’s executions use the guidance to match u, either both executions match u to the same node (as the guidance is the same for both executions), the guidance is impossible to follow in one of the executions (same case as before: the other execution matches u with a node part of the alternating chain) or, finally, the guidance is impossible to follow in both executions, both falling back to the ranking (handled by the previous case). B.4 Proof of Lemma 3.8 See 3.8 Proof B.3. Let M be the matching output under σ, let Mt,iM_t,i be the matching output under σt,i _t,i. First we show that, in the output matching under σ, u is matched to a node with rank lower than t. u cannot be matched to a node with rank t as it is v which we assumed is not part of the output matching, otherwise u cannot be matched to a node with rank greater than t as v is available, our first subclaim holds. Then, we show the desired claim. Let u1,u2…ulu_1,u_2… u_l be the nodes in U in reveal order that are matched (or not matched) in different manners under σ and σt,i _t,i. If u is not listed in u1…ulu_1… u_l then the wanted claim directly holds: u is matched to a node with rank lower than t in σ and the rank of that node increases by at most one in σt,i _t,i. In the remainder, we therefore assume that u is listed in u1…ulu_1… u_l. We show that for each i∈[1,l]i∈[1,l], at the reveal time of uiu_i, the set of matching candidates for uiu_i under σt,i _t,i strictly contains the set of matching candidates minus v for uiu_i under σ. We start with the case i=1i=1. When u1u_1 is revealed, the current matching is the same under σ and σt,i _t,i and the set of matching candidates for u1u_1 is the same in both. v is a neighbor of u1u_1 otherwise u1u_1 would be matched similarly under both rankings and the case i=1i=1 holds. We now deal with the case i≥2i≥ 2. As stated in Lemma 3.6, u1…ui−1u_1… u_i-1 are the nodes of U making up the unique alternating chain when uiu_i is revealed; that chain starts with an edge of Mt,iM_t,i and ends with an edge of M linked to ui−1u_i-1. All the internal nodes of that chain are both part of M and Mt,iM_t,i. For uiu_i, the beginning of the chain is a candidate node under σ and the end of the chain is a candidate option under σt,i _t,i. Removing v from the candidate set under σ hence gives the wanted subclaim. We just proved that, removing the option to match v under σ, all the nodes of U that are part of the unique alternating chain (assuming it exists) have a set of matching candidates strictly greater under σt,i _t,i than under σ (in the sense of inclusion). Hence, assuming that v is not matched under σ, u is matched under σt,i _t,i to a node with rank at most t−1t-1 in σ and so at most t in σt,i _t,i. B.5 Proof of Lemma 3.10 See 3.10 Proof B.4. Let v∈Vv∈ V be the random variable equal to the node with rank t, let u=m∗(v)u=m^*(v). Using total probabilities, we distinguish between three cases: when Ranking-DTB decides how to match u, it uses either the good guidance, the bad guidance or the ranking. If the good guidance is used, v is therefore matched with probability one — either Ranking-DTB matches u with v, or v was already matched before. In case the bad guidance happens when u is matched, we simply upper-bound the probability that v is matched by 11, hence the βτβτ term on the right member of our desired claim. The rest of the proof seeks an upper-bound on the probability that v is matched in case the random ranking is used when u is matched. We consider the following alternative process: pick a node v′∈Vv ∈ V uniformly at random, remove it from the ranking σ and put it back in with rank t, call σ′σ the newly obtained ranking. We call u′=m∗(v′)u =m^*(v ) and Ranking-DTB′ Ranking-DTB the algorithm running with ranking σ′σ . Clearly, the probability that v′v is not matched equals 1−xt1-x_t. By Lemma 3.8, the event that v′v is not matched under ranking σ′σ implies that u′u is matched under ranking σ with a node of rank no greater than t. Notice that u′u is independent of σ, so the probability that u′u is matched with a node of rank no greater than t is 1n⋅∑1≤s≤txs 1n· _1≤ s≤ tx_s, giving the desired result. B.6 Proof of Theorem 3.1 See 3.1 Proof B.5. First, notice that Ranking-DTB always outputs a matching that is maximal (i.e., it cannot be augmented greedily) which guarantees a competitive ratio greater than 1/21/2. The rest of the proof shows that the competitive ratio is no lower than (1−βτ)⋅(1−e−(1−τ))/(1−τ)(1-βτ)·(1-e^-(1-τ))/(1-τ). For all i∈⟦n⟧i∈ n we define Si=∑1≤s≤ixiS_i= _1≤ s≤ ix_i. Like in Lemma 3.10, we define xtx_t as the probability the node with rank t in σ is matched (note that σ is a random variable). To start, we prove by induction that, for all i∈⟦n⟧i∈ n it holds: St≥(1−βτ)⋅∑s=1t(1−1−τn+1−τ)s S_t≥(1-βτ)· _s=1^t (1- 1-τn+1-τ )^s The base case for t=1t=1 is obtained simply by rearranging the terms of Lemma 3.10 for t=1t=1. By induction, we assume the result holds for t and show it for t+1t+1. Adding St+1S_t+1 on both sides of Lemma 3.10 for t+1t+1: 1+St≤(1+1−τn)⋅St+1+βτ 1+S_t≤ (1+ 1-τn )· S_t+1+βτ ⟹St+1≥(1−1−τn+1−τ)⋅[(1−βτ)+St] S_t+1≥ (1- 1-τn+1-τ )· [(1-βτ)+S_t ] ≥(1−βτ)⋅∑s=1t+1(1−1−τn+1−τ)s ≥(1-βτ)· _s=1^t+1 (1- 1-τn+1-τ )^s which proves the subclaim by induction. We therefore have that ∑s=1nxs=Sn _s=1^nx_s\ =\ S_n ≥(1−βτ)⋅∑s=1n(1−1−τn+1−τ)s ≥(1-βτ)· _s=1^n (1- 1-τn+1-τ )^s ≥(1−βτ)⋅∑s=1n(1−1−τn)s ≥(1-βτ)· _s=1^n (1- 1-τn )^s =(1−βτ)⋅n⋅1−(1−(1−τ)/n)n+11−τ =(1-βτ)· n· 1-(1-(1-τ)/n)^n+11-τ ≥(1−βτ)⋅n⋅1−e−(1−τ)1−τ ≥(1-βτ)· n· 1-e^-(1-τ)1-τ Noticing that ∑s=1nxs _s=1^nx_s is the expected profit of Ranking-DTB and that an optimal algorithm has profit n ends the proof. Appendix C Proofs and Algorithm for Online Caching C.1 Pseudocode of Marking-DTB Algorithm 2 Marking-DTB Input: cache size k, initial cache content, trust parameter τ∈[0,1]τ∈[0,1] At the beginning, no pages are marked when a request to a page x arrives do: if the requested page is not cached then if the cache is full then r←r← a random number in [0,1][0,1] g←g← the page the guide suggests to evict if r≤τr≤τ and g is cached and non-marked then Evict g else Evict a non-marked page uniformly at random end if end if end if Mark x if there are k marked pages then Unmark all pages end if C.2 Proof of Lemma 4.3 See 4.3 Proof C.1. We prove this by strong induction on i=0,1…ni=0,1… n. The claim holds for i=0i=0. Let i∈[0,n]i∈[0,n], we assume that the induction hypothesis holds for all 0,1…i−10,1… i-1 and show it also holds for i. Let r(n+1−s)r(n+1-s) be the next page after r(n+1−i)r(n+1-i) on the blame chain if the bad guidance was used. It holds: [Xi] [X_i] =1+βτ[Xs]+1−τi⋅∑l=1i−1[Xl]. =1+β [X_s]+ 1-τi·Σ _l=1^i-1E[X_l]. Using the same equality for s and then the induction hypothesis we obtain: [Xs] [X_s] ≤1+βτ[Xs]+1−τs⋅∑l=1s−1[Xl] ≤ 1+β [X_s]+ 1-τs·Σ _l=1^s-1E[X_l] Moreover it holds: 1i⋅∑l=1i−1[Xl]≥1s⋅∑l=1s−1[Xl] 1i·Σ _l=1^i-1E[X_l]≥ 1s·Σ _l=1^s-1E[X_l] as the averaged terms on the left sum are either contained in the right sum or greater (induction hypothesis). Gathering the three previous inequalities gives the desired claim. C.3 Proof of Lemma 4.5 See 4.5 Proof C.2. Consider a blame chain r(0),r(i1)…r(n+1)r(0),r(i_1)… r(n+1). Let p∈[0,n]p∈[0,n] and let r(s)r(s) be the next page after r(p)r(p) in the blame chain in case the bad guidance was used. It holds: [Xp] [X_p] =1+βτ[Xs]+1−τp∑i=1p−1[Xi]. =1+β [X_s]+ 1-τpΣ _i=1^p-1E[X_i]. Using Lemma 4.3 gives: (1−βτ)⋅[Xp] (1-βτ)·E[X_p] ≤1+1−βτp∑i=1p−1[Xi] ≤ 1+ 1-βτpΣ _i=1^p-1E[X_i] We now assume by strong induction that [Xi]≤Hi/(1−βτ)E[X_i]≤ H_i/(1-βτ) for all i∈[1,p−1]i∈[1,p-1] — the base case for i=1i=1 clearly holds. Dividing the previous inequality by (1−βτ)(1-βτ): [Xp] [X_p] ≤11−βτ+1p∑i=1p−1Hi1−βτ ≤ 11-βτ+ 1pΣ _i=1^p-1 H_i1-βτ ⟹[Xp] [X_p] ≤11−βτ+1p⋅(1−βτ)∑i=1p−1p−i ≤ 11-βτ+ 1p·(1-βτ)Σ _i=1^p-1 p-ii ⟹[Xp] [X_p] ≤11−βτ+11−βτ⋅Hp−1−p−1p⋅11−βτ ≤ 11-βτ+ 11-βτ· H_p-1- p-1p· 11-βτ ⟹[Xp] [X_p] ≤Hp1−βτ ≤ H_p1-βτ It therefore holds that [Xn]≤Hn/(1−βτ)≤Hk/(1−βτ)E[X_n]≤ H_n/(1-βτ)≤ H_k/(1-βτ) and the claim follows. C.4 Proof of Theorem 4.1 See 4.1 Proof C.3. We assume that a good guidance suggests to evict the unmarked, cached page that will be requested latest. Let σ be the sequence of requested pages. We define a phase as a subsequence of consecutive requested pages that contains no more than k different pages. We greedily divide σ into phases: starting from the first request, take the longest possible phase, and so on until the end of σ. Let P be a phase, we define: • A clean page is a page that is requested during P but was not cached at the beginning of P. Define C the number of clean pages. • A returning page is a page that is requested during P and was cached at the beginning of P. Define R the number of returning pages. • A vanishing page is a page that is not requested during P and was cached at the beginning of P. There are C vanishing pages. First, notice that Marking-DTB pays no more than k during P, since it pays at most one for each page kind thanks to the marking mechanism. Then, we prove that the expected number of page faults is upper bounded by C/(τ(1−β))C/(τ(1-β)). With probability τ(1−β)τ(1-β), the algorithm uses a good guidance and Marking-DTB evicts a vanishing page. At any given time of P, the number of evictions until the next vanishing page is evicted follows a geometric law of parameter τ(1−β)τ(1-β). As there are C vanishing pages, the expected number of evictions until all vanishing pages are out of the cache is C/(τ(1−β))C/(τ(1-β)), which is an upper bound on the expected cost of Marking-DTB during phase P. Finally, there are C blame chains evolving in parallel, each with an expected length of at most Hk/(1−βτ)H_k/(1-βτ) by Lemma 4.5. The expected number of page faults is therefore no greater than C⋅Hk/(1−βτ)C· H_k/(1-βτ). Meanwhile, an optimal offline algorithm pays an amortized cost of at least C/2C/2 per phase (well-known proof from [Fiat1991CompetitivePA]) and the claim holds. Appendix D Proofs for Online Metrical Task System D.1 Proof of Theorem 5.1 See 5.1 Proof D.1. Consider an arbitrary time interval [t,t′][t,t ] and recall that our goal is to show that MTS-DTB is 2⋅min1τ(1−β)+1,1−τ(1−τβ)2Hn+1,n2· \ 1τ(1-β)+1, 1-τ(1-τβ)^2H_n+1,n\-competitive in this interval. Let p and p′p be the phases in which t and t′t lie, respectively. Observe that the cost paid by MTS-DTB between time t and the end of p as well as the cost between the beginning of p′p and t′t can be attributed to the additive constant. Thus, to complete our analysis, it is left to analyze the competitive ratio in a single (complete) phase. We first observe that any offline algorithm must pay a cost of at least 11 on every phase. Indeed, if an algorithm transitions during a phase, then it pays at least 11 in transition cost. Otherwise, it resided in the same state throughout the phase. By definition, a phase continues until all states become saturated. Thus, any offline algorithm must pay at least 11 in processing cost. It is therefore sufficient to provide an upper bound on the expected cost of MTS-DTB in a single phase p. Notice that by design, MTS-DTB incurs a cost of at most 11 in processing cost for every state it visits during p. This is because MTS-DTB stays in a state only until it becomes saturated. In particular, MTS-DTB incurs a total processing cost of 22 on the first and last states it visits during p. For each intermediate state, MTS-DTB incurs 11 in transition cost and at most 11 in processing cost. Therefore, to complete the analysis it is left to show that the expected number of transitions during p is bounded by min1τ(1−β),1−τ(1−τβ)2Hn,n−1 \ 1τ(1-β), 1-τ(1-τβ)^2H_n,n-1\. We start by showing that the number of transitions during p is at most n−1n-1. To see that, notice that by construction, whenever MTS-DTB transitions, it moves to an unsaturated state for p. Thus, in any transition, the number of unsaturated states decreases. It follows that the number of transitions during p is at most n−1n-1. We now show that the expected number of transitions MTS-DTB makes during p is upper bounded by 1/(τ(1−β))1/(τ(1-β)). To that end, we consider a guide that selects a state s∗s^* with longest time until saturation. Observe that if MTS-DTB transitions to s∗s^* during p, its next transition is only in the next phase. Recall that the probability of receiving non-corrupted guidance at each time i is τ(1−β)τ(1-β). Thus, the expected number of transitions during p is at most 1/(τ(1−β))1/(τ(1-β)). Finally, we need to show that the expected number of transitions in a phase is upper bounded by 1−τ(1−τβ)2Hn 1-τ(1-τβ)^2H_n. We say that a transition round is adversarial if a corrupted guidance is given in that round. Let X1X_1 be a random variable that counts the number of adversarial rounds until the first non-adversarial round. For each i>1i>1, let XiX_i be a random variable that counts the number of adversarial rounds between the (i−1)(i-1)-th and the i-th non-adversarial rounds. Let N be a random variable that counts the total number of non-adversarial rounds in the phase. The goal is now to bound the sum X1+⋯+XNX_1+…+X_N which serves as an upper bound on the number of transitions during the phase. To that end, we note that we can assume w.l.o.g. that N is determined strictly by the randomness of the algorithm. This is because non-adversarial rounds in which a non-corrupted guidance is given can only decrease the value of N (and thus, the sum). Based on this assumption, we get that N and the XiX_i variables are determined based on two independent sources of randomness: the former by the algorithm’s randomness, whereas the latter depends on the random assignment of bad guidance. In particular, N is independent of the random variables XiX_i. Thus, it follows from Wald’s identity that [X1+⋯+XN]=[X1]⋅[N]E[X_1+…+X_N]=E[X_1]·E[N] (here, notice that [X1]=[Xi]E[X_1]=E[X_i] for all i since the XiX_is are identically distributed). Since X1X_1 is a geometric variable with success probability 1−τβ1-τβ, we get [X1]⋅[N]=(1/(1−τβ))[N]E[X_1]·E[N]=(1/(1-τβ))E[N]. It is left to show that [N]≤(1−τ)1−βτHnE[N]≤ (1-τ)1-βτH_n. Denote by νk _k the number of non-adversarial rounds in the phase given that there are k unsaturated states and notice that N=νnN= _n. Clearly, ν1=1 _1=1. For k>1k>1, first note that given that the round is non-adversarial, the probability of moving from k unsaturated states to a state that leaves k−1k-1 unsaturated states (i.e., the state with nearest saturation time) is at most (1/k)(1−τ)(1/k)(1-τ). Now, conditioning on the round being non-adversarial we get a probability bound of (1−τ)1−βτ(1/k) (1-τ)1-βτ(1/k). Based on that, we get the recursive formula νk≤νk−1+(1−τ)1−βτ(1/k) _k≤ _k-1+ (1-τ)1-βτ(1/k). Developing the recurrence for n, we get νn≤(1−τ)1−βτHn _n≤ (1-τ)1-βτH_n which completes the analysis.