Learning-Augmented Online Bidding in Stochastic Settings
This work addresses online bidding problems for applications like interruptible systems, offering incremental improvements over prior deterministic and non-stochastic methods.
The paper tackles online bidding by introducing learning-augmented algorithms that incorporate stochasticity in predictions or randomization, achieving Pareto-optimal tradeoffs between consistency and robustness.
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.