What is Multi-Armed Bandit?
A Multi-Armed Bandit is a sequential decision problem in which a learner repeatedly chooses one action from a set, observes only the chosen action's reward, and tries to maximize cumulative reward despite uncertainty.
Quick Facts
| Specification | Official Specification |
|---|
How It Works
Define the feedback and objective before the algorithm
At round t, a policy selects arm A_t and observes its reward, not the counterfactual rewards of unchosen arms. Regret compares the collected reward with an explicit oracle, commonly the best fixed arm in hindsight or the best expected arm in a stochastic model. Bubeck and Cesa-Bianchi's survey separates stochastic and adversarial assumptions and shows why their guarantees are not interchangeable.
Match exploration to the environment
Epsilon-greedy explores without using uncertainty, Upper Confidence Bound methods act optimistically, Thompson Sampling randomizes through a posterior, and EXP3 targets adversarial rewards. Contextual, combinatorial, sleeping, nonstationary, and constrained bandits change what an arm or comparator means. A logarithmic stochastic-bandit bound does not survive arbitrary drift, delayed attribution, interference, or reward-model misspecification.
Treat serving and evaluation as one system
Log context, eligible actions, chosen action, selection probability, policy version, assignment time, reward definition, attribution window, missing outcomes, and safety overrides. Compare cumulative reward and regret with fixed-allocation and nonadaptive baselines, then inspect unsafe-action rate, subgroup exposure, latency, and recovery after drift. Auer, Cesa-Bianchi, and Fischer prove finite-time results for bounded stochastic rewards; those assumptions must be checked before using UCB1 as a production claim.
Key Characteristics
- Reveals reward only for the action selected on each round
- Balances immediate exploitation against information-gathering exploration
- Optimizes a sequential objective such as cumulative reward or regret
- Includes stochastic, adversarial, contextual, and constrained variants
- Requires explicit assumptions about stationarity, delay, and reward support
- Creates adaptive logs that need propensity-aware evaluation
Common Use Cases
- Allocating traffic among product or message variants
- Choosing recommendations while learning from partial feedback
- Routing requests among models with different quality and cost
- Prioritizing experiments when only tested options reveal outcomes
- Adapting resource allocation under explicit safety constraints
Example
Loading code...Frequently Asked Questions
What is the exploration-exploitation trade-off in a bandit?
Exploitation chooses the action currently estimated to be best, while exploration chooses uncertain actions to improve future decisions. Pure exploitation can lock onto an early mistake; indiscriminate exploration can waste reward. A bandit policy controls this trade-off against a stated horizon and feedback model.
How is a Multi-Armed Bandit different from A/B testing?
A conventional fixed-allocation A/B test prioritizes unbiased estimation under a prespecified design. A bandit adapts allocation as outcomes arrive to improve cumulative reward. Adaptive exposure changes the data distribution, so conventional fixed-sample confidence intervals and naive winner comparisons may be invalid.
How is a bandit different from reinforcement learning?
In the basic bandit, an action yields an immediate reward and does not change a persistent environment state. General reinforcement learning models transitions, delayed consequences, and multi-step credit assignment. Contextual bandits add side information but still omit action-dependent state transitions.
Which Multi-Armed Bandit algorithm should I use?
Choose from the assumptions, not a universal ranking. UCB fits bounded stationary rewards with valid confidence construction, Thompson Sampling requires a credible posterior, and adversarial methods such as EXP3 avoid stochastic assumptions at a different cost. Simulate delay, drift, constraints, and traffic before deployment.
When should a Multi-Armed Bandit not be used?
Avoid it when exploration can cause unacceptable harm, rewards are too delayed or ambiguous to attribute, actions change future states materially, legal requirements demand a fixed experimental design, or traffic cannot support overlap. Use a controlled experiment, causal design, or full reinforcement-learning model when those contracts fit better.