Multi-armed bandits: explore or exploit?

Imagine walking into a casino with five slot machines — the “one-armed bandits” that give this problem its name. Each machine pays out with its own hidden probability. You have a limited number of pulls. How do you walk out with the most money?

This is the multi-armed bandit problem: reinforcement learning with a single state. There is no position to move through, no long-term consequences of your choice — just repeated decisions between actions with unknown value. It is simple enough to solve well, and it contains the dilemma at the heart of all reinforcement learning.

Play the machines

Pull the levers yourself. Each bar shows your current estimate of that machine’s win rate — simply the fraction of its pulls that paid out.

The estimate for action $a$ after it has been tried $n$ times is its average reward:

Notice how you played. At first you probably tried everything. Then, as one machine looked good, you pulled it more — but every pull on it was a pull not spent learning about the others.

The dilemma

Every decision is a choice between two goals:

• Exploit: pull the machine that currently looks best, collecting reward now.
• Explore: pull another machine, to improve your estimates and perhaps discover something better.

Exploit too early and you may lock onto a mediocre machine forever. Explore too much and you waste pulls on machines you already know are bad.

Smarter exploration

ε-greedy explores blindly: it is just as likely to re-test a machine it knows is terrible as one it knows little about. Two better ideas:

ε-greedy

Exploit the best estimate most of the time; with probability ε choose a random action. Simple and surprisingly effective, but it never stops wasting a fraction ε of its pulls.

Upper confidence bound (UCB)

Add an uncertainty bonus to each estimate — large for rarely tried actions, shrinking as evidence accumulates — and pick the highest total. “Optimism in the face of uncertainty.”

Thompson sampling

Keep a probability distribution over each action’s true value, draw one plausible value for each, and pick the highest. Actions are explored in proportion to the chance that they are the best.

Regret

The reward lost compared with always choosing the best action. Good bandit algorithms keep total regret growing only slowly over time.

The race below runs each strategy on 150 different casinos of 10 machines and averages the results.

Try changing ε. A larger ε finds the best machine sooner but keeps exploring forever, capping its performance; a tiny ε is efficient once it knows the answer but slow to learn it.

Bandits at work

Bandit algorithms are among the most widely deployed forms of reinforcement learning, because many business decisions look exactly like this:

• Website and email testing: which headline, layout or subject line to show. A bandit shifts traffic to the winner during the test, losing less revenue than a fixed 50/50 A/B test.
• Recommendations and ads: which item to show a user, balancing proven favourites against new items that need a chance.
• Clinical trials and pricing: allocating patients or price points adaptively as evidence comes in.

A bandit has just one situation. Real problems have many — the robot’s position, a game board, a customer’s journey — and today’s action changes tomorrow’s situation. The next lecture introduces the framework that handles this: the Markov decision process.