技术摘要：基于极值渐近理论的多单位 I.I.D. 先知不等式

1. 问题定义

本文研究了多单位 I.I.D. 先知不等式问题。在此设定下，决策者依次观察到 $n$ 个来自已知分布 $F$ 的独立同分布（i.i.d.）非负奖励。决策者必须在每个奖励到达时做出不可撤销的“接受或拒绝”决策，且受到最多只能接受 $k$ 个奖励（$k \le n$）的约束。其目标是最大化预期总奖励。

在线策略的性能基准是一个能够预先观察到所有 $n$ 个实现值并选择前 $k$ 个最高奖励的“先知”。标准的衡量指标是竞争比，定义为在线策略的预期奖励与先知奖励的比值。本文关注的是依赖于实例的渐近竞争比（$ACR_k(F)$），即在固定分布 $F$ 和固定 $k$ 的情况下，当 $n \to \infty$ 时该比值的极限。

此外，本文还分析了确定性等价（Certainty Equivalent, CE）启发式算法的性能，这是一种广泛使用的自适应策略，通过动态调整接受阈值以维持统一的接受率，并将其与最优动态规划（DP）解进行对比。

2. 研究方法

作者利用极值理论（Extreme Value Theory, EVT）来刻画问题的渐近行为。核心的方法论转变是从针对所有可能分布的最坏情况分析（其中最坏情况分布可能随 $n$ 变化）转向依赖于实例的分析，即固定分布 $F$ 并令 $n$ 趋于无穷大。

关键技术工具：

• 极值条件： 分析假设 $F$ 满足极值条件，即 $n$ 个 i.i.d. 样本的最大值的归一化分布收敛于一个由极值指数 $\gamma \in \mathbb{R}$ 表征的广义极值（GEV）分布。
• 正则变化： 对于 $\gamma \neq 0$ 的分布，其尾部行为通过正则变化函数进行刻画。
• 递推关系的渐近分析： 作者通过分析最优 DP 和 CE 启发式算法各自的二维递推关系，推导了其值函数的渐近行为。他们利用了分位数函数 $F^{\leftarrow}(1 - 1/n)$ 的性质以及用于正则变化函数的 Karamata 定理。
• 竞争复杂度： 本文引入了“市场通胀”视角，计算为了使次优策略在原市场中达到与先知相同的奖励，市场规模（$m$）相对于原规模（$n$）需要扩大多少。

3. 核心贡献与结果

3.1. 最优渐近竞争比的特征描述

本文为满足极值条件的分布提供了最优渐近竞争比 $ACR_k(F)$ 的精确特征描述。

• 对 $\gamma$ 的依赖性： 该比例仅通过极值指数 $\gamma$ 和单位数 $k$ 取决于分布 $F$。
• 显式公式： 对于 $\gamma \in (0, 1)$（具有有限均值的重尾分布），该比例由下式给出：
  $$ACR_k(F) = \frac{(1-\gamma)^{1-\gamma} v_k \Gamma(k)}{\Gamma(k+1-\gamma)}$$
  其中 $\{v_k\}$ 是一个递归定义的序列。对于 $\gamma \notin (0, 1)$，该比例为 1。
• 大 $k$ 渐近性质： 对于较大的 $k$，作者推导出了一个对所有满足极值条件的分布都成立的显式下界：
  $$ACR_k(F) \ge 1 - \frac{\log k}{8k}(1+\epsilon)$$
  这改进了此前已知的 $1 - \frac{1}{\sqrt{2\pi k}}$ 的静态阈值算法紧确界。最坏情况的性能发生在 $\gamma = 1/2$ 时。

3.2. CE 启发式算法的性能

本文分析了不需要依赖“流体缩放”（fluid scaling, $k \propto n$）假设的确定性等价（CE）启发式算法。

• 渐近比例： CE 启发式算法实现的渐近竞争比 $apx_k(F)$ 与最优 DP 一样，仅取决于 $\gamma$ 和 $k$。
• 大 $k$ 收敛性： 对于较大的 $k$，CE 启发式算法的性能比例的主项与最优 DP 匹配：
  $$apx_k(F) \approx 1 - \frac{\gamma(1-\gamma)}{2} \frac{\log k}{k}$$
  这意味着对于大预算场景，即使没有流体缩放，CE 启发式算法也几乎与最优动态规划一样有效。
• 发散遗憾（Divergent Regret）： 更精细的分析揭示了一个关键区别。虽然比例趋于 1，但在 $k = o(n)$ 且 $n \to \infty$ 时，对于 $\gamma \in (0, 1)$ 的分布，加性遗憾（$V_{dp} - V_{ce}$）可能是发散的。具体而言，遗憾以 $\Omega((n/k)^\gamma)$ 的速度增长。这与有限支撑分布中遗憾是一致有界的结论形成对比。

3.3. 竞争复杂度

本文量化了“竞争复杂度”——即为了补偿策略的次优性而需要的市场规模膨胀程度。

• 对于 $\gamma \in (0, 1)$，最优 DP 和 CE 启发式算法的竞争复杂度均为 $C_k(F) = (ACR_k(F))^{-1/\gamma}$。
• 当 $k \to \infty$ 时，两种策略都需要 $1 + O(\frac{\log k}{k})$ 的市场规模膨胀因子才能匹配先知的表现。

4. 意义与主张

本文声称在先知不等式和在线资源分配理论方面做出了几项重要的贡献：

1. 显式最坏情况保证： 它提供了目前最强的显式解析表达式，用于提供针对广泛类别的分布（满足极值条件的分布）的最坏情况性能保证（$1 - \frac{\log k}{8k}$），改进了以往的隐式特征描述和静态阈值界限。
2. 依赖于实例的视角： 通过固定分布并令 $n \to \infty$，作者提供了一个可处理的框架，该框架利用了顶序统计量的统计规律性，提供了比传统最坏情况分析（其中分布随 $n$ 变化）更细致的视角。
3. CE 启发式算法的验证与局限性： 结果验证了 CE 启发式算法在大 $k$ 情况下即使没有流体缩放也是一种稳健且近乎最优的策略。然而，本文强调了一个关键局限：常见的流体缩放假设（$k \propto n$）可能是误导性的。在 $k \ll n$ 的情形下，CE 启发式算法相对于最优 DP 可能会遭受无界的加性遗憾，这一现象在离散、有限支撑的设定中并未出现。
4. 通过 EVT 实现统一： 本工作通过将问题简化为单一参数——极值指数 $\gamma$，统一了不同分布下的先知不等式理解，这类似于中心极限定理将求和行为简化为方差的方式。

作者得出结论，虽然 CE 启发式算法在大预算下非常有效，但决策者在将流体缩放直觉应用于具有稀疏预算（$k \ll n$）的固定实例时必须保持谨慎，因为其加性性能损失可能是显著的。