Machine learning & feedback

Multi-armed bandits and Thompson sampling

Choosing between options while learning creates a fundamental tension: use what currently looks best, or try something new? Bandit algorithms address it systematically, with Thompson sampling offering an especially elegant approach.

  • 9 min read
  • Updated on
  • smartlytics editorial team

At a glance

  1. A bandit algorithm reallocates trials while learning: promising options get more traffic, weak ones less. Regret measures the cost of learning.
  2. Thompson sampling chooses each option with the probability that it is currently the best, implemented with a single random draw from each posterior.
  3. Bandits optimise returns during an experiment; classical A/B tests optimise the quality of the conclusion. The right method depends on the goal.

Imagine a row of slot machines, sometimes called one-armed bandits. Each pays out with a different, unknown probability. You have a limited number of plays. Which machine do you choose: the best one so far, or another about which you know little? This picture gives the multi-armed bandit its name. Behind the metaphor lies a fundamental question for every learning system: the balance between exploration and exploitation.

The problem appears constantly in products and processes: which of five headlines, offers or recommendation orders should be shown? Each choice produces an observation, and each observation improves the knowledge available for the next choice.

The problem in a formula

There are KK arms. Each pull of arm ii produces a random reward with unknown mean μi\mu_i; in the simplest case, the reward is 1 for a click or purchase and 0 otherwise. In each round t=1,…,Tt = 1, \dots, T, an algorithm chooses an arm and sees only its outcome. The goal is to maximise the total reward.

Performance is measured by regret: the gap to an oracle that knows the best arm, with mean μ∗=max⁡iμi\mu^* = \max_i \mu_i, from the outset.

RT=Tμ∗−E[∑t=1Trt]=∑i=1KΔi E[Ni(T)],Δi=μ∗−μiR_T = T\mu^* - \E\Big[\sum_{t=1}^{T} r_t\Big] = \sum_{i=1}^{K} \Delta_i\, \E[N_i(T)], \qquad \Delta_i = \mu^* - \mu_i

Here Ni(T)N_i(T) is the number of pulls of arm ii up to round TT. The right side makes the issue clear: every pull of an inferior arm costs its gap Δi\Delta_i to the best. An algorithm with low regret rarely plays bad arms, but not so rarely that it overlooks an underestimated good one.

A fixed uniform allocation, as in a classical A/B test, gives each arm T/KT/K pulls. Its regret therefore grows linearly with TT: learning costs continue for as long as the experiment runs.

How good can it get?

In 1985, Tze Leung Lai and Herbert Robbins showed a logarithmic lower bound on the learning cost for suitably consistent algorithms (Lai & Robbins 1985). For each inferior arm ii, asymptotically,

lim inf⁡T→∞E[Ni(T)]ln⁡T≥1KL(μi,μ∗)\liminf_{T \to \infty} \frac{\E[N_i(T)]}{\ln T} \ge \frac{1}{\mathrm{KL}(\mu_i, \mu^*)}

where the Kullback–Leibler divergence for yes/no rewards is KL(p,q)=pln⁡pq+(1−p)ln⁡1−p1−q\mathrm{KL}(p, q) = p \ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}. The bound has two implications: regret grows at least as ln⁡T\ln T, and arms very similar to the best need more pulls to rule out. If the best arm has a 15% rate, KL(0,12; 0,15)≈0,0037\mathrm{KL}(0{,}12;\,0{,}15) \approx 0{,}0037, while KL(0,10; 0,15)≈0,011\mathrm{KL}(0{,}10;\,0{,}15) \approx 0{,}011. According to the bound, a 12% arm needs roughly three times as many pulls as a 10% arm.

Three strategies

ε-greedy: usually the best, sometimes random

The simplest strategy plays the arm with the highest observed rate with probability 1−ε1 - \varepsilon and a random arm with probability ε\varepsilon (Sutton & Barto 2018). Epsilon-greedy is easy to understand and implement but has two weaknesses. With fixed ε\varepsilon, it explores at the same rate forever, so regret grows linearly. Its exploration is also blind: a clearly poor arm is tried as often as a promising but poorly understood one.

UCB1: optimism under uncertainty

UCB methods, or Upper Confidence Bound methods, treat each arm as being as good as the data still plausibly allows. In every round, UCB1 selects the arm with the largest index

μ^i+2ln⁡tni\hat\mu_i + \sqrt{\frac{2 \ln t}{n_i}}

combining the observed rate μ^i\hat\mu_i with a bonus that shrinks as the number of previous pulls nin_i grows. Rarely played arms receive a large bonus and are therefore investigated. Auer, Cesa-Bianchi and Fischer showed a logarithmic finite-time regret bound for UCB1 when rewards lie in [0,1][0, 1] (Auer et al. 2002). UCB1 is deterministic: given the same data and tie-breaking rule, it makes the same choice.

Thompson sampling: choose according to the probability of being best

William R. Thompson proposed the idea in 1933 while considering which of two treatments was better (Thompson 1933). It is strikingly simple: choose each arm with precisely the probability that it is the best given current knowledge. There is no need to calculate that probability explicitly: one random draw from each posterior suffices.

For yes/no rewards, each arm uses a beta distribution, just as in Bayesian A/B testing:

For every arm i:  α_i = 1,  β_i = 1            (flat prior)
For every round t = 1, …, T:
  1. For each arm i, draw θ_i from Beta(α_i, β_i)
  2. Play the arm a with the largest θ_a
  3. Observe reward r ∈ {0, 1}
  4. α_a ← α_a + r,   β_a ← β_a + (1 − r)

Thompson sampling received little attention for decades. In the early 2010s, empirical comparisons showed that it matched or beat established methods in practical tasks such as ad and news selection and handled delayed feedback robustly (Chapelle & Li 2011). The first finite-time regret guarantees soon followed (Agrawal & Goyal 2012). For yes/no rewards, Thompson sampling even reaches the Lai–Robbins bound asymptotically (Kaufmann et al. 2012). Russo and colleagues provide an accessible survey of the theory and variants (Russo et al. 2018).

Thompson sampling beyond yes/no rewards

Not every reward is a click. For revenue or processing time, replace the beta distribution with a suitable model, such as a normal distribution for each arm’s mean. The principle remains: sample from every posterior, choose the arm with the best draw and update its posterior (Russo et al. 2018). For skewed quantities such as revenue per visitor, check the model instead of blindly assuming normality: a few large orders can substantially shift an arm’s estimated mean.

The prior also deserves attention. The flat Beta(1, 1) prior is a neutral starting point. If experience suggests click rates usually lie between 1% and 5%, a weakly informative prior such as Beta(1, 30), with a mean near 3% and a 95% interval from below 0.1% to just under 12%, can speed early learning without dominating later data. As in A/B testing, all arms should receive the same prior so that none starts with an advantage.

A step you can calculate yourself

After 90 rounds, three arms have the following record, all starting with a flat Beta(1, 1) prior. How do the three strategies choose round 91?

Arm Pulls Successes Observed rate Posterior P(best arm) = Thompson selection UCB1 index ε-greedy selection (ε = 0.1)
A 50 6 12.0% Beta(7, 45) 15% 0.544 3.3%
B 30 5 16.7% Beta(6, 26) 50% 0.714 93.3%
C 10 1 10.0% Beta(2, 10) 35% 1.049 3.3%

The Thompson-column probabilities are P(Arm i is best∣data)=∫fi(x)∏j≠iFj(x)  dxP(\text{Arm } i \text{ is best} \mid \text{data}) = \int f_i(x) \prod_{j \ne i} F_j(x)\,\d x: the probability that arm ii is best, given the data. They were calculated by numerical integration and confirmed with 400,000 simulated rounds. The strategies have visibly different characteristics:

  • ε-greedy puts almost everything on B because B has the highest observed rate, distributing the remainder uniformly.
  • UCB1 selects C despite its lowest observed rate: after just ten pulls, its uncertainty bonus makes it the most optimistic candidate.
  • Thompson sampling gives B half the probability but still gives C just over a third. C’s posterior is broad: it has roughly a 20% chance of a rate above 25%, versus just under 2% for A. Exploration goes where learning may be valuable.
Interactive

Bandit simulation: Thompson sampling, ε-greedy and UCB compared

The simulation requires JavaScript. It compares Thompson sampling, ε-greedy and UCB1 on the same three arms and displays cumulative regret over time.

Bandit or A/B test?

Both methods compare variants, but their goals differ. A fixed-allocation A/B test optimises the quality of the conclusion: a precise, well-documented estimate of the effect at the end. A bandit optimises returns during the run, accepting less precise estimates for weaker variants to avoid losing traffic to them.

A/B test (fixed allocation) Bandit (adaptive allocation)
Goal Estimate and substantiate the effect cleanly Maximise returns while learning
Regret during the run Grows linearly with duration Grows logarithmically for good methods
Statistical analysis Straightforward, with established methods Harder because allocation depends on the data
Well suited to Lasting product decisions, several metrics and guardrails Many short-lived variants, continuous optimisation, costly weak variants

Contextual bandits

The best option often depends on the situation: a headline works differently in the morning and evening, or on a phone and a desktop. Contextual bandits observe context before each choice, such as device, time of day or interests, and learn which arm works best in each context. A well-known example is LinUCB, used by Li and colleagues to personalise news-article selection (Li et al. 2010). Thompson sampling also extends to these models, for example through Bayesian regression for each arm (Russo et al. 2018).

Contextual bandits are a step towards reinforcement learning. In a bandit problem, the choice changes only the current reward. In reinforcement learning, it also changes the state of the world and thus future possibilities. Lattimore and Szepesvári provide the comprehensive textbook on bandit theory (Lattimore & Szepesvári 2020).

Practical considerations

  • Delayed feedback: purchases often arrive hours after a click. With batch updates, Thompson sampling’s randomness makes it more robust than deterministic methods that repeatedly play the same arm until the next update (Chapelle & Li 2011).
  • Changing environments: rates vary with seasons, weather or campaigns. A bandit that never forgets old data reacts too slowly. Sliding windows or discounting older observations can help.
  • Analysis after adaptive allocation: because good arms receive more data, naive effect estimates can be biased and classical confidence intervals no longer automatically apply. Plan an unbiased comparison group if a reliable effect estimate is needed at the end.
  • The right reward: a bandit optimises exactly the reward it is given. Clicks are easy to measure but reveal little about long-term value. A poorly chosen reward will be maximised reliably, including its side effects.
  • Guardrails: minimum shares per arm, exploration limits and human approval for new arms prevent an algorithm from exposing customers to unchecked variants.

Conclusion

Multi-armed bandits make the trade-off between learning and exploiting knowledge quantifiable. Regret measures learning’s cost, and the Lai–Robbins bound describes the best achievable asymptotic rate. ε-greedy is simple but loses returns through blind exploration. UCB1 explores selectively with an optimism bonus. Thompson sampling chooses each option with its probability of being best, an idea from 1933 that remains both powerful and simple. The appropriate strategy depends on whether the priority is making good choices while learning or establishing an effect as reliably as possible.

Frequently asked questions

What is a multi-armed bandit?

A decision problem in which you repeatedly choose one of several options, or arms, with unknown success rates and observe a reward after each choice. The aim is to collect as much reward as possible across all rounds, requiring learning and exploitation at the same time.

How does Thompson sampling work?

Maintain a posterior distribution for each arm’s success rate, using a beta distribution for yes/no rewards. In each round, draw one random value from each posterior and play the arm with the largest draw. Then update the chosen arm’s posterior using the outcome.

When is a bandit better than an A/B test?

When the priority is to lose as little return as possible during the experiment: many short-lived variants such as headlines or offers, costly weak variants, or continuous optimisation. If an effect needs to be estimated and documented cleanly, a fixed-allocation A/B test is usually preferable.

What does regret mean?

Regret is the difference between the reward obtainable if the best option had been known from the start and the expected reward actually obtained. It measures the cost of learning. Good bandit algorithms make regret grow only logarithmically with the number of rounds.

Sources and further reading

  1. PaperThompson, W. R. (1933): On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika 25(3/4), 285–294.
  2. PaperLai, T. L. and Robbins, H. (1985): Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 4–22.
  3. PaperAuer, P., Cesa-Bianchi, N. and Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.
  4. PaperChapelle, O. and Li, L. (2011): An Empirical Evaluation of Thompson Sampling. Advances in Neural Information Processing Systems 24 (NIPS 2011).
  5. PaperAgrawal, S. and Goyal, N. (2012): Analysis of Thompson Sampling for the Multi-armed Bandit Problem. Proceedings of the 25th Annual Conference on Learning Theory (COLT).
  6. PaperKaufmann, E., Korda, N. and Munos, R. (2012): Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis. Algorithmic Learning Theory (ALT 2012), Springer.
  7. PaperRusso, D. J., Van Roy, B., Kazerouni, A., Osband, I. and Wen, Z. (2018): A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning 11(1), 1–96.An accessible introduction with many examples and guidance on the theory.
  8. PaperLi, L., Chu, W., Langford, J. and Schapire, R. E. (2010): A Contextual-Bandit Approach to Personalized News Article Recommendation. Proceedings of the 19th International Conference on World Wide Web (WWW).
  9. BookLattimore, T. and Szepesvári, C. (2020): Bandit Algorithms. Cambridge University Press.The comprehensive theoretical textbook; the authors provide a freely readable edition online.
  10. BookSutton, R. S. and Barto, A. G. (2018): Reinforcement Learning: An Introduction (2nd edition). MIT Press.Chapter 2 covers bandits as the simplest case of reinforcement learning.

Content last reviewed on 25 September 2026. Please let us know about any errors: impressum@nyxai.com.

From NyxAI

smartlytics is the learning hub of NyxAI GmbH.

Explore the methods we work with, explained openly, with sources and calculations you can reproduce.

Decision Core

NyxAI is developing a Decision Core for Decision Intelligence that combines optimisation, simulation, statistics and reinforcement learning: compare options, make uncertainty visible and learn from outcomes, with people in control.

DeepSquare

Explainable chess AI with human playing styles: NyxAI’s testing ground for understandable decisions under time pressure.