Thompson Sampling

Thompson Sampling operates by probability matching—the probability of selecting an action equals the probability that the action is optimal given the posterior distribution. For each decision point, the algorithm draws a single sample from the posterior distribution of each arm's expected reward and selects the arm with the highest sampled value. This stochastic selection ensures that arms with high uncertainty but promising potential are explored proportionally to their chance of being the best, while arms with high certainty of being suboptimal are naturally suppressed.

The algorithm maintains a posterior distribution over each action's reward parameter, updated via Bayes' theorem after every observation. For binary rewards, a Beta distribution serves as the conjugate prior:

• Prior: Beta(α, β) representing initial beliefs
• Update: After observing a success, α → α + 1; after a failure, β → β + 1
• Result: The distribution narrows with more data, reflecting increased certainty This Bayesian framework naturally encodes uncertainty, making it ideal for cold-start items where the posterior remains wide, encouraging exploration.

Thompson Sampling achieves logarithmic regret in stationary environments, meaning the cumulative difference between the algorithm's performance and the optimal policy grows only logarithmically over time. Key regret characteristics:

• Lai-Robbins lower bound: Thompson Sampling asymptotically matches the theoretical lower bound for regret in multi-armed bandits
• Empirical performance: Often outperforms UCB and ε-greedy in practice, especially in the finite horizon
• Non-stationary adaptation: With appropriate forgetting mechanisms, it can track changing reward distributions This makes it particularly effective for dynamic retail environments where consumer preferences shift.

Contextual Thompson Sampling extends the algorithm to incorporate side information about users and items. Instead of maintaining independent per-arm distributions, it models expected rewards as a function of context features:

• Linear contextual bandits: Reward = θᵀx + ε, where θ has a multivariate Gaussian posterior
• Logistic contextual bandits: For binary outcomes, using a Bayesian logistic regression with Laplace approximation
• Neural contextual bandits: Using Bayesian neural networks with Monte Carlo dropout for uncertainty estimation This enables cold-start mitigation by allowing the model to generalize from similar items or users based on their feature representations.

Deploying Thompson Sampling in production requires addressing several engineering challenges:

• Prior specification: Weakly informative priors (e.g., Beta(1,1)) for cold-start items to ensure initial exploration
• Batch updating: Accumulating feedback and performing posterior updates in mini-batches to reduce computational overhead
• Delayed feedback: Handling the gap between action selection and reward observation using partial feedback models
• Scalability: For large action spaces, maintaining millions of Beta distributions is memory-efficient; each arm requires only two floating-point parameters (α, β)
• Non-binary rewards: Extending to Gaussian rewards with Normal-Inverse-Gamma conjugate priors or to multinomial outcomes with Dirichlet distributions

Thompson Sampling distinguishes itself from other exploration strategies:

• vs. ε-greedy: ε-greedy explores uniformly at random with fixed probability ε, wasting exploration on clearly suboptimal arms. Thompson Sampling directs exploration toward arms with high uncertainty and potential
• vs. UCB: Upper Confidence Bound algorithms use optimistic point estimates with deterministic confidence intervals. Thompson Sampling's stochastic sampling often provides better finite-sample performance and handles complex posterior shapes more naturally
• vs. Boltzmann exploration: Softmax exploration uses a temperature parameter to control exploration, requiring careful tuning. Thompson Sampling is parameter-free beyond the prior specification
• Key advantage: Thompson Sampling is the oldest bandit algorithm (proposed in 1933) yet remains state-of-the-art due to its elegant Bayesian foundation and strong empirical results