Asymptotically Optimal Learning for Parametric Prophet Inequalities
Jung-hun Kim, Anna Grebennikova, Vianney Perchet · 2026
Read Asymptotically Optimal Learning for Parametric Prophet Inequalities by Jung-hun Kim, Anna Grebennikova, Vianney Perchet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26893.txt.
Introduction
Kim, Grebennikova, and Perchet study online stopping problems where reward values come from an unknown formula family. In a prophet inequality, a decision maker sees random rewards one by one and must pick one on the spot. Here rewards follow an exponential-type family, covering cases like exponential and Pareto distributions, with one hidden parameter. The authors first pin down the best possible long-run competitive ratio when that parameter is fully known.
With full knowledge, the limiting ratio takes a closed form for unbounded rewards and reaches one for bounded rewards. Learning must then match that bar using only rewards seen so far, with no practice data. Their confidence-based dynamic programming policy does exactly that as rounds grow. It reaches the same best long-run ratio purely from online observations. Worked rates for standard examples and simulated tests confirm the policy performs as theory predicts.
Catalog record
| CREATOR | Jung-hun Kim, Anna Grebennikova, Vianney Perchet |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 150 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotically Optimal Learning for Parametric Prophet Inequalities Jung-hun Kim, Anna Grebennikova, Vianney Perchet Abstract We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter θ \theta , 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 ( θ / ( θ − c + ) ) c + / θ / Γ ( 1 − c + / θ ) , {\left({\theta}/({\theta-c_{+}})\right)^{c_{+}/\theta}}/{\Gamma(1-c_{+}/\theta)}, while in the bounded-support case, the limit is 1 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. 1 Introduction Prophet inequalities are a fundamental model of online decision-making and optimal stopping ( 10 ) . A decision-maker sequentially observes rewards and must irrevocably decide when to stop and accept the current reward. The benchmark is the prophet, who observes all realizations in advance and obtains the maximum reward. The goal is to design a stopping rule whose expected reward is competitive with this prophet benchmark. This framework has attracted significant attention due to its rich mathematical structure and its broad range of applications, including posted-price mechanisms ( 15 ) , online ad allocation ( 1 ) , and hiring processes in labor markets ( 2 ) . Classical prophet inequalities assume that the reward distributions are known. Under this assumption, for i.i.d. reward distributions, 9 established the classical 1-1/e guarantee, and subsequent work characterized the optimal full-information i.i.d. worst-case constant \kappa\approx 0.745 ( 4 ; 5 ) . However, full distributional knowledge is rarely available in applications. This has motivated a growing literature on prophet inequalities with unknown distributions. A central message of this literature is that, for arbitrary unknown distributions, learning is severely limited without sufficient offline samples: in the i.i.d. setting, one cannot improve over the competitive ratio 1/e with o(n) offline samples ( 3 ) . Achieving near-optimal worst-case guarantees for arbitrary distributions requires substantial distributional information, such as \Theta(n) or more offline samples ( 17 ) . Thus, in the absence of structure, learning prophet inequalities is constrained by strong sample-complexity barriers. A complementary perspective is to seek distribution-specific asymptotic performance beyond distribution-free worst-case guarantees. 7 pursue this direction using nonparametric relative-rank-based rules, establishing first-order asymptotic optimality in the Gumbel and reverse-Weibull domains. However, because their rules use only relative ranks, they cannot exploit parametric information in the observed reward values. This restriction is especially pronounced in the Fréchet heavy-tailed regime: no relative rank-based rule can attain the full-information Fréchet heavy-tailed limit, as discussed later. Even where the relative rank-based framework applies, its nonparametric rates can be slower than those achievable under stronger parametric structure. Another closely related direction is online learning in structured prophet inequality models. 12 study prophet inequalities under a linear reward structure with an unknown parameter and a known feature distribution. Their objective, however, is to recover the classical distribution-agnostic guarantee of 1-1/e . This guarantee is robust but not distribution-specific: it can be strictly below the optimal ratio achievable within a given distribution class, and is also below the optimal full-information i.i.d. worst-case constant \kappa\approx 0.745 . These works motivate the following question: Can one exploit parametric distributional structure to learn the unknown parameter online and match the full-information distribution-specific benchmark? We answer this question affirmatively for an exponential-type parametric family, which includes light-tailed, heavy-tailed, and bounded-support models such as exponential, Pareto, and bounded-support power-family distributions. Our goal is not to recover a distribution-agnostic worst-case constant, but to learn the parameter from online observations alone and match the full-information distribution-specific asymptotic competitive ratio. Our main contributions are summarized as follows. • Optimal full-information asymptotics. We characterize the asymptotically optimal competitive ratio for the proposed exponential-type family when the distribution parameter \theta is known. In the unbounded-support case, the limiting optimal ratio is \frac{1}{\Gamma(1-c_{+}/\theta)}\left(\frac{\theta}{\theta-c_{+}}\right)^{c_{+}/\theta}, which is governed by the endpoint-growth parameter c_{+} . In the bounded-support case, the optimal competitive ratio converges to 1 . • Online learning with asymptotically optimal guarantees. We propose a confidence-based dynamic-programming policy for online learning. The policy first estimates the unknown distribution parameter from an initial exploration phase, constructs an upper confidence bound, and then applies the corresponding plug-in DP thresholds. By exploiting the explicit parametric structure, the proposed policy achieves the same asymptotically optimal competitive ratio as the optimal known-parameter policy, using only online observations and no external offline samples. • Distribution-specific convergence guarantees. We derive refined convergence guarantees for representative distributions, including exponential, Pareto, and bounded-support power-family rewards. For exponential and bounded-support examples, our policy matches the convergence rates of the corresponding full-information optimal policies. For Pareto heavy-tailed rewards, we obtain a Pareto-specific convergence guarantee showing convergence to the full-information limiting ratio. These results show how tail or endpoint structure governs the speed of convergence, and are supported by numerical experiments. 2 Related Work Prophet inequalities with known distributions. The classical prophet inequality was initiated by 13 . Building on this line of work, 18 showed that a single threshold achieves the optimal 1/2 competitive ratio for independent non-identical rewards. For i.i.d. rewards, 9 established stronger guarantees of 1-1/e , and later work characterized the optimal full-information i.i.d. competitive ratio as constant \kappa\approx 0.745 ( 4 ) . These works assume that the reward distribution is known, whereas our focus is on learning the unknown parameter of a structured distribution online. Unknown distributions and sample-based prophet inequalities. 3 studied i.i.d. prophet inequalities with an unknown distribution and showed that, with no samples or even o(n) samples, the best possible ratio is 1/e . They also showed that n-1 samples yield a 1-1/e guarantee and that O(n^{2}) samples suffice to approach the optimal full-information constant \kappa . 17 improved the i.i.d. sample complexity to O(n/\varepsilon^{6}) for an \kappa-O(\varepsilon) guarantee. Our work is complementary: instead of using external offline samples from an arbitrary distribution, we exploit a parametric form and learn the unknown parameter from the online observations. Rank-based stopping and extreme-value theory. 7 studied optimal stopping for i.i.d. observations from an unknown continuous distribution using relative-rank-based rules. Their analysis is closely connected to extreme-value theory: they establish first-order asymptotic optimality in the Gumbel and reverse-Weibull domains, whereas in the Fréchet domain vanishing relative regret is impossible. Our endpoint regularity conditions admit a similar extreme-value interpretation. In contrast to their nonparametric, rank-based approach, we exploit parametric rewards to attain optimal distribution-specific asymptotic ratios across light-tailed, heavy-tailed, and bounded-support models within our family, with sharper convergence rates in canonical examples. Structured and parametric learning in prophet inequalities. 12 study prophet inequalities under a linear reward structure with an unknown parameter and a known feature distribution, and recover the classical 1-1/e guarantee. Their setting is structurally different from ours, and the resulting guarantee is distribution-agnostic rather than distribution-specific. In particular, it can be below the optimal ratio for a given distribution class and the optimal worst-case full-information i.i.d.