P5MediumPart P · MLE Production Engineering & Calibration
Beta-Bernoulli Thompson Sampling for Cold-Start & Routing
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?
💡
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 implicitly explores uncertain new arms whose posteriors have wide variance, naturally shifting traffic to the optimal arm at optimal 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.