Thompson Sampling

Thompson Sampling is a Bayesian approach to the exploration-exploitation tradeoff in bandit and decision-making problems. It selects actions by sampling from the posterior distribution of expected rewards, naturally balancing the desire to exploit known-good options with the need to explore uncertain ones.

How Thompson Sampling Works

• Maintain Beliefs: For each action (arm), maintain a posterior distribution over its expected reward, updated as observations accumulate.
• Sample: Draw a random sample from each action's posterior distribution.
• Act: Select the action whose sample is highest.
• Observe: See the actual reward and update the posterior distribution for the chosen action.

Why It Works

• Natural Exploration: Actions with high uncertainty have wide posterior distributions — they occasionally produce high samples, ensuring they get explored.
• Automatic Exploitation: As evidence accumulates, posteriors become narrow and centered on the true reward — the best action gets selected most often.
• Probability Matching: Thompson Sampling selects each action with probability approximately equal to the probability that it is the best action.

Mathematical Basis (Beta-Bernoulli Case)

• For binary rewards (click/no-click), maintain a Beta distribution $\text{Beta}(\alpha, \beta)$ for each action.
• $\alpha$ = number of successes + 1, $\beta$ = number of failures + 1.
• Sample $\theta \sim \text{Beta}(\alpha, \beta)$ for each action, pick the highest.
• After observing reward: success → increment $\alpha$; failure → increment $\beta$.

Advantages

• Simple Implementation: Just sample from posteriors and pick the max — no complex optimization.
• Strong Theoretical Guarantees: Near-optimal regret bounds, competitive with UCB.
• Handles Non-Stationarity: Naturally adapts when reward distributions change over time.
• Flexible: Works with any reward distribution, not just Bernoulli.

Applications

• A/B Testing: Adaptive experiment allocation — automatically send more traffic to the winning variant.
• Recommendation: Select content that balances showing popular items with exploring new ones.
• LLM Prompt Selection: Choose among prompt templates based on observed response quality.
• Hyperparameter Tuning: Bayesian optimization of hyperparameters.

Thompson Sampling is often the recommended default for exploration-exploitation problems due to its simplicity, strong performance, and elegant theoretical foundation.