mlsanityData to 7 Oct 2026

Optimal Single-Choice Prophet Inequalities from Samples

arXiv 1911.07945 ↗First posted 18 Nov 2019cs.DS cs.GTcited by 9

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 1; 2025: 1; 2026: 4.

9 papers.

  1. 2022Bandit Algorithms for Prophet Inequality and Pandora's Boxcited by 13
  2. 2023Semi-Bandit Learning for Monotone Stochastic Optimizationcited by 8
  3. 2023Robust Budget Pacing with a Single Samplecited by 4
  4. 2024Online Combinatorial Allocations and Auctions with Few Samplescited by 3
  5. 2025Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regretcited by 0
  6. 2026Pricing Query Complexity of Multiplicative Revenue Approximationcited by 0
  7. 2026Learning in Prophet Inequalities with Noisy Observationscited by 0
  8. 2026The Secretary Problem with a Stochastic Precursorcited by 0
  9. 2026Optimal No-Regret Learning for Repeated Prophet Inequalitycited by 0