Thompson Sampling

The core mechanism of Thompson Sampling is probability matching. Instead of always choosing the arm with the highest estimated mean reward (pure exploitation), it selects each arm with a probability equal to that arm being the optimal one, given the current uncertainty. This is achieved by:

• Maintaining a posterior distribution (e.g., Beta for Bernoulli rewards, Gaussian for normal rewards) for the expected reward of each arm.
• On each trial, sampling a single value from each arm's posterior distribution.
• Choosing the arm whose sampled value is the highest. This stochastic selection naturally balances exploration (sampling uncertain arms) and exploitation (sampling promising arms).

Thompson Sampling inherently quantifies and responds to uncertainty through its Bayesian framework. The variance of the posterior distribution for each arm directly represents the algorithm's uncertainty about that arm's true reward rate.

• High Variance (Early Stages): For an arm with few pulls, the posterior is wide. Random samples from this distribution can vary widely, giving it a significant chance of being selected over a known-good arm, promoting exploration.
• Low Variance (Later Stages): As an arm is pulled more, its posterior distribution tightens around the empirical mean. Its sampled values become consistent, and it is only selected if its mean is truly high, leading to exploitation. This dynamic adjustment requires no external tuning of an exploration parameter (like ε in ε-greedy).

Thompson Sampling provides strong theoretical performance guarantees. For the standard K-armed bandit problem, it achieves logarithmic expected cumulative regret under certain conditions, matching the asymptotic lower bound and making it asymptotically optimal.

• Cumulative Regret: The total difference in reward between always pulling the optimal arm and the algorithm's choices. Thompson Sampling's regret grows as O(log T).
• Frequentist Analysis: Modern analyses have proven these bounds without relying on a 'correct' Bayesian prior, showing robustness.
• Contextual Bandits: Extensions to linear contextual bandits also achieve near-optimal regret bounds (O(√T) or O(log T) depending on assumptions), making it applicable to personalized recommendations and dynamic treatment assignment.

Despite its Bayesian foundation, Thompson Sampling is often computationally straightforward to implement and scale.

• Conjugate Priors: Using conjugate prior-likelihood pairs (e.g., Beta-Bernoulli, Gaussian-Gaussian) allows the posterior to be updated with simple arithmetic upon observing a reward, requiring only O(1) computation per update.
• Parallelization: Sampling and selection for each arm is independent, making it easy to parallelize across a large set of arms.
• Comparison to UCB: Unlike Upper Confidence Bound (UCB) algorithms, which require calculating confidence intervals, Thompson Sampling only requires drawing random samples, which can be more efficient in complex models (e.g., deep neural network-based bandits where sampling from a posterior approximation is simpler than computing high-dimensional confidence sets).

The sampling-based approach generalizes elegantly beyond simple bandits to complex, real-world problems.

• Contextual Bandits with Deep Learning (Neural Thompson Sampling): The reward function is modeled by a deep neural network. A posterior over network weights is approximated (e.g., via bootstrapping, dropout as approximate Bayesian inference, or Laplace approximation). An action is chosen by sampling a network from this posterior and selecting the context-action pair with the highest predicted reward.
• Non-Stationary Environments: Can adapt to changing reward distributions by using forgetting mechanisms like discounting old observations or using change-point models within the Bayesian update.
• Hierarchical Models: Naturally incorporates shared structure between arms (e.g., in multi-task or meta-learning bandit settings) through hierarchical priors, allowing for efficient knowledge transfer.

Thompson Sampling occupies a distinct point in the design space of bandit algorithms.

• vs. ε-Greedy: ε-greedy explores randomly with a fixed probability ε, ignoring uncertainty. Thompson Sampling explores intelligently, proportionally to the probability an arm is optimal.
• vs. Upper Confidence Bound (UCB): UCB is a deterministic, optimism-in-the-face-of-uncertainty principle. It selects the arm with the highest upper confidence bound. Thompson Sampling is randomized and directly samples from the posterior. The two are often viewed as dual perspectives (frequentist optimism vs. Bayesian probability matching) and can have similar regret bounds.
• vs. Gittins Index: The Gittins Index provides an optimal solution for the discounted infinite-horizon Bayesian bandit problem but is often computationally intractable. Thompson Sampling is a simple, near-optimal heuristic for both discounted and finite-horizon settings.

The foundational sequential decision-making framework where an agent repeatedly chooses from a set of actions (arms), each providing a stochastic reward from an unknown distribution. The core tension is between exploitation (choosing the arm with the highest estimated reward) and exploration (trying other arms to gather more information). Thompson Sampling is a heuristic solution to this problem.

A global optimization strategy for expensive black-box functions. Like Thompson Sampling, it uses a probabilistic surrogate model (e.g., a Gaussian Process) to model the objective. It selects the next point to evaluate by optimizing an acquisition function, which explicitly balances exploration and exploitation. Common functions include Expected Improvement (EI) and Upper Confidence Bound (UCB).

A deterministic alternative to Thompson Sampling for the multi-armed bandit problem. The algorithm selects the arm with the highest upper confidence bound, calculated as the estimated mean reward plus an exploration bonus. The bonus (e.g., √(2 log t / n_i)) shrinks as an arm is pulled more often (n_i), ensuring all arms are sufficiently explored. It provides strong theoretical regret bounds.

An extension of the classic bandit problem where, before each decision, the agent observes a context vector (e.g., user features, time of day). The goal is to learn a policy mapping contexts to actions to maximize reward. Thompson Sampling is readily extended to this setting using contextual models like Bayesian linear regression or neural networks with approximate posterior distributions.

A broader framework for sequential decision-making in environments with delayed rewards and state transitions. The multi-armed bandit is a stateless, single-step RL problem. Thompson Sampling's principle of posterior sampling extends to RL as Posterior Sampling for Reinforcement Learning (PSRL), where the agent samples a full Markov Decision Process (MDP) from a posterior and acts optimally within it for an episode.

A class of computational algorithms that rely on repeated random sampling to obtain numerical results. Thompson Sampling is inherently a Monte Carlo method: it makes decisions by sampling from posterior distributions. This connects it to broader techniques like Monte Carlo Tree Search (MCTS), which uses random simulations to evaluate actions in complex decision trees.