Learning-Augmented Online Bidding in Stochastic Settings
Spyros Angelopoulos, Bertrand Simon
Abstract
Online bidding is a classic optimization problem, with several applications in online decision-making, the design of interruptible systems, and the analysis of approximation algorithms. In this work, we study online bidding under learning-augmented settings that incorporate stochasticity, in either the prediction oracle or the algorithm itself. In the first part, we study bidding under distributional predictions, and find Pareto-optimal algorithms that offer the best-possible tradeoff between the consistency and the robustness of the algorithm. In the second part, we study the power and limitations of randomized bidding algorithms, by presenting upper and lower bounds on the consistency/robustness tradeoffs. Previous works focused predominantly on oracles that do not leverage stochastic information on the quality of the prediction, and deterministic algorithms.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- The Primal-Dual method for Learning Augmented Algorithms cites Online Scheduling via Learned Weights
- Online Knapsack with Frequency Predictions cites The Primal-Dual method for Learning Augmented Algorithms
- Online Knapsack with Frequency Predictions cites Online Scheduling via Learned Weights
- Online Knapsack with Frequency Predictions cites Secretary and Online Matching Problems with Machine Learned Advice
- Secretary and Online Matching Problems with Machine Learned Advice cites Online Scheduling via Learned Weights
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms cites Online Scheduling via Learned Weights
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms cites Secretary and Online Matching Problems with Machine Learned Advice
- Robust and Consistent Ski Rental with Distributional Advice cites The Primal-Dual method for Learning Augmented Algorithms
- Robust and Consistent Ski Rental with Distributional Advice cites Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
Cited by top-tier papers1
Builds on16
- The Primal-Dual method for Learning Augmented AlgorithmsÉtienne Bamas, Andreas Maggiori, Ola SvenssonNeurIPS 2020 · 171 citations
- Secretary and Online Matching Problems with Machine Learned AdviceAntonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel KolevNeurIPS 2020 · 167 citations
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsAlexander Wei, Fred ZhangNeurIPS 2020 · 129 citations
- Online Scheduling via Learned WeightsSilvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei VassilvitskiiSODA 2020 · 83 citations
- Online Knapsack with Frequency PredictionsSungjin Im, Ravi Kumar, Mahshid Montazer Qaem, Manish PurohitNeurIPS 2021 · 70 citations
Related papers
- Ordinal Secretaries with AdviceHasti Nourmohammadi Sigaroudi, Ying Cao, Bo Sun, Xiaoqi TanAAAI 2026
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-SearchZiyad Benomar, Lorenzo Croissant, Vianney Perchet, Spyros AngelopoulosICML 2025
- Overcoming Brittleness in Pareto-Optimal Learning Augmented AlgorithmsAlex Elenter, Spyros Angelopoulos, Christoph Dürr, Yanni LefkiNeurIPS 2024 · 10 citations
- Time Fairness in Online Knapsack ProblemsAdam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali et al.ICLR 2024 · 8 citations
- Online Search with Best-Price and Query-Based PredictionsSpyros Angelopoulos, Shahin Kamali, Dehou ZhangAAAI 2022 · 11 citations
