ArXiv

Asymptotically Optimal Learning for Parametric Prophet Inequalities

2026-06-25 · 11:26 UTC ·Jung-hun Kim, Anna Grebennikova, Vianney Perchet ·1 min read
Authors
Jung-hun Kim, Anna Grebennikova, Vianney Perchet
Categories
cs.LG, stat.ML
arXiv
https://arxiv.org/abs/2606.26893v1
PDF
https://arxiv.org/pdf/2606.26893v1

Brief

The paper studies online learning for prophet inequalities when rewards are i.i.d. from an exponential-type parametric family with unknown θ (includes exponential, Pareto, bounded-support power-family). It gives a closed-form optimal full-information asymptotic competitive ratio (unbounded case: ((θ/(θ−c_+))^{c_+/θ})/Γ(1−c_+/θ); bounded case: 1) and designs a confidence-based dynamic-programming policy that, from only online samples, achieves these limits with distribution-specific convergence rates and synthetic validation.

Why it matters

Characterized the optimal full-information asymptotic competitive ratio for i.i.d. rewards from an exponential-type parametric family (unknown θ): for unbounded-support distributions the limit equals ((θ/(θ - c_+))^{c_+/θ}) / Γ(1 - c_+/θ), while for bounded-support power-family the limit is 1.

Key details

  • Propose a confidence-based dynamic-programming online learning policy that, using only online observations and no external offline samples, asymptotically attains the same optimal competitive ratio as the full-information benchmark.
  • Derive distribution-specific convergence rates for canonical examples (including exponential and Pareto) and validate the algorithm with synthetic numerical experiments; authors Jung-hun Kim, Anna Grebennikova, Vianney Perchet, arXiv:2606.26893v1 (2026-06-25).
Source evidence

Abstract

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.