1 Introduction

When you have different options with an unknown reward rate, how do you explore the different options to maximize rewards. The name multi-arm bandit comes from considering multiple slot machines with unknown payouts. This problem comes up a lot in the area of web optimization when you are trying to measure if a user takes an action or not. There are many approaches to solving this problem such as ϵ-greedy, softmax, UCB1 and Thompson sampling [1]. The differences between these algorithms is how they decide to explore/exploit arms based on previous results. I’ll go over ϵ-greedy to motivate the basic concept and Thompson sampling for a mathematically precise objective.

2 ϵ-greedy

The best arm is the arm with the highest historical success rate. At each trial, choose an arm with probability,

The best arm is recomputed after each trial. Each of the other arms are sampled with equal probability. ϵ controls how much time you spend exploring versus exploiting, it is typically chosen to be 0.1. The problem with ϵ-Greedy is that it can get stuck on the bad solution for a while.

3 Bernoulli distribution

A Bernoulli random variable is 1 with a probability p and 0 with a probability q = 1 - p. Usually 1 represents the event occur and 0 represent an event not occurring. This can be expressed with the probability mass function,

For a fair coin, p = 0.5 is the probability of a head appearing (k = 1).

4 Confidence interval

The confidence interval tells you how likely the true p is in a range. We can estimate p by conducting repeated Bernoulli trials.

where N is the total population size, n is the sample size, is the measured proportion and z_α∕2 is the confidence level desired by looking up n in the t-distribution table.

N is usually large, so finite population correction factor term,

leaving

where z_α∕2 is read from the normal error integral table as show in Table 1 instead of the t-distribution. For 95% confidence interval, z_α∕2 = 1.96, from adding row 1.9 and column 0.06 together.

5 β distribution

The next building block is the β distribution. The β distribution is the probability distribution of what the true p is based on observations. The probability density function is

where α,β > 0. Figure 1 shows the distribution for different values of α and β. α - 1 can be thought of as the number of times a trial succeeded and β - 1 the number of times a trial failed. In the beginning, we can assume maximum ignorance. We have no idea if the even always occurs, never occurs or what the chances of occurring would be, so the probability is uniform across all possibilities. If we assume there is chance for the event to occur and a chance for it to not occur, then we can start with α,β = 2. If in the next trial, the even doesn’t occur, we increment β to 3. So, we have 1 event occurring from 3 trials and our β distribution peaking at 1/3. As we get more information from each successful trial, our β distribution shifts.

6 Thompson sampling

Thompson sampling is when arms are sampled according the probability that each arm is the best arm [2]. This avoids getting stuck on bad arms and the algorithm will explore arms to get more information about which one is the best.

Each arm can be represented by a β distribution. If we randomly sample each distribution, we can get an estimated value of p. We choose the arm with the highest p. This minimizes the regret since we are choosing the arms with the best chance of being the best. Bad arms will be avoided once enough information is collected and arms with close distributions will be sampled equally until their distributions diverge.

In Python, numpy.random.beta draws samples from a β distribution. The results of a simulation using Thompson sampling is shown in Figure 2. The confidence interval decreases with increasing number of trials as .

References