Exploration, Contextual Bandits, and Online Learning

High-confidence head articles took almost all of the exposure a news recommender had to give. Offline data showed little evidence about niche sources, so every new model stayed uncertain about them and went on avoiding them. The loop closes on itself. A bandit receives feedback only for the action it chose, and the policy chose the head. In the logs, an item that genuinely performs badly and an item nobody tried look identical. The only thing that tells them apart is exposure. And exposure is spent out of a real user's session. That is what the rest of this lesson is about: what that exposure costs, who has paid it in public, and what has to be recorded while it is being spent.

Exploration is bounded before it starts. The loop runs in five stages, and four of them are decisions taken in advance. Context and eligible actions defines which candidates can be responsibly explored. Policy and probability chooses actions with known or reconstructable probabilities. Outcome and delay observes reward, guardrails and mature consequences. That stage's name matters: how long feedback takes to arrive changes which exploration method wins. Estimator and update learns from chosen actions while accounting for policy selection. Budget and stop rule limits regret, exposure, risk and experiment duration. Without that last stage, all four run until somebody notices.

The difference is where the uncertainty lives. Epsilon-greedy holds none. It randomizes a fixed share of decisions anyway, which is what makes its propensities so easy to write down and its behaviour easy to audit. The price is that it explores weak actions indiscriminately, so the eligible action set has to do the protecting.

Upper confidence bound adds a bonus for what the model does not know. The size of that bonus is not a metaphor. Auer and two co-authors proved it in 2002. UCB1 is the average reward plus a one-sided confidence bonus, and their Theorem 1 bounds its expected regret after n plays at 8·Σ_{i:μi<μ*}(ln n / Δi) + (1 + π²/3)·Σ_j Δj, for arbitrary reward distributions supported in [0,1]. What was new was not that regret grows logarithmically. It was when the guarantee applies. The abstract says it in one line: “In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.” Uniformly over time, not only asymptotically — the bound holds at the horizon you actually stop at. The cost of that guarantee is calibrated uncertainty. The bonus is only as good as the confidence interval underneath it.

Thompson sampling draws one plausible world and acts as though it were true. The case for it is empirical rather than a guarantee. Chapelle and Li ran both methods to T = 10^6 in 2011. The pool held 10 items, and at any given time one of them retired with probability 10^-3 and was replaced by a new one. Results were averaged over 100 repetitions. Then they varied how often feedback came back. With feedback at every step (δ=1), regret was 24,145 for UCB against 9,105 for Thompson — a ratio of 2.65. With feedback arriving only every 1,000 steps (δ=1,000), it was 226,220 against 59,256, a ratio of 3.82. “It appears that Thompson sampling is more robust than UCB when the delay is long,” they wrote. That is the map's outcome-and-delay stage with a price on it. A deterministic rule keeps picking the same arm while it waits. Here the wait cost it 3.82 times the regret.

A contextual bandit observes a context, chooses an action, receives feedback for the chosen action, and updates a policy. Exploration balances current estimated value against information about uncertain alternatives. Recommendation action spaces are large and structured, so practical systems often explore within a retrieved candidate set, or use uncertainty and randomization at selected stages.

What an exploration budget looks like in production is on the record. On MSN, the Decision Service ran exploration as epsilon-greedy with ε = 33%, on a 10-minute experimental unit, with a new model deployed every 5 minutes. Twelve authors published that deployment in 2016. A third of decisions randomized, and the loop closed in five minutes. Measured against the editorial ordering it replaced: “Experiments on the Slate segment of the page showed a >25% CTR improvement over a two-week period; the Panel showed a 5.3% improvement, which is even more significant as it receives 10x more traffic than the Slate.” Long-term engagement metrics were maintained or improved. Note which number is the impressive one: the smaller improvement, on the surface carrying ten times the traffic. Exploration must still respect eligibility, safety, user controls and experience budgets. Those bounds are numbers someone wrote down before Monday, not a disposition.

Exploration starts by restricting the action set to candidates that are eligible and plausibly useful. Then choose the uncertainty method and the budget: exposure limits, segments, stop conditions. Then log probabilities, preserving action probabilities, context, candidates and policy version. Then monitor regret and guardrails, tracking immediate and delayed user and provider outcomes. Then evaluate off-policy, checking overlap, weight variance and estimator sensitivity.

Steps three and five are one step separated in time, and there is a published receipt for what step three buys. A replay estimator is provably unbiased only under a randomized logging policy. Li and three colleagues showed that in 2011, and stated the condition in the paper itself: “In this section, we describe a sound technique for carrying out such an evaluation, assuming that the individual events are i.i.d., and that the logging policy chose each arm at each time step uniformly at random.” They validated it on about 40 million events from a Yahoo! Front Page “random bucket”, collected between 1 and 10 November 2009, with roughly 20 articles in the pool at any moment.

Read that as a price list. An unbiased offline estimate was not extracted from ordinary traffic by cleverness. It existed because uniformly random exposure had been served to real visitors for ten days, and recorded as such.

No support makes an estimate meaningless, because the new policy prefers actions the logs almost never exposed. A wrong propensity makes it confidently false, and the Decision Service team measured how false. On MSN exploration data, split 80/20 in time order, correctly logged data kept the train/test performance discrepancy within 5%. Overriding 10% of actions, so that the recorded probability was wrong, produced a 3.0x discrepancy. That is larger than reward-delay bias (1.3x), a modified feature (1.2x) or a deleted feature (2.4x), and second only to using the decision itself as a feature (8.7x). The failure is mundane rather than exotic: “A common error is when editors or business logic override the chosen action and record the override making the recorded probability incorrect.” An editor's veto on one decision in ten was enough.

Experiment contamination has a documented industrial fix. Google deployed overlapping experiment infrastructure in March 2007 and described it in 2010. System parameters are partitioned into layers, so a request sits in at most N experiments at once, one per layer. “Each experiment can only modify parameters associated with its layer (i.e., in that subset), and the same parameter cannot be associated with multiple layers.” Interaction is prevented by the parameter partition, not by coordination between teams. Google reports the arrangement enabled nearly an order of magnitude more experiments, launches and experimenters.