Thompson Sampling

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).

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.