Exploiting Similarities in A/B Testing with Off-Policy Estimation

Technical Summary: Exploiting Similarities in A/B Testing with Off-Policy Estimation

Problem Statement
A/B testing is the standard protocol for measuring the performance gain of a new decision system ($\pi_A$) relative to a baseline ($\pi_B$). Traditionally, this is performed using a difference-in-means estimator, which treats both systems as black boxes. While unbiased, this estimator is statistically suboptimal because it ignores potential structural similarities between the policies. In modern online applications (e.g., advertising, recommendations), decision systems are often stochastic and share significant structure, meaning they have similar "propensities" to make specific decisions. The paper argues that when policies overlap, the classical estimator suffers from unnecessary variance, while standard off-policy estimation (OPE) methods, which rely on importance weighting, are often too biased or unstable to replace A/B testing directly.

Methodology
The authors propose a family of A/B testing estimators that leverage off-policy estimation techniques to exploit the overlap between $\pi_A$ and $\pi_B$ without altering the standard experimental protocol.

1. Framework: The problem is modeled within an extended non-Markov Decision Process (NMDP) framework where users interact with the system over trajectories $\tau$. The goal is to estimate the improvement $I(\pi_A, \pi_B) = V(\pi_A) - V(\pi_B)$.
2. Estimator Construction: The proposed estimator $\hat{I}_f$ combines two components:
   • An $f$-regularized Inverse Propensity Scoring (IPS) term using data from the baseline policy ($D_B$).
   • A bias correction term using data from the target policy ($D_A$).
   • The function $f: \mathbb{R}_+ \to \mathbb{R}$ transforms the importance weights $w(\tau) = \pi_{target}(\tau) / \pi_{source}(\tau)$.
3. Theoretical Conditions:
   • Unbiasedness: The estimator is unbiased if $f(0) = -1$. This condition ensures that when policies have disjoint support (no overlap), the estimator naturally reverts to the standard difference-in-means estimator.
   • Variance Reduction: To reduce variance, the authors define a variance surrogate $S_f$. They derive conditions on $f$ (specifically $f(1)=0$ and bounds on $f(x)$) that guarantee lower variance than the difference-in-means estimator when policies are similar.
4. Optimal Transformations:
   • Surrogate-Optimal ($f^*_{n_r}$): The authors derive a closed-form function $f^*_{n_r}(x) = \frac{x-1}{n_r x + 1}$ (where $n_r = n_A/n_B$) that minimizes the variance surrogate. This estimator effectively reweights the data from both populations to account for sample imbalance.
   • Misspecification-Aware ($f^*_{\lambda, \Delta}$): Recognizing that propensities are often estimated from data rather than known, the authors introduce a regularization parameter $\lambda$ to balance bias and variance under propensity misspecification. This yields a robust estimator that degrades gracefully to the difference-in-means estimator as misspecification increases.

Key Contributions

• Novel Estimator Family: Introduction of a flexible family of A/B testing estimators based on importance weighting that explicitly exploits policy overlap.
• Theoretical Guarantees: Proof that the estimators are unbiased under specific conditions on $f$ and demonstrate improved concentration properties (lower variance) when policies are similar.
• Robustness: Development of misspecification-aware variants that remain robust when propensities are estimated from data, avoiding the high variance or bias typical of standard OPE methods.
• Graceful Degradation: The estimators are designed to automatically revert to the standard difference-in-means estimator when policies are distinct (no overlap) or when misspecification is severe, ensuring no performance loss in unfavorable scenarios.

Experimental Results
The authors validate their approach through three experimental settings:

1. Overlapping Policies & Data Imbalance: In a simplified bandit setting, the proposed estimators achieved substantial variance reduction (up to 27x in specific scenarios) when policies were close. The reduction was particularly effective in handling imbalanced user allocations ($n_A \neq n_B$), where the standard difference estimator struggles.
2. Sensitivity to Misspecification: In scenarios with induced errors in propensity estimation, the standard IPS and naive regularized estimators ($h_1$) showed high Mean Squared Error (MSE). In contrast, the proposed misspecification-aware estimators consistently outperformed the difference-in-means baseline, maintaining lower MSE even under moderate to high levels of misspecification.
3. Realistic Recommendation Problem: Simulating a non-Markovian recommendation environment with user boredom, the authors tested horizons $T \in \{1, \dots, 32\}$. The variance-optimal estimator ($f^*_1$) significantly reduced MSE for short to moderate horizons. However, for long horizons, compounding errors in propensity estimation degraded performance. The misspecification-aware estimator provided stable, modest gains across all horizons, outperforming both the standard difference estimator and other OPE-based approaches like DiffQ.

Significance and Claims
The paper claims that off-policy estimation ideas should not merely serve as a substitute for A/B testing but as a tool to enhance the statistical efficiency of A/B testing itself. By leveraging the known or estimated propensities of the systems being tested, practitioners can achieve more accurate improvement estimates with the same sample size. The proposed method is significant because it:

• Requires no changes to the standard A/B testing data collection protocol.
• Is robust to the practical reality of estimated propensities.
• Provides a "best of both worlds" scenario: it offers substantial variance reduction when policies are similar (the common case in iterative system updates) while guaranteeing safety (no worse than standard A/B testing) when they are not.

The authors conclude that while their approach addresses the variance issue in overlapping policies, challenges remain for very long horizons where propensity drift is significant, suggesting future work in exploiting sequential structures and doubly robust methods.