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 501–600 of 1,003
An Efficient Dynamic Sampling Policy for Monte Carlo Tree Search
Zhang, G., Peng, Y., & Xu, Y. (2022) · Winter Simulation Conference · doi:10.1109/wsc57314.2022.10015374 · Cited by 12
Convergence rate analysis for optimal computing budget allocation algorithms
Li, Y., & Gao, S. (2023) · Automatica · doi:10.1016/j.automatica.2023.111042 · Cited by 10
Learning Algorithms for Scheduling in Wireless Networks with Unknown Channel Statistics
Stahlbuhk, T., Shrader, B., & Modiano, E. (2018) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/3209582.3209586 · Cited by 10
Adaptive policies for perimeter surveillance problems
Grant, J. A., Leslie, D. S., Glazebrook, K. D., Szechtman, R., & Letchford, A. N. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2019.11.004 · Cited by 10
Universal Best Arm Identification
Shen, C. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2929936 · Cited by 10
Wang, Y., Roohi, N., West, M., Viswanathan, M., & Dullerud, G. E. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303982 · Cited by 10
Non-Stationary Representation Learning in Sequential Linear Bandits
Qin, Y., Menara, T., Oymak, S., Ching, S., & Pasqualetti, F. (2022) · IEEE Open Journal of Control Systems · doi:10.1109/ojcsys.2022.3178540 · Cited by 10
Bayandina, A., Gasnikov, A. V., & Lagunovskaya, A. (2018) · Automation and Remote Control · doi:10.1134/s0005117918080039 · Cited by 10
Multi-Armed Bandit for Species Discovery: A Bayesian Nonparametric Approach
Battiston, M., Favaro, S., & Teh, Y. W. (2016) · Journal of the American Statistical Association · doi:10.1080/01621459.2016.1261711 · Cited by 10
Bio-inspired decision-making and control: From honeybees and neurons to network design
Srivastava, V., & Leonard, N. E. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7963250 · Cited by 13
A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
Moulos, V. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9173931 · Cited by 10
Dynamic Spectrum Access Using Stochastic Multi-User Bandits
Bande, M., Magesh, A., & Veeravalli, V. V. (2021) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2021.3051328 · Cited by 10
Improving demand‐response scheme in smart grids using reinforcement learning
Bagherpour, R., Mozayani, N., & Badnava, B. (2021) · International Journal of Energy Research · doi:10.1002/er.7165 · Cited by 10
Learning Variable Ordering Heuristics with Multi-Armed Bandits and Restarts
Wattez, H., Koriche, F., Lecoutre, C., Paparrizou, A., & Tabary, S. (2020) · Frontiers in artificial intelligence and applications · doi:10.3233/faia200115 · Cited by 10
Cowan, W., & Katehakis, M. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.02865 · Cited by 10
Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance ReductionPreprint
Gu, B., Huo, Z., & Huang, H. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1612.01425 · Cited by 10
Toward an Ethical ExperimentPreprint
Narita, Y. (2018) · SSRN Electronic Journal · doi:10.2139/ssrn.3094905 · Cited by 10
Sequential resources allocation in linear stochastic bandits
Soare, M. (2015) · theses.fr (ABES) · doi:10.70675/4331b6a6z1054z4f1azb0adz6fdb0811629a · Cited by 10
Waypoint-Based Reinforcement Learning for Robot Manipulation Tasks
Mehta, S. A., Habibian, S., & Losey, D. P. (2024) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros58592.2024.10802681 · Cited by 20
Self-accelerated Thompson sampling with near-optimal regret upper bound
Zhu, Z., Huang, L., & Xu, H. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.01.086 · Cited by 9
Tan, C., Yang, L. F., & Wong, W. S. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3049357 · Cited by 9
Hosoda, J., Maher, S. J., Shinano, Y., & Villumsen, J. C. (2022) · EURO Journal on Transportation and Logistics · doi:10.1016/j.ejtl.2022.100091 · Cited by 9
Learning Proportionally Fair Allocations with Low Regret
Talebi, M. S., & Proutière, A. (2018) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3224431 · Cited by 9
Massive multi-player multi-armed bandits for IoT networks: An application on LoRa networks
Dakdouk, H., Féraud, R., Varsier, N., Maillé, P., & Laroche, R. (2023) · Ad Hoc Networks · doi:10.1016/j.adhoc.2023.103283 · Cited by 9
Radar Enhanced Multi-Armed Bandit for Rapid Beam Selection in Millimeter Wave Communications
Sneh, A., Darak, S. J., Ram, S. S., & Hanawal, M. K. (2023) · IEEE Communications Letters · doi:10.1109/lcomm.2023.3291389 · Cited by 9
Playing With a Multi Armed Bandit to Optimize Resource Allocation in Satellite-Enabled 5G Networks
Galli, A., Moscato, V., Romano, S. P., & Sperlí, G. (2023) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2023.3302064 · Cited by 13
Clinical online recommendation with subgroup rank feedback
Sui, Y., & Burdick, J. W. (2014) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/2645710.2645773 · Cited by 15
An Analysis of the Value of Information When Exploring Stochastic, Discrete Multi-Armed Bandits
Sledge, I. J., & Príncipe, J. C. (2018) · Entropy · doi:10.3390/e20030155 · Cited by 10
GNU Radio Implementation of MALIN: “Multi-Armed bandits Learning for Internet-of-things Networks”
Besson, L., Bonnefoi, R., & Moy, C. (2019) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc.2019.8885841 · Cited by 10
Adversarial Multi-user Bandits for Uncoordinated Spectrum Access
Bande, M., & Veeravalli, V. V. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682263 · Cited by 9
An online algorithm for the risk-aware restless bandit
Xu, J., Chen, L., & Tang, O. (2020) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.08.028 · Cited by 9
Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme
Nikolakakis, K. E., Kalogerias, D. S., Sheffet, O., & Sarwate, A. D. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3081525 · Cited by 11
Gao, X., Huang, X., Shao, Z., & Yang, Y. (2021) · IEEE Transactions on Green Communications and Networking · doi:10.1109/tgcn.2021.3083426 · Cited by 10
Proactive Edge Caching in Vehicular Networks: An Online Bandit Learning Approach
Wang, Q., & Grace, D. (2022) · IEEE Access · doi:10.1109/access.2022.3229645 · Cited by 10
Wang, K., Verma, S., Mate, A., Shah, S. S., Taneja, A., Madhiwalla, N., Hegde, A., & Tambe, M. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i10.26431 · Cited by 33
Calibrating Sales Forecast in a Pandemic: Random-Design Online Isotonic Regression
Simchi‐Levi, D., Sun, R., Wu, M. X., & Zhu, R. (2020) · Management Science · doi:10.1287/mnsc.2023.4969 · Cited by 10
Dai, X., Liu, X., Zuo, J., Chen, X., Chen, W., & Lui, J. C. S. (2026) · Artificial Intelligence · doi:10.1016/j.artint.2026.104500 · Cited by 9
Hedging Under Uncertainty: Regret Minimization Meets Exponentially Fast Convergence
Cohen, J., Héliou, A., & Mertikopoulos, P. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66700-3_20 · Cited by 9
Upper-Confidence Bound for Channel Selection in LPWA Networks with Retransmissions
Bonnefoi, R., Besson, L., Manco-Vasquez, J. C., & Moy, C. (2019) · IEEE Wireless Communications and Networking Conference Workshops (WCNCW) · doi:10.1109/wcncw.2019.8902891 · Cited by 9
Optimistic Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds
Jiang, D., Al‐Kanj, L., & Powell, W. B. (2020) · Operations Research · doi:10.1287/opre.2019.1939 · Cited by 12
Gu, Q., Karbasi, A., Khosravi, K., Mirrokni, V., & Zhou, D. (2024) · ACM / IMS Journal of Data Science · doi:10.1145/3592474 · Cited by 31
A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
Çaycı, S., Zheng, Y., & Eryılmaz, A. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i4.20285 · Cited by 10
Aging Wireless Bandits: Regret Analysis and Order-Optimal Learning Algorithm
Atay, E. U., Kadota, I., & Modiano, E. (2021) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt52861.2021.9589673 · Cited by 9
Learning an Adversary’s Actions for Secret Communication
Tahmasbi, M., Bloch, M. R., & Yener, A. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2940960 · Cited by 9
Managing Overstaying Electric Vehicles in Park-and-Charge FacilitiesPreprint
Biswas, A., Gopalakrishnan, R., & Dutta, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.05471 · Cited by 9
A survey on multi-player banditsPreprint
Boursier, É., & Perchet, V. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.16275 · Cited by 15
Crowdsensing Data Trading for Unknown Market: Privacy, Stability, and Conflicts
He, S., Xiao, M., Xu, Y., Gao, G., & Zhang, S. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3399816 · Cited by 8
Nonparametric multi-product dynamic pricing with demand learning via simultaneous price perturbation
Yang, X., Zhang, J., Hu, J.-Q., & Hu, J.-Q. (2024) · European Journal of Operational Research · doi:10.1016/j.ejor.2024.06.017 · Cited by 9
Quantum Entanglement Path Selection and Qubit Allocation via Adversarial Group Neural Bandits
Huang, Y., Wang, L., & Xu, J. (2024) · IEEE Transactions on Networking · doi:10.1109/tnet.2024.3510550 · Cited by 12
Greedy-Bayes for Targeted News Dissemination
Massoulié, L., Ohannessian, M. I., & Proutière, A. (2015) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2745844.2745868 · Cited by 8
Bayesian Optimization-based Modular Indirect Adaptive Control for a Class of Nonlinear Systems
Benosman, M., & Farahmand, A. (2016) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2016.07.960 · Cited by 8
Multi-armed bandit problem with online clustering as side information
Dzhoha, A., & Rozora, I. V. (2023) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2023.115132 · Cited by 9
Online-Learning-Based Multi-RIS-Aided Wireless Systems
Sharma, I., Kumar, R., & Darak, S. J. (2024) · IEEE Systems Journal · doi:10.1109/jsyst.2024.3391856 · Cited by 8
A sequential transit network design algorithm with optimal learning under correlated beliefs
Yoon, G., & Chow, J. Y. J. (2024) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2024.103707 · Cited by 8
Linear Bayes policy for learning in contextual-bandits
José Antonio Martín, H., & Pérez, A. M. V. (2013) · Expert Systems with Applications · doi:10.1016/j.eswa.2013.07.041 · Cited by 8
Infinitely Many-Armed Bandits with Budget Constraints
Li, H., & Xia, Y. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10881 · Cited by 8
Boundary Crossing Probabilities for General Exponential Families
Maillard, O.-A. (2018) · Mathematical Methods of Statistics · doi:10.3103/s1066530718010015 · Cited by 12
A Non-Stationary Online Learning Approach to Mobility Management
Zhou, Y., Shen, C., Luo, X., & van der Schaar, M. (2018) · International Conference on Communications · doi:10.1109/icc.2018.8422163 · Cited by 8
SpecWatch: A framework for adversarial spectrum monitoring with unknown statistics
Li, M., Yang, D., Lin, J. D., Li, M., & Tang, J. (2018) · Computer Networks · doi:10.1016/j.comnet.2018.07.018 · Cited by 8
Anytime mining of sequential discriminative patterns in labeled sequences
Mathonat, R., Nurbakova, D., Boulicaut, J., & Kaytoue, M. (2020) · Knowledge and Information Systems · doi:10.1007/s10115-020-01523-7 · Cited by 8
Response‐adaptive trial designs with accelerated Thompson sampling
Wang, J. (2021) · Pharmaceutical Statistics · doi:10.1002/pst.2098 · Cited by 8
Generalized Contextual Bandits With Latent Features: Algorithms and Applications
Xu, X., Xie, H., & Lui, J. C. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3124603 · Cited by 8
Improving QoE of Deep Neural Network Inference on Edge Devices: A Bandit Approach
Lu, B., Yang, J., Xu, J., & Ren, S. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3182728 · Cited by 10
Aziz, M., Anderton, J., Jamieson, K., Wang, A., Bouchard, H., & Aslam, J. A. (2022) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3523227.3546766 · Cited by 8
Bandit Learning in Many-to-One Matching Markets
Wang, Z., Guo, L., Yin, J., & Li, S. (2022) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3511808.3557248 · Cited by 8
Variance-Adaptive Algorithm for Probabilistic Maximum Coverage Bandits with General Feedback
Liu, X., Zuo, J., Xie, H. L., Joe‐Wong, C., & Lui, J. C. S. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228940 · Cited by 8
Learning With Side Information: Elastic Multi-Resource Control for the Open RAN
Zhang, X., Zuo, J., Huang, Z., Zhou, Z., Chen, X., & Joe‐Wong, C. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3339174 · Cited by 10
Uragami, D., Takahashi, T., & Matsuo, Y. (2013) · Biosystems · doi:10.1016/j.biosystems.2013.11.002 · Cited by 8
Mechanisms with learning for stochastic multi-armed bandit problems
Jain, S., Bhat, S., Ghalme, G. S., Padmanabhan, D., & Narahari, Y. (2016) · Indian Journal of Pure and Applied Mathematics · doi:10.1007/s13226-016-0186-3 · Cited by 8
LinUCB applied to Monte Carlo tree search
Mandai, Y., & Kaneko, T. (2016) · Theoretical Computer Science · doi:10.1016/j.tcs.2016.06.035 · Cited by 8
Work Capacity of Regulated Freelance Platforms: Fundamental Limits and Decentralized Schemes
Chatterjee, A., Varshney, L. R., & Vishwanath, S. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2766280 · Cited by 8
Interactions Between Learning and Broadcasting in Wireless Recommendation Systems
Song, L., Fragouli, C., & Devavrat Shah, B. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849556 · Cited by 8
Bandit-Based Relay Selection in Cooperative Networks Over Unknown Stationary Channels
Νομικός, Ν., Talebi, M. S., Wichman, R., & Charalambous, T. (2020) · Machine learning for signal processing ... · doi:10.1109/mlsp49062.2020.9231604 · Cited by 8
Efficient and Flexible Crowdsourcing of Specialized Tasks With Precedence Constraints
Chatterjee, A., Borokhovich, M., Varshney, L. R., & Vishwanath, S. (2018) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2018.2811736 · Cited by 8
Guaranteed satisficing and finite regret: Analysis of a cognitive satisficing value function
Tamatsukuri, A., & Takahashi, T. (2019) · Biosystems · doi:10.1016/j.biosystems.2019.02.009 · Cited by 9
Efficient subspace search in data streams
Fouché, E., Kalinke, F., & Böhm, K. (2020) · Information Systems · doi:10.1016/j.is.2020.101705 · Cited by 10
Optimal Learning for Structured BanditsPreprint
Parys, B. P. G. V., & Golrezaei, N. (2020) · SSRN Electronic Journal · doi:10.2139/ssrn.3651397 · Cited by 8
Resource Allocation for Statistical Estimation
Berthet, Q., & Chandrasekaran, V. (2015) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2494098 · Cited by 11
Sangare, F., & Han, Z. (2017) · IEEE International Conference on Communications workshops · doi:10.1109/iccw.2017.7962705 · Cited by 7
Multi-armed Bandit with Sub-exponential Rewards
Jia, H., Shi, C., & Shen, S. (2021) · Operations Research Letters · doi:10.1016/j.orl.2021.08.004 · Cited by 10
Dynamic Data Transaction in Crowdsensing Based on Multi-Armed Bandits and Shapley Value
Xu, C. L., Si, Y., Zhu, L., Zhang, C., Sharif, K., & Wu, H. (2021) · IEEE Transactions on Sustainable Computing · doi:10.1109/tsusc.2021.3128388 · Cited by 7
Castiglioni, M., Celli, A., Marchesi, A., & Gatti, N. (2022) · Artificial Intelligence · doi:10.1016/j.artint.2022.103821 · Cited by 7
Top-k Discovery Under Local Differential Privacy: An Adaptive Sampling Approach
Du, R., Ye, Q., Fu, Y., Hu, H., & Huang, K. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3471923 · Cited by 9
Oyo, K., Ichino, M., & Takahashi, T. (2015) · Transactions of the Japanese Society for Artificial Intelligence · doi:10.1527/tjsai.30.403 · Cited by 10
A Superprocess with Upper Confidence Bounds for Cooperative Spectrum Sharing
López-Martínez, M., Alcaraz, J. J., Badia, L., & Zorzi, M. (2016) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2016.2516991 · Cited by 8
Online Learning over a Finite Action Set with Limited Switching
Altschuler, J. M., & Talwar, K. (2020) · Mathematics of Operations Research · doi:10.1287/moor.2020.1052 · Cited by 7
ONLINE OPTIMAL TASK OFFLOADING WITH ONE-BIT FEEDBACK
Zhao, S., Zhu, Z., Yang, F., & Luo, X. (2018) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2018.8646619 · Cited by 7
Emotion and Memory Model to Promote Mathematics Learning - An Exploratory Long-term Study
Ahmad, M., & Mubin, O. (2018) · International Conference on Human-Agent Interaction (HAI) · doi:10.1145/3284432.3284451 · Cited by 9
Online Channel-state Clustering And Multiuser Capacity Learning For Wireless Scheduling
Tariq, I., Sen, R., Veciana, G. A. D., & Shakkottai, S. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737425 · Cited by 7
Low-Complexity Methods for Estimation After Parameter Selection
Harel, N., & Routtenberg, T. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2970311 · Cited by 7
Dynamic allocation optimization in A/B tests using classification-based preprocessing
Claeys, E., Gançarski, P., Maumy‐Bertrand, M., & Wassner, H. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3076025 · Cited by 15
A TDRL Model for the Emotion of Regret
Broekens, J., & Dai, L. (2019) · International Conference on Affective Computing and Intelligent Interaction and workshops · doi:10.1109/acii.2019.8925441 · Cited by 12
Jin, R., Simchi‐Levi, D., Wang, L., Wang, X., & Yang, S. (2019) · Management Science · doi:10.1287/mnsc.2020.3773 · Cited by 7
A Bandit-Learning Approach to Multifidelity Approximation
Xu, Y., Keshavarzzadeh, V., Kirby, R. M., & Narayan, A. (2022) · SIAM Journal on Scientific Computing · doi:10.1137/21m1408312 · Cited by 14
Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach
Iacob, A., Cautis, B., & Maniu, S. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977172.58 · Cited by 7
Using sentiment analysis to reinforce learning: The case of airport community engagement
Diana, T. (2022) · Journal of Air Transport Management · doi:10.1016/j.jairtraman.2022.102228 · Cited by 7
Zou, M., Chen, J., Luo, J., Hu, Z., & Chen, S. (2022) · Electronics · doi:10.3390/electronics11213526 · Cited by 7
Bridging Adversarial and Nonstationary Multi-Armed Bandit
Chen, N., Yang, S., & Zhang, H. (2025) · Production and Operations Management · doi:10.1177/10591478251313780 · Cited by 7
Pareto Upper Confidence Bounds algorithms: An empirical study
Drugan, M. M., Nowé, A., & Manderick, B. (2014) · IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning · doi:10.1109/adprl.2014.7010620 · Cited by 12
Bandit User Selection Algorithm for Budgeted and Time-Limited Mobile Crowdsensing
Yang, S., Qi, X., Wu, F., Gao, X., & Chen, G. (2017) · Globecom · doi:10.1109/glocom.2017.8254592 · 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.