Description
Multi-arm bandit with Thompson Sampling: Beta-Bernoulli posteriors, regret minimization, convergence criteria.
A/B tests have a fixed hypothesis and duration. Multi-arm bandits continuously allocate traffic to better-performing variants, minimizing regret while converging to the best option. Thompson Sampling is the most practical bandit algorithm — simple to implement, no free parameters, and provably optimal. STEP 1 — SETUP Variants: A (control), B, C, ... (up to 10 before statistical noise dominates). Reward: binary (click, conversion, purchase) or continuous (revenue, time-spent, latency). Normalize continuous rewards to [0,1] or use a Gaussian prior. Decision frequency: every N observations (N=100 for high-traffic, N=10 for low-traffic). Too-frequent decisions increase variance without faster convergence. STEP 2 — THOMPSON SAMPLING (Beta-Bernoulli for binary rewards) Each variant maintains a Beta posterior: Beta(α = prior_pseudo_successes + observed_successes, β = prior_pseudo_failures + observed_failures). - Prior: Beta(1,1) = uniform (no prior knowledge). Beta(α_historical, β_historical) for informed priors from historical data. - At each decision point: sample from each variant's Beta distribution. Pick the variant with the highest sample. This automatically balances exploration (samples from uncertain distributions are more spread out) and exploitation (distributions with higher means produce higher samples on average). STEP 3 — REGRET MINIMIZATION Regret = reward lost by not always picking the best variant. Thompson Sampling minimizes cumulative regret asymptotically. In practice, regret is <5% of the maximum possible gain after the first 1000 samples per variant. STEP 4 — CONVERGENCE CHECK - After N observations per variant, compute the probability that each variant is optimal: P(β_i > max(β_j for j≠i)). - Stop when the leading variant's P(optimal) > 0.95 and its expected reward exceeds the runner-up by at least the minimum detectable effect (MDE). - If no variant reaches 0.95 after N=10,000 per variant, declare the differences practically insignificant and pick the simplest variant (usually control). STEP 5 — IMPLEMENTATION ```python import numpy as np def thompson_sample(betas): # betas: list of (alpha, beta) tuples per variant samples = [np.random.beta(a, b) for a, b in betas] return int(np.argmax(samples)) def update_beta(betas, chosen_idx, reward): a, b = betas[chosen_idx] betas[chosen_idx] = (a + reward, b + 1 - reward) return betas ``` STEP 6 — PITFALLS - Delayed feedback: if reward is not observable for 24 hours, use a grace period before updating the posterior. - Non-stationary reward: if user behavior changes seasonally, use a sliding window (last N=5000 observations) or a decay factor (halve pseudo-counts every 2 weeks). - Simpson's paradox: segment by traffic source and run separate bandits per segment. OUTPUT: Setup parameters, Thompson Sampling implementation, convergence criteria, pitfalls checklist.
No comments yet. Be the first!