Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets

• URL: http://arxiv.org/abs/2211.06567v2
• Date: Tue, 27 Feb 2024 21:19:08 GMT
• Title: Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
• Authors: Russell Lee, Bo Sun, Mohammad Hajiesmaili, John C.S. Lui
• Abstract summary: This paper develops learning-augmented algorithms for energy trading in volatile electricity markets. We incorporate machine-learned predictions to design competitive algorithms for online search problems.
• Score: 32.50099216716867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper develops learning-augmented algorithms for energy trading in volatile electricity markets. The basic problem is to sell (or buy) $k$ units of energy for the highest revenue (lowest cost) over uncertain time-varying prices, which can framed as a classic online search problem in the literature of competitive analysis. State-of-the-art algorithms assume no knowledge about future market prices when they make trading decisions in each time slot, and aim for guaranteeing the performance for the worst-case price sequence. In practice, however, predictions about future prices become commonly available by leveraging machine learning. This paper aims to incorporate machine-learned predictions to design competitive algorithms for online search problems. An important property of our algorithms is that they achieve performances competitive with the offline algorithm in hindsight when the predictions are accurate (i.e., consistency) and also provide worst-case guarantees when the predictions are arbitrarily wrong (i.e., robustness). The proposed algorithms achieve the Pareto-optimal trade-off between consistency and robustness, where no other algorithms for online search can improve on the consistency for a given robustness. Further, we extend the basic online search problem to a more general inventory management setting that can capture storage-assisted energy trading in electricity markets. In empirical evaluations using traces from real-world applications, our learning-augmented algorithms improve the average empirical performance compared to benchmark algorithms, while also providing improved worst-case performance.

Related papers

• Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems [0.0]
  This paper presents algorithms with machine learning predictions for the Online Bounded Allocation and the Online Ad-Auctions problems. We constructed primal-dual algorithms that achieve competitive performance depending on the quality of the predictions.
  arXiv  Detail & Related papers  (2024-02-13T13:02:11Z)
• Learning-augmented Online Algorithm for Two-level Ski-rental Problem [8.381344684943212]
  We study the two-level ski-rental problem,where a user needs to fulfill a sequence of demands for multiple items by choosing one of three payment options. We develop a learning-augmented algorithm (LADTSR) by integrating Machine Learning predictions into the robust online algorithm.
  arXiv  Detail & Related papers  (2024-02-09T16:10:54Z)
• Rethinking and Benchmarking Predict-then-Optimize Paradigm for Combinatorial Optimization Problems [62.25108152764568]
  Many web applications rely on solving optimization problems, such as energy cost-aware scheduling, budget allocation on web advertising, and graph matching on social networks. We consider the performance of prediction and decision-making in a unified system. We provide a comprehensive categorization of current approaches and integrate existing experimental scenarios.
  arXiv  Detail & Related papers  (2023-11-13T13:19:34Z)
• Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.582885296330195]
  We study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. We introduce competitive (robust) threshold-based algorithms for both the deterministic and deterministic variants of this problem. We then propose learning-augmented algorithms that take advantage of black-box advice to achieve significantly better average-case performance.
  arXiv  Detail & Related papers  (2023-10-31T16:34:49Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• 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)
• Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems [13.593621603504847]
  We design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate. We also guarantee a worst-case competitive ratio regardless of the prediction quality. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.
  arXiv  Detail & Related papers  (2021-09-03T14:27:33Z)
• 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)
• 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.