CoChat

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

Bubeck, Sébastien, Cesa-Bianchi, Nicolò · 2012 · Foundations and Trends® in Machine Learning

The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.

Abstract

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 payoffs process associated with each option. In this monograph, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.

Overview

Integrity signals

Registry

Crossref · 10.1561/2200000024

Cites

9 of 9 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Show all 9 references

Research works printed but not linked: 164

  1. Abbasi-Yadkori, 2011, Advances in Neural Information Processing Systems (NIPS)
  2. Abe, 1999, Proceedings of the International Conference on Machine Learning (ICML)
  3. Abernethy, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
  4. Abernethy, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
  5. Agarwal, 2010, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 9.
  6. Agarwal, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  7. Agarwal, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings Volume 19, 2011.
  8. Agarwal, 2011, Advances in Neural Information Processing Systems (NIPS)
  9. Agrawal, 1995, Sample mean based index policies with O(log n) regret for the multi-armed bandit problem, Advances in Applied Mathematics, 27, 1054
  10. Agrawal, 2012, Analysis of Thompson sampling for the multi-armed bandit problem, Proceedings of the Annual Conference on Learning Theory (COLT), 23
  11. Allenberg, 2006, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  12. Amin, 2011, Bandits, query learning, and the haystack dimension, Proceedings of the Annual Conference on Learning Theory (COLT), 19
  13. Antos, 2008, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  14. Arora, 2012, Proceedings of the International Conference on Machine Learning (ICML)
  15. Arora, 2012, The multiplicative weights update method: A meta-algorithm and applications, Theory of Computing, 8, 121, 10.4086/toc.2012.v008a006 · doi:10.4086/toc.2012.v008a006
  16. Arrow, 1949, Bayes and minimax solutions of sequential decision problems, Econometrica, 213, 10.2307/1905525 · DOI · Paper page
  17. Audibert, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
  18. Audibert, 2010, Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research, 11, 2635
  19. Audibert, 2011, Proceedings of the Annual Conference on Learning Theory (COLT)
  20. Audibert, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  21. Audibert, 2009, Exploration-exploitation trade-off using variance estimates in multi-armed bandits, Theoretical Computer Science, 410, 1876, 10.1016/j.tcs.2009.01.016 · DOI · Paper page
  22. Auer, 2002, Using confidence bounds for exploitation-exploration trade-offs, Journal of Machine Learning Research, 3, 397
  23. Auer, 2002, The non-stochastic multi-armed bandit problem, SIAM Journal on Computing, 32, 48, 10.1137/S0097539701398375 · DOI
  24. Auer, 2010, UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem, Periodica Mathematica Hungarica, 61, 55, 10.1007/s10998-010-3055-6 · DOI
  25. Auer, 2007, Proceedings of the International Conference on Learning Theory (COLT)
  26. Bañós, 1968, On pseudo-games, Annals of Mathematical Statistics, 39, 1932, 10.1214/aoms/1177698023 · DOI
  27. Babaioff, 2010, ACM Conference on Electronic Commerce (EC)
  28. Babaioff, 2009, ACM Conference on Electronic Commerce (EC)
  29. Bach, 2011, Advances in Neural Information Processing Systems (NIPS)
  30. Ball, 1997, Flavors of Geometry, 1
  31. Bartlett, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
  32. Bartók, 2010, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  33. Bartók, 2011, Lecture notes.
  34. Beck, 2003, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, 31, 167, 10.1016/S0167-6377(02)00231-6 · DOI · Paper page
  35. Ben-Tal, 1999, MINERVA Optimization Center Report
  36. Berry, 1997, Bandit problems with infinitely many arms, Annals of Statistics, 25, 2103, 10.1214/aos/1069362389 · DOI
  37. Beygelzimer, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
  38. Beygelzimer, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
  39. Boucheron, 2005, Theory of classification: A survey of recent advances, ESAIM: Probability and Statistics, 9, 323, 10.1051/ps:2005018 · DOI · Paper page
  40. Bubeck, 2010, PhD thesis,Université Lille 1
  41. Bubeck, 2011, Lecture notes
  42. Bubeck, 2012, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 23
  43. Bubeck, 2012, arXiv
  44. Bubeck, 2011, arXiv
  45. Bubeck, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  46. Bubeck, 2009, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  47. Bubeck, 2011, Pure exploration in finitely-armed and continuously-armed bandits, Theoretical Computer Science, 412, 1832, 10.1016/j.tcs.2010.12.059 · DOI · Paper page
  48. Bubeck, 2009, Advances in Neural Information Processing Systems (NIPS)
  49. Bubeck, 2011, X-armed bandits, Journal of Machine Learning Research, 12, 1587
  50. Bubeck, 2012, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedingsvolume 23
  51. Bubeck, 2012, arXiv
  52. Bui, 2011, Advances in Neural Information Processing Systems (NIPS)
  53. Burnetas, 1997, Optimal adaptive policies for Markov decision processes, Mathematics of Operations Research, 222, 10.1287/moor.22.1.222 · DOI · Paper page
  54. Busa-Fekete, 2011, Proceedings of the International Conference on Machine Learning (ICML)
  55. Cappé, 2012, arXiv
  56. Carpentier, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  57. Carpentier, 2011, Advances in Neural Information Processing Systems (NIPS)
  58. Cesa-Bianchi, 2006, Prediction, Learning, and Games, 10.1017/CBO9780511546921 · DOI · Paper page
  59. Cesa-Bianchi, 2012, Combinatorial bandits, Journal of Computer and System Sciences, 78, 1404, 10.1016/j.jcss.2012.01.001 · DOI · Paper page
  60. Cesa-Bianchi, 2005, Minimizing regret with label efficient prediction, IEEE Transactions on Information Theory, 51, 2152, 10.1109/TIT.2005.847729 · DOI
  61. Cesa-Bianchi, 2007, Improved second-order bounds for prediction with expert advice, Machine Learning, 66, 321, 10.1007/s10994-006-5001-7 · DOI
  62. Chapelle, 2011, Advances in Neural Information Processing Systems (NIPS)
  63. Chu, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
  64. Conn, 2009, Introduction to Derivative-Free Optimization, 10.1137/1.9780898718768 · DOI · Paper page
  65. Cope, 2009, Regret and convergence bounds for a class of continuum-armed bandit problems, IEEE Transactions on Automatic Control, 54, 1243, 10.1109/TAC.2009.2019797 · DOI
  66. Coquelin, 2007, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)
  67. Crammer, 2011, Proceedings of the International Conference on Machine Learning (ICML)
  68. Dani, 2008, Advances in Neural Information Processing Systems (NIPS)
  69. Dani, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
  70. Devanur, 2009, ACM Conference on Electronic Commerce (EC)
  71. Dudík, 2011, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)
  72. Even-Dar, 2002, Proceedings of the Annual Conference on Computational Learning Theory (COLT)
  73. Even-Dar, 2006, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, Journal of Machine Learning Research, 7, 1079
  74. Filippi, 2011, Optimally sensing a single channel without prior information: The tiling algorithm and regret bounds, IEEE Journal of Selected Topics in Signal Processing, 5, 68, 10.1109/JSTSP.2010.2058091 · DOI
  75. Filippi, 2010, Advances in Neural Information Processing Systems (NIPS)
  76. Flaxman, 2005, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
  77. Foster, 2012, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)
  78. Foster, 1998, Asymptotic calibration, Biometrika, 85, 379, 10.1093/biomet/85.2.379 · DOI · Paper page
  79. Garivier, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19
  80. Garivier, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  81. Gelly, 2006, INRIA Technical Report
  82. Gittins, 2011, Multi-armed Bandit Allocation Indices, 10.1002/9780470980033 · DOI · Paper page
  83. Gittins, 1979, Bandit processes and dynamic allocation indices, Journal of the Royal Statistical Society. Series B (Methodological), 148, 10.1111/j.2517-6161.1979.tb01068.x · DOI · Paper page
  84. Grove, 2001, General convergence results for linear discriminant updates, Machine Learning, 43, 173, 10.1023/A:1010844028087 · DOI
  85. Grünewälder, 2010, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)
  86. György, 2007, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)
  87. György, 2007, The on-line shortest path problem under partial monitoring, Journal of Machine Learning Research, 8, 2369
  88. Hannan, 1957, Approximation to Bayes risk in repeated play, Contributions to the Theory of Games, 3, 97
  89. Hart, 2000, A simple adaptive procedure leading to correlated equilibrium, Econometrica, 68, 1127, 10.1111/1468-0262.00153 · DOI · Paper page
  90. Hart, 2001, A general class of adaptive strategies, Journal of Economic Theory, 98, 26, 10.1006/jeth.2000.2746 · DOI
  91. Hazan, 2011, Optimization for Machine Learning, 287, 10.7551/mitpress/8996.003.0012 · DOI
  92. Hazan, 2011, Advances in Neural Information Processing Systems (NIPS)
  93. Hazan, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  94. Helmbold, 2009, Learning permutations with exponential weights, Journal of Machine Learning Research, 10, 1705
  95. Herbster, 1998, Tracking the best expert, Machine Learning, 32, 151, 10.1023/A:1007424614876 · DOI · Paper page
  96. Hiriart-Urruty, 2001, Fundamentals of Convex Analysis, 10.1007/978-3-642-56468-0 · DOI · Paper page
  97. Honda, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  98. Hoock, 2010, Proceedings of the European Conference on Genetic Programming (EuroGP)
  99. Juditsky, 2005, Recursive aggregation of estimators by the Mirror Descent algorithm with averaging, Problems of Information Transmission, 41, 368, 10.1007/s11122-006-0005-2 · DOI
  100. Kakade, 2012, Regularization techniques for learning with matrices, Journal of Machine Learning Research, 13, 1865
  101. Kakade, 2003, On the sample complexity of reinforcement learning
  102. Kakade, 2008, Proceedings of the International Conference on Machine Learning (ICML)
  103. Kalai, 2005, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, 71, 291, 10.1016/j.jcss.2004.10.016 · DOI · Paper page
  104. Kale, 2010, Advances in Neural Information Processing Systems (NIPS)
  105. Kanade, 2009, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 5
  106. Kanade, 2012, Proceedings of the Innovations in Theoretical Computer Science Conference
  107. Kaufmann, 2012, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 22
  108. Kaufmann, 2012, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  109. Kearns, 2002, A sparse sampling algorithm for near-optimal planning in large Markovian decision processes, Machine Learning, 49, 193, 10.1023/A:1017932429737 · DOI · Paper page
  110. Kiefer, 1953, Sequential minimax search for a maximum, Proceedings of the American Mathematical Society, 4, 502, 10.1090/S0002-9939-1953-0055639-3 · DOI · Paper page
  111. Kiefer, 1952, Stochastic estimation of the maximum of a regression function, Annals of Mathematical Statistics, 23, 462, 10.1214/aoms/1177729392 · DOI · Paper page
  112. Kivinen, 2001, Relative loss bounds for multidimensional regression problems, Machine Learning, 45, 301, 10.1023/A:1017938623079 · DOI
  113. Kleinberg, 2004, Advances in Neural Information Processing Systems (NIPS)
  114. Kleinberg, 2010, Regret bounds for sleeping experts and bandits, Machine Learning, 80, 245, 10.1007/s10994-010-5178-7 · DOI · Paper page
  115. Kleinberg, 2008, Multi-armed bandits in metric spaces, 10.1145/1374376.1374475 · DOI
  116. Kocsis, 2006, Proceedings of the European Conference on Machine Learning (ECML)
  117. Koolen, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
  118. Lai, 1985, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6, 4, 10.1016/0196-8858(85)90002-8 · DOI · Paper page
  119. Lezaud, 1998, Chernoff-type bound for finite Markov chains, Annals of Applied Probability, 8, 849, 10.1214/aoap/1028903453 · DOI
  120. Li, 2010, Proceedings of the International Conference on World Wide Web (WWW)
  121. Liu, 2010, Dynamic multichannel access with imperfect channel state detection, IEEE Transactions on Signal Processing, 58, 2795, 10.1109/TSP.2010.2041600 · doi:10.1109/tsp.2010.2041600
  122. Mahajan, 2008, Foundations and Applications of Sensor Management, 121, 10.1007/978-0-387-49819-5_6 · DOI · Paper page
  123. Maillard, 2011, JMLR Workshop and Conference Proceedings
  124. Maillard, 2011, JMLR Workshop and Conference Proceedings
  125. Mannor, 2011, Advances in Neural Information Processing Systems (NIPS)
  126. Mannor, 2004, The sample complexity of exploration in the multi-armed bandit problem, Journal of Machine Learning Research, 5, 623
  127. McMahan, 2004, Proceedings of the Annual Conference on Learning Theory (COLT)
  128. McMahan, 2009, Proceedings of the International Conference on Learning Theory (COLT)
  129. Nemirovski, 1979, Efficient methods for large-scale convex optimization problems, Ekonomika i Matematicheskie Metody, 15
  130. Nemirovski, 2009, Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19, 1574, 10.1137/070704277 · DOI · Paper page
  131. Nemirovski, 1983, Problem Complexity and Method Efficiency in Optimization
  132. Nesterov, 2011, CORE Discussion Papers
  133. Ortner, 2012, arXiv
  134. Perchet, 2011, arXiv
  135. Pucci de Farias, 2006, Combining expert advice in reactive environments, Journal of the ACM, 53, 762, 10.1145/1183907.1183911 · doi:10.1145/1183907.1183911
  136. Rakhlin, 2009, Lecture notes on online learning
  137. Rusmevichientong, 2010, Linearly parameterized bandits, Mathematics of Operations Research, 35, 395, 10.1287/moor.1100.0446 · DOI · Paper page
  138. Salomon, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  139. Seldin, 2011, Advances in Neural Information Processing Systems (NIPS)
  140. Shalev-Shwartz, 2007, Online learning: Theory, algorithms, and applications
  141. Slivkins, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19.
  142. Slivkins, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
  143. Srebro, 2011, Advances in Neural Information Processing Systems (NIPS)
  144. Srinivas, 2010, Proceedings of the International Conference on Machine Learning (ICML)
  145. Stoltz, 2005, Incomplete information and internal regret in prediction of individual sequences
  146. Sutton, 1998, Reinforcement Learning: An Introduction
  147. Szepesvári, 2010, Algorithms for Reinforcement Learning, 10.1007/978-3-031-01551-9 · DOI · Paper page
  148. Takimoto, 2003, Paths kernels and multiplicative updates, Journal of Machine Learning Research, 4, 773
  149. Tekin, 2012, Online learning of rested and restless bandits, IEEE Transactions on Information Theory, 58, 5588, 10.1109/TIT.2012.2198613 · DOI
  150. Teytaud, 2009, Advances in Computer Games, 65
  151. Thompson, 1933, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Bulletin of the American Mathematical Society, 25, 285
  152. Uchiya, 2010, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  153. Wald, 1947, Sequential Analysis
  154. Wang, 2005, Arbitrary side observations in bandit problems, Advances in Applied Mathematics, 34, 903, 10.1016/j.aam.2004.10.004 · DOI
  155. Wang, 2005, Bandit problems with side observations, IEEE Transactions on Automatic Control, 50, 338, 10.1109/TAC.2005.844079 · DOI
  156. Wang, 2008, Advances in Neural Information Processing Systems (NIPS)
  157. Warmuth, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
  158. Warmuth, 2008, Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension, Journal of Machine Learning Research, 9, 2287
  159. Wilkens, 2012, ACM Conference on Electronic Commerce (EC)
  160. Yu, 2011, Proceedings of the International Conference on Machine Learning (ICML)
  161. Yu, 2009, Markov decision processes with arbitrary reward processes, Mathematics of Operations Research, 34, 737, 10.1287/moor.1090.0397 · DOI
  162. Yue, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
  163. Yue, 2011, Proceedings of the International Conference on Machine Learning (ICML)
  164. Zinkevich, 2003, Proceedings of the International Conference on Machine Learning (ICML)

Cited by

Items 601–700 of 1,003

Metadata

Authors
Bubeck, S., & Cesa-Bianchi, N.
Affiliations
  • Princeton University (US)
  • Dipartimento di Informatica, Università degli Studi di Milano , Milano 20135,
Corresponding author
Bubeck, Sébastien
Venue
Foundations and Trends® in Machine Learning
Publisher
Emerald
Published
2012-12-12
Volume
5
Issue
1
Pages
1-122
ISSN
  • 1935-8237 (ISSN-L)
  • 1935-8245
OpenAlex
W2950929549
Cited by
1,295
References
4
Citations by year
2026: 63 · 2025: 90 · 2024: 88 · 2023: 127 · 2022: 128 · 2021: 122 · 2020: 172 · 2019: 125 · 2018: 110 · 2017: 89 · 2016: 72 · 2015: 53 · 2014: 39 · 2013: 16 · 2012: 1
FWCI
46.03
Type
journal article
Language
en
Open access
closed
Locations
Foundations and Trends® in Machine Learning (publishedVersion)
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 › Mathematics › Theoretical Computer Science › Optimization and Search Problems
Keywords
multi-armed bandits, regret analysis, exploration-exploitation balance, stochastic bandits, adversarial bandits, contextual bandits, sequential decision making

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.