Exploration and bandits

The model is trained on logs collected by a previous version of the same model. Everything it did not show is absent from the data, and a good item with no impressions will stay unknown: to learn a CTR you have to show the item; to show it you have to know its CTR.

The way out is to change the logging policy. Two cheap ways: a random quota (ε-greedy) and softmax sampling with a temperature. They usually take the first 95% of the benefit. Beyond that comes a bandit layer with an estimate of uncertainty.

An important caveat about softmax sampling: it re-ranks only what the funnel has already selected, and the funnel selected greedily. Real exploration requires a mechanism at retrieval too.

From Hoeffding's inequality: for a sample on [0,1] with true mean μ and sample mean \(\hat\mu\), \(\mathbb{P}(\mu \ge \hat\mu + u) \le e^{-2nu^2}\). Set the right-hand side equal to δ and solve for u: \(U = \sqrt{-\ln\delta / 2n}\).

Then choose δ = 1/k^c — demanding an ever more reliable bound as time goes on — and get \(a_k = \arg\max [Q_k(a) + c\sqrt{\log k / n_k(a)}]\).

It reads as «the estimate of the mean reward plus the width of the confidence interval». The bonus decays as \(1/\sqrt{n}\): at 1 impression it is 3.03, at 1000 it is already 0.096. So no separate exploration knob is needed — the algorithm shrinks it as data accumulates.

UCB is deterministic and optimistic: it takes the upper bound of the interval. Thompson is Bayesian: it samples parameters from the posterior and acts greedily with respect to the sample. For a binary reward that is Beta-Bernoulli — a Beta prior is conjugate to the Bernoulli, the update is trivial (success → α+1, failure → β+1), three lines of code and no hyperparameters beyond the prior.

By regret both are sublinear, unlike ε-greedy: for the latter, doubling the interval doubles the increment (73.9 → 142.5), because a fixed share of random traffic is spent forever.

The main practical difference is not in the reward but in measurability, see the next question.

Because of propensities. UCB is deterministic: in a given state the order is the same, so π(i|u) equals zero or one, and IPS, SNIPS and doubly robust turn into a division by zero. A new model cannot be evaluated offline on such logs.

Thompson defines a distribution over permutations: the propensities are positive and can be estimated by repeated sampling at the same μ and σ. One layer closes both problems — it explores and it makes the data suitable for evaluation.

A caveat: positive propensities alone are not enough, their spread matters too. If 1% of the observations have a weight of 100, the effective sample size falls from 1000 to 39 — the estimate is formally unbiased but useless. Hence weight clipping and the requirement that the policy not stray far from the logging one.

A direct transfer does not work: in the classical setting there are a handful of arms pulled thousands of times each, and here there are millions of items and zero impressions in the tail. The options are an item, a source of candidates, the whole policy, a group of items.

Almost always an item is chosen, and that is possible because an impression counter is not the only source of uncertainty. A trained model can answer «I do not know» about an item with unfamiliar features and an empty history. The uncertainty comes from the model, not from a counter.

Hence the right formulation: a bandit is an add-on over the ranker, not a replacement. The ranker is responsible for the mean, the bandit for what to do with the spread around it.

Four engineering reasons. The cost of a mistake is bounded: the layer rearranges a hundred already-filtered candidates, and the worst case is showing the ninth instead of the second; at retrieval the cost is bounded by nothing. All the features are here, and σ is needed about a (user, item) pair in context. There are few candidates: an ensemble of five models over a hundred is affordable, over ten thousand it is not. And this is the point where a decision is being made anyway.

The limitation: the layer explores only what the funnel selected. If retrieval is greedy, the bandit explores inside an already biased pool.

Three sources: an ensemble of models (the sample variance of the predictions), MC-dropout (dropout at inference, several passes of the head) and neural linear (Bayesian linear regression over the last layer, giving an honest \(\sqrt{x^\top A^{-1}x}\)). The first two cost almost nothing in development.

The main thing is not to confuse epistemic uncertainty («the model does not know», decreases with data) with aleatoric («the event is random», never decreases). The temptation to take \(\sigma = \sqrt{p(1-p)}\) is strong — the formula is at hand. But that is pure aleatoric noise: at p = 0.3 it equals 0.4583 both at one impression and at ten thousand. Such a bonus is maximal at p = 0.5 and simply drags mediocrities upwards.

The check: plot σ as a function of the number of impressions. No dependence means you are measuring the wrong thing. And do not build an ensemble from models with a shared embedding table: the predictions will coincide and σ will collapse.

Remember that the dependence is a hump, not a staircase. In the simulation α = 3 gives 0.909 of the ideal output against 0.834 for greedy (plus 9% by rearranging the same pool), while α = 5 already gives 0.891: we start lifting items about which everything is already clear.

And separately about small α. At α = 0.5 the gem looks into the top in 7 catalogues out of 8 but settles at top-1 in only 2: it gets a few impressions, catches an unlucky streak, its estimate sags, and the bonus \(\propto 1/\sqrt{n}\) has already dried up. A small bonus is worse than none — it spends impressions without finishing the job.

When a random quota and softmax sampling are enough — and they are enough to take the first 95% of the benefit. The layer pays for itself under three conditions at once: the catalogue updates fast, there is an honest estimate of uncertainty, and propensities are needed for offline evaluation.

There is also a deterministic alternative: hard-lift exactly one post by a little-known author to a fixed position. That is how it is done in the open-sourced code of the X feed. Predictable, explainable, ten lines — and if the only task is to keep a new author from dying in obscurity, that is enough.

And a methodological trap: the gain from exploration shows up in the quality of future models, while it is measured by a week-long A/B on today's metrics. On that horizon it almost always looks like a loss.