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 301–400 of 1,003
Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
Sinclair, S. R., Banerjee, S., & Yu, C. L. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3366703 · Cited by 21
Zhou, P., Yan, Q., Wang, K., Xu, Z., Ji, S., & Bian, K. (2019) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2019.2955464 · Cited by 21
Reinforcement Learning Approaches in Social Robotics
Akalın, N., & Loutfi, A. (2021) · Sensors · doi:10.3390/s21041292 · Cited by 192
Massive Unsourced Random Access for Massive MIMO Correlated Channels
Xie, X., Wu, Y., Gao, J., & Zhang, W. (2020) · Globecom · doi:10.1109/globecom42002.2020.9347959 · Cited by 21
Optimal Policy for Dynamic Assortment Planning Under Multinomial Logit Models
Chen, X., Wang, Y., & Zhou, Y. (2021) · Mathematics of Operations Research · doi:10.1287/moor.2021.1133 · Cited by 35
The Externalities of Exploration and How Data Diversity Helps Exploitation
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603208 · Cited by 21
Sequential decision-making in mining and processing based on geometallurgical inputs
Koch, P.-H., & Rosenkranz, J. (2020) · Minerals Engineering · doi:10.1016/j.mineng.2020.106262 · Cited by 20
An integrated development environment for faster feature engineering
Anderson, M. R., Cafarella, M., Jiang, Y., Wang, G., & Zhang, B. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2733004.2733054 · Cited by 20
Chambaz, A., Zheng, W., & van der Laan, M. J. (2017) · The Annals of Statistics · doi:10.1214/16-aos1534 · Cited by 20
An Online Minimax Optimal Algorithm for Adversarial Multiarmed Bandit Problem
Gökcesu, K., & Kozat, S. S. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2806006 · Cited by 20
CBA: Contextual Quality Adaptation for Adaptive Bitrate Video Streaming
Alt, B., Ballard, T., Steinmetz, R., Koeppl, H., & Rizk, A. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737418 · Cited by 21
Online Optimization Using Zeroth Order Oracles
Shames, I., Selvaratnam, D., & Manton, J. H. (2019) · IEEE Control Systems Letters · doi:10.1109/lcsys.2019.2921593 · Cited by 20
Learning Product Rankings Robust to Fake Users
Golrezaei, N., Manshadi, V., Schneider, J., & Sekar, S. (2020) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3465456.3467580 · Cited by 24
Wu, J., Zhou, P., Chen, Q., Xu, Z., Ding, X., & Jiang, H. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3133653 · Cited by 23
History of seeking better solutions, AKA simulation optimization
Fu, M. C., & Henderson, S. G. (2017) · Winter Simulation Conference · doi:10.1109/wsc.2017.8247787 · Cited by 27
Convergence of heterogeneous distributed learning in stochastic routing games
Krichene, S., Krichene, W., Dong, R., & Bayen, A. M. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447043 · Cited by 20
Building Bridges: Viewing Active Learning from the Multi-Armed Bandit LensPreprint
Ganti, R., & Gray, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.6830 · Cited by 20
Optimization of a SSP's Header Bidding Strategy using Thompson Sampling
Jauvion, G., Grislain, N., Sielenou, P. D., Garivier, A., & Gerchinovitz, S. (2018) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3219819.3219917 · Cited by 22
A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting
Gupta, S., Chaudhari, S., Mukherjee, S., Joshi, G., & Yağan, O. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.3041246 · Cited by 26
An Adaptive Targeted Field Experiment: Job Search Assistance for Refugees in Jordan
Caria, S. A., Gordon, G., Kasy, M., Quinn, S., Shami, S., & Teytelboym, A. (2023) · Journal of the European Economic Association · doi:10.1093/jeea/jvad067 · Cited by 42
Νομικός, Ν., Talebi, M. S., Charalambous, T., & Wichman, R. (2022) · IEEE Open Journal of the Communications Society · doi:10.1109/ojcoms.2022.3154292 · Cited by 19
Bandit-based inventory optimisation: Reinforcement learning in multi-echelon supply chains
Preil, D., & Krapp, M. (2022) · International Journal of Production Economics · doi:10.1016/j.ijpe.2022.108578 · Cited by 21
A Unified and Efficient Coordinating Framework for Autonomous DBMS Tuning
Zhang, X., Chang, Z., Wu, H., Li, Y., Chen, J., Tan, J. R., Li, F., & Cui, B. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3589331 · Cited by 19
Resource Allocation for LoRaWAN Network Slicing: Multi-Armed Bandit-based Approaches
Mardi, F. Z., Hadjadj‐Aoul, Y., Bagaa, M., & Benamar, N. (2024) · Internet of Things · doi:10.1016/j.iot.2024.101195 · Cited by 19
Pure Exploration for Max-Quantile Bandits
David, Y., & Shimkin, N. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46128-1_35 · Cited by 19
Finite budget analysis of multi-armed bandit problems
Xia, Y., Qin, T., Ding, W., Li, H., Zhang, X., Yu, N., & Liu, T. (2017) · Neurocomputing · doi:10.1016/j.neucom.2016.12.079 · Cited by 19
Spectrometry analysis based on approximation coefficients and deep belief networks
He, J., Tang, X., Gong, P., Wang, P., Han, Z., Yan, W. J., & Gao, L. (2018) · Nuclear Science and Techniques · doi:10.1007/s41365-018-0402-4 · Cited by 19
On the Prior Sensitivity of Thompson Sampling
Liu, C.-Y., & Li, L. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46379-7_22 · Cited by 20
Rethinking search engines and recommendation systems: a game theoretic perspective
Tennenholtz, M., & Kurland, O. (2019) · Communications of the ACM · doi:10.1145/3340922 · Cited by 21
Fair Incentive Mechanism With Imperfect Quality in Privacy-Preserving Crowdsensing
Li, Y., Li, F., Zhu, L., Chen, H., Li, T., & Wang, Y. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3164664 · Cited by 19
Toward Optimal Adaptive Wireless Communications in Unknown Environments
Zhou, P., & Jiang, T. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2524638 · Cited by 20
Spectrum Sensing Across Multiple Service Providers: A Discounted Thompson Sampling Method
Zhou, M., Wang, T., & Wang, S. (2019) · IEEE Communications Letters · doi:10.1109/lcomm.2019.2941717 · Cited by 19
Balancing exploration and exploitation with information and randomizationPreprint
Wilson, R. C., Bonawitz, E. B., Costa, V. D., & Ebitz, R. B. (2020) · PsyArXiv (OSF Preprints) · doi:10.31234/osf.io/e9azw · Cited by 21
Multi-User Multi-Armed Bandits for Uncoordinated Spectrum Access
Bande, M., & Veeravalli, V. V. (2019) · 2012 International Conference on Computing, Networking and Communications (ICNC) · doi:10.1109/iccnc.2019.8685615 · Cited by 18
Learning Algorithms for Minimizing Queue Length Regret
Stahlbuhk, T., Shrader, B., & Modiano, E. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437817 · Cited by 18
Shen, C., Zhang, X., Wei, W., & Xu, J. (2023) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3583780.3614921 · Cited by 20
Networked bandits with disjoint linear payoffs
Fang, M., & Tao, D. (2014) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623672 · Cited by 18
Bandit-Based Task Assignment for Heterogeneous Crowdsourcing
Zhang, H., Ma, Y., & Sugiyama, M. (2015) · Neural Computation · doi:10.1162/neco_a_00782 · Cited by 21
Feng, Y., Zhou, P., Wu, D. O., & Hu, Y. (2018) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2018.2804335 · Cited by 18
Correlated Multi-Armed Bandits with A Latent Random Source
Gupta, S., Joshi, G., & Yağan, O. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054429 · Cited by 18
On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables
Arbel, J., Marchal, O., & Nguyen, H. D. (2019) · ESAIM Probability and Statistics · doi:10.1051/ps/2019018 · Cited by 37
Scaling Multi-Armed Bandit Algorithms
Fouché, E., Komiyama, J., & Böhm, K. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330862 · Cited by 20
Automating Deep Neural Network Model Selection for Edge Inference
Lu, B., Yang, J., Chen, L. Y., & Ren, S. (2019) · IEEE International Conference on Cognitive Machine Intelligence (CogMI) · doi:10.1109/cogmi48466.2019.00035 · Cited by 24
Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures
Verstraeten, T., Bargiacchi, E., Libin, P., Helsen, J., Roijers, D. M., & Nowé, A. (2020) · Scientific Reports · doi:10.1038/s41598-020-62939-3 · Cited by 18
Distributed learning dynamics of Multi-Armed Bandits for edge intelligence
Chen, S., Tao, Y., Yu, D., Li, F., & Gong, B. (2020) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2020.101919 · Cited by 18
Stochastic bandits with side observations on networks
Buccapatnam, S., Eryılmaz, A., & Shroff, N. B. (2014) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2637364.2591989 · Cited by 24
Online Collaborative Filtering on Graphs
Banerjee, S., Sanghavi, S., & Shakkottai, S. (2016) · Operations Research · doi:10.1287/opre.2016.1508 · Cited by 20
Load Prediction for Energy-Aware Scheduling for Cloud Computing Platforms
Dambreville, A., Tomasik, J., Cohen, J., & Dufoulon, F. (2017) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2017.201 · Cited by 18
Recent Advances in Multiarmed Bandits for Sequential Decision Making
Agrawal, S. (2019) · doi:10.1287/educ.2019.0204 · Cited by 19
Ghosh, A., Chowdhury, S. R., & Gopalan, A. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.11052 · Cited by 17
Privacy-preserving Stable Crowdsensing Data Trading for Unknown Market
Sun, H., Xiao, M., Xu, Y., Gao, G., & Zhang, S. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228966 · Cited by 17
Trends in Mobile Cyber-Physical Systems for health Just-in time interventions
Jaimes, L. G., Calderón, J. M., Lopez, J. G., & Raij, A. B. (2015) · IEEE SoutheastCon · doi:10.1109/secon.2015.7132887 · Cited by 17
Dynamic Information Retrieval Modeling
Yang, G. H., Sloan, M., & Wang, Y.-X. (2016) · Synthesis lectures on information concepts, retrieval, and services · doi:10.2200/s00718ed1v01y201605icr049 · Cited by 23
Functional Sequential Treatment Allocation
Kock, A., Preinerstorfer, D., & Veliyev, B. (2020) · Journal of the American Statistical Association · doi:10.1080/01621459.2020.1851236 · Cited by 24
Online Learning for Measuring Incentive Compatibility in Ad Auctions?
Feng, Z., Schrijvers, O., & Sodomka, E. (2019) · International World Wide Web Conference (WWW) · doi:10.1145/3308558.3313674 · Cited by 17
Online Power Optimization in Feedback-Limited, Dynamic and Unpredictable IoT Networks
Marcastel, A., Belmega, E. V., Mertikopoulos, P., & Fijalkow, I. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2910479 · Cited by 17
Content Harvest Network: Optimizing First Mile for Crowdsourced Live Streaming
Pang, H., Wang, Z., Yan, C., Ding, Q., Yi, K., Liu, J., & Sun, L. (2018) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2018.2862619 · Cited by 17
Fast Reconfigurable Antenna State Selection with Hierarchical Thompson Sampling
Zhao, T., Li, M., & Poloczek, M. (2019) · International Conference on Communications · doi:10.1109/icc.2019.8761809 · Cited by 17
Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial BanditsPreprint
Zimmert, J., & Seldin, Y. (2018) · Research at the University of Copenhagen (University of Copenhagen) · doi:10.48550/arxiv.1807.07623 · Cited by 24
Optimizing mHealth Interventions with a Bandit
Rabbi, M., Klasnja, P., Choudhury, T., Tewari, A., & Murphy, S. A. (2019) · Studies in neuroscience, psychology and behavioral economics · doi:10.1007/978-3-030-31620-4_18 · Cited by 17
QTAccel: A Generic FPGA based Design for Q-Table based Reinforcement Learning Accelerators
Meng, Y., Kuppannagari, S. R., Rajat, R., Srivastava, A., Kannan, R., & Prasanna, V. K. (2020) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw50202.2020.00024 · Cited by 17
A General Framework for Bandit Problems Beyond Cumulative Objectives
Cassel, A., Mannor, S., & Zeevi, A. J. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.1335 · Cited by 20
Learning to Schedule Network Resources Throughput and Delay Optimally Using Q+-Learning
Bae, J., Lee, J., & Chong, S. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3051663 · Cited by 21
Online influence maximization in non-stationary Social Networks
Bao, Y., Wang, X., Wang, Z., Wu, C., & Lau, F. C. M. (2016) · International Workshop on Quality of Service · doi:10.1109/iwqos.2016.7590438 · Cited by 17
Bayesian Optimisation of Large-Scale Biophysical Networks
Hadida, J., Sotiropoulos, S. N., Abeysuriya, R., Woolrich, M. W., & Jbabdi, S. (2018) · NeuroImage · doi:10.1016/j.neuroimage.2018.02.063 · Cited by 21
The Political Economy of AI: Towards Democratic Control of the Means of PredictionPreprint
Kasy, M. (2023) · SSRN Electronic Journal · doi:10.31235/osf.io/x7pcy · Cited by 18
Book announcement: Introduction to Multi-Armed Bandits
Slivkins, A. (2020) · ACM SIGecom Exchanges · doi:10.1145/3440959.3440965 · Cited by 16
Alban, A., Chick, S. E., & Förster, M. (2022) · Management Science · doi:10.1287/mnsc.2022.4540 · Cited by 17
Distributed Online Private Learning of Convex Nondecomposable Objectives
Cheng, H., Liao, X., & Li, H. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3329832 · Cited by 18
LinkSelFiE: Link Selection and Fidelity Estimation in Quantum Networks
Liu, M., Li, Z., Wang, X., & Lui, J. C. S. (2024) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom52122.2024.10621263 · Cited by 23
Small Cell Transmit Power Assignment Based on Correlated Bandit Learning
Wang, Z., & Shen, C. (2017) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2017.2679660 · Cited by 16
Dual-Mandate Patrols: Multi-Armed Bandits for Green Security
Xu, L., Bondi, E., Fang, F., Perrault, A., Wang, K., & Tambe, M. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i17.17757 · Cited by 16
Decentralized Heterogeneous Multi-Player Multi-Armed Bandits With Non-Zero Rewards on Collisions
Magesh, A., & Veeravalli, V. V. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3136095 · Cited by 24
Online-Learning-Based Defense Against Jamming Attacks in Multichannel Wireless CPS
Alipour-Fanid, A., Dabaghchian, M., Wang, N., Jiao, L., & Zeng, K. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3066476 · Cited by 16
Ensemble Wrapper Subsampling for Deep Modulation Classification
Ramjee, S., Ju, S., Yang, D., Liu, X., Gamal, A. E., & Eldar, Y. C. (2021) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2021.3108809 · Cited by 16
Truthful Learning Mechanisms for Multi–Slot Sponsored Search Auctions with ExternalitiesPreprint
Gatti, N., Lazaric, A., & Rocco, M. (2016) · Cited by 16
Adaptive Discretization in Online Reinforcement Learning
Sinclair, S. R., Banerjee, S., & Yu, C. L. (2022) · Operations Research · doi:10.1287/opre.2022.2396 · Cited by 21
Yi, Y., Zhu, N., He, J., Jurcut, A. D., Ma, X., & Luo, Y. (2023) · Computer Communications · doi:10.1016/j.comcom.2023.01.010 · Cited by 16
Costa, R. D., Hirata, C. M., & Pugliese, V. U. (2023) · IEEE Access · doi:10.1109/access.2023.3245055 · Cited by 13
Totoro: A Scalable Federated Learning Engine for the Edge
Ching, C.-W., Chen, X., Kim, T., Ji, B., Wang, Q., Silva, D. D., & Hu, L. (2024) · European Conference on Computer Systems · doi:10.1145/3627703.3629575 · Cited by 25
AgileDART: An Agile and Scalable Edge Stream Processing Engine
Ching, C.-W., Chen, X., Kim, C., Wang, T., Chen, D., Silva, D. D., & Hu, L. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3526143 · Cited by 21
Rabbi, M., Aung, M. H., & Choudhury, T. (2017) · Springer eBooks · doi:10.1007/978-3-319-51394-2_26 · Cited by 18
Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures
Neyshabouri, M. M., Gökcesu, K., Gökcesu, H., Özkan, H., & Kozat, S. S. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2854796 · Cited by 15
Delay-Optimal Task Offloading for Dynamic Fog Networks
Tan, Y., Wang, K., Yang, Y., & Zhou, M. (2019) · International Conference on Communications · doi:10.1109/icc.2019.8761113 · Cited by 16
Competitive Online Optimization under Inventory Constraints
Lin, Q., Yi, H., Pang, J., Chen, M., Wierman, A., Honig, M. L., & Xiao, Y. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3322205.3311081 · Cited by 36
Smoothness-Adaptive Contextual Bandits
Gur, Y., Momeni, A., & Wager, S. (2022) · Operations Research · doi:10.1287/opre.2021.2215 · Cited by 19
A Method for Optimizing Opaque Filter Queries
He, W., Anderson, M. R., Strome, M. B., & Cafarella, M. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3389766 · Cited by 16
Bayesian Meta-Prior Learning Using Empirical Bayes
Nabi, S., Nassif, H., Hong, J., Mamani, H., & Imbens, G. W. (2021) · Management Science · doi:10.1287/mnsc.2021.4136 · Cited by 21
A revised approach for risk-averse multi-armed bandits under CVaR criterion
Khajonchotpanya, N., Xue, Y., & Rujeerapaiboon, N. (2021) · Operations Research Letters · doi:10.1016/j.orl.2021.05.005 · Cited by 15
Asynchronous parallel Bayesian optimization for AI-driven cloud laboratories
Frisby, T. S., Gong, Z., & LANGMEAD, C. J. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab291 · Cited by 15
Umami, I. (2021) · Journal of Applied Data Sciences · doi:10.47738/jads.v2i2.28 · Cited by 15
Combination of Auction Theory and Multi-Armed Bandits: Model, Algorithm, and Application
Gao, G., Huang, S., Huang, H., Xiao, M., Wu, J., Sun, Y.-E., & Zhang, S. (2022) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2022.3197459 · Cited by 15
Getting the Best Out of Both Worlds: Algorithms for Hierarchical Inference at the Edge
Moothedath, V. N., Champati, J. P., & Gross, J. (2024) · IEEE Transactions on Machine Learning in Communications and Networking · doi:10.1109/tmlcn.2024.3366501 · Cited by 19
Distributed Emergent Software: Assembling, Perceiving and Learning Systems at Scale
Porter, B., & Filho, R. R. (2019) · IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO) · doi:10.1109/saso.2019.00024 · Cited by 15
Linear Thompson Sampling Under Unknown Linear Constraints
Moradipari, A., Alizadeh, M., & Thrampoulidis, C. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9053865 · Cited by 15
Multi-Player Multi-Armed Bandits With Collision-Dependent Reward Distributions
Shi, C., & Shen, C. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3093261 · Cited by 15
Randomized Gradient-Free Methods in Convex Optimization
Gasnikov, A. V., Dvinskikh, D., Dvurechensky, P. E., Gorbunov, E., Beznosikov, A. N., & Lobanov, A. (2023) · Springer eBooks · doi:10.1007/978-3-030-54621-2_859-1 · Cited by 19
Designing Lookahead Policies for Sequential Decision Problems in Transportation and Logistics
Powell, W. B. (2022) · IEEE Open Journal of Intelligent Transportation Systems · doi:10.1109/ojits.2022.3148574 · Cited by 14
Noisy Zeroth-Order Optimization for Non-smooth Saddle Point Problems
Dvinskikh, D., Tominin, V., Tominin, I., & Gasnikov, A. V. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-09607-5_2 · Cited by 14
Model-Based Thompson Sampling for Frequency and Rate Selection in Underwater Acoustic Communications
Tong, J., Fu, L., Wang, Y., & Han, Z. (2023) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2023.3247450 · Cited by 14
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.