What Is the Multi-Armed Bandit Problem?

The multi-armed bandit problem, also called the K-armed or N-armed bandit problem, is a sequential decision problem in which an agent repeatedly chooses one of several actions and observes only the reward of the action it took. The name comes from a gambler facing a row of slot machines, each paying out according to an unknown distribution, who must decide which arm to pull on every round. Because the reward of the unchosen arms stays hidden, the agent has to spend some rounds gathering information about arms it is unsure of and other rounds collecting reward from the arm it currently believes is best. That tension between exploration and exploitation is the defining feature of the problem.

The formulation dates to work by William Thompson in 1933 on allocating patients between two treatments, and was placed on rigorous footing by Herbert Robbins in 1952. It occupies a position between classical statistics and reinforcement learning: unlike a full Markov decision process there is no state that the agent's actions change, but unlike supervised learning the data the agent sees depends on the choices it makes.

Regret and Fundamental Limits

Performance is measured by regret, the difference between the reward an oracle would have obtained by always playing the best arm and the reward the algorithm actually obtained. A useful algorithm has regret growing sublinearly in the horizon, meaning the average per-round loss vanishes over time. Lai and Robbins established in 1985 that for a broad class of reward distributions no policy can do better than logarithmic regret asymptotically, with the constant governed by the Kullback-Leibler divergence between each suboptimal arm's distribution and the best one. This lower bound is the yardstick against which every subsequent algorithm is measured.

Index Policies and Bayesian Sampling

The simplest practical rule is epsilon-greedy: play the empirically best arm most of the time and pick uniformly at random with small probability. It works but leaves a fixed exploration cost unless the probability is annealed. Upper confidence bound methods do better by adding an optimism term to each arm's sample mean, sized so that it shrinks as the arm is played more often, and then acting greedily on that inflated estimate. The finite-time analysis of the multiarmed bandit problem by Auer, Cesa-Bianchi, and Fischer showed that the UCB1 policy attains logarithmic regret uniformly over time rather than only asymptotically, using nothing more than bounded rewards.

Thompson sampling takes a Bayesian route. It maintains a posterior over each arm's reward parameter, draws one sample from each posterior per round, and plays the arm with the highest draw, so an arm is chosen in proportion to its probability of being optimal. It performed well empirically for decades before theory caught up, and the analysis of Thompson sampling for the multi-armed bandit problem supplied the first logarithmic regret bound for the Bernoulli case, later sharpened to match the Lai-Robbins constant.

Variants and Extensions

Several extensions cover situations the basic model excludes. In the contextual bandit the agent observes a feature vector before choosing, and the reward depends on both context and arm, which is the setting behind most recommendation and advertising deployments. The adversarial bandit drops the assumption of stochastic rewards entirely and evaluates policies such as Exp3 against an arbitrary reward sequence. Non-stationary formulations let reward distributions drift, and analyses of exploration and exploitation with non-stationary rewards show that regret then scales with a variation budget rather than logarithmically. Best-arm identification changes the objective from cumulative reward to correctly identifying the top arm within a fixed budget or confidence level.

Applications

The multi-armed bandit problem has applications across several fields, including:

• Online advertising, content recommendation, and A/B testing
• Adaptive clinical trial design and treatment allocation
• Dynamic pricing and revenue management
• Network routing, channel selection, and cognitive radio spectrum access
• Hyperparameter search and automated experiment allocation
• Portfolio selection and resource allocation under uncertainty