{"id":50560,"date":"2020-03-24T18:16:37","date_gmt":"2020-03-24T12:46:37","guid":{"rendered":"https:\/\/vwo.com\/blog\/?p=50560"},"modified":"2025-05-05T16:59:33","modified_gmt":"2025-05-05T11:29:33","slug":"multi-armed-bandit-algorithm","status":"publish","type":"post","link":"https:\/\/vwo.com\/blog\/multi-armed-bandit-algorithm\/","title":{"rendered":"Multi-Armed Bandit (MAB) \u2013 A\/B Testing Sans Regret"},"content":{"rendered":"\n

Most readers of this blog would be familiar with A\/B Testing<\/a>. Just as a quick reminder, A\/B Testing is an experiment where a random visitor to your digital property is shown a different version than the original (also called \u2018control\u2019) in an optimizer\u2019s quest to discover an optimal version that maximizes conversions. <\/p>\n\n\n\n

For example, maybe it\u2019s the red button that maximized clicks or maybe it\u2019s the blue button. Who knows? Well, your A\/B test would know. Systematically done A\/B tests, with effective a\/b testing tools<\/a>, can lead to a big improvement in conversion as Moscow-based Tinkoff Bank discovered a 36% uplift<\/a>.<\/p>\n\n\n\n

However, in this quest to maximize conversions, there is a cost that is inevitable \u2013 while the A\/B tests are in progress, a sizable portion of the traffic is routed to a losing variant directly reducing business metrics (like sales or conversions). <\/p>\n\n\n\n

It is said that in an A\/B test, the cost of increasing conversions is the conversions, per se. We say, \u2018touche\u2019.<\/p>\n\n\n\n

Let us take the example of Jim, a UX Analyst, who works with a mobile brand that is launching its latest and greatest handset next week. To hype the demand and trigger wildfire sales, Jim decides to run flash sales on the company\u2019s mobile app for 3 days.<\/p>\n\n\n\n

Here is a rider, though \u2013 Jim is aware that the brand\u2019s in-app navigation is poor (he ran a survey with active users to arrive at the conclusion) and visitors find it difficult to locate the product.<\/p>\n\n\n\n

To improve navigation, he decided to do an experiment where he created a variation with more intuitive navigation leading users directly into the flash sales funnel to test if this version would solve discovery issues for the new handset. In short, Jim is trying to improve a crucial KPI \u2013 the percentage of sessions in which users were able to discover the new handset<\/em>.<\/p>\n\n\n\n

He looks at incoming data from the experiment and observes that the tweaks to in-app navigation are demonstrating a strong uplift. Jim is trigger-happy though \u2013 he wants to share early results with the senior leadership and get them equally excited. Just as he is about to barge into the CMO\u2019s cabin with a copy of early trends to convince her to direct more traffic towards the new navigation, he is stopped in his tracks by a quip from a Data Scientist.<\/p>\n\n\n\n

\u201cJim, these trends are great but are they statistically robust? Where is the significance?\u201d<\/p>\n\n\n\n

\u201cBut we don\u2019t have time to wait for it! The sale ends in 3 days!\u201d Jim grunts.<\/p>\n\n\n\n

Who is right? Jim, who is tasked with doing the best possible within 3 days, or the data scientist who is questioning the statistical significance<\/a>? Well, both are and here\u2019s why.\u00a0<\/p>\n\n\n\n

Remember the earlier quip about the cost of increasing conversions, being the conversions? Jim\u2019s situation warrants an approach that minimizes the cost of running an A\/B test. The loss of conversions due to the low-performing variation is called Bayesian<\/a> regret. <\/p>\n\n\n\n

Minimizing the regret is especially important in time-sensitive situations, or in cases where the cost of poor variations is so high that businesses hesitate to run A\/B tests.<\/p>\n\n\n\n

Since Jim is relying on a three-day window to maximize sales, he can\u2019t wait for statistical significance and lose out on conversions, which sometimes takes weeks (or months, for low-traffic websites). If he waits for statistical significance, he won\u2019t be able to use the results as the 3-day window will be over.<\/p>\n\n\n\n

If only Jim had Multi-Armed Bandit<\/a> algorithms to use, this issue wouldn\u2019t have happened. Here\u2019s why.<\/p>\n\n\n\n

\"slot<\/figure>\n\n\n

What is multi-armed bandit testing?<\/strong><\/h2>\n\n\n

MAB is a type of A\/B testing that uses machine learning to learn from data gathered during the test to dynamically increase visitor allocation in favor of better-performing variations. What this means is that variations that aren\u2019t good get less and less traffic allocation over time.\u00a0<\/p>\n\n\n\n

The core concept of MAB is \u2018dynamic traffic allocation\u2019 \u2013 it\u2019s a statistically robust method to continuously identify the degree to which a version is outperforming others and to route the majority of the traffic dynamically and in real-time to the winning variant.<\/p>\n\n\n\n

Unlike A\/B tests, MAB maximizes the total number of conversions during the course of the test. The trade-off is that statistical certainty takes a backseat because the focus is on conversions and finding out the exact conversion rates (of all variations, including the worst-performing ones).<\/p>\n\n\n

What is the multi-armed bandit problem?<\/strong><\/h2>\n\n\n

MAB is named after a thought experiment where a gambler has to choose among multiple slot machines with different payouts, and a gambler\u2019s task is to maximize the amount of money he takes back home. Imagine for a moment that you\u2019re the gambler. How would you maximize your winnings? <\/p>\n\n\n\n

As you have multiple slot machines to choose from, you can either determine payout possibilities by taking a chance with all the machines, and collecting enough data until you know for sure which machine is the best.\u00a0<\/p>\n\n\n\n

Doing this will reveal to you the exact payoff ratio of all the slot machines, but in the process, you would have wasted a lot of money on low-payoff machines. This is what can happen in an A\/B test. The alternative is to focus on a few slots faster, continuously evaluate winnings, and maximize your investments over these slots for higher returns. This is what happens in the multi-armed bandit approach.<\/p>\n\n\n\n

\"an<\/figure>\n\n\n

Exploration and exploitation<\/strong><\/h2>\n\n\n

To understand MAB better, there are two pillars that power this algorithm \u2013 \u2018exploration\u2019 and \u2018exploitation\u2019. Most classic A\/B tests are, by design, forever in \u2018exploration\u2019 mode \u2013 after all, determining statistically significant results is their reason for existence, hence the perpetual exploration. <\/p>\n\n\n\n

In an A\/B test, the focus is on discovering the exact conversion rate of variations. MAB adds a twist to A\/B Testing \u2013 exploitation. Owing to the \u2018maximize conversions and profit\u2019 intent of MAB, exploitation, and exploration, run in parallel, akin to a train track \u2013 think of the algorithm exploring at a rate of many visitors per second, arriving at constantly shifting winning baselines and continuously allocating the majority of your traffic dynamically to the variant that has a higher chance of winning in that instant (exploitation).<\/p>\n\n\n\n

It may sound like MAB uses heuristics to allocate more traffic to better performing variation. However, under the hood, VWO\u2019s implementation of MAB is statistically robust. VWO uses a mathematical model to continuously update the estimated conversion rates of variations and allocates traffic in direct proportion to those estimates. <\/p>\n\n\n\n

As the estimate of best-performing variation gets better, that variation gets a higher percentage of traffic. In case you\u2019re interested in learning the mathematics of VWO\u2019s MAB algorithm, you may want to read more about a concept called Thompson Sampling<\/a> or you can request a demo<\/a> from our optimization specialists to get to know more about how it works.<\/p>\n\n\n\n

Over the test cycle, the algorithm balances between exploration and exploitation phases. As high performers garner more conversions, the traffic split continues to widen and reaches a point where a vast majority of users are getting served the better performing variation. MAB thus allows Jim from our example above, to progressively roll out the best version of his mobile app, without having to wait for his tests to reach statistical significance.<\/p>\n\n\n\n

\"Ab<\/figure>\n\n\n\n

Exploration v\/s Exploitation in A\/B Testing and Bandit Selection<\/p>\n\n\n

Why A\/B Testing is better than MAB<\/strong><\/h2>\n\n\n

When weighing the pros and cons of multi-armed bandit vs A\/B testing, understand that they both solve different use cases due to their distinct focuses. An A\/B test is done to collect data with its associated statistical confidence. A business then uses the collected data, interprets it in a larger context and then makes a decision. <\/p>\n\n\n\n

In contrast, multi armed bandit algorithms maximize a given metric (which is conversions of a particular type in VWO\u2019s context). There\u2019s no intermediate stage of interpretation and analysis as the MAB algorithm is adjusting traffic automatically. What this means is that A\/B testing is perfect for cases where:<\/p>\n\n\n\n