A restaurant regular faces a small dilemma every visit: order the dish they know they enjoy, or try something new that might be better, or worse. A marketing team faces the same dilemma at larger scale: keep spending on the channel that has worked so far, or test new channels that might work better. So does a business choosing suppliers, a manager assigning work, or a founder deciding which product idea to pursue.
This is the tension between exploitation, using what you already know to get good results now, and exploration, trying alternatives to learn whether something better exists. Exploit too much and you may never discover a better option. Explore too much and you waste effort on options that are worse than what you already have.
Decision theorists formalise this dilemma as the multi-armed bandit problem, named after slot machines, sometimes called one-armed bandits. Algorithms for Decision Making by Mykel Kochenderfer, Tim Wheeler and Kyle Wray uses bandit problems to introduce exploration and exploitation, a central challenge in learning from experience. This article explains the problem, the main strategies for addressing it, and how to apply them to practical business decisions. It is part of GoCore’s series on decision making.
The bandit problem
Imagine a row of slot machines, each with a different, unknown probability of paying out. Each time you play, you choose one machine and observe whether it pays. Your goal is to win as much as possible over a fixed number of plays.
At first, you know nothing about the machines. As you play, you learn which ones seem to pay more often. The dilemma is how to balance:
- playing the machine that has looked best so far, to earn the most now, and
- trying other machines, which may be better but have been tried too little to tell.
Each machine is called an arm. The problem appears whenever there are several options with uncertain payoffs and the only way to learn about them is to try them.
Measuring performance: regret
A useful measure of a strategy is regret: the difference between what it earned and what would have been earned by always choosing the best option from the start. Regret captures the cost of not knowing which option is best. Good strategies keep regret low by learning quickly which options are best and then mostly using them.
Representing what you know
The book describes a Bayesian approach to tracking what has been learned about each arm. For options with yes-or-no outcomes, such as whether a customer clicked, bought or responded, each arm’s success rate can be represented by a beta distribution, which is updated simply by counting successes and failures. This approach is explained in Learning from small numbers.
The beta distribution captures both the estimated success rate and how uncertain that estimate is. An option tried 1,000 times has a narrow distribution; one tried five times has a wide one. Good exploration strategies use this uncertainty.
The greedy trap
The simplest strategy is greedy: always choose the option with the highest estimated success rate so far. It sounds sensible, but it can fail badly.
Suppose two options are tried once each. Option A succeeds by chance; option B fails by chance, even though B is actually better. A greedy strategy now chooses A every time and never tries B again, so it never learns that B is better. Early luck locks in a poor choice.
Every useful exploration strategy is, in one way or another, a way of avoiding this trap.
Undirected exploration strategies
Undirected strategies explore without specifically targeting the most uncertain options.
Epsilon-greedy
Most of the time, choose the best-looking option; but with a small probability, often written ε (epsilon), choose an option at random. With ε = 0.1, the strategy exploits 90% of the time and explores 10% of the time.
Epsilon-greedy is simple and robust. Its weaknesses are that it explores at the same rate forever, even after the best option is clear, and that when it explores, it is as likely to try an option known to be poor as one that might be good. A common refinement reduces ε over time.
Explore-then-commit
Try every option a fixed number of times, then commit to the best for the remainder. This is essentially how a traditional A/B test works: split traffic evenly for a set period, then choose the winner.
It is easy to understand and plan. Its weakness is that the exploration phase continues even when one option is clearly inferior, and the commitment is final even if early results were misleading.
Directed exploration strategies
Directed strategies explore deliberately, focusing on options where more information is most useful.
Softmax
Choose options with probabilities that increase with their estimated value. Better-looking options are chosen more often, but weaker ones still get occasional tries, more often if they are close to the best. A parameter controls how strongly choices favour the best-looking option.
Optimism in the face of uncertainty
Strategies such as upper confidence bound (UCB) methods choose the option with the highest optimistic estimate: its estimated value plus a bonus that is larger for options tried less often. An option that has been tried rarely might be better than it looks, so it gets the benefit of the doubt until it has been tried enough to know. As evidence accumulates, the bonus shrinks, and the strategy settles on the best option.
The book also describes a related quantile strategy, which chooses the option with the highest value at a chosen upper point of its uncertainty distribution.
Posterior sampling (Thompson sampling)
Posterior sampling, also known as Thompson sampling after William Thompson, who proposed it in 1933, works as follows: for each option, draw a random plausible success rate from its current distribution, then choose the option whose draw is highest.
Options that are clearly good are chosen most of the time, because their draws are consistently high. Options with high uncertainty are chosen occasionally, because their draws sometimes come out high. Options that are clearly poor are rarely chosen. The amount of exploration adjusts automatically to the evidence. Posterior sampling is simple to implement and performs very well in practice, which has made it popular in online experimentation and advertising.
Optimal exploration
For some bandit problems, the truly optimal strategy can be calculated using dynamic programming over the decision maker’s beliefs, treating the problem as a sequential decision in which beliefs are the state. The book explains how this works for small problems. For a classic version of the problem with discounted rewards, the economist John Gittins showed in the 1970s that the optimal strategy can be expressed through an index computed separately for each arm, a result known as the Gittins index.
Optimal strategies are computationally demanding for large problems, which is why practical strategies such as UCB and posterior sampling are widely used: they come close to optimal performance with far less computation.
Comparing strategies
| Strategy | How it explores | Strengths | Weaknesses |
|---|---|---|---|
| Greedy | Not at all | Simple | Can lock onto a poor option |
| Epsilon-greedy | Randomly, at a fixed rate | Simple, robust | Wastes effort on clearly poor options |
| Explore-then-commit | Evenly, then stops | Easy to plan; familiar A/B test | Inflexible; commitment can be wrong |
| Softmax | More often for near-best options | Smooth balance | Needs tuning |
| Upper confidence bound | Favours uncertain options | Strong theoretical guarantees | Can over-explore with many options |
| Posterior sampling | In proportion to chance of being best | Adapts automatically; strong in practice | Needs a probabilistic model |
A worked illustration
This is an illustration with round numbers.
A small online shop is testing three versions of an email offer. After a few days:
| Version | Sent | Purchases | Simple rate | Posterior (uniform prior) |
|---|---|---|---|---|
| A | 200 | 12 | 6.0% | about 6.4% |
| B | 40 | 3 | 7.5% | about 9.5% |
| C | 200 | 6 | 3.0% | about 3.5% |
A greedy approach would focus on B, based on only 40 sends. An even split, as in a traditional A/B test, would keep sending a third of emails to C, which looks clearly weaker.
Posterior sampling would send most emails to A and B, with B receiving a substantial share because it is promising but uncertain, and C receiving very few. As more data arrives, the strategy shifts towards whichever of A and B proves better, without the shop having to decide when to stop a test.
Applying bandit thinking in business
Marketing and pricing
Testing advertisements, email subject lines, landing pages and offers is a natural bandit problem. Bandit-style approaches allocate more traffic to better-performing versions as evidence accumulates, reducing the cost of testing compared with fixed even splits. Traditional A/B tests remain valuable when the goal is a clear, reliable conclusion rather than maximum results during the test.
Products and services
Businesses choosing which products to promote, which menu items to feature or which services to emphasise face the same trade-off. Keeping a small, deliberate share of effort for trying new options prevents a business from becoming stuck with its early choices.
Suppliers and partners
Using one proven supplier for most orders while occasionally placing small orders with alternatives keeps information about the market current and reduces dependence.
Strategy and new ventures
At a larger scale, the choice between focusing on a proven business and exploring new opportunities is a bandit problem too. GoCore’s article Why GoCore is starting broad describes a deliberate period of exploration before narrowing focus, which follows the same logic: explore more when little is known, then shift towards exploitation as evidence accumulates.
When conditions change
Real business environments change: customer preferences shift, competitors move, and seasons turn. In such non-stationary settings, an option that was best last year may not be best now. Continuing to explore a little, and giving more weight to recent results, keeps decisions current.
Different options for different situations
In many problems, the best option depends on the situation. The best offer for a returning customer may differ from the best offer for a new one; the best supplier for urgent orders may differ from the best for bulk orders. Extensions of the bandit problem, often called contextual bandits, choose options based on the characteristics of each situation, learning which option works best in which context. They are widely used in online recommendation and personalisation. The same exploration principles apply: options that are uncertain in a particular context deserve occasional trials there.
Practical guidelines
- Explore more early, less later. When little is known, the value of learning is high. As evidence accumulates, focus on what works.
- Explore where uncertainty is high and promise is real. Do not spend effort re-testing options that are clearly poor.
- Use small, cheap tests. Exploration should cost little relative to the potential gain.
- Keep a small exploration budget permanently. Conditions change; continued small-scale testing keeps knowledge fresh.
- Count the cost of not knowing. Sticking with a familiar option has a hidden cost if a better option exists.
Common mistakes
Locking onto early winners. Early results are noisy; give promising alternatives a fair chance.
Splitting evenly for too long. Continuing to test clearly inferior options wastes resources.
Never exploring again. Markets change, and yesterday’s best option may not be today’s.
Treating every test as a one-off. Exploration works best as a continuing process.
Ignoring the size of the opportunity. Exploration is worth more when the potential improvement is large and the time to benefit from it is long.
Questions to ask
- Which of our recurring choices involves options whose value we do not fully know?
- Are we exploiting a familiar option without checking whether something better exists?
- Are we spending too much effort on options that are clearly worse?
- How much of our effort is set aside for deliberate exploration?
- For your own business: what small, cheap test could reveal a better option this month?
Bringing it together
The multi-armed bandit problem captures one of the most common dilemmas in decision making: whether to exploit what is known to work or explore alternatives that might be better. Greedy strategies risk locking onto early luck. Undirected strategies such as epsilon-greedy and explore-then-commit explore in simple ways; directed strategies such as softmax, upper confidence bounds and posterior sampling focus exploration where uncertainty and promise are greatest.
For businesses, bandit thinking offers practical guidance: explore more when knowledge is thin, focus as evidence accumulates, keep a small permanent budget for trying new things, and allocate effort in proportion to both promise and uncertainty.
Source: Mykel J. Kochenderfer, Tim A. Wheeler and Kyle H. Wray, Algorithms for Decision Making (MIT Press, 2022). Explanations are GoCore’s own; figures in the worked illustration are not data. This article is general information, not professional advice.
