EUVIMEDSkopri EUVIMED
Crossref

A Tutorial on Thompson Sampling

Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen

Foundations and Trends® in Machine Learning · 2018-07-12 · 11 (1) · 1-96

DOI: 10.1561/2200000070 ↗

At a glance

Journal article in Foundations and Trends® in Machine Learning, published online on 2018-07-12. Written by Daniel J. Russo and 4 co-authors. Cited 421 times so far (Crossref); 84 references.

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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, product recommendation, assortment, 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.

Cite

APA

Russo, D. J., Roy, B. V., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends® in Machine Learning, 11(1), 1-96. https://doi.org/10.1561/2200000070

Vancouver

Russo DJ, Roy BV, Kazerouni A, Osband I, Wen Z. A Tutorial on Thompson Sampling. Foundations and Trends® in Machine Learning. 2018;11(1):1-96. doi:10.1561/2200000070

BibTeX
@article{Russo2018,
  author = {Russo, Daniel J. and Roy, Benjamin Van and Kazerouni, Abbas and Osband, Ian and Wen, Zheng},
  title = {A Tutorial on Thompson Sampling},
  journal = {Foundations and Trends® in Machine Learning},
  year = {2018},
  volume = {11},
  number = {1},
  pages = {1--96},
  doi = {10.1561/2200000070}
}
Start for free →