Table of Contents

Multi-Armed Bandits

Imagine this scenario: we're in a casino. There are many different slot machines (known as "one-armed bandits", as they're known for robbing people), each with a lever (an arm, if you will). We think that some slot machines payout more frequently than others do, and our goal is to walk out of the casino with the most money.

The question is, how do we learn which slot machine rewards us with the most money in the shortest amount of time? We could try all the slot machines out to get a sense of the expected return from playing each machine. But remember, each time we play a poor performing machine, we lower our take that we walk out of the casino with that night. In order to maximize how much money we walk out of the casino with, we will have to be efficient with how we collect our data.

Rewriting the scenario above into a business language. Each time a shopper looks comes to a webpage, we show them one of the $K$ variations of the webpage. They either click on it or do not, and we log this information about the (binary) reward for each $K$ variations. Next, we proceed to the next shopper and have to choose one of $K$ webpage variations again.

Differences Between A/B Testing and Bandit Testing

In both scenarios above, we would normally determine our "winner" (the slot machine that pays the most, or the best webpage variations that gets the most clicks) using the well-known A/B testing approach. The A/B testing approach consists of a period of pure exploration, where we're randomly assigning equal numbers of users to one of the $K$ variations and run the test until it's valid. After that, it jumps into pure exploitation, where you send 100% of your users to the more successful version of your site.

Two possible problems with the classical A/B testing approach is that:

• It jumps discretely from exploration to exploitation, when we might be able to transition more smoothly.
• During the exploratory phase (the test), it wastes resources exploring inferior options in order to gather as much data as possible.

Given the exploration - exploitation dilemma stated above, the bandit testing approach try to account for this. The following graph depicts the difference between the two types of testing method:

If we have three variations that we wish to test, the A/B testing approach we try out each of the three variations with equal proportions until we are done with our test at week 5, and then select the variation with the highest value.

As for bandit testing, it attempts to use what it knows about each variation from the very beginning, and it continuously updates the probabilities that it will select each variation throughout the optimization process. In the above chart we can see that with each new week, the bandit testing reduces how often it selects the lower performing options and increases how often if selects the highest performing option.

We need to explore in order to figure out what works and what doesn't. On the other hand, if we exploit we take advantage of what we have learned. The bandit testing approach highlights the fact that collecting data also has its cost.

To be specific, bandit testing algorithms will try to minimize what's known as regret, which is the difference between our actual payoff and the payoff we would have collected had we played the optimal (best) options at every opportunity. There are tons of different bandit methods, in the next section we'll look at some of the more common ones.

Bandit Algorithms

Before introducing the algorithms and trying them out through simulations, we'll denote some notations and terminologies to formally define the problem:

• Arms is simply the variations that we're testing (webpages that we're testing) and there will be $K$ of them in total.
• In a simulation of $t$ turns (how many samples in a simulation), we'll maintain empirical means of the reward for each arm (e.g. after trying out arm A for 10 turns, it got 3 clicks, the empirical means is simply 0.3) that are updated at every turn $t$.
• $u_i(t)$ is the empirical mean of arm $i$ after $t$ turns.
• $p_i(t)$ is the probability of picking arm $i$ at turn $t$.

Let's look at our simulated data before diving into each algorithms (hopefully the docstrings are self-explanatory).

Algorithm 1 - Epsilon Greedy

At each round $t = 1, 2, ...$ the Epsilon Greedy algorithm will:

• Choose a random arm with the probability of $\epsilon$.
• Choose the arm with the current best empirical mean with probability of $1-\epsilon$.

In mathematical notations:

\begin{align} p_i(t+1)= \begin{cases} 1 - \epsilon + \epsilon \big/ K & \quad \text{if i = } argmax_{j = 1, ..., K} \ u_j(t) \\ \epsilon \big/ K & \quad otherwise \end{cases} \end{align}

Or more intuitively:

• When a new visitor comes to the site, the algorithm flips a coin that comes up tail with the probability of $\epsilon$. When it does in fact comes up tail, the algorithm is going to explore. The exploration phase is to randomly choose amongst any possible arm with equal (uniform) probability and showing it to the visitor.
• On the other hand, the algorithm will exploit the best known solution with the probability of $1- \epsilon$. To exploit, the algorithm looks up the current empirical means and shows the best one to the visitor.

The image below sums up the algorithm pretty well.

The decrease_const parameter in the function above may look unfamiliar.

For the Epsilon Greedy algorithm, setting the $\epsilon$ can be a bit tricky. If it's too small, exploration will be slow at the beginning, and we will be slow to react to changes. If we happen to sample, say, the second-best arm the first few times, it may take a long time to discover that another arm is actually better. If $\epsilon$ is too big, we'll waste many trials pulling random arms without gaining much.

To accommodate for this situation, we will set the $\epsilon$ value at a higher value in the beginning and anneal (gradually lower) it over time. Intuitively, this simply means that after exploring around for a while, we become more certain about each arms' empirical means. After that, it's better to exploit.

In the function call above, the $\epsilon$ at turn $t$ will become:

\begin{align} \epsilon(t) = \epsilon(0) \Big/ (1 + t/T) \end{align}

Where $T$ is a new parameter that represents a decreasing constant.

Note that there are different ways of annealing a parameter, but the spirit is the same.

Algorithm 2 - Boltzmann Exploration (Softmax)

The Softmax algorithm picks each arm with a probability that is proportional to its average reward.

\begin{align} p_i(t+1)= \frac{ e^{u_i(t) / \tau} }{ \sum_{j=1}^K e^{u_j(t) / \tau} } \end{align}

Where $\tau$ is a temperature parameter, controlling the randomness of the choice. When $\tau$ = 0, the algorithm acts like pure greedy. As $\tau$ grows to infinity, the algorithm will pick arms uniformly at random.

Algorithm 3 - Upper Confidence Bounds (UCB)

In the world of statistics, whenever we estimate some unknown parameter (such as the mean of a distribution) using random samples, there is a way to quantify the uncertainty inherent in our estimate. For example, the true mean of a fair six-sided die is 3.5. But if we only roll it once and get a 2, our best estimate of the mean is just 2. Obviously that estimate is not very good, and we can quantify the confidence we have for our estimate. There are confidence bounds which can be written, for example, as: "The mean of this die is 2, with a 95-th percentile lower bound of 1.4 and a 95-th percentile upper bound of 5.2."

The upper confidence bound (UCB) family of algorithms, as its name suggests, selects the arm with the largest upper confidence bound at each turn. The intuition is this: the more times we roll the die, the tighter the confidence bounds, and if we roll the die an infinite number of times then the width of the confidence bound is zero. In short, as the number of rolls increases, the uncertainty decreases, and so does the width of the confidence bound.

Thus, unlike Epsilon Greedy and Softmax algorithm that only keeps track of the empirical means, the UCB algorithm also maintains the number of times that each arm has been played, denoted by $n_i(t)$. Initially, each arm is played once. Afterwards, at round t, the algorithm greedily picks the arm $j(t)$ as follows:

\begin{align} j(t) = argmax_{i = 1, ..., K} \left( u_i + \sqrt{\frac{2 \cdot ln(t)}{n_i}} \right) \end{align}

We can see that the UCB algorithm will try to learn about arms that we don't know enough about. The main advantages of these types of algorithms are:

• Take uncertainty of sample mean estimate into account in a smart way.
• No parameters (e.g. epsilon, annealing) to validate.

Experimenting With Bandit Algorithms

In this section, we'll use our simulated data to experiment with our algorithms. To do this we'll also need a metric to calculate how well we are doing. Recall the absolute best we can do is to always pick the webpage (arm) with the largest click through rate (ctr). Denote this best arm's probability of $w_{opt}$. Our score should be relative to how well we would have done had we chosen the best arm from the beginning. This motivates the total regret of a strategy, defined as:

\begin{align} R_T & = \sum_{t=1}^{T} \left( w_{opt} - w_{I(t)} \right) \nonumber \\ & = Tw_{opt} - \sum_{t=1}^{T} \; w_{I(t)} \end{align}

Where $T$ is the total number of samples in the experiment, $w_{I(t)}$ is the probability of obtaining the reward (getting clicked) of the chosen arm in the $t_{th}$ turn. A total regret of 0 means the strategy is attaining the best possible score. This is likely not possible, as initially our algorithm will often make the wrong choice. Ideally, a strategy's total regret should flatten as it learns the best bandit. (Mathematically, we achieve $w_{I(t)} = w_{opt}$ often)

We'll run the experiment and plot the cumulative regret of the three algorithms below:

Section Conclusion: The plot of the cumulative expected regret of the experiment above showed that all three different algorithms have converged (the cumulative expected regret gradually decreases to a steady level). And the UCB seems to be doing better than the other two algorithms in this limited horizon as the way to read the graph is the lower the better (the y-axis represents regrets).

Bayesian Bandits

Next, we'll introduce a Bayesian method called Thompson Sampling. Recall that the the problem we want to solve is the following. We came up with $K$ different variations of the webpage (e.g. different layout) and we wish to find the ones with the best click through rate (CTR), e.g. clicking to sign-up for the newsletter. Let's represent each CTR by $\theta_i$ - i.e., $\theta_i$ is the true probability that an individual user will click when they were shown with the $i_{th}$ webpage. It is important to note that we don't actually know what $\theta_i$ is - if we did, we could simply choose $i$ for which $\theta_i$ was largest and move on. We're simply pretending that we know in order to simulate the performance of the algorithm.

Using the Bayesian approach we will construct a prior probability distribution which represents our original belief about what the actual value of $\theta_i$, our ctr for the $i_{th}$ webpage is. The prior we'll use is the Beta distribution. Here's a quick recap of the distribution:

Beta Distribution

The Beta distribution is very useful in Bayesian statistics. A random variable $X$ has a Beta distribution, with parameters $(\alpha, \beta)$, if its density function is:

\begin{align} f_X(x | \; \alpha, \beta ) = \frac{ x^{(\alpha - 1)}(1-x)^{ (\beta - 1) } }{B(\alpha, \beta) } \end{align}

where $B$ is the Beta function (hence the name). The random variable $X$ is only allowed in [0,1], making the Beta distribution a popular distribution for decimal values, probabilities and proportions. The values of $\alpha$ and $\beta$, both positive values, provide great flexibility in the shape of the distribution. Below we plot some Beta distributions with different $\alpha$ and $\beta$ values:

There are two important things to note about the Beta distribution:

The first is the presence of the flat distribution above, specified by parameters $(1,1)$. This is the Uniform distribution. Hence the Beta distribution is a generalization of the Uniform distribution.

The second is that there is an interesting connection between the Beta distribution and the Binomial distribution. Suppose we are interested in some unknown proportion or probability $p$. We assign a $\text{Beta}(\alpha, \beta)$ prior to $p$. We observe some data generated by a Binomial process, say $X \sim \text{Binomial}(N, p)$, with $p$ still unknown. Then our posterior is again a Beta distribution, i.e. $p | X \sim \text{Beta}( \alpha + X, \beta + N -X )$. Succinctly, one can relate the two by "a Beta prior with Binomial observations creates a Beta posterior".

In light of the above two paragraphs, if we start with a $\text{Beta}(1,1)$ prior on $p$ (which is a Uniform), observe data $X \sim \text{Binomial}(N, p)$, then our posterior is $\text{Beta}(1 + X, 1 + N - X)$.

Thompson Sampling

So after assuming the priors on the probability of ctr for each webpage. To be explicit on the phrase "assuming the priors", we will assume that we're completely ignorant of these probabilities. So a very natural prior is the flat prior over 0 to 1, $\text{Beta}(\alpha=1,\beta=1)$. The algorithm then proceeds as follows:

For each turn:

1. Sample a random variable $X_i$ from the prior of arm $i$, for all $i$ ($K$ in total).
2. Select the arm with largest sample, i.e. select $i = \text{argmax}\; X_i$.
3. Observe the result of pulled arm $i$, and update your prior with that arm $i$.
4. Return to 1.

Like all the algorithms we've introduced before, Thompson Sampling suggests that we should not discard losers, but we should pick them at a decreasing rate as we gather confidence that there exist better webpages (arms). This follows because there is always a non-zero chance that a webpage with a lower ctr will get chosen, but the probability of this event decreases as we play more rounds.

In our simulation, we gave the Bayesian bandit two webpages (arms) - one had a CTR of 0.25, the other had a CTR of 0.35. To start with, both webpages were displayed to the user with roughly equal probability. Over time, evidence accumulated that arm 2 was considerably better than arm 1. At this point the algorithm switched to displaying primarily webpage 1, and the overall CTR of the experiment converged to 0.35 (the optimal CTR).

We can also visualize our Beta distribution for each arms in different turns.

As we can see, we started out with some prior Beta distributions that represents the our initial beliefs about possible ctr values for each arm. We then update these beliefs based on evidence by showing different webpages to other randomly chosen users and observing the ctr. After doing this for many number of turns, we incrementally narrow the width of each arm's Beta distribution. Meaning that as we gather more data, we become more confident about each arm's actual ctr.

Note that we don't really care how accurate we become about the inference of the hidden probabilities — for this problem we are more interested in becoming more confident in choosing the best arm. This is basically why at the end of experiment, arm 1's distribution is wider. The algorithm is ignorant about what that hidden probability might be, but we are reasonably confident that it is not the best, so the algorithm chooses to ignore it.

From the above, we can see that starting after 100 pulls, the majority of arm 2's distribution already leads the pack, hence the algorithm will almost always choose this arm. This is good, as this arm is indeed better.

Notes On Bandit Testings

In world settings, we need to account for situations such as delayed batch update or delay feedback. In such cases, algorithms such as Epsilon Greedy, Softmax, UCB needs the distributions to be updated every single round to work properly. On the other hand, Thompson Sampling is more realistic as it relies on random samples, which will be different every time even if the distributions are each arm aren't updated for a while.

So, after gaining some knowledge on bandit testings. The question that comes into our head is that: "In general, when is it preferred over the classical A/B testing?"

Short-term testing

"Whenever you have a small amount of time for both exploration and exploitation, use a bandit testing."

Bandit testing are conducive for short tests for clear reasons – if you were to run a classic A/B testing you’d not even be able to enjoy the period of pure exploitation. Instead, bandit testing allow you to adjust in real time and send more traffic, more quickly, to the better variation. Here are some possible use cases:

• Headlines: News has a short life cycle. Why would you run A/B testing on a headline if by the time you learn which variation is best, the time where the answer is applicable is over?
• Holiday Campaigns: e.g. If you’re running tests on an ecommerce site for Black Friday, an A/B testing isn’t that practical – you might only be confident in the result at the end of the day. On the other hand, a bandit testing will drive more traffic to the better-performing variation – and that in turn can increase revenue.

Long-term testing

Because Bandit testing automatically shift traffic to higher performing (at the time) variations, thus it is effective in long term (or ongoing) testing where you can set it and forget about it. e.g. Serving specific ads and content to user sets (targeting ads).

Reference

• Notes: Algorithms for the multi-armed bandit problem
• Blog: When to Run Bandit Tests Instead of A/B Tests
• Blog: Bayesian Bandits - optimizing click throughs with statistics
• Blog: Balancing Earning with Learning: Bandits and Adaptive Optimization
• Notebook: Bayesian Methods for Hackers Chapter 6