Multi-armed bandit

A multi-armed bandit models repeated choices under uncertainty when each action reveals information only after it is selected. The name comes from a row of slot machines, or “one-armed bandits,” whose unknown payout rates must be learned through play. In the basic stochastic formulation, each of K arms produces rewards from a fixed but unknown distribution, and the objective is to maximize cumulative reward over T rounds. The central trade-off is exploration—trying uncertain arms—and exploitation—choosing the arm currently believed to be best.¹

Performance is commonly measured by regret: the difference between the reward obtained and the reward that would have resulted from always selecting the best arm in hindsight. Expected regret, rather than prediction accuracy alone, captures the economic cost of experimentation.¹

Bandit algorithms differ mainly in how they value uncertainty. Epsilon-greedy selects the empirically best arm most of the time and explores randomly with probability epsilon. Upper-confidence-bound methods add an uncertainty bonus to each estimated mean, favoring arms whose potential value remains high; under standard stochastic assumptions, such methods achieve logarithmic regret in the number of rounds. Thompson sampling instead draws plausible reward parameters from a posterior distribution and chooses the arm favored by that sample, linking Bayesian inference to exploration.³⁵

The classical Lai–Robbins result established asymptotic lower bounds showing that sufficiently efficient policies must sample inferior arms in proportion to the information needed to distinguish them from the optimum.²

Real systems often require a richer model than independent, stationary arms. In a contextual bandit, the agent observes features about the current user, patient, document, or environment before choosing an action; rewards then depend on both the action and that context. This setting sits between supervised learning and full reinforcement learning: feedback is received for the chosen action, but the system usually does not model long-term state transitions.⁴

Other variants address delayed or censored rewards, nonstationary environments, adversarially chosen outcomes, and structured actions such as combinations of products. Applications include online recommendation, advertising, clinical experimentation, routing, resource allocation, and adaptive scientific testing. Practical deployments must also account for safety constraints, fairness, interference between users, and the possibility that experimentation changes the data-generating process.

Bandit theory is not limited to choosing among physical machines; its distinctive feature is partial feedback, because the outcomes of unchosen actions remain unknown. This makes it relevant to settings where randomization is valuable but costly, including adaptive clinical trials and sequential pricing. Thompson sampling predates modern machine learning: William R. Thompson introduced the Bayesian method in 1933, decades before the term became widely used in computing.³

There is also a sharp distinction between regret against the best fixed arm and regret against a changing or adaptive benchmark. A policy can perform well under stationary assumptions yet fail when preferences drift, rewards are delayed, or actions affect one another. Contextual bandit experiments on news recommendation helped demonstrate how online learning can personalize decisions while observing feedback only for displayed items.⁴

Arm

One available action or option in a bandit problem.

Regret

The cumulative loss relative to a specified benchmark, often the best fixed arm.

Exploration

Selecting uncertain actions to gather information about their rewards.

Exploitation

Selecting the action currently estimated to produce the greatest reward.

Contextual bandit

A bandit problem in which observed features influence the value of each available action.