# With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2025.

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

- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)

## Abstract (arXiv)

We study online algorithms with predictions using distributional advice, a type of prediction that arises when leveraging expert knowledge or historical data. To demonstrate the usefulness and versatility of this framework, we focus on the fundamental problem of online metric matching, considering both the fractional and integral variants. Our main positive result is, for the former, an algorithm achieving the optimal cost under perfect advice, while smoothly defaulting to competitive ratios comparable to advice-free algorithms as the prediction's quality degrades. For the integral matching, we are able to provide an algorithm with essentially the same guarantees, up to an additive sublinear term. We conclude by discussing how our algorithmic framework can be extended to other online optimization problems.