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
Items 201–300 of 1,003
Zois, D. (2016) · IEEE World Forum on Internet of Things (WF-IoT) · doi:10.1109/wf-iot.2016.7845446 · Cited by 41
Handel, B., & Misra, K. (2015) · Marketing Science · doi:10.1287/mksc.2015.0914 · Cited by 36
Deep Controlled Learning for Inventory Control
Temizöz, T., Imdahl, C., Dijkman, R., Lamghari-Idrissi, D., & van Jaarsveld, W. L. (2025) · European Journal of Operational Research · doi:10.1016/j.ejor.2025.01.026 · Cited by 45
BLISS: Budget LImited robuSt crowdSensing through online learning
Han, K., Zhang, C., & Luo, J. (2014) · IEEE International Conference on Sensing, Communication, and Networking (SECON) · doi:10.1109/sahcn.2014.6990395 · Cited by 34
Online Learning-Assisted VNF Service Chain Scaling with Network Uncertainties
Wang, X., Wu, C., Le, F., & Lau, F. C. M. (2017) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud.2017.34 · Cited by 35
Advancements in Dueling Bandits
Sui, Y., Zoghi, M., Hofmann, K., & Yue, Y. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/776 · Cited by 78
Link Rate Selection using Constrained Thompson Sampling
Gupta, H., Eryılmaz, A., & Srikant, R. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737610 · Cited by 34
Learning in Auctions: Regret is Hard, Envy is Easy
Daskalakis, C., & Syrgkanis, V. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.31 · Cited by 34
Multi-Armed Bandits: Theory and Applications to Online Learning in Networks
Zhao, Q. Q. (2019) · Synthesis lectures on communication networks · doi:10.2200/s00941ed2v01y201907cnt022 · Cited by 40
Online Learning and Optimization for Revenue Management Problems with Add-on Discounts
Simchi‐Levi, D., Sun, R., & Zhang, H. (2022) · Management Science · doi:10.1287/mnsc.2021.4222 · Cited by 33
Offline Simulation Online Application: A New Framework of Simulation-Based Decision Making
Hong, L. J., & Jiang, G. (2019) · Asia Pacific Journal of Operational Research · doi:10.1142/s0217595919400153 · Cited by 33
Approximate Bayesian Inference
Alquier, P. (2020) · Entropy · doi:10.3390/e22111272 · Cited by 44
Surveillance in an abruptly changing world via multiarmed bandits
Srivastava, V., Reverdy, P. B., & Leonard, N. E. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039462 · Cited by 33
Bayesian Contextual Bandits for Hyper Parameter Optimization
Sui, G., & Yu, Y. H. (2020) · IEEE Access · doi:10.1109/access.2020.2977129 · Cited by 33
Pure Exploration of Multi-armed Bandit Under Matroid ConstraintsPreprint
Chen, L., Gupta, A., & Li, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07162 · Cited by 32
Learning Online Trends for Interactive Query Auto-Completion
Wang, Y., Ouyang, H. J., Deng, H., & Chang, Y. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2738639 · Cited by 38
Ma, W. (2018) · Mathematics of Operations Research · doi:10.1287/moor.2017.0884 · Cited by 31
Regional Multi-Armed Bandits With Partial Informativeness
Wang, Z., Zhou, R., & Shen, C. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2870383 · Cited by 31
Video Big Data Retrieval Over Media Cloud: A Context-Aware Online Learning Approach
Feng, Y., Zhou, P., Xu, J., Ji, S., & Wu, D. O. (2018) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2018.2885237 · Cited by 31
The dynamics of explore–exploit decisions reveal a signal-to-noise mechanism for random exploration
Feng, S. F., Wang, S., Zarnescu, S., & Wilson, R. C. (2021) · Scientific Reports · doi:10.1038/s41598-021-82530-8 · Cited by 40
Tailoring data source distributions for fairness-aware data integration
Nargesian, F., Asudeh, A., & Jagadish, H. V. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3476249.3476299 · Cited by 53
On optimal foraging and multi-armed bandits
Srivastava, V., Reverdy, P. B., & Leonard, N. E. (2013) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2013.6736565 · Cited by 31
Sequential Monte Carlo for inference in nonlinear state space models
Dahlin, J. (2014) · Linköping University Electronic Press eBooks · doi:10.3384/lic.diva-106752 · Cited by 35
Wang, Y., Reyes, K. G., Brown, K. A., Mirkin, C. A., & Powell, W. B. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/140971117 · Cited by 31
Chen, Y., Bernstein, A., Devraj, A. M., & Meyn, S. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147814 · Cited by 33
Multiagent Online Learning in Time-Varying Games
Duvocelle, B., Mertikopoulos, P., Staudigl, M., & Vermeulen, D. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2022.1283 · Cited by 39
Sherlock: A Multi-Objective Design Space Exploration Framework
Gautier, Q., Althoff, A., Crutchfield, C. L., & Kastner, R. (2022) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/3511472 · Cited by 35
Online Tuning of EASY-Backfilling using Queue Reordering Policies
Gaussier, É., Lelong, J., Reis, V., & Trystram, D. (2018) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2018.2820699 · Cited by 33
Deshpande, Y., Javanmard, A., & Mehrabi, M. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1979011 · Cited by 53
Optimal Learning for Urban Delivery Fleet Allocation
Huang, Y., Zhao, L., Powell, W. B., Tong, Y., & Ryzhov, I. O. (2019) · Transportation Science · doi:10.1287/trsc.2018.0861 · Cited by 29
Deep Reinforcement Learning based Wireless Network Optimization: A Comparative Study
Yang, K., Shen, C., & Liu, T. (2020) · IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infocomwkshps50562.2020.9162925 · Cited by 34
Active learning for optimal intervention design in causal models
Zhang, J., Cammarata, L. V., Squires, C., Sapsis, T. P., & Uhler, C. (2023) · Nature Machine Intelligence · doi:10.1038/s42256-023-00719-0 · Cited by 40
Generalized Global Bandit and Its Application in Cellular Coverage Optimization
Shen, C., Zhou, R., Tekin, C., & van der Schaar, M. (2018) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2018.2798164 · Cited by 29
Kleinberg, R. D., Leyton-Brown, K., & Lucier, B. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/281 · Cited by 45
Stratification Trees for Adaptive Randomisation in Randomised Controlled Trials
Tabord‐Meehan, M. (2022) · The Review of Economic Studies · doi:10.1093/restud/rdac083 · Cited by 34
Landgren, P., Srivastava, V., & Leonard, N. E. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619744 · Cited by 28
A Fast Beam Searching Scheme in mmWave Communications for High-Speed Trains
Cheng, M., Wang, J.-B., Wang, J., Lin, M., Wu, Y., & Zhu, H. (2019) · International Conference on Communications · doi:10.1109/icc.2019.8761773 · Cited by 28
Gasnikov, A. V., Lagunovskaya, A., Usmanova, I., & Fedorenko, F. (2016) · Automation and Remote Control · doi:10.1134/s0005117916110114 · Cited by 35
Dynamic Joint Assortment and Pricing Optimization With Demand LearningPreprint
Miao, S., & Chao, X. (2018) · SSRN Electronic Journal · doi:10.2139/ssrn.3173267 · Cited by 28
Adaptive Memory Replay for Continual Learning
Smith, J. S., Valkov, L., Halbe, S., Gutta, V., Feris, R., Kira, Z., & Karlinsky, L. (2024) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw63382.2024.00364 · Cited by 68
Personalized optimization with user’s feedback
Simonetto, A., Dall’Anese, E., Monteil, J., & Bernstein, A. (2021) · Automatica · doi:10.1016/j.automatica.2021.109767 · Cited by 29
Bandits with Global Convex Constraints and Objective
Agrawal, S., & Devanur, N. R. (2019) · Operations Research · doi:10.1287/opre.2019.1840 · Cited by 31
On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
Shahrampour, S., Noshad, M., & Tarokh, V. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2706192 · Cited by 27
GRAPH-BASED RECOMMENDATION SYSTEM
Yang, K., & Toni, L. (2018) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2018.8646359 · Cited by 27
When Robot Personalisation Does Not Help: Insights from a Robot-Supported Learning Study
Gao, Y., Barendregt, W., Obaid, M., & Castellano, G. (2018) · IEEE RO-MAN · doi:10.1109/roman.2018.8525832 · Cited by 40
Faster Activity and Data Detection in Massive Random Access: A Multiarmed Bandit Approach
Dong, J., Zhang, J., Shi, Y., & Wang, J. H. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3142185 · Cited by 28
Nonparametric Pricing Analytics with Customer CovariatesPreprint
Chen, N., & Gallego, G. (2018) · SSRN Electronic Journal · doi:10.2139/ssrn.3172697 · Cited by 29
Zangirolami, V., & Borrotti, M. (2024) · Knowledge-Based Systems · doi:10.1016/j.knosys.2024.111663 · Cited by 32
Online Pricing for Mobile Crowdsourcing with Multi-Minded Users
Han, K., He, Y., Tan, H., Tang, S., Huang, H., & Luo, J. (2017) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/3084041.3084058 · Cited by 26
Personalized Menu Optimization with Preference Updater: A Boston Case Study
Song, X., Danaf, M., Atasoy, B., & Ben-Akiva, M. E. (2018) · Transportation Research Record Journal of the Transportation Research Board · doi:10.1177/0361198118758674 · Cited by 27
A Non-Stationary Online Learning Approach to Mobility Management
Zhou, Y., Shen, C., & van der Schaar, M. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2893168 · Cited by 26
Toward Optimal Adaptive Online Shortest Path Routing With Acceleration Under Jamming Attack
Zhou, P., Xu, J., Wang, W., Hu, Y., Wu, D. O., & Ji, S. (2019) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2019.2930464 · Cited by 28
Intelligent Task Caching in Edge Cloud via Bandit Learning
Miao, Y., Hao, Y., Chen, M., Gharavi, H., & Hwang, K. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.3047417 · Cited by 26
Learning-Based Decentralized Offloading Decision Making in an Adversarial Environment
Cho, B., & Xiao, Y. (2021) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2021.3115899 · Cited by 29
SAGA: A Scalable Framework for Optimizing Data Cleaning Pipelines for Machine Learning Applications
Siddiqi, S., Kern, R., & Böehm, M. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3617338 · Cited by 48
Local Clustering in Contextual Multi-Armed Bandits
Ban, Y., & He, J. (2021) · International World Wide Web Conference (WWW) · doi:10.1145/3442381.3450058 · Cited by 27
One for All and All for One: Distributed Learning of Fair Allocations With Multi-Player Bandits
Bistritz, I., Baharav, T. Z., Leshem, A., & Bambos, N. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3073065 · Cited by 26
Technical note—Knowledge gradient for selection with covariates: Consistency and computation
Ding, L., Hong, L. J., Shen, H., & Zhang, X. (2021) · Naval Research Logistics (NRL) · doi:10.1002/nav.22028 · Cited by 29
Differential privacy of populations in routing games
Dong, R., Krichene, W., Bayen, A. M., & Sastry, S. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402640 · Cited by 31
A Hybrid Bandit Framework for Diversified Recommendation
Ding, Q., Liu, Y., Miao, C., Cheng, F. Y., & Tang, H. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i5.16524 · Cited by 32
Auction-Based Combinatorial Multi-Armed Bandit Mechanisms with Strategic Arms
Gao, G., Huang, H., Xiao, M., Wu, J., Sun, Y.-E., & Zhang, S. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488765 · Cited by 25
Learning and Selecting the Right Customers for Reliability: A Multi-Armed Bandit Approach
Li, Y., Hu, Q., & Li, N. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619481 · Cited by 25
A reliability-aware multi-armed bandit approach to learn and select users in demand response
Li, Y., Hu, Q., & Li, N. (2020) · Automatica · doi:10.1016/j.automatica.2020.109015 · Cited by 25
Online Open World RecognitionPreprint
Rosa, R. D., Mensink, T., & Caputo, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.02275 · Cited by 35
Online Reinforcement Learning for Beam Tracking and Rate Adaptation in Millimeter-wave Systems
Krunz, M., Aykin, I., Sarkar, S., & Akgun, B. (2023) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2023.3243910 · Cited by 26
Large-Scale Bandit Approaches for Recommender Systems
Zhou, Q., Zhang, X., Xu, J., & Liang, B. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70087-8_83 · Cited by 24
Adversarial Bandits with Knapsacks
Immorlica, N., Sankararaman, K. A., Schapire, R. E., & Slivkins, A. (2022) · Journal of the ACM · doi:10.1145/3557045 · Cited by 24
A Collaborative Learning Based Approach for Parameter Configuration of Cellular Networks
Chuai, J., Chen, Z., Liu, G., Guo, X., Wang, X., Liu, X., Zhu, C., & Shen, F. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737657 · Cited by 24
Bootstrap Thompson Sampling and Sequential Decision Problems in the Behavioral Sciences
Eckles, D., & Kaptein, M. C. (2019) · SAGE Open · doi:10.1177/2158244019851675 · Cited by 31
Privacy-Preserving Collaborative Learning for Multiarmed Bandits in IoT
Chen, S., Tao, Y., Yu, D., Li, F., Gong, B., & Cheng, X. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3015986 · Cited by 24
Towards Instance Optimal Bounds for Best Arm IdentificationPreprint
Chen, L., Li, J., & Qiao, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.06031 · Cited by 28
Tian, L., Oviatt, S. L., Muszyński, M., Chamberlain, B. C., Healey, J., & Sano, A. (2022) · ACM eBooks · doi:10.1145/3502398 · Cited by 31
SRTuner: Effective Compiler Optimization Customization by Exposing Synergistic Relations
Park, S., Latifi, S., Park, Y., Behroozi, A., Jeon, B., & Mahlke, S. A. (2022) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo53902.2022.9741263 · Cited by 27
Distributionally Robust Batch Contextual Bandits
Si, N., Zhang, F., Zhou, Z., & Blanchet, J. (2023) · Management Science · doi:10.1287/mnsc.2023.4678 · Cited by 60
Chen, X., Diao, D., Chen, H., Yao, H., Piao, H., Sun, Z., Yang, Z., Goebel, R. G., Jiang, B., & Chang, Y. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i6.25864 · Cited by 37
Developmental learning for Intelligent Tutoring Systems
Clement, B., Roy, D., Oudeyer, P., & Lopes, M. C. (2014) · IEEE International Conference on Development and Learning (ICDL) · doi:10.1109/devlrn.2014.6983019 · Cited by 27
Lelarge, M., Proutière, A., & Talebi, S. (2013) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2013.6691221 · Cited by 23
Setpoint Tracking With Partially Observed Loads
Lesage‐Landry, A., & Taylor, J. A. (2018) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2018.2804353 · Cited by 23
Satisficing in Time-Sensitive Bandit Learning
Russo, D., & Roy, B. V. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2021.1229 · Cited by 42
Differentially Private Mechanisms for Budget Limited Mobile Crowdsourcing
Han, K., Liu, H., Tang, S., Xiao, M., & Luo, J. (2018) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2018.2848265 · Cited by 23
Tractable Sampling Strategies for Ordinal Optimization
Shin, D., Broadie, M. N., & Zeevi, A. J. (2018) · Operations Research · doi:10.1287/opre.2018.1753 · Cited by 23
Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms
Bura, A., Rengarajan, D., Kalathil, D. M., Shakkottai, S., & Chamberland, J. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3105880 · Cited by 24
Learning Algorithms for Minimizing Queue Length Regret
Stahlbuhk, T., Shrader, B., & Modiano, E. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3054854 · Cited by 42
From reactive towards anticipatory fishing agents
Madsen, J. K., Bailey, R. M., Carrella, E., & Koralus, P. (2020) · Journal of Simulation · doi:10.1080/17477778.2020.1742588 · Cited by 24
Synthetic Control as Online Linear Regression
Chen, J. (2023) · Econometrica · doi:10.3982/ecta20720 · Cited by 23
Near-Optimal and Practical Jamming-Resistant Energy-Efficient Cognitive Radio Communications
Zhou, P., Wang, Q., Wang, W., Hu, Y., & Wu, D. O. (2017) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2017.2721931 · Cited by 22
Regret Bounds for Batched Bandits
Esfandiari, H., Karbasi, A., Mehrabian, A., & Mirrokni, V. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i8.16901 · Cited by 27
Sahu, A. K., & Kar, S. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3012609 · Cited by 23
Multidimensional Dynamic Pricing for Welfare Maximization
Roth, A., Slivkins, A., Ullman, J., & Wu, Z. S. (2017) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3033274.3085106 · Cited by 22
A quality assuring, cost optimal multi-armed bandit mechanism for expertsourcing
Jain, S., Gujar, S., Bhat, S., Zoeter, O. R., & Narahari, Y. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2017.10.001 · Cited by 22
Bandit-based Random Mutation Hill-Climbing
Liu, J., Pérez-Liébana, D., & Lucas, S. M. (2017) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2017.7969564 · Cited by 25
Exploration and Incentives in Reinforcement Learning
Simchowitz, M., & Slivkins, A. (2023) · Operations Research · doi:10.1287/opre.2022.0495 · Cited by 48
Online Data Valuation and Pricing for Machine Learning Tasks in Mobile Health
Xu, A., Zheng, Z., Wu, F., & Chen, G. (2022) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom48880.2022.9796669 · Cited by 25
Chen, X., Xue, J., Lei, Z., Qian, X., & Ukkusuri, S. V. (2022) · Transportation Research Part D Transport and Environment · doi:10.1016/j.trd.2022.103447 · Cited by 24
Seiden: Revisiting Query Processing in Video Database Systems
Bang, J., Kakkar, G. T., Chunduri, P., Mitra, S., & Arulraj, J. J. P. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3598581.3598599 · Cited by 23
Nguyen, A., Pogoncheff, G., Dong, B. X., Bui, N., Truong, H., Pham, N., Nguyen, L., Nguyen-Huu, H., Bui-Diem, K., Vu-Tran-Thien, Q., et al. (2023) · Scientific Reports · doi:10.1038/s41598-023-43975-1 · Cited by 29
The Multi-Armed Bandit With Stochastic Plays
Lesage‐Landry, A., & Taylor, J. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2765501 · Cited by 21
Enhancing Reputation via Price Discounts in E-Commerce Systems: A Data-Driven Approach
Xie, H. L., Ma, R. T. B., & Lui, J. C. S. (2018) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3154417 · Cited by 28
Selection Problems in the Presence of Implicit Bias
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603209 · Cited by 22
Learning algorithms for scheduling in wireless networks with unknown channel statistics
Stahlbuhk, T., Shrader, B., & Modiano, E. (2018) · Ad Hoc Networks · doi:10.1016/j.adhoc.2018.10.006 · Cited by 21
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.