Thompson Sampling

The core mechanism of Thompson Sampling is probability matching: an action is chosen with a frequency proportional to its probability of being the best option. At each decision step, the algorithm draws a random 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 are explored naturally, while arms with high estimated rewards are exploited frequently. The process is inherently self-correcting—as more data is gathered, the posterior distributions narrow, reducing exploration automatically.

Thompson Sampling is fundamentally a Bayesian algorithm that requires specifying a prior distribution over each arm's reward parameter. Common choices include:

• Beta-Bernoulli model: For binary outcomes (click/no-click), using a Beta(α, β) prior where α represents successes and β represents failures.
• Gaussian model: For continuous rewards with known variance, using a Normal prior on the mean.
• Dirichlet-Multinomial model: For categorical outcomes with more than two possible results. The choice of prior encodes initial beliefs and can incorporate domain knowledge. A uniform prior (Beta(1,1)) represents complete ignorance, while an informed prior can accelerate early performance.

Thompson Sampling achieves logarithmic regret in the stochastic multi-armed bandit setting, meaning the cumulative difference between its performance and an optimal oracle strategy grows only logarithmically with time. This is provably optimal. Key regret characteristics include:

• Lai-Robbins lower bound: Thompson Sampling asymptotically matches the theoretical lower bound for regret in stochastic bandits.
• Finite-time guarantees: Recent theoretical work provides finite-time regret bounds, not just asymptotic results.
• Empirical superiority: In practice, Thompson Sampling often outperforms UCB (Upper Confidence Bound) and ε-greedy strategies, especially in the early stages of learning when uncertainty is high.

The algorithm extends naturally to contextual bandits where side information is available before each decision. In Contextual Thompson Sampling, the reward model becomes a function of context features (e.g., user demographics, time of day). A common implementation uses Bayesian logistic regression or Bayesian linear regression with a prior over the weight vector. At each step:

1. A weight vector is sampled from the posterior distribution over model parameters.
2. The predicted reward is computed for each arm using the sampled weights and current context.
3. The arm with the highest predicted reward is selected. This allows personalization based on observed features while maintaining the exploration-exploitation balance.

Thompson Sampling is computationally lightweight compared to many alternatives. For the Beta-Bernoulli case, each update requires only incrementing two counters (successes and failures), and sampling from a Beta distribution is a standard library call. Key implementation considerations:

• Conjugate priors: Using conjugate prior-likelihood pairs (Beta-Binomial, Normal-Normal) ensures the posterior remains in the same distribution family, enabling closed-form updates without MCMC.
• Batch updates: Posterior updates can be performed in batches rather than after every single observation, reducing computational overhead in high-throughput systems.
• Non-conjugate extensions: For complex reward models (e.g., neural networks), approximate inference methods like variational inference or Monte Carlo dropout can approximate Thompson Sampling.

Thompson Sampling differs from other bandit algorithms in fundamental ways:

• vs. ε-greedy: ε-greedy explores uniformly at random with fixed probability ε, while Thompson Sampling directs exploration toward arms that might plausibly be optimal, making it far more efficient.
• vs. UCB (Upper Confidence Bound): UCB constructs deterministic confidence intervals and always selects the arm with the highest upper bound. Thompson Sampling is stochastic and naturally handles complex posterior shapes that UCB's symmetric intervals cannot capture.
• vs. Boltzmann exploration: Softmax/Boltzmann exploration uses a temperature parameter to control exploration randomness, while Thompson Sampling's randomness is driven by genuine posterior uncertainty, which diminishes automatically with data.

An extension of the multi-armed bandit problem where the agent observes contextual information (e.g., user demographics, time of day) before making a decision. Unlike standard Thompson Sampling which assumes a static reward distribution, contextual bandits use this side information to personalize actions. The algorithm learns a mapping from context to expected reward, often using linear models or neural networks to generalize across similar contexts.

The fundamental dilemma that Thompson Sampling elegantly addresses. Exploitation involves choosing the action with the highest known reward to maximize immediate gains. Exploration involves selecting uncertain actions to gather data that may lead to higher rewards in the future. Thompson Sampling naturally balances these by sampling from the posterior distribution: actions with high uncertainty are chosen proportionally to their probability of being optimal.

The standard framework for evaluating bandit algorithms. Regret is defined as the difference between the cumulative reward obtained by an optimal oracle strategy and the reward accumulated by the algorithm. Thompson Sampling is proven to achieve logarithmic regret under many standard settings, meaning the rate of suboptimal choices decreases rapidly over time, making it highly efficient for production environments.

The mathematical backbone of Thompson Sampling. Instead of point estimates, Bayesian inference maintains a posterior probability distribution over the unknown reward parameters. Key concepts include:

• Prior Distribution: Initial belief about the reward probability (e.g., Beta(1,1) for binary outcomes).
• Likelihood: How probable the observed data is given the parameters.
• Posterior Update: Using Bayes' theorem to refine beliefs after each observation. This probabilistic approach naturally quantifies uncertainty.

A frequentist alternative to Thompson Sampling for solving the exploration-exploitation dilemma. UCB algorithms select the action that maximizes an optimistic estimate of the reward, calculated as the empirical mean plus an uncertainty bonus. While both achieve optimal regret bounds, Thompson Sampling often outperforms UCB empirically because its randomized selection is more robust to delayed feedback and non-stationary environments.

A generalization of the bandit problem where actions influence not just immediate rewards but also future states. While Thompson Sampling solves single-step decisions, MDPs model sequential planning. Extensions like Posterior Sampling for Reinforcement Learning (PSRL) apply the Thompson Sampling principle to MDPs by maintaining a posterior over transition dynamics and reward functions, sampling a full model, and solving it to generate a policy.