Thompson Sampling

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.

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.