Exploration and Multi-Armed Bandits
The purest form of the explore–exploit dilemma: greedy, ε-greedy, UCB and Thompson sampling, regret, and where bandits run in the real world — from A/B tests to recommendations.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
5 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. Should you order your favourite dish again, or try something new on the menu? That everyday question is the exploration versus exploitation dilemma, and multi armed bandits are its purest mathematical form. In this deep dive we compare four strategies with real simulations.
The bandit problem. Imagine a row of slot machines, sometimes called one armed bandits. Each arm pays out with its own unknown probability. Every round you pull one arm and see whether it pays. Your goal is to win as much as possible. It is reinforcement learning with a single state: actions have no long term consequences.
The dilemma. The dilemma is sharp. Exploiting means pulling the arm that looks best so far, earning reward now, but perhaps based on too little evidence. Exploring means pulling an uncertain arm to learn about it, which costs reward if it turns out worse. Good strategies balance the two.
Our bandit. Our test bandit has five arms with true win rates of twenty five, fifty, eighty, thirty five and sixty percent. The agent does not know them. Arm three is the best, and arm five, at sixty percent, is a tempting runner up that can fool a careless strategy.
Estimating values. Every strategy keeps an estimate of each arm’s value, usually the average reward it has paid so far: total reward divided by the number of pulls. It can be updated incrementally, nudging the estimate towards each new reward, exactly the same pattern as the TD updates in the previous lecture.
Greedy. The greedy strategy always pulls the arm with the highest current estimate. Here it tries each arm once, gets lucky with arm five, and then sticks with it for almost three hundred pulls. It never gives arm three, the true best, a fair second chance. That lost opportunity is the price of never exploring.
Pause and think. Pause and think. The greedy agent pulled the best arm once and happened to get nothing. Why can it never recover? Its estimate for that arm is now zero, lower than the runner up, so it never pulls it again. Without new data, the wrong estimate can never be corrected.
ε-greedy. Epsilon greedy adds a little randomness. Ninety percent of the time it exploits the best estimate, and ten percent of the time it pulls a random arm. That occasional exploration is enough to discover arm three. After three hundred pulls it has chosen arm three two hundred and seventy five times.
Regret. How do we score a strategy? With regret: the reward you missed compared with always pulling the best arm. Constant exploration with a fixed epsilon has regret that keeps growing in proportion to time. The best strategies achieve regret that grows only logarithmically, which means they eventually almost stop wasting pulls.
Linear vs logarithmic regret. The shape of regret matters. A strategy that keeps exploring at a fixed rate wastes a constant fraction of pulls forever, so its regret grows in a straight line. The best strategies have logarithmic regret: they make fewer and fewer mistakes, so the curve flattens out over time.
Optimistic initial values. A simple trick is optimistic initial values. Start every estimate high, for example at one for win rates. Even a purely greedy agent then tries every arm, because untried arms look perfect. Our greedy agent used exactly this, which is why it sampled each arm once before locking in.
Optimism. A smarter principle is optimism in the face of uncertainty. Treat any arm you are unsure about as if it might be excellent. Rarely tried arms get a bonus, so they keep being tried until the uncertainty is resolved. Exploration then focuses on arms that could plausibly be the best, instead of being purely random.
UCB. UCB puts this into a formula. Each arm’s score is its estimated value plus an exploration bonus, the square root of two log t divided by the number of pulls. Rarely tried arms get a large bonus, and the bonus shrinks as evidence accumulates. Always pull the arm with the highest optimistic score.
Compute a bonus. Let us compute a bonus. At pull one hundred, an arm has been tried only four times. The bonus is the square root of two times the natural log of one hundred, about nine point two, divided by four. That is about one point five, larger than any possible win rate, so this arm will be tried again soon.
UCB in action. Here is UCB. Its exploration is systematic rather than random: every arm keeps getting occasional pulls while its bonus is large. On our bandit it still spends quite a few pulls on the weaker arms after three hundred rounds, because arms three and five are not so far apart. Over a longer horizon the bonus shrinks and UCB commits.
Thompson sampling. Thompson sampling, first proposed in 1933, takes a Bayesian view. It keeps a probability distribution over each arm’s win rate. Every round it samples one plausible value for each arm and pulls the arm whose sample is highest. Arms are explored in proportion to the probability that they are actually the best.
Beliefs sharpen. This is the kind of belief Thompson sampling maintains for each arm. A Beta distribution starts wide, and every success or failure sharpens it. An arm with a wide, uncertain belief sometimes produces a high sample and gets explored. An arm with a sharp, low belief is rarely chosen.
Thompson in action. Here is Thompson sampling on our bandit. Early on it spreads its pulls across all the arms. As the beliefs sharpen, arm three wins the sampling contest more and more often. It concentrates on the best arm smoothly, without any tuning parameter at all.
Head to head. Now the fair comparison: each strategy runs a hundred times for five hundred pulls, and we plot how often it chooses the best arm. By the end, Thompson sampling picks the best arm about ninety eight percent of the time, epsilon greedy about eighty nine, UCB about seventy five, and greedy about seventy four.
Pause and think. Pause and think. Why does epsilon greedy never reach one hundred percent best arm choices, even once it knows which arm is best? Because it keeps exploring at random ten percent of the time forever, so it plateaus around ninety percent. Decaying epsilon over time fixes this.
Decaying exploration. The simple fix for epsilon greedy is to decay epsilon over time: explore a lot at first, when little is known, and less later, once estimates are reliable. A schedule like c divided by t gives logarithmic regret in theory. Deep Q networks use the same idea, lowering epsilon from one to point one.
Changing worlds. Real payout rates often drift over time. Plain averages give ancient evidence as much weight as fresh evidence, so they adapt slowly. Using a constant step size instead produces a recency weighted average in which old rewards fade away, so the agent can track a changing world.
Strategy summary. Here is the summary. Greedy never really explores and can get stuck forever. Epsilon greedy explores blindly and needs decay. UCB adds a principled bonus, and Thompson sampling samples from its beliefs. Both UCB and Thompson achieve logarithmic regret, and Thompson is often strongest in practice.
Bandits vs A/B tests. Bandits are closely related to A B testing. A classic A B test splits traffic evenly for a fixed period, then decides. That gives clean statistics, but half the users see the worse version throughout. A bandit shifts traffic towards the better variant as evidence grows, losing less along the way.
When to use which. Which should you use? A fixed A B test gives clean, well understood statistics and is best when you want to learn a durable truth. A bandit is better when earning reward during the test matters, like short lived promotions, though its statistics are harder to analyse and it can be fooled by trends over time.
Contextual bandits. Real systems usually know something about each situation. A contextual bandit observes a context, such as who the user is or what time it is, and learns which arm works best for that context. News sites have used contextual bandits to decide which headline to show each reader.
Bandits in the wild. Bandits run in many places: recommendation and advertising systems, adaptive clinical trials that assign more patients to better treatments, hyperparameter search methods that give more compute to promising configurations, and the UCT rule inside Monte Carlo tree search, which AlphaGo used to decide which moves to explore.
Exploration in full RL. In full reinforcement learning, exploration is harder, because the agent must reach new states, not just try new actions. Ideas from bandits carry over: optimistic initial values, bonuses for rarely visited states, curiosity rewards for surprising observations, and noisy networks. Hard games like Montezuma’s Revenge need these.
Thompson sampling in code. Thompson sampling is only a few lines of code. Start each arm with a flat Beta belief. Each round, sample a plausible win rate for every arm, pull the arm with the highest sample, observe the reward, and update that arm’s wins or losses. The Beta distribution does the rest.
Pause and think. Pause and think. The best headline on a news site changes every few days. Which strategies are most at risk? Any strategy that stops exploring, including fully converged UCB or Thompson sampling. Changing, non stationary problems need continued exploration, such as forgetting old data or keeping a minimum epsilon.
Recap. To recap. Bandits isolate the explore exploit dilemma. Greedy can lock onto a mediocre arm forever. Epsilon greedy explores randomly and should decay. UCB adds an optimism bonus, Thompson sampling samples from its beliefs, and regret is how we score them. Contextual bandits personalise the choice.