What does cumulative regret measure in a multi-armed bandit experiment?

## The setup regret is defined on A multi-armed bandit problem has **arms** (the variants you can serve), **rounds** (each user or impression you must assign), and a **reward** observed after each round — a click, a conversion, revenue. Arm `a` has an unknown true mean reward `mu_a`. The best arm has mean `mu* = max over a of mu_a`, and each arm's **gap** is `Delta_a = mu* - mu_a`, which is zero for the best arm and positive for every other arm. At round `t` your **policy** picks an arm `a_t`. The **instantaneous regret** of that round is `mu* - mu_{a_t}` — what you gave up by not serving the best arm on that round. **Cumulative regret** over N rounds is the sum: ``` R_N = sum over t of (mu* - mu_{a_t}) = sum over arms of Delta_a * n_a ``` where `n_a` is the number of rounds arm `a` was served. The second form is the useful one: regret is *how much traffic you sent to each loser, weighted by how much worse that loser is*. ## Regret is defined against unknown quantities The definition uses the **true** means, not the rewards you happened to observe. That has a practical consequence people often miss: you cannot read your realized regret off a dashboard, because you never know `mu*`. Regret is a criterion for reasoning about and comparing allocation policies before and after the fact, and an estimate of it is only as good as your estimate of the gaps. (The version above, using the true means rather than realized noisy rewards, is often called *expected* or *pseudo*-regret.) ## A worked example Two variants of a signup button have true click rates 5.0% and 4.0%, so `Delta = 0.01` for the worse one. You have 100,000 impressions. - **Even fixed split.** 50,000 impressions go to the 4% variant. Regret = `0.01 * 50,000 = 500` clicks lost over the run. - **Adaptive allocation** that learns quickly and ends up serving the worse variant only 5,000 impressions pays `0.01 * 5,000 = 50` clicks. Note what scales the answer: the **gap**, not the win. A 0.1-point gap over the same traffic costs a tenth as much, which is exactly why small effects are cheap to leave undecided and large effects are expensive. ## Linear versus sublinear regret Any fixed allocation that keeps sending a constant share of traffic to a worse arm has regret growing **linearly** in N — twice the traffic, twice the loss. An allocator that concentrates traffic on the leader as evidence accumulates can get regret growing **sublinearly** (much slower than N), so *average* regret per round goes to zero as the run gets longer. Policies with that property are called no-regret policies. This is the entire promise of adaptive allocation: not that it is faster, but that the price you pay for learning stops growing proportionally to how long you run. ## Why the objective matters: earnings versus estimation A fixed-horizon A/B test optimises a different thing entirely. Its objective is an **unbiased estimate** of the difference between arms, with a confidence interval narrow enough to support a decision. For a two-arm comparison with total sample size N and similar variances, the variance of the estimated difference is `sigma^2 * (1/n_A + 1/n_B)`, which is **minimised when the split is even**. So the allocation that best measures the difference is exactly the allocation that maximises regret, and the allocation that minimises regret starves the losing arm of the data needed to measure it. The two goals are in direct tension; choosing between them is choosing what you are buying with your traffic. ## Simple regret and identification Cumulative regret counts every round of the run. A different objective, **simple regret**, only counts the end: if you recommend arm `r` at the end, simple regret is `mu* - mu_r`. Under a fixed sample budget, *best-arm identification* aims to make the probability of recommending the wrong arm as small as possible, and it happily spends samples on near-tied contenders that a cumulative-regret objective would starve, because in-run earnings do not count against it. ## Common mistakes - Treating regret as an error rate or a p-value. It is measured in units of the reward — clicks, conversions, revenue — not in probability. - Measuring regret against the average arm rather than the best arm. - Claiming a fixed-horizon test has no regret. It has a lot of regret, deliberately; that spend is what buys the clean estimate. - Assuming a low-regret run also produces a trustworthy per-arm effect estimate. It does not, because allocation depended on the data.