Beyond A/B Testing: How Multi-Armed Bandits Can Scale Complex Experimentation in Enterprise

A/B testing has long been the cornerstone of experimentation in the software and machine learning domains. By comparing two versions of a webpage, application, feature, or algorithm, businesses can determine which version performs better based on predefined metrics of interest. However, as the complexity of business problems or experimentation grows, A/B testing can be a constraint in empirically evaluating successful development. Multi-armed bandits (MAB) is a powerful alternative that can scale complex experimentation in enterprises by dynamically balancing exploration and exploitation.

The Limitations of A/B Testing

While A/B testing is effective for simple experiments, it has several limitations:

1. Static allocation: A/B tests allocate traffic equally or according to a fixed ratio, potentially wasting resources on underperforming variations.
2. Exploration vs. exploitation: A/B testing focuses heavily on exploration, often ignoring the potential gains from exploiting known good options.
3. Time inefficiency: A/B tests can be time-consuming, requiring sufficient data collection periods before drawing conclusions.
4. Scalability: Managing multiple simultaneous A/B tests for complex systems can be cumbersome and resource-intensive.

Multi-Armed Bandits

The multi-armed bandit problem is a classic Reinforcement Learning problem where an agent must choose between multiple options (arms) to maximize the total reward over time. Each arm provides a random reward from a probability distribution unique to that arm. The agent must balance exploring new arms (to gather more information) and exploiting the best-known arms (to maximize reward). In the context of experimentation, MAB algorithms dynamically adjust the allocation of traffic to different variations based on their performance, leading to more efficient and adaptive experimentation. The terms "exploration" and "exploitation" refer to the fundamental trade-off that an agent must balance to maximize cumulative rewards over time. This trade-off is central to the decision-making process in MAB algorithms.

Exploration

Exploration is the process of trying out different options (or "arms") to gather more information about their potential rewards. The goal of exploration is to reduce uncertainty and discover which arms yield the highest rewards.

Purpose

To gather sufficient data about each arm to make informed decisions in the future.

Example

In an online advertising scenario, exploration might involve displaying various different ads to users to determine which ad generates the most clicks or conversions. Even though some ads perform poorly initially, they are still shown to collect enough data to understand their true performance.

Exploitation 

Exploitation, on the other hand, is the process of selecting the option (or "arm") that currently appears to offer the highest reward based on the information gathered so far. The main purpose of exploitation is to maximize immediate rewards by leveraging known information.

Purpose

To maximize the immediate benefit by choosing the arm that has provided the best results so far.

Example

In the same online advertising case, exploitation would involve predominantly showing the advertisement that has already shown the highest click-through rate, thereby maximizing the expected number of clicks.

Types of Multi-Armed Bandit Algorithms

1. Epsilon-Greedy: With probability ε, the algorithm explores a random arm, and with probability 1-ε, it exploits the best-known arm.
2. UCB (Upper Confidence Bound): This algorithm selects arms based on their average reward and the uncertainty or variance in their rewards, favoring less-tested arms to a calculated degree.
3. Thompson Sampling: This Bayesian approach samples from the posterior distribution of each arm's reward, balancing exploration and exploitation according to the likelihood of each arm being optimal.

Implementing Multi-Armed Bandits in Enterprise Experimentation

Step-By-Step Guide

1. Define objectives and metrics: Clearly outline the goals of your experimentation and the key metrics for evaluation.
2. Select an MAB algorithm: Choose an algorithm that aligns with your experimentation needs. For instance, UCB is suitable for scenarios requiring a balance between exploration and exploitation, while Thompson Sampling is beneficial for more complex and uncertain environments.
3. Set up infrastructure: Ensure your experimentation platform supports dynamic allocation and real-time data processing (e.g. Apache Flink or Apache Kafka can help manage the data streams effectively).
4. Deploy and monitor: Launch the MAB experiment and continuously monitor the performance of each arm. Adjust parameters like ε in epsilon-greedy or prior distributions in Thompson Sampling as needed.
5. Analyze and iterate: Regularly analyze the results and iterate on your experimentation strategy. Use the insights gained to refine your models and improve future experiments.

Top Python Libraries for Multi-Armed Bandits

MABWiser

1. Overview: MABWiser is a user-friendly library specifically designed for multi-armed bandit algorithms. It supports various MAB strategies like epsilon-greedy, UCB, and Thompson Sampling.
2. Capabilities: Easy-to-use API, support for context-free and contextual bandits, online and offline learning.

Vowpal Wabbit (VW)

1. Overview: Vowpal Wabbit is a fast and efficient machine learning system that supports contextual bandits, among other learning tasks.
2. Capabilities: High-performance, scalable, supports contextual bandits with rich feature representations.

Contextual

1. Overview: Contextual is a comprehensive library for both context-free and contextual bandits, providing a flexible framework for various MAB algorithms.
2. Capabilities: Extensive documentation, support for numerous bandit strategies, and easy integration with real-world data.

Keras-RL

1. Overview: Keras-RL is a library for reinforcement learning that includes implementations of bandit algorithms. It is built on top of Keras, making it easy to use with deep learning models.
2. Capabilities: Integration with neural networks, support for complex environments, easy-to-use API.

Example using MABWiser.

# Import MABWiser Library 
from mabwiser.mab import MAB, LearningPolicy, NeighborhoodPolicy 

# Data 
arms = ['Arm1', 'Arm2'] 
decisions = ['Arm1', 'Arm1', 'Arm2', 'Arm1'] 
rewards = [20, 17, 25, 9] 

# Model 
mab = MAB(arms, LearningPolicy.UCB1(alpha=1.25)) 

# Train 
mab.fit(decisions, rewards) 

# Test 
mab.predict()

Example from MABWiser of Context Free MAB setup.

# 1. Problem: A/B Testing for Website Layout Design.
# 2. An e-commerce website experiments with 2 different layouts options 
#   for their homepage.
# 3. Each layouts decision leads to generating different revenues
# 4. What should the choice of layouts be based on historical data?

from mabwiser.mab import MAB, LearningPolicy

# Arms
options = [1, 2]

# Historical data of layouts decisions and corresponding rewards
layouts = [1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1]
revenues = [10, 17, 22, 9, 4, 0, 7, 8, 20, 9, 50, 5, 7, 12, 10]
arm_to_features = {1: [0, 0, 1], 2: [1, 1, 0], 3: [1, 1, 0]}

# Epsilon Greedy Learning Policy
# random exploration set to 15%
greedy = MAB(arms=options,
             learning_policy=LearningPolicy.EpsilonGreedy(epsilon=0.15),
             seed=123456)

# Learn from past and predict the next best layout
greedy.fit(decisions=layouts, rewards=revenues)
prediction = greedy.predict()

# Expected revenues from historical data and results
expectations = greedy.predict_expectations()
print("Epsilon Greedy: ", prediction, " ", expectations)
assert(prediction == 2)

# more data from online learning 
additional_layouts = [1, 2, 1, 2]
additional_revenues = [0, 12, 7, 19]

# model update and new layout 
greedy.partial_fit(additional_layouts, additional_revenues)
greedy.add_arm(3)

# Warm starting a new arm
greedy.warm_start(arm_to_features, distance_quantile=0.5)

Conclusion

Multi-armed bandits offer a sophisticated and scalable alternative to traditional A/B testing, particularly suited for complex experimentation in enterprise settings. By dynamically balancing exploration and exploitation, MABs enhance resource efficiency, provide faster insights, and improve overall performance. For software and machine learning engineers looking to push the boundaries of experimentation, incorporating MABs into your toolkit can lead to significant advancements in optimizing and scaling your experiments. Above we have touched upon just the tip of the iceberg in the rich and actively researched literature in the field of Reinforcement Learning to get started.