The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Learning to Optimize via Posterior Sampling
Abstract
This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multiarmed bandit problems. The algorithm, also known as Thompson Sampling and as probability matching, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. This result lets us convert regret bounds developed for UCB algorithms into Bayesian regret bounds for posterior sampling. Our second theoretical contribution is a Bayesian regret bound for posterior sampling that applies broadly and can be specialized to many model classes. This bound depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm Bayesian regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models. Further, our analysis provides insight into performance advantages of posterior sampling, which are highlighted through simulation results that demonstrate performance surpassing recently proposed UCB algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Finite-time Analysis of the Multiarmed Bandit Problem
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002) · Machine Learning · doi:10.1023/a:1013689704352 · Cited by 6,033
Asymptotically efficient adaptive allocation rules
Lai, T. L., & Robbins, H. (1985) · Advances in Applied Mathematics · doi:10.1016/0196-8858(85)90002-8 · Cited by 2,406
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. W. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2182033 · Cited by 1,850
(1998) · Springer Texts in Statistics · doi:10.1007/b98854 · Cited by 1,719
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
(2011) · Cited by 1,000
Multi-Armed Bandit Allocation Indices.
Bather, J. A., & Gittins, J. C. (1990) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2982809 · Cited by 998
Improved Algorithms for Linear Stochastic Bandits
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011) · Cited by 919
Analysis of Thompson Sampling for the multi-armed bandit problem
Agrawal, S., & Goyal, N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.1797 · Cited by 819
Multi‐Armed Bandit Allocation Indices
Gittins, J., Glazebrook, K., & Weber, R. (2011) · Wiley eBooks · doi:10.1002/9780470980033 · Cited by 684
Thompson Sampling for Contextual Bandits with Linear Payoffs
Agrawal, S., & Goyal, N. (2012) · arXiv · doi:10.48550/arxiv.1209.3352 · Cited by 600
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581
Linearly Parameterized Bandits
Rusmevichientong, P., & Tsitsiklis, J. N. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0446 · Cited by 427
A modern Bayesian look at the multi‐armed bandit
Scott, S. L. (2010) · Applied Stochastic Models in Business and Industry · doi:10.1002/asmb.874 · Cited by 406
Multi-armed bandits in metric spaces
Kleinberg, R., Slivkins, A., & Upfal, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374475 · Cited by 396
Computationally Related Problems
Sahni, S. K. (1974) · SIAM Journal on Computing · doi:10.1137/0203021 · Cited by 376
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis
Kaufmann, E., Korda, N., & Munos, R. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-34106-9_18 · Cited by 365
Minimax policies for adversarial and stochastic bandits
Audibert, J.-Y., Est, U. P., & Bubeck, S. (2009) · HAL · Cited by 346
Further Optimal Regret Bounds for Thompson Sampling
Agrawal, S., & Goyal, N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.3353 · Cited by 287
Adaptive Treatment Allocation and the Multi-Armed Bandit Problem
Lai, T. L. (1987) · The Annals of Statistics · doi:10.1214/aos/1176350495 · Cited by 279
Parametric Bandits: The Generalized Linear Case
Filippi, S., Cappé, O., Garivier, A., & Szepesvári, C. (2010) · Cited by 259
Bubeck, S., Munos, R., Stoltz, G., & Szepesvári, C. (2011) · Journal of Machine Learning Research · Cited by 214
Optimistic bayesian sampling in contextual-bandit problems
May, B. C., Korda, N., Lee, A., & Leslie, D. S. (2012) · Lancaster EPrints (Lancaster University) · doi:10.82444/warw.33678499 · Cited by 213
A dynamic allocation index for the discounted multiarmed bandit problem
GITTINS, J. C., & JONES, D. M. (1979) · Biometrika · doi:10.1093/biomet/66.3.561 · Cited by 207
Kullback–Leibler upper confidence bounds for optimal sequential allocation
Cappé, O., Garivier, A., Maillard, O.-A., Munos, R., & Stoltz, G. (2013) · The Annals of Statistics · doi:10.1214/13-aos1119 · Cited by 181
Contextual Bandit Algorithms with Supervised Learning Guarantees
Beygelzimer, A., Langford, J. C., Li, L. C., Reyzin, L., & Schapire, R. E. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.4058 · Cited by 175
The Knowledge Gradient Algorithm for a General Class of Online Learning Problems
Ryzhov, I. O., Powell, W. B., & Frazier, P. I. (2012) · Operations Research · doi:10.1287/opre.1110.0999 · Cited by 159
Stochastic simultaneous optimistic optimizationPreprint
Valko, M., Carpentier, A., & Munos, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.24537 · Cited by 76
Prior-free and prior-dependent regret bounds for Thompson Sampling
Bubeck, S., & Liu, C.-Y. (2014) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2014.6814158 · Cited by 76
Online-to-Confidence-Set Conversions and Application to Sparse Stochastic Bandits
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2012) · Cited by 59
Thompson Sampling: An Optimal Finite Time Analysis
Kaufmann, E., Korda, N., & Munos, R. (2012) · Cited by 19
Bandits, Query Learning, and the Haystack Dimension
Amin, K., Kearns, M. J., & Syed, U. (2011) · Cited by 18
Generalized Thompson Sampling for Contextual BanditsPreprint
Li, L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.7163 · Cited by 17
Open Problem: Regret Bounds for Thompson Sampling
Li, L., & Chapelle, O. (2012) · Conference on Learning Theory · Cited by 15
Cited by
Taking the Human Out of the Loop: A Review of Bayesian Optimization
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & de Freitas, N. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2494218 · Cited by 6,049
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 976
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Deep Exploration via Bootstrapped DQN
Osband, I., Blundell, C., Pritzel, A., & Roy, B. V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04621 · Cited by 434
A Tutorial on Thompson Sampling
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834710 · Cited by 380
Self-citation
Metadata
- Authors
- Russo, D., & Van Roy, B.
- Venue
- Mathematics of Operations Research
- Published
- 2014-11
- Volume
- 39
- Issue
- 4
- Pages
- 1221-1243
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2149721706
- Cited by
- 493
- References
- 34
- FWCI
- 28.75
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.