How would you implement a multi-armed bandit for real-time ad optimization?

What's really being asked

This question evaluates whether you can translate a theoretical reinforcement learning problem into a scalable production architecture. Interviewers care about your grasp of the exploration versus exploitation trade-off, your ability to separate online inference from offline learning, and your awareness of operational realities like delayed feedback, non-stationary click-through rates, and distributed state management.

The full answer

First, algorithm selection. Name Thompson Sampling with Beta priors for binary click rewards or UCB1 for frequentist confidence bounds. Second, system architecture. Sketch a low-latency ad server that fetches arm distributions from Redis or a feature store, samples an arm in single-digit milliseconds, and logs the impression. Third, feedback loop. Show an async stream processor, perhaps Kafka to Flink, that consumes click events, updates the posterior parameters or empirical means, and writes back to the store. Fourth, exploration handling. Explain that Thompson Sampling naturally explores by drawing from the posterior, while UCB1 adds an explicit confidence bonus. Fifth, scaling and robustness. Mention sharding by user segment or campaign, handling delayed clicks with attribution windows, using uniform priors for cold-start arms, and decaying old data when ad fatigue makes rewards non-stationary.

The mistakes people make

Proposing a pure epsilon-greedy strategy without discussing why it wastes regret on obviously inferior arms. Ignoring the engineering split between synchronous serving and asynchronous learning, which would add tens of milliseconds to every ad request. Failing to address delayed feedback, meaning clicks arrive minutes after impressions and can temporarily skew reward estimates. Treating the problem as a static A/B test with occasional randomization rather than a continuous online learning loop.

What usually comes next

How do you handle non-stationarity when an ad's click-through rate decays over time? What happens if your state store fails and the serving tier loses all posterior parameters? How do you prevent a new arm from starving due to low initial samples? Can you extend this to contextual bandits using user features?

A concrete example

Imagine three ad copy variants for a sneaker campaign. Variant A has a Beta(50, 950) posterior after 1,000 impressions, variant B is Beta(5, 95), and variant C is a new arm at Beta(1, 1). At serving time, Thompson Sampling draws a random value from each Beta distribution. A usually wins because its mean is highest, but B occasionally wins when it draws above its mean, and C wins rarely because its prior is wide. When a user clicks, the async pipeline increments the alpha parameter for that variant. Over a day serving ten million requests, the system automatically shifts traffic toward A while still giving B and C enough impressions to prove whether they are actually better.