Search papers, labs, and topics across Lattice.
This paper investigates learning in prophet inequalities with rewards from a parametric family, including exponential and Pareto distributions, and establishes the optimal full-information asymptotic competitive ratios for both unbounded and bounded cases. The authors introduce a confidence-based dynamic programming policy that achieves these optimal ratios using only online observations, eliminating the need for offline samples. Numerical experiments validate the effectiveness of the proposed algorithm, showcasing its performance across various synthetic instances.
Achieving optimal competitive ratios in prophet inequalities without relying on offline samples could revolutionize online learning strategies.
We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter $θ$, 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(θ/({θ-c_+})\right)^{c_+/θ}}/ {Γ(1-c_+/θ)},$ 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.
