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
Next: M7-074 →
📐 Mathematical Definition
UCB: μ^i+cln⁡tni;TS: θi∼posterior, arg⁡max⁡iθi\text{UCB}:\ \hat\mu_i+c\sqrt{\frac{\ln t}{n_i}};\qquad \text{TS}:\ \theta_i\sim\text{posterior},\ \arg\max_i\theta_i
⚡ 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 μ^k=SkNk\hat{\mu}_k = \frac{S_k}{N_k} be the sample average reward of arm kk. Policy:
at={arg⁡max⁡kμ^kwith probability 1−ϵUniform Random({1,…,K})with probability ϵa_t = \begin{cases} \arg\max_k \hat{\mu}_k & \text{with probability } 1 - \epsilon \\ \text{Uniform Random}(\{1, \dots, K\}) & \text{with probability } \epsilon \end{cases}
Theoretical Regret: Cumulative regret scales linearly: R(T)=O(ϵTΔ)R(T) = O(\epsilon T \Delta). If ϵ\epsilon decays as ϵt=min⁡(1,cK/d2t)\epsilon_t = \min(1, cK / d^2 t), regret achieves O(ln⁡T)O(\ln T), but tuning decay parameters c,dc, d 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 ≥1−t−4\ge 1 - t^{-4}:
UCBk(t)=μ^k+2ln⁡tNk(t)\text{UCB}_k(t) = \hat{\mu}_k + \sqrt{\frac{2 \ln t}{N_k(t)}}at=arg⁡max⁡k(μ^k+c⋅2ln⁡tNk(t))a_t = \arg\max_k \left( \hat{\mu}_k + c \cdot \sqrt{\frac{2 \ln t}{N_k(t)}} \right)
- Theoretical Regret: Strictly bounded logarithmically: R(T)≤8∑k:Δk>0ln⁡TΔk+O(1)=O(ln⁡T)R(T) \le 8 \sum_{k : \Delta_k > 0} \frac{\ln T}{\Delta_k} + O(1) = O(\ln T).
- Limitation: Assumes bounded rewards (r∈[0,1]r \in [0, 1]), deterministic policy (cannot sample diverse slates), and requires tuning hyperparameter cc.

(3) Thompson Sampling (Posterior Sampling):
For binary click rewards (r∈{0,1}r \in \{0, 1\}), assumes conjugate prior θk∼Beta(αk,βk)\theta_k \sim \text{Beta}(\alpha_k, \beta_k) initialized to Beta(1,1)\text{Beta}(1, 1):
- At each round tt, sample realization θ~k∼Beta(αk,βk)\tilde{\theta}_k \sim \text{Beta}(\alpha_k, \beta_k) for all k∈[1,K]k \in [1, K].
- Select arm with highest sampled probability: at=arg⁡max⁡kθ~ka_t = \arg\max_k \tilde{\theta}_k.
- Observe reward rt∈{0,1}r_t \in \{0, 1\}, update posterior parameters:
αat←αat+rt,βat←βat+(1−rt)\alpha_{a_t} \leftarrow \alpha_{a_t} + r_t, \quad \beta_{a_t} \leftarrow \beta_{a_t} + (1 - r_t)
- Theoretical Regret: Matches the asymptotic lower bound of Lai & Robbins: R(T)≤(1+ϵ)∑kln⁡TDKL(μk∥μ∗)=O(ln⁡T)R(T) \le (1 + \epsilon) \sum_{k} \frac{\ln T}{D_{\text{KL}}(\mu_k \parallel \mu^*)} = O(\ln T).

🏭 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 rtr_t arrives 2 hours after impression; UCB stalls or over-samples because NkN_k increments while μ^k\hat{\mu}_k 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: αk←γαk+rt, βk←γβk+(1−rt)\alpha_k \leftarrow \gamma \alpha_k + r_t, \, \beta_k \leftarrow \gamma \beta_k + (1-r_t) with discount factor γ∈[0.95,0.999]\gamma \in [0.95, 0.999]. ⑤ Contextual expansion (LinUCB vs. LinTS)—when contextual features xx (user demographics) are present, bandits must condition on xx; 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. O(log⁡T)O(\log T)), 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.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM7-072: Explain Content-Based and Side-Information Approaches for Cold-Start Recommendation📋 Back to BankNext →M7-074: Explain Re-Ranking and Diversity Strategies to Protect and Elevate Long-Tail Content