Multi-Armed Bandit Algorithms for Optimization

The explore/exploit tradeoff

The name comes from a "multi-armed bandit" — a row of slot machines, each with an unknown, different payout rate, where a gambler has to decide, pull by pull, whether to keep testing machines that might pay better (exploring) or stick with the machine that's performed best so far (exploiting). Every optimization decision with a limited budget of trials faces this exact tension: spend too much time exploring and you waste resources on options you already have enough evidence are inferior; spend too little and you lock in a choice before you've actually learned enough to be sure it's the best one. A multi-armed bandit algorithm is a formal policy for allocating trials between exploration and exploitation that adapts as evidence accumulates, rather than committing to a single fixed split in advance.

Why a standard A/B test is a fixed, inefficient allocation

A classic A/B test allocates traffic in a fixed split — commonly 50/50 — for the entire duration of the test, regardless of how the results are trending partway through. If one variant is clearly performing worse by day three of a four-week test, a fixed-split A/B test still keeps sending it half of all remaining traffic for the next 25 days, purely because the pre-registered design said so. That's the correct choice when the goal is a clean, unbiased estimate of the true effect size for a permanent decision — but it's wasteful when the actual goal is simply to maximize total conversions over the test period itself, since every visitor routed to the losing variant during that time is a conversion left on the table.

Epsilon-greedy: the simplest bandit policy

Epsilon-greedy is the easiest bandit algorithm to understand and implement: pick a small probability epsilon (commonly 0.05-0.10), and on each trial, explore (pick a random arm) with that probability, otherwise exploit (pick whichever arm currently has the best observed performance). It's crude — it keeps exploring at a constant rate even after the right answer is extremely well established, and it treats a barely-behind arm the same as a hopelessly behind one when deciding whether to explore it — but its simplicity makes it easy to reason about and implement correctly, which has real value over a more sophisticated algorithm nobody on the team fully trusts.

Thompson sampling: allocating in proportion to confidence

Thompson sampling takes a more principled approach: it maintains a probability distribution over the likely true conversion rate of each arm (updated continuously as data comes in), and on each trial, draws a random sample from each arm's current distribution and picks whichever arm's sample came out highest. Early on, when an arm's distribution is wide (little data, high uncertainty), it still gets picked fairly often because its samples can swing high just from that uncertainty — which naturally produces exploration without a fixed epsilon parameter. As data accumulates and an arm's true performance becomes clear, its distribution narrows, and the algorithm exploits it more and more automatically. This makes Thompson sampling self-tuning: it explores heavily while uncertain and smoothly shifts to exploitation as confidence grows, without anyone having to hand-set an exploration rate.

Epsilon-greedy vs. Thompson sampling vs. fixed A/B test

What's next

Whether using a fixed A/B test or a bandit algorithm, the thing actually being optimized is usually a landing page's conversion rate — the next lesson covers the structural framework for diagnosing and improving that page itself.

Next: Landing Page Optimization Framework →