Thompson sampling is an algorithm for online decision problems where actions are taken sequentially in a manner that must balance between exploiting what is known to maximize immediate performance and investing to accumulate new information that may improve future performance. The algorithm addresses a broad range of problems in a computationally efficient manner and is therefore enjoying wide use. This tutorial covers the algorithm and its application, illustrating concepts through a range of examples, including Bernoulli bandit problems, shortest path problems, dynamic pricing, recommendation, active learning with neural networks, and reinforcement learning in Markov decision processes. Most of these problems involve complex information structures, where information revealed by taking an action informs beliefs about other actions. We will also discuss when and why Thompson sampling is or is not effective and relations to alternative algorithms.

该论文介绍了Thompson采样算法在处理在线决策问题，尤其是在平衡当前性能和收集信息提高未来性能之间的探索与利用上的应用。该算法适用于各种问题并具有高效的计算能力，具体例子包括伯努利老虎机问题，最短路径问题，推荐系统，主动学习等。此外，本文还讨论了Thompson采样算法何时有效、何时无效以及与其他算法的关系。

Thompson抽样教程