# Learning in Prophet Inequalities with Noisy Observations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 2 Apr 2026.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Individual Fairness in Prophet Inequalities](https://mlsanity.com/paper/2205.10302/) (2022)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Prophet Inequalities with Linear Correlations and Augmentations](https://mlsanity.com/paper/2001.10600/) (2020)
- [Beating 1-1/e for Ordered Prophets](https://mlsanity.com/paper/1704.05836/) (2017)
- [Windowed Prophet Inequalities](https://mlsanity.com/paper/2011.14929/) (2020)
- [Prophet Inequality on I.I.D. Distributions: Beating 1-1/e with a Single Query](https://mlsanity.com/paper/2205.05519/) (2022)
- [Lookback Prophet Inequalities](https://mlsanity.com/paper/2406.06805/) (2024)

## Abstract (arXiv)

We study the prophet inequality, a fundamental problem in online decision-making and optimal stopping, in a practical setting where rewards are observed only through noisy realizations and reward distributions are unknown. At each stage, the decision-maker receives a noisy reward whose true value follows a linear model with an unknown latent parameter, and observes a feature vector drawn from a distribution. To address this challenge, we propose algorithms that integrate learning and decision-making via lower-confidence-bound (LCB) thresholding. In the i.i.d. setting, we establish that both an Explore-then-Decide strategy and an varepsilon-Greedy variant achieve the sharp competitive ratio of 1 - 1/e, under a mild condition on the optimal value. For non-identical distributions, we show that a competitive ratio of 1/2 can be guaranteed against a relaxed benchmark. Moreover, with limited window access to past rewards, the tight ratio of 1/2 against the optimal benchmark is achieved.