Multi-Armed Bandit

The multi-armed bandit problem is a classic problem in reinforcement learning in which an agent repeatedly chooses between a fixed set of options — called "arms", in reference to the levers of a slot machine — each returning a reward drawn from an unknown probability distribution, and must decide how to allocate its choices to maximise total reward over time.^[1] It is the canonical formalisation of the exploration–exploitation trade-off: the agent must explore arms to learn their reward distributions while exploiting the arms that appear best, and the choices it makes affect only the rewards it collects, not the underlying distributions.^[1]

Background

The problem takes its name from the image of a gambler facing multiple "one-armed bandits" (slot machines). A 1933 paper by W. R. Thompson proposed a Bayesian strategy — later named Thompson sampling — that chooses each arm according to its probability of being the best, making it one of the earliest formal solutions to the problem.^[2] During the following decades the multi-armed bandit became a central object of study in statistics, operations research, and computer science, with contributions connecting it to stochastic scheduling and to the study of optimal decision making under uncertainty.^[1]

The problem is a simplified form of reinforcement learning. In a full reinforcement learning setting, actions change the state of the environment and therefore the distribution of future rewards; in a bandit problem, each action yields an independent reward and does not affect the state, which makes the problem tractable to analyse rigorously while still capturing the core tension between exploration and exploitation.^[1]

Key Concepts

A central measure of performance in multi-armed bandit research is regret, the difference between the cumulative reward collected by an algorithm and the reward that would have been collected by always playing the best arm. Fundamental lower bounds show that no algorithm can achieve regret smaller than a value proportional to the square root of the number of arms times the number of rounds, in the worst case.^[3] Algorithms such as UCB (upper confidence bound) and Thompson sampling achieve near-optimal regret, growing only logarithmically with the number of rounds.^[2][3]

Epsilon-greedy is the simplest family of strategies: with probability epsilon the agent chooses a random arm (exploration) and otherwise chooses the arm with the highest estimated reward (exploitation). Upper confidence bound (UCB) algorithms instead select the arm with the highest plausible upper bound on its reward, automatically exploring arms whose estimates are uncertain. Thompson sampling is a Bayesian method that samples from the posterior distribution of each arm's reward parameter and plays the arm that appears best in that sample, implementing a principle known as probability matching.^[3] For stationary problems Thompson sampling and UCB are regarded as near-optimal, while variants such as discounted UCB and sliding-window Thompson sampling have been developed for settings where reward distributions change over time.^[1]

Applications and Impact

Multi-armed bandit algorithms are widely used in industry wherever systems must choose between alternatives with unknown performance. They are commonly deployed as a more efficient alternative to classical A/B testing, dynamically shifting traffic toward better-performing variants instead of splitting traffic evenly, in applications such as website optimisation, online advertising, and recommendation systems.^[4] Bandit methods are also used in clinical trials to allocate patients between treatments while minimising overall harm, and they appear as components of larger reinforcement learning systems.^[3] Open-source libraries such as MABWiser and Vowpal Wabbit provide ready-made implementations of the main bandit strategies.^[4]

>See Also

• Reinforcement Learning
• Q-Learning
• Markov Decision Process
• A/B Testing in Machine Learning
• Bayesian Inference

References