Preprint · 2011 · Open access
Analysis of Thompson Sampling for the multi-armed bandit problem
arXiv (Cornell University) · Published 8 November 2011 · DOI 10.48550/arxiv.1111.1797
In brief
“Analysis of Thompson Sampling for the multi-armed bandit problem” is a 2011 preprint by Shipra Agrawal and Navin Goyal, published in arXiv (Cornell University). OpenAlex counts 966 citations as of 19 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).
- Citations
- 966
- Most cited in
- 2020 (169)
- References
- 13
- Authors
- 2
Abstract
The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the multi-armed bandit problem. More precisely, for the two-armed bandit problem, the expected regret in time $T$ is $O(\frac{\ln T}Δ + \frac{1}{Δ^3})$. And, for the $N$-armed bandit problem, the expected regret in time $T$ is $O([(\sum_{i=2}^N \frac{1}{Δ_i^2})^2] \ln T)$. Our bounds are optimal but for the dependence on $Δ_i$ and the constant factors in big-Oh.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Agrawal, S., & Goyal, N. (2011). Analysis of Thompson Sampling for the multi-armed bandit problem. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1111.1797
MLA 9
Agrawal, Shipra, and Navin Goyal. “Analysis of Thompson Sampling for the multi-armed bandit problem.” arXiv (Cornell University), 2011. https://doi.org/10.48550/arxiv.1111.1797.
Chicago
Agrawal, Shipra and Navin Goyal. 2011. “Analysis of Thompson Sampling for the multi-armed bandit problem.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1111.1797.
Harvard
Agrawal, S. and Goyal, N. (2011) ‘Analysis of Thompson Sampling for the multi-armed bandit problem’, arXiv (Cornell University). doi:10.48550/arxiv.1111.1797.
IEEE
S. Agrawal and N. Goyal, “Analysis of Thompson Sampling for the multi-armed bandit problem,” arXiv (Cornell University), 2011, doi: 10.48550/arxiv.1111.1797.
BibTeX
@misc{agrawal2011analysis,
title = {{Analysis of Thompson Sampling for the multi-armed bandit problem}},
author = {Agrawal, Shipra and Goyal, Navin},
howpublished = {arXiv (Cornell University)},
year = {2011},
doi = {10.48550/arxiv.1111.1797},
url = {https://doi.org/10.48550/arxiv.1111.1797}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2017 | 78 | |
| 2018 | 91 | |
| 2019 | 100 | |
| 2020 | 169 | |
| 2021 | 138 | |
| 2022 | 74 | |
| 2023 | 68 | |
| 2024 | 59 | |
| 2025 | 32 | |
| 2026 | 14 |
Topic and keywords
Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Thompson sampling
- multi-armed bandits
- regret bounds
- exploration-exploitation balance
- Bayesian decision making
- two-armed bandit
- logarithmic regret
- sequential decision making
Work with this paper
Most-cited papers in Decision Sciences
- The PRISMA 2020 statement: an updated guideline for reporting systematic reviewsMatthew James Page, Joanne E. McKenzie, Patrick M. Bossuyt and 23 more · BMJ · 2021 · 144,919 citations
- Evaluating Structural Equation Models with Unobservable Variables and Measurement ErrorClaes Fornell, David F. Larcker · Journal of Marketing Research · 1981 · 118,336 citations
- Cutoff criteria for fit indexes in covariance structure analysis: Conventional criteria versus new alternativesLi‐tze Hu, Peter M. Bentler · Structural Equation Modeling A Multidisciplinary Journal · 1999 · 117,461 citations
- Common method biases in behavioral research: A critical review of the literature and recommended remedies.Philip M. Podsakoff, SCOTT B. MACKENZIE, Jeong Yeon Lee and 1 more · Journal of Applied Psychology · 2003 · 89,248 citations
- Preferred reporting items for systematic reviews and meta-analyses: the PRISMA statementDavid Moher, Alessandro Liberati, Jennifer Tetzlaff and 2 more · BMJ · 2009 · 85,524 citations
Questions about this paper
How do I cite this paper in APA style?
Agrawal, S., & Goyal, N. (2011). Analysis of Thompson Sampling for the multi-armed bandit problem. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1111.1797
How many times has this paper been cited?
966 times, according to OpenAlex on 19 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.
Who wrote this paper?
Shipra Agrawal, Navin Goyal.
What is the DOI of this paper?
10.48550/arxiv.1111.1797, permanently at https://doi.org/10.48550/arxiv.1111.1797. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 19 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.