Asymptotically Optimal Learning for Parametric Prophet Inequalities

In online decision-making, the prophet inequality framework compares a decision-maker's performance against a 'prophet' who knows all future rewards. While classical results assume known distributions, real-world applications often involve unknown parameters. This paper asks whether one can exploit the parametric structure of reward distributions to learn these parameters online and achieve the same competitive ratio as a prophet who knows the distribution perfectly.

The authors focus on an exponential-type parametric family, which encompasses light-tailed (e.g., exponential), heavy-tailed (e.g., Pareto), and bounded-support distributions. They first derive the theoretical optimal competitive ratio for this family under full information. To bridge the gap between theory and practice, they propose a 'Confidence-based Dynamic-Programming' (CDP-OL) policy. This algorithm uses an initial exploration phase to estimate the unknown parameter, constructs an upper confidence bound to account for estimation error, and then applies a plug-in dynamic programming strategy to determine optimal stopping thresholds.

The study demonstrates that the proposed CDP-OL policy is asymptotically optimal. In the unbounded-support case, the policy achieves the theoretical limit determined by the tail growth of the distribution. In the bounded-support case, the competitive ratio converges to 1. Notably, the authors show that for heavy-tailed Fréchet distributions, exploiting the parametric structure is essential, as nonparametric rank-based methods are mathematically incapable of reaching the optimal competitive ratio in this regime. The authors also provide refined convergence rates for canonical distributions, showing that their policy matches the performance of full-information benchmarks.

This work provides a rigorous foundation for online learning in optimal stopping problems where the distribution is not fully known but follows a structured parametric form. By moving beyond distribution-agnostic worst-case guarantees, the authors offer a more powerful framework that achieves higher performance in specific, structured environments. This is particularly relevant for applications like dynamic pricing, ad allocation, and hiring, where the underlying reward processes often exhibit predictable parametric behaviors.