History of Stats Accelerator and multi-armed bandits

When you set up an A/B test using Optimizely Experimentation, you choose the percentage of visitors (or samples) exposed to each test's variations. This is the test's traffic allocationtraffic allocation. The traffic allocation stays the same unless you manually change it. For example, you may change the allocation to direct more traffic to a variation that performs better than the others.

For several years, Optimizely Experimentation only let you adjust traffic manually. Over time, Optimizely heard from several users that Optimizely's set up was inconvenient and unscalable because they needed to be able to change traffic frequently. Their business needs could be classified into two scenarios:

To help users achieve these two goals, Optimizely Experimentation initially launched Stats Accelerator with two modes: Accelerate Learnings to address the first scenario and Accelerate Impact to address the second. Both modes dynamically change a test's traffic allocation, but their strategies and intent differ vastly.

Optimizely Experimentation partnered with Kevin Jamieson, from the Computer Science and Engineering Department at the University of Washington, who developed an iterative algorithm that discovers significant variations as fast as possible by directing more visitors to the variations with a better chance of reaching statistical significance. This prioritizes finding the variation whose effect size (the observed difference between it and the baseline) is most significant while keeping the false discovery rate under a given threshold. 

For simplicity, Optimizely Experimentation assumes that variations have a true mean greater than the baseline for the rest of this section. This implies that all variations will eventually be found to have statistically significant improvements. Optimizely Experimentation is interested in finding the variation furthest from the baseline in as few samples as possible. This algorithm allocates more traffic to the variation with the highest confidence bound on each iteration. The highest confidence bound is the upper endpoint of the confidence interval that is furthest from 0. At the next iteration, it observes the resulting variations' confidence intervals and empirical mean and makes decisions based on that. When a variation reaches statistical significance, it is taken out of consideration, and the process repeats. The algorithm focuses on the remaining inconclusive variations to determine the next best one.

Variations whose true means are close to the baseline's true mean require more samples to detect this effect size, whereas those furthest away require fewer. To identify the variations whose true means are furthest from the baseline, the algorithm uses the confidence interval by interpreting the upper confidence bound as the highest possible value it will observe of that variation. It picks the one with the highest upper confidence bound and guesses that this is the best-performing one. If correct, the allocated samples will continue reinforcing the empirical mean observed, and the variation will reach statistical significance faster. If wrong, the updated confidence interval and empirical mean would reveal this, and the algorithm refocuses on other variations. It does so according to the exact heuristic used when starting the round that has just been completed: it assumes that the variation whose upper confidence bound is greatest shows the most potential to reach statistical significance first.

See the Experiments section of 'A Bandit Approach to Multiple Testing with False Discovery Control', where the results indicate that this speedup can be at least two to three times faster.

Optimizely Experimentation uses a different algorithm depending on what type of metric the mab optimization is being run on:

See Maximize lift with multi-armed bandit optimizations.

There needs to be a portion of traffic designated for exploratory purposes because the empirical (sample) mean may not be close to its true mean. Epsilon-Greedy and Thompson Sampling in multi-armed bandits are common strategies that address the exploitation-exploration dilemma. 

Thompson Sampling favors early exploration due to uncertainties at the early stages of a test. In contrast, Epsilon-Greedy focuses more on exploitation, funneling most traffic to the variation with the highest empirical mean. If a customer only uses the observed information, they would direct new visitors to the variation with the highest empirical mean. But how do they know if that variation has the highest actual mean? They would need more samples to reduce this uncertainty. This is where exploration becomes essential because that reveals more evidence about the underlying means. Hence, a balance between the two is necessary.

Stats Accelerator also has a form of exploration and exploitation as well. In terms of exploitation, it uses the upper confidence bounds of each variation, allocating more traffic to the highest bound. And if its decision was suboptimal, it would know from the updated results of the test. As a result, it will explore other variations.

See Stats Accelerator compared to multi-armed bandit optimizations for details.

Stats Accelerator – Used to reduce the time to find the best significant variation. Provides you with actionable insight into where the best significant variation can be implemented quickly. It focuses on the statistical uncertainties of the variations, using the confidence intervals to update the test's allocation to reduce the time to find the best significant variation.

Multi-armed bandit – Used for promotions, sales, or anything temporary, where the intent is to drive more traffic to a variation with the highest metric value. It only focuses on the variations' empirical mean to maximize some payoff by funneling more traffic to the winning variation.