Betting on Bets: Anytime-Valid Tests for Stochastic Dominance

1. Problem Statement

The paper addresses the challenge of sequentially testing for Stochastic Dominance (SD) in real-time.

• Context: Decision-makers (DMs) often need to compare two uncertain prospects, $X$ and $Y$ (e.g., a new treatment vs. a baseline, or a new algorithm vs. an old one), to determine if one has a definite "upside" over the other.
• The Gap: Traditional SD tests are fixed-sample and rely on asymptotic validity. They cannot be safely monitored continuously; stopping early based on a p-value inflates Type I error (the "optional stopping" problem).
• The Goal: Develop Anytime-Valid (SAVI) tests that allow the DM to monitor data as it arrives and stop at any adaptively chosen time while strictly controlling the Type I error.
• Specific Challenge: Unlike testing for differences in means, SD is a nonparametric, composite hypothesis involving entire distribution functions. The paper focuses on testing the null hypothesis that $Y$ is dominated by $X$ ($Y \preceq X$) against the alternative that $Y$ has an upside ($Y \not\preceq X$).

2. Methodology

The authors utilize the framework of e-processes and testing-by-betting.

A. Core Framework: E-Variables and E-Processes

• E-variables: Non-negative random variables $E$ such that $\mathbb{E}[E] \leq 1$ under the null hypothesis.
• E-processes: A sequence of adapted non-negative random variables $(E_t)$ where the running product forms a test supermartingale.
• Validity: By Ville's Inequality, if $(E_t)$ is an e-process for a null $\mathcal{H}_0$, then $\mathbb{P}(\exists t: E_t \geq 1/\alpha) \leq \alpha$. This guarantees Type I error control under optional stopping.

B. First-Order Stochastic Dominance (FSD)

• Null Hypothesis: $\mathcal{H}_0: F_X(z) \leq F_Y(z)$ for all $z$ (i.e., $Y$ is dominated by $X$).
• Building Blocks: The authors construct "atomic" e-variables for a fixed threshold $z$:
  $$S(\lambda, z) = 1 + \lambda [ \mathbb{I}(X \leq z) - \mathbb{I}(Y \leq z) ]$$
  This represents a bet where the skeptic wins if $X$ is "better" (lower CDF value) than $Y$ at threshold $z$.
• Mixture Strategy: Since the null is an intersection over all $z$, the authors use a mixture of e-variables across thresholds $z \in \mathcal{Z}$ with predictable weights $\psi_t$.
• Optimal Betting:
  • GRO (Growth-Rate Optimal): For a fixed $z$, the optimal betting fraction $\lambda^*(z)$ maximizes the expected log-growth under the alternative.
  • Plug-in Estimator: The authors use empirical distributions to estimate $\lambda^*(z)$ sequentially.
  • Adaptive Weights: To handle the infinite/continuous space of thresholds, they employ Exponential Weighted Aggregation (EWA). The weights $\psi_t(z)$ are updated adaptively to place more "betting capital" on regions where the CDF difference is largest (violating the null).

C. Higher-Order Stochastic Dominance ($k$-SD)

• Definition: $k$-SD involves iterated integrals of CDFs, corresponding to utility functions with specific curvature properties (e.g., concave for 2nd-order/risk aversion).
• Challenge: The building-block e-variables for $k \geq 2$ are unbounded if data is unbounded.
• Solutions:
  1. Bounded Support: If data has a finite lower bound $a$, the authors normalize the utility generators to create bounded e-variables.
  2. Sub-exponential Tails: For unbounded data, they assume sub-exponential tails and construct e-variables using sub-$\psi$ processes (based on cumulant generating functions).
• Universal Portfolios: For general utility classes where explicit GRO bets are hard to derive, they use Universal Portfolio (UP) strategies (Cover, 1991) to achieve asymptotic log-optimality.

D. The Reverse Problem (Affirming Dominance)

The paper also briefly addresses the harder problem of affirming that $Y$ dominates $X$ (rejecting the null that they are incomparable).

• Impossibility: They prove that no non-trivial e-variable exists for the general non-SD null because the hypothesis set is non-convex.
• Resolution: They propose testing for Restricted SD with $\epsilon$-separation (dominance holds with a margin $\epsilon$ over a specific subset of the support). This allows for valid sequential tests using time-uniform confidence bands (tvCS).

3. Key Contributions

1. Novel E-Processes for SD: The first family of anytime-valid sequential tests for Stochastic Dominance (both first-order and higher-order).
2. Nonparametric & Robust: The methods require no parametric assumptions on the distributions and are robust to dependence between $X$ and $Y$ (including anti-monotonic cases).
3. Optimality:
   • Derivation of Growth-Rate Optimal (GRO) e-variables for FSD.
   • Proof of asymptotic power one (the test rejects the null with probability 1 if the alternative is true) under mild conditions.
4. Adaptive Aggregation: Introduction of adaptive weighting schemes (exponential weights) that dynamically focus on the most informative thresholds, significantly improving power when the "non-dominance region" is small or unknown.
5. Theoretical Limits: Formal characterization of the impossibility of testing the general non-SD null and the conditions required to make it tractable (restricted SD).

4. Experimental Results

The authors validate their methods through extensive simulations:

• Validity: Under the null hypothesis (even with maximal anti-monotonic dependence), the Ville error (Type I error) remains strictly below the significance level $\alpha$ (e.g., 0.05) for all time steps.
• Power:
  • The proposed GRO e-processes grow exponentially under the alternative, leading to much faster rejection times than baseline methods.
  • Adaptive variants (using exponential weights) significantly outperform non-adaptive baselines, especially when the region of dominance is small or the initial search interval is mismatched.
• Comparison with Baselines:
  • Compared to time-uniform CDF bands (e.g., Howard & Ramdas, 2022), the proposed SD-specific tests are far more powerful (requiring orders of magnitude fewer samples to reject).
  • Compared to classical fixed-sample tests (e.g., Barrett & Donald, 2003), the sequential tests offer anytime-validity while maintaining competitive or superior power.
• Higher-Order SD: The methods successfully detect 2nd and 3rd-order dominance, with adaptive strategies showing particular advantage in difficult "contact set" scenarios.

5. Significance and Impact

• Real-Time Decision Making: This work enables rigorous, real-time monitoring of uncertain prospects in fields like A/B testing, clinical trials, and algorithmic trading, where waiting for a fixed sample size is inefficient or risky.
• Safety: The "anytime-valid" guarantee ensures that decision-makers can stop experiments early if a new treatment is clearly superior (or inferior) without inflating false positive rates.
• Generality: By extending to higher-order SD and integral stochastic orders, the framework applies to a wide range of economic and decision-theoretic problems involving risk aversion and utility maximization.
• Theoretical Advancement: It bridges the gap between classical nonparametric statistics and modern sequential inference (e-processes), demonstrating how "betting on bets" can solve complex composite hypothesis testing problems.

In summary, the paper provides a mathematically rigorous, distribution-free, and computationally efficient toolkit for testing stochastic dominance in sequential settings, offering a significant improvement over existing fixed-sample and conservative sequential methods.