Multi-Armed Bandits for Product Decisions

A multi-armed bandit is an A/B test that changes the traffic split while it runs. It is the simplest useful reinforcement learning problem, it is the only one in this cluster you can ship this week, and the arithmetic for what it buys you is four lines long.

A bandit is an A/B test that acts on what it learns

The setup: several options, one decision at a time, and after each decision you observe a reward for the option you chose and nothing about the others. That last clause is the whole problem. In a conventional experiment you decide the split in advance and read the result at the end; a bandit reads the result continuously and moves traffic towards whatever is winning.

It is a reinforcement learning problem with the state removed. Your action does not change which situation you face next, so there is no credit assignment, no discounting and no value propagation — the parts that make RL hard are all absent. This is why so many problems people bring to reinforcement learning are better solved here: pricing tiers, which of five prompts to use, which recommendation slate to show, which email subject line to send.

Compared with a fixed A/B test the trade is explicit. You get fewer conversions lost to the losing variant, and you give up a clean fixed-sample significance test, because the sample sizes are now determined by the data you collected. That is a real cost and it is covered below.

Three batches, worked out

Assumptions. Three variants of a checkout button. Their true conversion rates are 6 per cent for A, 9 per cent for B and 7 per cent for C — unknown to the algorithm. Traffic arrives in batches of 600. Allocation is epsilon-greedy with eps = 0.10, spread evenly across all three arms, with the remainder going to the current leader.

BATCH 1 -- no data yet, so split evenly: 200 / 200 / 200

  observed:   A  12 / 200 = 6.0%
              B  19 / 200 = 9.5%
              C  14 / 200 = 7.0%
  leader: B

BATCH 2 -- eps = 0.10 over 3 arms = 20 visitors each,
           leader takes the remaining 540

  allocation:  A  20      B  560      C  20

  observed:   A   1 /  20 =  5.0%
              B  52 / 560 =  9.3%
              C   2 /  20 = 10.0%

  cumulative: A  13 / 220 = 5.91%
              B  71 / 760 = 9.34%
              C  16 / 220 = 7.27%
  leader: B

BATCH 3 -- same allocation

  allocation:  A  20      B  560      C  20

  observed:   A   2 /  20 = 10.0%
              B  50 / 560 =  8.9%
              C   1 /  20 =  5.0%

  cumulative: A  15 /  240 = 6.25%
              B 121 / 1320 = 9.17%
              C  17 /  240 = 7.08%

Notice batch 2 and batch 3 for arm C: 10 per cent then 5 per cent, on 20 visitors each. Twenty samples tells you almost nothing, and an arm that gets 20 visitors per batch will spend a long time with an estimate that could be off by several percentage points. That is the price of exploiting early, and it is why a bandit is bad at telling you how bad the losers are.

What the reallocation is worth

Compare the allocation the bandit produced against an even split of the same 1,800 visitors, using the true rates declared above:

bandit allocation:  A 240,  B 1320,  C 240
  expected conversions = 0.06*240 + 0.09*1320 + 0.07*240
                       = 14.4    + 118.8      + 16.8
                       = 150.0            (8.33% of 1800)

even split:         A 600,  B  600,  C 600
  expected conversions = 0.06*600 + 0.09*600  + 0.07*600
                       = 36.0     + 54.0      + 42.0
                       = 132.0            (7.33% of 1800)

difference: 18 conversions on 1800 visitors, a 13.6% relative gain

Two honest caveats about that 18. It shrinks as the variants get closer together — if B were 7.5 per cent instead of 9, the same arithmetic gives about 6 conversions rather than 18. And it grows with how long you run before deciding, which is exactly the situation where a fixed test would have been stopped anyway. The bandit is most valuable when the traffic is large, the gap is real, and the decision would otherwise sit unmade for weeks.

Thompson sampling, and why it is usually better

Epsilon-greedy wastes its exploration budget evenly on arms it has already ruled out. Thompson sampling instead keeps a distribution over each arm’s rate and lets the overlap decide the allocation.

For a binary outcome the posterior is a Beta distribution, and updating it is addition. Starting from a uniform prior, Beta(1, 1), and applying batch 1 above:

arm   successes  failures   posterior        mean     std dev
 A       12         188      Beta(13, 189)    6.44%     1.7 pp
 B       19         181      Beta(20, 182)    9.90%     2.1 pp
 C       14         186      Beta(15, 187)    7.43%     1.8 pp

To choose an arm, draw one sample from each posterior and serve whichever draw is highest. B has the highest mean, but B at 9.9 ± 2.1 and C at 7.4 ± 1.8 overlap substantially, so a draw from C beats a draw from B a meaningful fraction of the time and C keeps receiving traffic in proportion to the probability that it is actually best. A, further away, fades faster.

That is the property worth having: exploration is allocated by how plausible it is that an arm is the winner, rather than by a constant you picked. It needs no tuning parameter, it handles any number of arms, and it degrades gracefully when two arms are genuinely equal.

The whole thing in thirty lines

import random

class ThompsonBandit:
    """Beta-Bernoulli Thompson sampling for binary rewards."""

    def __init__(self, n_arms, prior_a=1.0, prior_b=1.0):
        self.a = [prior_a] * n_arms      # successes + prior
        self.b = [prior_b] * n_arms      # failures  + prior

    def choose(self, rng=random):
        draws = [rng.betavariate(a, b) for a, b in zip(self.a, self.b)]
        return max(range(len(draws)), key=lambda i: draws[i])

    def update(self, arm, converted):
        if converted:
            self.a[arm] += 1
        else:
            self.b[arm] += 1

    def summary(self):
        return [(a - 1, b - 1, a / (a + b)) for a, b in zip(self.a, self.b)]


if __name__ == "__main__":
    TRUE = [0.06, 0.09, 0.07]            # unknown to the algorithm
    rng = random.Random(0)
    bandit = ThompsonBandit(len(TRUE))
    conversions = 0

    for _ in range(1800):
        arm = bandit.choose(rng)
        converted = rng.random() < TRUE[arm]
        bandit.update(arm, converted)
        conversions += converted

    print("conversions:", conversions)
    for i, (s, f, mean) in enumerate(bandit.summary()):
        print(f"arm {i}: {s} / {s + f} pulls, posterior mean {mean:.3%}")

Run it with different seeds. The total conversions vary by several per cent between runs and the allocation to the two losing arms varies more than that, which is the honest picture: a bandit is a stochastic process and a single run is one sample from it. If you are going to report the gain from switching to one, simulate it over many seeds with your own rates before promising a number.

Three situations where a bandit is wrong

1. The reward arrives much later than the decision. If conversion happens 14 days after the click, the bandit spends 14 days reallocating on incomplete information, and early arms look worse simply because their conversions have not landed yet. Either model the delay explicitly or use a fixed split.
2. You need a defensible statistical claim. Adaptive allocation invalidates the standard fixed-sample test — sample sizes depend on the outcomes, so the usual confidence intervals are wrong. If the result has to survive a review, run a conventional experiment, or use methods designed for adaptive data such as always-valid confidence sequences.
3. The environment changes. A bandit that has committed to an arm stops collecting evidence about the others, so a change in which arm is best can go undetected for a long time. Sliding windows and discounted counts help; the honest fix is to re-randomise periodically and accept the cost.

There is a fourth, less technical failure: optimising the metric you can measure rather than the one you want. A bandit on click-through finds the most clickable variant, including the misleading one. It is the smallest possible instance of reward hacking and it arrives much faster than in a training run.

Contextual bandits, and model routing

A contextual bandit sees features before choosing: the user, the device, the query. Instead of one rate per arm it fits a model predicting the reward for each arm given the context, and then applies the same exploration logic to the predictions.

This is the shape of the routing problem in an LLM application. The context is the request — length, task type, whether tools are needed — the arms are models, and the reward is some combination of an outcome measure and cost. It is a contextual bandit rather than a full RL problem for one specific reason: routing this request does not change which request arrives next. Keep it that way if you can, because the moment the decision does affect the next state — a multi-step agent where an early cheap model produces context the later steps depend on — you are back in an MDP and the analysis in the MDP page applies instead.