The DOI matches its Crossref record; 141 of the 141 references it cites were found in a registry or an index.
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Abstract
A multi-armed bandit problem - or, simply, a bandit problem - is a sequential allocation problem defined by a set of actions. At each time step, a unit resource is allocated to an action and some observable payoff is obtained. The goal is to maximize the total payoff obtained in a sequence of allocations. The name bandit refers to the colloquial term for a slot machine (a "one-armed bandit" in American slang). In a casino, a sequential allocation problem is obtained when the player is facing many slot machines at once (a "multi-armed bandit"), and must repeatedly choose where to insert the next coin. Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the 1930s, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this book, the focus is on two extreme cases in which the analysis of regret is particularly simple and elegant: independent and identically distributed payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, it also analyzes some of the most important variants and extensions, such as the contextual bandit model. This monograph is an ideal reference for students and researchers with an interest in bandit problems.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
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
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Bandit Based Monte-Carlo Planning
Kocsis, L., & Szepesvári, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11871842_29 · Cited by 2,855
THOMPSON, W. R. (1933) · Biometrika · doi:10.1093/biomet/25.3-4.285 · Cited by 2,712
A contextual-bandit approach to personalized news article recommendation
Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772758 · Cited by 2,562
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
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
Introduction to Online Convex Optimization
Hazan, E. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831719 · Cited by 813
Information-seeking, curiosity, and attention: computational and neural mechanisms
Gottlieb, J., Oudeyer, P.-Y., Lopes, M., & Baranes, A. (2013) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2013.09.001 · Cited by 784
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Introduction to Online Convex Optimization
Hazan, E. (2016) · Foundations and Trends in Optimization · doi:10.1561/2400000013 · Cited by 747
Online learning: A comprehensive survey
Hoi, S. C. H., Sahoo, D., Lu, J., & Zhao, P. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.04.112 · Cited by 746
Application of Machine Learning in Wireless Networks: Key Techniques and Open Issues
Sun, Y., Peng, M., Zhou, Y., Huang, Y., & Mao, S. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2924243 · Cited by 678
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
Kaufmann, E., Cappé, O., & Garivier, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.4443 · Cited by 661
Humans use directed and random exploration to solve the explore–exploit dilemma.
Wilson, R. C., Geana, A., White, J. M., Ludvig, E. A., & Cohen, J. D. (2014) · Journal of Experimental Psychology: General · doi:10.1037/a0038199 · Cited by 580
Learning to Optimize via Posterior Sampling
Russo, D., & Van Roy, B. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2014.0650 · Cited by 493
Reinforcement learning for control: Performance, stability, and deep approximators
Buşoniu, L., de Bruin, T., Tolić, D., Kober, J., & Palunko, I. (2018) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2018.09.005 · Cited by 463
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
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Duchi, J. C., Jordan, M. I., Wainwright, M. J., & Wibisono, A. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2409256 · Cited by 370
Adaptive Learning-Based Task Offloading for Vehicular Edge Computing Systems
Sun, Y., Guo, X., Song, J., Zhou, S., Jiang, Z., Liu, X., & Niu, Z. (2019) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2019.2895593 · Cited by 369
A unified framework for stochastic optimization
Powell, W. B. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.07.014 · Cited by 314
Multi-Armed Bandit-Based Client Scheduling for Federated Learning
Xia, W., Quek, T. Q. S., Guo, K., Wen, W., Yang, H. H., & Zhu, H. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3008091 · Cited by 313
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Perolat, J., Silver, D., & Graepel, T. (2017) · arXiv · doi:10.48550/arxiv.1711.00832 · Cited by 295
Further Optimal Regret Bounds for Thompson Sampling
Agrawal, S., & Goyal, N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.3353 · Cited by 287
Rabbi, M., Aung, M. H., Zhang, M., & Choudhury, T. (2015) · Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing · doi:10.1145/2750858.2805840 · Cited by 265
Unifying Count-Based Exploration and Intrinsic Motivation
Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., & Munos, R. (2016) · arXiv · doi:10.48550/arxiv.1606.01868 · Cited by 264
Online Decision Making with High-Dimensional Covariates
Bastani, H., & Bayati, M. (2020) · Operations Research · doi:10.1287/opre.2019.1902 · Cited by 263
Fairness in Learning: Classic and Contextual Bandits
Joseph, M., Kearns, M., Morgenstern, J., & Roth, A. (2016) · arXiv · doi:10.48550/arxiv.1605.07139 · Cited by 199
Progress in context-aware recommender systems — An overview
Raza, S., & Ding, C. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2019.01.001 · Cited by 151
Bandit Convex Optimization for Scalable and Dynamic IoT Management
Chen, T., & Giannakis, G. B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2839563 · Cited by 139
PopTherapy: Coping with Stress through Pop-Culture
Paredes, P., Giald-Bachrach, R., Czerwinski, M., Roseway, A., Rowan, K., & Hernandez, J. (2014) · Proceedings of the 8th International Conference on Pervasive Computing Technologies for Healthcare · doi:10.4108/icst.pervasivehealth.2014.255070 · Cited by 152
Minimax Regret Bounds for Reinforcement Learning
Azar, M. G., Osband, I., & Munos, R. (2017) · arXiv · doi:10.48550/arxiv.1703.05449 · Cited by 124
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 113
EX2: Exploration with Exemplar Models for Deep Reinforcement Learning
Fu, J., Co-Reyes, J. D., & Levine, S. (2017) · arXiv · doi:10.48550/arxiv.1703.01260 · Cited by 95
Li, D., Raymond, L., & Bergman, P. (2020) · doi:10.3386/w27736 · Cited by 64
Sublinear regret for learning POMDPs
Xiong, Y., Chen, N., Gao, X., & Zhou, X. (2022) · Production and Operations Management · doi:10.1111/poms.13778 · Cited by 6
Metadata
- Authors
- Bubeck, S.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2012
- OpenAlex
- W2049934117
- Cited by
- 1,404
- References
- 141
- FWCI
- 29.93
- Type
- book
- 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.