Multi-Armed Bandits

You walk into a casino, with three slot machines. One of them pays better, but you don't know which. Every coin you spend testing is a coin not spent on the best machine. Websites face this exact puzzle. Which headline should we show? Each visitor is a coin.

• Three machines, one is better
• Testing costs money
• Each visitor is a coin

Epsilon greedy

The simplest strategy is called epsilon greedy. Ten percent of the time, explore, and show a random advert. The rest of the time, exploit, and show the current best. We simulate twenty thousand visitors. The true click rates are hidden from the algorithm. Run it. Look at the counts. It quickly found the best advert, and showed it far more than the others. Unlike a classic A B test, which splits visitors evenly until the end, a bandit shifts traffic to the winner while it learns.

import numpy as np

rng = np.random.default_rng(1)
true_rates = [0.03, 0.05, 0.08]   # unknown click rates of three adverts
counts = np.zeros(3)
wins = np.zeros(3)

for visitor in range(20000):
    if rng.random() < 0.1:
        ad = rng.integers(3)
    else:
        ad = (wins / np.maximum(counts, 1)).argmax()
    counts[ad] += 1
    wins[ad] += rng.random() < true_rates[ad]

print("Times each advert was shown:", counts.astype(int))
print("Measured rates:", (wins / counts).round(3))

Times each advert was shown: [ 1601  2993 15406]
Measured rates: [0.033 0.055 0.083]

Summary