Standard 3 stops to get here

Multi-Armed Bandit

The simplest decision problem with a trade-off between exploring and exploiting: repeatedly pick one of several options with unknown payouts to maximize total reward.

Your route here

3 stops · basics first
  1. Machine Learning ✓ understood

    Building systems that learn patterns from data instead of following hand-written rules, getting better at a task as they see more examples.

  2. Reinforcement Learning ✓ understood

    Learning through interaction with an environment, receiving rewards or penalties to learn optimal behavior policies.

  3. Reward ✓ understood

    The single number an environment sends back after each action, telling a reinforcement learning agent how good that step was; the agent learns to maximize its long-run total.

  4. Multi-Armed Bandit · you are here ✓ understood

Picture it

ε-greedy

  • Usually pull the best arm so far
  • With small probability ε, pick at random

Upper confidence bound

  • Score = average payout + uncertainty bonus
  • Rarely tried arms get a bigger bonus

Thompson sampling

  • Keep a belief about each arm's payout
  • Sample from beliefs, pull the winner
Notice that all three spend some pulls on arms that look worse right now; they differ in how they decide when that exploration is worth it.

A multi-armed bandit is a row of slot machines with different, unknown payout rates. Each turn you pull one arm and see its reward. Your goal is to earn as much as possible over many pulls. The name comes from the slot machine’s old nickname, the “one-armed bandit”.

The difficulty is the exploration–exploitation trade-off in its purest form. Pull the arm that has paid best so far and you might be ignoring a better one you under-sampled. Keep sampling others and you give up reward you could have had. Unlike full reinforcement learning, there are no states to move between: every action leads back to the same choice, so the whole problem is about learning which action is best while acting.

Measuring success: regret

Bandit algorithms are judged by regret: how much total reward you lost compared with always pulling the best arm, had you known it from the start. Good algorithms keep regret growing slowly as the number of pulls increases, which means they settle on the best arm without wasting too many pulls on bad ones.

Common strategies

  • ε-greedy: exploit the best-looking arm most of the time, explore at random with a small probability.
  • Upper confidence bound (UCB): be optimistic about arms you know little about by adding an uncertainty bonus to each arm’s average.
  • Thompson sampling: keep a probability distribution over each arm’s payout, sample from it, and pull the arm that looks best in the sample.

Where it shows up

Bandits are a natural fit for online experiments. Compared with a fixed-split A/B test, a bandit shifts traffic toward the winning variant while the test is still running. The same framing is used for ad and content selection in recommender systems, where each item shown is an arm and each click is a reward.

Where it sits

Before this

Reinforcement Learning Reward
Multi-Armed Bandit

Leads to

Nothing yet: a destination in its own right.

Explore nearby

Agents & RL Exploration vs Exploitation The RL dilemma of trying new actions (exploration) versus using known good actions (exploitation) to maximize reward. Evaluation A/B Testing Comparing two model versions in production by routing traffic to each and measuring performance differences. Foundations Recommender System AI systems that suggest items (products, content) to users based on preferences, behavior, and similarity. Training Online Learning Models that learn continuously from streaming data, updating incrementally as new data arrives. Foundations Personalization Tailoring content, recommendations, or experiences to individual users based on their preferences and behavior. Agents & RL Monte Carlo Tree Search A search algorithm combining tree search with random sampling, used in game-playing AIs.

Sources

  1. Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed.) . MIT Press, 2018; chapter 2, Multi-armed Bandits
  2. Lattimore and Szepesvári, Bandit Algorithms . Cambridge University Press (free online edition)