Thompson Sampling for Contextual Bandits with Linear Payoffs
Open accessAbstract
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied versions of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ (or $\tilde{O}(d\sqrt{T \log(N)})$), which is the best regret bound achieved by any computationally efficient algorithm available for this problem in the current literature, and is within a factor of $\sqrt{d}$ (or $\sqrt{\log(N)}$) of the information-theoretic lower bound for this problem.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Thompson sampling remains computationally efficient as long as the argmax over layouts can be solved efficiently.
“This property ensures that Thompson Sampling remains computationally efficient as long as we can efficiently solve arдmax A B ⊤ A,X W [2].”
From An Efficient Bandit Algorithm for Realtime Multivariate Optimization (2017) · cites this paper as [2]
With an efficient oracle, there is an efficient algorithm with regret bound Õ(M^{3/2}√T), the best achieved by a computationally efficient algorithm.
“With an oracle which efficiently solves equation 2, then both [11] and [2] give an efficient algorithm with a regret bound of Õ(M 3/2 √ T ), the best achieved by a computationally efficient algorithm.”
From An Efficient Bandit Algorithm for Realtime Multivariate Optimization (2017) · cites this paper as [2]
Bandit methods have shown impressive empirical performance and can easily incorporate context.
“Bandit methods have shown impressive empirical performance [8] and can easily incorporate context [2,14].”
From An Efficient Bandit Algorithm for Realtime Multivariate Optimization (2017) · cites this paper as [2]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 23
- Abbasi-Yadkori, Yasin, P´ al, D´ avid, and Szepesv´ ari, Csaba. Improved Algorithms for Linear Stochastic Bandits. In NIPS , pp. 2312-2320, 2011.
- Agrawal, Shipra and Goyal, Navin. Analysis of Thompson Sampling for the Multi-armed Bandit Problem. In COLT , 2012.
- Agrawal, Shipra and Goyal, Navin. Thompson Sampling for Contextual Bandits with Linear Payoffs. ICML , 2013a.
- Agrawal, Shipra and Goyal, Navin. Further Optimal Regret Bounds for Thompson Sampling. AISTATS , 2013b.
- Auer, Peter. Using Confidence Bounds for Exploitation-Exploration Trade-offs. Journal of Machine Learning Research , 3:397-422, 2002.
- Auer, Peter, Cesa-Bianchi, Nicol` o, Freund, Yoav, and Schapire, Robert E. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. , 32(1):48-77, 2002.
- Bubeck, S´ ebastien, Cesa-Bianchi, Nicol` o, and Kakade, Sham M. Towards minimax policies for online linear optimization with bandit feedback. Proceedings of the 25th Conference on Learning Theory (COLT) , pp. 1-14, 2012.
- Chapelle, Olivier and Li, Lihong. An Empirical Evaluation of Thompson Sampling. In NIPS , pp. 2249-2257, 2011.
- Chapelle, Olivier and Li, Lihong. Open Problem: Regret Bounds for Thompson Sampling. In COLT , 2012.
- Chu, Wei, Li, Lihong, Reyzin, Lev, and Schapire, Robert E. Contextual Bandits with Linear Payoff Functions. Journal of Machine Learning Research Proceedings Track , 15:208-214, 2011.
- Dani, Varsha, Hayes, Thomas P., and Kakade, Sham M. Stochastic Linear Optimization under Bandit Feedback. In COLT , pp. 355-366, 2008.
- Filippi, Sarah, Capp´ e, Olivier, Garivier, Aur´ elien, and Szepesv´ ari, Csaba. Parametric Bandits: The Generalized Linear Case. In NIPS , pp. 586-594, 2010.
- Graepel, Thore, Candela, Joaquin Qui˜ nonero, Borchert, Thomas, and Herbrich, Ralf. Web-Scale Bayesian Click-Through rate Prediction for Sponsored Search Advertising in Microsoft's Bing Search Engine. In ICML , pp. 13-20, 2010.
- Granmo, O.-C. Solving Two-Armed Bernoulli Bandit Problems Using a Bayesian Learning Automaton. International Journal of Intelligent Computing and Cybernetics (IJICC) , 3(2):207-234, 2010.
- Kaelbling, Leslie Pack. Associative Reinforcement Learning: Functions in kDNF. Machine Learning , 15(3):279-298, 1994.
- Langford, John and Zhang, Tong. The Epoch-Greedy Algorithm for Multiarmed Bandits with Side Information. In NIPS , 2007.
- Ortega, Pedro A. and Braun, Daniel A. Linearly Parametrized Bandits. Journal of Artificial Intelligence Research , 38:475-511, 2010.
- Sarkar, Jyotirmoy. One-armed badit problem with covariates. The Annals of Statistics , 19(4):1978-2002, 1991.
- Strehl, Alexander L., Mesterharm, Chris, Littman, Michael L., and Hirsh, Haym. Experience-efficient learning in associative bandit problems. In ICML , pp. 889-896, 2006.
- Strens, Malcolm J. A. A Bayesian Framework for Reinforcement Learning. In ICML , pp. 943-950, 2000.
- Thompson, William R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika , 25(3-4):285-294, 1933.
- Woodroofe, Michael. A one-armed bandit problem with a concomitant variable. Journal of the American Statistics Association , 74(368):799-806, 1979.
- Wyatt, Jeremy. Exploration and Inference in Learning from Reinforcement . PhD thesis, Department of Artificial Intelligence, University of Edinburgh, 1997.
Cited by
Sorted by citations
An Efficient Bandit Algorithm for Realtime Multivariate Optimization
Hill, D. N., Nassif, H., Liu, Y., Iyer, A., & Vishwanathan, S. V. N. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098184 · Cited by 112 · see citing works
“…problem is to estimate µ while minimizing cumulative regret over T rounds: Ω ( M √ T ) for the regret, along with a matching upper bound [11]. and[2]giveanefficientalgorithmwitha regretbound of ˜ O ( M / √ T ) , Next we will specify how to compute and update a model of µ , generate feature…”
MethodReinforcement learning and bandits for speech and language processing: Tutorial, review and outlook
Lin, B. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.122254 · Cited by 28 · see citing works
- Authors
- Agrawal, S., & Goyal, N.
- Affiliations
- Microsoft Research (India) (IN)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2012
- Pages
- 127-135
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1209.3352
- OpenAlex
- W2166253248
- Cited by
- 600
- References
- 0
- Citations by year
- 2026: 4 · 2025: 20 · 2024: 34 · 2023: 42 · 2022: 37 · 2021: 130 · 2020: 90 · 2019: 79 · 2018: 59 · 2017: 36 · 2016: 24 · 2015: 17 · 2014: 19 · 2013: 8 · 2012: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- International Conference on Machine Learning
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- Thompson sampling, contextual bandits, regret bounds, adaptive adversaries, Bayesian reinforcement learning, multi-armed bandits, information-theoretic lower bounds, online learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
