Bandits in Recommendation Systems

Cold start, exploration bonus in ranking, batched bandits, delayed feedback, cascaded exploration

Pure exploitation recommendation systems have a fundamental self-fulfilling problem: items that were never shown cannot accumulate the impressions needed to estimate their quality, so they are never shown. Popular items stay popular not because they are always the best choice but because they received the most data. New items, niche items, and items that would suit specific user segments never get discovered. This is the filter bubble — not a philosophical concern but a measurable system failure: catalog coverage collapses, long-tail content atrophies, and users see an increasingly narrow slice of what is available.

Bandit exploration in recommendation systems must confront engineering realities that pure bandit theory ignores: batched updates (not per-interaction), delayed feedback (clicks arrive seconds to days after impressions), and cascade position bias (users scan top-to-bottom, so items at higher positions get more examination regardless of quality). The practical answer is to dedicate a fixed exploration budget and use content-based priors to warm-start new items rather than starting from scratch.

Key points

• Cold start is a bandit exploration problem. New items score near zero in collaborative filtering because they have no interaction history — so they are not shown — so they accumulate no history. This circular dependency is broken by assigning new items a forced exploration budget (e.g., 1000 impressions) with a UCB-style uncertainty bonus that decays as impressions accumulate. Without this, new items never escape the cold start.
• Exploration bonus in ranking: score(item) = predicted_reward(item) + α · uncertainty(item). Uncertainty can be content-based (new item → high uncertainty regardless of user), user-item (item rarely shown to this user type → high uncertainty for this user), or model-based (variance of ensemble predictions). α is tuned to balance short-term CTR against long-term catalog coverage and user satisfaction.
• Exploration operates at multiple levels simultaneously: item level (which item to recommend), user level (new users need diverse items to reveal preferences, not just the global popular items), and context level (new device types, new usage patterns, and new demographics require exploration of whether preference patterns differ).
• Delayed feedback breaks the assumption of immediate reward. Clicks arrive seconds to hours after the recommendation event; purchase or subscription conversion may arrive days later. The bandit cannot update until reward arrives. Solutions: optimistic reward imputation (assign unobserved rewards an optimistic value, correct when reward arrives), delayed update (buffer (context, arm) pairs and update when reward arrives), or reward shaping (use fast proxy rewards like scroll time as surrogates for slow rewards like purchase).
• Batched bandits: production systems update model parameters in batches (hourly, daily), not per-interaction. All rounds in a batch use the same policy parameters. Regret degrades by O(√batch_size) versus online updates — acceptable for large T. The practical approach: compute UCB or TS posterior at batch start using all previous statistics; let the entire batch run on that fixed policy; update at batch end.
• Cascade position bias: users scan a ranked list top-to-bottom and click the first satisfying item. Items at position 1 receive far more examination probability than items at position 5. A raw CTR of 2% at position 5 may be better item quality than 5% at position 1. Exploration of lower-ranked items is masked by cascade stopping — items below the first click are never examined. Solution: occasionally promote uncertain items to high positions (exploration slots) and use position-debiased reward models to attribute CTR to item quality rather than position.
• Blending bandits with neural rankers: retrieval (ANN top-K candidates) → neural ranker (P(click|user, item, context)) → bandit exploration layer (adjust neural scores with exploration bonus). Key tension: if the bandit layer causes distribution shift, the next neural ranker retraining sees biased data — popular items get more training signal, unexplored items get less. Fix: train the neural ranker with importance weighting (DR estimator) on the logged data so that exploration traffic does not bias the feature representation.
• Measuring exploration quality separately from exploitation quality: online CTR measures exploitation. Item discovery rate (fraction of catalog items receiving ≥ N impressions per day) and impression distribution entropy measure exploration. Short-term CTR is not the right optimisation target — a 0.1% CTR reduction from exploration may be acceptable if it improves long-term retention and prevents catalog collapse.
• Exploration budget: dedicate X% of traffic (e.g., 5%) to exploration, run pure exploitation on the rest. This makes exploration operationally transparent and auditable. Vary the budget by user segment (new users get more, since their preferences are unknown), item segment (new items get more, since their quality is unknown), and time of day (low-traffic periods can absorb more exploration risk).

Recap

• Filter bubble: items never shown accumulate no data, so they're never shown — catalog coverage collapses.
• Cold start = exploration problem: give new items a forced impression budget with a decaying uncertainty bonus and content-based priors.
• Exploration bonus in ranking: score = predicted_reward + α·uncertainty, at item / user / context levels.
• Delayed feedback: clicks arrive seconds to days later — buffer (context, arm), impute optimistically, or use fast proxy rewards.
• Batched bandits: update hourly/daily on fixed policy; regret degrades only O(√batch_size).
• Cascade position bias: users scan top-down; raw CTR conflates quality with position — use position-debiased rewards.
• Measure exploration separately: catalog discovery rate and impression entropy, not just short-term CTR.

Check your understanding