The Pareto Frontier of Randomized Learning-Augmented Online Bidding
Mathis Degryse, Imrane Zaakour, Christoph Dürr, Spyros Angelopoulos · 2026
Read The Pareto Frontier of Randomized Learning-Augmented Online Bidding by Mathis Degryse, Imrane Zaakour, Christoph Dürr, Spyros Angelopoulos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06106.txt.
Introduction
Mathis Degryse and three co-authors close a gap in the theory of learning augmented online bidding. In online bidding, an algorithm raises bids step by step for tasks such as resource allocation and clustering. The learning augmented version also hears predictions from an oracle, and quality is judged by consistency when predictions are good versus robustness when they are bad.
The authors derive matching upper and lower bounds on the best consistency for each robustness level above a stated threshold. Their key device is the bidding function, an abstraction that unifies how randomized bidding strategies are designed and analyzed. That device simplifies proofs that earlier work had left open. They also apply randomized bidding to the incremental median problem, showing the method works in a practical clustering setting.
Catalog record
| CREATOR | Mathis Degryse, Imrane Zaakour, Christoph Dürr, Spyros Angelopoulos |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06106
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Pareto Frontier of Randomized Learning-Augmented Online Bidding Mathis Degryse, Imrane Zaakour, Christoph Dürr, Spyros Angelopoulos 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 C as a function of the robustness R R , which match when R ≥ 2.885 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. 1 Introduction In several sequential decision-making settings, the algorithm relies on increasing a quantity until it reaches a level that guarantees success, without knowing that threshold in advance. For instance, a scheduler may gradually increase the runtime allocated to a job until it finishes, or an algorithm may successively guess larger values of an unknown optimum until feasibility is reached. In such settings, all unsuccessful choices contribute to the total cost, hence the performance of the algorithm depends on how quickly it reaches the threshold without excessive overshooting. Online bidding [ 20 ] provides a simple abstraction of this fundamental tradeoff. In this problem, a player submits an increasing sequence of bids until one of them reaches or exceeds an unknown threshold u , and pays the sum of all bids made up to that point. The objective is to design a bidding strategy whose total cost is as small as possible relative to the unknown threshold. Formally, in the deterministic setting, the player produces an increasing sequence 1 1 1 As in previous work on online bidding and related incremental allocation problems, we consider bi-infinite sequences. This convention simplifies exposition and avoids additional technical assumptions, such as requiring that u be at least as large as the first bid. X=(x_{i})_{i\in\mathbb{Z}} , and given a threshold u it incurs cost equal to \operatorname{cost}(X,u)=\sum_{j\leq i}x_{j}\text{ for $i$ such that }x_{i-1}<u\leq x_{i}. The normalized cost of X is then defined as \operatorname{nc}(X,u)=\operatorname{cost}(X,u)/u . For simplicity, we will use the notation \operatorname{nc}(u) when X is implied from context. In the randomized setting, X is an increasing sequence of random bids, and the cost of X on a threshold u is measured by its expected value. Under the standard framework of competitive analysis [ 16 ] , the objective is to minimize the worst-case normalized ratio, i.e., when the threshold is chosen adversarially. In practice, however, the algorithm may have access to additional information in the form of a prediction , obtained from historical data or learned models. This has motivated the study of learning-augmented algorithms [ 35 ] , where a prediction oracle is incorporated into the design and analysis of the algorithm. The goal is to leverage such predictions to obtain significantly improved performance when they are accurate, while still retaining strong worst-case guarantees when they are not. We consider a natural oracle which provides the algorithm with a prediction \hat{u} . In this context, the consistency and the robustness of a bidding strategy are defined as its worst-case normalized cost, assuming error-free or adversarial predictions, respectively. Formally \operatorname{cons}(X)=\operatorname{nc}(X,\hat{u}),\quad\text{and}\quad\operatorname{rob}(X)=\sup_{u}\operatorname{nc}(X,u). (1) A natural goal is to design algorithms that achieve the optimal tradeoff between consistency and robustness; in the learning-augmented literature, such algorithms are often called Pareto-optimal . While this question has been answered for deterministic online bidding [ 3 ] , it remains open in the randomized setting. Randomization is known to improve performance even in the classical setting without predictions: the optimal randomized competitive ratio is e [ 20 ] , compared to the optimal deterministic ratio of 4 [ 13 ] . This naturally raises the question of how much randomization can improve learning-augmented bidding. In this work, we quantify this improvement by characterizing the best-possible tradeoff achievable by randomized algorithms. 1.1 Contributions We present and analyze an algorithm that is R -robust for all R\geq e , and provably attains the optimal consistency 2 2 2 During the preparation of this manuscript, we became aware of concurrent independent work by C. Lee et al. [ 29 ] that obtains a similar result. for all R\geq 2/\ln 2\approx 2.885 . For the remaining, and very narrow regime R\in[e,2.885] , we derive analytical upper and lower bounds which significantly improve upon the state of the art of [ 5 , 40 ] . In particular, for R=e+\varepsilon and \varepsilon\to 0 , the consistency of our algorithm is C=e-\Omega(\varepsilon^{1/4}) , improving upon the previously known guarantee of C=e-\Omega(\varepsilon) . Our lower bound, which is tight for R\geq 2.885 , also yields improved impossibility guarantees throughout the regime R\in[e,2.885] . Figure 1 illustrates the obtained results and their comparison to previous work. We complement our theoretical analysis with a numerical evaluation that explicitly incorporates prediction error . This study shows that our algorithm achieves improved smoothness , namely a more graceful degradation in performance as prediction quality deteriorates, compared to previous approaches. Finally, we present an experimental application to the classical incremental median problem, demonstrating that randomized online bidding can yield significant practical improvements in clustering settings, even under highly inaccurate predictions. From a technical perspective, our design and analysis rely on a new abstraction that we call a bidding function . This framework shifts the focus from discrete, randomized sequences to the analysis of continuous functions, providing substantially greater flexibility in both algorithm design and lower-bound arguments. In particular, it enables a more systematic treatment of consistency–robustness tradeoffs than previous sequence-based approaches. A useful parallel can be drawn with online conversion problems, where threshold functions have played a central role in the development of improved algorithms, and in unifying the analysis of several online problems [ 17 , 41 ] . 1.2 Related Work Learning-augmented algorithms Algorithms augmented with a machine-learned prediction on some unknown aspect of the input have been studied in a large variety of online problems, such as rent-and-buy problems [ 25 ] , scheduling [ 28 ] , caching [ 33 ] , matching [ 7 ] , packing [ 26 ] , covering [ 12 ] , sorting [ 11 ] , graph problems [ 9 ] , optimal stopping [ 23 ] and data structures [ 31 ] . These are only some representative works, and since the seminal works [ 33 , 37 ] the field has experienced a remarkable growth; we refer to the online compendium [ 32 ] for a listing of several recent works. The analysis of learning-augmented algorithms is intricate. Several works have focused on tradeoffs between the consistency (i.e., the performance of the algorithm assuming error-free prediction) and the robustness (i.e., the performance under adversarial prediction). Tradeoffs for deterministic algorithms have been studied for a variety of problems, e.g. [ 41 , 30 , 6 , 12 , 1 , 14 ] , often