Multi-Armed Bandit

Compare ε-greedy, UCB and Thompson sampling on slot machines with hidden payouts

Beginner

The slot machines

Arm 1

p = ?

Arm 2

p = ?

Arm 3

p = ?

Arm 4

p = ?

Arm 5

p = ?

Each pull pays 1 with the arm's hidden probability p, otherwise 0. All three strategies play their own copy of the same machines, one pull each per step.

Controls

Arms5ε (ε-greedy)0.10c (UCB1)1.0Seed

Speed

Step 0 of 5,000. ε and c can be changed mid-run; changing arms or seed starts over.

ε-greedy

Total reward

Regret

0.0

Arm	Pulls	Est.
1	0	–
2	0	–
3	0	–
4	0	–
5	0	–

UCB1

Total reward

Regret

0.0

Arm	Est.	Upper bound
1	–	∞
2	–	∞
3	–	∞
4	–	∞
5	–	∞

Thompson sampling

Total reward

Regret

0.0

Arm	Est.	Post. mean
1	–	0.500
2	–	0.500
3	–	0.500
4	–	0.500
5	–	0.500

Cumulative regret

ε-greedyUCB1Thompson sampling

Regret adds up p_best − p_chosen on every pull. A curve that flattens means the strategy has settled on the best arm.

Thompson sampling posteriors

Arm 1 Beta(1, 1)

Arm 2 Beta(1, 1)

Arm 3 Beta(1, 1)

Arm 4 Beta(1, 1)

Arm 5 Beta(1, 1)

Each curve is Beta(1 + wins, 1 + losses): what Thompson sampling believes about that arm's payout rate. Wide curves still get explored; narrow ones low down are abandoned.

How to use this visualizer

1
Press Run. Every step, each of the three strategies pulls one arm of its own copy of the machines.
2
Watch the pull counts: a good strategy ends up pulling the best arm most of the time. The highlighted row is the arm just pulled.
3
Compare the cumulative regret curves. ε-greedy grows in a straight line; UCB1 and Thompson sampling bend over and flatten.
4
Watch the Thompson posteriors sharpen. Click Reveal payout rates to see where the true rates lie.
5
Change ε and c mid-run. UCB1's theory uses c = √2, but that explores cautiously; on these machines c around 0.5 to 1 usually earns less regret.
6
Press New machines for a fresh set of payout rates; sets where two arms are close are the hardest.

The explore-exploit dilemma

Picture a row of slot machines, each paying out with a different unknown probability. Every pull you must choose: play the machine that has paid best so far, or try another one that might be better. Too little exploring and you can get stuck on a mediocre arm. Too much and you waste pulls on arms you already know are poor.

The multi-armed bandit is reinforcement learning with a single state: there is no future to plan for, only the trade-off between learning and earning. The same trade-off appears in A/B testing, ad selection, clinical trials and recommendation systems.

Exploration

Pull arms you know little about, in case one of them is better than your current favourite.

Exploitation

Pull the arm that looks best so far, to collect reward now.

Regret

Reward lost compared with always pulling the best arm. Good strategies keep it growing slowly.

Uncertainty

An arm pulled 3 times has a much less reliable estimate than one pulled 300 times. UCB and Thompson sampling use this.

Strategy	Idea	Regret growth
ε-greedy	Exploit the best estimate, but explore a random arm with probability ε	Linear (keeps exploring forever at rate ε)
UCB1	Pick the arm with the highest optimistic upper bound on its value	Logarithmic, O(log T)
Thompson sampling	Sample a plausible rate from each posterior and pick the highest sample	Logarithmic, often lowest in practice

Key formulas

Sample-average estimate

Q(a) = (total reward from a) / N(a)

Q(a): estimated payout rate of arm a
N(a): number of times arm a has been pulled

UCB1

a_t = argmax_a [ Q(a) + c √( ln t / N(a) ) ]

t: total pulls so far
c: exploration strength; c = √2 is the classic UCB1 choice

Thompson sampling with a Beta posterior

θ_a ~ Beta(1 + S(a), 1 + F(a)), then play argmax_a θ_a

S(a), F(a): wins and losses of arm a so far
Beta(1, 1): the uniform prior we start from

Cumulative regret

Regret(T) = Σ_t=1..T ( p* − p_{a_t} )

p* is the best arm's true rate. This is the expected regret, so luck on individual pulls does not add noise.

Code

Python

import math, random

def epsilon_greedy(counts, wins, eps):
    if random.random() < eps:
        return random.randrange(len(counts))
    return max(range(len(counts)), key=lambda k: wins[k] / counts[k] if counts[k] else 0)

def ucb1(counts, wins, c=math.sqrt(2)):
    for k, n in enumerate(counts):
        if n == 0:
            return k                      # try every arm once
    t = sum(counts)
    return max(range(len(counts)),
               key=lambda k: wins[k] / counts[k] + c * math.sqrt(math.log(t) / counts[k]))

def thompson(counts, wins):
    samples = [random.betavariate(1 + wins[k], 1 + counts[k] - wins[k]) for k in range(len(counts))]
    return max(range(len(counts)), key=lambda k: samples[k])

# After pulling arm k and seeing reward r (0 or 1):
#   counts[k] += 1; wins[k] += r

Practice problems

Problem 1: Which arm does UCB1 pull?

After t = 100 pulls, arm A has been pulled 40 times with average reward 0.60, and arm B 10 times with average 0.50. Using c = √2 ≈ 1.414, which arm does UCB1 pull next?

Show solution

ln 100 ≈ 4.605

A: 0.60 + 1.414 × √(4.605 / 40) = 0.60 + 1.414 × 0.339 ≈ 1.080

B: 0.50 + 1.414 × √(4.605 / 10) = 0.50 + 1.414 × 0.679 ≈ 1.460

B has the lower estimate but far more uncertainty, so its upper bound is higher.

UCB1 pulls arm B

Problem 2: Same mean, different certainty

Under Thompson sampling, arm A has 7 wins in 10 pulls and arm B has 1 win in 1 pull. What are their posteriors and posterior means, and what is the chance that B's sample exceeds 0.9?

Show solution

A: Beta(1 + 7, 1 + 3) = Beta(8, 4), mean 8 / 12 ≈ 0.667

B: Beta(1 + 1, 1 + 0) = Beta(2, 1), mean 2 / 3 ≈ 0.667

Beta(2, 1) has density 2x and CDF x², so P(θ > 0.9) = 1 − 0.9² = 0.19

For Beta(8, 4) the same probability is only about 0.02, because its posterior is much narrower.

Equal means, but B is sampled above 0.9 about 19% of the time, so it still gets explored

Discussion

Questions, ideas or a different approach? Join the conversation.