针对参数化先知不等式，提出可在线学习的最优算法。
Asymptotically Optimal Learning for Parametric Prophet Inequalities
- 利用参数结构设计置信区间动态规划策略
- 无须离线数据即可达到理论最优渐近竞争力
- 适用于指数、帕累托等分布，适合在线决策场景
我们研究了从指数型参数族中独立同分布抽取奖励、但未知参数θ的先知不等式学习问题，该类包括指数分布、帕累托分布及有界支持幂律分布。首先刻画了该族在全信息下的最优渐近竞争力：无界支持情况下极限为 $ { heta/( heta - c_+)}^{c_+/ heta} / ext{Γ}(1 - c_+/ heta) $，有界支持情况下极限为1。随后提出一种基于置信区间的动态规划在线学习策略，仅依赖在线观测即可实现相同最优渐近竞争力，无需外部离线样本。进一步推导了典型例子的分布特异性收敛速率，并通过合成实验验证算法性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。