Betting on Bets: Anytime-Valid Tests for Stochastic Dominance

1. 研究背景与问题定义

核心问题：
如何在数据随时间顺序到达的情况下，实时监测并检验一个不确定前景（Prospect）$Y$ 是否比另一个前景 $X$ 具有“优势”（Upside）？

• 随机占优 (Stochastic Dominance, SD)： 这是一个经典的非参数概念，用于比较整个分布函数，而不仅仅是均值。
  • 一阶随机占优 (FSD)： $X$ 的累积分布函数 (CDF) 始终位于 $Y$ 的 CDF 下方（即 $F_X(z) \le F_Y(z)$ 对所有 $z$ 成立）。这意味着任何偏好更多而非更少的决策者都会偏好 $X$。
  • 高阶随机占优 (k-SD)： 基于 CDF 的积分比较，对应于具有特定效用函数（如风险厌恶、谨慎性等）的决策者的偏好。
• 现有方法的局限性：
  • 传统的 SD 检验通常是固定样本量的，依赖渐近理论（Asymptotic validity），无法在数据收集过程中随时停止（Optional Stopping），否则会导致第一类错误（Type I error）膨胀。
  • 许多现有方法依赖于参数假设或特定的正则性条件（如 CDF 的连续性、有界性）。
  • 现有的顺序检验方法（如基于时间均匀置信带的 KS 检验）在检验 SD 时往往过于保守，功效（Power）较低。

目标：
开发一套任意时刻有效 (Anytime-Valid) 的顺序检验方法，基于 e-processes (e-过程)，能够在任何自适应选择的样本量下控制第一类错误，同时具备高功效，且无需对分布做参数假设。

---

2. 方法论：基于“赌注”的 e-过程构建

论文的核心思想是将统计检验转化为一个赌博游戏（Testing by Betting）。

2.1 基础构建块：e-变量 (E-variables)

对于一阶随机占优 (FSD) 的零假设 $\mathcal{H}_0: Y \preceq_1 X$，作者构建了一个基础的 e-变量。
对于任意阈值 $z$，定义指示函数差值 $D(z) = \mathbb{I}(X \le z) - \mathbb{I}(Y \le z)$。
构建 e-变量：
$$S(\lambda, z) = 1 + \lambda [ \mathbb{I}(X \le z) - \mathbb{I}(Y \le z) ]$$
其中 $\lambda \in [0, 1]$ 是赌注比例。

• 解释： 如果 $X$ 在 $z$ 处表现更好（即 $X \le z$ 而 $Y > z$），赌注翻倍；反之则损失。在零假设下，期望收益 $\le 0$，因此 $S$ 是一个 e-变量（期望值 $\le 1$）。

2.2 混合策略与 e-过程 (E-processes)

由于 SD 是一个关于所有 $z$ 的交集假设（Intersection Null），作者采用混合策略 (Method of Mixtures)：

1. 阈值混合： 对所有可能的阈值 $z$ 进行加权混合，形成序列 e-变量 $S_t$。
2. 累积财富： 将序列 e-变量连乘形成 e-过程 $E_t = \prod_{l=1}^t S_l$。
3. Ville 不等式： 根据 Ville 不等式，如果 $E_t$ 是零假设下的上鞅，则 $P(\exists t, E_t \ge 1/\alpha) \le \alpha$。这意味着无论何时停止，第一类错误都被控制在 $\alpha$ 以内。

2.3 增长速率最优 (GRO) 与自适应策略

为了最大化检验功效（即让 $E_t$ 在备择假设下增长最快）：

• GRO 赌注： 对于固定 $z$，选择 $\lambda$ 使得 $\mathbb{E}[\log S]$ 最大化。这导出了最优赌注 $\lambda^*(z)$，依赖于 $X$ 和 $Y$ 在 $z$ 处的概率差。
• 自适应权重： 在顺序数据中，使用指数权重 (Exponential Weights) 或 通用投资组合 (Universal Portfolio, UP) 策略来动态调整对不同阈值 $z$ 的赌注分配。
  • 如果某个 $z$ 处的 CDF 差异显著（即 $F_X(z) < F_Y(z)$），算法会自动增加该阈值的权重。
  • 这种方法不需要预先知道非占优区域在哪里，能够自动发现并聚焦于“违规”区域。

2.4 高阶随机占优 (Higher-order SD)

对于 $k$-阶 SD ($k \ge 2$)：

• 利用 $k$-SD 的生成函数特征（Lower Partial Moments）。
• 有界数据： 假设数据有下界 $a$，构造归一化的效用生成器 $u^{[k]}_z(x)$，其差值有界，从而直接应用上述赌博框架。
• 无界数据： 对于无界但具有次指数尾部 (Sub-exponential tails) 的数据，利用次指数过程理论构建 e-变量。
• 通用策略： 对于复杂的效用类，使用通用投资组合 (Universal Portfolio) 策略来渐近地实现最优对数增长率，而无需显式推导每个 $z$ 的最优 $\lambda$。

---

3. 主要贡献

1. 任意时刻有效的 SD 检验框架：

   • 首次系统地提出了针对一阶及高阶随机占优的顺序检验方法，基于 e-processes，严格保证了在连续监控下的第一类错误控制。
   • 解决了传统固定样本检验无法在 A/B 测试等场景中随时停止的问题。

2. 非参数与鲁棒性：

   • 无分布假设： 不假设 $X$ 和 $Y$ 的具体分布形式。
   • 依赖鲁棒性： 即使 $X$ 和 $Y$ 之间存在强相关性（甚至是完全负相关/反单调），检验依然有效。这是许多基于独立同分布假设的传统方法无法做到的。

3. 高功效的自适应算法：

   • 提出了基于 GRO 和通用投资组合的自适应混合策略。
   • 模拟实验表明，该方法在检测 CDF 接触集（Contact Sets，即分布非常接近的区域）时，比基于时间均匀置信带（Time-uniform CDF bands）的基准方法（如 Howard & Ramdas, 2022）具有显著更高的功效（更少的样本量即可拒绝零假设）。

4. 对“非 SD 零假设”的探讨：

   • 讨论了反向问题：检验 $X$ 是否严格占优 $Y$（即拒绝 $X \not\preceq Y$）。
   • 证明了在一般连续支撑集下，构建非平凡 e-变量是不可能的（由于零假设非凸）。
   • 提出了在$\epsilon$-分离（即分布之间存在最小间隙）或有限支撑集条件下的可行检验方案。

---

4. 实验结果

论文通过三个模拟场景验证了方法的有效性：

1. 反单调性玩具示例 (Antimonotonicity)：

   • 在 $X$ 和 $Y$ 完全负相关且分布有界的情况下，所有 GRO e-过程都能快速收敛，且 Ville 错误（第一类错误）始终控制在 0.05 以下。
   • 证明了方法对依赖结构的鲁棒性。

2. 无界连续数据与自适应区域：

   • 在正态分布场景下，测试了初始搜索区间与真实非占优区域不匹配的情况。
   • 结果： 自适应方法（AdaGRO-Exp）能够自动将权重转移到正确的区域，即使初始区间错误也能快速拒绝零假设；而非自适应方法在区间不匹配时完全失效。

3. 接触集 (Contact Sets) 与高阶 SD：

   • 模拟了 CDF 在大部分区域重合（接触集大）的情况。
   • 对比： 与经典的非顺序检验（如 Barrett & Donald, 2003; Linton et al., 2010）及基于置信带的顺序检验相比，GRO e-过程在功效上表现更优或相当，但具备任意时刻有效性。
   • 高阶 SD： 在二阶和三阶 SD 测试中，基于通用投资组合 (UP) 的自适应策略表现优异，特别是在接触集较大时，显著优于固定赌注策略。

---

5. 意义与应用

• 实际应用价值： 该方法非常适合在线 A/B 测试、新疗法评估、投资组合选择等场景。决策者可以在收集到足够证据时立即停止实验并做出决策，而无需担心多重检验或数据窥探（Data Snooping）带来的错误风险。
• 理论突破： 将在线学习（Online Learning）中的“赌注”和“投资组合”理论成功应用于非参数的随机占优检验，解决了复合零假设下的顺序推断难题。
• 扩展性： 框架可推广至多变量随机占优、非平稳数据（Non-stationary）以及更一般的积分随机序（Integral Stochastic Orders）。

总结：
这篇论文提出了一套强大的、分布自由的、任意时刻有效的随机占优检验工具。通过结合 e-processes 理论和自适应混合策略，它不仅克服了传统顺序检验的保守性，还解决了复杂依赖结构下的推断问题，为实时决策提供了坚实的统计学基础。