Multi-armed bandits

The big idea

You walk into a casino with a row of slot machines, each paying out with a different, unknown probability. You have 1,000 coins. Every coin you put in a machine teaches you a little about that machine, and every coin spent on a poor machine is money lost. Play the machine that has done best so far and you may never discover a better one. Keep trying them all and you waste coins on machines you already know are bad. This is the exploration-exploitation trade-offThe tension between using the option that currently looks best (exploit) and trying other options to learn whether they are better (explore)., and the slot machine puzzle, the multi-armed banditA sequential decision problem with several options (arms) of unknown average reward: each round you pick one, see its reward, and try to maximize the total. The simplest reinforcement learning problem: one state, no transitions., is reinforcement learning with everything else removed: one state, no consequences beyond the reward itself.

Bandits are not just a toy. Every A/B test, every choice of which headline, thumbnail or price to show, and every new item that needs some traffic to prove itself ( Cold start, diversity and feedback loops ) is a bandit. Three strategies cover most practice: explore at random a fixed share of the time, explore where uncertainty is highest, or explore in proportion to the chance of being best.

How it works

Step 1: Measuring a strategy by regret

Each arm $i$ pays a reward with mean ${\mu }_i$, unknown to you. Let ${\mu }^{\ast }$ be the best arm's mean. After $T$ pulls, your regretThe reward a bandit strategy lost compared with always playing the best arm: T times the best mean minus the expected reward of the arms actually pulled. is what you gave up by not always pulling the best arm:

Example: arms pay 5 and 9 percent. Pulling the 5 percent arm 200 times out of 1,000 costs $200\times (0.09-0.05)=8$ expected wins. A strategy that keeps exploring at a fixed rate has regret that grows in a straight line with $T$. A good strategy explores less as it learns, so its regret curve bends and flattens. Lai and Robbins proved that regret must grow at least logarithmically in the number of pulls, and Auer, Cesa-Bianchi and Fischer showed simple strategies that achieve logarithmic regret.

Step 2: Epsilon-greedy

The simplest strategy: with probability $\epsilon$ (say 0.1) pull a random arm; otherwise pull the arm with the best average so far. It is easy to explain and to implement. Its weakness is that it explores blindly forever: it keeps spending 10 percent of pulls on arms it has known to be bad for a long time, and it explores a clearly hopeless arm as often as a promising one. With $\epsilon =0$ it is pure greed, and it can lock onto the first arm that pays out.

Step 3: Upper confidence bound

UCBA bandit strategy that scores each arm by its average reward plus a bonus that is large when the arm has few pulls, then picks the highest score: optimism in the face of uncertainty. follows "optimism in the face of uncertainty". Score each arm by its average plus a bonus that is large when it has been tried rarely, and pick the highest score. The classic version, UCB1, uses

where ${\bar{x}}_i$ is arm $i$'s average reward, $n_i$ its number of pulls, and $t$ the total pulls so far. An arm is pulled either because its average is high or because we know little about it. As $n_i$ grows the bonus shrinks, so exploration fades on its own. The $\ln t$ term slowly raises every bonus, so no arm is abandoned forever.

Step 4: Thompson sampling

Thompson samplingA bandit strategy that keeps a probability distribution over each arm's mean, draws one sample from each, and pulls the arm with the highest sample, so each arm is chosen with the probability that it is the best. keeps a belief about each arm's payout rate. For win/lose rewards that belief is a Beta distribution: start at Beta(1, 1), which is flat, and after $w$ wins and $l$ losses it is Beta($1+w$, $1+l$). Each round, draw one random sample from every arm's belief and pull the arm with the highest draw.

An arm with a wide belief sometimes draws a high sample and gets tried; an arm whose belief is narrow and low almost never does. The net effect is that each arm is pulled with roughly the probability that it is the best one. Thompson described the idea in 1933. In the code and the lab below it beats UCB1 clearly.

Step 5: Contextual bandits

So far every user is the same. A contextual banditA bandit whose best arm depends on observed features (the context), such as the user's history or device, so the strategy learns a model from context to reward per arm. sees features first (the user's history, country, device, time of day), then chooses an arm. Instead of one average per arm it learns a model that predicts each arm's reward from the context, and explores with any of the strategies above: LinUCB adds a confidence bonus to a linear model, and Thompson sampling draws from a posterior over the model. Contextual bandits are reinforcement learning where actions do not change future states: each decision is scored on its own immediate reward.

Try it

• With the defaults (payouts from 4 to 9 percent, 2,000 pulls), Thompson sampling has the lowest regret (33.6, against 51.6 for UCB1 and 64.5 for epsilon-greedy), but it has put only 40 percent of its pulls on machine 5. Raise pulls to 5,000: Thompson's share rises to 64 percent and its regret curve flattens, while UCB1's keeps climbing to 113.9.
• Set epsilon to 0. Pure greed locks onto machine 1 for the whole run, and its regret is a straight line: 99.9 after 2,000 pulls.
• Pick "one clear winner". Thompson finds machine 4 almost at once (96 percent of pulls, regret 13.8 at 2,000), while UCB1's bonus keeps it testing the poor machines (regret 128.8). Then press New luck a few times to see how much one run can vary.

Going deeper

Code: four strategies, 200 runs

import numpy as np

# Five slot machines (arms) with hidden payout probabilities. Each strategy gets 5,000 pulls;
# regret = pulls x best probability - expected payout of the arms actually pulled.
P = np.array([0.04, 0.05, 0.06, 0.07, 0.09])
T, RUNS = 5000, 200

def run(strategy, rng, eps=0.1):                      # all RUNS games at once, one row each
    n, s = np.ones((RUNS, len(P))), (rng.random((RUNS, len(P))) < P) * 1.0   # pull every arm once
    regret, rows = np.zeros(T), np.arange(RUNS)
    for t in range(T):
        if strategy == "eps":                           # explore with probability eps, else best mean
            a = np.where(rng.random(RUNS) < eps, rng.integers(len(P), size=RUNS), np.argmax(s / n, 1))
        elif strategy == "ucb":                         # UCB1: mean + sqrt(2 ln t / n)
            a = np.argmax(s / n + np.sqrt(2 * np.log(t + len(P)) / n), 1)
        else:                                           # Thompson: sample each arm's Beta posterior
            a = np.argmax(rng.beta(1 + s, 1 + n - s), 1)
        s[rows, a] += rng.random(RUNS) < P[a]; n[rows, a] += 1
        regret[t] = np.mean(P.max() - P[a])
    return regret.cumsum(), n[:, -1].mean() / n.sum(1).mean()

for name, kw in [("epsilon-greedy 0.1", dict(strategy="eps")), ("epsilon-greedy 0.01", dict(strategy="eps", eps=0.01)),
                 ("UCB1", dict(strategy="ucb")), ("Thompson sampling", dict(strategy="thompson"))]:
    R, best = run(rng=np.random.default_rng(1), **kw)
    print(f"{name:20s} regret after 500: {R[499]:5.1f}  after 5000: {R[-1]:6.1f}  share of pulls on best arm {best:.0%}")

# Contextual: two kinds of users, two artworks. Artwork A suits group 0, artwork B suits group 1.
rng = np.random.default_rng(2)
Pc = np.array([[0.10, 0.04], [0.03, 0.08]])            # Pc[group, artwork]
wins = {"one best artwork for all": 0, "best artwork per group": 0}
s, n = np.zeros((2, 2)), np.zeros((2, 2))
s1, n1 = np.zeros(2), np.zeros(2)
for t in range(20000):
    g = rng.integers(2)
    a1 = np.argmax(rng.beta(1 + s1, 1 + n1 - s1))       # ignores the group
    a2 = np.argmax(rng.beta(1 + s[g], 1 + n[g] - s[g])) # Thompson sampling per group
    r1, r2 = rng.random() < Pc[g, a1], rng.random() < Pc[g, a2]
    s1[a1] += r1; n1[a1] += 1; s[g, a2] += r2; n[g, a2] += 1
    wins["one best artwork for all"] += r1; wins["best artwork per group"] += r2
for k, v in wins.items():
    print(f"{k:25s} plays per 1,000 impressions: {v / 20:.1f}")

epsilon-greedy 0.1   regret after 500:  12.9  after 5000:   53.3  share of pulls on best arm 63%
epsilon-greedy 0.01  regret after 500:  19.8  after 5000:  136.4  share of pulls on best arm 31%
UCB1                 regret after 500:  13.1  after 5000:  116.0  share of pulls on best arm 30%
Thompson sampling    regret after 500:  10.7  after 5000:   44.0  share of pulls on best arm 70%
one best artwork for all  plays per 1,000 impressions: 60.5
best artwork per group    plays per 1,000 impressions: 87.5

The same five machines as the lab's first scenario (4, 5, 6, 7 and 9 percent), 5,000 pulls, averaged over 200 independent runs.

• Thompson sampling has the lowest regret: 44.0 after 5,000 pulls, with 70 percent of pulls on the best machine.
• Epsilon-greedy with 0.1 reaches 53.3; its regret keeps growing in a straight line because 10 percent of pulls are always random.
• Epsilon-greedy with 0.01 is worse, 136.4: with so little exploration it often settles on a second-best machine.
• UCB1 reaches 116.0 and only 30 percent of pulls on the best machine. Its bonus $\sqrt{2\ln t/n}$ is sized for rewards anywhere between 0 and 1, which is far wider than the gaps between payouts of a few percent, so it keeps exploring for a long time. Tune or pick the algorithm for the reward scale you actually have.

The last part is a contextual example: two groups of users and two artworks, where artwork A suits group 0 (10 against 4 percent) and B suits group 1 (8 against 3 percent). A bandit that ignores the group earns 60.5 plays per 1,000 impressions; Thompson sampling per group earns 87.5, close to the 90 that always choosing perfectly would give.

Bandits against A/B tests

An A/B test splits traffic evenly until the end, then switches everyone to the winner. That gives a clean estimate of the difference, but every user in the losing arm pays for it: the regret of the test. A bandit shifts traffic toward the better arm while it learns, so it loses less, but the estimate of how much better it is becomes less precise, and it assumes the arms do not change over time. Use A/B tests when you need to know the size of an effect; use bandits when you mainly want to earn while choosing, or when there are many options or they change often.

Practical details

• Delayed rewards. A purchase may come days after an impression. Update in batches and keep exploring while waiting.
• Drifting payouts. Click rates change with seasons and news. Discount old observations or use a sliding window.
• Logging. Record the probability with which each arm was chosen. With those probabilities you can evaluate a new policy on old logs, as in the Netflix case below.

Trade-offs

Common mistakes

• Running pure greedy (epsilon 0) and calling it a bandit: it locks onto early luck.
• Comparing strategies by one run. Bandit results vary a lot run to run; average many.
• Using UCB1's default bonus for rewards that are tiny probabilities, so it over-explores.
• Not logging the choice probabilities, which makes later offline evaluation impossible.
• Treating a contextual problem as a plain bandit, so the "best" arm is an average that is best for nobody.

In the wild

Check yourself

Recap