Learning-Augmented Online Bidding in Stochastic Settings

• URL: http://arxiv.org/abs/2510.25582v1
• Date: Wed, 29 Oct 2025 14:47:18 GMT
• Title: Learning-Augmented Online Bidding in Stochastic Settings
• Authors: Spyros Angelopoulos, Bertrand Simon,
• Abstract summary: We study online bidding under learning-augmented settings that incorporate either the prediction oracle or the algorithm itself.<n>In the first part, we study bidding under robustnessal predictions, and find algorithms that offer the best-possible tradeoff between the consistency and the distribution of the algorithm.<n>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.
• Score: 34.40612230021777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Prediction-Specific Design of Learning-Augmented Algorithms [10.918779264590297]
  We show that prediction-specific performance criteria can enable significant performance improvements over coarser notions of consistency and robustness.<n>We develop a general bi-level optimization framework that enables systematically designing strongly-optimal algorithms.<n>Our results demonstrate that prediction-specific, strongly-optimal algorithms can significantly improve performance across a variety of online decision-making settings.
  arXiv  Detail & Related papers  (2025-10-16T17:06:53Z)
• Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms [8.793721044482613]
  We introduce approaches based on both deterministic measures and measures that balance the trade-off between the algorithm's incomparable performance and the risk associated with the imperfect oracle.<n>We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling.
  arXiv  Detail & Related papers  (2025-01-29T15:16:27Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  We propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. We apply this new approach to a well-studied online problem, namely the one-way trading problem.
  arXiv  Detail & Related papers  (2024-08-07T23:15:21Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box. In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
  arXiv  Detail & Related papers  (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
  arXiv  Detail & Related papers  (2023-01-30T13:17:15Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  We introduce a general design approach for algorithms that learn predictors. We apply techniques from online learning to learn against adversarial instances, tune robustness-consistency trade-offs, and obtain new statistical guarantees. We demonstrate the effectiveness of our approach at deriving learning algorithms by analyzing methods for bipartite matching, page migration, ski-rental, and job scheduling.
  arXiv  Detail & Related papers  (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  We extend the primal-dual method for online algorithms to incorporate predictions that advise the online algorithm about the next action to take. We show that our algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.
  arXiv  Detail & Related papers  (2020-10-22T11:58:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
  arXiv  Detail & Related papers  (2020-10-22T04:51:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.