In “An Empirical Evaluation of Thompson Sampling”, Chapelle and Lihong Li (NIPS 2011) compare Upper Confidence Bound (UCB), Gittins, and Thompson methods for the multi-armed bandit problem.  More theoretical analysis has been done for UCB and Gittins, but Thompson sampling is simple (as opposed to Gittins) and seems to work well, sometimes performing significantly better that the other common algorithms. Both synthetic and real world (advertising) results are presented.

Related Posts via Categories

• Link/Book(pdf): “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems”
• Link: AlphaGo Wins against one of the best Go Players on the Planet
• Ted Dunning on Bandits
• “Stochastic Superoptimization” and “Programming by Optimization”
• “Generalized Thompson sampling for sequential decision-making and causal inference”
• “Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained”
• “Linear Bandits in High Dimension and Recommendation Systems”
• “A Survey of Monte Carlo Tree Search Methods”
• Schwarzenegger Bandit Success Formula
• “Analysis of Thompson Sampling for the multi-armed bandit problem”