通过方差约束改进预言家不等式,让算法更贴近真实场景。
Kernel Methods for Refined Prophet Inequalities
- 用核方法将选择问题转化为量化空间中的凸优化。
- 在方差受限条件下,精确给出独立同分布情况的最优策略。
- 适用于非独立、随机终止等复杂场景,适合理论研究者。
单次选择预言家不等式是经典的贝叶斯在线选择问题:独立非负值按序到达,决策者只能不可撤销地选一个。经典单阈值保证在最坏情况下紧致,但紧致实例高度不规则——预言家优势主要来自极值出现的罕见事件。本文通过限制预言家价值的相对方差(即 Var(max X_i)/E[max X_i]^2)来细化最坏情况分析,引入一种非参数复杂度度量,介于确定性情形(可完全恢复预言家收益)与无约束最坏情况之间。核心贡献是提出通用核方法:将实例表示为最大值的分位数函数,将阈值收益表达为该分位数的线性核泛函,从而将最坏情况分析转化为无限维凸规划,恢复量化空间中的强极小极大对偶性,并将有界方差对手问题简化为单参数变分族。基于此框架,我们精确刻画了独立同分布下的有界方差曲线,获得渐近最优的有限时域阈值,推导出固定顺序非同分布模型的闭式解,并建立预言家-秘书下界程序,在任意正有限方差约束下严格优于独立同分布基准。进一步应用该核视角,我们在横断面概率生成函数满足凸性条件(包括单调风险率情形)下,给出了独立同分布随机时域的精确公式,凸显该技术在单阈值设置中的广泛适用性。
原文摘要 · Abstract (English)
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime. Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。