What it costs to find out: exploration under a budget

A system that only ever picks what looks best stops learning without telling you, and a small, logged share of deliberate exploration keeps it learning and makes the next rule testable before it goes live.

What it means for the business

Every system that picks what to do next from past results has this problem, whether the system is a person, a spreadsheet or a model. Which items to process when the budget covers a fraction of them. Which variant of a page to show. Which customers to call, which cases to audit, which ad to run. What you choose produces a result, what you skip produces nothing, and tomorrow's choice is made from today's results.

A system that stops exploring stops learning, and nothing will tell you. The report shows that the chosen things perform well, because the chosen things are the only things with results. It cannot show anything about what was never chosen, so a ranking can stay confident and go stale for years.

Learning can be cheap, if it is targeted. When the same kind of decision repeats often and results come back quickly, the unavoidable cost of finding out grows very slowly, provided the exploration goes where you are still unsure. It is not cheap with many options and few decisions about each, with options that are nearly equal, in a world that keeps changing, or where a wrong choice does real harm; there the exploration budget has to be planned and capped. Zero exploration does not save the cost. It turns it into never finding out.

Keep a measurement tax, and write down the odds. If you want to ask next year whether a different rule would have done better, a small random slice of decisions has to run this year, and every decision has to be logged with the probability it had of being made. Without that, every new rule has to be tried live, at full risk. The slice has a price you can estimate: its share of the budget times how much less a random pick earns than the last ranked picks it pushes out. Size it by the question it will have to answer.

Rank by value per unit of budget. When options cost different amounts, an item worth half as much at a tenth of the cost belongs higher in the queue, not lower.

Say which problem you are solving. Earning while you learn, picking a winner once, or proving how big a difference is. Each needs its own tools. An adaptive test earns more while it runs, because it sends less traffic to the loser, but measures the difference less precisely. A fixed A/B test proves the difference, but only if it is read once, or read with a method built for checking as it goes.

Three questions to ask your data team:

1. How does our system decide what to pursue, what share of that is exploration, and does that share go where we are unsure or everywhere?
2. If we changed the rule, could we score the new one on last year's data without running it live? If not, what would we have had to log?
3. What do we actually know about the things we never choose?

The theory, for the technical reader

The problem

Picture a row of slot machines. Each pays out at its own rate, and nobody tells you which rate belongs to which machine. You have a fixed number of pulls and want to earn as much as possible. It is the smallest version of a problem every business has, and it has been studied since Thompson's paper of 1933, and since the 1950s under the name multi-armed bandit. Herbert Robbins posed the two-machine version in 1952. Peter Whittle later recalled that during the war, efforts to solve it so sapped the energies and minds of Allied analysts that the suggestion was made to drop the problem over Germany, as the ultimate instrument of intellectual sabotage.

The catch is that you only learn about a machine by pulling it. Every pull on a machine you are unsure about is a pull you did not spend on the machine you believe is best.

Regret, and why the obvious strategies fail

The measure the field uses is regret: the total value you would have earned by always choosing the best option, minus what you actually earned. A strategy is good if its regret grows slowly as the number of decisions grows.

Always choose the current leader. A few unlucky results on the truly best option make it look bad, it is never chosen again, and the mistake is never corrected. When that happens, every later decision loses the same amount, so the expected regret grows in a straight line, with a slope set by how likely the lock-in is.

Spread choices evenly. This learns, but a fixed share of every future decision goes to options already known to be worse, so regret again grows in a straight line. The same holds for the common fix of choosing at random a fixed fraction of the time, say 10%. If the random fraction shrinks over time, the loss stops growing in a straight line, and shrinking it at about one over the number of decisions gets close to the floor below (Auer, Cesa-Bianchi and Fischer, 2002), but only if it is tuned to how close the options are, which is what you are trying to learn.

Explore first, then commit. Try everything for a while, pick the winner, never look back. The exploration phase has to be sized before you know how close the options are; in the worst case the regret grows like the number of decisions to the power two-thirds. Slower than a straight line, and still far from the floor.

The floor: how cheap learning can possibly be

In 1985, Tze Leung Lai and Herbert Robbins proved how much learning must cost at minimum. Any strategy that eventually finds the best option, on every problem rather than by luck on one, has to spend a certain number of choices on the others, and for long games that number grows only logarithmically. Concretely, the regret after T decisions is at least about

log T × Σ (gap to the best) ÷ (how distinguishable the option is from the best)

summed over the inferior options. The logarithm means that running the game ten times longer adds roughly a fixed amount of unavoidable waste, not ten times as much. The denominator, formally the Kullback–Leibler divergence between the reward distributions, says that options nearly as good as the best are the expensive ones to rule out: a small gap takes many samples to see. Wildly worse options are cheap, because a handful of tries exposes them.

Two limits matter in practice. The bound is about one fixed set of options and a long game: with a million items each seen a few times it says little, and real systems share what they learn across similar items through their features, which is what contextual bandits do (Li, Chu, Langford and Schapire, 2010). And in the worst case over nearly equal options, the regret grows like the square root of options times decisions, not like a logarithm.

Two strategies that come close to the floor

Optimism. Rate each option not by its average so far but by the best it could plausibly be given the evidence, and choose the top-rated one. An option then gets chosen either because it is good or because it is uncertain, and choosing an uncertain option shrinks the uncertainty. Auer, Cesa-Bianchi and Fischer's 2002 rule, UCB1, makes this concrete: the rating is the average plus a bonus that shrinks as the option is tried more, and its regret per inferior option is bounded by about 8 log T divided by the gap. That grows logarithmically like the floor, but can sit well above it; a refined version, KL-UCB (Garivier and Cappé, 2011), meets the floor exactly for yes-or-no rewards.

Thompson sampling. The older idea, from William Thompson in 1933, and the one that tends to do best in practice. Keep, for each option, a curve describing what its true rate could be given the results so far. Each round, draw one value from each curve and choose the option with the highest draw. An option is therefore chosen with exactly the probability that it is the best one. An option that is almost certainly worse rarely draws highest; an option whose value is unresolved gets drawn in proportion to how likely it is to be the best.

For yes-or-no outcomes the recipe fits on a line. Start each option at one imagined win and one imagined loss. After every result, add one to the wins or the losses. The curve is the Beta distribution with those two counts, and drawing from it is a library call.

Thompson's method was largely ignored for most of eighty years. Steven Scott at Google argued for it in 2010 under the name randomized probability matching. Chapelle and Li showed in 2011 that it matched or beat the alternatives on display advertising and news recommendation data, and in simulations held up better than optimism when results arrived late. In 2012 Agrawal and Goyal gave the first proof that its regret grows logarithmically, and Kaufmann, Korda and Munos showed that it meets the Lai–Robbins floor exactly for yes-or-no rewards. It ran Google Analytics' content experiments, now discontinued, and it is one of the standard policies on Stitch Fix's experimentation platform; Spotify described a simpler bandit with a fixed share of random exploration for its home page in 2018, and Netflix described bandits for choosing artwork in 2017.

Both strategies do the same thing in different ways: they spend the learning budget where the uncertainty is, not evenly and not nowhere.

When each choice costs something

The classic problem counts decisions. Real problems count money, compute or time, and the options differ in what they consume. With a single budget, the intuition is value per unit of cost. With several limits at once, the best plan is a mix of options worked out as a linear programme, and Badanidiyuru, Kleinberg and Slivkins showed in 2013, under the name bandits with knapsacks, how to learn that mix as you go. The exploration logic stays the same: options with uncertain value per cost get tried in proportion to how much the uncertainty could change the plan.

The feedback loop, and why it is invisible

The loop in the figure at the top, where items ranked low never produce the outcome that could raise their rank, is known as the selective labels problem. Lakkaraju and colleagues showed in 2017 how to evaluate a model fairly when outcomes exist only for the cases earlier decision-makers approved, and Chaney, Stewart and Engelhardt showed in simulations in 2018 that recommenders trained on their own recommendations made users' behaviour more alike without making them better off. The bandit view says what to do about it: a share of the budget has to go to items the ranking is unsure about, so that the ranking keeps being corrected by evidence rather than only confirmed by it.

Proving a new rule without running it

Suppose the old system chose deterministically, always the top of its ranking, and you want to know whether a new ranking would have done better last year. The old data contains outcomes only for the items the old system chose. Wherever the new ranking would have chosen differently, there is no outcome to look at, at any sample size.

Now suppose the old system had also processed a small random slice of items regardless of rank, and had logged, for every item, the probability with which it was chosen. Reweighting each logged outcome by one over that probability gives an unbiased estimate of what the new rule would have achieved, provided every choice the new rule could make had some chance of being made and that chance was logged. The estimator comes from survey sampling (Horvitz and Thompson, 1952). In 2011 Li, Chu, Langford and Wang showed on Yahoo's front page, which ran exactly such a random bucket, that replaying random logs predicted how a new rule would do live. The smaller the random slice, the noisier the estimate and the more history it needs.

The weights are the catch. An outcome logged with probability one in a thousand gets a weight of a thousand, and a handful of such outcomes can swing the estimate. The toolkit for that is well established: cap the weights and accept a little bias (Bottou and colleagues, 2013, on Bing's ad placement), normalise the weights so they sum to one (Swaminathan and Joachims, 2015), or combine the reweighting with a model of the outcome so that either one being right is enough (Dudík, Langford and Li, 2011). Netflix's artwork work followed the pattern end to end: candidate models were compared offline on logged data with exploration, and only the winners went to a live test.

Complications that change the answer

Results arrive late. A click is known in a second; whether it turned into a sale may not be known for weeks. A system that counts a silent click as a failure learns the wrong rate. Joulani, György and Szepesvári showed in 2013 that a delay adds to the regret rather than multiplying it, so late feedback is survivable, and Chapelle showed in 2014 how to model the delay itself instead of guessing.

Decisions come in batches. Most systems decide once a day or once an hour, not one at a time. Karbasi, Mirrokni and Shadravan showed in 2021 that Thompson sampling keeps its guarantee with only logarithmically many batches, if the batch sizes are chosen adaptively. In the related problem of tuning expensive experiments, Kandasamy and colleagues showed in 2018 that running Thompson draws in parallel is nearly as good as running them one by one.

The world moves. Everything above assumes that an option's rate does not change. When it does, the fix is to forget: weigh recent results more, or keep only a window of them. Garivier and Moulines analysed both in 2011. A shorter memory learns changes faster and knows everything less precisely.

You may want to stop, not to keep earning. Regret is the right measure when the system keeps deciding. When the goal is to pick a winner once and then stop experimenting, the problem is best-arm identification, and the efficient strategies differ: successive rejects (Audibert, Bubeck and Munos, 2010) drops the worst option at each stage, and top-two Thompson sampling (Russo, 2016) splits the effort between the two leading candidates. A regret algorithm spends most of its tries on the current leader, which it already knows enough about, and too few on the close contender: the right call for earning, the wrong one for picking a winner.

Adaptive allocation and honest inference pull apart. If traffic shifts toward the leader while the test runs, the final numbers are no longer a fair comparison, and that has to be corrected for. The cautionary tale is medical. A 1985 trial of a treatment for newborns made each next patient more likely to receive whichever treatment had done better so far; eleven infants received the new treatment and survived, one received the conventional one and died. The design did what it set out to do ethically, and the result convinced few, because one control patient is not evidence; further trials followed (Ware, 1989). Any adaptive system whose result must later be proven needs a minimum share for every option, and that share is the price of being able to prove it.

Fixed tests have their own trap. A fixed-split A/B test is honest only if it is read once at the end. Optimizely simulated millions of tests of a page against itself in 2015: checked after every visitor, more than half declared a winner or loser at some point; a sequential method built for continuous checking brought that to 3%. Johari and colleagues published the method in 2017.

Sources

• Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285–294.
• Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the AMS 58, 527–535.
• Gittins, J. C. (1979). Bandit processes and dynamic allocation indices, with discussion (Whittle's remark is in the discussion). JRSS B 41, 148–177.
• Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6, 4–22.
• Auer, P., Cesa-Bianchi, N. and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235–256.
• Garivier, A. and Cappé, O. (2011). The KL-UCB algorithm for bounded stochastic bandits and beyond. COLT.
• Li, L., Chu, W., Langford, J. and Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. WWW.
• Scott, S. L. (2010). A modern Bayesian look at the multi-armed bandit. Applied Stochastic Models in Business and Industry 26, 639–658. Scott, S. L. (2015). Multi-armed bandit experiments in the online service economy. Applied Stochastic Models in Business and Industry 31, 37–45.
• Chapelle, O. and Li, L. (2011). An empirical evaluation of Thompson sampling. NIPS.
• Agrawal, S. and Goyal, N. (2012). Analysis of Thompson sampling for the multi-armed bandit problem. COLT. Kaufmann, E., Korda, N. and Munos, R. (2012). Thompson sampling: an asymptotically optimal finite-time analysis. ALT.
• Badanidiyuru, A., Kleinberg, R. and Slivkins, A. (2013). Bandits with knapsacks. FOCS; Journal of the ACM 65(3), 2018.
• Horvitz, D. G. and Thompson, D. J. (1952). A generalization of sampling without replacement from a finite universe. JASA 47, 663–685.
• Li, L., Chu, W., Langford, J. and Wang, X. (2011). Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. WSDM.
• Dudík, M., Langford, J. and Li, L. (2011). Doubly robust policy evaluation and learning. ICML. Bottou, L. et al. (2013). Counterfactual reasoning and learning systems. JMLR 14, 3207–3260. Swaminathan, A. and Joachims, T. (2015). The self-normalized estimator for counterfactual learning. NIPS.
• Lakkaraju, H. et al. (2017). The selective labels problem. KDD. Chaney, A., Stewart, B. and Engelhardt, B. (2018). How algorithmic confounding in recommendation systems increases homogeneity and decreases utility. RecSys.
• Chapelle, O. (2014). Modeling delayed feedback in display advertising. KDD, 1097–1105. Joulani, P., György, A. and Szepesvári, C. (2013). Online learning under delayed feedback. ICML.
• Kandasamy, K. et al. (2018). Parallelised Bayesian optimisation via Thompson sampling. AISTATS. Karbasi, A., Mirrokni, V. and Shadravan, M. (2021). Parallelizing Thompson sampling. NeurIPS.
• Garivier, A. and Moulines, E. (2011). On upper-confidence bound policies for switching bandit problems. ALT.
• Audibert, J.-Y., Bubeck, S. and Munos, R. (2010). Best arm identification in multi-armed bandits. COLT. Russo, D. (2016). Simple Bayesian algorithms for best arm identification. COLT.
• Bartlett, R. H. et al. (1985). Extracorporeal circulation in neonatal respiratory failure: a prospective randomized study. Pediatrics 76, 479–487. Ware, J. H. (1989). Investigating therapies of potentially great benefit: ECMO. Statistical Science 4, 298–340.
• Optimizely (2015). The story behind our Stats Engine. Johari, R., Koning, P., Pekelis, L. and Walsh, D. (2017). Peeking at A/B tests. KDD.
• Netflix Technology Blog (2017). Artwork personalization at Netflix. McInerney, J. et al. (2018). Explore, exploit, and explain. RecSys. Stitch Fix (2020). Multi-armed bandits and the Stitch Fix experimentation platform.
• For the whole field: Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Slivkins, A. (2019). Introduction to multi-armed bandits. Foundations and Trends in Machine Learning 12(1–2).