A multi-armed bandit is a model for making repeated choices when the payoff of each option is uncertain and you only learn the outcome of the option you choose. The challenge is to balance exploration—trying options to learn about them—with exploitation—choosing the option that currently seems best.
What is a multi-armed bandit?
Imagine choosing among several online headlines, product recommendations, or routes. Each choice produces a reward, such as a click, purchase, or shorter trip, but the reward is uncertain. You can observe the result of the choice you made; you do not get to see what would have happened had you chosen the other options.
In a basic K-armed bandit problem, there are K available options, called arms. Each arm has an unknown reward distribution. On each round, the learner selects one arm and observes its reward. In the stationary stochastic version, each arm’s reward distribution stays the same over time, although individual rewards can vary.
The learner uses observed rewards to estimate how valuable each arm is, while trying to maximize the total reward collected over many rounds. This is a compact model of sequential decision-making under uncertainty: every choice affects both what you earn now and what you learn for later.
#1 Best Overall
How exploration and exploitation work
Exploitation: use what you know
Exploitation means selecting the arm with the highest estimated expected reward. If one option has consistently produced better results in the observations so far, choosing it may yield a strong immediate payoff.
Exploration: learn what you do not know
Exploration means selecting an arm to gather information, even when its current estimate is below the apparent leader. Its true expected reward may be higher than the limited observations suggest. Trying it can improve later decisions, but may give up reward in the current round.
The tension is unavoidable: choosing only the current favorite can leave a better option undiscovered, while exploring too often can waste opportunities to earn reward from a strong option. Bandit algorithms differ mainly in how they decide when uncertainty is worth investigating.
What cumulative regret measures
Cumulative regret compares the learner’s choices with a benchmark: the optimal arm, meaning the arm with the highest expected reward. For each round, regret is the difference between that arm’s expected reward and the expected reward of the arm actually selected; cumulative regret sums those gaps across rounds.
The Tool Desk
Outbyte PC Repair FREEClear out junk files and repair common Windows errorsFree Scan →Outbyte Driver Updater FREEFix the driver behind crashes, sound loss and screen glitchesFind Drivers →Sublinear cumulative regret means average regret per round decreases as the number of rounds grows. It does not mean every choice is optimal, nor that the learner never makes a poor choice. It means that, over time, the accumulated cost of not always choosing the best arm grows more slowly than the number of decisions.
Three common bandit algorithms
These methods offer different rules for choosing between estimated reward and uncertainty. Their performance depends on the problem’s assumptions and implementation, so there is no universally best choice.
| Method | How it explores | What to keep in mind |
|---|---|---|
| Epsilon-greedy | Usually chooses the arm with the highest current estimate; with probability ε, it chooses an arm at random. | Simple to understand and implement. If ε stays fixed, the algorithm continues exploring at that rate, which can keep adding exploration cost. |
| Upper confidence bound (UCB) | Chooses using an estimated value plus an uncertainty bonus, which can favor arms that look promising or have been sampled relatively little. | The bonus provides a direct way to account for uncertainty. Specific formulas and guarantees depend on the version and its assumptions. |
| Thompson sampling | Uses a Bayesian posterior over reward parameters, samples candidate parameters, and chooses an arm according to its probability of being best. | Its behavior depends on the model and prior used. Agrawal and Goyal’s 2012 analysis proves logarithmic expected regret for the stochastic bandit setting and assumptions studied in their paper, not for every variant or setting. |
For a gentle introduction, epsilon-greedy makes the explore-or-exploit choice explicit. UCB adds an uncertainty bonus to estimated value. Thompson sampling represents uncertainty probabilistically. Comparing them fairly requires matching the reward model, feedback conditions, objective, and implementation.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.Why the bandit setting matters
“Multi-armed bandit” does not describe one set of assumptions. In a stationary stochastic bandit, each arm’s rewards are drawn from an unknown but stable distribution. In an adversarial bandit, rewards may be chosen or vary in a way that does not follow that stationary stochastic model. In a contextual bandit, the learner also observes context—such as information about the current user or situation—before choosing an arm.
Do these 3 things before closing this tab:
1Clear out junk files and repair common Windows errors2Fix the driver behind crashes, sound loss and screen glitches3Repair Windows errors before they cause bigger problemsThese settings call for different methods and guarantees. Real deployments can add further complications, including delayed feedback or changing reward patterns. A method designed for stable reward distributions should not be assumed to retain its guarantees when the environment changes or when the learner has contextual information.
For a broad technical introduction to stochastic, adversarial, contextual, and related bandit problems, see Aleksandrs Slivkins’ Introduction to Multi-Armed Bandits (author manuscript, September 2019).
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
