Cold start, exploration and bandits

What it is

Cold start is the condition where a ranking or recommendation system has no behavioural signal for an entity, so the signals it normally ranks by are empty. There are three distinct versions and they need different solutions:

Type	Missing signal	Typical fix
Item cold start	New listing, video, product: no clicks, no purchases	Content features, exploration budget
User cold start	New or logged-out user: no history	Popularity priors, onboarding, context
System cold start	New market, new vertical, new deployment	Transfer from a related domain, editorial rules

Exploration is deliberately showing something whose value you are uncertain about, in order to learn its value. A bandit algorithm is a formal policy for deciding how much to explore and what to explore, given that every exploratory impression costs you the expected revenue of showing the known-good item instead.

The thing this is confused with is A/B testing, and the distinction is worth stating precisely. An A/B test fixes the allocation and measures; a bandit changes the allocation as it measures. An A/B test with a 50/50 split will keep sending half your traffic to the losing arm for the full duration, by design, because that is what gives it clean statistics and an unbiased estimate of the effect size. A bandit shifts traffic toward the winner as evidence accumulates, which earns more during the experiment and gives you a worse estimate of how much the loser lost by. Both are correct tools; they optimise different things.

The problem it solves

A ranking model trained on engagement predicts engagement from features that mostly encode past engagement: click-through rate, purchase count, popularity, embedding vectors learned from co-occurrence. For a new item all of those are zero or undefined. The model does what it was trained to do and ranks the item at the bottom. It gets no impressions, so it accumulates no signal, so it stays at the bottom. The item is not being judged badly; it is not being judged at all.

This has three consequences that show up in product metrics:

Supply-side churn. On any two-sided marketplace, a seller whose new listing gets no impressions in its first week concludes the platform does not work and leaves. Marketplaces track this explicitly as new-listing time-to-first-sale.
The catalog ossifies. The same winners keep winning, which is the popularity bias feedback loop with a specific cause. The system's estimate of a never-shown item never improves.
The training data degrades. Your logs contain feedback only on what you showed, so the next model is trained on an even narrower slice. This is the selection bias problem described in judgment collection, and exploration is the only general cure: it is what puts off-policy data in your logs.

That third point is the one most teams underweight. Exploration is not only about finding good new items, it is about keeping your training data honest. A system with zero exploration is training on its own output.

Mechanics

The formal setting

A multi-armed bandit: $K$ arms, each with an unknown reward distribution. At each step you pick an arm and observe a reward. Your objective is to minimise regret, the difference between what you earned and what you would have earned by always picking the best arm:

$$R(T) = T\mu^* - \sum_{t=1}^{T}\mu_{a_t}$$

The useful fact is that the achievable regret is $O(\log T)$, not $O(T)$: the cost of learning is logarithmic in the horizon, so exploration is cheap over a long run and expensive over a short one. That single fact tells you when bandits are worth it.

Epsilon-greedy

With probability $\varepsilon$ pick a random arm; otherwise pick the current best. Trivially simple, and a reasonable baseline.

def epsilon_greedy(counts, values, epsilon=0.1):
    if random.random() < epsilon:
        return random.randrange(len(values))     # explore uniformly
    return max(range(len(values)), key=lambda a: values[a])

Its defect is that it explores uniformly, spending as much on an arm it has already proven terrible as on one it is genuinely unsure about. Regret is linear unless you decay $\varepsilon$, and the decay schedule is another thing to tune.

UCB1: optimism in the face of uncertainty

Pick the arm with the highest upper confidence bound on its value:

$$\text{UCB}_a = \hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}}$$

The second term is a bonus that grows with total time $t$ and shrinks with the number of pulls $n_a$ of that arm. An arm that has been pulled rarely gets a large bonus, so it gets tried; an arm pulled often has a tight bound, so it is judged on its mean.

import math

def ucb1(counts, values, t):
    for a, n in enumerate(counts):
        if n == 0:
            return a                              # every arm at least once
    return max(range(len(values)),
               key=lambda a: values[a] + math.sqrt(2 * math.log(t) / counts[a]))

UCB1 has a proved $O(\log T)$ regret bound and no tuning parameter beyond the exploration constant. Its weakness in practice is that it is deterministic, which means every user in the same state sees the same arm, and it assumes rewards arrive immediately.

Thompson sampling: the one to actually use

Maintain a posterior over each arm's value; sample from each posterior; play the arm with the highest sample. For binary rewards (click or no click) the posterior is Beta and the update is one line.

import random

class ThompsonBandit:
    def __init__(self, k, prior_a=1.0, prior_b=1.0):
        self.alpha = [prior_a] * k     # successes + prior
        self.beta  = [prior_b] * k     # failures + prior

    def select(self):
        samples = [random.betavariate(self.alpha[a], self.beta[a])
                   for a in range(len(self.alpha))]
        return max(range(len(samples)), key=lambda a: samples[a])

    def update(self, arm, reward):     # reward in {0, 1}
        if reward:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

Three properties make this the default recommendation:

It is naturally randomised, so different users see different arms, which makes it usable in a ranking context and gives you the propensity randomness that IPS-based offline evaluation needs.
It handles delayed feedback gracefully. Because selection is a sample from a posterior rather than a deterministic argmax, arms with pending unobserved outcomes are not systematically over- or under-selected. UCB, being deterministic, can hammer one arm repeatedly while its rewards are still in flight.
The prior is a place to put your domain knowledge. This matters enormously for cold start and is covered below.

Chapelle and Li's empirical study found Thompson sampling matched or beat UCB on display advertising and news recommendation data, including under delayed feedback, which is the practical reason it dominates in industry despite UCB having the tidier theory.

Contextual bandits: where ranking actually lives

Plain bandits assume every arm has one true value. In ranking, an item's value depends on the query, the user and the context, so you need a contextual bandit: the reward is a function of a feature vector $x$ (query terms, user segment, device, hour) and the arm.

LinUCB models the reward as linear in the features and maintains a confidence ellipsoid per arm:

$$\text{score}_a(x) = x^\top \hat{\theta}_a + \alpha \sqrt{x^\top A_a^{-1} x}$$

with $A_a$ the accumulated feature covariance for arm $a$. The bonus is now large for feature directions that arm has not been tried in, not merely for arms with few pulls. That is the right generalisation: a listing may have 10,000 impressions on desktop and none on mobile, and a plain bandit cannot express that.

The production shortcut most teams take is simpler and works: run the existing ranking model to get a score, then use the bandit only over a small slot budget. Rank normally, and reserve one or two positions in the results for exploration items chosen by a bandit over the cold-start pool. This keeps the machine learning system you already have and confines the bandit to a bounded, auditable amount of traffic.

Solving cold start specifically: informative priors

The bandit machinery says nothing about where a new arm starts. That choice is the entire cold-start solution, and it is a modelling problem rather than a bandit problem.

A flat Beta(1,1) prior on a new item means "could be anything from 0 to 1 click-through," which is far too optimistic and wastes exploration. The right move is to set the prior from a content-based prediction: run the item's features (category, price, title embedding, seller reputation) through a model trained on mature items to predict its CTR, then set the prior mean to that prediction with a variance reflecting the model's uncertainty.

# Convert a predicted CTR and a confidence weight into Beta parameters.
# `strength` is the pseudo-count: how many impressions this prediction is worth.
def prior_from_content(pred_ctr, strength=50):
    return pred_ctr * strength, (1 - pred_ctr) * strength

A strength of 50 says "treat this prediction as worth 50 observed impressions." After 500 real impressions the prior is nearly washed out and the item is judged on its own behaviour. This is a hybrid recommender in bandit clothing: content features carry the item until behavioural signal takes over, and the pseudo-count is the explicit knob controlling the handover.

A worked example: an exploration budget on a listings marketplace

A marketplace has roughly 40,000 new listings per day and 12 million search result impressions per day. New listings were getting a median of 4 impressions in their first 48 hours; a third got zero. Seller complaints about "my listing is invisible" were the top support category from new sellers.

The design. Reserve position 5 of every search result page for an exploration slot on 100 percent of traffic. Fill it from listings under 7 days old that match the query above a relevance floor, chosen by Thompson sampling with a content-derived prior.

The cost, computed before building anything. Position 5 in this interface has a click-through rate of about 3.1 percent when filled by the ranker's own choice. Exploration items are a mix, and the pessimistic assumption was that they would convert at half the rate of the item they displaced, so the modelled loss was roughly 1.5 percent absolute CTR on one of ten positions:

$$\text{expected CTR loss} \approx \frac{0.031 - 0.0155}{\text{page CTR of } 0.183} \approx 8.5%\ \text{of one slot's contribution} \approx 0.8%\ \text{of page CTR}$$

Under 1 percent of page CTR was judged an acceptable price and, importantly, was stated up front as the budget so the result could be evaluated against it rather than argued about afterwards.

The prior. A gradient-boosted model trained on mature listings predicted CTR from category, price percentile within category, photo count, title length, and seller tenure. Held-out RMSE was 0.011 against a mean CTR of 0.029, so the model was informative but not precise, and strength was set to 30 pseudo-impressions.

Results after six weeks:

                                    before      after
new-listing median impressions       4          61        (48h window)
new listings with 0 impressions      33%        4%
overall page CTR                     0.183      0.181     (-1.1%, within budget)
new-seller 30-day retention          41%        49%
GMV from listings <14 days old       6.2%       11.8%

The overall CTR cost came in slightly above the modelled 0.8 percent at 1.1 percent, which is the kind of miss that matters: the pessimistic conversion assumption was roughly right and the displaced item was slightly better than assumed. The offsetting gains were larger than the cost, but note that they show up in different metrics, on a longer horizon, and to a different team's targets. A team measured only on page CTR would have correctly concluded this was a regression and reverted it.

That is the real lesson of the example and it is organisational rather than technical: exploration always costs the metric it is measured against and pays in a metric someone else owns. The design work is getting the second metric on the same dashboard before you launch, which is the same argument made on the popularity bias page.

Production evidence

Yahoo's news recommendation work (Li, Chu, Langford and Schapire, WWW 2010) is the canonical contextual bandit deployment: LinUCB on the Today module front page, with a published unbiased offline evaluation method using logged data from a randomised-serving bucket. That randomised bucket is the enabling detail, and their reported 12.5 percent CTR lift over a context-free baseline is one of the few industrial bandit numbers with a paper behind it.

Netflix's artwork selection uses contextual bandits to choose which image to show for a title per member, described in their "Artwork Personalization at Netflix" post. They document the closed-loop hazard explicitly: because the bandit chooses what is shown, the logged data is not a random sample, so their offline replay evaluation depends on recorded propensities.

Spotify has published on bandits for playlist and shelf ordering in the home feed, including the counterfactual evaluation infrastructure needed to make offline decisions from bandit-logged data.

Etsy, Airbnb and Uber Eats have each described exploration budgets for new-supply cold start on marketplaces, and the common pattern across all three is the one used in the worked example: a bounded number of slots rather than a global policy change, because a bounded slot budget makes the cost calculable in advance and the change revertible.

Microsoft's Vowpal Wabbit ships production contextual bandit learners with the exploration and counterfactual-evaluation tooling built in, and the associated "Decision Service" paper describes the full loop (explore, log with propensities, learn, deploy) as an operated system rather than an algorithm.

The debate

Bandits versus A/B tests. Bandits win when the arms are many, short-lived, and individually low-stakes: which of 2,000 thumbnails, which of 40,000 new listings. Running an A/B test per thumbnail is absurd. A/B tests win when you need a defensible effect size for a decision that is expensive to reverse, when the metric is delayed or long-horizon (retention, LTV), and when the change is a genuine product decision rather than an item selection. My position: bandits for item selection, A/B tests for policy changes, including for the change that introduces the bandit. The bandit itself should be launched as an A/B test.

How much to explore. The honest answer has variables. Explore more when the catalog turns over fast (news, marketplaces, short-form video), when the supply side is a customer you can lose, and when your training data is visibly narrow. Explore less when items are long-lived and expensive to evaluate, when traffic is thin enough that exploration will not converge before the item is stale, and when the cost of a bad impression is high (a bad ad on a sensitive page, a bad result in a legal or medical search). A concrete default: one slot in ten, on 100 percent of traffic, capped by a relevance floor. Committing to a number and a floor is better than an adaptive scheme nobody can reason about.

When bandits are the wrong tool entirely. If traffic per item is low enough that an item cannot accumulate a meaningful posterior before it goes stale, the bandit never gets to the exploit phase and you have implemented an expensive random sampler. The arithmetic: to distinguish a 3 percent CTR from a 2 percent CTR with any confidence you need on the order of a few thousand impressions per item. If your item turnover means a listing sees 200 impressions in its life, use a content model and skip the bandit, because the behavioural signal will never arrive. This is the most common way bandit projects fail and it is detectable with a back-of-envelope calculation before any code is written.

A serious hazard worth stating. A bandit optimising a short-horizon reward will find the clickbait. CTR-maximising bandits on content surfaces reliably drift toward sensational thumbnails and titles, because that is the maximum of the objective they were given. The mitigations are a longer-horizon reward (completion, next-day return, purchase rather than click) and a quality floor as a hard constraint outside the bandit. Do not rely on the bandit to balance this; give it an objective whose maximum you would be happy with.

Follow-up Q&A

"Why Thompson sampling over UCB?"

Three reasons, in order of practical importance. First, delayed feedback: real rewards arrive minutes to days later, and UCB's deterministic argmax will select the same arm repeatedly during the delay window because nothing has updated, while Thompson's sampling naturally spreads selections. Second, randomisation: Thompson gives different users different arms, which both avoids a uniform experience and produces the propensity variation that unbiased offline evaluation needs. Third, priors: the Beta prior is exactly where a content-based CTR prediction belongs, which is the cold-start solution. Chapelle and Li's empirical comparison supports it on display advertising and news data.

"How do you evaluate a bandit offline?"

Replay with importance weighting, and it requires that you logged the selection propensity at serving time. For each logged event where the bandit chose arm $a$ with probability $p_a$, and your candidate policy would have chosen $a'$, you can only use the event if $a = a'$, and you weight it by $1/p_a$. This is why logging the propensity is a hard requirement rather than a nice-to-have: if you did not log it, the data is unusable for counterfactual evaluation and you are reduced to online testing for every change. Li et al.'s WWW 2010 paper gives the unbiased replay estimator; the practical catch is high variance when propensities get small, handled by clipping the weights and accepting a small bias.

"How does a bandit interact with a learning-to-rank model?"

Do not try to make the LTR model itself a bandit; that path leads to a system nobody can debug. The clean composition is: LTR produces a relevance score and a ranked list, a filter takes cold-start-eligible items above a relevance floor, and the bandit chooses among those for a fixed slot budget. The bandit's exploration also feeds the LTR model's next training set with off-policy data, which is the compounding benefit. Two systems, one interface, each independently testable.

"What about user cold start, as opposed to item?"

Different problem, mostly not a bandit problem. The tools are: context you have without history (query text, geography, device, referrer, time of day), popularity priors segmented by whatever you do know, an onboarding flow that collects explicit preferences, and rapid within-session adaptation, which is usually the highest value because a logged-out user gives you three or four signals in the first minute that outweigh any demographic prior. A bandit over user segments can help decide which onboarding variant to show, but the core of user cold start is feature engineering, not exploration.

"You have 40,000 new items a day and 12 million impressions. Do the numbers work?"

That is the calculation I would insist on doing first. One slot in ten of 12 million impressions is 1.2 million exploration impressions per day against 40,000 new items, so roughly 30 impressions per item per day, 210 in a week. At a 3 percent CTR that is about 6 clicks, which is enough to distinguish a terrible item from an average one but not enough to distinguish average from good. So the design should promote items out of exploration on a coarse signal (is this clearly below floor) rather than trying to estimate a precise CTR, and the fine ranking should come from the main model once the item has accumulated real traffic. If the numbers had come out at 3 impressions per item, I would have built a content model and no bandit.

Common misconceptions

"Exploration is free because those impressions were low value anyway." Every exploration impression displaces the item the ranker wanted to show, and that item had the highest expected value by construction. The cost is real, computable in advance, and should be stated as a budget before launch. Teams that describe exploration as free have not measured it.

"A bandit will find the best item." It will find the item that maximises the reward you defined, over the horizon you gave it. If the reward is a click, it finds what gets clicked. Bandits are extremely literal, and the gap between "the metric" and "what we want" is where the damage happens.

"Epsilon-greedy is fine, the algorithm barely matters." The algorithm matters less than the prior and the reward definition, which is true and is why this page spends more space on priors. But epsilon-greedy specifically wastes exploration uniformly on arms already known to be bad, and switching to Thompson sampling is about fifteen lines of code, so there is no reason to accept the waste.

"Cold start is solved by content-based recommendation." Content features give you a prior, not a solution. They tell you what similar items achieved, and the whole reason a new item is interesting is that it might not behave like similar items. Content gets you a defensible starting position; exploration is what corrects it.

"We can add exploration later." Adding it later means every model you train until then is fitted on your own ranker's output, and the resulting narrowness is baked into the embeddings and the feature distributions. Exploration is cheapest to introduce early, when the catalog is small and the cost of a suboptimal impression is low.

Interview delivery note

The sentence to have ready: "An item with no impressions has no signal, and a model trained on engagement will rank it last forever, so I treat exploration as a budgeted line item: one slot in ten, priced in advance as expected CTR loss, with the prior set from a content model so we are not exploring blind." It contains the diagnosis, the mechanism, the cost discipline and the cold-start-specific fix in one breath.

The senior-versus-staff separator is doing the impressions-per-item arithmetic unprompted. A senior engineer names Thompson sampling and explains the Beta posterior. A staff engineer divides the exploration budget by the number of new items, gets 30 impressions per item per day, and concludes that this is enough to detect a disaster and not enough to rank finely, then designs to that constraint. That calculation is what separates a bandit that works from a bandit that is a random sampler with extra steps.

The second staff signal is naming the organisational problem: exploration costs the metric you are measured on and pays in a metric someone else owns. Saying "before launching this I would get new-seller retention and new-listing GMV onto the search team's own dashboard" shows you have shipped something like this rather than read about it.

The Staff & Team Lead Interview Reference