# Optimal Single-Choice Prophet Inequalities from Samples

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2019.

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Learning in Prophet Inequalities with Noisy Observations](https://mlsanity.com/paper/2604.01789/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of 1/2 can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant varepsilon > 0, O(n) samples from the distribution suffice to achieve the optimal competitive ratio (≈ 0.745) within (1+varepsilon), resolving an open problem of Correa, D"utting, Fischer, and Schewior.