On the Complexity of A/B Testing
  A/B testing refers to the task of determining the best option among two
alternatives that yield random outcomes. We provide distribution-dependent
lower bounds for the performance of A/B testing that improve over the results
currently available both in the fixed-confidence (or delta-PAC) and
fixed-budget settings. When the distribution of the outcomes are Gaussian, we
prove that the complexity of the fixed-confidence and fixed-budget settings are
equivalent, and that uniform sampling of both alternatives is optimal only in
the case of equal variances. In the common variance case, we also provide a
stopping rule that terminates faster than existing fixed-confidence algorithms.
In the case of Bernoulli distributions, we show that the complexity of
fixed-budget setting is smaller than that of fixed-confidence setting and that
uniform sampling of both alternatives -though not optimal- is advisable in
practice when combined with an appropriate stopping criterion.
