Thompson sampling is a Bayesian sequential decision algorithm that samples from posterior distributions over alternatives and selects the alternative with the highest sampled value.
When the best option is unknown, Thompson sampling uses Bayesian beliefs to choose among alternatives while learning from their observed rewards. section 2.4.1
At each decision point:
Maintain a prior distribution for each option’s expected reward, then update it to a posterior as outcomes arrive. section 2.4.1
Sample a reward from each option’s posterior and choose the option with the highest sampled value. section 2.4.1
Repeat as evidence accumulates; increasingly precise posteriors concentrate decisions on the best-performing option. section 2.4.1
How Timeless Algorithms, The Foundational Ideas covers it
How deep it goes
Explains prior-to-posterior updating and reward sampling as a repeated decision process.
Examples
Names online advertising, recommendation systems, website optimization, and pricing, with clicks, purchases, and conversions as outcomes.
What you can do after
Understand how posterior beliefs guide repeated choices while leaving uncertain alternatives opportunities for exploration.
How it connects
Connects Bayesian inference, Bayes’ theorem, posterior distributions, and the exploration–exploitation tradeoff.
Experimentation for EngineersThompson sampling is a Bayesian bandit algorithm that samples each alternative's expected reward from its posterior distribution and selects an alternative according to those samples.
Bayesian Optimization in ActionThompson sampling is a Bayesian decision policy that samples a plausible model or parameter value from a posterior distribution and selects the action that is optimal under that sample.
Applied Reinforcement LearningA Bayesian bandit action-selection algorithm that samples each action's expected reward from its posterior distribution and selects the action with the best sample.
Grokking BayesThompson sampling is a Bayesian action-selection method that samples candidate parameters or values from their posterior distribution and chooses the corresponding action.
Bayes' theoremuses · Bayes' theorem relates conditional probabilities, expressing a posterior probability in terms of a prior probability, a likelihood, and the evidence.
MaxPosteriorSamplingimplemented by · MaxPosteriorSampling is a BoTorch sampler that draws posterior samples at candidate points and selects candidates maximizing those samples.
multi-armed banditkind of · A multi-armed bandit is a sequential decision problem in which an agent repeatedly chooses among alternatives with uncertain rewards, balancing reward seeking with information gathering.
exploration-exploitation trade-offaddresses · The exploration-exploitation trade-off is the decision problem of balancing actions that gather information about uncertain alternatives with actions chosen for their currently expected payoff.
beta distributionuses · The beta distribution is a continuous probability distribution on the interval from zero to one, parameterized by two positive shape parameters.
bootstrap Thompson samplingincludes · Bootstrap Thompson sampling is a form of Thompson sampling that estimates each alternative's probability of being best from bootstrap resamples or an ensemble of fitted models.
This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.