pith. sign in

arxiv: 2302.05366 · v5 · submitted 2023-02-10 · 💻 cs.DS

Online Algorithms with Randomly Infused Advice

Yuval Emek , Yuval Gil , Maciej Pacut , Stefan Schmid This is my paper

Pith reviewed 2026-05-24 09:18 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmsrandomly infused advicecompetitive analysispagingmetrical task systemsset coveradvice models
0
0 comments X

The pith

Infusing advice into the random bits buffer improves the competitive ratio of classic online algorithms as the infusion probability alpha grows.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces randomly infused advice, a method that lets an omniscient but unreliable oracle write advice directly into the random-bits buffer an online algorithm already uses. Each round the infusion succeeds with probability alpha independently; otherwise the buffer holds fresh random bits as usual. This interface is applied without modifying the algorithms themselves to the problems of paging, uniform metrical task systems, and online set cover. For each problem the authors derive new upper bounds on competitive ratio that become tighter as alpha increases, together with matching or nearly matching lower bounds. The approach quantifies how partial, probabilistic advice affects performance while remaining inside the standard online model with no distributional assumptions on the input.

Core claim

By writing advice generated by an omniscient but unreliable oracle into the random-bits buffer B with success probability alpha per round, classic online algorithms for paging, uniform metrical task systems, and online set cover achieve competitive ratios that improve as alpha increases; new upper bounds are established and complemented by often tight lower bounds on the competitive ratio of any online algorithm under randomly infused advice.

What carries the argument

Randomly infused advice (RIA), the mechanism that overwrites the random-bits buffer with oracle advice independently each round with fixed probability alpha.

If this is right

  • The competitive ratio for paging decreases monotonically as alpha increases from 0 to 1.
  • Uniform metrical task systems exhibit the same monotonic improvement in competitive ratio with alpha.
  • Online set cover likewise obtains tighter competitive ratios as alpha grows.
  • Lower bounds often match the derived upper bounds, establishing tightness for the three problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same infusion interface could be applied to other randomized online algorithms to obtain alpha-dependent bounds without redesigning the algorithms.
  • Knowing alpha in advance might allow an algorithm to allocate more or less of its buffer usage to the infused advice.
  • RIA provides a continuous interpolation between fully random and fully advised regimes inside the existing competitive-analysis framework.

Load-bearing premise

The oracle writes its advice directly into the random-bits buffer that the algorithm already reads, and each round the infusion succeeds independently with probability alpha.

What would settle it

An input sequence and value of alpha for which the competitive ratio of one of the three classic algorithms does not decrease when alpha is increased, or for which the stated upper bound is violated.

read the original abstract

We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any probabilistic assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer B from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 {\le} {\alpha} {\le} 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - {\alpha}, then the buffer B contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter {\alpha} increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces Randomly Infused Advice (RIA), a model in which an omniscient but unreliable oracle writes advice directly into the random-bits buffer B of an existing randomized online algorithm, succeeding independently each round with probability alpha (otherwise fresh random bits are supplied). The authors apply RIA to three classic problems—paging, uniform metrical task systems, and online set cover—claiming new upper bounds on the competitive ratio of standard algorithms that improve monotonically with alpha, together with (often tight) lower bounds on the competitive ratio of any RIA-augmented online algorithm for the same problems.

Significance. If the claimed bounds are correct, the work supplies a clean, non-intrusive interface for interpolating between fully adversarial (alpha=0) and fully advised (alpha=1) regimes while preserving the original algorithm. The explicit parameter alpha and the fact that the interface re-uses the existing random-bit buffer make the model easy to apply to other randomized online algorithms; the three concrete applications demonstrate that the approach yields non-trivial quantitative improvements without requiring new algorithm design.

major comments (2)
  1. [Abstract / Introduction] The abstract and introduction assert that upper bounds improving with alpha exist for the three problems, yet the provided text supplies no proof sketches, potential-function arguments, or explicit competitive-ratio expressions (e.g., no analogue of the classic k-competitive paging bound expressed as a function of alpha). Without these derivations it is impossible to verify that the claimed improvement is not an artifact of the mixture model.
  2. [Abstract] The lower-bound statements are described as “often tight,” but the text does not indicate whether the matching lower bounds hold for every alpha in [0,1] or only at the endpoints; a concrete statement of the functional dependence on alpha is required to assess tightness.
minor comments (1)
  1. [Abstract] The notation for the infusion success probability is introduced as both “alpha” and “{alpha}”; a single consistent symbol should be used throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need for greater explicitness in the abstract and introduction. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / Introduction] The abstract and introduction assert that upper bounds improving with alpha exist for the three problems, yet the provided text supplies no proof sketches, potential-function arguments, or explicit competitive-ratio expressions (e.g., no analogue of the classic k-competitive paging bound expressed as a function of alpha). Without these derivations it is impossible to verify that the claimed improvement is not an artifact of the mixture model.

    Authors: The full technical sections (3–5) contain the complete derivations, including the explicit competitive-ratio expressions as functions of α and the associated potential-function arguments for each of the three problems. However, we agree that the abstract and introduction would benefit from a concise statement of these expressions (e.g., the α-dependent paging bound) so that the improvement is immediately verifiable. We will add a short paragraph to the introduction summarizing the functional forms and a one-sentence statement to the abstract. revision: yes

  2. Referee: [Abstract] The lower-bound statements are described as “often tight,” but the text does not indicate whether the matching lower bounds hold for every alpha in [0,1] or only at the endpoints; a concrete statement of the functional dependence on alpha is required to assess tightness.

    Authors: We will replace the phrase “often tight” with an explicit per-problem statement of the α-range on which each lower bound is tight (full interval for some problems, endpoints only for others). This clarification will be inserted both in the abstract and in the introduction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces the RIA model by explicitly defining how advice is written into the existing random-bits buffer B with independent per-round success probability alpha (0 ≤ α ≤ 1), without any probabilistic input assumptions or new algorithm design. It then applies this interface to classic randomized algorithms for paging, uniform metrical task systems, and online set cover, deriving competitive-ratio upper bounds that improve with alpha and matching lower bounds. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or model description; the bounds follow directly from the mixture of advised and fresh bits under the stated interface. The central claims are therefore independent of the inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claim rests on the probabilistic model of independent per-round infusions and the assumption that writing into the existing random-bits buffer is a valid non-intrusive interface.

free parameters (1)
  • alpha
    Infusion success probability per round; treated as an exogenous parameter that tunes the competitive ratio.
axioms (1)
  • standard math Independent Bernoulli trials govern whether advice is infused each round.
    Used to model oracle reliability without further justification in the abstract.
invented entities (1)
  • Randomly Infused Advice (RIA) interface no independent evidence
    purpose: Augment existing randomized online algorithms with partial reliable advice via the random-bits buffer.
    New model introduced by the paper; no independent evidence supplied.

pith-pipeline@v0.9.0 · 5839 in / 1170 out tokens · 21354 ms · 2026-05-24T09:18:23.577422+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 2 internal anchors

  1. [1]

    10 Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In11th Innovations in Theoretical Computer Science Conference, ITCS 2020 (ITCS) , volume 151, pages 52:1–52:15,

    work page 2020

  2. [2]

    Online metric algorithms with untrusted predictions

    11 Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. InProceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event , volume 119 of Proceedings of Machine Learning Research, pages 345–355. PMLR,

    work page 2020

  3. [3]

    The primal-dual method for learning augmented algorithms

    12 Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. InAdvances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020 ,

    work page 2020

  4. [4]

    Learning- augmented weighted paging

    13 Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning- augmented weighted paging. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022 , pages 67–89. SIAM,

    work page 2022

  5. [5]

    Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias- Dimitriadis

    27 José R. Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias- Dimitriadis. The secretary problem with independent sampling. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 2047–2058. SIAM,

    work page 2021

  6. [6]

    Online Algorithms with Randomly Infused Advice

    31 Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online algorithms with randomly infused advice. CoRR, abs/2302.05366,

    work page internal anchor Pith review Pith/arXiv arXiv

  7. [7]

    URL:https://doi.org/10.48550/arXiv.2302. 05366. 32 Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms.J. Algorithms, 12(4):685–699,

    work page internal anchor Pith review doi:10.48550/arxiv.2302

  8. [8]

    Online algorithms for weighted paging with predictions

    37 Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, volume 168 ofLIPIcs, pages 69:1–69:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2020

  9. [9]

    39 Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke

    URL: https://doi.org/10.1017/9781108637435.031. 39 Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. Randomized online algorithms with high probability guarantees. In31st International Symposium on Theoretical Aspects of Computer Science (STACS) , volume 25, pages 470–481,

    work page doi:10.1017/9781108637435.031

  10. [10]

    Improving online algorithms via ML predictions

    46 Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , pages 9684–9693,

    work page 2018

  11. [11]

    Near-optimal bounds for online caching with machine learned advice

    49 Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 , pages 1834–1845. SIAM,

    work page 2020

  12. [12]

    Sleator and Robert E

    50 Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM , 28(2):202–208, 1985.doi:10.1145/2786.2793. 51 Jeffery R. Westbrook. Randomized algorithms for multiprocessor page migration.SIAM J. Comput., 23(5):951–965,

    work page doi:10.1145/2786.2793 1985

  13. [13]

    53 Neal E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525–541, 1994.doi:10.1007/BF01189992. ,

    work page doi:10.1007/bf01189992 1994