Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
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
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
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
Self-citationSome aspects of the sequential design of experiments
Robbins, H. (1952) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1952-09620-8 · Cited by 2,184
Improved Algorithms for Linear Stochastic Bandits
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011) · Cited by 919
Near-optimal Regret Bounds for Reinforcement Learning
(2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1859902 · Cited by 207
Associative Reinforcement Learning using Linear Probabilistic Concepts
Abe, N., & Long, P. M. (1999) · Cited by 60
Beating the adaptive bandit with high probability
Abernethy, J., & Rakhlin, A. (2009) · ScholarlyCommons (University of Pennsylvania) · Cited by 27
Optimal Allocation Strategies for the Dark Pool ProblemPreprint
Agarwal, A., Bartlett, P. L., & Dama, M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.2245 · Cited by 25
Research works printed but not linked: 164
- Abbasi-Yadkori, 2011, Advances in Neural Information Processing Systems (NIPS)
- Abe, 1999, Proceedings of the International Conference on Machine Learning (ICML)
- Abernethy, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
- Abernethy, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
- Agarwal, 2010, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 9.
- Agarwal, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- Agarwal, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings Volume 19, 2011.
- Agarwal, 2011, Advances in Neural Information Processing Systems (NIPS)
- Agrawal, 1995, Sample mean based index policies with O(log n) regret for the multi-armed bandit problem, Advances in Applied Mathematics, 27, 1054
- Agrawal, 2012, Analysis of Thompson sampling for the multi-armed bandit problem, Proceedings of the Annual Conference on Learning Theory (COLT), 23
- Allenberg, 2006, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Amin, 2011, Bandits, query learning, and the haystack dimension, Proceedings of the Annual Conference on Learning Theory (COLT), 19
- Antos, 2008, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Arora, 2012, Proceedings of the International Conference on Machine Learning (ICML)
- 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
- Arrow, 1949, Bayes and minimax solutions of sequential decision problems, Econometrica, 213, 10.2307/1905525 · DOI · Paper page
- Audibert, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
- Audibert, 2010, Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research, 11, 2635
- Audibert, 2011, Proceedings of the Annual Conference on Learning Theory (COLT)
- Audibert, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- 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
- Auer, 2002, Using confidence bounds for exploitation-exploration trade-offs, Journal of Machine Learning Research, 3, 397
- Auer, 2002, The non-stochastic multi-armed bandit problem, SIAM Journal on Computing, 32, 48, 10.1137/S0097539701398375 · DOI
- 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
- Auer, 2007, Proceedings of the International Conference on Learning Theory (COLT)
- Bañós, 1968, On pseudo-games, Annals of Mathematical Statistics, 39, 1932, 10.1214/aoms/1177698023 · DOI
- Babaioff, 2010, ACM Conference on Electronic Commerce (EC)
- Babaioff, 2009, ACM Conference on Electronic Commerce (EC)
- Bach, 2011, Advances in Neural Information Processing Systems (NIPS)
- Ball, 1997, Flavors of Geometry, 1
- Bartlett, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
- Bartók, 2010, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Bartók, 2011, Lecture notes.
- 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
- Ben-Tal, 1999, MINERVA Optimization Center Report
- Berry, 1997, Bandit problems with infinitely many arms, Annals of Statistics, 25, 2103, 10.1214/aos/1069362389 · DOI
- Beygelzimer, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
- Beygelzimer, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
- Boucheron, 2005, Theory of classification: A survey of recent advances, ESAIM: Probability and Statistics, 9, 323, 10.1051/ps:2005018 · DOI · Paper page
- Bubeck, 2010, PhD thesis,Université Lille 1
- Bubeck, 2011, Lecture notes
- Bubeck, 2012, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 23
- Bubeck, 2012, arXiv
- Bubeck, 2011, arXiv
- Bubeck, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- Bubeck, 2009, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- 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
- Bubeck, 2009, Advances in Neural Information Processing Systems (NIPS)
- Bubeck, 2011, X-armed bandits, Journal of Machine Learning Research, 12, 1587
- Bubeck, 2012, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedingsvolume 23
- Bubeck, 2012, arXiv
- Bui, 2011, Advances in Neural Information Processing Systems (NIPS)
- Burnetas, 1997, Optimal adaptive policies for Markov decision processes, Mathematics of Operations Research, 222, 10.1287/moor.22.1.222 · DOI · Paper page
- Busa-Fekete, 2011, Proceedings of the International Conference on Machine Learning (ICML)
- Cappé, 2012, arXiv
- Carpentier, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Carpentier, 2011, Advances in Neural Information Processing Systems (NIPS)
- Cesa-Bianchi, 2006, Prediction, Learning, and Games, 10.1017/CBO9780511546921 · DOI · Paper page
- Cesa-Bianchi, 2012, Combinatorial bandits, Journal of Computer and System Sciences, 78, 1404, 10.1016/j.jcss.2012.01.001 · DOI · Paper page
- Cesa-Bianchi, 2005, Minimizing regret with label efficient prediction, IEEE Transactions on Information Theory, 51, 2152, 10.1109/TIT.2005.847729 · DOI
- Cesa-Bianchi, 2007, Improved second-order bounds for prediction with expert advice, Machine Learning, 66, 321, 10.1007/s10994-006-5001-7 · DOI
- Chapelle, 2011, Advances in Neural Information Processing Systems (NIPS)
- Chu, 2011, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15
- Conn, 2009, Introduction to Derivative-Free Optimization, 10.1137/1.9780898718768 · DOI · Paper page
- 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
- Coquelin, 2007, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)
- Crammer, 2011, Proceedings of the International Conference on Machine Learning (ICML)
- Dani, 2008, Advances in Neural Information Processing Systems (NIPS)
- Dani, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
- Devanur, 2009, ACM Conference on Electronic Commerce (EC)
- Dudík, 2011, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)
- Even-Dar, 2002, Proceedings of the Annual Conference on Computational Learning Theory (COLT)
- Even-Dar, 2006, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, Journal of Machine Learning Research, 7, 1079
- 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
- Filippi, 2010, Advances in Neural Information Processing Systems (NIPS)
- Flaxman, 2005, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Foster, 2012, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)
- Foster, 1998, Asymptotic calibration, Biometrika, 85, 379, 10.1093/biomet/85.2.379 · DOI · Paper page
- Garivier, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19
- Garivier, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Gelly, 2006, INRIA Technical Report
- Gittins, 2011, Multi-armed Bandit Allocation Indices, 10.1002/9780470980033 · DOI · Paper page
- 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
- Grove, 2001, General convergence results for linear discriminant updates, Machine Learning, 43, 173, 10.1023/A:1010844028087 · DOI
- Grünewälder, 2010, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)
- György, 2007, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)
- György, 2007, The on-line shortest path problem under partial monitoring, Journal of Machine Learning Research, 8, 2369
- Hannan, 1957, Approximation to Bayes risk in repeated play, Contributions to the Theory of Games, 3, 97
- Hart, 2000, A simple adaptive procedure leading to correlated equilibrium, Econometrica, 68, 1127, 10.1111/1468-0262.00153 · DOI · Paper page
- Hart, 2001, A general class of adaptive strategies, Journal of Economic Theory, 98, 26, 10.1006/jeth.2000.2746 · DOI
- Hazan, 2011, Optimization for Machine Learning, 287, 10.7551/mitpress/8996.003.0012 · DOI
- Hazan, 2011, Advances in Neural Information Processing Systems (NIPS)
- Hazan, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- Helmbold, 2009, Learning permutations with exponential weights, Journal of Machine Learning Research, 10, 1705
- Herbster, 1998, Tracking the best expert, Machine Learning, 32, 151, 10.1023/A:1007424614876 · DOI · Paper page
- Hiriart-Urruty, 2001, Fundamentals of Convex Analysis, 10.1007/978-3-642-56468-0 · DOI · Paper page
- Honda, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- Hoock, 2010, Proceedings of the European Conference on Genetic Programming (EuroGP)
- 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
- Kakade, 2012, Regularization techniques for learning with matrices, Journal of Machine Learning Research, 13, 1865
- Kakade, 2003, On the sample complexity of reinforcement learning
- Kakade, 2008, Proceedings of the International Conference on Machine Learning (ICML)
- 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
- Kale, 2010, Advances in Neural Information Processing Systems (NIPS)
- Kanade, 2009, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 5
- Kanade, 2012, Proceedings of the Innovations in Theoretical Computer Science Conference
- Kaufmann, 2012, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 22
- Kaufmann, 2012, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- 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
- 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
- Kiefer, 1952, Stochastic estimation of the maximum of a regression function, Annals of Mathematical Statistics, 23, 462, 10.1214/aoms/1177729392 · DOI · Paper page
- Kivinen, 2001, Relative loss bounds for multidimensional regression problems, Machine Learning, 45, 301, 10.1023/A:1017938623079 · DOI
- Kleinberg, 2004, Advances in Neural Information Processing Systems (NIPS)
- Kleinberg, 2010, Regret bounds for sleeping experts and bandits, Machine Learning, 80, 245, 10.1007/s10994-010-5178-7 · DOI · Paper page
- Kleinberg, 2008, Multi-armed bandits in metric spaces, 10.1145/1374376.1374475 · DOI
- Kocsis, 2006, Proceedings of the European Conference on Machine Learning (ECML)
- Koolen, 2010, Proceedings of the Annual Conference on Learning Theory (COLT)
- Lai, 1985, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6, 4, 10.1016/0196-8858(85)90002-8 · DOI · Paper page
- Lezaud, 1998, Chernoff-type bound for finite Markov chains, Annals of Applied Probability, 8, 849, 10.1214/aoap/1028903453 · DOI
- Li, 2010, Proceedings of the International Conference on World Wide Web (WWW)
- 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
- Mahajan, 2008, Foundations and Applications of Sensor Management, 121, 10.1007/978-0-387-49819-5_6 · DOI · Paper page
- Maillard, 2011, JMLR Workshop and Conference Proceedings
- Maillard, 2011, JMLR Workshop and Conference Proceedings
- Mannor, 2011, Advances in Neural Information Processing Systems (NIPS)
- Mannor, 2004, The sample complexity of exploration in the multi-armed bandit problem, Journal of Machine Learning Research, 5, 623
- McMahan, 2004, Proceedings of the Annual Conference on Learning Theory (COLT)
- McMahan, 2009, Proceedings of the International Conference on Learning Theory (COLT)
- Nemirovski, 1979, Efficient methods for large-scale convex optimization problems, Ekonomika i Matematicheskie Metody, 15
- Nemirovski, 2009, Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19, 1574, 10.1137/070704277 · DOI · Paper page
- Nemirovski, 1983, Problem Complexity and Method Efficiency in Optimization
- Nesterov, 2011, CORE Discussion Papers
- Ortner, 2012, arXiv
- Perchet, 2011, arXiv
- 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
- Rakhlin, 2009, Lecture notes on online learning
- Rusmevichientong, 2010, Linearly parameterized bandits, Mathematics of Operations Research, 35, 395, 10.1287/moor.1100.0446 · DOI · Paper page
- Salomon, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Seldin, 2011, Advances in Neural Information Processing Systems (NIPS)
- Shalev-Shwartz, 2007, Online learning: Theory, algorithms, and applications
- Slivkins, 2011, Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19.
- Slivkins, 2008, Proceedings of the Annual Conference on Learning Theory (COLT)
- Srebro, 2011, Advances in Neural Information Processing Systems (NIPS)
- Srinivas, 2010, Proceedings of the International Conference on Machine Learning (ICML)
- Stoltz, 2005, Incomplete information and internal regret in prediction of individual sequences
- Sutton, 1998, Reinforcement Learning: An Introduction
- Szepesvári, 2010, Algorithms for Reinforcement Learning, 10.1007/978-3-031-01551-9 · DOI · Paper page
- Takimoto, 2003, Paths kernels and multiplicative updates, Journal of Machine Learning Research, 4, 773
- Tekin, 2012, Online learning of rested and restless bandits, IEEE Transactions on Information Theory, 58, 5588, 10.1109/TIT.2012.2198613 · DOI
- Teytaud, 2009, Advances in Computer Games, 65
- 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
- Uchiya, 2010, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Wald, 1947, Sequential Analysis
- Wang, 2005, Arbitrary side observations in bandit problems, Advances in Applied Mathematics, 34, 903, 10.1016/j.aam.2004.10.004 · DOI
- Wang, 2005, Bandit problems with side observations, IEEE Transactions on Automatic Control, 50, 338, 10.1109/TAC.2005.844079 · DOI
- Wang, 2008, Advances in Neural Information Processing Systems (NIPS)
- Warmuth, 2011, Proceedings of the International Conference on Algorithmic Learning Theory (ALT)
- Warmuth, 2008, Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension, Journal of Machine Learning Research, 9, 2287
- Wilkens, 2012, ACM Conference on Electronic Commerce (EC)
- Yu, 2011, Proceedings of the International Conference on Machine Learning (ICML)
- Yu, 2009, Markov decision processes with arbitrary reward processes, Mathematics of Operations Research, 34, 737, 10.1287/moor.1090.0397 · DOI
- Yue, 2009, Proceedings of the Annual Conference on Learning Theory (COLT)
- Yue, 2011, Proceedings of the International Conference on Machine Learning (ICML)
- Zinkevich, 2003, Proceedings of the International Conference on Machine Learning (ICML)
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
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
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
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
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
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
Derivative-free optimization methods
Larson, J., Menickelly, M., & Wild, S. M. (2019) · Acta Numerica · doi:10.1017/s0962492919000060 · Cited by 381
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
Wu, Q., Zhang, H., Gao, X., He, P., Weng, P., Gao, H., & Chen, G. (2019) · The World Wide Web Conference · doi:10.1145/3308558.3313442 · Cited by 271
Inherent Tradeoffs in the Fair Determination of Risk Scores
(2023) · The Societal Impacts of Algorithmic Decision-Making · doi:10.1145/3603195.3603197 · Cited by 310
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
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
Non-stochastic Best Arm Identification and Hyperparameter Optimization
Jamieson, K., & Talwalkar, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.07943 · Cited by 232
Learning-based optimization of cache content in a small cell base station
Blasco, P., & Gunduz, D. (2014) · 2014 IEEE International Conference on Communications (ICC) · doi:10.1109/icc.2014.6883600 · Cited by 298
A Survey of Graph Neural Networks for Social Recommender Systems
Sharma, K., Lee, Y.-C., Nambi, S., Salian, A., Shah, S., Kim, S.-W., & Kumar, S. (2024) · ACM Computing Surveys · doi:10.1145/3661821 · Cited by 268
Provably Efficient Reinforcement Learning with Linear Function Approximation
Jin, C., Yang, Z., Wang, Z., & Jordan, M. I. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.1309 · Cited by 314
An Information-Theoretic Analysis of Thompson SamplingPreprint
Russo, D., & Roy, B. V. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.5341 · Cited by 286
Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2277869 · Cited by 244
Self-citationMunos, R. (2014) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000038 · Cited by 233
Hermes: Latency Optimal Task Assignment for Resource-constrained Mobile Computing
Kao, Y.-H., Krishnamachari, B., Ra, M.-R., & Bai, F. (2017) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2017.2679712 · Cited by 241
Online Network Revenue Management Using Thompson Sampling
Ferreira, K. J., Simchi-Levi, D., & Wang, H. (2018) · Operations Research · doi:10.1287/opre.2018.1755 · Cited by 243
Regret in Online Combinatorial Optimization
Audibert, J.-Y., Bubeck, S., & Lugosi, G. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2013.0598 · Cited by 208
Self-citationBalancing exploration and exploitation with information and randomization
Wilson, R. C., Bonawitz, E., Costa, V. D., & Ebitz, R. B. (2021) · Current Opinion in Behavioral Sciences · doi:10.1016/j.cobeha.2020.10.001 · Cited by 215
Badanidiyuru, A., Kleinberg, R., & Slivkins, A. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.30 · Cited by 199
Quantum circuit architecture search for variational quantum algorithms
Du, Y., Huang, T., You, S., Hsieh, M.-H., & Tao, D. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00570-y · Cited by 184
Automatic Prompt Optimization with “Gradient Descent” and Beam Search
Pryzant, R., Iter, D., Li, J., Lee, Y., Zhu, C., & Zeng, M. (2023) · Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2023.emnlp-main.494 · Cited by 191
Introduction to Reinforcement Learning
Ding, Z., Huang, Y., Yuan, H., & Dong, H. (2020) · Deep Reinforcement Learning · doi:10.1007/978-981-15-4095-0_2 · Cited by 165
Learning in games with continuous action sets and unknown payoff functions
Mertikopoulos, P., & Zhou, Z. (2019) · Mathematical Programming · doi:10.1007/s10107-018-1254-8 · Cited by 182
Data-Oriented Mobile Crowdsensing: A Comprehensive Survey
Liu, Y., Kong, L., & Chen, G. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2910855 · Cited by 181
Linear Thompson sampling revisited
Abeille, M., & Lazaric, A. (2017) · Electronic Journal of Statistics · doi:10.1214/17-ejs1341si · Cited by 179
Offline Multi-Action Policy Learning: Generalization and Optimization
Zhou, Z., Athey, S. C., & Wager, S. (2022) · Operations Research · doi:10.1287/opre.2022.2271 · Cited by 284
Automating model search for large scale machine learning
Sparks, E., Talwalkar, A., Haas, D., Franklin, M. J. M., Jordan, M. I., & Kraska, T. (2015) · ACM Symposium on Cloud Computing (SoCC) · doi:10.1145/2806777.2806945 · Cited by 182
Explore First, Exploit Next: The True Shape of Regret in Bandit Problems
Garivier, A., Ménard, P., & Stoltz, G. (2018) · Mathematics of Operations Research · doi:10.1287/moor.2017.0928 · Cited by 165
When Will Workers Follow an Algorithm? A Field Experiment with a Retail Business
Kawaguchi, K. (2018) · Management Science · doi:10.1287/mnsc.2020.3599 · Cited by 174
Achieving differential privacy of data disclosure in the smart grid
Zhao, J. Y., Jung, T., Wang, Y., & Li, X. (2014) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2014.6847974 · Cited by 155
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
Parallel Gaussian process optimization with upper confidence bound and pure explorationPreprint
Contal, E., Buffoni, D., Robicquet, R., & Vayatis, N. (2013) · Cited by 151
Badanidiyuru, A., Kleinberg, R., & Slivkins, A. (2018) · Journal of the ACM · doi:10.1145/3164539 · Cited by 162
MNL-Bandit: A Dynamic Learning Approach to Assortment Selection
Agrawal, S., Avadhanula, V., Goyal, V., & Zeevi, A. J. (2019) · Operations Research · doi:10.1287/opre.2018.1832 · Cited by 157
Cohen, M. C., Lobel, I., & Leme, R. P. (2020) · Management Science · doi:10.1287/mnsc.2019.3485 · Cited by 218
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
Cost-friendly Differential Privacy for Smart Meters: Exploiting the Dual Roles of the Noise
Zhang, Z., Qin, Z., Zhu, L., Weng, J., & Ren, K. (2016) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2016.2585963 · Cited by 139
Efficient Beam Alignment in Millimeter Wave Systems Using Contextual Bandits
Hashemi, M., Sabharwal, A., Koksal, C. E., & Shroff, N. B. (2018) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2018.8486279 · Cited by 136
Online Evaluation for Information Retrieval
Hofmann, K., Li, L. C., & Radlinski, F. (2016) · now publishers, Inc. eBooks · doi:10.1561/1500000051 · Cited by 162
Multi-armed bandits with application to 5G small cells
Maghsudi, S., & Hossain, E. (2016) · IEEE Wireless Communications · doi:10.1109/mwc.2016.7498076 · Cited by 132
Adaptive Treatment Assignment in Experiments for Policy Choice
Kasy, M., & Sautmann, A. (2019) · Econometrica · doi:10.2139/ssrn.3434834 · Cited by 151
Bandits with concave rewards and convex knapsacks
Agrawal, S., & Devanur, N. R. (2014) · ACM Conference on Economics and Computation (EC) · doi:10.1145/2600057.2602844 · Cited by 138
Online Learning for Position-Aided Millimeter Wave Beam Training
Va, V., Shimizu, T., Bansal, G., & Heath, R. W. (2019) · IEEE Access · doi:10.1109/access.2019.2902372 · Cited by 133
Learning to Optimize via Information-Directed Sampling
Russo, D., & Roy, B. V. (2017) · Operations Research · doi:10.1287/opre.2017.1663 · Cited by 141
Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds
Agrawal, S., & Jia, R. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2022.1266 · Cited by 131
Stochastic bandits robust to adversarial corruptions
Lykouris, T., Mirrokni, V., & Leme, R. P. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188918 · Cited by 133
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
“We now define a stochastic contextual multi-armed bandit problem [5].”
BackgroundMay AI? Design Ideation with Cooperative Contextual Bandits
Koch, J., Lucero, A., Hegemann, L., & Oulasvirta, A. (2019) · CHI Conference on Human Factors in Computing Systems · doi:10.1145/3290605.3300863 · Cited by 174
Review on ranking and selection: A new perspective
Hong, L. J., Fan, W., & Luo, J. (2021) · Frontiers of Engineering Management · doi:10.1007/s42524-021-0152-6 · Cited by 110
Kernel-based Methods for Bandit Convex Optimization
Bubeck, S., Lee, Y. T., & Eldan, R. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055403 · Cited by 104
Self-citationBeam Alignment and Tracking for Millimeter Wave Communications via Bandit Learning
Zhang, J., Huang, Y., Zhou, Y., & You, X. (2020) · IEEE Transactions on Communications · doi:10.1109/tcomm.2020.2988256 · Cited by 106
Bayesian Incentive-Compatible Bandit Exploration
Mansour, Y., Slivkins, A., & Syrgkanis, V. (2015) · ACM Conference on Economics and Computation (EC) · doi:10.1145/2764468.2764508 · Cited by 107
Optimal Exploration–Exploitation in a Multi-armed Bandit Problem with Non-stationary Rewards
Besbes, O., Gur, Y., & Zeevi, A. J. (2019) · Stochastic Systems · doi:10.1287/stsy.2019.0033 · Cited by 111
Azevedo, E. M., Deng, A., Olea, J. L. M., Rao, J. M., & Weyl, E. G. (2020) · Journal of Political Economy · doi:10.1086/710607 · Cited by 140
Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
Yu, C.-K., van der Schaar, M., & Sayed, A. H. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2695451 · Cited by 96
A Change-Detection Based Framework for Piecewise-Stationary Multi-Armed Bandit Problem
Liu, F., Lee, J., & Shroff, N. B. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11746 · Cited by 105
Stochastic Dual Averaging for Decentralized Online Optimization on Time-Varying Communication Graphs
Lee, S., Nedić, A., & Raginsky, M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2650563 · Cited by 97
A Distributed Online Pricing Strategy for Demand Response Programs
Li, P., Wang, H., & Zhang, B. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2739021 · Cited by 92
Multi-Armed-Bandit-Based Spectrum Scheduling Algorithms in Wireless Networks: A Survey
Li, F., Yu, D., Yang, H., Yu, J., Karl, H., & Cheng, X. (2020) · IEEE Wireless Communications · doi:10.1109/mwc.001.1900280 · Cited by 92
Understanding Doctor Decision Making: The Case of Depression Treatment
Currie, J., & MacLeod, W. B. (2020) · Econometrica · doi:10.3982/ecta16591 · Cited by 96
Subset Selection Via Implicit Utilitarian Voting
Caragiannis, I., Nath, S., Procaccia, A. D., & Shah, N. (2017) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5282 · Cited by 89
Combinatorial Sleeping Bandits With Fairness Constraints
Li, F., Liu, J., & Ji, B. (2019) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2019.2954310 · Cited by 91
Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance
Wei, W., & Liu, L. (2024) · ACM Computing Surveys · doi:10.1145/3645102 · Cited by 128
Learning-Aided Network Association for Hybrid Indoor LiFi-WiFi Systems
Wang, J., Jiang, C., Zhang, H., Zhang, X., Leung, V. C. M., & Hanzo, L. (2017) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2017.2778345 · Cited by 86
Hassan, U. U., & Curry, E. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2016.03.022 · Cited by 85
Multi-Armed Bandit Learning in IoT Networks: Learning Helps Even in Non-stationary Settings
Bonnefoi, R., Besson, L., Moy, C., Kaufmann, E., & Palicot, J. (2018) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-319-76207-4_15 · Cited by 89
Risk-Averse Multi-Armed Bandit Problems Under Mean-Variance Measure
Vakili, S., & Zhao, Q. Q. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2592622 · Cited by 88
Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms
Landgren, P., Srivastava, V., & Leonard, N. E. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798264 · Cited by 90
Ho, C.-J., Slivkins, A., & Vaughan, J. W. (2016) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4940 · Cited by 87
Modeling Human Decision Making in Generalized Gaussian Multiarmed Bandits
Reverdy, P. B., Srivastava, V., & Leonard, N. E. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2307024 · Cited by 84
Combinatorial Multi-armed Bandits for Real-Time Strategy Games
Ontañón, S. (2017) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5398 · Cited by 80
Multi‐Armed Bandits, Gittins Index, and its Calculation
Chakravorty, J., & Mahajan, A. (2014) · Wiley eBooks · doi:10.1002/9781118596333.ch24 · Cited by 82
Jia, L., Qi, N., Su, Z., Chu, F., Fang, S., Wong, K., & Chae, C. (2024) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2024.3482973 · Cited by 87
Indifference-Zone-Free Selection of the Best
Fan, W., Hong, L. J., & Nelson, B. L. (2016) · Operations Research · doi:10.1287/opre.2016.1530 · Cited by 79
Bandit-based Communication-Efficient Client Selection Strategies for Federated Learning
Cho, Y. J., Gupta, S., Joshi, G., & Yağan, O. (2020) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf51394.2020.9443523 · Cited by 82
Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
Li, Y., Wang, Y., & Zhou, Y. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3267732 · Cited by 78
Informational confidence bounds for self-normalized averages and applications
Garivier, A. (2013) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2013.6691311 · Cited by 79
Efficient Ranking And Selection In Parallel Computing Environments
Ni, E. C. (2016) · eCommons (Cornell University) · Cited by 75
Balasubramanian, K., & Ghadimi, S. (2021) · Foundations of Computational Mathematics · doi:10.1007/s10208-021-09499-8 · Cited by 85
Machine Intelligence in Healthcare and Medical Cyber Physical Systems: A Survey
Shishvan, O. R., Zois, D., & Soyata, T. (2018) · IEEE Access · doi:10.1109/access.2018.2866049 · Cited by 78
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
Self-citationParallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration
Contal, E., Buffoni, D., Robicquet, A., & Vayatis, N. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40988-2_15 · Cited by 85
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
Alon, N., Cesa‐Bianchi, N., Gentile, C., Mannor, S., Mansour, Y., & Shamir, O. (2017) · SIAM Journal on Computing · doi:10.1137/140989455 · Cited by 71
Self-citationQuality-Aware Pricing for Mobile Crowdsensing
Han, K., Huang, H., & Luo, J. (2018) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2018.2846569 · Cited by 71
Federated-Learning-Based Client Scheduling for Low-Latency Wireless Communications
Xia, W., Wen, W., Wong, K., Quek, T. Q. S., Zhang, J., & Zhu, H. (2021) · IEEE Wireless Communications · doi:10.1109/mwc.001.2000252 · Cited by 72
Shi, C., & Shen, C. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i11.17156 · Cited by 126
Distributed cooperative decision making in multi-agent multi-armed bandits
Landgren, P., Srivastava, V., & Leonard, N. E. (2021) · Automatica · doi:10.1016/j.automatica.2020.109445 · Cited by 73
Differentially Private Unknown Worker Recruitment for Mobile Crowdsensing Using Multi-Armed Bandits
Zhao, H., Xiao, M., Wu, J., Xu, Y., Huang, H., & Zhang, S. (2020) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2020.2990221 · Cited by 69
BLOT: Bandit Learning-Based Offloading of Tasks in Fog-Enabled Networks
Zhu, Z., Liu, T., Yang, Y., & Luo, X. (2019) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2927978 · Cited by 68
Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603203 · Cited by 67
The Internet of Federated Things (IoFT)
Kontar, R. A., Shi, N., Yue, X., Chung, S., Byon, E., Chowdhury, M., Jin, J. J., Kontar, W., Masoud, N., Nouiehed, M., et al. (2021) · IEEE Access · doi:10.1109/access.2021.3127448 · Cited by 86
Online decision making in crowdsourcing markets: theoretical challenges
Slivkins, A., & Vaughan, J. W. (2014) · ACM SIGecom Exchanges · doi:10.1145/2692359.2692364 · Cited by 69
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
- ORCID
- 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
- Semantic Scholar
- cf8543cc0e49377dae2e83d2941db15d8708f00e
- 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.