Menu
Concepts

Multi-armed bandits

3 min readintermediateUpdated 28 Sept 2026
1 · In one line

A multi-armed bandit applies an action, observes its reward, then continues the process with another action.

1 · What it is

A bandit round selects one action and observes its reward. In the bandit feedback model, only the realized reward of the chosen arm is observed. Repeating this process creates a tension between exploiting strong estimates and exploring uncertain alternatives.

An upper-confidence method adds an uncertainty bonus to each reward estimate. Untried or rarely tried actions receive a larger bonus. UCB1 achieves logarithmic regret without prior knowledge of the reward distributions. An epsilon-greedy method sometimes selects an action at random rather than greedily. Thompson sampling instead samples actions according to their posterior probability of being optimal.

The accumulated cost of learning is measured with regret. Contextual bandits add information about the situation before choosing, such as user and article features in news recommendation. The standard stationary formulation assumes reward distributions do not change with time.

2 · Why it exists

Sequential decisions must balance useful exploration with high-reward choices.

Partial feedbackIn the bandit feedback model, only the realized reward of the chosen arm is observed.
UncertaintyA greedy action can stop exploring alternatives that might be better.
Opportunity costRegret compares accumulated reward with repeatedly choosing an optimal action.
3 · How it works

Follow one round of an upper-confidence strategy.

One upper-confidence bandit roundThree actions have empirical mean rewards and uncertainty bonuses. Their sums form upper-confidence scores. The highest score selects action B, whose observed reward updates only B.
An optimistic score gives uncertain actions room to be tested while favoring strong observed rewards.
  1. 1 · scoreCombine each action's reward estimate with an uncertainty bonus.
  2. 2 · chooseSelect the action with the largest upper-confidence score.
  3. 3 · observeApply the selected action and observe its reward.
  4. 4 · updateUpdate that action's count and reward estimate.

The uncertainty bonus shrinks as an action is selected more often.

4 · Where it's used
WhoWhat they askWhat it works with
Recommender team“Which item should be shown while preferences are still uncertain?”Reward estimates and uncertainty
Experiment owner“Which variant should receive the next user?”Action histories and observed outcomes
Operations researcher“How much reward was lost while learning?”Cumulative regret
5 · What it solves, and what it doesn't
solves
  • UCB1 selects each action at least once because an untried action has an infinite bonus.
  • Thompson sampling selects actions according to posterior probability of being optimal.
  • Contextual bandits can use information about users and items when choosing an action.
doesn't solve
  • Standard Thompson sampling may explore poorly when informative actions are not themselves plausible winners.
  • Active exploration has a cost when a short time horizon matters.
  • A stationary bandit formulation does not by itself handle changing reward distributions.
6 · Go deeper
Reinforcement learningQ-learningRecommender systemsReward modelsProbability

Sources used

This explainer is written in original language. The links below support its factual claims.

  1. paperFinite-time Analysis of the Multiarmed Bandit Problem, Auer, Cesa-Bianchi and Fischer · read 28 Sept 2026
  2. paperA Tutorial on Thompson Sampling, Russo et al. · read 28 Sept 2026
  3. paperA contextual-bandit approach to personalized news article recommendation, Microsoft Research · read 28 Sept 2026
  4. paperOn Upper-Confidence Bound Policies for Non-Stationary Bandit Problems, Garivier and Moulines · read 28 Sept 2026
  5. paperRegret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Bubeck and Cesa-Bianchi · read 28 Sept 2026
Suggest a correction