Exploration, Exploitation, and Contextual Bandits

In a multi-armed bandit, the learner repeatedly chooses among actions and observes a reward for the chosen action. A contextual bandit sees more. It also observes information about the current case before choosing.

Unlike full reinforcement learning, the standard bandit abstraction does not emphasize long chains of action-dependent state. It is appropriate when each decision is largely evaluated by its immediate or bounded outcome.

The abstraction is not a web-era invention. The rule now called Thompson sampling — draw each arm with its posterior probability of being optimal — was described by William R. Thompson in Biometrika in December 1933. The 2012 paper that finally analysed it still says the algorithm “dates back to 1933”. What took eight decades was not the idea but the guarantee. Chapelle and Li reported in 2011 that the 78-year-old heuristic was empirically competitive with UCB — short for upper confidence bound, the rule that plays whichever arm has the highest optimistic estimate: its average reward so far plus a bonus that is larger the less the arm has been tried — and the proof arrived from Shipra Agrawal and Navin Goyal the following summer: “In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the stochastic multi-armed bandit problem.” Their bound for the stochastic two-armed bandit is O(ln T/Δ + 1/Δ³). In plain words: the bound on the reward given up grows only with the logarithm of the number of rounds T, so doubling a long run adds a fixed amount of regret rather than doubling it, and it grows as Δ, the gap between the better and the worse arm, shrinks, because close arms are harder to tell apart. Seventy-nine years separated a working rule from a reason to trust it. That is worth remembering before you read a bandit heuristic's good behaviour on a dashboard as evidence about its behaviour in general.

The measurement most often cited for what context is worth comes from Yahoo!’s front page. In 2010 four researchers modelled the choice of article for its Today Module as a contextual bandit. They evaluated it on a logged dataset of “over 33 million events”. Their LinUCB algorithm conditions on user and article features. It produced “a 12.5% click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.” The size of the prize is a fair guide to the size of the argument. A personalised policy beat an unpersonalised one by an eighth, not by a multiple.

The choice depends on whether allocation adapts and whether actions reshape future states.

What adaptive allocation costs is on record in medicine, and the cost is not the one usually anticipated. Bartlett's 1985 ECMO study was one of the earliest clinical trials to use response-adaptive allocation. It applied the randomized play-the-winner rule to newborns. The rule did exactly what it was designed to do, and in doing so destroyed the comparison. James H. Ware set out the outcome in 1989: “This trial used a randomized play-the-winner design. Eleven patients received ECMO therapy and all survived. Only one patient received CMT and this patient died. In part because of the success of ECMO therapy, this trial provided very little comparative data on the two therapies.” Twelve patients in total. A control arm of one child. A later review from the MRC Biostatistics Unit at the University of Cambridge reports the identical counts: “In total, 12 patients were observed: one in the control group, who died, and 11 in the ECMO group, who all survived”.

A second trial, with fixed randomization, had to be run before anyone learned anything: 6 of 10 survived on conventional therapy and 9 of 9 on ECMO. Response-adaptive randomization was then little used in clinical trials for the following 20 years. The stated risk of adaptive allocation is that it exposes people to weaker options. ECMO is the opposite failure. The allocation was defensible for every individual patient and evidentially almost empty, eleven patients to one. Choosing a fixed randomized experiment is not timidity. It is a decision that the comparison is the product.

Only the reward for the chosen action is normally observed. That creates counterfactual uncertainty.

The cycle also has a clock, and the price of ignoring it has been measured. Chapelle and Li simulated a 10-item dynamic pool for a million steps. Updating after every step left UCB with a regret of 24,145. Updating only every 1000 steps pushed it to 226,220, roughly ninefold. Thompson sampling's rose from 9,105 to 59,256, and the ratio between the two widened from 2.65 to 3.82. Live traffic told the same story. On over 34 million randomized Yahoo! front-page serving events collected over 7 days in June 2009, UCB's normalised click-through rate fell sharply as the update delay went from 10 to 60 minutes, while the randomized policies held up. Chapelle and Li state it plainly in their section on “News Article Recommendation”: “While the deterministic UCB works well with short delay, its performance drops significantly as the delay increases.” Agrawal and Goyal, working independently, list “small regret for delayed feedback” among Thompson sampling's properties.

The mechanism is structural rather than incidental. A deterministic rule commits every impression in the batch to the arm that looked best when the last update landed. A randomized one keeps spreading its bets while the feedback is in flight. Joulani and his co-authors gave the formal companion result in 2013: delay increases regret multiplicatively in adversarial problems and additively in stochastic ones. Step 4 of the cycle is not a bookkeeping step. Its period is a design parameter with a measured price.

Online adaptation should begin with a policy and governance review.

That review is not a courtesy this lesson invented. Two drug regulators have published theirs. The FDA issued its final guidance on adaptive designs for clinical trials of drugs and biologics in November 2019. It defines an adaptive design as one “that allows for prospectively planned modifications to one or more aspects of the design based on accumulating data from subjects in the trial”. Prospectively planned is the whole of the first two steps below. The admissible actions and the baseline are fixed before the data arrives, not selected once it has. The same guidance names play-the-winner explicitly under response-adaptive randomization, and attaches there the condition that is the fifth step: “Finally, as with many other adaptive techniques based on outcome data, response-adaptive randomization works best in trials with relatively short-term ascertainment of outcomes.” ECMO used exactly the design that paragraph governs, randomized play-the-winner.

The European Medicines Agency aims at the analysis instead. Its reflection paper, adopted on 18 October 2007, calls a design adaptive only if the modification is made “with full control of the type I error”. An adaptation the analysis does not account for does not qualify as an adaptive design in that document. It is simply an uncontrolled one. Neither agency forbids adaptation. Both make it conditional on things being written down first, which is what the steps below ask of a deployed policy.

The suitability of exploration depends on reversibility, feedback delay, and who bears the cost.

Regret compares accumulated reward with a reference policy that would choose better actions under the model. It captures the cost of learning over time. That cost has a known rate, and a known floor. Auer and his co-authors open their 2002 finite-time analysis of the multi-armed bandit problem by recalling the floor: “Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays.” Lai and Robbins had established in 1985 that no allocation rule that does well on every problem instance can do better than Ω(ln n). Theorem 1 of the 2002 paper shows that its UCB1 policy reaches that rate with the constants written down: on K machines with rewards supported in [0,1], expected regret after n plays is at most 8·Σ_{i:μi<μ*}(ln n / Δi) + (1 + π²/3)·Σ_{j=1..K} Δj. The bound holds uniformly over time, not merely asymptotically. Learning has a price, the price is logarithmic, and you can compute it in advance.

Product teams also need absolute safety, fairness, stability, and long-term effects. A policy can have low regret under a narrow reward and still be unacceptable. ECMO is the sharpest case. Eleven of its twelve patients were allocated to the arm that worked, which is close to no regret at all, and the trial produced almost no comparative data on the two therapies. Regret was the wrong objective for what that trial existed to do.

The two article placements below are invented, with click rates chosen for easy arithmetic. Placement A is clicked 5% of the time and placement B 4%, though the learner does not know that at the start.