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 401–500 of 1,003
Liu, J., Liu, J., Xu, H., Liao, Y., Yao, Z., Chen, M., & Qian, C. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3492140 · Cited by 22
Reinforcement learning applied to a situation awareness decision-making model
Costa, R. D., & Hirata, C. M. (2025) · Information Sciences · doi:10.1016/j.ins.2025.121928 · Cited by 14
Strategic Conversations Under Imperfect Information: Epistemic Message Exchange Games
Asher, N. M., & Paul, S. (2018) · Journal of Logic Language and Information · doi:10.1007/s10849-018-9271-9 · Cited by 14
Learn and Pick Right Nodes to Offload
Zhu, Z., Liu, T., Jin, S., & Luo, X. (2018) · Globecom · doi:10.1109/glocom.2018.8648042 · Cited by 14
Learning to Rank: Regret Lower Bounds and Efficient Algorithms
Combes, R., Magureanu, S., Proutière, A., & Laroche, C. (2015) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2796314.2745852 · Cited by 22
Gan, C., Zhou, R., Yang, J., & Shen, C. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3001388 · Cited by 14
Lumbreras, J., Haapasalo, E., & Tomamichel, M. (2022) · Quantum · doi:10.22331/q-2022-06-29-749 · Cited by 27
Lai, P., Wang, R., Zhang, W., & Xu, H. (2021) · Physics of Fluids · doi:10.1063/5.0068454 · Cited by 18
Learning on the Job: Long-Term Behavioural Adaptation in Human-Robot Interactions
Duchetto, F. D., & Hanheide, M. (2022) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2022.3178807 · Cited by 21
Efficient approximate thompson sampling for search query recommendation
Hsieh, C.-C., Neufeld, J., King, T. H., & Cho, J. J. (2015) · ACM Symposium on Applied Computing · doi:10.1145/2695664.2695748 · Cited by 15
Learning in auctions: Regret is hard, envy is easy
Daskalakis, C., & Syrgkanis, V. (2022) · Games and Economic Behavior · doi:10.1016/j.geb.2022.03.001 · Cited by 14
OnPlan: A Framework for Simulation-Based Online Planning
Belzner, L., Hennicker, R., & Wirsing, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-28934-2_1 · Cited by 14
Thresholding Bandits with Augmented UCB
Mukherjee, S., Naveen, K. P., Sudarsanam, N., & Ravindran, B. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/350 · Cited by 28
Multi-armed Bandit Based Hyper-Heuristics for the Permutation Flow Shop Problem
de Almeida, C. P., Gonçalves, R. A., Venske, S. M., Lüders, R., & Delgado, M. (2018) · Brazilian Conference on Intelligent Systems · doi:10.1109/bracis.2018.00032 · Cited by 14
Adaptive Matching for Expert Systems with Uncertain Task Types
Shah, V., Gulikers, L., Massoulié, L., & Vojnović, M. (2020) · Operations Research · doi:10.1287/opre.2019.1954 · Cited by 14
Energy-Aware Task Allocation for Mobile IoT by Online Reinforcement Learning
Yao, J., & Ansari, N. (2019) · International Conference on Communications · doi:10.1109/icc.2019.8761509 · Cited by 14
A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems
Meshram, R. H., Gopalan, A., & Manjunath, D. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-67235-9_19 · Cited by 14
Contextual Bandit-Based Sequential Transit Route Design under Demand Uncertainty
Yoon, G., & Chow, J. Y. J. (2020) · Transportation Research Record Journal of the Transportation Research Board · doi:10.1177/0361198120917388 · Cited by 14
Arya, S., & Yang, Y. (2020) · Statistics & Probability Letters · doi:10.1016/j.spl.2020.108818 · Cited by 26
Atan, O., Tekin, C., & van der Schaar, M. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2818742 · Cited by 14
Approximation Algorithms for Stochastic Combinatorial Optimization Problems
Li, J., & Liu, Y. (2016) · Journal of the Operations Research Society of China · doi:10.1007/s40305-015-0116-9 · Cited by 16
CBRAP: Contextual Bandits with RAndom Projection
Yu, X., Lyu, M. R.-T., & King, I. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10888 · Cited by 14
Distributed Bandits with Heterogeneous Agents
Yang, L., Chen, Y.-Z. J., Hajiemaili, M. H., Lui, J. C. S., & Towsley, D. (2022) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom48880.2022.9796901 · Cited by 18
Quantum Bandit With Amplitude Amplification Exploration in an Adversarial Environment
Cho, B., Xiao, Y., Hui, P., & Dong, D. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3279207 · Cited by 16
Adversarial Group Linear Bandits and Its Application to Collaborative Edge Inference
Huang, Y., Zhang, L., & Xu, J. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228900 · Cited by 13
Cloud storage tier optimization through storage object classification
Khan, A. Q., Matskin, M., Prodan, R., Bussler, C. J., Roman, D., & Soylu, A. (2024) · Computing · doi:10.1007/s00607-024-01281-2 · Cited by 18
Learning-based hybrid TDMA-CSMA MAC protocol for virtualized 802.11 WLANs
Shoaei, A. D., Derakhshani, M., Parsaeefard, S., & Le‐Ngoc, T. (2015) · IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) · doi:10.1109/pimrc.2015.7343602 · Cited by 13
Efficient and flexible crowdsourcing of specialized tasks with precedence constraints
Chatterjee, A., Borokhovich, M., Varshney, L. R., & Vishwanath, S. (2016) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2016.7524615 · Cited by 13
A practical approach to sample size calculation for fixed populations
Kaptein, M. C. (2019) · Contemporary Clinical Trials Communications · doi:10.1016/j.conctc.2019.100339 · Cited by 20
Entropic Regularization of Markov Decision Processes
Belousov, B., & Peters, J. (2019) · Entropy · doi:10.3390/e21070674 · Cited by 28
Decentralized Spectrum Learning for IoT Wireless Networks Collision Mitigation
Moy, C., & Besson, L. (2019) · International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT) · doi:10.1109/dcoss.2019.00117 · Cited by 16
Online reinforcement learning for adaptive interference coordination
Alcaraz, J. J., Ayala‐Romero, J. A., Vales‐Alonso, J., & Losilla, F. (2020) · Transactions on Emerging Telecommunications Technologies · doi:10.1002/ett.4087 · Cited by 13
A Regret Analysis of Bilateral Trade
Cesa-Bianchi, N., Cesari, T., Colomboni, R., Fusco, F., & Leonardi, S. (2021) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3465456.3467645 · Cited by 13
Self-citationBanditMTL: Bandit-based Multi-task Learning for Text Classification
Mao, Y., Wang, Z., Liu, W., Lin, X., & Hu, W. (2021) · doi:10.18653/v1/2021.acl-long.428 · Cited by 13
Machine Learning for Data Management: A System View
Li, G., & Zhou, X. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00297 · Cited by 13
Weak Signal Asymptotics for Sequentially Randomized Experiments
Xu, K., & Wager, S. (2023) · Management Science · doi:10.1287/mnsc.2023.4964 · Cited by 50
A Distributionally Robust Approach to Regret Optimal Control using the Wasserstein Distance
Taha, F. A., Yan, S., & Bitar, E. Y. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10384311 · Cited by 13
Work capacity of freelance markets: Fundamental limits and decentralized schemes
Chatterjee, A., Varshney, L. R., & Vishwanath, S. (2015) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2015.7218558 · Cited by 13
Interactive Intent Modeling from Multiple Feedback Domains
Daee, P., Pyykkö, J., Głowacka, D., & Samuel Kaski, A. (2016) · ACM International Conference on Intelligent User Interfaces (IUI) · doi:10.1145/2856767.2856803 · Cited by 13
No-regret replanning under uncertainty
Sun, W., Sood, N., Dey, D., Ranade, G. V., Prakash, S., & Kapoor, A. (2017) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2017.7989758 · Cited by 17
Online learning-based clustering approach for news recommendation systems
Nguyen, M. N. H., Pham, C., Son, J., & Hong, C. S. (2016) · Asia-Pacific Network Operations and Management Symposium (APNOMS) · doi:10.1109/apnoms.2016.7737269 · Cited by 13
Vriens, E., & Corten, R. (2018) · Social Networks · doi:10.1016/j.socnet.2018.01.007 · Cited by 13
Beyond the Click-Through Rate: Web Link Selection with Multi-level Feedback
Chen, K., Cai, K., Huang, L., & Lui, J. C. S. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/459 · Cited by 13
Moy, C., Besson, L., Delbarre, G., & Toutain, L. (2020) · Annals of Telecommunications · doi:10.1007/s12243-020-00795-y · Cited by 15
Zeroth-Order Algorithms for Smooth Saddle-Point Problems
Sadiev, A., Beznosikov, A. N., Dvurechensky, P. E., & Gasnikov, A. V. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-86433-0_5 · Cited by 13
Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games
Kovařík, V., & Lisý, V. (2019) · Machine Learning · doi:10.1007/s10994-019-05832-z · Cited by 14
Socially-Optimal Mechanism Design for Incentivized Online Learning
Wang, Z., Gao, L., & Huang, J. (2022) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom48880.2022.9796676 · Cited by 12
Mohamed, E. M., Hashima, S., Anjum, N., Hatano, K., Shafai, W. E., & ElHalawany, B. M. (2022) · IET Communications · doi:10.1049/cmu2.12474 · Cited by 12
Guo, Y., & Shmaya, E. (2025) · American Economic Review · doi:10.1257/aer.20191950 · Cited by 12
Artificial Intelligence-Based Decision Support Systems for Precision and Digital Health
Deliu, N., & Chakraborty, B. (2025) · Springer eBooks · doi:10.1007/978-981-96-0742-6_1 · Cited by 15
Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering
Bresler, G., & Karzand, M. (2018) · IEEE Transactions on Information Theory · doi:10.1109/ita.2018.8502955 · Cited by 15
Thorn, P. D., & Schurz, G. (2019) · Journal of Mathematical Psychology · doi:10.1016/j.jmp.2018.12.006 · Cited by 12
Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
Kuroki, Y., Xu, L., Miyauchi, A., Honda, J., & Sugiyama, M. (2020) · Neural Computation · doi:10.1162/neco_a_01299 · Cited by 12
SeqScout: Using a Bandit Model to Discover Interesting Subgroups in Labeled Sequences
Mathonat, R., Nurbakova, D., Boulicaut, J., & Kaytoue, M. (2019) · IEEE International Conference on Data Science and Advanced Analytics (DSAA) · doi:10.1109/dsaa.2019.00022 · Cited by 12
Abdelghany, A., Uguen, B., Moy, C., & Lemur, D. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3167016 · Cited by 14
Bayesian Reinforcement Learning With Limited Cognitive Load
Arumugam, D., Ho, M. K., Goodman, N. D., & Roy, B. V. (2024) · Open Mind · doi:10.1162/opmi_a_00132 · Cited by 28
On the efficiency of a randomized mirror descent algorithm in online optimization problems
Gasnikov, A. V., Nesterov, Y. E., & Spokoiny, V. G. (2015) · Computational Mathematics and Mathematical Physics · doi:10.1134/s0965542515040041 · Cited by 16
Randomized allocation with arm elimination in a bandit problem with covariates
Qian, W., & Yang, Y. (2016) · Electronic Journal of Statistics · doi:10.1214/15-ejs1104 · Cited by 13
Learning‐based iterative modular adaptive control for nonlinear systems
Benosman, M., Farahmand, A., & Xia, M. (2018) · International Journal of Adaptive Control and Signal Processing · doi:10.1002/acs.2892 · Cited by 12
Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms
Hendel, G., Miltenberger, M., & Witzig, J. (2019) · Operations research proceedings · doi:10.1007/978-3-030-18500-8_64 · Cited by 12
Intelligent Caching Algorithms in Heterogeneous Wireless Networks with Uncertainty
Hu, B., Chen, Y., Huang, Z., Mehta, N. A., & Pan, J. (2019) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2019.00154 · Cited by 12
Constrained regret minimization for multi-criterion multi-armed bandits
Kagrecha, A., Nair, J., & Jagannathan, K. (2023) · Machine Learning · doi:10.1007/s10994-022-06291-9 · Cited by 12
Meta-Scheduling for the Wireless Downlink Through Learning With Bandit Feedback
Song, J., Veciana, G. A. D., & Shakkottai, S. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3117783 · Cited by 12
Garivier, A., & Kaufmann, E. (2021) · Sequential Analysis · doi:10.1080/07474946.2021.1847965 · Cited by 17
Beam Drift in Millimeter Wave Links: Beamwidth Tradeoffs and Learning Based Optimization
Zhang, J., & Masouros, C. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2021.3088896 · Cited by 14
A Case for Sampling-Based Learning Techniques in Coflow Scheduling
Jajoo, A., Hu, Y., & Lin, X. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3138923 · Cited by 12
Learning for serving deadline-constrained traffic in multi-channel wireless networks
Çaycı, S., & Eryılmaz, A. (2017) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt.2017.7959911 · Cited by 12
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits
Raghavan, M., Slivkins, A., Vaughan, J. W., & Wu, Z. S. (2023) · SIAM Journal on Computing · doi:10.1137/19m1247115 · Cited by 34
Toward Intelligent Reconfigurable Wireless Physical Layer (PHY)
Singh, N., Santosh, S. V. S., & Darak, S. J. (2021) · IEEE Open Journal of Circuits and Systems · doi:10.1109/ojcas.2020.3042463 · Cited by 12
Optimal sequential treatment allocationPreprint
Kock, A., & Thyrsgaard, M. (2017) · RePEc: Research Papers in Economics · doi:10.48550/arxiv.1705.09952 · Cited by 15
Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit FeedbackPreprint
Ba, W., Lin, T., Zhang, J., & Zhou, Z. (2021) · SSRN Electronic Journal · doi:10.2139/ssrn.3978421 · Cited by 22
Data-Driven Online Resource Allocation for User Experience Improvement in Mobile Edge Clouds
Fu, L., Tong, J., Lin, T., & Zhang, J. (2024) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2024.3403996 · Cited by 11
Selective Reviews of Bandit Problems in AI via a Statistical View
Zhou, P., Wei, H., & Zhang, H. (2025) · Mathematics · doi:10.3390/math13040665 · Cited by 14
Cognitive management of self — Organized radio networks based on multi armed bandit
Daher, T., Jemaa, S. B., & Decreusefond, L. (2017) · IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) · doi:10.1109/pimrc.2017.8292257 · Cited by 11
Incentive mechanisms for mobile data offloading through operator-owned WiFi access points
Zhao, Y., Xu, K., Zhong, Y., Li, X., Wang, N., Su, H., Shen, M., & Li, Z. (2020) · Computer Networks · doi:10.1016/j.comnet.2020.107226 · Cited by 11
Meleško, J., & Ramanauskaitė, S. (2021) · Applied Sciences · doi:10.3390/app11136048 · Cited by 13
Emotion and memory model for social robots: a reinforcement learning based behaviour selection
Ahmad, M., Gao, Y., Alnajjar, F., Shahid, S., & Mubin, O. (2021) · Behaviour and Information Technology · doi:10.1080/0144929x.2021.1977389 · Cited by 15
Dynamic Pricing and Placing for Distributed Machine Learning Jobs: An Online Learning Approach
Zhou, R., Zhang, X., Lui, J. C. S., & Li, Z. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3242707 · Cited by 14
A New Framework: Short-Term and Long-Term Returns in Stochastic Multi-Armed Bandit
Sawwan, A., & Wu, J. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228899 · Cited by 11
Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making
Zhou, J., Hao, B., Wen, Z., Zhang, J., & Sun, W. W. (2024) · Journal of the American Statistical Association · doi:10.1080/01621459.2024.2311364 · Cited by 19
Adversarial Bandit for online interactive active learning of zero-shot spoken language understanding
Ferreira, E., Reiffers-Masson, A., Jabaian, B., & Lefèvre, F. (2016) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2016.7472860 · Cited by 11
Aggregation of multi-armed bandits learning algorithms for opportunistic spectrum access
Besson, L., Kaufmann, E., & Moy, C. (2018) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc.2018.8377070 · Cited by 11
Zuo, J., Zhang, X., & Joe‐Wong, C. (2019) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3305218.3305252 · Cited by 11
Bayesian Uncertainty Directed Trial Designs
Ventz, S., Cellamare, M., Bacallado, S., & Trippa, L. (2018) · Journal of the American Statistical Association · doi:10.1080/01621459.2018.1497497 · Cited by 13
Agent-based modelling as a tool for elephant poaching mitigation
Neil, E., Madsen, J. K., Carrella, E., Payette, N., & Bailey, R. M. (2020) · Ecological Modelling · doi:10.1016/j.ecolmodel.2020.109054 · Cited by 14
Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges
Hou, B., Choudhury, S., Lee, G., Mandalika, A., & Srinivasa, S. S. (2020) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra40945.2020.9197014 · Cited by 16
Jacobi-Style Iteration for Distributed Submodular Maximization
Du, B., Qian, K., Claudel, C., & Sun, D. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3180696 · Cited by 21
Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
Chen, Y., Wang, Y., Fang, E. X., Wang, Z., & Li, R. (2022) · Journal of the American Statistical Association · doi:10.1080/01621459.2022.2108816 · Cited by 27
Bandit-based Monte-Carlo structure learning of probabilistic logic programs
Mauro, N. D., Bellodi, E., & Riguzzi, F. (2015) · Machine Learning · doi:10.1007/s10994-015-5510-3 · Cited by 14
On Lower Bounds for Statistical Learning Theory
Loh, P. (2017) · Entropy · doi:10.3390/e19110617 · Cited by 12
A stochastic multi-armed bandit approach to nonparametric H∞-norm estimation
Müller, M. I., Valenzuela, P. E., Proutière, A., & Rojas, C. R. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264343 · Cited by 11
Impact of Detour-Aware Policies on Maximizing Profit in RidesharingPreprint
Biswas, A., Gopalakrishnan, R., Tulabandhula, T., Metrewar, A., Mukherjee, K., & Thangaraj, R. S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.02682 · Cited by 11
VAP: Online Data Valuation and Pricing for Machine Learning Models in Mobile Health
Xu, A., Zheng, Z., Li, Q., Wu, F., & Chen, G. (2023) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2023.3316145 · Cited by 13
Sneh, A., Ram, S. S., Darak, S. J., & Tewari, A. (2024) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2024.3391905 · Cited by 10
Learning to Schedule in Multiclass Many-Server Queues with Abandonment
Zhong, Y., Birge, J. R., & Ward, A. R. (2024) · Operations Research · doi:10.1287/opre.2022.0197 · Cited by 10
Data-Driven Configuration of Interference Coordination Parameters in HetNets
Ayala‐Romero, J. A., Alcaraz, J. J., & Vales‐Alonso, J. (2018) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2018.2825606 · Cited by 10
Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits
Kagrecha, A., Nair, J., & Jagannathan, K. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3163524 · Cited by 10
Althar, R. R., & Samanta, D. (2020) · Studies in big data · doi:10.1007/978-981-15-7965-3_7 · Cited by 10
mmWave Beam Steering with Hierarchical Optimal Sampling for Unimodal Bandits
Blinn, N., Boerger, J., & Bloch, M. R. (2021) · International Conference on Communications · doi:10.1109/icc42927.2021.9500373 · Cited by 10
Optimal Routing to Parallel Servers With Unknown Utilities—Multi-Armed Bandit With Queues
Fu, X., & Modiano, E. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2022.3227136 · Cited by 10
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.