Repeated A/B Testing

Nicolò Cesa-Bianchi, Tommaso R. Cesari, Yishay Mansour, Vianney Perchet

Abstract

We introduce a novel theoretical framework for Return On Investment (ROI) maximization in repeated decision-making. Our setting is motivated by the use case of companies that regularly receive proposals for technological innovations and want to quickly decide whether they are worth implementing. We design an algorithm for learning ROI-maximizing decision-making policies over a sequence of innovation proposals. Our algorithm provably converges to an optimal policy in class $\Pi$ at a rate of order $\min\big\{1/(N\Delta^2),N^{-1/3}\}$, where $N$ is the number of innovations and $\Delta$ is the suboptimality gap in $\Pi$. A significant hurdle of our formulation, which sets it aside from other online learning problems such as bandits, is that running a policy does not provide an unbiased estimate of its performance.

Introduction

In the technology industry, companies are constantly evaluating new features or innovations through A/B testing. While these tests are essential for data-driven decision-making, they are not cost-free; they consume time, computational resources, and user attention. Traditional machine learning frameworks, such as Multi-Armed Bandits, typically focus on maximizing cumulative rewards. However, in industrial contexts, the primary objective is often the Return on Investment (ROI)—the ratio of total value gained to the total cost incurred during testing. This paper addresses the challenge of learning optimal decision-making policies that maximize this ratio over a sequence of innovation proposals.

The Problem of Bias and Ratios

Maximizing ROI introduces two significant theoretical hurdles. First, ROI is a multiplicative metric, making standard additive regret minimization techniques inapplicable. Second, a "Bias Problem" arises: if a policy decides to reject an innovation early to conserve costs, the true value of that innovation remains unknown. This selection bias makes it mathematically impossible to obtain an unbiased estimate of a policy's performance solely from the data it chooses to observe.

Methodology: The CAPE Algorithm

To address these challenges, we propose the Capped Policy Elimination (CAPE) algorithm. CAPE is designed to select the best policy from a finite set $\Pi$. The core innovation of CAPE is an "oversampling" strategy. During an initial exploration phase, the algorithm collects more samples than any single policy would typically require. These additional samples allow for the construction of unbiased estimates for the rewards and costs of all candidate policies simultaneously.

Algorithm 1: Capped Policy Elimination (CAPE)

For scenarios involving an infinite (countable) set of policies—such as varying decision thresholds—we introduce the Extension to Countable (ESC) preprocessing step. ESC identifies a baseline policy with positive reward to bound the search space, effectively reducing the infinite problem to a finite one manageable by CAPE.

Key Insights

A critical theoretical finding is the Impossibility Result, which proves that unbiased estimation of a policy's reward is impossible without observing more data than the policy itself requires. This necessitates the oversampling approach used in CAPE.

Furthermore, the analysis reveals that focusing on the False Discovery Rate (FDR) is often suboptimal for ROI. A policy that occasionally accepts slightly negative innovations may be superior to one that spends excessive resources to ensure perfect accuracy, as the latter misses opportunities to identify high-value "home run" innovations. ROI maximization requires a global analysis over the entire sequence of $N$ tasks rather than round-by-round additive regret analysis.

Results and Convergence

The CAPE algorithm demonstrates strong theoretical performance. For a finite policy set, it converges to the optimal policy at a rate of $1/(N\Delta^2)$, where $\Delta$ represents the suboptimality gap. In cases where the gap is negligible, the algorithm maintains a convergence rate of $N^{-1/3}$. The combined ESC-CAPE approach preserves this $N^{-1/3}$ rate even for infinite policy sets.

Limitations and Future Work

While CAPE provides a robust framework for ROI maximization, several avenues for future research remain. The current model assumes a stationary (I.I.D.) distribution of innovation quality, which may not hold if "easy wins" are exhausted over time. Additionally, while the $N^{-1/3}$ rate is conjectured to be optimal, a formal lower bound proof is still needed. Extending these results to non-stochastic or adversarial settings also presents an interesting challenge for future work.

Summary updated

Abstract

We introduce a novel theoretical framework for Return On Investment (ROI) maximization in repeated decision-making. Our setting is motivated by the use case of companies that regularly receive proposals for technological innovations and want to quickly decide whether they are worth implementing. We design an algorithm for learning ROI-maximizing decision-making policies over a sequence of innovation proposals. Our algorithm provably converges to an optimal policy in class $\Pi$ at a rate of order $\min\big\{1/(N\Delta^2),N^{-1/3}\}$, where $N$ is the number of innovations and $\Delta$ is the suboptimality gap in $\Pi$. A significant hurdle of our formulation, which sets it aside from other online learning problems such as bandits, is that running a policy does not provide an unbiased estimate of its performance.
BibTeX
@inproceedings{cesabianchi2021repeated,
  author = {Nicolò Cesa-Bianchi and Tommaso R. Cesari and Yishay Mansour and Vianney Perchet},
  title = {{Repeated A/B Testing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=4idcxaFrEw},
}
Figure