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

arXiv: https://arxiv.org/abs/2211.06567 · HTML: https://mlsanity.com/paper/2211.06567/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 12 Nov 2022.

## Builds on (most cited first, 13 of 13)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Data-driven Competitive Algorithms for Online Knapsack and Set Cover](https://mlsanity.com/paper/2012.05361/) (2020)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)
- [Improved Bounds for Online Facility Location with Predictions](https://mlsanity.com/paper/2107.08277/) (2021)
- [Optimal Online Algorithms for Peak-Demand Reduction Maximization with Energy Storage](https://mlsanity.com/paper/2105.04728/) (2021)
- [Competitive Prediction-Aware Online Algorithms for Energy Generation Scheduling in Microgrids](https://mlsanity.com/paper/2205.12168/) (2022)

## Built on by (most cited first, 9 of 9)

- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search](https://mlsanity.com/paper/2502.05720/) (2025)
- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand](https://mlsanity.com/paper/2404.15211/) (2024)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.17701/) (2025)
- [Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors](https://mlsanity.com/paper/2509.26511/) (2025)

## Abstract (arXiv)

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.