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 901–1,000 of 1,003
The Upper Confidence Bound Algorithm
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.010 · Cited by 2
Palette: Towards Multi-source Model Selection and Ensemble for Reuse
Li, Y., Shen, Y., & Chen, L. (2021) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde51399.2021.00215 · Cited by 4
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.024 · Cited by 3
Avin, C., van Duijn, I., Pacut, M., & Schmid, S. (2023) · Information and Computation · doi:10.1016/j.ic.2023.105038 · Cited by 2
Sequential Monte Carlo bandits
Urteaga, I., & Wiggins, C. H. (2024) · Foundations of Data Science · doi:10.3934/fods.2024005 · Cited by 3
Bandit Label Inference for Weakly Supervised LearningPreprint
Li, K., & Malik, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.06807 · Cited by 2
Towards a unifying theory of generalizationPreprint
Schulz, E. (2017) · PsyArXiv (OSF Preprints) · doi:10.31234/osf.io/rzj2m · Cited by 2
Understanding Doctor Decision Making: The Case of Depression
Currie, J. L., & MacLeod, W. B. (2018) · National Bureau of Economic Research · doi:10.3386/w24955 · Cited by 2
The Survival Bandit ProblemPreprint
Riou, C., Honda, J., & Sugiyama, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03019 · Cited by 2
Marty, F. M., & Warin, T. (2023) · Journal of Economy and Technology · doi:10.54932/iwpg7510 · Cited by 6
Technical Note—Online Matching with Bayesian Rewards
Simchi‐Levi, D., Sun, R., & Wang, X. (2023) · Operations Research · doi:10.1287/opre.2021.0499 · Cited by 1
Fair Incentive Mechanism for Mobile Crowdsensing
Li, Y., Li, F., Yang, S., & Zhang, C. (2024) · SpringerBriefs in computer science · doi:10.1007/978-981-99-6921-0_3 · Cited by 1
Thanh, L. T., Ji, Y., & Lui, J. C. S. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3399876 · Cited by 1
EWS: Towards Cost-Effective Job Scheduling via Combinatorial Multi-Armed Bandit Learning
Xiao, L., Xiao, Z., Wu, D., & Hu, M. (2024) · IEEE International Conference on Networking, Architecture and Storage (NAS) · doi:10.1109/nas63802.2024.10781367 · Cited by 1
MTRP: A High-Performance Cost-Efficient Buffering Scheme for Multi-Tenant Cloud Services
Zhu, Z., Jin, P., Huang, G., Wang, X., & Yuan, Y. (2024) · IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA) · doi:10.1109/ispa63168.2024.00228 · Cited by 1
Strategic Interplay: Game-Theoretic Frameworks for Topological Robustness Against Data Poisoning
Феррара, М. (2025) · WSEAS Transactions on Information Science and Applications archive · doi:10.37394/23209.2025.22.44 · Cited by 1
Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization
Mu, H., Tang, Y., & Li, Z. (2025) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc63710.2025.11107900 · Cited by 1
AIPO: Automatic Instruction Prompt Optimization by model itself with “Gradient Ascent”
Park, K., & Kim, D. (2025) · Computer Speech & Language · doi:10.1016/j.csl.2025.101889 · Cited by 1
GLMFuzz: Vulnerability Knowledge Guided Prompting for Efficient Network Protocol Fuzzing
Zhu, S., Gan, S., Wang, X., & Nan, Y. (2025) · IEEE International Conference on Software Quality, Reliability and Security (QRS) · doi:10.1109/qrs65678.2025.00062 · Cited by 2
Multipath Inter-Domain Routing Protocols for Quantum Networks With Online Path Selection
Li, Z., Liu, M., Cai, K., Allcock, J., Zhang, S., & Lui, J. C. S. (2025) · IEEE Transactions on Networking · doi:10.1109/ton.2025.3615081 · Cited by 1
Liu, Y., Wang, J., Qi, Q., Chen, D. Y., Zhuang, Z., Liao, J., & Han, Z. (2026) · IEEE Transactions on Networking · doi:10.1109/ton.2026.3664933 · Cited by 1
A natural adaptive process for collective decision‐making
Brandl, F., & Brandt, F. (2024) · Theoretical Economics · doi:10.3982/te5380 · Cited by 2
Introduction to Applied Affective Computing
Tian, L., Oviatt, S. L., Muszyński, M., Chamberlain, B. C., Healey, J., & Sano, A. (2022) · ACM eBooks · doi:10.1145/3502398.3502400 · Cited by 1
Online Joint Assortment-Inventory Optimization Under MNL Choices
Liang, Y., Mao, X., & Wang, S. (2026) · Operations Research · doi:10.1287/opre.2023.0167 · Cited by 1
Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variables
Barreto, M., Marchal, O., & Arbel, J. (2025) · Statistics & Probability Letters · doi:10.1016/j.spl.2025.110555 · Cited by 6
Linear Bandits With Side Observations on Networks
Kar, A., Singh, R., Liu, F., Liu, X., & Shroff, N. (2024) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2024.3422323 · Cited by 1
Bandits with Concave Aggregated Reward
Yu, Y., Zhang, S.-J., Li, S.-A., Zhang, L., Xie, W., & Li, X.-Y. (2024) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2024/597 · Cited by 1
Socially Optimal Mechanism Design for Relay-Assisted Asynchronous Federated Learning
Sun, P., Liao, G., Huang, J., Li, X., Wang, Y., & Chen, X. (2025) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2025.3574619 · Cited by 3
Deep Sigma Point Processes for RCS Modeling in Spaceborne SAR Imagery
El-Darymli, K., Gierull, C. H., Biron, K., & Huang, W. (2025) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2025.3581154 · Cited by 1
DPShaping: Balancing Privacy Guarantee and Communication Cost in IoT Traffic Shaping
Zhang, S., Cui, X., Du, H., Li, S., Yu, Y., Hou, J., & Li, X. (2025) · ACM Transactions on Sensor Networks · doi:10.1145/3745783 · Cited by 1
Online Pricing for Balancing Parking Demand and Supply in a Shared Parking Case
Zhou, X., Jiang, H., Bai, M., & Chen, R. (2025) · International Conference on Data-driven Optimization of Complex Systems (DOCS) · doi:10.1109/docs67533.2025.11200568 · Cited by 1
Chatterjee, D., & Maiti, S. (2026) · International Journal of Data Science and Analysis · doi:10.1007/s41060-026-01333-0
Optimization via the strategic law of large numbers
Chen, X., Chen, Z., Gao, W. Y., Yan, X., & Zhang, G. (2026) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2519845123 · Cited by 8
Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendations
Shen, C., Zhan, Y., Yu, W., Zhang, X., & Xu, J. (2026) · ACM Transactions on Information Systems · doi:10.1145/3793543 · Cited by 1
Zhang, W., Hudson, A., Petersen, M., & van der Laan, M. J. (2026) · Journal of the American Statistical Association · doi:10.1080/01621459.2026.2657052 · Cited by 5
Run-length certificates in quantum learning: Sample complexity and noise thresholds
Bang, J. (2026) · Physical Review A · doi:10.1103/cn9t-dynd · Cited by 3
Lodh, E., Majumder, S., Chowdhury, T., & De, M. (2026) · Journal of Computer-Aided Molecular Design · doi:10.1007/s10822-026-00823-4 · Cited by 3
Taricco, G. (2026) · Entropy · doi:10.3390/e28070811 · Cited by 1
LinUCB Applied to Monte-Carlo Tree Search
Mandai, Y., & Kaneko, T. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-27992-3_5 · Cited by 1
Meta-algorithm to Choose a Good On-Line Prediction (Short Paper)
Dambreville, A., Tomasik, J., & Cohen, J. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-49259-9_10 · Cited by 1
Fast Iterative model for Sequential-Selection-Based Applications
Amirizadeh, K., & Mandava, R. (2014) · INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY · doi:10.24297/ijct.v12i7.3092 · Cited by 1
LIMSI Submission for WMT'17 Shared Task on Bandit Learning
Wisniewski, G. (2017) · Conference on Machine Translation (WMT) · doi:10.18653/v1/w17-4779 · Cited by 1
Patish, U., & Ullman, S. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i03.5620 · Cited by 1
Multi-Armed Bandits for Human-Machine Decision Making
Reverdy, P. B., & Srivastava, V. (2018) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2018.8461843 · Cited by 1
Silva, R. C., Direne, A. I., Marczal, D., Borille, A. C., Guimarães, P. R. B., Cabral, A. D. S., & Camargo, B. F. (2018) · Revista Brasileira de Informática na Educação · doi:10.5753/rbie.2018.26.01.70 · Cited by 2
Can Machine Learning Techniques Provide Better Learning Support for Elderly People?
Hatano, K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-91131-1_14 · Cited by 1
An Approximate Dynamic Programming Approach to Repeated Games with Vector Losses
Kamble, V., Loiseau, P., & Walrand, J. C. (2022) · Operations Research · doi:10.1287/opre.2022.2334 · Cited by 1
Three asymptotic regimes for ranking and selection with general sample distributions
Dong, J., & Zhu, Y. (2016) · Winter Simulation Conference · doi:10.1109/wsc.2016.7822096 · Cited by 1
Mistake bounds on the noise-free multi-armed bandit game
Nakamura, A., Helmbold, D. P., & Warmuth, M. K. (2019) · Information and Computation · doi:10.1016/j.ic.2019.104453 · Cited by 1
Social Bandit Learning: Strangers Can Help
Zong, J., Liu, T., Zhu, Z., Luo, X., & Qian, H. L. (2020) · International Conference on Wireless Communications and Signal Processing (WCSP) · doi:10.1109/wcsp49889.2020.9299725 · Cited by 1
The Explore-Then-Commit Algorithm
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.009 · Cited by 1
On testing transitivity in online preference learning
Haddenhorst, B., Bengs, V., & Hüllermeier, E. (2021) · Machine Learning · doi:10.1007/s10994-021-06026-2 · Cited by 1
Future of Affective Computing and Applied Affective Computing
Tian, L., Oviatt, S. L., Muszyński, M., Chamberlain, B. C., Healey, J., & Sano, A. (2022) · ACM eBooks · doi:10.1145/3502398.3502411 · Cited by 1
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.003 · Cited by 1
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.016 · Cited by 1
Minimax Optimal Bandits for Heavy Tail Rewards
Lee, K., & Lim, S. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3203035 · Cited by 1
Learning and Pricing with Inventory Constraints
Chen, Q., Wang, H., & Wang, Z. (2022) · Springer series in supply chain management · doi:10.1007/978-3-031-01926-5_5 · Cited by 1
Mode Selection of Content Delivery at Edge Nodes Based on Learning
Xu, Y., & Tang, H. (2022) · Wireless Personal Communications · doi:10.1007/s11277-022-10104-6 · Cited by 1
Bellodi, E. (2023) · Intelligenza Artificiale · doi:10.3233/ia-221072 · Cited by 7
Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits
Xiong, G., & Li, J. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i9.26251 · Cited by 1
Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice
Eldowa, K., Cesa‐Bianchi, N., Metelli, A. M., & Restelli, M. (2023) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw55543.2023.10161661 · Cited by 1
Self-citationUnknown Worker Recruitment in Mobile Crowdsourcing
Xiao, M., Xu, Y., & Sun, H. (2023) · Wireless networks · doi:10.1007/978-3-031-32397-3_3 · Cited by 1
Beta Upper Confidence Bound Policy for the Design of Clinical Trials
Dzhoha, A., & Rozora, I. V. (2023) · Austrian Journal of Statistics · doi:10.17713/ajs.v52isi.1751 · Cited by 1
Mitigating Bias in Algorithmic Decision-making: Evaluating Claims and Practices
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603212 · Cited by 1
Extremum information transfer over networks for remote estimation and distributed learning
Vasconcelos, M. M., & Mitra, U. (2024) · Frontiers in Complex Systems · doi:10.3389/fcpxs.2024.1322785 · Cited by 1
Consensus-Based Thompson Sampling for Stochastic Multiarmed Bandits
Hayashi, N. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3426379 · Cited by 1
Transfer in Sequential Multi-Armed Bandits via Reward Samples
Rahul, N., & Katewa, V. (2024) · European Control Conference (ECC) · doi:10.23919/ecc64448.2024.10590903 · Cited by 1
Toward Order Optimal Channel Access in Unknown Environments: An Online Learning Method
Ye, S., & Wang, S. (2024) · IEEE Transactions on Communications · doi:10.1109/tcomm.2024.3434960 · Cited by 1
RumFuzz: Coverage-guided Greybox Fuzzing with Reasonable Use of Memory
Xu, J., Wang, J., Ma, Y., Li, L., & Jia, C. (2024) · IEEE International Conference on Software Quality, Reliability and Security (QRS) · doi:10.1109/qrs62785.2024.00059 · Cited by 1
Effective Generalized Low-Rank Tensor Contextual Bandits
Yi, Q., Yang, Y., Tang, S., Liu, J., & Wang, Y. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3469782 · Cited by 1
Learning to detect via multi-armed bandit
Zhou, Y., Zou, Y., Wu, Y., Shi, Y., & Zhang, J. (2025) · Elsevier eBooks · doi:10.1016/b978-0-44-322073-9.00014-6 · Cited by 1
Adaptive Address Family Selection for Latency-Sensitive Applications on Dual-Stack Hosts
Piraux, M., & Bonaventure, O. (2024) · ACM SIGCOMM Computer Communication Review · doi:10.1145/3717512.3717514 · Cited by 1
CVaR-based Thompson Sampling for Factored Multi-agent Multi-Armed Risk-aware Bandit
Li, J., & Tian, H. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10864902 · Cited by 1
Representative Arm Identification: A fixed confidence approach to identify cluster representatives
Gharat, S., Yadav, A., Karamchandani, N., & Nair, J. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10890622 · Cited by 2
Multi-Armed Bandits and Quantum Channel Oracles
Buchholz, S., Kübler, J. M., & Schölkopf, B. (2025) · Quantum · doi:10.22331/q-2025-03-25-1672 · Cited by 9
Stepwise Optimization: Cascaded Algorithm Selection
Yang, Y., Qian, H., & Hu, Y.-Q. (2025) · Machine learning · doi:10.1007/978-981-96-5929-6_13 · Cited by 1
A greedy and optimistic clustering for leveraging individual covariate uncertainty
Okuno, A., & Hattori, K. (2025) · Annals of the Institute of Statistical Mathematics · doi:10.1007/s10463-025-00947-8 · Cited by 5
On Human Decision-Making Heuristics and Algorithm Design in Engineering [Further Thoughts]
Leonard, N. E. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2308607 · Cited by 1
Online Experimentation for Information Retrieval
Hofmann, K. (2015) · Communications in computer and information science · doi:10.1007/978-3-319-25485-2_2 · Cited by 1
On Monte-Carlo tree search for deterministic games with alternate moves and complete information
Delattre, S., & Fournier, N. (2018) · ESAIM Probability and Statistics · doi:10.1051/ps/2018006 · Cited by 1
Multi-model optimization with discounted reward and budget constraint
Shi, J., & Chen, M. (2018) · doi:10.1145/3208788.3208796 · Cited by 1
Small Cell Power Assignment with Unimodal Continuum-Armed Bandit Learning
Wang, Z., & Shen, C. (2018) · IEEE International Conference on Communications workshops · doi:10.1109/iccw.2018.8403499 · Cited by 1
Active Distribution Learning from Indirect Samples
Gupta, S., Joshi, G., & Yağan, O. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8635924 · Cited by 1
Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory
Su, L., Zubeldía, M., & Lynch, N. A. (2019) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3376930.3376932 · Cited by 1
Glimsdal, S., & Granmo, O. (2018) · Applied Intelligence · doi:10.1007/s10489-018-1172-8 · Cited by 1
Gradient-free Online Resource Allocation Algorithms for Dynamic Wireless Networks
Marcastel, A., Belmega, E. V., Mertikopoulo, P., & Fijalkow, I. (2019) · IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) · doi:10.1109/spawc.2019.8815409 · Cited by 2
NARPCA: Neural Accumulate-Retract PCA for Low-Latency High-Throughput Processing on Datastreams
Axenie, C., Tudoran, R., Bortoli, S., Hassan, M. A. H., & Brasche, G. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30487-4_20 · Cited by 1
Online Learning with Diverse User Preferences
Gan, C., Yang, J., Zhou, R., & Shen, C. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849646 · Cited by 1
Modeling and optimization of Human-Machine Interaction Processes via the Maximum Entropy Principle
Zheng, J., & Veciana, G. A. D. (2019) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2019.8919959 · Cited by 1
OPQR: Online Pricing and Quality Requesting for Mobile Crowd Sensing
Liang, J., Li, L., Li, Q., & Jiang, Y. (2019) · IEEE Symposium on Computers and Communications (ISCC) · doi:10.1109/iscc47284.2019.8969776 · Cited by 1
Robust Dynamic Spectrum Access in Adversarial Environments
Guan, Z., Hu, T. Y., Palombo, J., Liston, M. J., Bucci, D. J., & Liang, Y. (2020) · International Conference on Communications · doi:10.1109/icc40277.2020.9148923 · Cited by 1
Stochastic Bandits with Finitely Many Arms
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.008 · Cited by 4
Efficient Algorithm for Multi-Constrained Opportunistic Wireless Scheduling
Xu, X., & Wang, L. (2020) · International Conference on Mobility, Sensing and Networking (MSN) · doi:10.1109/msn50589.2020.00040 · Cited by 1
No-Regret Learning for Coalitional Model Predictive Control
Chanfreut, P., Maestre, J. M., Zhu, Q., & Camacho, E. F. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.1674 · Cited by 1
Cascading Bandit Under Differential Privacy
Wang, K., Dong, J., Wang, B., & Li, S. (2022) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp43922.2022.9746966 · Cited by 1
Bernoulli multi-armed bandit problem under delayed feedback
Dzhoha, A. (2021) · Bulletin of Taras Shevchenko National University of Kyiv Series Physics and Mathematics · doi:10.17721/1812-5409.2021/1.2 · Cited by 1
Kaptein, M. C. (2021) · Human-computer interaction series · doi:10.1007/978-3-030-67322-2_7 · Cited by 1
Multi-armed bandits for bid shading in first-price real-time bidding auctions
Tilli, T., & Espinosa-Leal, L. (2021) · Journal of Intelligent & Fuzzy Systems · doi:10.3233/jifs-202665 · Cited by 1
The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603204 · Cited by 1
A Differentially Private Context-Aware Edge-Cloud-Enabled Nursing System in Smart Home
Liu, G., Li, Q., Wang, D.-H., Ren, R.-B., Chou, H.-T., & Zhou, P. (2021) · International Conference on Computer Communication and Network Security (CCNS) · doi:10.1109/ccns53852.2021.00019 · Cited by 1
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.