Multi-armed bandits: epsilon-greedy, UCB and Thompson sampling, explained and measured

A multi-armed bandit is a problem where you repeatedly choose one of several options, each with an unknown reward rate, and see the reward only for the option you chose. The goal is to collect as much reward as possible while you are still learning which option is best, which forces a trade-off between exploiting the current favourite and exploring the others. Epsilon-greedy, upper confidence bound (UCB) and Thompson sampling are the three standard algorithms for it.

Bandits are the smallest problem in which exploration has a price, which is why courses on reinforcement learning start with them, and they sit behind adaptive A/B tests, ad allocation and clinical trial designs. This guide derives the three algorithms and their regret bounds, runs them against each other in seeded simulations, and measures the part most introductions skip: what an adaptive bandit costs you in statistical power and bias.

What is a multi-armed bandit? A concrete example#

The name comes from slot machines, once called one-armed bandits, and the problem was posed formally by Robbins in 1952 [1]: a gambler facing a row of them must decide which levers to pull, and how often, without knowing their payout rates. Suppose you have five versions of a sign-up page and each visitor either converts or does not. Unknown to you, their conversion rates are 0.30, 0.45, 0.50, 0.55 and 0.60. A visitor sent to the 0.30 page costs 0.30 conversions in expectation; one sent to the 0.55 page costs only 0.05, but that page is also the hardest to tell apart from the best.

Two naive strategies fail in opposite directions. Splitting traffic evenly for 10,000 visitors (a classic A/B/n test) learns the rates well but sends four fifths of visitors to worse pages, losing exactly 1,200 conversions in expectation. Always sending visitors to whichever page looks best so far (pure greedy) often locks onto the wrong page after a few unlucky early visitors. In our simulation below the greedy strategy ended on the best page in only 42% of runs. Bandit algorithms sit between the two, exploring in proportion to how plausible each arm still is and shifting traffic to the winner as evidence arrives.

Regret: how bandit algorithms are scored#

Write ${\mu }_i$ for the mean reward of arm $i$, ${\mu }^{\ast }={\max }_i{\mu }_i$ for the best mean, and ${\Delta }_i={\mu }^{\ast }-{\mu }_i$ for the gap of arm $i$. If $N_i(T)$ is the number of times arm $i$ was pulled in the first $T$ steps, the expected regret is

Here $A_t$ is the arm chosen at step $t$, and the expectation is over both the rewards and any randomness in the algorithm. The second form is the useful one: regret is a weighted count of mistakes, where pulling an arm with a small gap is a small mistake and pulling a terrible arm is a big one. A good algorithm therefore stops pulling clearly bad arms quickly and spends its exploration on the arms that are close to the best. Every regret number below is this quantity (pseudo-regret), averaged over seeded runs.

Linear regret means mistakes at a fixed rate forever (the uniform split loses 0.12 conversions per visitor); regret growing like $\ln T$ means mistakes become ever rarer. How slowly can it grow? Lai and Robbins answered this in 1985 [3]. For any algorithm that is reasonable on every instance (its regret is $o(T^a)$ for every $a>0$),

$\mathrm{KL}({\mu }_i,{\mu }^{\ast })$ is the Kullback-Leibler divergence between Bernoulli distributions with means ${\mu }_i$ and ${\mu }^{\ast }$: how distinguishable one pull of arm $i$ is from one pull of the best arm. The bound says each suboptimal arm must be pulled about $\ln T/\mathrm{KL}({\mu }_i,{\mu }^{\ast })$ times, or the algorithm risks never finding out that it is suboptimal. Arms that look almost like the best one are expensive to rule out. For our five arms the constant is 19.5, so the asymptotic rate at $T=10,000$ is $19.5\ln 10,000\approx 180$. Almost all of that constant comes from the 0.55 arm: its gap is only 0.05 and its KL divergence from the 0.60 arm is 0.0051, contributing 9.7 on its own.

Is a multi-armed bandit reinforcement learning?#

Yes, in the sense that it is the simplest case of it. A Markov decision process has states, actions, transitions and rewards; a bandit is an MDP with a single state that every action returns you to. What disappears is the hard part of full reinforcement learning, credit assignment over time: in a bandit, an action's consequences arrive immediately and do not change what happens next, so there is no need for Bellman equations or bootstrapped value estimates. What remains is the other hard part, the exploration-exploitation trade-off, in its purest form.

The bandit estimates ${\hat{\mu }}_i$ are the one-state version of the action values $Q(s,a)$ used everywhere else in RL, and the exploration rules below reappear almost unchanged: epsilon-greedy is the default behaviour policy in Q-learning, and optimism in the face of uncertainty is the idea behind count-based exploration bonuses in larger problems [11].

Epsilon-greedy#

Keep a running average ${\hat{\mu }}_i$ of the rewards from each arm. With probability $1-\epsilon$ pull the arm with the highest average; with probability $\epsilon$ pull an arm chosen uniformly at random. The average is updated incrementally after each pull of arm $i$:

where $N_i$ is the number of pulls of arm $i$ including this one and $r$ is the reward just observed. This "old estimate plus step size times error" form is the template for every value update in reinforcement learning; replace $1/N_i$ with a constant step size and it is the Q-learning update with no next state.

Epsilon-greedy explores blindly: it spends as much traffic on the 0.30 arm, obviously bad after a few hundred pulls, as on the 0.55 arm, which is genuinely hard to rule out. With a constant $\epsilon$ its regret grows linearly, at roughly $\epsilon$ times the average gap per step. Auer, Cesa-Bianchi and Fischer showed that decaying $\epsilon$ like $1/t$ gives logarithmic regret, but their schedule needs the smallest gap, which you do not know [4]. We also run the gentler schedule ${\epsilon }_t=\min (1,K/\sqrt{t})$, which needs no knowledge of the gaps.

Upper confidence bound (UCB)#

UCB replaces random exploration with optimism. For each arm it computes a plausible upper limit on the mean, given the data so far, and pulls the arm whose upper limit is highest. UCB1, from Auer and colleagues [4], first pulls each arm once and then chooses

The first term is the estimated mean and the second is an exploration bonus that shrinks as an arm is pulled more ($N_i$ grows) and slowly grows for arms that are neglected ($\ln t$ grows). The bonus comes from Hoeffding's inequality: for rewards in $[0,1]$, the true mean exceeds ${\hat{\mu }}_i+\sqrt{2\ln t/N_i}$ with probability at most $t^{-4}$. An arm is pulled either because it looks good or because we know little about it, and both reasons fade as evidence accumulates. Auer and colleagues proved the finite-time bound

which holds at every $T$, not just in the limit. It is logarithmic, as Lai and Robbins require, but with a loose constant: for our five arms it evaluates to about 2,950 at $T=10,000$, while UCB1's measured regret is 282.

A worked example#

After 100 steps on a two-arm problem, suppose arm A has been pulled 60 times with a mean of 0.55 and arm B 10 times with a mean of 0.40. With $\ln 100=4.61$, UCB1 scores arm A at $0.55+\sqrt{2\times 4.61/60}=0.55+0.39=0.94$ and arm B at $0.40+\sqrt{2\times 4.61/10}=0.40+0.96=1.36$. UCB1 pulls B. Its mean is lower, but ten pulls are too few to rule out that B is better. Both indices exceed 1, an impossible conversion rate: UCB1's bonus is deliberately conservative, which is why its constant is large.

Thompson sampling#

Thompson sampling is the oldest of the three, proposed in 1933 for allocating patients between two treatments [2], and it took almost eighty years for its regret to be analysed [5, 6]. It keeps a posterior distribution over each arm's mean, draws one sample from each posterior, and pulls the arm whose sample is highest. For 0/1 rewards with a uniform prior the posterior is a Beta distribution:

where $S_i$ and $F_i$ are the numbers of successes and failures observed on arm $i$. The effect is probability matching: each arm is pulled with exactly the posterior probability that it is the best arm. An arm that is probably bad is still tried occasionally, in proportion to how plausible it is that it is actually best, and never more than that.

In the worked example, arm A's posterior is $\mathrm{Beta}(34,28)$, with mean 0.548 and standard deviation 0.063, and arm B's is $\mathrm{Beta}(5,7)$, with mean 0.417 and standard deviation 0.137. By simulation, a draw from B beats a draw from A 19.6% of the time, so Thompson sampling sends about one in five of the next visitors to B, where UCB1 sent the next one to B with certainty.

Kaufmann, Korda and Munos proved that for Bernoulli rewards Thompson sampling matches the Lai-Robbins constant exactly [6]: it is asymptotically optimal, not just logarithmic. Chapelle and Li found it hard to beat on display advertising and news recommendation data [7].

How do the algorithms compare? A seeded simulation#

Setup (simulation). The five Bernoulli arms from the example, horizon $T=10,000$, 2,000 independent runs per algorithm, numpy seed 20261101. We report mean regret at $T$ with a 95% interval for the mean, the 99th percentile across runs (the bad-luck case), and the share of all pulls that went to the best arm.

Four things stand out. Greedy's median run loses about 500, but one run in ten loses 1,500 or more because it locked onto a worse arm early, and its 99th percentile, 2,999, is worse than the uniform split. UCB1 is the most predictable (smallest spread across runs), but its conservative bonus costs four times Thompson sampling's regret. Thompson sampling with nothing tuned matches a UCB whose constant was tuned on this very instance. And constant ε-greedy does well over this horizon, but its curve bends upwards as the linear exploration cost takes over.

The dashed Lai-Robbins line sits above Thompson sampling's curve. That is not a contradiction: the bound describes the limit, and lower-order terms dominate at moderate horizons when one gap is only 0.05. Rerun to 100,000 steps (400 runs), Thompson's regret reached 108 ± 4 and was growing at 15.3 per unit of $\ln t$, still below the 19.5 slope it must eventually reach; UCB1 reached 627 ± 7, growing at 152 per unit of $\ln t$, almost eight times the optimal rate.

As a cross-check, we ran the 10-armed Gaussian testbed of Sutton and Barto [11] (2,000 random problems, 1,000 steps). Over the last 100 steps, greedy chose the optimal arm 34.7% of the time and averaged a reward of 1.02; ε = 0.01 reached 59.0% and 1.31; ε = 0.1 reached 80.3% and 1.37; UCB with $c=2$ reached 86.0% and 1.49, against 1.55 for an oracle. These match the curves in the book's Figures 2.2 and 2.4.

UCB vs Thompson sampling#

Thompson sampling usually wins on regret, in the literature [7, 9] as in our table. UCB still has real advantages, and the deployment matters more than the regret curve.

The batching row matters: production systems update every few minutes, not after every impression. A deterministic rule then sends a whole batch to one arm, while Thompson sampling spreads it in proportion to the posterior [7, 9].

Multi-armed bandit vs A/B testing#

An A/B test fixes the allocation so that, at the end, you can estimate the difference between arms with a known error rate. A bandit changes the allocation to collect reward during the test. Most comparisons say the bandit sacrifices some certainty; we measured how much.

Setup (simulation). Two arms with conversion rates 10% and 12%, 20,000 visitors, 4,000 seeded replications. Three designs: a 50/50 split; Thompson sampling with Beta(1, 1) priors; and Thompson sampling with a floor that keeps each arm's share of traffic at or above 20%. At the end, each run applies the usual two-proportion z-test at the 5% level to whatever data the design collected, which is what an analyst who exports the logs would do. We also reran everything with both arms at 10%, to measure false positives.

The bandit does what it promises: it loses 29 conversions instead of 200, and it ends with the right arm ahead in 99.8% of runs. But the naive analysis of its data is compromised in three ways. Power falls from 99.6% to 79.7%, because the median run shows the worse arm to only 1,122 visitors. The estimates are biased: the losing arm's average measured rate is 9.29% rather than 10%, so the estimated lift is 2.7 points instead of the true 2.0. This is a general property of adaptively collected data: an arm that has an unlucky streak is sampled less and never gets the chance to recover, so sample means are biased downwards [12]. Most striking, when the two arms are identical, the naive z-test declares a winner 12.3% of the time instead of 5%.

The 20% floor recovers almost everything: power 95.7%, false positive rate 5.1%, no visible bias, at a cost of 81 lost conversions, still 60% fewer than the A/B test. Use a pure bandit when the goal is reward and nobody will report the effect size, an A/B test when the estimate is the product, and a floor (or an analysis built for adaptive data) when you need both. For more on getting intervals and sample sizes right, see our guides on statistical significance and how many samples an evaluation needs.

What is a contextual bandit?#

In a contextual bandit the learner sees a feature vector before each choice: who the user is, what the query was, which patient is being treated. The best arm can differ by context, so the learner estimates a model of reward given context and arm. LinUCB, introduced for news article recommendation [8], assumes the expected reward of arm $a$ is linear in the context, $\mathbb{E}[r\mid x,a]=x^{\top }{\theta }_a$, and picks

where ${\hat{\theta }}_a={\mathbf{A}}_a^{-1}{b}_a$ is the ridge regression estimate from past contexts $x_s$ and rewards (with $b_a$ the sum of $r_s{x}_s$ over pulls of arm $a$), and $\alpha$ sets the width of the confidence bonus. The bonus is large for contexts unlike anything this arm has seen, which is UCB's optimism lifted to a regression. Thompson sampling generalises the same way, by sampling ${\theta }_a$ from a Gaussian posterior [9]. Contextual bandits also produce logged data that can be reused to evaluate a new policy offline, which is the bridge to offline reinforcement learning.

Bandits in LLM training and evaluation#

Bandits show up around language models in two places, and it is worth being precise about both.

Training. A common formulation of fine-tuning from human feedback treats each prompt as a context, the whole response as a single action, and the reward model's score as the reward, with the episode ending after one response. The InstructGPT paper describes its RL environment in exactly these terms, as "a bandit environment" [13]. That makes response-level RLHF a contextual bandit with an enormous action space, optimised by policy gradient methods rather than by the index rules above. The wider picture is in our guide to reinforcement learning for LLMs.

Evaluation. Picking the best of several prompts, decoding settings or checkpoints on a limited budget looks like a bandit, and adaptive allocation can save calls. Two cautions carry over. Regret is the wrong objective: you want to identify the best option or estimate its score, a different problem called best-arm identification or pure exploration [10]. And scores from adaptively allocated samples are biased, with the losers looking worse than they are. If the result will be reported, freeze the allocation or correct for it, and compute intervals as you would for any evaluation. The same applies when evaluating RL agents.

Code: the three algorithms in numpy#

This is a complete, runnable implementation of the three algorithms as described above, on the five-arm example. With 50 seeds it prints mean regrets close to the table (for example, about 216, 273 and 76 for ε-greedy, UCB1 and Thompson sampling; ε-greedy's spread across runs is wide, so its 50-run mean moves more).

import numpy as np

def run_bandit(mu, T, policy, seed=0, eps=0.1, c=np.sqrt(2)):
    """One run on a Bernoulli bandit. Returns cumulative pseudo-regret."""
    rng = np.random.default_rng(seed)
    K = len(mu); n = np.zeros(K); s = np.zeros(K); regret = 0.0
    for t in range(1, T + 1):
        if policy == "eps-greedy":
            means = np.where(n > 0, s / np.maximum(n, 1), np.inf)   # untried arms first
            a = rng.integers(K) if rng.random() < eps else int(np.argmax(means))
        elif policy == "ucb":
            a = t - 1 if t <= K else int(np.argmax(s / n + c * np.sqrt(np.log(t) / n)))
        elif policy == "thompson":
            a = int(np.argmax(rng.beta(1 + s, 1 + n - s)))   # Beta(1,1) prior
        r = rng.random() < mu[a]
        n[a] += 1; s[a] += r
        regret += max(mu) - mu[a]
    return regret

mu = np.array([0.30, 0.45, 0.50, 0.55, 0.60])
for p in ["eps-greedy", "ucb", "thompson"]:
    regs = [run_bandit(mu, 10_000, p, seed=k) for k in range(50)]
    print(f"{p:11s} mean regret {np.mean(regs):6.1f}")

Choosing an algorithm#

Failure modes#

Non-stationarity. Every guarantee above assumes the arms' rates are fixed. Real conversion rates drift with seasons, campaigns and novelty effects. A stationary algorithm that has stopped exploring an arm will not notice when it improves. Discount old observations, use a sliding window, or keep an exploration floor.

Delayed rewards. If conversions arrive hours after the impression, the algorithm makes many choices on stale counts. Deterministic rules suffer most; include the delay in any simulation used to choose settings.

The wrong reward. A bandit optimises exactly the reward you give it. Optimise click-through and it will find the most clickable variant, whether or not that is the most useful one. This is the bandit-sized version of reward hacking.

Reading bandit logs as an experiment. As measured above, a z-test on adaptively collected data can double the false positive rate and inflate effect sizes.

Greedy by accident, or over-tuned. Turning exploration off "once things look stable" turns any algorithm into greedy, with greedy's heavy tail. At the other extreme, UCB with c = 0.5 won our table only on the instance it was tuned for; Thompson sampling came within 5 units with nothing tuned.

The next step up is to let actions change the state, which brings in Markov decision processes and the value functions built on them.

Frequently asked questions#

Sources#

1. H. Robbins. Some aspects of the sequential design of experiments, 1952. doi.org
2. W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, 1933. doi.org
3. T. L. Lai, H. Robbins. Asymptotically efficient adaptive allocation rules, 1985. doi.org
4. P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time Analysis of the Multiarmed Bandit Problem, 2002. doi.org
5. S. Agrawal, N. Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem, 2012. arxiv.org
6. E. Kaufmann, N. Korda, R. Munos. Thompson Sampling: An Asymptotically Optimal Finite Time Analysis, 2012. arxiv.org
7. O. Chapelle, L. Li. An Empirical Evaluation of Thompson Sampling, 2011. papers.nips.cc
8. L. Li, W. Chu, J. Langford, R. E. Schapire. A Contextual-Bandit Approach to Personalized News Article Recommendation, 2010. arxiv.org
9. D. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen. A Tutorial on Thompson Sampling, 2018. arxiv.org
10. T. Lattimore, C. Szepesvári. Bandit Algorithms, 2020. doi.org
11. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
12. X. Nie, X. Tian, J. Taylor, J. Zou. Why Adaptively Collected Data Have Negative Bias and How to Correct for It, 2018. arxiv.org
13. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, et al.. Training language models to follow instructions with human feedback, 2022. arxiv.org