[cmansley]

I think the real distinction here is stationary verses non-stationary distributions. Many of the arguments made in this article hinge on the fact that the responses to the same input change over time (nights are different then daytime, which is different than the weekends). By continuously running the A/B testing, you are looking at a small window in time, which you assume is stationary so you can do your t-tests or whatever statistical test.

But, to be clear, this is a heuristic in A/B testing. If you have a window of time over which you know your distributions are stationary, you should always use a logarithmic regret MAB algorithm because it is theoretically better.

I think the best way to frame this argument is that because the domain does not match the assumptions of MAB, A/B testing has been shown to be robust and easy to modify for non-stationary domains, while logarithmic regret algorithms are somewhat more fragile.

[btilly]

Correction.

A/B testing does not need to assume that it is testing over a small window in time that has stationary conversion rates. In fact in practice tests run for a long window of time over which you have good evidence that the distribution is not stationary. For example in the middle of running a long test that eventually found a small lift, I've often run and rolled out a second test that generated a much stronger lift.

The weaker assumption that you need is that the preference between versions is stable across your fluctuations. Then because the mix of versions is time independent, that non-stationary fluctuation is not statistically different between the slice that was put into A and the slice that was put into B. And therefore the variation between different samples becomes just another unknown random factor that does not interfere with your statistical analysis of whether there is a difference.

This is an advantage between A/B testing and the current state of the art in MAB algorithms. When this came up before, Noel (at Myna) and I privately did an admittedly brief search of the literature for discussion of this point with regards to MAB algorithms. We turned up a number of things that would work in the long run, but none that directly addressed the problem.

But in discussion we did manage to come up with effective MAB algorithms, whose regret is only a constant factor worse than standard MAB algorithms, that accurately will identify stable preferences in the face of constantly fluctuating conversion rates. To the best of my knowledge nobody, including Noel, has yet implemented such algorithms in practice. But in principle it can be done.

However even if you do it, several of my other points still apply as real differences.

[cmansley]

Wait.

I am slightly confused and this may demonstrate my ignorance, but I was under the impression that A/B testing worked by allocating two different approach to the users and then scoring the response. This provides a sampling from the population of users as to how effective A or B is. You can then run some statistical test on the averages of the scores for each test to determine which one is the winner.

If what I said is true, these statistical tests almost always assume that the distribution that is being drawn from is stationary. So, the only way things work out is if you have an underlying stationary distribution. Otherwise, your statistical test might indicate the wrong thing.

I freely admit that many of your points are still valid, but I don't see how A/B is a more powerful algorithm that has less assumptions.

[btilly]

Perhaps stepping back can clarify.

The necessary, reasonable, and much weaker assumption needed for A/B testing is that users are independent of each other, and arrive by some Poisson process. Meaning that at any given point in time there is some average rate that users arrive, but each user's arrival is independent of all other arrivals. (More mathematically precisely, the number of people who will arrive in any specified time period follows a Poisson distribution. Poisson processes accurately model everything from nuclear decay counts to emergency room arrivals.) If you randomly divide a group of people who arrived by a Poisson process into two subgroups in a fixed ratio (say, evenly), those subgroups will also turn out to be generated by a Poisson process.

Now we're going to take those subgroups, and feed them into our versions. Let's focus on what happens with version A. Depending on when a user arrived, that user will have some chance of converting to a success, and some chance of not doing so. If we look at a random user that arrived and ignore when they arrived, their probability of converting will be the average of their probability of converting, weighted by the rate of arrival. Furthermore our assumption that users are arriving from a Poisson process means that each user is statistically independent from all of the others. Now it is true that if we pay attention to the fact that certain users arrived close to others, there are likely correlations to be found between those specifically users. But if you sample two random users from all of the users who could have arrived, they will be independent and have an identical probability of conversion, which is that average. (This flows out of the assumption that the initial population came from a Poisson process.)

This same analysis can be done for A and for B. Now we don't know the actual conversion rates over our trial. But suppose that we did know them, and it happened to be that the conversion rate for B is better at every time than for A. Then it it is easy to show that the average conversion rate (weighted by arrival rate of course) over the whole interval for B would be better than for A.

Therefore if we assume that there is a consistent preference, statistical evidence over the sample that B converts better than A is valid statistical evidence that B is actually the better version at any given point in time. This holds even if the difference between their conversion rate is much lower than the fluctuation of the conversion rates of both over the interval we sampled from.

(Very helpfully for A/B test practitioners, this math works whether or not you happen to understand it. As long as you're not adjusting sampling rates, A/B tests are statistically valid.)

Now take a traditional MAB algorithm. The whole analysis that I just did falls apart. The fact that we send traffic to the versions at different rates at different points of time means that the average for random people in the two versions is weighted differently over the interval. This opens up the possibility that the average conversion rate of the whole sample for B can be better than for A, yet A might at every point in time have had a better conversion rate than B.

See http://en.wikipedia.org/wiki/Simpsons_paradox if that seems impossible to you. If you've read that and understand how being better in the sample that a MAB algorithm collected is not statistical evidence that you're actually better, then you may want to re-read this post to understand why an A/B test is still statistically valid.

To avoid this trap, what you need to do in the MAB algorithm is either subsample or scale data (subsampling is provably more robust but not much so, scaling is simpler and converges faster) so that the statistical decision that you're basing your MAB choices on avoids this pitfall, at least in the limit. But as I said before, a detailed discussion of how to make this work and the necessary trade-offs would get fairly involved.

[cmansley]

I don't know how we got onto arrival rates of our visitors. I would just like to state that Simpson's paradox is exactly why we shouldn't compare percent conversions. They are meaningless. However, many of the statistical tests like Student's t-test compensate for this paradox by including the number of samples in the tests. See : http://en.wikipedia.org/wiki/Student%27s_t-test#Unequal_samp...

I think you said one thing that are at the heart of the issue. We assume that the E[conversion of B] > E[conversion of A] for the entire period sampled.

I think all of the details about Poisson processes are not required if you just assume that each person is drawn IID from the population.

I just don't think you are answering the right questions here.

Let's assume that each person arrives IID from the infinite population. Then, we have a Bernoulli process for each A or B query. A "conversion" results in a 1, a failure results in a 0. Since, these people are arriving IID, we can select a sub-sample which is also IID. We would now like to estimate the parameters for each process and/or compare the two processes. We can do this using t-test. This will give us the statistical significance that the one group had a higher "conversion rate" than the other group. Note: rate does not factor into this problem at all because we assume the participants were IID, so the t-test (used correctly accounting for different number of samples) will tell us which test is larger.

My question is now what happens when the parameters of your queries for A or B change over time. Still under the assumption that E[B] > E[A], it now matters greatly in which order you use your samples.

I think the only reason you brought the Poisson model into the discussion is to weight the more recent samples higher and down weight the earlier samples in your basket of samples. This is a heuristic for considering a fixed interval in which the samples are stationary. It effectively considers a window that slides with the time of arrival.

[btilly]

First let me mention that you should not try to use the Student's t-test. One of the first assumptions of the Student's t-test is that Each of the two populations being compared should follow a normal distribution. In A/B tests this assumption is almost never true, and therefore the Student's t-test is an inappropriate statistical assumption.

OK, now to what I said about Poisson distributions. Assuming that people arrive on a Poisson distribution allows us to conclude 2 key facts:

1. The statistics will behave exactly like it would if each person arrives IID from an infinite population.

2. Simpson's paradox will not apply to the theoretical distribution of the samples for A and B.

Assuming #1 without #2 does not get you very far. But having facts #1 and #2 allows us to use statistics.

I have no idea why you would speculate that I am attempting to weight recent samples higher and downweight earlier samples. All samples are, in fact, weighted exactly the same. This fact notwithstanding, different times of arrival are not weighted the same. That is because the sample rate fluctuates over time depending on factors such as traffic levels on your webserver. But it fluctuates in an identical way for the two versions. (This fact is critical in being able to conclude point #2.)

Does this help?

[cmansley]

First, I was using Student t-test as a stand-in for whatever test or statistical measure you would like to use. I believe the popular one is Hoeffding's inequality in the bandit literature, hence the log term in the MAB algorithms. I agree this was a poor choice of example.

Second, I believe I am getting hung up on the fact that different arrival times are "weighted" differently. I think you are claiming that the Poisson assumption gives us equal numbers of A and B trials, so we can combined the statistics (counts) and avoid Simpson's paradox. This is fine, but why would you say "different times of arrival are not weighted the same". Does this mean you are somehow weighting periods of heavy traffic down and weighting low traffic up?

So, what happens when trial A becomes less favorable over time or is less favorable for brief periods? This means that the underlying random variable's mean is changing over time. Most statistical bounds cannot handle this situation.

I am not saying that A/B testing is not something we should do in general. I am saying that it is a good heuristic with very few provable properties compared with logarithmic regret MAB algorithms.

[cmansley]

Also, I agree that MAB algorithms do not consider the case of adding bandit "arms" during the trial. A dynamic number of bandit arms problem may not be well studied, but is very interesting. This might be another reason for requiring a reweighing of the samples.