Lune

NeurIPS2025Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Robust and Consistent Ski Rental with Distributional AdviceJihwan Kim, Chenglin FanICML 2026 · 1 citation

Builds on16

  1. The Primal-Dual method for Learning Augmented AlgorithmsÉtienne Bamas, Andreas Maggiori, Ola SvenssonNeurIPS 2020 · 171 citations
  2. Secretary and Online Matching Problems with Machine Learned AdviceAntonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel KolevNeurIPS 2020 · 167 citations
  3. Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsAlexander Wei, Fred ZhangNeurIPS 2020 · 129 citations
  4. Online Scheduling via Learned WeightsSilvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei VassilvitskiiSODA 2020 · 83 citations
  5. Online Knapsack with Frequency PredictionsSungjin Im, Ravi Kumar, Mahshid Montazer Qaem, Manish PurohitNeurIPS 2021 · 70 citations

Related papers

  1. Ordinal Secretaries with AdviceHasti Nourmohammadi Sigaroudi, Ying Cao, Bo Sun, Xiaoqi TanAAAI 2026
  2. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-SearchZiyad Benomar, Lorenzo Croissant, Vianney Perchet, Spyros AngelopoulosICML 2025
  3. Overcoming Brittleness in Pareto-Optimal Learning Augmented AlgorithmsAlex Elenter, Spyros Angelopoulos, Christoph Dürr, Yanni LefkiNeurIPS 2024 · 10 citations
  4. Time Fairness in Online Knapsack ProblemsAdam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali et al.ICLR 2024 · 8 citations
  5. Online Search with Best-Price and Query-Based PredictionsSpyros Angelopoulos, Shahin Kamali, Dehou ZhangAAAI 2022 · 11 citations
Dusk over the sea between two cliffs drawn in fine vertical lines