Thompson sampling
In plain wordsA way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far.
A Bayesian strategy for the exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one. that, at each round, draws one sample of the unknown parameters from their posteriorposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces. distribution and takes the actionaction, n.: A choice an AI agent makes at one moment — move left, place a stone, type a command — which changes its situation and may earn it a reward. that would be optimal if that sample were true; the observed rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time. then updates the posterior. Each action is thus chosen with the probability that it is optimal, so uncertain options are explored in proportion to their chance of being best and exploration fades as evidence accumulates. With conjugate priors (for example Beta–Bernoulli for click-or-no-click rewards) it takes a few lines of code. It achieves asymptotically optimal logarithmic regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying. in standard banditsmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., often beats UCBupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance. empirically, extends to contextual bandits and, as posterior sampling for reinforcement learning, to full MDPs by sampling a whole model per episode. When exact posteriors are intractable, ensembles, bootstrapping or Laplace approximations stand in.
With Thompson sampling, the new ad got traffic only while its click rate was still plausibly the best.
Origin
Proposed by William R. Thompson in 'On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples' (Biometrika, 1933), one of the earliest bandit papers. Long neglected, it was revived after Olivier Chapelle and Lihong Li's empirical study (NIPS 2011) and Shipra Agrawal and Navin Goyal's regret analysis (2012).
Related
- multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others.
- regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.
- posteriorposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces.
- Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability.
- exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.
- epsilon-greedyepsilon-greedy, adj.: A simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random.
- upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.
Sources
- Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3–4), 285–294.
- Chapelle, O. & Li, L. (2011). An Empirical Evaluation of Thompson Sampling. NIPS 2011.
- Russo, D. et al. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning 11(1), 1–96.
Mentioned in
Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability., epsilon-greedyepsilon-greedy, adj.: A simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random., exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one., multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying., upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.