Thompson Sampling

The core mechanism of Thompson Sampling is maintaining a posterior probability distribution over each arm's unknown reward parameter. At each decision step, the algorithm draws a random sample from each arm's posterior and selects the arm with the highest sampled value. This means arms with high uncertainty have a chance to produce high samples, driving exploration. As more data is collected, the posterior distributions narrow, reducing exploration naturally. For Bernoulli bandits, this typically uses a Beta distribution as the conjugate prior, updated with observed successes and failures. The elegance lies in the fact that the probability an arm is selected exactly equals the probability it is optimal given current knowledge.

Unlike Epsilon-Greedy, which requires manual tuning of the exploration rate ε, or Upper Confidence Bound (UCB), which requires setting an exploration bonus coefficient, Thompson Sampling automatically calibrates exploration based on uncertainty. When an arm has been tried few times, its posterior is wide, generating highly variable samples that occasionally beat well-established arms. As data accumulates, the posterior concentrates around the true mean, and sampling naturally converges to exploitation. This self-tuning property makes Thompson Sampling particularly robust in non-stationary environments where reward distributions shift over time, as the posterior can widen again with a forgetting mechanism or sliding window.

Thompson Sampling extends naturally to contextual bandits by modeling the expected reward as a function of context features with a Bayesian model. In the linear contextual case, a Gaussian prior is placed on the weight vector, and the posterior is updated via Bayesian linear regression. At decision time, a weight vector is sampled from the posterior, and the arm with the highest predicted reward given the current context is selected. This enables real-time personalization where the algorithm learns which actions work best for specific user segments, device types, or time-of-day patterns without requiring separate models for each context partition.

Thompson Sampling provides strong theoretical guarantees on regret minimization. For the standard stochastic K-armed bandit, it achieves a logarithmic regret bound, meaning the cumulative regret grows only logarithmically with the number of rounds. This is asymptotically optimal, matching the theoretical lower bound. In practice, Thompson Sampling often outperforms UCB and Epsilon-Greedy in empirical studies, especially in the early rounds where efficient exploration is critical. The algorithm's regret performance stems from its ability to quickly eliminate clearly suboptimal arms while continuing to sample promising but uncertain arms proportionally to their probability of being best.

Thompson Sampling is computationally efficient when using conjugate priors, where the posterior distribution remains in the same family as the prior after observing data. Common pairings include:

• Beta-Bernoulli for binary click/no-click rewards
• Gaussian-Gaussian for continuous rewards like revenue or time-on-site
• Dirichlet-Multinomial for categorical outcomes with more than two possibilities The update step requires only simple parameter additions rather than expensive Markov Chain Monte Carlo sampling. For non-conjugate models, Laplace approximation or bootstrapped Thompson Sampling can approximate the posterior efficiently, making the algorithm viable for high-throughput production systems serving millions of decisions per second.

Thompson Sampling handles the cold start problem through informative prior specification. Rather than starting with uniform uncertainty, practitioners can encode domain knowledge into the prior distributions. For example, a new product category can inherit the prior from a similar existing category, or a hierarchical Bayesian model can share statistical strength across related arms. This warm-start capability means the algorithm can begin with reasonable performance from the first interaction, avoiding the random exploration phase that plagues uninformed methods. The prior also acts as a natural regularization mechanism, preventing overfitting to early noisy observations.

The foundational class of algorithms to which Thompson Sampling belongs. A Bayesian Bandit maintains a posterior probability distribution over the unknown reward parameters of each arm. As new data is observed, this distribution is updated using Bayes' theorem, quantifying the uncertainty around each arm's true value. Unlike deterministic methods like UCB, the Bayesian approach provides a full probabilistic model of the environment, enabling more nuanced exploration strategies and principled uncertainty quantification.

A deterministic alternative to Thompson Sampling that selects actions by maximizing an optimistic estimate of the expected reward. The algorithm calculates a confidence interval for each arm and chooses the one with the highest upper bound. The key difference from Thompson Sampling is that UCB adds an explicit exploration bonus based on the uncertainty of the estimate, while Thompson Sampling naturally randomizes selection according to the probability of optimality. UCB is often simpler to implement but can be less robust in non-stationary environments.

The primary optimization objective in bandit problems. Regret is defined as the difference between the cumulative reward of an optimal oracle policy and the reward accumulated by the learning algorithm. Thompson Sampling is renowned for achieving logarithmic regret bounds in many settings, meaning the per-round regret decreases rapidly as the algorithm learns. This formal framework allows data scientists to prove that an algorithm will converge to near-optimal performance, a critical assurance for business-critical personalization systems.

A statistical method for estimating the performance of a new policy using historical data collected under a different logging policy. This is critical for offline model validation before deployment. Key techniques include:

• Inverse Propensity Scoring (IPS): Re-weights observed rewards by the inverse probability of the action being taken by the logging policy, correcting for selection bias.
• Doubly Robust Estimator: Combines IPS with a direct reward model to provide unbiased estimates even if one of the two models is misspecified.
• These methods allow safe, rigorous comparison of Thompson Sampling against alternative algorithms without risking live user experience.

A bandit problem where the underlying reward distributions change over time, reflecting real-world dynamics like shifting consumer preferences or seasonal trends. Standard Thompson Sampling assumes stationary rewards, but variants exist that incorporate discount factors or sliding windows to forget old observations. In non-stationary environments, the algorithm must continuously adapt, making the balance between stability and plasticity a central design challenge for production personalization systems.

A contextual bandit that uses a deep neural network to model the complex, non-linear relationship between context features and expected rewards. While classical Thompson Sampling often assumes a linear or simple parametric reward model, Neural Bandits leverage the representational power of deep learning to capture intricate user behavior patterns. This fusion allows Thompson Sampling's principled exploration to scale to high-dimensional, unstructured context spaces like image embeddings or natural language descriptions.