The Pareto Frontier of Randomized Learning-Augmented Online Bidding

Christoph D\"urr; Imrane Saakour; Mathis Degryse; Spyros Angelopoulos

arxiv: 2605.06106 · v2 · submitted 2026-05-07 · 💻 cs.DS

The Pareto Frontier of Randomized Learning-Augmented Online Bidding

Mathis Degryse , Imrane Saakour , Christoph D\"urr , Spyros Angelopoulos This is my paper

Pith reviewed 2026-05-15 07:00 UTC · model grok-4.3

classification 💻 cs.DS

keywords online biddinglearning-augmented algorithmsconsistency-robustness tradeoffrandomized algorithmsPareto frontierbidding functiononline decision making

0 comments

The pith

Randomized bidding strategies achieve matching upper and lower bounds on consistency as a function of robustness when robustness is at least 2.885.

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

The paper analyzes randomized online bidding where an algorithm uses oracle predictions to generate bids over time. It introduces a bidding function abstraction that unifies the design and analysis of all randomized strategies. Using this abstraction the authors derive analytical upper and lower bounds on the optimal consistency C for any given robustness R and show that these bounds coincide exactly once R reaches 2.885. This closes the remaining gap between what was previously achievable and what is provably optimal. A reader would care because the result fully characterizes the Pareto frontier for this prediction-augmented online problem and directly informs algorithm choice in applications such as resource allocation and clustering.

Core claim

The optimal consistency-robustness trade-off for randomized learning-augmented online bidding is completely characterized by matching analytical bounds once robustness R is at least 2.885; the bidding-function abstraction supplies both the upper-bound construction and the matching lower-bound proof.

What carries the argument

The bidding function, a novel abstraction that encodes any randomized bidding strategy as a distribution over bids and enables direct calculation of consistency and robustness values.

If this is right

For all robustness values at or above 2.885 the best possible consistency is now known exactly.
The same bidding-function technique yields explicit algorithms that attain the optimal trade-off.
The framework immediately applies to the incremental median problem and produces measurable improvements in clustering cost.
Any future randomized strategy for this problem cannot beat the identified Pareto curve without violating robustness.

Where Pith is reading between the lines

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

The bidding-function view may transfer to other online decision problems that admit a similar prediction-augmented formulation.
In practice one could tune the robustness parameter to the observed prediction accuracy and obtain near-optimal performance without hand-crafted heuristics.
The matching bounds suggest that further progress would require either weaker robustness definitions or richer prediction models.
The same abstraction could be used to study competitive analysis of randomized algorithms even without machine-learned predictions.

Load-bearing premise

Every possible randomized bidding strategy can be represented by a bidding function and the oracle predictions admit a clean consistency-robustness analysis.

What would settle it

A concrete randomized bidding strategy whose measured consistency lies strictly below the derived lower-bound curve for some robustness value R greater than or equal to 2.885 while still satisfying the robustness guarantee.

Figures

Figures reproduced from arXiv: 2605.06106 by Christoph D\"urr, Imrane Saakour, Mathis Degryse, Spyros Angelopoulos.

**Figure 1.** Figure 1: Consistency–robustness tradeoff for various bidding strategies and different ranges of the view at source ↗

**Figure 2.** Figure 2: Expected normalized cost as function of σ 2 ∈ [0, 4]. 6 Numerical Evaluation We present a numerical evaluation of the performance of our algorithms. We consider the following setup. The oracle outputs a prediction uˆ, and the true threshold u is generated at random according to u = uˆ · exp(η), where η ∼ N (0, σ2 ) represents a Gaussian noise. The variance σ 2 thus captures the prediction error of the orac… view at source ↗

**Figure 3.** Figure 3: Average empirical approximation ratios for the incremental median problem applied to view at source ↗

**Figure 4.** Figure 4: Expected normalized cost as function of σ 2 for R = 3 and R = 2.73. to Fk. Here, we adhere to the original description of the algorithm of [21], where an incremental solution F1 ⊆ F2 ⊆ . . . ⊆ Fn only needs to satisfy |Fi | ≤ i. Another option would have been to fill the sets greedily with points so to satisfy |Fi | = i for all i. The theoretical performance guarantee of the bidding sequence translates to … view at source ↗

**Figure 5.** Figure 5: Average empirical approximation ratios of the incremental median algorithms for different view at source ↗

read the original abstract

Online bidding is a classical problem in online decision-making, with applications in resource allocation, hierarchical clustering, and the analysis of approximation algorithms. We study its randomized learning-augmented variant, where an online algorithm generates a sequence of random bids while leveraging predictions from an oracle. We provide analytical upper and lower bounds on the optimal consistency $C$ as a function of the robustness $R$, which match when $R \geq 2.885$, effectively closing the gap left by previous work. The key technical ingredient is the notion of a bidding function, a novel abstraction that provides a unified framework for the design and analysis of randomized bidding strategies. We complement our theoretical results with an experimental application of randomized bidding to the incremental median problem, demonstrating the applicability of our algorithm in practical clustering settings.

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.

Desk Editor's Note private letter to a colleague

Matching bounds close the consistency-robustness gap for randomized bidding when R >= 2.885 via a new bidding function abstraction, though the abstraction's completeness needs checking.

read the letter

This paper's main contribution is matching analytical upper and lower bounds on the optimal consistency C as a function of robustness R, at least for R at or above 2.885, in the randomized learning-augmented online bidding setting. It closes the gap left by prior work using a bidding function abstraction that unifies the design and analysis of randomized strategies. They also include an experiment applying the approach to the incremental median problem in clustering, which shows the framework can be used in a practical setting like resource allocation or hierarchical clustering. The results are framed as direct analytical comparisons to earlier bounds rather than fitted parameters, and the abstract points to the relevant prior literature on consistency-robustness tradeoffs, so the citations look on target. The abstraction is the key technical move, and it appears to let them derive tight bounds where previous randomized analyses fell short. One soft spot worth checking is whether the bidding function abstraction really captures every possible randomized strategy without loss of generality. If some history-dependent or non-stationary randomization cannot be reduced to this form while preserving the same consistency-robustness pair, then the lower-bound construction only proves tightness inside the abstraction rather than for the absolute best randomized algorithm. The paper presents the abstraction as novel and unifying, so the full proofs should address this directly. This work is aimed at researchers in online algorithms who care about prediction-augmented settings and tight Pareto frontiers. Readers working on bidding problems, resource allocation, or clustering with predictions will get concrete value from the matching bounds and the new framework. It deserves peer review because it supplies analytical progress on a specific open question in the subfield, even if the abstraction claim requires careful scrutiny in the derivations.

Referee Report

1 major / 2 minor

Summary. The paper examines the randomized learning-augmented version of the online bidding problem. It introduces the concept of a bidding function as a novel abstraction for designing and analyzing randomized bidding strategies. The main result is a pair of matching analytical upper and lower bounds on the optimal consistency C in terms of the robustness R, which coincide for all R ≥ 2.885 and thereby close the gap left by earlier work. The theoretical findings are complemented by an experimental evaluation on the incremental median problem, illustrating the approach in a clustering context.

Significance. If the bidding-function abstraction is without loss of generality, the paper delivers the tight Pareto frontier for the consistency-robustness tradeoff in this setting, which constitutes a substantial theoretical advance. The explicit matching of upper and lower bounds for sufficiently large R and the concrete application to incremental median computation are notable strengths. The work provides a unified framework that may prove useful for other online problems with predictions.

major comments (1)

[Section 3 (Bidding Function Abstraction)] The bidding function abstraction is presented as capturing every possible randomized bidding strategy. A rigorous argument is required showing that any history-dependent or non-stationary randomization can be represented in this form without changing the achievable (C, R) pair; otherwise the lower-bound construction only applies inside the restricted class and does not necessarily close the gap for the true optimal randomized algorithm.

minor comments (2)

[Abstract] The numerical threshold 2.885 is given without an indication of whether it is exact or approximate; if it arises from solving an equation, stating the equation would improve precision.
[Experimental Evaluation] The description of the experimental setup for the incremental median problem could include more details on the prediction oracle model and the baseline algorithms used for comparison.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We address the single major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Section 3 (Bidding Function Abstraction)] The bidding function abstraction is presented as capturing every possible randomized bidding strategy. A rigorous argument is required showing that any history-dependent or non-stationary randomization can be represented in this form without changing the achievable (C, R) pair; otherwise the lower-bound construction only applies inside the restricted class and does not necessarily close the gap for the true optimal randomized algorithm.

Authors: We agree that a fully rigorous reduction is required to establish that the bidding-function abstraction is without loss of generality. The current manuscript provides an intuitive justification but does not contain a complete formal argument. In the revised version we will insert a new subsection (3.3) that proves the following: for any (possibly history-dependent and non-stationary) randomized bidding strategy, there exists a bidding function f such that the induced distribution over bids at each step yields identical consistency C and robustness R. The argument proceeds by (i) conditioning the randomization only on the current prediction value and the minimal sufficient statistic of the history (which, for the online-bidding objective, reduces to the current bid level), (ii) showing that any additional history dependence can be averaged out without decreasing the competitive ratios, and (iii) verifying that the resulting f remains a valid probability distribution over bids. Consequently the lower-bound construction applies to the unrestricted class of randomized algorithms, closing the gap for all R ≥ 2.885. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces a bidding function as a novel abstraction for unified analysis of randomized strategies and derives matching analytical upper and lower bounds on optimal consistency C(R) for R ≥ 2.885. No quoted step reduces these bounds to fitted parameters, self-definitions, or load-bearing self-citations by construction; the abstraction is presented as a technical tool enabling the bounds rather than a construct whose completeness is presupposed in the equations. The central claim rests on explicit analytical comparisons to prior work rather than renaming or smuggling inputs, making the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the bidding function abstraction as the key modeling tool and standard assumptions from online algorithms and learning-augmented frameworks.

axioms (1)

domain assumption The bidding function abstraction captures all possible randomized bidding strategies.
Described as the key technical ingredient providing a unified framework.

pith-pipeline@v0.9.0 · 5438 in / 1148 out tokens · 49876 ms · 2026-05-15T07:00:44.907557+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We introduce the notion of a bidding function B:R→R+ … normalized mass ˜B(t):=∫_{t+1}^{-∞} B(x)/B(t) dx … work function wB(t):=∫_t^{-∞} B(x)/B(t) dx … cons(B):=inf_t ˜B(t), rob(B):=sup_t ˜B(t).

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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Optimal Learning-Augmented Algorithm for Online Bidding
cs.DS 2026-05 unverdicted novelty 7.0

A Pareto-optimal randomized learning-augmented algorithm for online bidding is obtained by reducing any algorithm to a bidding profile whose optimal form is characterized by a system of delayed differential equations.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

https://scikit-learn-extra.readthedocs.io/en/stable/modules/ cluster.html#k-medoids]

scikit-learn-extra documentation : Clustering with kmedoids, clara and common-nearest- neighbors, 2019. https://scikit-learn-extra.readthedocs.io/en/stable/modules/ cluster.html#k-medoids]

work page 2019
[2]

Online facility location with multiple advice.Advances in Neural Information Processing Systems, 34:4661–4673, 2021

Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice.Advances in Neural Information Processing Systems, 34:4661–4673, 2021

work page 2021
[3]

A regression approach to learning-augmented online algorithms.Advances in Neural Information Processing Systems, 34:30504–30517, 2021

Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to learning-augmented online algorithms.Advances in Neural Information Processing Systems, 34:30504–30517, 2021. 10

work page 2021
[4]

Online search with a hint.Inf

Spyros Angelopoulos. Online search with a hint.Inf. Comput., 295(Part B):105091, 2023

work page 2023
[5]

Online Computation with Untrusted Advice

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 52:1–52:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020

work page 2020
[6]

Search games with predictions.Operations Research, 2026

Spyros Angelopoulos, Thomas Lidbetter, and Konstantinos Panagiotou. Search games with predictions.Operations Research, 2026

work page 2026
[7]

Learning-augmented online bidding in stochastic settings

Spyros Angelopoulos and Bertrand Simon. Learning-augmented online bidding in stochastic settings. InNeurips, The Thirty-Ninth Annual Conference on Neural Information Processing Systems, 2025

work page 2025
[8]

Secretary and online matching problems with machine learned advice.Advances in Neural Information Processing Systems, 33:7933–7944, 2020

Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice.Advances in Neural Information Processing Systems, 33:7933–7944, 2020

work page 2020
[9]

k-means++: the advantages of careful seeding

David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors,Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027–1035. SIAM, 2007

work page 2007
[10]

On-line load balancing.Online algorithms: the state of the art, pages 178–195, 2005

Yossi Azar. On-line load balancing.Online algorithms: the state of the art, pages 178–195, 2005

work page 2005
[11]

Online graph algorithms with predictions

Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35–66. SIAM, 2022

work page 2022
[12]

Sorting with predictions

Xingjian Bai and Christian Coester. Sorting with predictions. InNeurIPS, 2023

work page 2023
[13]

The primal-dual method for learning augmented algorithms.Advances in Neural Information Processing Systems, 33:20083–20094, 2020

Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms.Advances in Neural Information Processing Systems, 33:20083–20094, 2020

work page 2020
[14]

Anatole Beck and Donald J. Newman. Yet more on the linear search problem.Israel Journal of Mathematics, 8:419–429, 1970

work page 1970
[15]

Pareto- optimality, smoothness, and stochasticity in learning-augmented one-max-search.arXiv preprint arXiv:2502.05720, 2025

Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. Pareto- optimality, smoothness, and stochasticity in learning-augmented one-max-search.arXiv preprint arXiv:2502.05720, 2025

work page arXiv 2025
[16]

On tradeoffs in learning-augmented algorithms

Ziyad Benomar and Vianney Perchet. On tradeoffs in learning-augmented algorithms. In AISTATS, volume 258 ofProceedings of Machine Learning Research, pages 802–810. PMLR, 2025

work page 2025
[17]

Cambridge University Press, 1998

Allan Borodin and Ran El-Yaniv.Online computation and competitive analysis. Cambridge University Press, 1998

work page 1998
[18]

Optimal online algorithms for one-way trading and online knapsack problems: A unified competitive analysis

Ying Cao, Bo Sun, and Danny HK Tsang. Optimal online algorithms for one-way trading and online knapsack problems: A unified competitive analysis. In2020 59th IEEE Conference on Decision and Control (CDC), pages 1064–1069. IEEE, 2020

work page 2020
[19]

Incremental clustering and dynamic information retrieval

Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. InProceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 626–635, 1997. 11

work page 1997
[20]

Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. InAISTATS, volume 206 ofProceedings of Machine Learning Research, pages 9377–9399. PMLR, 2023

work page 2023
[21]

Incremental medians via online bidding.Algorithmica, 50(4):455–478, 2008

Marek Chrobak, Claire Kenyon, John Noga, and Neal E Young. Incremental medians via online bidding.Algorithmica, 50(4):455–478, 2008

work page 2008
[22]

Sigact news online algorithms column 10: Competitiveness via doubling.ACM SIGACT News, 37(4):115–126, 2006

Marek Chrobak and Claire Kenyon-Mathieu. Sigact news online algorithms column 10: Competitiveness via doubling.ACM SIGACT News, 37(4):115–126, 2006

work page 2006
[23]

Hare, David Jeffrey, and Donald Knuth

Robert Corless, Gaston Gonnet, D. Hare, David Jeffrey, and Donald Knuth. On the Lambert W function.Advances in Computational Mathematics, 5:329–359, 01 1996

work page 1996
[24]

Secretaries with advice.Mathematics of Operations Research, 49(2):856–879, 2024

Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice.Mathematics of Operations Research, 49(2):856–879, 2024

work page 2024
[25]

A note on generalized inverses.Mathematical Methods of Operations Research, 77(3):423–432, 2013

Paul Embrechts and Marius Hofert. A note on generalized inverses.Mathematical Methods of Operations Research, 77(3):423–432, 2013

work page 2013
[26]

Online algorithms for rent-or-buy with expert advice

Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. InProceedings of the 36th International Conference on Machine Learning, ICML, volume 97 ofProceedings of Machine Learning Research, pages 2319–2327. PMLR, 2019

work page 2019
[27]

Online knapsack with frequency predictions.Advances in Neural Information Processing Systems, 34:2733–2743, 2021

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions.Advances in Neural Information Processing Systems, 34:2733–2743, 2021

work page 2021
[28]

Online state exploration: Competitive worst case and learning-augmented algorithms

Sungjin Im, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. Online state exploration: Competitive worst case and learning-augmented algorithms. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 333–348. Springer, 2023

work page 2023
[29]

Online schedul- ing via learned weights

Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859–1877. SIAM, 2020

work page 2020
[30]

Optimal Learning-Augmented Algorithm for Online Bidding

Changyeol Lee, Dahoon Lee, Jongseo Lee, Yongho Shin, and Changki Yun. Optimal learning- augmented algorithm for online bidding.arXiv preprint arXiv:2605.07349, April 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[31]

Russell Lee, Bo Sun, Mohammad Hajiesmaili, and John C. S. Lui. Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. InThe 15th ACM International Conference on Future and Sustainable Energy Systems, e-Energy 2024, Singapore, June 4-7, 2024, pages 50–71. ACM, 2024

work page 2024
[32]

Learning augmented binary search trees

Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, pages 13431–13440. PMLR, 2022

work page 2022
[33]

Algorithms with predictions

Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https:// algorithms-with-predictions.github.io/, 2026

work page 2026
[34]

Competitive caching with machine learned advice

Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021

work page 2021
[35]

Mettu and C

Ramgopal R. Mettu and C. Greg Plaxton. The online median problem.SIAM Journal on Computing, 32(3):816–832, 2003

work page 2003
[36]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. InBeyond the Worst-Case Analysis of Algorithms, pages 646–662. Cambridge University Press, 2020. 12

work page 2020
[37]

OpenStreetMap

OpenStreetMap contributors. OpenStreetMap. https://www.openstreetmap.org, 2026. Data accessed 2026. Licensed under the Open Data Commons Open Database License (ODbL) v1.0

work page 2026
[38]

Improving online algorithms via ml predictions.Advances in Neural Information Processing Systems, 31, 2018

Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions.Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[39]

Russell and Shlomo Zilberstein

Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. InProceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pages 212–217, 1991

work page 1991
[40]

Improved learning- augmented algorithms and (tight) lower bounds for multi-option ski rental problem.ACM Transactions on Algorithms, 22(1):1–30, 2025

Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved learning- augmented algorithms and (tight) lower bounds for multi-option ski rental problem.ACM Transactions on Algorithms, 22(1):1–30, 2025

work page 2025
[41]

Pareto- Optimal Learning-Augmented Algorithms for Online Conversion Problems

Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto- Optimal Learning-Augmented Algorithms for Online Conversion Problems. InAdvances in Neural Information Processing Systems, volume 34, pages 10339–10350. Curran Associates, Inc., 2021

work page 2021
[42]

Z u 1 X k∈Z (1[X k < x]−1[X k <1]) dx # =E

Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning- augmented online algorithms. InProceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2020. 13 Appendix A Omitted material from Section 3 Proof of Theorem 1.Foru∈R + we have cost(XB, u) = Z 1 0 X i∈Z B(i+λ)·1[B(i+λ−1)< u] dλ = X i∈Z Z 1 0 ...

work page 2020
[43]

If the sequence( wi)i∈Z converges (either when i→ −∞ , or i→ +∞) towards w∗, then w∗ ∈[w , w]

work page
[44]

If for somek∈Z,w k > worw k < w, thenw k+1 > w k

work page
[45]

Next, we prove these claims:

If for somek∈Z,w k ≥w , thenw k+1 ≥w . Next, we prove these claims:

work page
[46]

Thus the normalized cost at integer points must converge tof(w∗, 1/w∗) = w∗e1/w∗ ≤R

By continuity ofg, w∗ must satisfy that there existsx such that g(w∗, x) = w∗, which gives x = 1 /w∗. Thus the normalized cost at integer points must converge tof(w∗, 1/w∗) = w∗e1/w∗ ≤R. Which givesw ∗ ∈[w , w]by definition of these two values

work page
[47]

Note thatf(wk, 1/wk) > R

Let wk be such a value. Note thatf(wk, 1/wk) > R. We havef(wk, ℓk) ≤R , so ℓk < 1/wk by monotonicity off. Henceg(w k, ℓk) =w k+1 > g(w k,1/w k) =w k, by monotonicity ofg

work page
[48]

Note thatf(w, 1/w) = R≥f (wk, ℓk) ≥f (w, ℓk), hence ℓk ≤ 1/w by monotonicity off

Let wk be such a value. Note thatf(w, 1/w) = R≥f (wk, ℓk) ≥f (w, ℓk), hence ℓk ≤ 1/w by monotonicity off. Sog(w k, ℓk)≥g(w ,1/w ) =w , by monotonicity ofg. Next, we prove that for alli∈Z , wi ≤ w : Suppose, by way of contradiction, that for somek∈Z , wk > w. Then by (2), we have that for everyj≥k , wj < w j+1, hence the sequence(wi)i∈Z is increasing. It i...

work page
[49]

We haveg(w, ℓ1) = w2 ≤ w = g(w, ℓ∗ 1

= w. We haveg(w, ℓ1) = w2 ≤ w = g(w, ℓ∗ 1. Therefore ℓ1 ≥ℓ ∗ 1, so we have˜π(1) = f(w, ℓ1) ≥f (w, ℓ∗ 1). Moreover, introducing ℓ∗ 2 with a similar definition,g(w2, ℓ∗

work page
[50]

= w = g(w, ℓ∗ 1), and sincew2 ≥w , we must haveℓ∗ 2 ≥ℓ ∗ 1, so ℓ2 ≥ℓ ∗ 2 ≥ℓ ∗

work page
[51]

It remains to show the upper bound on the consistency of classI bidding functions

We have˜π(2) =f(w2, ℓ2)≥f(w , ℓ∗ 1). It remains to show the upper bound on the consistency of classI bidding functions. The following lemma will be useful, as it shows that a sequence of slopes can always be extended by the slopes1/ w. Lemma 19.LetR≥e. •IfR≥R 0, there exists aR-robust classIbidding function that achieves consistencyw + 1. • Otherwise, the...

work page 2000

[1] [1]

https://scikit-learn-extra.readthedocs.io/en/stable/modules/ cluster.html#k-medoids]

scikit-learn-extra documentation : Clustering with kmedoids, clara and common-nearest- neighbors, 2019. https://scikit-learn-extra.readthedocs.io/en/stable/modules/ cluster.html#k-medoids]

work page 2019

[2] [2]

Online facility location with multiple advice.Advances in Neural Information Processing Systems, 34:4661–4673, 2021

Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice.Advances in Neural Information Processing Systems, 34:4661–4673, 2021

work page 2021

[3] [3]

A regression approach to learning-augmented online algorithms.Advances in Neural Information Processing Systems, 34:30504–30517, 2021

Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to learning-augmented online algorithms.Advances in Neural Information Processing Systems, 34:30504–30517, 2021. 10

work page 2021

[4] [4]

Online search with a hint.Inf

Spyros Angelopoulos. Online search with a hint.Inf. Comput., 295(Part B):105091, 2023

work page 2023

[5] [5]

Online Computation with Untrusted Advice

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 52:1–52:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020

work page 2020

[6] [6]

Search games with predictions.Operations Research, 2026

Spyros Angelopoulos, Thomas Lidbetter, and Konstantinos Panagiotou. Search games with predictions.Operations Research, 2026

work page 2026

[7] [7]

Learning-augmented online bidding in stochastic settings

Spyros Angelopoulos and Bertrand Simon. Learning-augmented online bidding in stochastic settings. InNeurips, The Thirty-Ninth Annual Conference on Neural Information Processing Systems, 2025

work page 2025

[8] [8]

Secretary and online matching problems with machine learned advice.Advances in Neural Information Processing Systems, 33:7933–7944, 2020

Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice.Advances in Neural Information Processing Systems, 33:7933–7944, 2020

work page 2020

[9] [9]

k-means++: the advantages of careful seeding

David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors,Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027–1035. SIAM, 2007

work page 2007

[10] [10]

On-line load balancing.Online algorithms: the state of the art, pages 178–195, 2005

Yossi Azar. On-line load balancing.Online algorithms: the state of the art, pages 178–195, 2005

work page 2005

[11] [11]

Online graph algorithms with predictions

Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35–66. SIAM, 2022

work page 2022

[12] [12]

Sorting with predictions

Xingjian Bai and Christian Coester. Sorting with predictions. InNeurIPS, 2023

work page 2023

[13] [13]

The primal-dual method for learning augmented algorithms.Advances in Neural Information Processing Systems, 33:20083–20094, 2020

Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms.Advances in Neural Information Processing Systems, 33:20083–20094, 2020

work page 2020

[14] [14]

Anatole Beck and Donald J. Newman. Yet more on the linear search problem.Israel Journal of Mathematics, 8:419–429, 1970

work page 1970

[15] [15]

Pareto- optimality, smoothness, and stochasticity in learning-augmented one-max-search.arXiv preprint arXiv:2502.05720, 2025

Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. Pareto- optimality, smoothness, and stochasticity in learning-augmented one-max-search.arXiv preprint arXiv:2502.05720, 2025

work page arXiv 2025

[16] [16]

On tradeoffs in learning-augmented algorithms

Ziyad Benomar and Vianney Perchet. On tradeoffs in learning-augmented algorithms. In AISTATS, volume 258 ofProceedings of Machine Learning Research, pages 802–810. PMLR, 2025

work page 2025

[17] [17]

Cambridge University Press, 1998

Allan Borodin and Ran El-Yaniv.Online computation and competitive analysis. Cambridge University Press, 1998

work page 1998

[18] [18]

Optimal online algorithms for one-way trading and online knapsack problems: A unified competitive analysis

Ying Cao, Bo Sun, and Danny HK Tsang. Optimal online algorithms for one-way trading and online knapsack problems: A unified competitive analysis. In2020 59th IEEE Conference on Decision and Control (CDC), pages 1064–1069. IEEE, 2020

work page 2020

[19] [19]

Incremental clustering and dynamic information retrieval

Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. InProceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 626–635, 1997. 11

work page 1997

[20] [20]

Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. InAISTATS, volume 206 ofProceedings of Machine Learning Research, pages 9377–9399. PMLR, 2023

work page 2023

[21] [21]

Incremental medians via online bidding.Algorithmica, 50(4):455–478, 2008

Marek Chrobak, Claire Kenyon, John Noga, and Neal E Young. Incremental medians via online bidding.Algorithmica, 50(4):455–478, 2008

work page 2008

[22] [22]

Sigact news online algorithms column 10: Competitiveness via doubling.ACM SIGACT News, 37(4):115–126, 2006

Marek Chrobak and Claire Kenyon-Mathieu. Sigact news online algorithms column 10: Competitiveness via doubling.ACM SIGACT News, 37(4):115–126, 2006

work page 2006

[23] [23]

Hare, David Jeffrey, and Donald Knuth

Robert Corless, Gaston Gonnet, D. Hare, David Jeffrey, and Donald Knuth. On the Lambert W function.Advances in Computational Mathematics, 5:329–359, 01 1996

work page 1996

[24] [24]

Secretaries with advice.Mathematics of Operations Research, 49(2):856–879, 2024

Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice.Mathematics of Operations Research, 49(2):856–879, 2024

work page 2024

[25] [25]

A note on generalized inverses.Mathematical Methods of Operations Research, 77(3):423–432, 2013

Paul Embrechts and Marius Hofert. A note on generalized inverses.Mathematical Methods of Operations Research, 77(3):423–432, 2013

work page 2013

[26] [26]

Online algorithms for rent-or-buy with expert advice

Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. InProceedings of the 36th International Conference on Machine Learning, ICML, volume 97 ofProceedings of Machine Learning Research, pages 2319–2327. PMLR, 2019

work page 2019

[27] [27]

Online knapsack with frequency predictions.Advances in Neural Information Processing Systems, 34:2733–2743, 2021

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions.Advances in Neural Information Processing Systems, 34:2733–2743, 2021

work page 2021

[28] [28]

Online state exploration: Competitive worst case and learning-augmented algorithms

Sungjin Im, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. Online state exploration: Competitive worst case and learning-augmented algorithms. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 333–348. Springer, 2023

work page 2023

[29] [29]

Online schedul- ing via learned weights

Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859–1877. SIAM, 2020

work page 2020

[30] [30]

Optimal Learning-Augmented Algorithm for Online Bidding

Changyeol Lee, Dahoon Lee, Jongseo Lee, Yongho Shin, and Changki Yun. Optimal learning- augmented algorithm for online bidding.arXiv preprint arXiv:2605.07349, April 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026

[31] [31]

Russell Lee, Bo Sun, Mohammad Hajiesmaili, and John C. S. Lui. Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. InThe 15th ACM International Conference on Future and Sustainable Energy Systems, e-Energy 2024, Singapore, June 4-7, 2024, pages 50–71. ACM, 2024

work page 2024

[32] [32]

Learning augmented binary search trees

Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, pages 13431–13440. PMLR, 2022

work page 2022

[33] [33]

Algorithms with predictions

Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https:// algorithms-with-predictions.github.io/, 2026

work page 2026

[34] [34]

Competitive caching with machine learned advice

Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021

work page 2021

[35] [35]

Mettu and C

Ramgopal R. Mettu and C. Greg Plaxton. The online median problem.SIAM Journal on Computing, 32(3):816–832, 2003

work page 2003

[36] [36]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. InBeyond the Worst-Case Analysis of Algorithms, pages 646–662. Cambridge University Press, 2020. 12

work page 2020

[37] [37]

OpenStreetMap

OpenStreetMap contributors. OpenStreetMap. https://www.openstreetmap.org, 2026. Data accessed 2026. Licensed under the Open Data Commons Open Database License (ODbL) v1.0

work page 2026

[38] [38]

Improving online algorithms via ml predictions.Advances in Neural Information Processing Systems, 31, 2018

Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions.Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[39] [39]

Russell and Shlomo Zilberstein

Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. InProceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pages 212–217, 1991

work page 1991

[40] [40]

Improved learning- augmented algorithms and (tight) lower bounds for multi-option ski rental problem.ACM Transactions on Algorithms, 22(1):1–30, 2025

Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved learning- augmented algorithms and (tight) lower bounds for multi-option ski rental problem.ACM Transactions on Algorithms, 22(1):1–30, 2025

work page 2025

[41] [41]

Pareto- Optimal Learning-Augmented Algorithms for Online Conversion Problems

Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto- Optimal Learning-Augmented Algorithms for Online Conversion Problems. InAdvances in Neural Information Processing Systems, volume 34, pages 10339–10350. Curran Associates, Inc., 2021

work page 2021

[42] [42]

Z u 1 X k∈Z (1[X k < x]−1[X k <1]) dx # =E

Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning- augmented online algorithms. InProceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2020. 13 Appendix A Omitted material from Section 3 Proof of Theorem 1.Foru∈R + we have cost(XB, u) = Z 1 0 X i∈Z B(i+λ)·1[B(i+λ−1)< u] dλ = X i∈Z Z 1 0 ...

work page 2020

[43] [43]

If the sequence( wi)i∈Z converges (either when i→ −∞ , or i→ +∞) towards w∗, then w∗ ∈[w , w]

work page

[44] [44]

If for somek∈Z,w k > worw k < w, thenw k+1 > w k

work page

[45] [45]

Next, we prove these claims:

If for somek∈Z,w k ≥w , thenw k+1 ≥w . Next, we prove these claims:

work page

[46] [46]

Thus the normalized cost at integer points must converge tof(w∗, 1/w∗) = w∗e1/w∗ ≤R

By continuity ofg, w∗ must satisfy that there existsx such that g(w∗, x) = w∗, which gives x = 1 /w∗. Thus the normalized cost at integer points must converge tof(w∗, 1/w∗) = w∗e1/w∗ ≤R. Which givesw ∗ ∈[w , w]by definition of these two values

work page

[47] [47]

Note thatf(wk, 1/wk) > R

Let wk be such a value. Note thatf(wk, 1/wk) > R. We havef(wk, ℓk) ≤R , so ℓk < 1/wk by monotonicity off. Henceg(w k, ℓk) =w k+1 > g(w k,1/w k) =w k, by monotonicity ofg

work page

[48] [48]

Note thatf(w, 1/w) = R≥f (wk, ℓk) ≥f (w, ℓk), hence ℓk ≤ 1/w by monotonicity off

Let wk be such a value. Note thatf(w, 1/w) = R≥f (wk, ℓk) ≥f (w, ℓk), hence ℓk ≤ 1/w by monotonicity off. Sog(w k, ℓk)≥g(w ,1/w ) =w , by monotonicity ofg. Next, we prove that for alli∈Z , wi ≤ w : Suppose, by way of contradiction, that for somek∈Z , wk > w. Then by (2), we have that for everyj≥k , wj < w j+1, hence the sequence(wi)i∈Z is increasing. It i...

work page

[49] [49]

We haveg(w, ℓ1) = w2 ≤ w = g(w, ℓ∗ 1

= w. We haveg(w, ℓ1) = w2 ≤ w = g(w, ℓ∗ 1. Therefore ℓ1 ≥ℓ ∗ 1, so we have˜π(1) = f(w, ℓ1) ≥f (w, ℓ∗ 1). Moreover, introducing ℓ∗ 2 with a similar definition,g(w2, ℓ∗

work page

[50] [50]

= w = g(w, ℓ∗ 1), and sincew2 ≥w , we must haveℓ∗ 2 ≥ℓ ∗ 1, so ℓ2 ≥ℓ ∗ 2 ≥ℓ ∗

work page

[51] [51]

It remains to show the upper bound on the consistency of classI bidding functions

We have˜π(2) =f(w2, ℓ2)≥f(w , ℓ∗ 1). It remains to show the upper bound on the consistency of classI bidding functions. The following lemma will be useful, as it shows that a sequence of slopes can always be extended by the slopes1/ w. Lemma 19.LetR≥e. •IfR≥R 0, there exists aR-robust classIbidding function that achieves consistencyw + 1. • Otherwise, the...

work page 2000