Preprint · 2011 · Open access

Analysis of Thompson Sampling for the multi-armed bandit problem

Shipra Agrawal, Navin Goyal

arXiv (Cornell University) · Published 8 November 2011 · DOI 10.48550/arxiv.1111.1797

Open PDFView at the publisherCite this paper

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

YearCitationsShare of the best year
20177878
20189191
2019100100
2020169169
2021138138
20227474
20236868
20245959
20253232
20261414

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

All highly cited Decision Sciences papers

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.