P5MediumPart P · MLE Production Engineering & Calibration

Beta-Bernoulli Thompson Sampling for Cold-Start & Routing

⚡Flashcard Drill➔

Implement conjugate Beta-Bernoulli Thompson Sampling to balance uncertainty exploration and exploitation in RecSys cold-start and model routing.

⏱️ Time: O(T * K)
💾 Space: O(K)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def thompson_sampling_sim(true_ctrs: np.ndarray, rounds: int = 1000, seed: int = 7) -> dict:
rng =
k = len(true_ctrs)
alpha = np.ones(k, dtype=np.float64)
beta = np.ones(k, dtype=np.float64)
pulls = np.zeros(k, dtype=np.int64)
total_reward = 0
for _ in range(rounds):
sampled = rng.beta(alpha, beta)
arm = int(np.argmax(sampled))
reward = int(rng.random() < true_ctrs[arm])
pulls[arm] += 1
total_reward += reward
alpha[arm] += reward
beta[arm] += (1 - reward)
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What goes wrong with naive Bandits under delayed conversions?
Q2: How do you extend Thompson Sampling when user context matters?
Next: Platt Scaling & Expected Calibration Error (ECE) for Ads pCTR →
💡

Core Mental Anchor / Mnemonic

Sample from conjugate Beta posterior; wide variance drives natural exploration

📐 Mathematical Derivation & Core Formula

$$\theta_a \sim \text{Beta}(\alpha_0 + S_a,\; \beta_0 + F_a),\quad a^* = \arg\max_a \theta_a$$
Drawing θa∼Beta(αa,βa)\theta_a \sim \text{Beta}(\alpha_a, \beta_a) implicitly explores uncertain new arms whose posteriors have wide variance, naturally shifting traffic to the optimal arm at optimal O(log⁡T)O(\log T) regret without manual epsilon schedules.

🔄 Tensor Dimensions & Shape Flow

alpha, beta: (K,) -> Beta sample -> argmax arm -> conjugate update

🛡️ Numerical Stability & Pitfalls Checklist

  • Apply exponential decay gamma < 1 to alpha/beta when click preferences shift over time
  • Handle delayed conversions carefully so unattributed clicks do not permanently starve true winners
  • Aggregate updates in micro-batches under high QPS to avoid lock contention

💻 Reference Code Implementation

import numpy as np

def thompson_sampling_sim(true_ctrs: np.ndarray, rounds: int = 1000, seed: int = 7) -> dict:
    rng = np.random.default_rng(seed)
    k = len(true_ctrs)
    alpha = np.ones(k, dtype=np.float64)
    beta = np.ones(k, dtype=np.float64)
    pulls = np.zeros(k, dtype=np.int64)
    total_reward = 0
    for _ in range(rounds):
        sampled = rng.beta(alpha, beta)
        arm = int(np.argmax(sampled))
        reward = int(rng.random() < true_ctrs[arm])
        pulls[arm] += 1
        total_reward += reward
        alpha[arm] += reward
        beta[arm] += (1 - reward)
    return {"pulls": pulls.tolist(), "best_arm_picked": int(np.argmax(pulls)), "total_reward": total_reward}

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

res = thompson_sampling_sim(np.array([0.05, 0.12, 0.35, 0.18]), rounds=800, seed=42)
assert res['best_arm_picked'] == 2
assert res['pulls'][2] > sum(res['pulls']) * 0.65
print('P5 PASS')

🎯 Core Follow-up Inquiries & Reference Answers

Q1:What goes wrong with naive Bandits under delayed conversions?
Unconverted impressions look like failures immediately after serving, prematurely suppressing high-value items whose conversions arrive hours later.
Q2:How do you extend Thompson Sampling when user context matters?
Use Contextual Bandits such as LinUCB / Linear Thompson Sampling with a Bayesian ridge regression posterior over context features.
⚡
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➔
← Prev: Idempotent CDC Incremental Vector Sync PlannerBack to Part P & All 105Next: Platt Scaling & Expected Calibration Error (ECE) for Ads pCTR →