Multi-Armed Bandits: ε-greedy, UCB1 and Thompson Sampling

After reading this you will know how three bandit strategies decide which arm to pull, how to compute their regret by hand, and why greedy plateaus while UCB1 and Thompson sampling bend toward flat.

What a bandit problem is

Picture a row of k slot machines. Each machine (an "arm") pays out 1 with some fixed probability and 0 otherwise. You do not know these probabilities. You have a budget of pulls, and you want to collect as much reward as you can.

The tension is simple. To learn which arm is best you must try arms that might be bad. Every pull spent testing a weak arm is a pull you did not spend on the best one. That is the exploration versus exploitation dilemma, stripped of everything else. There is no state, no sequence of moves, just repeated choices from the same fixed set.

Concrete hook: suppose there are three arms with true payout rates 0.3, 0.5 and 0.55. The best arm pays 0.55. If a strategy runs for 1000 pulls and earns 500 reward on average, it lost 1000 \times 0.55 - 500 = 50 compared with an oracle that always played arm 3. That gap of 50 is the regret. The whole game is keeping it small.

Regret, the one number that matters

Let \mu^{*} be the mean of the best arm and \mu_{a_t} the mean of the arm you actually pulled at step t. Cumulative regret after T pulls is:

R(T) = T \mu^{*} - \sum_{t=1}^{T} \mu_{a_t}

Here T \mu^{*} is what the oracle earns and the sum is the expected reward of your choices. Notice regret uses the true means, not the noisy rewards you observed. It measures decision quality, not luck.

An equivalent form makes the driver visible. Let \Delta_a = \mu^{*} - \mu_a be the gap of arm a, and let n_a(T) be how many times you pulled it:

R(T) = \sum_{a} \Delta_a \, n_a(T)

Regret is the sum, over arms, of each arm's gap times how often you chose it. Pulling the best arm costs 0 (its gap is zero). Pulling a slightly worse arm costs a little. The art is spending your mistakes on cheap arms early, then stopping.

Good algorithms achieve regret that grows like O(\ln T): doubling the horizon adds only a constant amount of regret. Greedy grows like O(T), a straight line, because it can lock onto a wrong arm forever.

The three strategies and their rules

Each strategy keeps, for every arm, an estimated mean \hat{\mu}_a (successes divided by pulls) and a pull count n_a. They differ only in how they turn those numbers into a choice.

ε-greedy

With probability \varepsilon pull a uniformly random arm; otherwise pull the arm with the highest \hat{\mu}_a. If \varepsilon = 0.1 and there are three arms, then on any step you explore with probability 0.1 and exploit with probability 0.9. Simple, but the exploration never stops, so it pays a constant tax forever.

UCB1

Pull the arm that maximises an optimistic score:

\text{UCB}_a = \hat{\mu}_a + c \sqrt{\frac{2 \ln t}{n_a}}

The first term is what you believe. The second is a confidence bonus that is large when n_a is small and shrinks as you pull the arm. As total time t grows, \ln t grows slowly, nudging you to revisit neglected arms. The constant c (often 1) scales how bold you are. This is optimism in the face of uncertainty: an unexplored arm looks good until proven otherwise.

Thompson sampling

Keep a Beta posterior per arm: \text{Beta}(s_a + 1, f_a + 1) where s_a is successes and f_a is failures. Each step, draw one random sample from every arm's posterior and pull the arm with the largest sample. The randomness lives in the belief, not in the choice. An arm you are unsure about has a wide posterior and sometimes samples high, so it gets tried. As evidence accumulates, posteriors narrow and the best arm wins almost every draw.

A worked example on the demo data

Run the lab with its defaults: three arms and the hidden means shown below. The numbers here are computable by hand so you can check the mechanics of one step.

One UCB1 decision at step 30

Suppose after 29 pulls the counts and estimated means are these:

State just before pull 30 (t = 30)
Arm	True mean	Pulls n_a	Estimate μ̂_a
1	0.30	5	0.200
2	0.50	9	0.556
3	0.55	15	0.533

Compute \ln 30 = 3.401, so 2 \ln 30 = 6.802.
Arm 1 bonus: \sqrt{6.802 / 5} = \sqrt{1.360} = 1.166. Score 0.200 + 1.166 = 1.366.
Arm 2 bonus: \sqrt{6.802 / 9} = \sqrt{0.7558} = 0.869. Score 0.556 + 0.869 = 1.425.
Arm 3 bonus: \sqrt{6.802 / 15} = \sqrt{0.4535} = 0.673. Score 0.533 + 0.673 = 1.206.
Highest score is arm 2 at 1.426, so UCB1 pulls arm 2.

Notice what happened. Arm 3 has the best estimate but the smallest bonus because it has been pulled most. Arm 1 has the worst estimate but the largest bonus. Arm 2 wins on the sum. This is the mechanism that keeps under-sampled arms in play without ever choosing randomly.

The chart below shows the shape you should expect after a full run of a few thousand pulls with these means.

Thompson sampling regret rising fast early then flattening. Doubling t from 1000 to 2000 adds only about 3 regret, the logarithmic signature.

Reading the results in the lab

Three things are worth watching side by side.

The regret curves. A straight rising line means linear regret and a strategy stuck on a wrong arm; pure greedy often does this. A curve that bends toward horizontal means the strategy has mostly found the best arm and is now paying little. ε-greedy usually sits between: it bends but keeps a constant upward slope equal to \varepsilon \cdot \bar{\Delta}, where \bar{\Delta} is the average gap of the non-best arms. With \varepsilon = 0.1, two suboptimal arms of average gap 0.15, and uniform exploration, that slope is about 0.1 \times 0.15 = 0.015 regret per pull, or 15 extra regret every 1000 pulls that never goes away.

Per-arm pull counts. A healthy UCB1 or Thompson run puts the vast majority of pulls on the best arm and only a logarithmic trickle on the rest. If greedy shows most pulls on the second-best arm, it got unlucky early and locked in.

Thompson's Beta posteriors. Early on all three curves are wide and overlapping. As pulls accumulate, the best arm's posterior narrows and shifts right, and its sampled values dominate. When one posterior clearly separates from the rest, exploration has effectively ended.

When to reach for a bandit, and when not

Bandits fit problems where you repeatedly choose one option from a fixed set, get quick feedback, and the world does not remember your past choices. Website headline testing, ad selection, and choosing which of several treatments to show next are classic fits. Compared with a fixed A/B test, a bandit shifts traffic toward the winner while the test runs, so it wastes fewer impressions on the loser.

Bandits do not fit when your action changes the state you land in. If pulling an arm moves you to a new situation with new options, you have a full reinforcement learning problem, not a bandit. For that, see the Q-Learning Gridworld, where actions move an agent between cells, or the CartPole Balancing AI, where each action changes the physics you face next.

The clean logarithmic regret bounds assume the arm means are fixed. If payouts drift over time (a headline gets stale, a season changes), a strategy that has converged will not notice. Real systems handle this with discounting or sliding windows, which this lab does not simulate.

Common mistakes

Reading regret off a single run. One run is noisy. A strategy can look great because it got lucky on its first few pulls. Regret bounds are statements about the average over many runs. Reset and re-run several times before trusting the ranking.

Setting ε too high forever. A fixed \varepsilon = 0.3 keeps you exploring one pull in three even after the best arm is obvious. That is a permanent tax of roughly 0.3 \times \bar{\Delta} per pull. If you insist on ε-greedy, decay it, for example \varepsilon_t = 1/t, so exploration fades.

Confusing reward with regret. A lucky greedy run can earn high reward while still having high regret, because regret is measured against the true best arm, not against the noisy outcomes. Judge strategies by regret.

Expecting arms with tiny gaps to separate fast. Two arms at 0.55 and 0.54 differ by 0.01. Telling them apart needs far more pulls than arms at 0.3 and 0.6, because the signal is buried in Bernoulli noise. Small gaps mean slow convergence for every strategy.

Comparing the strategies at a glance

Typical ordering: greedy worst (linear), ε-greedy paying a steady tax, UCB1 and Thompson lowest. Exact values vary by run and by the true means.

The ranking above is typical, not guaranteed. Thompson sampling and UCB1 trade places depending on the arm means and the constant c. Both beat a fixed ε-greedy over a long horizon because their exploration shrinks instead of staying constant. Greedy trails whenever an unlucky early draw hides the best arm.

Frequently asked questions

Why does pure greedy sometimes win short runs?

Over a few dozen pulls the exploration bonuses of UCB1 and the wide posteriors of Thompson force them to test weak arms, while a greedy run that happened to sample the best arm first pays nothing. That advantage is fragile. Extend the horizon and greedy's linear regret overtakes the others.

What value of c should I use for UCB1?

The theory uses c = 1 with the \sqrt{2 \ln t / n} bonus. Larger c explores more (safer if gaps are tiny, slower to converge); smaller c explores less and risks greedy-like lock-in. Try 0.5, 1 and 2 on the same means and compare the regret curves.

Why add 1 to successes and failures in Thompson sampling?

The Beta(1, 1) prior is uniform on [0, 1], meaning "before any data, every payout rate is equally plausible." Adding observed successes and failures updates it to Beta(s + 1, f + 1). With zero data the posterior is flat, so early samples range widely and every arm gets a fair chance.

Does Thompson sampling need the rewards to be 0 or 1?

The Beta posterior shown here assumes Bernoulli (0/1) rewards, which is what this lab uses. Thompson sampling generalises to other reward distributions by swapping in the matching conjugate prior (for example a Normal posterior for continuous rewards), but the 0/1 case is the cleanest to reason about.

Is lower regret always the goal?

In this lab, yes: it isolates decision quality. In production you may also care about variance across runs, how fast a strategy reacts to change, and how simple it is to implement and audit. Thompson sampling and ε-greedy are both easy to code; UCB1 needs the running counts but no random number generator.

Try it yourself in the tool