How does Thompson sampling's cumulative regret compare with a fixed 50/50 split?

## Defining regret properly Cumulative regret is a business quantity, not an inferential one. For each impression, take the true rate of the best arm minus the true rate of the arm you actually served, and add it up over all impressions. It measures the reward foregone relative to an oracle that knew the best arm from the start. It is denominated in conversions (or revenue), it is only computable in a simulation where the true rates are known, and it says nothing about whether you can declare a winner. A candidate who defines regret as "the difference between the observed conversion rates" has confused it with an effect estimate. The two answer different questions: regret asks *what did serving cost me*, an effect estimate asks *how different are the arms*. ## The fixed split, exactly A fixed 50/50 split is trivial to analyse. With arms whose true rates are 4% and 5%, half of all traffic goes to the worse arm forever, and each such impression costs 0.01 conversions in expectation. Over 100,000 impressions: `regret = 50,000 x (0.05 - 0.04) = 500 conversions` The key property is that this grows **linearly** in the horizon. The split does not learn. At a million impressions the loss is 5,000 conversions; at ten million, 50,000. Every additional impression under a fixed split contributes the same expected regret as the first one, because the allocation never responds to what has been learned. ## Thompson sampling, asymptotically Thompson sampling's allocation does respond. Early on, when the posteriors overlap, it splits traffic near-evenly and accumulates regret at roughly the fixed-split rate. As the posteriors separate, the worse arm's draws stop winning and its traffic share collapses. The total number of impressions it ever spends on the worse arm grows only about **logarithmically** in the horizon — the classic result for stochastic bandits is that the plays of a suboptimal arm scale like `log(T)` divided by a divergence term that shrinks as the arms get closer. Multiplying by the per-impression gap, cumulative regret scales like `log(T) / gap` rather than `T x gap / 2`. The practical consequence is about the *shape*, and that is the part worth emphasising in an interview. At a modest horizon with a small gap, Thompson sampling saves a factor of a few — the sampler still needs a lot of traffic to separate a 4% arm from a 5% arm, and it pays regret while doing so. At ten times the horizon, the fixed split's regret is ten times larger while Thompson sampling's has barely moved. The advantage compounds with how long the allocation runs, not with how clever the rule is. ## Where the gap matters Regret depends on the gap between arms in two opposing ways. A large gap makes each wasted impression expensive, but it also makes the arms easy to separate, so an adaptive rule cuts its losses almost immediately — this is where Thompson sampling wins overwhelmingly. A tiny gap makes separation slow, so the sampler splits traffic near-evenly for a long time and behaves much like the fixed split — but each wasted impression costs almost nothing, so the absolute regret is small either way. The uncomfortable middle is a moderate gap over a moderate horizon, where the difference is real but only a factor of a few. A useful sanity check before claiming a big win from adaptive allocation: multiply the expected gap by half your traffic. If that number is not material to the business, adaptive allocation is not solving an expensive problem. ## What the fixed split buys Regret is one axis, and optimising it alone is a mistake. The equal split provides things the adaptive rule deliberately gives up: - **Equal, pre-planned sample sizes.** Every arm ends with the same number of impressions, so every arm's rate is measured to the same precision. Thompson sampling deliberately starves the loser, so you end up knowing the winner well and the loser poorly — including *how much* worse it was. - **A stable allocation.** The split does not move while a report is being read or a dashboard reviewed. An adaptive allocator's shifting shares make day-over-day metric comparisons harder to interpret, because the mix of served arms changed underneath them. - **Operational simplicity.** No posterior state to persist, no update pipeline to keep healthy, no allocation to rate-limit. ## Honest caveats Thompson sampling does not dominate in every run. Over a short horizon, with a mis-specified prior, or when rewards land long after decisions, it can trail a fixed split — the guarantee is asymptotic and in expectation, not per-run. And regret is measured against the *best available arm*: an adaptive rule that concentrates perfectly on a mediocre arm because no better one was in the pool has low regret and no business value. ## The compact answer Fixed split: regret `= T x gap / 2`, linear, unbounded. Thompson sampling: regret about `log(T) / gap`, sublinear, flattening. The longer it runs and the larger the gap, the bigger the advantage — and the fixed split buys balanced sample sizes and a stable allocation in exchange.