Adaptive Experiments and Bandit Allocation

Yahoo!'s Front Page Today Module — the box that decides which story a visitor meets first — was run as a contextual-bandit problem. The system did exactly what the abstractions describe. It observed something about the visitor, chose an article, watched for the click, and let what it saw change what it chose next. The team published the results in 2010.

The gain was measured rather than asserted. The abstract states it in one sentence: “Finally, using this offline evaluation method, we successfully applied our new algorithm to a Yahoo! Front Page Today Module dataset containing over 33 million events. Results showed a 12.5% click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.”

Now the part that is easy to read past. That 12.5% is not something the adapting system worked out about itself. The events came out of a random bucket — traffic in which articles were chosen uniformly at random rather than by any policy. About 4.7 million events on 1 May 2009 served as tuning data, and about 36 million events over 3-9 May 2009 as evaluation data. The number that justified the adaptive algorithm was produced by the one slice of traffic forbidden to adapt.

That is the trade in its plainest form. Adaptation buys you a real gain, and less loss while you are still finding out. What it does not buy is the evidence for its own gain. A log written entirely by an adapting policy is thick wherever its estimates were already high and thin wherever they were low. And an option it has stopped showing is an option it has stopped learning about — including everything the person did afterwards, once the click was over.

A response-adaptive design updates its assignment probabilities as outcomes arrive, and it can condition them on the context of each unit as well. That is the whole point of it. Less traffic spent on the option that is losing means less cost paid while learning, and on a surface that repeats forever, that saving is not small.

The cost lands somewhere else.

Observations collected this way are not independent draws. What the system saw earlier decided what it looked at later, so the record is dependent by construction, and unevenly sampled on top of that — thick wherever the estimate was already high, thin wherever it was low. Ordinary analysis assumes neither of those things about its input.

Getting the evidence back means holding four conditions at once. You know the probability with which each action was logged. You explored enough that no arm and no segment is empty. The reward meant the same thing at the end of the run as it did at the start. And the method you analyse with was built for adaptively collected data rather than for a fixed design.

The third of those sounds like housekeeping and is not. A simulated 200-patient trial makes the case. Four Bayesian outcome-adaptive randomization methods were set against an equally randomized group-sequential design, in Annals of Oncology in 2015. Outcome-adaptive randomization overestimated the treatment effect and lost power. The estimation bias grew much larger when patient prognosis drifted during the trial — that is, when the thing being rewarded stopped meaning what it had meant at the start. It could also fail on its own ethical terms. “Outcome AR has several undesirable properties. These include a high probability of a sample size imbalance in the wrong direction, which might be surprising to nonstatisticians, wherein many more patients are assigned to the inferior treatment arm, the opposite of the intended effect,” report Thall and colleagues.

Miss one of the four and you still have the clicks. You simply have no defensible account of what you learned. Optimizing the reward that arrives now also quietly spends whatever would have arrived later — the delayed outcome nobody measured, the precision someone downstream was going to need.

A fixed experiment spends its whole run collecting one clean comparison, and pays for that in every unit it sends to the option that turns out to be worse. An adaptive design spends the run earning instead, and pays for it in the comparison.

Both halves of that sentence have a price, and a simulation has named them. A 148-patient two-arm trial was run under the alternative hypothesis, with p0 = 0.3 and p1 = 0.5, in Statistical Science in 2015. Fixed randomization gave power 0.809. The Gittins-index bandit rule gave 0.364. The Current Belief (CB) and Whittle-index (WI) rules gave 0.228 and 0.282. “In the most extreme case, for the CB and WI rules, the power is approximately 3.5 times smaller than with a FR design,” write Villar and colleagues.

What the bandit bought with that power sits on the other side of the same simulation, and it is not nothing. The proportion of patients reaching the better arm rose from 0.501 under fixed randomization to 0.862 under the Gittins index. Nearly nine patients in ten on the better treatment, against roughly one in two. The price was keeping less than half the power to demonstrate that it was the better treatment. Neither design is the careful choice by default. The careful choice is knowing which of the two you actually need before you start.

Three questions usually settle it. What does exploration cost here — a slightly duller headline for one reader, or a worse dose for one patient? Will the best action still be the best action later, or does the answer drift with the season, the audience, the news cycle? And what do you owe at the end of this: a decision you can act on quietly, or evidence that someone else will have to defend?

All four have already done their work in the story of the Front Page Today Module. They are worth stating plainly on their own, because in a fast meeting they slide into one another, and most of the failures in this lesson begin as a word used loosely.

The fourth of them has a price tag attached to it from a production system. Microsoft deliberately randomized the Bing ad placement system. Mainline reserves were multiplied by a log-normal draw with mean 1 and width sigma = 0.3, so that 95% of the multipliers fell between 0.52 and 1.74. Twenty-two million search result pages were collected over five consecutive weeks. Against an unrandomized control bucket, the randomization produced only a small but statistically significant rise in mainline ads per page. The click yield and average revenue differences were not significant. In return, the logged choice probabilities let the same data answer counterfactual questions the system never ran.

That return is not optional extra credit. It is a requirement of the method. “Since these factors represents conditional probabilities resulting from the effect of an independent noise variable in the structural equation model, this assumption means that the data must be collected with an experiment involving active randomization,” write Bottou and colleagues in 2013.

Whether adaptation makes sense is not a question about how big the surface is or how much money rides on it. It is a question about the reward and the way you observe it: how fast it comes back, how faithfully it stands in for the thing you actually care about, and how often the same decision comes round again. Two of the four cases below are settled by a regulator's own text, and one by a trial that has been argued about ever since.

Each pass through the system does the same four things in the same order. It observes the context — who arrived, and what is already known about them. It chooses an action under the current policy. It observes the reward that action earned. It updates the policy, so the next person meets a slightly different system than the last one did.

Nothing inside that circle checks its own coverage. That is the fifth step, and it sits outside the loop deliberately. Someone has to look at where the traffic actually went, arm by arm and segment by segment, and ask whether any part of the space has quietly emptied out. It is also the step that shows you which assumptions the loop has been running on: that the reward still means what it meant, that every arm is still being seen.

In the Front Page Today Module work that step had a physical form — a bucket of traffic in which articles were chosen uniformly at random, sitting outside the policy and reporting on it. What the check is looking for has already been measured. Even the best-behaved rule in the two-arm simulation stopped allocating to the truly superior arm with probability 0.0035, and the worst did so with probability 0.1730.

Take one real surface — a ranking, a layout, a message people receive — and answer four things for it on paper, before any code. What exactly is the reward, and when does it arrive? How often does the same decision come round again? What does a wrong choice cost the person on the other end of it? And could you say afterwards, for any single impression, how likely the system was to choose what it chose?

The fourth question has a known passing answer and a known price. Microsoft paid it in the open. A log-normal multiplier of mean 1 and width sigma = 0.3 on mainline reserves, 22 million search result pages over five consecutive weeks, and no significant difference in click yield or average revenue against the unrandomized bucket. If your surface cannot state a comparable price, you do not yet know what you are proposing to spend.

Then write out the fixed version of the same test beside it, and state what each design leaves you holding at the end — one side holding power 0.809, the other holding 0.862 of its units on the better arm. The comparison tends to settle itself, and often not in favour of the more sophisticated option.

Every system of this kind optimizes a stand-in for the thing you actually want. A fixed experiment is at least neutral about that stand-in: if clicks are a poor proxy for satisfaction, the experiment will still show you the damage sitting in the other measurements. An adaptive one is not neutral. It takes the proxy at its word and pushes more and more traffic toward whatever maximises it, so a weak proxy is not merely misleading — it is amplified. Short-term clicks come out of satisfaction, out of diversity, out of safety.

Which is why none of these should run bare. Guardrail metrics that can stop it. Evaluation against the delayed outcome and not only the immediate one. A floor under exploration so that no arm can be starved — the arm abandoned with probability 0.1730 under the Current Belief rule was the truly superior one. Constraints on what the policy is permitted to do at all. And randomized holdouts, revisited on a schedule rather than when someone remembers.

The rule underneath all of it is short. Prefer fixed randomization when what you owe is an unbiased comparison, when the outcomes are delayed, when rare harms are the thing you are watching for, or when a minimum of information about each arm is non-negotiable. Prefer adaptive allocation when the action repeats, the reward comes back reliably, exploration is ethically acceptable, and learning a good policy — rather than answering a question — is genuinely the objective.

The two are not exclusive, and the hybrid is usually the honest answer. Hold a slice of traffic in plain randomization, adapt the rest, and you keep a clean read on exactly the thing the adapting part of your system is busy optimizing away.

That slice is not a thought experiment. A second Yahoo! paper, in 2011, built an entire offline evaluation method on one: “For offline evaluation, millions of events were collected from a “random bucket” from Nov. 1 2009 to Nov. 10 2009. In the random bucket, articles are randomly selected from the article pool to serve users.” About 40 million events in the offline evaluation data set, about 20 articles available in the pool at every moment, and a replay estimator they proved unbiased. None of it could have been recovered from a log written entirely by the policy under test.