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 701–800 of 1,003
A Tutorial on Bandit Learning and Its Applications in 5G Mobile Edge Computing (Invited Paper)
Liu, S., Cheng, P., Chen, Z., Vucetic, B. S., & Li, Y. (2022) · Frontiers in Signal Processing · doi:10.3389/frsip.2022.864392 · Cited by 4
Measuring Convergence Inertia: Online Learning in Self-adaptive Systems with Context Shifts
Alberts, E., & Gerostathopoulos, I. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-19759-8_15 · Cited by 4
A Buffered Semi-Asynchronous Mechanism with MAB for Efficient Federated Learning
Wang, C., Wu, Q., Ma, Q., & Chen, X. (2022) · International Conference on High Performance Big Data and Intelligent Systems (HPBD&IS) · doi:10.1109/hdis56859.2022.9991371 · Cited by 6
Multi-Armed Bandits With Self-Information Rewards
Weinberger, N., & Yemini, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3299460 · Cited by 9
Online Learning for Adaptive Probing and Scheduling in Dense WLANs
Xu, T., Zhang, D., & Zheng, Z. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228988 · Cited by 4
Kadabra: Adapting Kademlia for the Decentralized Web
Zhang, Y., & Venkatakrishnan, S. B. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-47751-5_19 · Cited by 4
Age-of-Information Minimization for Energy Harvesting Sensor in Non-Stationary Environment
Jaiswal, A., & Chattopadhyay, A. (2023) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt58741.2023.10349881 · Cited by 4
B2-Bandit: Budgeted Pricing With Blocking Constraints for Metaverse Crowdsensing Under Uncertainty
Liu, X., Qin, Y., Wu, W., Fu, C., Lyu, Y., Dong, F., & Luo, J. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3345396 · Cited by 4
Contextual Bandits for Online Markdown Pricing for E-commerce
G, U., Sethuraman, S., & Ramanan, S. (2024) · COMAD/CODS · doi:10.1145/3632410.3632448 · Cited by 5
Distributed Linear Bandits With Differential Privacy
Li, F., Zhou, X., & Ji, B. (2024) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2024.3362978 · Cited by 6
Jiang, Y., Ye, Q., Fapi, E. T., Sun, W., & Li, F. (2024) · IEEE Internet of Things Magazine · doi:10.1109/iotm.001.2300247 · Cited by 4
Secure Dynamic Scheduling for Federated Learning in Underwater Wireless IoT Networks
Yan, L., Wang, L., Li, G., Shao, J., & Xia, Z. (2024) · Journal of Marine Science and Engineering · doi:10.3390/jmse12091656 · Cited by 4
A General Framework for Clustering and Distribution Matching With Bandit Feedback
Yavas, R. C., Huang, Y., Tan, V. Y. F., & Scarlett, J. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3528655 · Cited by 4
Genetic Multi-Armed Bandits: A Reinforcement Learning Inspired Approach for Simulation Optimization
Preil, D., & Krapp, M. (2024) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2024.3524505 · Cited by 4
Active learning for classification: An optimistic approach
Collet, T., & Pietquin, O. (2014) · IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning · doi:10.1109/adprl.2014.7010610 · Cited by 5
Zheng, R., & Hua, C. (2016) · Wireless networks · doi:10.1007/978-3-319-50502-2_2 · Cited by 4
A Robust UCB scheme for active learning in regression from strategic crowds
Padmanabhan, D., Bhat, S., Garg, D., Shevade, S., & Narahari, Y. (2016) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2016.7727473 · Cited by 5
Liu, L., & Jia, W. (2021) · International Journal of Computational Intelligence Systems · doi:10.2991/ijcis.d.210520.001 · Cited by 4
Worst-case regret analysis of computationally budgeted online kernel selection
Li, J., & Liao, S. (2022) · Machine Learning · doi:10.1007/s10994-021-06082-8 · Cited by 4
Structured Projection-free Online Convex Optimization with Multi-point Bandit Feedback
Ding, Y., & Lavaei, J. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683142 · Cited by 4
Correlated combinatorial bandits for online resource allocation
Gupta, S., Zuo, J., Joe‐Wong, C., Joshi, G., & Yağan, O. (2022) · ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc) · doi:10.1145/3492866.3549727 · Cited by 4
Multi-channel transmission scheduling with hopping scheme under uncertain channel states
Song, Y., & Ye, D. (2023) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2023.01.025 · Cited by 4
Li, F., Yuan, X., Wang, L., Yang, H., Yu, D., Lyu, W., & Cheng, X. (2023) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2023.3273501 · Cited by 4
The Societal Impacts of Algorithmic Decision-Making
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195 · Cited by 11
Lobanov, A. V., & Gasnikov, A. V. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-47859-8_6 · Cited by 4
Incentive-Aware Recommender Systems in Two-Sided Markets
Dai, X., Xu, W., Qi, Y., & Jordan, M. I. (2024) · ACM Transactions on Recommender Systems · doi:10.1145/3674158 · Cited by 8
Algorithmes de bandits pour la recommandation à tirages multiples
Louëdec, J., Chevalier, M., Garivier, A., & Mothe, J. (2015) · Document numérique · doi:10.3166/dn.18.2-3.59-79 · Cited by 4
Kamiura, M., & Kohei, S. (2017) · Biosystems · doi:10.1016/j.biosystems.2017.08.004 · Cited by 6
Gittins index based control policy for a class of pursuit‐evasion problems
Tan, C., Xu, C., Yang, L., & Wong, W. S. (2017) · IET Control Theory and Applications · doi:10.1049/iet-cta.2017.0398 · Cited by 5
New bounds on the price of bandit feedback for mistake-bounded online multiclass learning
Long, P. M. (2019) · Theoretical Computer Science · doi:10.1016/j.tcs.2019.11.017 · Cited by 16
Han, S., Li, X., Yan, L., Liu, Z., & Guan, X. (2018) · Soft Computing · doi:10.1007/s00500-018-3357-9 · Cited by 4
Online Learning Methods for Controlling Dynamic Cyber Deception Strategies
Gutierrez, M., & Kiekintveld, C. D. (2020) · Springer eBooks · doi:10.1007/978-3-030-33432-1_11 · Cited by 4
Adversarial Bandits Policy for Crawling Commercial Web Content
Han, S., Bendersky, M., Gajda, P., Novikov, S., Najork, M., Brodowsky, B., & Popescul, A. (2020) · International World Wide Web Conference (WWW) · doi:10.1145/3366423.3380125 · Cited by 4
Tampubolon, E., & Boche, H. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054699 · Cited by 4
Dynamic Pricing and Placement for Distributed Machine Learning Jobs
Zhang, X., Zhou, R., Lui, J. C. S., & Li, Z. (2020) · International Conference on Big Data Computing and Communications (BigCom) · doi:10.1109/bigcom51056.2020.00029 · Cited by 4
Ghadakchi, V., Xie, M., & Termehchy, A. (2020) · International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM) · doi:10.1145/3401071.3401655 · Cited by 4
Optimal Frequency and Rate Selection Using Unimodal Objective Based Thompson Sampling Algorithm
Tong, J., Lai, S., Fu, L., & Han, Z. (2020) · International Conference on Communications · doi:10.1109/icc40277.2020.9148988 · Cited by 4
Throughput Maximization in Uncooperative Spectrum Sharing Networks
Stahlbuhk, T., Shrader, B., & Modiano, E. (2020) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2020.3012273 · Cited by 4
Accordia: Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications
Liu, Y., Xu, H., & Lau, W. C. (2020) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs47774.2020.00088 · Cited by 4
An optimal bidimensional multi-armed bandit auction for multi-unit procurement
Bhat, S., Jain, S., Gujar, S., & Narahari, Y. (2019) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-018-9611-0 · Cited by 4
Self-adjusting Linear Networks
Avin, C., van Duijn, I., & Schmid, S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-34992-9_29 · Cited by 4
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
Wang, L., Li, B., Zhou, H., Giannakis, G. B., Varshney, L. R., & Zhao, Z. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i11.17218 · Cited by 4
Stochastic Graphical Bandits with Adversarial Corruptions
Lu, S., Wang, G., & Zhang, L. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i10.17060 · Cited by 4
Extreme Bandits Using Robust Statistics
Bhatt, S., Li, P., & Samorodnitsky, G. P. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3209931 · Cited by 4
Order scoring, bandit learning and order cancellations
Gao, X., & Xu, T. (2021) · Journal of Economic Dynamics and Control · doi:10.1016/j.jedc.2021.104287 · Cited by 4
Emotion-aware Human–Robot Interaction and Social Robots
Tian, L., Oviatt, S. L., Muszyński, M., Chamberlain, B. C., Healey, J., & Sano, A. (2022) · ACM eBooks · doi:10.1145/3502398.3502407 · Cited by 6
Budget-limited distribution learning in multifidelity problems
Xu, Y., & Narayan, A. (2022) · Numerische Mathematik · doi:10.1007/s00211-022-01337-5 · Cited by 4
On High-dimensional and Low-rank Tensor Bandits
Shi, C., Shen, C., & Sidiropoulos, N. D. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206552 · Cited by 4
Estimation of Games under No Regret: Structural Econometrics for AI
Lomys, N., & Magnolfi, L. (2025) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3736252.3742516 · Cited by 4
Schemata Bandits for Binary Encoded Combinatorial Optimisation Problems
Drugan, M. M., Isasi, P., & Manderick, B. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-13563-2_26 · Cited by 4
Thompson Sampling for Bayesian Bandits with Resets
Viappiani, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-41575-3_31 · Cited by 4
Adaptive matching for expert systems with uncertain task types
Shah, V., Gulikers, L., Massoulié, L., & Vojnović, M. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262814 · Cited by 4
Stochastic Multi-path Routing Problem with Non-stationary Rewards: Building PayU's Dynamic Routing
Trivedi, P., & Singh, A. K. (2018) · International World Wide Web Conference (WWW) · doi:10.1145/3184558.3191630 · Cited by 5
Network-Model-Based vs. Network-Model-Free Approaches to Internet Congestion Control
Schapira, M. (2018) · IEEE International Conference on High Performance Switching and Routing (HPSR) · doi:10.1109/hpsr.2018.8850755 · Cited by 4
Human-Machine Collaboration for Face Recognition
Ravindranath, S., Baburaj, R., Balasubramanian, V. N., Namburu, N., Gujar, S., & Jawahar, C. V. (2020) · Joint International Conference on Data Science & Management of Data (CODS-COMAD) · doi:10.1145/3371158.3371160 · Cited by 4
Policy Optimization as Online Learning with Mediator Feedback
Metelli, A. M., Papini, M., D’Oro, P., & Restelli, M. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i10.17083 · Cited by 14
Ochi, K., & Kamiura, M. (2015) · Biosystems · doi:10.1016/j.biosystems.2015.06.009 · Cited by 5
Incentivizing exploration via information asymmetry
Slivkins, A. (2017) · XRDS Crossroads The ACM Magazine for Students · doi:10.1145/3123744 · Cited by 4
Search as a simple take-the-best heuristic
Yahosseini, K. S., & Moussaïd, M. (2019) · Royal Society Open Science · doi:10.1098/rsos.190529 · Cited by 4
Bandit Regret Scaling with the Effective Loss RangePreprint
Cesa‐Bianchi, N., & Shamir, O. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.05091 · Cited by 4
Self-citationBe Greedy in Multi-Armed BanditsPreprint
Jedor, M., Louëdec, J., & Perchet, V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.01086 · Cited by 4
When Will Workers Follow an Algorithm?: A Field Experiment with a Retail BusinessPreprint
Kawaguchi, K. (2022) · SocArXiv (OSF Preprints) · doi:10.31235/osf.io/a4d63 · Cited by 4
Foundations of Information Theory
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.019 · Cited by 4
Dai, J., Li, X., Han, S., Yu, J., & Liu, Z. (2025) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2025.3533010 · Cited by 3
Optimizing Dynamic Pricing Demand Response Algorithm Using Reinforcement Learning in Smart Grid
Bagherpour, R., Mozayani, N., & Badnava, B. (2020) · International Computer Conference, Computer Society of Iran (CSICC) · doi:10.1109/csicc49403.2020.9050115 · Cited by 3
Treatment recommendation with distributional targets
Kock, A., Preinerstorfer, D., & Veliyev, B. (2022) · Journal of Econometrics · doi:10.1016/j.jeconom.2022.08.003 · Cited by 10
Earning and Learning with Varying Cost
Zhong, Y., Hong, L. J., & Liu, G. (2021) · Production and Operations Management · doi:10.1111/poms.13380 · Cited by 4
Dou, H., Zhu, S., Zhang, Y., Chen, P., & Zheng, Z. (2024) · The Journal of Supercomputing · doi:10.1007/s11227-024-06123-8 · Cited by 4
A Differentially Private Approach for Budgeted Combinatorial Multi-Armed Bandits
Wang, H., Cui, L., Wang, E., & Liu, J. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3401836 · Cited by 3
Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback
Hou, I.-H. (2024) · ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc) · doi:10.1145/3641512.3686369 · Cited by 3
Automated network management and configuration using Probabilistic Trans-Algorithmic Search
Gonen, B., Gündüz, G., & Yüksel, M. (2014) · Computer Networks · doi:10.1016/j.comnet.2014.11.013 · Cited by 3
Learn to adapt: Self-optimizing small cell transmit power with correlated bandit learning
Wang, Z., Shen, C., Luo, X., & van der Schaar, M. (2017) · International Conference on Communications · doi:10.1109/icc.2017.7997146 · Cited by 3
Efficient Real-Parameter Single Objective Optimizer Using Hierarchical CMA-ES Solvers
Drugan, M. M. (2017) · Advances in intelligent systems and computing · doi:10.1007/978-3-319-69710-9_10 · Cited by 3
Optimal Learning for Structured Bandits
Parys, B. P. G. V., & Golrezaei, N. (2023) · Management Science · doi:10.1287/mnsc.2020.02108 · Cited by 3
Optimisation with Zeroth-Order Oracles in Formation
Michael, E., Zelazo, D., Wood, T. A., Manzie, C. G., & Shames, I. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304272 · Cited by 3
Literature Review of mmWave Networks
Yang, P., Wu, W. R., Zhang, N., & Shen, X. (2021) · Wireless networks · doi:10.1007/978-3-030-88630-1_2 · Cited by 3
Optimized setting of privacy budget in a recommendation system with local differential privacy
暴, 婷., 徐, 蕾., 祝, 烈., & 王, 丽. (2021) · Scientia Sinica Informationis · doi:10.1360/ssi-2021-0304 · Cited by 3
Shan, Y., Wang, H., & Zhang, C. (2022) · Security and Communication Networks · doi:10.1155/2022/2965081 · Cited by 3
Greedy-Bayes for Targeted News Dissemination
Massoulié, L., Ohannessian, M. I., & Proutière, A. (2015) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2796314.2745868 · Cited by 3
Bandit Procedures for Designing Patient-Centric Clinical Trials
Villar, S. S., & Jacko, P. (2022) · Springer series in supply chain management · doi:10.1007/978-3-031-01926-5_14 · Cited by 3
Multi-armed bandit based device scheduling for crowdsensing in power grids
Zhao, J., Ni, Y., & Zhu, H. (2023) · Frontiers in Energy Research · doi:10.3389/fenrg.2023.1141954 · Cited by 3
Cloud Configuration Optimization for Recurring Batch-Processing Applications
Liu, Y., Xu, H., & Lau, W. C. (2023) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2023.3246086 · Cited by 3
Huang, Y., & Hu, J. (2023) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc55779.2023.10156437 · Cited by 3
Distributed Stochastic Bandits with Hidden Contexts
Lin, J., & Moothedath, S. (2023) · European Control Conference (ECC) · doi:10.23919/ecc57647.2023.10178370 · Cited by 3
Adaptive designs for best treatment identification with top‐two Thompson sampling and acceleration
Wang, J., & Tiwari, R. C. (2023) · Pharmaceutical Statistics · doi:10.1002/pst.2331 · Cited by 3
Node Authentication for Underwater Sensor Networks Based on Time Reversal and LinUCB
Liu, C., Zhao, R., Shi, T., & Wang, H. (2023) · MTS/IEEE OCEANS Conference (OCEANS) · doi:10.1109/oceanslimerick52467.2023.10244452 · Cited by 3
Stochastic Adversarial Noise in the “Black Box” Optimization Problem
Lobanov, A. V. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-47859-8_5 · Cited by 3
Arton, A., Carrella, E., Madsen, J. K., & Bailey, R. M. (2024) · Ecological Complexity · doi:10.1016/j.ecocom.2023.101070 · Cited by 2
From Learning to Analytics: Improving Model Efficacy With Goal-Directed Client Selection
Tong, J., Chen, Z., Fu, L., Zhang, J., & Han, Z. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3383038 · Cited by 3
FedACS: An Adaptive Client Selection Framework for Communication-Efficient Federated Graph Learning
Xu, H., Gao, X., Liu, J., Ma, Q., & Huang, L. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3563404 · Cited by 7
PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators
Xu, R., Wang, H., Zhang, X., Li, B., & Cui, P. (2025) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3711896.3737085 · Cited by 3
Efficient Ranking and Selection in Parallel Computing Environments
Ni, E. C., Ciocan, D. F., Henderson, S. G., & Hunter, S. R. (2017) · Operations Research · doi:10.1287/opre.2016.1577 · Cited by 3
PAC models in stochastic multi-objective multi-armed bandits
Drugan, M. M. (2017) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3071178.3071337 · Cited by 3
Optimal Learning for Dynamic Coding in Deadline-Constrained Multi-Channel Networks
Çaycı, S., & Eryılmaz, A. (2019) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2019.2913666 · Cited by 3
Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory
Su, L., Zubeldía, M., & Lynch, N. A. (2019) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3309697.3331498 · Cited by 3
Intelligent Adjustment of Game Properties at Run Time Using Multi-armed Bandits
Amiri, Z., & Sekhavat, Y. A. (2019) · The Computer Games Journal · doi:10.1007/s40869-019-00083-3 · Cited by 4
Dimensionality Reduction for Low-Latency High-Throughput Fraud Detection on Datastreams
Axenie, C., Tudoran, R., Bortoli, S., Hassan, M. A. H., Sánchez, C. S., & Brasche, G. (2019) · International Conference on Machine Learning and Applications · doi:10.1109/icmla.2019.00194 · Cited by 3
Memory-Constrained No-Regret Learning in Adversarial Multi-Armed Bandits
Xu, X., & Zhao, Q. Q. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3070201 · Cited by 3
Rosella: A Self-Driving Distributed Scheduler for Heterogeneous Clusters
Wu, Q., & Liu, Z. (2021) · International Conference on Mobility, Sensing and Networking (MSN) · doi:10.1109/msn53354.2021.00073 · Cited by 4
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.