mlsanityData to 14 Oct 2026

Learning-Augmented Online Bidding in Stochastic Settings

arXiv 2510.25582 ↗First posted 29 Oct 2025cs.GT cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 24 of its 52 references that are in the map. First posted on arXiv 29 Oct 2025.

Builds on

24 of 52 references.

References · 24

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  3. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  4. 2024Improving Online Algorithms via ML Predictionscited by 66
  5. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  6. 2019Online Computation with Untrusted Advicecited by 42
  7. 2020Secretaries with Advicecited by 41
  8. 2022Learning Augmented Binary Search Treescited by 31
  9. 2021Online Graph Algorithms with Predictionscited by 25
  10. 2021Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problemscited by 19
  11. 2023Sorting with Predictionscited by 14
  12. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
12 more
  1. 2024Binary Search with Distributional Predictionscited by 11
  2. 2022Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Marketscited by 9
  3. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  4. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  5. 2020Online Search With a Hintcited by 7
  6. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  7. 2020Contract Scheduling With Predictionscited by 5
  8. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  9. 2024Search Games with Predictionscited by 2
  10. 2024Barely Random Algorithms and Collective Metrical Task Systemscited by 2
  11. 2025With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Designcited by 2
  12. 2021Competitive Sequencing with Noisy Advicecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0
  2. 2026Learning-Augmented and Randomized Algorithms for Line Aggregation with Delayscited by 0
  3. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0