Learning in Prophet Inequalities with Noisy Observations
This work addresses a practical challenge in online decision-making for applications like auctions or hiring, though it is incremental by extending existing prophet inequality frameworks to noisy and unknown settings.
The paper tackles the prophet inequality problem in online decision-making with noisy observations and unknown reward distributions, proposing algorithms that achieve competitive ratios of 1 - 1/e in i.i.d. settings and 1/2 in non-identical or limited-window scenarios.
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.