在奖励观测有噪声的场景下，实现接近最优的在线决策。
Learning in Prophet Inequalities with Noisy Observations
- 用置信下界阈值融合学习与决策，适应未知分布。
- 独立同分布下达到1-1/e的竞争比，非独立时保证1/2。
- 适合奖励信息不完整、需实时判断的智能系统应用。
我们研究了在实际场景中奖励仅通过噪声观测且分布未知的序贯决策问题。每阶段，决策者接收到一个服从线性模型的噪声奖励，其真实值依赖于未知潜变量，同时观察到一个来自分布的特征向量。为此，我们提出结合学习与决策的低置信下界（LCB）阈值策略。在独立同分布设置下，我们证明探索后决定策略和ε-贪婪变体在最优值满足弱条件下均能达到尖锐的竞争比1-1/e。对于非同分布情形，我们证明可对放松的基准保证1/2的竞争比。此外，在仅有限窗口访问历史奖励的情况下，也能实现对最优基准的紧竞争比1/2。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。