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 601–700 of 1,003
Mohamed, A. S., Lesage‐Landry, A., & Taylor, J. A. (2017) · IEEE Electrical Power and Energy Conference (EPEC) · doi:10.1109/epec.2017.8286168 · Cited by 7
Mirror Descent and Constrained Online Optimization Problems
Titov, A., Stonyakin, F. S., Gasnikov, A. V., & Alkousa, M. S. (2019) · Communications in computer and information science · doi:10.1007/978-3-030-10934-9_5 · Cited by 7
Handover Mitigation in Dense HetNets via Bandit Arm Elimination
Zhao, Y., & Luo, X. (2019) · Globecom · doi:10.1109/globecom38437.2019.9013926 · Cited by 7
Sarıtaç, A. Ö., & Tekin, C. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8308614 · Cited by 7
Task selection for bandit-based task assignment in heterogeneous crowdsourcing
Zhang, H., & Sugiyama, M. (2015) · Conference on Technologies and Applications of Artificial Intelligence (TAAI) · doi:10.1109/taai.2015.7407065 · Cited by 7
Self-Unaware Adversarial Multi-Armed Bandits With Switching Costs
Alipour-Fanid, A., Dabaghchian, M., & Zeng, K. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3110194 · Cited by 8
Reassessing the proper place of man and machine in translation: a pre-translation scenario
Ive, J., Max, A., & Yvon, F. (2018) · Machine Translation · doi:10.1007/s10590-018-9223-9 · Cited by 13
Social Learning and the Innkeeper's Challenge
Bahar, G., Smorodinsky, R., & Tennenholtz, M. (2019) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3328526.3329569 · Cited by 7
Bandwidth and Storage Efficient Caching Based on Dynamic Programming and Reinforcement Learning
Lin, Z., Huang, W., & Chen, W. (2019) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2019.2948337 · Cited by 7
Gaussian Data-Aided Sensing With Multichannel Random Access and Model Selection
Choi, J. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2957964 · Cited by 7
Long, J., Han, J., & Weinan, E. (2022) · CSIAM Transactions on Applied Mathematics · doi:10.4208/csiam-am.so-2021-0026 · Cited by 17
Fast Algorithms for Online Personalized Assortment Optimization in a Big Data RegimePreprint
Miao, S., & Chao, X. (2019) · SSRN Electronic Journal · doi:10.2139/ssrn.3432574 · Cited by 10
Parallelizing Thompson SamplingPreprint
Karbasi, A., Mirrokni, V., & Shadravan, M. M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.01420 · Cited by 7
Task Variance Regularized Multi-Task Learning
Mao, Y., Wang, Z., Liu, W., Lin, X., & Hu, W. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3207049 · Cited by 11
Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
Qian, W., Ing, C., & Liu, J. Y. (2022) · Journal of the American Statistical Association · doi:10.1080/01621459.2022.2152343 · Cited by 6
Distributed online bandit linear regressions with differential privacy
Dai, M., Ho, D. W. C., Zhang, B., Yuan, D., & Xu, S. (2023) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2023.09.001 · Cited by 6
LinFuzz: Program-Sensitive Seed Scheduling Greybox Fuzzing Based on LinUCB Algorithm
Su, Y., Xiong, D., Wan, Y., Shi, C., & Zeng, Q. (2024) · IEEE Access · doi:10.1109/access.2024.3404918 · Cited by 6
Marty, F. M., & Warin, T. (2024) · Journal of Economy and Technology · doi:10.1016/j.ject.2024.10.001 · Cited by 6
Shortest Path Routing in Unknown Environments: Is the Adaptive Optimal Strategy Available?
Zhou, P., Cheng, L., & Wu, D. O. (2016) · IEEE International Conference on Sensing, Communication, and Networking (SECON) · doi:10.1109/sahcn.2016.7733015 · Cited by 6
Learning adversary's actions for secret communication
Tahmasbi, M., Bloch, M. R., & Yener, A. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8007021 · Cited by 6
Dynamic Privacy Pricing Based on Reinforcement Learning
Chen, X., Yu, Y., Xu, L., Lei, M., & Bi, W. (2018) · International Conference on Big Data and Computing (ICBDC) · doi:10.1145/3220199.3220227 · Cited by 6
A Unified Approach to Translate Classical Bandit Algorithms to Structured Bandits
Gupta, S., Chaudhari, S., Mukherjee, S., Joshi, G., & Yağan, O. (2021) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp39728.2021.9413628 · Cited by 6
Wang, Y., & Masoud, N. (2021) · IEEE Access · doi:10.1109/access.2021.3120700 · Cited by 7
Delay-Optimal Scheduling for Integrated mmWave Sub-6 GHz Systems with Markovian Blockage Model
Yao, G., Hashemi, M., Singh, R., & Shroff, N. B. (2022) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2022.3166990 · Cited by 6
On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
Nguyen-Tang, T., Yin, M., Gupta, S., Venkatesh, S., & Arora, R. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i8.26116 · Cited by 34
Safe Optimization of an Industrial Refrigeration Process Using an Adaptive and Explorative Framework
Korkmaz, B. S., Zagórowska, M., & Mercangöz, M. (2023) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2023.10.1811 · Cited by 6
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
Dagan, Y., Daskalakis, C., Fishelson, M., & Golowich, N. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649681 · Cited by 25
Online Learning and Game Theory. A Quick Overview with recent results and applications
Fauré, M., Gaillard, P., Gaujal, B., & Perchet, V. (2015) · ESAIM Proceedings and Surveys · doi:10.1051/proc/201551014 · Cited by 6
Posterior sampling for Monte Carlo planning under uncertainty
Bai, A., Wu, F., & Chen, X. (2018) · Applied Intelligence · doi:10.1007/s10489-018-1248-5 · Cited by 6
Carousel Ads Optimization in Yahoo Gemini Native
Aharon, M., Somekh, O., Shahar, A., Singer, A., Trayvas, B., Vogel, H., & Dobrev, D. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330740 · Cited by 6
Heuristic-Q: A Privacy Data Pricing Method Based on Heuristic Reinforcement Learning
Chen, X., Chen, J., Chen, Y., Yang, J., & Li, D. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-24268-8_51 · Cited by 6
Learning-based modular indirect adaptive control for a class of nonlinear systems
Benosman, M., Farahmand, A., & Xia, M. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7525001 · Cited by 6
Quasi-Stochastic Approximation and Off-Policy Reinforcement Learning
Bernstein, A., Chen, Y., Colombino, M., Dall’Anese, E., Mehta, P. G., & Meyn, S. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029247 · Cited by 6
Multiagent Low-Dimensional Linear Bandits
Chawla, R., Sankararaman, A., & Shakkottai, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3179521 · Cited by 6
Intra- and Inter-Server Smart Task Scheduling for Profit and Energy Optimization of HPC Data Centers
Mamun, S. A., Gilday, A., Singh, A. K., Ganguly, A., Merrett, G. V., Wang, X., & Al‐Hashimi, B. M. (2020) · Journal of Low Power Electronics and Applications · doi:10.3390/jlpea10040032 · Cited by 6
Secure Outsourcing of Multi-armed Bandits
Ciucanu, R., Lafourcade, P., Lombard-Platet, M., & Soare, M. (2020) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom50675.2020.00038 · Cited by 7
Neuroevolution-enhanced multi-objective optimization for mixed-precision quantization
Miret, S., Chua, V. S., Marder, M., Phielipp, M., Jain, N. K., & Majumdar, S. (2022) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3512290.3528692 · Cited by 12
Cascaded Algorithm Selection With Extreme-Region UCB Bandit
Hu, Y.-Q., Liu, X., Li, S.-Q., & Yang, Y. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3094844 · Cited by 6
Tong, J., Zhang, H., Fu, L., Leshem, A., & Han, Z. (2022) · IEEE Transactions on Communications · doi:10.1109/tcomm.2022.3161679 · Cited by 6
Nonparametric learning for impulse control problems—Exploration vs. exploitation
Christensen, S., & Strauch, C. (2023) · The Annals of Applied Probability · doi:10.1214/22-aap1849 · Cited by 6
Daisee: Adaptive importance sampling by balancing exploration and exploitation
Lu, X., Rainforth, T., & Teh, Y. W. (2023) · Scandinavian Journal of Statistics · doi:10.1111/sjos.12637 · Cited by 6
It's about time! Modeling customer behaviors as the secretary problem in daily deal websites
Zhao, T., Hu, M. M., Rahimi, R., & King, I. (2017) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2017.7966318 · Cited by 6
Competing Bandits: The Perils of Exploration Under Competition
Aridor, G., Mansour, Y., Slivkins, A., & Wu, Z. S. (2025) · ACM Transactions on Economics and Computation · doi:10.1145/3711831 · Cited by 6
Truthful learning mechanisms for multi-slot sponsored search auctions with externalities
Gatti, N., Lazaric, A., Rocco, M., & Trovò, F. (2015) · Artificial Intelligence · doi:10.1016/j.artint.2015.05.012 · Cited by 13
No-Regret Learning from Partially Observed Data in Repeated Auctions
Karaca, O., Sessa, P. G., Leidi, A., & Kamgarpour, M. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.029 · Cited by 6
Robust Bandit Learning with Imperfect Context
Yang, J., & Ren, S. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i12.17267 · Cited by 6
Takahashi, T., Kohno, Y., & Uragami, D. (2016) · Transactions of the Japanese Society for Artificial Intelligence · doi:10.1527/tjsai.ai30-m · Cited by 6
Online Learning for Wireless Distributed ComputingPreprint
Kao, Y.-H., Wright, K.-L., Krishnamachari, B., & Bai, F. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.02830 · Cited by 6
Deep Reinforcement Learning for Wireless Network
Sharma, B., Saini, R. K., Singh, A., & Singh, K. K. (2020) · Wiley eBooks · doi:10.1002/9781119640554.ch3 · Cited by 6
System-Level Digital Twin Modeling for Underwater Wireless IoT Networks
Wang, L., Yan, L., Li, X., & Han, S. (2024) · Journal of Marine Science and Engineering · doi:10.3390/jmse13010032 · Cited by 9
Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback
Ba, W., Lin, T., Zhang, J., & Zhou, Z. (2025) · Operations Research · doi:10.1287/opre.2021.0445 · Cited by 6
Learning the Optimal Path and DNN Partition for Collaborative Edge Inference
Huang, Y., Zhang, L., & Xu, J. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3602966 · Cited by 11
On some stochastic mirror descent methods for constrained online optimization problems
Alkousa, M. S. (2019) · Computer Research and Modeling · doi:10.20537/2076-7633-2019-11-2-205-217 · Cited by 5
Differentially Private and Budget-Limited Bandit Learning over Matroids
Han, K., He, Y., Liu, A. X., Tang, S., & Huang, H. (2020) · INFORMS journal on computing · doi:10.1287/ijoc.2019.0903 · Cited by 6
Multi-Item Nontruthful Auctions Achieve Good Revenue
Daskalakis, C., Fishelson, M., Lucier, B., Syrgkanis, V., & Velusamy, S. (2022) · SIAM Journal on Computing · doi:10.1137/22m1471742 · Cited by 5
Fair Probabilistic Multi-Armed Bandit With Applications to Network Optimization
Guo, Z., Zhang, C., Li, M., & Krunz, M. (2024) · IEEE Transactions on Machine Learning in Communications and Networking · doi:10.1109/tmlcn.2024.3421170 · Cited by 5
A Novel Use of Reinforcement Learning for Elevated Click-Through Rate in Online Advertising
Haider, U., & Yildiz, B. (2023) · 2023 International Conference on Computational Science and Computational Intelligence (CSCI) · doi:10.1109/csci62032.2023.00017 · Cited by 1
Learning Context-Aware Probabilistic Maximum Coverage Bandits: A Variance-Adaptive Approach
Liu, X., Zuo, J.-H., Wang, J., Wang, Z., Xu, Y.-D., & Lui, J. C. S. (2024) · IEEE Conference on Computer Communications · doi:10.1109/infocom52122.2024.10621257 · Cited by 6
A Federated Online Restless Bandit Framework for Cooperative Resource Allocation
Tong, J., Li, X., Fu, L., Zhang, J., & Letaief, K. B. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3453250 · Cited by 7
Belzner, L., & Gabor, T. (2016) · IEEE International Workshops on Foundations and Applications of Self* Systems (FAS*W) · doi:10.1109/fas-w.2016.36 · Cited by 5
Linear UCB for Online SON Management
Daher, T., Jemaa, S. B., & Decreusefond, L. (2018) · IEEE Vehicular Technology Conference · doi:10.1109/vtcspring.2018.8417683 · Cited by 5
Learning Frameworks for Dynamic Joint RF Energy Harvesting and Channel Access
Sangare, F., Nguyen, D. H. N., & Han, Z. (2019) · IEEE Access · doi:10.1109/access.2019.2925281 · Cited by 5
Spectrum Sharing Among Rapidly Deployable Small Cells: A Hybrid Multi-Agent Approach
Gao, B., Lu, L., Xiong, K., Park, J.-M. J., Yang, Y., & Wang, Y. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2945712 · Cited by 5
Contextual combinatorial conservative bandits
Zhang, X., Liu, W., Li, S., & Zhang, S. (2026) · Theoretical Computer Science · doi:10.1016/j.tcs.2026.115966 · Cited by 7
Stochastic One-Sided Full-Information Bandit
Zhao, H., & Chen, W. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-46133-1_10 · Cited by 5
Reconfigurable and Computationally Efficient Architecture for Multi-Armed Bandit Algorithms
Santosh, S. V. S., & Darak, S. J. (2020) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas45731.2020.9180702 · Cited by 5
Batched Learning in Generalized Linear Contextual Bandits With General Decision Sets
Ren, Z., Zhou, Z., & Kalagnanam, J. (2020) · IEEE Control Systems Letters · doi:10.1109/lcsys.2020.3047601 · Cited by 5
Periodic Updates for Constrained OCO with Application to Large-Scale Multi-Antenna Systems
Wang, J., Dong, M., Liang, B., & Boudreau, G. (2022) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2022.3194357 · Cited by 5
Bandit-Based Power Control in Full-Duplex Cooperative Relay Networks
Νομικός, Ν., Charalambous, T., & Wichman, R. (2021) · International Conference on Communications · doi:10.1109/icc42927.2021.9501010 · Cited by 5
Learning the Optimal Controller Placement in Mobile Software-Defined Networks
Koutsopoulos, I. (2022) · IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM) · doi:10.1109/wowmom54355.2022.00029 · Cited by 5
Conversion-Based Dynamic-Creative-Optimization in Native Advertising
Kaplan, Y., Shtoff, A., Shadi, T., Somekh, O., & Koren, Y. (2022) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata55660.2022.10020498 · Cited by 5
Weighted Restless Bandit and Its Applications
Wan, P., & Xu, X. (2015) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2015.58 · Cited by 5
Contextual bandits with hidden contexts: a focused data capture from social media streams
Lamprier, S., Gisselbrecht, T., & Gallinari, P. (2019) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-019-00648-w · Cited by 5
Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory
Su, L., Zubeldía, M., & Lynch, N. A. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3322205.3311082 · Cited by 5
Kernel-based Multi-Task Contextual Bandits in Cellular Network Configuration
Wang, X., Guo, X., Chuai, J., Chen, Z., & Liu, X. (2019) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata47090.2019.9006449 · Cited by 5
Contextual Multi-armed Bandit Based Pricing Scheme for Cooperative D2D Communications
Meng, Y., & Wang, Z. (2020) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc45663.2020.9120767 · Cited by 5
No-Regret Learning from Partially Observed Data in Repeated Auctions
Karaca, O., Sessa, P. G., Leidi, A., & Kamgarpour, M. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000428693 · Cited by 5
A Novel Approach to Address External Validity Issues in Fault Prediction Using Bandit Algorithms
Hayakawa, T., Tsunoda, M., Toda, K., Nakasai, K., Tahir, A., Bennin, K. E., Monden, A., & Matsumoto, K. (2021) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2020edl8098 · Cited by 5
Modeling Attrition in Recommender Systems with Departing Bandits
Ben-Porat, O., Cohen, L., Leqi, L., Lipton, Z. C., & Mansour, Y. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20554 · Cited by 5
Mixed-Input Bayesian Optimization Method for Structural Damage Diagnosis
Huang, C., Lee, J., Zhang, Y., Zhou, S., & Tang, J. (2022) · IEEE Transactions on Reliability · doi:10.1109/tr.2022.3179602 · Cited by 6
Best Arm Identification in Restless Markov Multi-Armed Bandits
Karthik, P. N., Reddy, K. S., & Tan, V. Y. F. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3230939 · Cited by 5
Beznosikov, A., Stepanov, I., Voronov, A., & Gasnikov, A. (2021) · Optim. Methods Softw. · doi:10.1080/10556788.2025.2502829 · Cited by 7
Locality-Sensitive Linear Bandit Model for Online Social Recommendation
Zhao, T., & King, I. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46687-3_9 · Cited by 5
Li, Y., Reyes, K. G., Vazquez-Anderson, J., Wang, Y., Contreras, L. M., & Powell, W. B. (2018) · INFORMS journal on computing · doi:10.1287/ijoc.2017.0803 · Cited by 5
Persistent Surveillance of Events with Unknown Rate Statistics
Baykal, C., Rosman, G., Kotowick, K., Donahue, M., & Rus, D. L. (2020) · Springer proceedings in advanced robotics · doi:10.1007/978-3-030-43089-4_47 · Cited by 5
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.038 · Cited by 5
Sparse Stochastic BanditsPreprint
Kwon, J., Perchet, V., & Vernade, C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.01383 · Cited by 10
Stochastic Selection Problems with TestingPreprint
Attias, C., Krauthgamer, R., Levi, R., & Shaposhnik, Y. (2017) · SSRN Electronic Journal · doi:10.2139/ssrn.3076956 · Cited by 5
Online Learning and Optimization for Revenue Management Problems with Add-on DiscountsPreprint
Simchi‐Levi, D., Sun, R., & Zhang, H. (2020) · SSRN Electronic Journal · doi:10.2139/ssrn.3591281 · Cited by 5
Busacca, F., Palazzo, S., Raftopoulos, R., & Schembra, G. (2025) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2025.3577726 · Cited by 4
Busacca, F., Galluccio, L., Palazzo, S., Panebianco, A., & Raftopoulos, R. (2025) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2025.3629240 · Cited by 4
Data distribution tailoring revisited: cost-efficient integration of representative data
Chang, J., Cui, B., Nargesian, F., Asudeh, A., & Jagadish, H. V. (2024) · The VLDB Journal · doi:10.1007/s00778-024-00849-w · Cited by 8
Combinatorial Incentive Mechanism for Bundling Spatial Crowdsourcing with Unknown Utilities
Wang, H., Cui, L., Zhang, L., Shen, L., & Chen, L. (2024) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom52122.2024.10621352 · Cited by 4
Adaptive ambiguity-aware weighting for multi-label recognition with limited annotations
Shrewsbury, D., Kim, S., & Lee, S. (2024) · Neural Networks · doi:10.1016/j.neunet.2024.106642 · Cited by 4
Mitigating bias in heterogeneous federated learning via stratified client selection
Liu, Y., Xia, H., Li, W., & Niu, T. (2025) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-024-01886-6 · Cited by 4
Dai, X., Liu, X., Zuo, J., Xie, H. L., Joe‐Wong, C., & Lui, J. C. S. (2025) · IEEE Transactions on Networking · doi:10.1109/ton.2024.3519568 · Cited by 4
Dynamic Channel Allocation via Bandit Learning for WiFi 7 Networks with Multi-Link Operation
Lian, S., Tong, J., & Fu, L. (2025) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc61545.2025.10978791 · Cited by 4
Teaming in the AI Era: AI-Augmented Frameworks for Forming, Simulating, and Optimizing Human Teams
Almutairi, M. (2025) · ACM Conference on User Modeling, Adaptation and Personalization (UMAP) · doi:10.1145/3699682.3727574 · Cited by 4
UAV-Centric Privacy-Preserving Computation Offloading in Multi-UAV Mobile Edge Computing
Gao, C., Wei, D., Li, K., & Liu, W. (2025) · Drones · doi:10.3390/drones9100701 · Cited by 4
Collet, T., & Pietquin, O. (2015) · Computational Intelligence and Neuroscience · doi:10.1155/2015/973696 · Cited by 7
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.