Technical Summary: Algorithm for Adaptive Experiments that Trade-off Statistical Analysis with Reward

1. Problem Statement

In digital field experiments (e.g., A/B testing in education, mobile health, or web interfaces), researchers face a fundamental dichotomy between two competing objectives:

1. Maximizing Reward: Allocating participants to the most effective experimental condition (arm) to maximize cumulative positive outcomes (e.g., student learning, click-through rates).
2. Statistical Inference: Collecting data that allows for valid hypothesis testing to determine if arms differ significantly. This requires controlling the False Positive Rate (FPR/Type I error) and ensuring sufficient Statistical Power (1 - Type II error).

Traditional Uniform Randomization (UR) ensures valid statistical inference but fails to maximize participant reward by ignoring performance differences during the experiment. Conversely, Thompson Sampling (TS), a popular Bayesian multi-armed bandit algorithm, maximizes reward by adaptively assigning participants to better-performing arms. However, TS introduces significant challenges for statistical inference:

• Biased Estimates: TS tends to under-sample arms that are currently estimated to be worse, leading to imbalanced sample sizes.
• Inflated FPR: This imbalance causes standard hypothesis tests (like the Wald test) to produce false positives at rates higher than the nominal significance level (e.g., >0.05).
• Reduced Power: The lack of sufficient data on both arms makes it harder to detect true differences when they exist, particularly when the difference between arms is small.

The paper posits that practitioners need an approach that balances these goals, avoiding the extreme trade-offs where one must choose between reliable science (UR) and optimal user outcomes (TS).

2. Methodology: TS-PostDiff

The authors propose TS-PostDiff (Thompson Sampling - Posterior Probability of Small Difference), a hybrid algorithm that adaptively mixes Uniform Randomization (UR) and Thompson Sampling (TS).

Core Mechanism

The algorithm operates on a "double-Bayesian" approach. At each time step $t$, the algorithm decides whether to assign a participant via UR or TS based on the posterior probability that the difference between the arms is "small."

1. Small-Difference Threshold ($\delta$): The experimenter defines a threshold $\delta \in [0, 1]$. This represents a difference in arm means below which the experimenter is willing to forgo some reward to gain better statistical properties (lower FPR, higher power).
2. Adaptive Probability ($\phi_t$): The algorithm calculates the posterior probability $\phi_t$ that the absolute difference between the true arm means ($|p_1 - p_2|$) is less than $\delta$, given the data observed up to time $t$:
   $$\phi_t = P(|p_1 - p_2| < \delta \mid D_t)$$
3. Assignment Strategy:
   • With probability $\phi_t$, the algorithm assigns the participant Uniformly at Random (UR). This occurs when the algorithm is uncertain or believes the arms are effectively equivalent.
   • With probability $1 - \phi_t$, the algorithm assigns the participant according to Thompson Sampling (TS). This occurs when the algorithm is confident that a meaningful difference exists, allowing it to exploit the better arm.

Algorithmic Details

• Resampling: To prevent the algorithm from becoming too exploitative due to using the same posterior samples for both the threshold check and the arm selection, TS-PostDiff includes a resampling step. If the condition $|p_1 - p_2| < \delta$ is met, the algorithm triggers UR; otherwise, it resamples $p_1$ and $p_2$ from their posteriors to select the arm with the highest sampled value (standard TS).
• Comparison Baselines: The paper evaluates TS-PostDiff against:
  • $\epsilon$/TT-TS (Top-Two Thompson Sampling): Adds a fixed amount of exploration ($\epsilon$) to the second-best arm.
  • TS-Probability Clipping: Constrains the maximum allocation probability to an arm to prevent it from reaching 100%, ensuring some exploration.

3. Key Contributions

• Novel Algorithm: Introduction of TS-PostDiff, which dynamically adjusts the level of exploration based on the posterior probability of a "small difference" rather than using a fixed exploration rate.
• Interpretability: The algorithm allows domain scientists to set an interpretable threshold ($\delta$) representing the minimum effect size of interest. Below this threshold, the algorithm prioritizes data quality (inference); above it, it prioritizes user benefit (reward).
• Empirical Evaluation: A comprehensive simulation study comparing TS-PostDiff, UR, TS, $\epsilon$/TT-TS, and TS-ProbClip across various arm differences and sample sizes (specifically 197 and 785 participants).

4. Results

The evaluation, conducted over 10,000 simulations, highlights the following trade-offs:

• Small Arm Differences (e.g., $\le 0.1$):

  • TS suffers from inflated FPR (up to 0.13 vs. 0.05 for UR) and significantly reduced Power.
  • TS-PostDiff behaves similarly to UR, maintaining FPR close to the nominal level (e.g., 0.07) and achieving high Power (close to 0.8), while sacrificing minimal reward compared to UR.
  • $\epsilon$/TT-TS and TS-ProbClip improve upon TS but do not match the Power of TS-PostDiff in these small-difference regimes because their fixed exploration rates are insufficient to fully counteract the bias when differences are negligible.

• Large Arm Differences (e.g., $\ge 0.2$):

  • All algorithms achieve near-perfect Power (approaching 1.0).
  • TS-PostDiff shifts behavior toward TS, allocating a high proportion of participants to the optimal arm (e.g., 89% vs. 50% for UR), thereby maximizing reward.
  • TS-PostDiff outperforms $\epsilon$/TT-TS and TS-ProbClip in reward accumulation for large differences because it does not impose a fixed "ceiling" on exploitation.

• Overall Performance:

  • TS-PostDiff achieves a superior trade-off curve, approaching the "ideal" behavior: behaving like UR when differences are small (to protect inference) and like TS when differences are large (to maximize reward).
  • In a specific educational case study (self-explanation prompts), TS-PostDiff assigned 89% of students to the better condition when the effect was large (0.20), compared to 50% for UR, while maintaining statistical validity.

5. Significance and Claims

The paper claims that TS-PostDiff offers a practical solution for the "Statistically Sensitive" design of adaptive experiments. Its significance lies in:

• Bridging the Gap: It resolves the dichotomy between reliable statistical inference and reward maximization without requiring complex post-hoc corrections or deterministic strategies.
• Practitioner Utility: It provides a mechanism for non-statisticians (e.g., product designers, educators) to control the experiment's behavior via a single, interpretable parameter ($\delta$) representing the "small difference" threshold.
• Adaptive Flexibility: Unlike fixed-mixture algorithms (like $\epsilon$-greedy or fixed TT-TS), TS-PostDiff adapts its exploration rate based on the data, ensuring that exploration is high only when necessary (i.e., when the difference is ambiguous) and low when the optimal arm is clear.

The authors conclude that while TS-PostDiff is currently limited to two-arm binary reward settings, it represents a significant step toward algorithms that can balance scientific rigor with ethical and practical considerations in online experimentation. Future work is suggested to extend this to multi-arm settings and formalize objective functions that weight Power, FPR, and Reward.