Multi-armed bandit: Definition and Examples

A multi-armed bandit is a sequential decision problem in which a learner repeatedly picks one of $K$ options ("arms"), each with an unknown reward distribution, and sees only the reward of the arm it picked. It is reinforcement learning with a single state: there are no transitions, only the exploration-exploitation trade-off in its purest form.

Definition

At each round $t = 1, \dots, T$ , the learner picks an arm $A_{t}$ and receives a reward $R_{t}$ drawn from that arm's distribution with mean $μ_{A_{t}}$ . The goal is to maximise total reward, or equivalently to minimise regret:

R_{T} = T a max μ_{a} - E [t = 1 \sum T R_{t}] .

The name comes from a gambler facing a row of slot machines ("one-armed bandits") with different, unknown payout rates.

Variants

Stochastic bandits: each arm's rewards are independent draws from a fixed distribution.
Adversarial bandits: rewards may be chosen by an opponent; algorithms such as EXP3 randomise to stay safe.
Contextual bandits: before choosing, the learner sees a context (a user, a query) and learns a policy from contexts to arms. This is a one-step MDP.
Best-arm identification: the goal is to find the best arm with confidence, not to earn reward along the way.

Worked example

Two page variants convert at 5% and 4%, and 10,000 visitors arrive. A fixed 50/50 split sends 5,000 visitors to the worse variant, losing $5, 000 \times 0.01 = 50$ expected conversions. In 300 seeded simulations, a Beta-Bernoulli Thompson sampling allocator lost 18 on average, because it shifted traffic toward the better variant as evidence accumulated. The trade-off: the adaptive allocation gives less data on the losing arm, so effect-size estimates are less precise than in a balanced test.

Standard algorithms

Epsilon-greedy explores at random; UCB explores optimistically; Thompson sampling explores by posterior sampling. The last two achieve regret that grows only logarithmically in $T$ , which is the best possible rate.

Why it matters

Bandits are where exploration theory is cleanest, so most exploration ideas in full RL are first worked out here. They also appear directly in practice: adaptive clinical and product experiments, recommendation, ad allocation, and choosing which model, prompt or eval items to sample next when budgets are tight. Robbins framed the problem in 1952 as a question of sequential experimental design, and that framing still fits.

Sources

Herbert Robbins. Some aspects of the sequential design of experiments, 1952. doi.org
Tor Lattimore, Csaba Szepesvári. Bandit Algorithms, 2020. tor-lattimore.com