# Optimal No-Regret Learning for Repeated Prophet Inequality

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 16 references that are in the map.
- First posted on arXiv 20 Sep 2026.

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

- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Sample Complexity of Posted Pricing for a Single Item](https://mlsanity.com/paper/2406.00819/) (2024)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack](https://mlsanity.com/paper/2107.02058/) (2021)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Prophet inequality for bipartite matching: merits of being simple and non adaptive](https://mlsanity.com/paper/1902.06243/) (2019)

## Abstract (arXiv)

We study repeated prophet inequalities under prefix feedback. In each of T rounds, a learner encounters fresh values drawn independently from n boxes with unknown [0,1]-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. Regret is measured against the optimal stopping policy that knows the distributions. We give an efficient algorithm achieving widetilde O(√T) expected regret, matching the lower bound up to logarithmic factors. Our algorithm explores directly through near-optimal policies, combining empirical backward induction with box-specific reach bonuses. A relative-drop aggregation rule then exploits the nesting structure of observed prefixes to preserve exploration, thereby removing the polynomial dependence on the box number n. This resolves an open question posed by Liu et al. (2025).