# Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 43 references that are in the map.
- First posted on arXiv 29 Jan 2025.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [Contract Scheduling with Distributional and Multiple Advice](https://mlsanity.com/paper/2404.12485/) (2024)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [Contract Scheduling With Predictions](https://mlsanity.com/paper/2011.12439/) (2020)
- [Advice Complexity of the Online Search Problem](https://mlsanity.com/paper/1612.09299/) (2016)
- [Online Search With Best-Price and Query-Based Predictions](https://mlsanity.com/paper/2112.01592/) (2021)
- [R'enyi-Ulam Games and Online Computation with Imperfect Advice](https://mlsanity.com/paper/2301.01631/) (2023)

## Abstract (arXiv)

We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling.