Explore or exploit: bandits

You have moved to a new town with five places to get lunch. The first one you try is pretty good. Do you keep going there, or try the others? If you always return to the first, you might never find the great one around the corner. If you keep trying new places, you eat a lot of mediocre lunches.

That tension has a name, and it sits at the heart of every system that learns by trial and error.

Learning without an answer key

In the earlier tracks, every model learned from examples with known answers: this photo is a cat, the next word was “the”. That is supervised learningSupervised learningLearning from examples that come with the right answer attached, such as photos labeled "cat" or houses with their sale prices.Taught in The learning loopOpen in glossary.

Reinforcement learningReinforcement learningLearning to act by trial and error: an agent takes actions, receives rewards, and adjusts its behavior to collect more reward over time, with no answer key telling it the right action.Open in glossary works without an answer key. A learner, called an agentAgent (reinforcement learning)In reinforcement learning, the learner that observes its situation, chooses actions, and receives rewards. Not to be confused with a language model agent that uses tools.Open in glossary, takes actions and receives a rewardRewardA number an agent receives after acting that says how well things went. The agent's goal is to collect as much reward as possible over time.Open in glossary, a number that says how well things went. Nobody tells it which action would have been best. It has to find out by trying, and the only way to learn about an action is to take it.

The simplest version is the multi-armed banditMulti-armed banditA problem where you repeatedly choose among several options (like slot machines) with unknown payouts, aiming to win as much as possible. The situation never changes between choices.Open in glossary, named after slot machines (once called one-armed bandits). You face several machines. Each pays out with its own chance, which you cannot see. Every turn you pull one, and it pays 1 or 0. Your goal is to win as much as possible over many pulls.

The explore or exploit tradeoff

Every pull is a choice between two things:

• Exploit: pull the machine that has paid best so far, to collect reward now.
• Explore: pull a machine you know less about, to learn whether it is better.

Exploiting too early can lock you onto a mediocre machine forever. Exploring too much wastes pulls on machines you already know are bad. This is the explore or exploit tradeoffExplore or exploit tradeoffThe choice between taking the action that looks best so far (exploit) and trying something less known that might be better (explore). Too little exploring locks in mistakes; too much wastes reward.Open in glossary.

To compare strategies, count what they give up. After each pull, add the gap between the best machine’s payout chance and the chance of the machine you pulled. The total is called regretRegretThe total reward given up by not always choosing the best option: summed over every choice, the best option's expected payout minus the chosen option's.Open in glossary. Pulling the best machine adds nothing; pulling a machine that pays 0.2 when the best pays 0.8 adds 0.6. Lower regret is better, and a perfect strategy that somehow knew the best machine would have none.

Race three strategies

Below, three strategies play the same five machines. To make the race fair, they also share the same luck: the third pull of machine B pays the same for every strategy that makes it. They differ only in which machines they choose.

import numpy as np

# After 14 pulls: machine A paid 2 of its 4 pulls, machine B 7 of its 10.
pulls = np.array([4, 10])
wins = np.array([2, 7])
t = pulls.sum()

# Epsilon-greedy and UCB both track the share of pulls that paid.
means = wins / pulls

# UCB adds a bonus that is large for machines tried only a few times.
c = np.sqrt(2)  # UCB1
bonus = c * np.sqrt(np.log(t) / pulls)
ucb = means + bonus

# Thompson sampling keeps a belief per machine: Beta(1 + wins, 1 + losses).
a, b = 1 + wins, 1 + pulls - wins
belief_mean = a / (a + b)
belief_sd = np.sqrt(a * b / ((a + b) ** 2 * (a + b + 1)))

for name, m, bo, u, bm, bs in zip("AB", means, bonus, ucb, belief_mean, belief_sd):
    print(f"{name}: mean {m:.2f} + bonus {bo:.2f} = UCB score {u:.2f}"
          f" | belief {bm:.2f} +/- {bs:.2f}")
print("Greedy pulls", "AB"[np.argmax(means)], "next; UCB pulls", "AB"[np.argmax(ucb)])

# Thompson sampling draws one plausible chance per machine and pulls the higher.
rng = np.random.default_rng(0)
draws = rng.beta(a, b, size=(100_000, 2))
print(f"Thompson picks A in {np.mean(draws[:, 0] > draws[:, 1]):.0%} of draws")

A: mean 0.50 + bonus 1.15 = UCB score 1.65 | belief 0.50 +/- 0.19
B: mean 0.70 + bonus 0.73 = UCB score 1.43 | belief 0.67 +/- 0.13
Greedy pulls B next; UCB pulls A
Thompson picks A in 24% of draws

Three ways to explore

Greedy, and epsilon-greedy. The simplest strategy keeps the average payout of each machine and always pulls the best average. With epsilon at 0 you saw the problem: a machine that pays out on its first pulls looks great, the best machine may lose its first few pulls, and greed never looks back. Averaged over 200 runs on the Spread out machines, pure greed piles up about 219 regret in 1,000 pulls.

Epsilon-greedyEpsilon-greedyAn exploration rule: with a small probability epsilon take a random action, otherwise take the action that currently looks best.Open in glossary fixes this crudely: with a small probability epsilon it pulls a random machine, otherwise it is greedy. With epsilon 0.1 the average regret falls to about 49. But notice its line never flattens. One pull in ten stays random forever, long after the best machine is obvious, so regret keeps growing at a steady slope.

Optimism: upper confidence bounds. A smarter idea is to explore where it might pay. UCBUpper confidence boundAn exploration strategy that scores each option by its average reward plus a bonus that is large for rarely tried options, then picks the highest score: optimism about what is uncertain.Open in glossary ranks each machine by its average plus a bonus that is large when the machine has been tried only a few times. In effect it assumes each machine is as good as it could plausibly be, then pulls the most promising. A machine that is truly worse sees its bonus shrink with every pull until it stops being chosen, and a machine that is truly better proves itself.

In the code above, machine B has the better average (0.70 against 0.50), but A has been tried only 4 times, so its bonus is bigger and UCB pulls A. Greed would pull B.

Matching beliefs: Thompson sampling. Thompson samplingThompson samplingAn exploration strategy that keeps a probability distribution over each option's payout, draws one plausible value from each, and picks the option with the highest draw.Open in glossary, proposed by William Thompson in 1933 for deciding how many patients should get each of two treatments, keeps a belief about each machine’s payout chance: a probability distribution that is wide when the machine has few pulls and narrow when it has many. Each turn it draws one plausible chance from each belief and pulls the machine with the highest draw. A machine gets pulled about as often as it is likely to be the best. In the code, A wins the draw about 24% of the time.

What the race shows

Averaged over 200 runs of 1,000 pulls on the Spread out machines:

UCB1, the standard setting, explores more than these machines need. Its bonus is designed so that its guarantee holds for any machines with payouts between 0 and 1 (Auer, Cesa-Bianchi, and Fischer, 2002). With a smaller bonus it does better here, but the best c depends on the machines, and a bonus that is too small brings back the greedy failure.

The curves of UCB and Thompson sampling bend over: as they become sure, they explore less. Lai and Robbins (1985) proved that any strategy that does well on every set of machines must let its regret grow at least with the logarithm of the number of pulls, and UCB1 was shown to stay within that logarithmic rate. A fixed epsilon cannot: its regret grows in proportion to the number of pulls.

Bandits and the rest of reinforcement learning

A bandit has one situation that never changes: the same five machines, every turn. Most problems are not like that. A move in chess changes the board, and what you should do next depends on where you are. In the next lesson the agent’s actions change its situation, and rewards can arrive long after the actions that earned them.

The tradeoff you met here never goes away. Every agent in this track has to explore to learn, and every bit of exploring costs something.