Asymptotically Optimal Learning for Parametric Prophet Inequalities

arXiv:2606.26893v1 Announce Type: new Abstract: We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter heta, a class that includes exponential, Pareto, and bounded-support power-family distributions. We first characterize the optimal full-information asymptotic competitive ratio for this family. In the unbounded-support case, the limit is {left({heta}/({heta-c_+})right)^{c_+/heta}}/ {Gamma(1-c_+/heta)}, while in the bounded-support case, the limit is 1. We then propose a confidence-based dynamic-programming policy for online learning. By exploiting the explicit parametric structure, the policy achieves the same optimal asymptotic competitive ratio using only online observations, without external offline samples. We further derive distribution-specific convergence rates for canonical examples. Finally, numerical experiments on synthetic instances illustrate the performance of our algorithm.

Source: arXiv cs.LG | 2026-06-26