M7-073M7: Retrieval, Ranking & RecSysCold Start & Long-Tail DistributionHard
⚡Flashcard Drill➔Mastery:
Compare Multi-Armed Bandit Algorithms in Production: Epsilon-Greedy, UCB, and Thompson Sampling
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
Epsilon-greedy explores uniformly at random with linear regret, UCB explores deterministically via upper confidence bounds with O(log T) regret, and Thompson Sampling samples from Bayesian posteriors, providing the premier empirical performance in production.
📌 Key Takeaways
- •Epsilon-greedy simplicity vs. blind exploration: Easy to implement, but explores uniformly across all arms regardless of how poorly they have performed.
- •Upper Confidence Bound (UCB): Deterministic optimism under uncertainty; prioritizes arms with either high empirical mean or high variance.
- •Thompson Sampling (Bayesian): Probability matching; samples parameters from posterior distributions, offering superior empirical regret and natural handling of delayed feedback.
📐 Mathematical Derivations
Mathematical & Algorithmic Formulation: Multi-Armed Bandit Comparison.
(1) $\epsilon$-Greedy Algorithm:
Let be the sample average reward of arm . Policy:
Theoretical Regret: Cumulative regret scales linearly: . If decays as , regret achieves , but tuning decay parameters in production is brittle.
(2) Upper Confidence Bound (UCB1):
Applies Hoeffding's Inequality to construct an upper confidence bound containing the true mean with probability :
- Theoretical Regret: Strictly bounded logarithmically: .
- Limitation: Assumes bounded rewards (), deterministic policy (cannot sample diverse slates), and requires tuning hyperparameter .
(3) Thompson Sampling (Posterior Sampling):
For binary click rewards (), assumes conjugate prior initialized to :
- At each round , sample realization for all .
- Select arm with highest sampled probability: .
- Observe reward , update posterior parameters:
- Theoretical Regret: Matches the asymptotic lower bound of Lai & Robbins: .
(1) $\epsilon$-Greedy Algorithm:
Let be the sample average reward of arm . Policy:
Theoretical Regret: Cumulative regret scales linearly: . If decays as , regret achieves , but tuning decay parameters in production is brittle.
(2) Upper Confidence Bound (UCB1):
Applies Hoeffding's Inequality to construct an upper confidence bound containing the true mean with probability :
- Theoretical Regret: Strictly bounded logarithmically: .
- Limitation: Assumes bounded rewards (), deterministic policy (cannot sample diverse slates), and requires tuning hyperparameter .
(3) Thompson Sampling (Posterior Sampling):
For binary click rewards (), assumes conjugate prior initialized to :
- At each round , sample realization for all .
- Select arm with highest sampled probability: .
- Observe reward , update posterior parameters:
- Theoretical Regret: Matches the asymptotic lower bound of Lai & Robbins: .
🏭 Production Trade-offs
In-Depth Analysis & Engineering Trade-offs: ① Why Thompson Sampling beats UCB in production—UCB is deterministic and conservative, frequently over-exploring mediocre arms until their confidence intervals shrink; Thompson Sampling naturally explores proportional to the probability that an arm is truly optimal; across empirical benchmarks, Thompson Sampling achieves 30–50% lower cumulative regret. ② Handling delayed feedback—in real-world e-commerce, user conversion arrives 2 hours after impression; UCB stalls or over-samples because increments while remains zero; Thompson Sampling easily accommodates batch posterior updates via asynchronous queuing. ③ Batch serving & slate recommendation—recommending a slate of 10 items at once: Thompson Sampling naturally generates a diverse slate by simply drawing 10 independent samples from the joint posteriors; UCB produces identical items unless forced through artificial penalization. ④ Non-stationary environments (Drifting preferences)—user tastes drift over time; classic bandits assume static arm reward distributions; production systems employ Discounted Thompson Sampling or Sliding-Window Bandits: with discount factor . ⑤ Contextual expansion (LinUCB vs. LinTS)—when contextual features (user demographics) are present, bandits must condition on ; LinUCB and Linear Thompson Sampling scale to contextual personalization via Bayesian linear regression. ⑥ Interview takeaway—compare the three algorithms across exploration style (random vs. deterministic bound vs. Bayesian sampling), regret bounds (linear vs. ), detail Thompson Sampling's Beta-Binomial update loop, and explain why Thompson Sampling dominates production slate recommendation.
⚠️ Common Interview Pitfalls
- ✕Using standard UCB in delayed-feedback conversion settings, causing severe over-exploration of un-converted items before conversion attribution completes.
- ✕Using static epsilon-greedy without decaying epsilon, accumulating continuous linear regret and degrading long-term platform revenue.
- ✕Failing to incorporate a decay factor (gamma) in non-stationary production environments, allowing stale historical counts to prevent adaptation to new trends.
🎯 Interviewer Follow-up Inquiries
- ?Why does Thompson Sampling naturally support slate recommendation (generating top-k distinct items) while UCB requires ad-hoc penalties?
- ?How does Discounted Thompson Sampling adapt to non-stationary click distributions where item popularity decays over time?
- ?What is the mathematical formulation of Linear Thompson Sampling (LinTS) for contextual recommendation?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚