Thompson Sampling

The core mechanism of Thompson Sampling is probability matching. Instead of selecting the arm with the highest estimated mean reward, the algorithm samples a potential reward value from the posterior distribution of each arm. The arm whose sampled value is highest is chosen for that round. This elegantly encodes uncertainty: arms with wider (more uncertain) posteriors have a higher chance of being sampled, driving exploration.

• Example: If Arm A has a posterior mean of 0.8 with high confidence (narrow distribution) and Arm B has a posterior mean of 0.7 with low confidence (wide distribution), Thompson Sampling will still choose Arm B a non-zero percentage of the time, probing to see if its true mean is higher.

Thompson Sampling requires no external tuning parameter (like the ε in ε-greedy or the exploration constant in UCB) to control the exploration rate. The balance emerges automatically from the Bayesian update process. As an arm is pulled and its posterior distribution narrows (uncertainty decreases), the probability of sampling a high value from it decreases unless its mean is truly high. This leads to a natural progression from exploration to exploitation.

• Key Benefit: This eliminates the need for costly hyperparameter sweeps to set an exploration schedule, making the algorithm simpler to deploy in production systems where conditions may change.

For computational efficiency, Thompson Sampling is typically implemented with conjugate prior distributions. A common choice is using a Beta distribution for Bernoulli rewards (click/no-click) and a Normal-Gamma distribution for Gaussian rewards. This allows the posterior distribution to be updated analytically with simple parameter updates upon observing a new reward, enabling constant-time, O(1) updates per round.

• Update Rule (Beta-Bernoulli): Starting with prior Beta(α=1, β=1). After observing a reward of 1 (success), update to Beta(α+1, β). After a reward of 0 (failure), update to Beta(α, β+1).

Thompson Sampling achieves strong theoretical performance guarantees. For the classical K-armed bandit problem, it is asymptotically optimal, meaning its cumulative regret grows at the optimal rate described by the Lai-Robbins lower bound. Modern analyses provide finite-time Bayesian regret bounds that are sublinear in the time horizon T.

• Practical Implication: This theoretical foundation assures engineers that the algorithm will not just perform well empirically but is provably efficient in the long run, converging to the best arm and minimizing lost reward.

The algorithm extends powerfully to contextual bandits, where side information (context) is available for each decision. In Linear Thompson Sampling, a linear function models the expected reward given the context. A prior distribution is placed over the weight vector. The algorithm samples a weight vector from its posterior, computes the expected reward for each arm using the sampled weights and the current context, and selects the arm with the highest value.

• Use Case: This is foundational for personalized recommendations, where the context is user features, and arms are articles or products.

Thompson Sampling is inherently robust to delayed feedback, a common challenge in production systems (e.g., an ad click may be reported minutes later). Because it operates by maintaining a posterior distribution, feedback can be incorporated whenever it arrives, simply by updating the posterior parameters with the historical context. This also allows for efficient batched updates, where decisions are made in real-time, but the Bayesian updates are applied in mini-batches for system efficiency.

• System Design Impact: This decouples the low-latency inference path from the potentially higher-latency training update loop.

A multi-armed bandit is a sequential decision-making framework where an agent must balance exploring unknown actions with exploiting the best-known action to maximize cumulative reward. It is the foundational problem Thompson Sampling is designed to solve.

• Analogy: A gambler choosing between multiple slot machines (bandits) with unknown payout rates.
• Key Challenge: The agent lacks prior knowledge of the true reward distribution for each action.
• Applications: Clinical trial designs, website A/B testing, and real-time recommendation systems.

Upper Confidence Bound is a deterministic algorithm for the multi-armed bandit problem that selects the action with the highest estimated reward plus an exploration bonus proportional to the uncertainty of that estimate.

• Contrast with Thompson Sampling: UCB uses a deterministic, optimism-in-the-face-of-uncertainty principle, while Thompson Sampling is probabilistic and Bayesian.
• Mechanism: The bonus term, often derived from the Hoeffding inequality, shrinks as an action is sampled more.
• Use Case: Preferred in environments where deterministic, explainable action selection is required.

Regret minimization is the theoretical framework for analyzing online learning and bandit algorithms, where the goal is to minimize the cumulative loss difference between the algorithm's predictions and the best fixed decision in hindsight.

• Regret Definition: The total reward lost by not always playing the optimal arm.
• Theoretical Guarantee: A key metric for proving an algorithm's asymptotic optimality; both UCB and Thompson Sampling can be shown to have sublinear regret.
• Importance: Provides a rigorous, mathematical benchmark for comparing the performance of different exploration strategies.

Online learning is a machine learning paradigm where a model updates its parameters sequentially, one data point or mini-batch at a time, without revisiting past data.

• Core Property: Suitable for streaming data and real-time adaptation where storing the entire dataset is infeasible.
• Foundation: Algorithms like Stochastic Gradient Descent (SGD) are the fundamental update rule for most online learning systems.
• System Context: Thompson Sampling is an online learning algorithm specifically for the sequential decision-making subclass of problems.

Bayesian inference is a statistical method where Bayes' theorem is used to update the probability for a hypothesis as more evidence or data becomes available. Thompson Sampling is a direct application of this framework.

• Posterior Distribution: Represents updated beliefs about an unknown parameter (e.g., reward rate of a bandit arm) after observing data.
• Prior Distribution: Encodes initial beliefs before seeing any data.
• Thompson Sampling Mechanism: The algorithm works by sampling a potential reward model from this posterior distribution for each arm and then selecting the arm with the highest sampled value.

Contextual bandits extend the multi-armed bandit framework by incorporating side information (context) about each decision round, allowing the optimal action to depend on the observed context.

• Example: Recommending an article based on a user's browsing history and demographic data.
• Thompson Sampling Extension: Contextual Thompson Sampling uses a probabilistic linear model (or deep neural network) where parameters are sampled from a posterior, enabling personalized exploration.
• Industrial Application: The primary framework for modern, real-time personalization systems in tech companies.