Thompson Sampling

Thompson Sampling maintains a posterior probability distribution over the expected reward for each possible action. This distribution, often a Beta distribution for Bernoulli rewards or a Gaussian for continuous rewards, encodes the algorithm's uncertainty. A wide distribution indicates high uncertainty (encouraging exploration), while a narrow, peaked distribution indicates high confidence (encouraging exploitation).

The algorithm does not simply choose the action with the highest estimated mean reward. Instead, it performs probability matching: it selects an action with a probability equal to the posterior probability that said action is optimal. This is implemented by sampling a single reward estimate from the posterior distribution of each arm and then choosing the arm with the highest sampled value. This elegant mechanism naturally balances exploration and exploitation.

Beliefs are updated sequentially and online after each action and observed reward. For a Bernoulli bandit (success/failure rewards), if a Beta(α, β) prior is used:

• A success increments α.
• A failure increments β. This Bayesian update ensures the posterior distribution incorporates all historical data, continuously refining the estimate of each action's reward probability. The algorithm requires no separate exploration phase.

Thompson Sampling achieves asymptotically optimal regret bounds for standard multi-armed bandit problems. Regret is the difference between the cumulative reward of the optimal strategy and the algorithm's reward. For Bernoulli bandits, its regret grows logarithmically with the number of rounds, matching the theoretical lower bound. This makes it highly sample-efficient in practice.

The framework extends naturally to contextual bandits, where side information (context) is available before each decision. A probabilistic model (e.g., a Bayesian linear regression) predicts rewards given the context. Thompson Sampling operates by sampling a parameter vector from the posterior of this model and selecting the action that maximizes the reward under the sampled parameters. This is foundational for modern personalized recommendation systems.

In model-based reinforcement learning, Thompson Sampling can be applied at the level of the environment model. An agent maintains a posterior distribution over possible world models (e.g., over transition dynamics). It samples a model, plans an optimal policy under that sampled model, acts, and then updates the model posterior with the observed outcome. This is known as Posterior Sampling for Reinforcement Learning (PSRL).

The Multi-Armed Bandit Problem is the foundational sequential decision-making framework where an agent must repeatedly choose between multiple actions (arms), each providing a stochastic reward drawn from an unknown distribution. The core challenge is the exploration-exploitation trade-off: balancing the need to gather information about uncertain arms (exploration) with the desire to capitalize on the arm currently believed to be best (exploitation). Thompson Sampling is a Bayesian solution to this problem.

Upper Confidence Bound (UCB) is a deterministic, frequentist alternative to Thompson Sampling for solving the multi-armed bandit problem. Instead of sampling from a posterior, UCB algorithms select the arm with the highest upper confidence bound on its expected reward. This bound is calculated as the current empirical mean plus an exploration bonus that shrinks as the arm is pulled more often. Key variants include UCB1 and KL-UCB. Unlike Thompson Sampling, UCB provides explicit, worst-case regret bounds.

Bayesian Inference is the statistical paradigm that underpins Thompson Sampling. It involves updating the probability for a hypothesis (e.g., 'arm A is optimal') as more evidence (observed rewards) becomes available. The process follows Bayes' Theorem: Posterior ∝ Likelihood × Prior.

• Prior: Initial belief about reward distributions (e.g., Beta(1,1) for Bernoulli rewards).
• Likelihood: Probability of observed data given the parameters.
• Posterior: Updated belief after observing data. Thompson Sampling acts by sampling parameters from this posterior.

A Conjugate Prior is a probability distribution that, when used as a prior for a specific likelihood function, results in a posterior distribution that is in the same family. This mathematical convenience is critical for the efficient, closed-form updates in Thompson Sampling.

• For Bernoulli/Binomial rewards (success/failure), the conjugate prior is the Beta distribution.
• For Gaussian rewards with known variance, the conjugate prior for the mean is another Gaussian distribution. Using a conjugate prior allows the agent to update its belief state (the posterior parameters) analytically after each observation, enabling real-time decision-making.

Regret is the primary performance metric for evaluating bandit algorithms like Thompson Sampling. It quantifies the cumulative opportunity cost of not always selecting the optimal action.

• Cumulative Regret: The sum over time of the difference between the reward of the optimal arm and the reward of the arm actually chosen.
• Bayesian Regret: The expected cumulative regret, where the expectation is taken over both the randomness in the algorithm and the prior distribution over problem instances. A key goal is to design algorithms with sublinear regret, meaning the average regret per round goes to zero over time, proving the agent is learning optimally.

Contextual Bandits extend the classic multi-armed bandit framework by incorporating side information or context. Before each round, the agent observes a context vector (e.g., user features, time of day) that can inform which arm is likely to be best. The goal is to learn a policy that maps contexts to actions. Thompson Sampling can be extended to this setting, often by using a Bayesian linear model (e.g., with a Gaussian prior) to parameterize the expected reward for each arm given the context, enabling personalized decision-making.