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 101–200 of 1,003
Online decision making in crowdsourcing markets: theoretical challenges
Slivkins, A., & Vaughan, J. W. (2014) · ACM SIGecom Exchanges · doi:10.1145/2692359.2692364 · Cited by 88
Dynamic Pricing with Limited Supply
Babaioff, M., Dughmi, S., Kleinberg, R., & Slivkins, A. (2015) · ACM Transactions on Economics and Computation · doi:10.1145/2559152 · Cited by 129
A Multi-armed Bandit Approach to Online Spatial Task Assignment
Hassan, U. U., & Curry, E. (2014) · IEEE International Conference on Ubiquitous Intelligence and Computing, Autonomic and Trusted Computing, and Scalable Computing and Communications (UIC-ATC-ScalCom) · doi:10.1109/uic-atc-scalcom.2014.68 · Cited by 68
Liang, J., Wu, J., Gao, Z., Sun, H., Yang, X., & Lo, H. K. (2019) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2019.05.011 · Cited by 66
Taming the Uncertainty: Budget Limited Robust Crowdsensing Through Online Learning
Han, K., Zhang, C., & Luo, J. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2015.2418191 · Cited by 67
Multi-armed bandits in multi-agent networks
Shahrampour, S., Rakhlin, A., & Jadbabaie, A. (2017) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2017.7952664 · Cited by 69
Dynamic Assortment Personalization in High Dimensions
Kallus, N., & Udell, M. R. (2020) · Operations Research · doi:10.1287/opre.2019.1948 · Cited by 91
Active ranking from pairwise comparisons and when parametric assumptions do not help
Heckel, R., Shah, N. B., Ramchandran, K., & Wainwright, M. J. (2019) · The Annals of Statistics · doi:10.1214/18-aos1772 · Cited by 90
MAMBA: A Multi-armed Bandit Framework for Beam Tracking in Millimeter-wave Systems
Aykin, I., Akgun, B., Feng, M., & Krunz, M. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155408 · Cited by 73
The complexity of constrained min-max optimization
Daskalakis, C., Skoulakis, S., & Zampetakis, M. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451125 · Cited by 83
Cao, X., Yang, B. F., Wang, K., Li, X., Yu, Z., Yuen, C., Zhang, Y., & Han, Z. (2024) · Proceedings of the IEEE · doi:10.1109/jproc.2024.3417332 · Cited by 80
Misra, I., Girshick, R., Fergus, R., Hebert, M., Gupta, A., & van der Maaten, L. J. P. (2018) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2018.00009 · Cited by 86
The effect of atomoxetine on random and directed exploration in humans
Warren, C. M., Wilson, R. C., van der Wee, N. J., Giltay, E. J., van Noorden, M. S., Cohen, J. D., & Nieuwenhuis, S. (2017) · PLoS ONE · doi:10.1371/journal.pone.0176034 · Cited by 76
Risk-aware multi-armed bandit problem with application to portfolio selection
Huo, X., & Fu, F. (2017) · Royal Society Open Science · doi:10.1098/rsos.171377 · Cited by 64
Trust-Based Collaborative Privacy Management in Online Social Networks
Xu, L., Jiang, C., He, N., Han, Z., & Benslimane, A. (2018) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2018.2840488 · Cited by 65
Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications
Huang, W., Ok, J., Li, L., & Chen, W. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/317 · Cited by 61
On Thompson Sampling and Asymptotic Optimality
Leike, J., Lattimore, T., Orseau, L., & Hütter, M. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/688 · Cited by 61
Optimal Rate Sampling in 802.11 Systems: Theory, Design, and Implementation
Combes, R., Ok, J., Proutière, A., Yun, D., & Yi, Y. (2018) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2018.2854758 · Cited by 62
Collaborative Spatial Reuse in wireless networks via selfish Multi-Armed Bandits
Wilhelmi, F., Cano, C., Neu, G., Bellalta, B., Jönsson, A., & Barrachina‐Muñoz, S. (2019) · Ad Hoc Networks · doi:10.1016/j.adhoc.2019.01.006 · Cited by 62
Efficient-UCBV: An Almost Optimal Algorithm Using Variance Estimates
Mukherjee, S., Naveen, K. P., Sudarsanam, N., & Ravindran, B. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.12110 · Cited by 57
Online Markov Decision Processes With Kullback–Leibler Control Cost
Guan, P., Raginsky, M., & Willett, R. M. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2301558 · Cited by 70
A Multiarmed Bandit Incentive Mechanism for Crowdsourcing Demand Response in Smart Grids
Jain, S., Narayanaswamy, B., & Narahari, Y. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8806 · Cited by 56
Multi-Player Multi-Armed Bandits for Stable Allocation in Heterogeneous Ad-Hoc Networks
Darak, S. J., & Hanawal, M. K. (2019) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2019.2934003 · Cited by 56
Stochastic bandits with side observations on networks
Buccapatnam, S., Eryılmaz, A., & Shroff, N. B. (2014) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2591971.2591989 · Cited by 75
On distributed cooperative decision-making in multiarmed bandits
Landgren, P., Srivastava, V., & Leonard, N. E. (2016) · European Control Conference (ECC) · doi:10.1109/ecc.2016.7810293 · Cited by 90
Natural search algorithms as a bridge between organisms, evolution, and ecology
Hein, A. M., Carrara, F., Brumley, D. R., Stocker, R., & Levin, S. A. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1606195113 · Cited by 58
Dynamic Privacy Pricing: A Multi-Armed Bandit Approach With Time-Variant Rewards
Xu, L., Jiang, C., Qian, Y., Zhao, Y., Li, J., & Ren, Y. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2611487 · Cited by 56
Low-Complexity, Low-Regret Link Rate Selection in Rapidly-Varying Wireless Channels
Gupta, H., Eryılmaz, A., & Srikant, R. (2018) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2018.8486206 · Cited by 55
A Non-Stochastic Learning Approach to Energy Efficient Mobility Management
Shen, C., Tekin, C., & van der Schaar, M. (2016) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2016.2612038 · Cited by 55
Task recommendation in crowdsourcing systems: A bibliometric analysis
Yin, X., Wang, H., Wang, W., & Zhu, K. (2020) · Technology in Society · doi:10.1016/j.techsoc.2020.101337 · Cited by 60
Hedging the Drift: Learning to Optimize Under Nonstationarity
Cheung, W. C., Simchi‐Levi, D., & Zhu, R. (2021) · Management Science · doi:10.1287/mnsc.2021.4024 · Cited by 60
Algorithms for Online Influencer Marketing
Lagrée, P., Cappé, O., Cautis, B., & Maniu, S. (2018) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3274670 · Cited by 72
A Survey on Supervised Classification on Data Streams
Lemaire, V., Salperwyck, C., & Bondu, A. (2015) · Lecture notes in business information processing · doi:10.1007/978-3-319-17551-5_4 · Cited by 67
An Adversarial Model for Scheduling with Testing
Dürr, C., Erlebach, T., Megow, N., & Meißner, J. (2020) · Algorithmica · doi:10.1007/s00453-020-00742-2 · Cited by 58
Dynamic Rate and Channel Selection in Cognitive Radio Systems
Combes, R., & Proutière, A. (2014) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2014.2361084 · Cited by 51
Maghsudi, S., & Stanczak, S. (2014) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2014.2369425 · Cited by 53
Online Learning of Nash Equilibria in Congestion Games
Krichene, W., Drighès, B., & Bayen, A. M. (2015) · SIAM Journal on Control and Optimization · doi:10.1137/140980685 · Cited by 51
Orabona, F., & Pál, D. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.11.021 · Cited by 141
Input selection for fast feature engineering
Anderson, M. R., & Cafarella, M. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498272 · Cited by 64
ONETS: Online Network Slice Broker From Theory to Practice
Sciancalepore, V., Zanzi, L., Costa‐Pérez, X., & Capone, A. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3094116 · Cited by 52
Context‐based dynamic pricing with online clustering
Miao, S., Chen, X., Chao, X., Liu, J., & Zhang, Y. (2022) · Production and Operations Management · doi:10.1111/poms.13783 · Cited by 57
Data Poisoning Attacks and Defenses in Dynamic Crowdsourcing With Online Data Quality Learning
Zhao, Y., Gong, X., Lin, F., & Chen, X. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3133365 · Cited by 55
Bailey, R. M., Carrella, E., Axtell, R. L., Burgess, M. G., Cabral, R. B., Drexler, M., Dorsett, C., Madsen, J. K., Merkl, A. A., & Saul, S. E. (2018) · Sustainability Science · doi:10.1007/s11625-018-0579-9 · Cited by 56
Reinforcement Learning Algorithms for Adaptive Cyber Defense against Heartbleed
Zhu, M., Hu, Z., & Liu, P. (2014) · ACM Workshop on Moving Target Defense (MTD) · doi:10.1145/2663474.2663481 · Cited by 50
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603207 · Cited by 49
Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach
Krishnasamy, S., Sen, R., Johari, R., & Shakkottai, S. (2020) · Operations Research · doi:10.1287/opre.2020.1995 · Cited by 91
Social Learning in Multi Agent Multi Armed Bandits
Sankararaman, A., Ganesh, A. J., & Shakkottai, S. (2019) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3366701 · Cited by 59
LACO: A Latency-Driven Network Slicing Orchestration in Beyond-5G Networks
Zanzi, L., Sciancalepore, V., García‐Saavedra, A., Schotten, H. D., & Costa-Perez, X. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3027963 · Cited by 51
Srikanth, K., & Ungureanu, T. S. (2024) · Strategic Management Journal · doi:10.1002/smj.3646 · Cited by 52
Maghsudi, S., & Member, S. (2016) · Cited by 48
A Review of Client Selection Methods in Federated Learning
Mayhoub, S., & M. Shami, T. (2024) · Archives of Computational Methods in Engineering · doi:10.1007/s11831-023-10011-4 · Cited by 47
Collaborative Learning of Stochastic Bandits Over a Social Network
Kolla, R. K., Jagannathan, K., & Gopalan, A. (2016) · IEEE/ACM Transactions on Networking · doi:10.1109/allerton.2016.7852375 · Cited by 53
Secure Mobile Edge Computing in IoT via Collaborative Online Learning
Li, B., Chen, T., & Giannakis, G. B. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2949504 · Cited by 49
An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
Gorbunov, E., Dvurechensky, P. E., & Gasnikov, A. V. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259225 · Cited by 65
How to Make Envy Vanish Over Time
Benadè, G., Kazachkov, A. M., Procaccia, A. D., & Psomas, A. (2018) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3219166.3219179 · Cited by 46
Survey on cognitive anti‐jamming communications
Aref, M. A., Jayaweera, S. K., & Yepez, E. (2020) · IET Communications · doi:10.1049/iet-com.2020.0024 · Cited by 50
The Closed Loop Between Opinion Formation and Personalized Recommendations
Rossi, W. S., Polderman, J. W., & Frasca, P. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3105616 · Cited by 82
Dynamic Pricing with Multiple Products and Partially Specified Demand Distribution
den Boer, A. V. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2013.0636 · Cited by 47
Optimal Rate Sampling in 802.11 systems
Combes, R., Proutière, A., Yun, D., Ok, J., & Yi, Y. (2014) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2014.6848225 · Cited by 45
Parallel Ranking and Selection
Hunter, S. R., & Nelson, B. L. (2017) · Simulation foundations, methods and applications · doi:10.1007/978-3-319-64182-9_12 · Cited by 45
Cheung, W. C., & Simchi‐Levi, D. (2017) · SSRN Electronic Journal · doi:10.2139/ssrn.3075658 · Cited by 48
Can small islands protect nearby coasts from tsunamis? An active experimental design approach
Stefanakis, T., Contal, E., Vayatis, N., Frédéric Dias, A., & SYNOLAKIS, C. E. (2014) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2014.0575 · Cited by 50
Gasnikov, A. V., Krymova, E., Lagunovskaya, A., Usmanova, I., & Fedorenko, F. (2017) · Automation and Remote Control · doi:10.1134/s0005117917020035 · Cited by 44
Braverman, M., Mao, J., Schneider, J., & Weinberg, S. M. (2018) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3219166.3219233 · Cited by 44
Analysis of the apparent nuclear modification in peripheral Pb–Pb collisions at 5.02 TeV
Acharya, S., Acosta, F. T., Adamová, D., Adolfsson, J., Aggarwal, M. M., Rinella, G. A., Agnello, M., Agrawal, N., Ahammed, Z., Ahn, S. U., et al. (2019) · Physics Letters B · doi:10.1016/j.physletb.2019.04.047 · Cited by 60
A note on a tight lower bound for capacitated MNL-bandit assortment selection models
Chen, X., & Wang, Y. (2018) · Operations Research Letters · doi:10.1016/j.orl.2018.08.006 · Cited by 44
Hyper-heuristics using multi-armed bandit models for multi-objective optimization
de Almeida, C. P., Gonçalves, R. A., Venske, S. M., Lüders, R., & Delgado, M. (2020) · Applied Soft Computing · doi:10.1016/j.asoc.2020.106520 · Cited by 45
Martins, I. D., Bahiense, L., Infante, C. E. D. D. C., & Arruda, E. F. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113236 · Cited by 44
A continuous-time approach to online optimization
Kwon, J., & Mertikopoulos, P. (2017) · Journal of Dynamics and Games · doi:10.3934/jdg.2017008 · Cited by 43
Adversarial Bandits with Knapsacks
Immorlica, N., Sankararaman, K. A., Schapire, R. E., & Slivkins, A. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00022 · Cited by 43
Online Learning in Variable Feature Spaces under Incomplete Supervision
He, Y., Yuan, X., Chen, S., & Wu, X. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i5.16532 · Cited by 47
How Many Workers to Ask? Adaptive Exploration for Collecting High Quality Labels
Abraham, I., Alonso, O., Kandylas, V., Patel, R., Shelford, S., & Slivkins, A. (2016) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2911451.2911514 · Cited by 48
Machine learning augmented branch and bound for mixed integer linear programming
Scavuzzo, L., Aardal, K., Lodi, A., & Yorke‐Smith, N. (2024) · Mathematical Programming · doi:10.1007/s10107-024-02130-y · Cited by 112
A Perspective on Incentive Design: Challenges and Opportunities
Ratliff, L. J., Dong, R., Sekar, S., & Fiez, T. (2018) · Annual Review of Control Robotics and Autonomous Systems · doi:10.1146/annurev-control-053018-023634 · Cited by 71
Learning to Bid Without Knowing your Value
Feng, Z., Podimata, C., & Syrgkanis, V. (2018) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3219166.3219208 · Cited by 49
Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control
Zhang, W., & Mei, Y. (2022) · Technometrics · doi:10.1080/00401706.2022.2054861 · Cited by 46
Maghsudi, S., & Hossain, E. (2017) · IEEE Access · doi:10.1109/access.2017.2676166 · Cited by 41
Distributed Learning and Optimal Assignment in Multiplayer Heterogeneous Networks
Tibrewal, H., Patchala, S., Hanawal, M. K., & Darak, S. J. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737653 · Cited by 41
Tao, C., Zhang, Q., & Zhou, Y. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00017 · Cited by 71
Waiting But Not Aging: Optimizing Information Freshness Under the Pull Model
Li, F., Sang, Y., Liu, Z., Li, B., Wu, H., & Ji, B. (2020) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2020.3041654 · Cited by 45
A Learning Approach to Frequent Handover Mitigations in 3GPP Mobility Protocols
Shen, C., & van der Schaar, M. (2017) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc.2017.7925950 · Cited by 40
Concentration bounds for empirical conditional value-at-risk: The unbounded case
Kolla, R. K., Prashanth, L. A., Bhat, S. P., & Jagannathan, K. (2018) · Operations Research Letters · doi:10.1016/j.orl.2018.11.005 · Cited by 57
EdgeLaaS: Edge Learning as a Service for Knowledge-Centric Connected Healthcare
Li, G., Xu, G., Sangaiah, A. K., Wu, J., & Li, J. (2019) · IEEE Network · doi:10.1109/mnet.001.1900019 · Cited by 40
Nonstationary Reinforcement Learning: The Blessing of (More) Optimism
Cheung, W. C., Simchi‐Levi, D., & Zhu, R. (2023) · Management Science · doi:10.1287/mnsc.2023.4704 · Cited by 45
Engineering highly active nuclease enzymes with machine learning and high-throughput screening
Thomas, N., Belanger, D., Xu, C. A., Lee, H., Hirano, K., Iwai, K., Polic, V., Nyberg, K. D., Hoff, K. G., Frenz, L., et al. (2025) · Cell Systems · doi:10.1016/j.cels.2025.101236 · Cited by 56
A Unified Framework for Optimization Under Uncertainty
Powell, W. B. (2016) · doi:10.1287/educ.2016.0149 · Cited by 43
Explainable predictive process monitoring: a user evaluation
Rizzi, W., Comuzzi, M., Francescomarino, C. D., Ghidini, C., Lee, S., Maggi, F. M., & Nolte, A. (2024) · Process Science · doi:10.1007/s44311-024-00003-3 · Cited by 45
Online convex optimization with ramp constraints
Khuzani, M. B., Li, N., & Wierman, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7403279 · Cited by 38
Multi-objective Contextual Multi-armed Bandit With a Dominant Objective
Tekin, C., & Turğay, E. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2841822 · Cited by 41
Entanglement is Necessary for Optimal Quantum Property Testing
Bubeck, S., Chen, S., & Li, J. Z. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00070 · Cited by 38
Self-citationLearning to Rank: Regret Lower Bounds and Efficient Algorithms
Combes, R., Magureanu, S., Proutière, A., & Laroche, C. (2015) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2745844.2745852 · Cited by 62
Zhang, Z., Cao, W., Qin, Z., Zhu, L., Yu, Z., & Ren, K. (2017) · International Workshop on Quality of Service · doi:10.1109/iwqos.2017.7969167 · Cited by 37
Johari, R., Kamble, V., & Kanoria, Y. (2021) · Operations Research · doi:10.1287/opre.2020.2013 · Cited by 45
Age-of-Information Oriented Scheduling for Multichannel IoT Systems With Correlated Sources
Tong, J., Fu, L., & Han, Z. (2022) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2022.3179305 · Cited by 50
On the Optimal Sample Complexity for Best Arm IdentificationPreprint
Chen, L., & Li, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03774 · Cited by 60
Zhao, H., Du, W. D., Liu, W., Lei, T., & Lei, Q. (2018) · EasyChair preprint · doi:10.1109/smartworld.2018.00133 · Cited by 37
Distribution-Free Contextual Dynamic Pricing
Luo, Y., Sun, W. W., & Liu, Y. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2023.1369 · Cited by 48
Manas: multi-agent neural architecture search
Lopes, V., Carlucci, F. M., Esperança, P. M., Singh, M., Yang, A., Gabillon, V., Xu, H., Chen, Z., & Wang, J. (2019) · Machine-mediated learning · doi:10.1007/s10994-023-06379-w · Cited by 31
An Order Optimal Policy for Exploiting Idle Spectrum in Cognitive Radio Networks
Oksanen, J., & Koivunen, V. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2391072 · Cited by 42
Regret bounds for restless Markov bandits
Ortner, R., Ryabko, D., Auer, P. L., & Munos, R. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.09.026 · Cited by 49
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.