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 801–900 of 1,003
Padmanabhan, D., Bhat, S., Prabuchandran, K. J., Shevade, S., & Narahari, Y. (2021) · Applied Intelligence · doi:10.1007/s10489-021-02387-2 · Cited by 3
Batched Learning in Generalized Linear Contextual Bandits with General Decision Sets
Ren, Z., Zhou, Z., & Kalagnanam, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483345 · Cited by 3
Equilibrium Tracking and Convergence in Dynamic Games
Mertikopoulos, P., & Staudigl, M. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683224 · Cited by 4
Adapting bandit algorithms for settings with sequentially available arms
Gabrielli, M., Antonelli, M., & Trovò, F. (2024) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2023.107815 · Cited by 3
Online learning for hierarchical scheduling to support network slicing in cellular networks
Song, J., Veciana, G. A. D., & Shakkottai, S. (2021) · Performance Evaluation · doi:10.1016/j.peva.2021.102237 · Cited by 3
Rufato, R. C., Diouane, Y., Henry, J., Ahlfeld, R., & Morlier, J. (2022) · AIAA AVIATION Forum · doi:10.2514/6.2022-4037 · Cited by 3
Multichannel Resource Allocation for Smooth Streaming: Non-Convexity and Bandits
Bhimaraju, A., Zacharias, A. A., & Chatterjee, A. (2022) · IEEE Transactions on Communications · doi:10.1109/tcomm.2022.3182756 · Cited by 3
Setting Reserve Prices in Second-Price Auctions with Unobserved Bids
Rhuggenaath, J., Akçay, A., Zhang, Y., & Kaymak, U. (2022) · INFORMS journal on computing · doi:10.1287/ijoc.2022.1199 · Cited by 3
Dynamic Global Sensitivity for Differentially Private Contextual Bandits
Wang, H., Zhao, D., & Wang, H. (2022) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3523227.3546781 · Cited by 4
Multi-domain Active Learning for Semi-supervised Anomaly Detection
Vercruyssen, V., Perini, L., Meert, W., & Davis, J. J. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-26412-2_30 · Cited by 5
AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration
Brandt, J., Schede, E., Haddenhorst, B., Bengs, V., Hüllermeier, E., & Tierney, K. J. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i10.26456 · Cited by 3
PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison
Flynn, H., Reeb, D., Kandemir, M., & Peters, J. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3305381 · Cited by 3
Ichiro Hasuo, A., Oyabu, Y., Eberhart, C., Suenaga, K., Cho, K., & Katsumata, S.-Y. (2023) · Journal of Logical and Algebraic Methods in Programming · doi:10.1016/j.jlamp.2023.100922 · Cited by 3
A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of the Multi-Armed Bandit
Nakamura, S., & Sugiyama, M. (2024) · Neural Computation · doi:10.1162/neco_a_01728 · Cited by 3
Bandit Sequential Posted Pricing via Half-Concavity
Singla, S., & Wang, Y. (2024) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3670865.3673495 · Cited by 3
Bayesian Reinforcement Learning with Exploration
Lattimore, T., & Hütter, M. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11662-4_13 · Cited by 12
Akbarzadeh, N., & Tekin, C. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852376 · Cited by 3
Learning traffic congestion by contextual bandit problems for optimum localization
Şahin, Ü., Yücesoy, V., Koç, A., & Tekin, C. (2017) · Signal Processing and Communications Applications Conference (SIU) · doi:10.1109/siu.2017.7960447 · Cited by 3
On minimaxity of Follow the Leader strategy in the stochastic setting
Kotłowski, W. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.12.030 · Cited by 3
Spectral MAB for Unknown Graph Processes
Toni, L., & Pascal Frossard, B. (2018) · European Signal Processing Conference (EUSIPCO) · doi:10.23919/eusipco.2018.8553372 · Cited by 3
Learning in multi-agent systems with asymmetric information structure
Tan, C., Qi, Q., & Wong, W. S. (2020) · Neurocomputing · doi:10.1016/j.neucom.2019.08.112 · Cited by 3
Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model
Chen, C., Zhao, C., & Li, S. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20569 · Cited by 9
Optimizing mHealth Interventions with a Bandit
Rabbi, M., Klasnja, P., Choudhury, T., Tewari, A., & Murphy, S. A. (2022) · Studies in neuroscience, psychology and behavioral economics · doi:10.1007/978-3-030-98546-2_21 · Cited by 4
Online Learning for Scheduling MIP Heuristics
Chmiela, A., Gleixner, A., Lichocki, P., & Pokutta, S. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-33271-5_8 · Cited by 3
Dynamic Pricing Using Thompson Sampling with Fuzzy Events
Rhuggenaath, J., da Costa, P. R. D. O., Zhang, Y., Akçay, A., & Kaymak, U. (2020) · Communications in computer and information science · doi:10.1007/978-3-030-50146-4_48 · Cited by 3
Campagner, A., Ciucci, D., & Cabitza, F. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-57524-3_5 · Cited by 4
Yoon, G., Chow, J. Y. J., Dmitriyeva, A., & Fay, D. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2020.3038675 · Cited by 5
Keller, G., & Rady, S. (2020) · Games and Economic Behavior · doi:10.1016/j.geb.2020.08.003 · Cited by 3
Foundations of Convex Analysis
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.033 · Cited by 3
An Opinion Dynamics Model with Increasing Self-ConfidencePreprint
Wang, C. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.05732 · Cited by 3
Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth ObjectivesPreprint
Arora, R., Marinov, T. V., & Ullah, E. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.09609 · Cited by 4
Randomized Value Functions via Posterior State-Abstraction SamplingPreprint
Arumugam, D., & Roy, B. V. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.02383 · Cited by 5
Self-Tuning Bandits over Unknown Covariate-ShiftsPreprint
Suk, J., & Kpotufe, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.08584 · Cited by 3
Hadoux, E. (2015) · theses.fr (ABES) · doi:10.70675/2623c974z7d78z44d9za017z579c09ffa745 · Cited by 7
Efficient Prompt Optimization Through the Lens of Best Arm Identification
Shi, C., Yang, K., Chen, Z., Li, J., Yang, J., & Shen, C. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-3161 · Cited by 3
Emotion Recognition in the Wild
Tian, L., Oviatt, S. L., Muszyński, M., Chamberlain, B. C., Healey, J., & Sano, A. (2022) · ACM eBooks · doi:10.1145/3502398.3502404 · Cited by 2
Maximal Objectives in the Multiarmed Bandit with Applications
Özbay, E., & Kamble, V. (2024) · Management Science · doi:10.1287/mnsc.2022.00801 · Cited by 2
ϵ-Neural Thompson Sampling of Deep Brain Stimulation for Parkinson Disease Treatment
Hsu, H.-L., Gao, Q., & Pajić, M. (2024) · ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS) · doi:10.1109/iccps61052.2024.00027 · Cited by 3
On Collaboration in Distributed Parameter Estimation With Resource Constraints
Chen, Y.-Z. J., Menasché, D. S., & Towsley, D. (2024) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2024.3468997 · Cited by 2
Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis
Markarian, C., Fachkha, C., & Yassine, N. (2024) · IEEE Access · doi:10.1109/access.2024.3504541 · Cited by 2
Siddiqi, S., Phani, A., Kern, R., & Böehm, M. (2025) · ACM Transactions on Database Systems · doi:10.1145/3771766 · Cited by 4
Does Feedback Help in Bandits with Arm Erasures?
Karakas, M., Hanna, O. A., Yang, L. F., & Fragouli, C. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195223 · Cited by 2
Revenue Maximization and Learning in Product Ranking
Chen, N., Li, A., & Yang, S. (2026) · Operations Research · doi:10.1287/opre.2020.0781 · Cited by 3
Finite-Time Convergence to an $\epsilon$-Efficient Nash Equilibrium in Potential Games
Maddux, A. M., Ouhamma, R., Ćatić, H., & Kamgarpour, M. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3673502 · Cited by 2
Reinforcement Learning as Meta-induction
Douven, I., & Schurz, G. (2026) · Minds and Machines · doi:10.1007/s11023-026-09764-1 · Cited by 2
Adaptive Token Routing for Heterogeneous LLM Inference in Edge-Cloud Continuum
Patel, T. (2026) · IEEE SoutheastCon · doi:10.1109/southeastcon63549.2026.11476596 · Cited by 3
A cognitive satisficing strategy for bandit problems
Kohno, Y., & Takahashi, T. (2015) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760.2015.1075531 · Cited by 2
Noise Free Multi-armed Bandit Game
Nakamura, A., Helmbold, D. P., & Warmuth, M. K. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-30000-9_32 · Cited by 2
Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming
Lim, C. H., Linderoth, J., Luedtke, J., & Wright, S. J. (2021) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2019.0029 · Cited by 2
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.044 · Cited by 4
PPAR: A Privacy-Preserving Adaptive Ranking Algorithm for Multi-Armed-Bandit Crowdsourcing
Chen, S., Yu, D., Li, F., Zou, Z., Liang, W., & Cheng, X. (2022) · International Workshop on Quality of Service · doi:10.1109/iwqos54832.2022.9812914 · Cited by 2
MAB based Network Selection mechanism for URLLC users in RIS assisted network
Deb, S., Ghosh, S. K., & Ghosh, S. C. (2022) · IEEE International Symposium on Network Computing and Applications (NCA) · doi:10.1109/nca57778.2022.10013616 · Cited by 2
Wang, H., Wang, E., Yang, Y.-J., Yang, B., & Liu, J.-C. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3335248 · Cited by 1
On Penalization in Stochastic Multi-Armed Bandits
Fang, G., Li, P., & Samorodnitsky, G. P. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3525666 · Cited by 2
Efficient Hardware Implementation of Multi-Armed Bandit Algorithms for RIS-Aided Wireless Networks
Sharma, I., Kumar, R., & Darak, S. J. (2025) · IEEE International Conference on Interdisciplinary Approaches in Technology and Management for Social Innovation (IATMSI) · doi:10.1109/iatmsi64286.2025.10985441 · Cited by 2
Distributed and Adaptive Routing Based on Game Theory
Jonglez, B., & Gaujal, B. (2017) · International Teletraffic Congress · doi:10.23919/itc.2017.8064333 · Cited by 2
Lenient Regret for Multi-Armed Bandits
Merlis, N., & Mannor, S. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i10.17082 · Cited by 12
Autonomous Target Allocation Recommendations
Marsh, L., Cochrane, M., Lodge, R., Sims, B., Traish, J. M., & Xu, R. Y. D. (2020) · IEEE Symposium Series on Computational Intelligence (SSCI) · doi:10.1109/ssci47803.2020.9308399 · Cited by 2
A Multi-Armed Bandit Strategy for Countermeasure Selection
Cochrane, M., & Hunjet, R. (2020) · IEEE Symposium Series on Computational Intelligence (SSCI) · doi:10.1109/ssci47803.2020.9308612 · Cited by 2
Low-Regret Algorithms for Strategic Buyers with Unknown Valuations in Repeated Posted-Price Auctions
Rhuggenaath, J., da Costa, P. R. D. O., Zhang, Y., Akçay, A., & Kaymak, U. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-67661-2_25 · Cited by 2
Goal-oriented adaptive sampling under random field modelling of response probability distributions
Gautier, A., Ginsbourger, D., & Pirot, G. (2021) · ESAIM Proceedings and Surveys · doi:10.1051/proc/202171108 · Cited by 2
Dynamic Creative Optimization in Verizon Media Native Advertising
Koren, Y., Somekh, O., Shahar, A., Itzhaki, A., Cohen, T., Krasteva, M., & Shadi, T. (2020) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata50022.2020.9378251 · Cited by 2
Auto-Tuning for Cellular Scheduling Through Bandit-Learning and Low-Dimensional Clustering
Tariq, I., Sen, R., Novlan, T. D., Akoum, S., Majmundar, M., Veciana, G. A. D., & Shakkottai, S. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3077455 · Cited by 2
Regret-Minimization in Risk-Averse Bandits
Agrawal, S., Juneja, S., & Koolen, W. M. (2021) · Indian Control Conference · doi:10.1109/icc54714.2021.9703134 · Cited by 2
An Adversarial Approach to Adaptive Model Predictive Control
Wachel, P., & Rojas, C. R. (2022) · Journal of Advances in Applied & Computational Mathematics · doi:10.15377/2409-5761.2022.09.10 · Cited by 2
Reinforcement Learning for Bandits with Continuous Actions and Large Context Spaces
Duckworth, P., Vallis, K. A., Lacerda, B., & Hawes, N. (2023) · Frontiers in artificial intelligence and applications · doi:10.3233/faia230320 · Cited by 5
Aziz, M., Anderton, J., Jamieson, K., Wang, A., Bouchard, H., & Aslam, J. A. (2023) · ACM Transactions on Recommender Systems · doi:10.1145/3626324 · Cited by 2
Dorn, Y. V., Kornilov, N. М., Kutuzov, N., Nazin, A., Gorbunov, E., & Gasnikov, A. V. (2024) · Computational Management Science · doi:10.1007/s10287-023-00500-z · Cited by 3
Accelerated first-order optimization under nonlinear constraints
Muehlebach, M., & Jordan, M. I. (2025) · Mathematical Programming · doi:10.1007/s10107-025-02224-1 · Cited by 2
A Sampling-Based Gittins Index Approximation
Baas, S., Boucherie, R. J., & Braaksma, A. (2026) · Mathematics of Operations Research · doi:10.1287/moor.2023.0225 · Cited by 2
Synergies between Evolutionary Algorithms and Reinforcement Learning
Drugan, M. M. (2015) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/2739482.2756582 · Cited by 2
Dynamic and probabilistic estimation of manipulable obstacles for indoor navigation
Clingerman, C., Wei, P., & Lee, D. D. (2015) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7354249 · Cited by 2
Multi-armed bandits based on a variant of Simulated Annealing
Abdulla, M. S., & Bhatnagar, S. (2016) · Indian Journal of Pure and Applied Mathematics · doi:10.1007/s13226-016-0184-5 · Cited by 2
Optimization through satisficing with prospects
Oyo, K., & Takahashi, T. (2017) · AIP conference proceedings · doi:10.1063/1.4992542 · Cited by 2
Risk Control of Best Arm Identification in Multi-armed Bandits via Successive Rejects
Yu, X., King, I., & Lyu, M. R.-T. (2017) · Proceedings · doi:10.1109/icdm.2017.153 · Cited by 2
Managing load contract restrictions with online learning
Henríquez-Auba, R., Lesage‐Landry, A., Taylor, J. A., Olivares, D. E., & Negrete-Pincetic, M. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8309118 · Cited by 2
Learning to Rank and Discover for E-Commerce Search
Goswami, A., Zhai, C., & Mohapatra, P. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96133-0_25 · Cited by 2
Online Kernel Selection with Multiple Bandit Feedbacks in Random Feature Space
Li, J., & Liao, S. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-99247-1_27 · Cited by 2
Online Learning Framework Based on User-Centric Access Behavior
Huang, G.-H., Jiang, H., Xie, J., Zeng, Y., & Yi, S. (2018) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc/smartcity/dss.2018.00069 · Cited by 2
DORB: Dynamically Optimizing Multiple Rewards with Bandits
Pasunuru, R., Guo, H., & Bansal, M. (2020) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.625 · Cited by 9
Iterative H-norm Estimation Using Cyclic-Prefixed Signals
Müller, M. I., & Rojas, C. R. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303806 · Cited by 2
Sledge, I. J., & Príncipe, J. C. (2021) · Studies in systems, decision and control · doi:10.1007/978-3-030-60990-0_19 · Cited by 2
Meka, R., Alaeddini, A., Ovuegbe, C., Bhounsule, P. A., Najafirad, P., & Yang, K. (2021) · IEEE Access · doi:10.1109/access.2021.3095755 · Cited by 2
Optimal control for networks with unobservable malicious nodes
Liu, B., & Modiano, E. (2021) · Performance Evaluation · doi:10.1016/j.peva.2021.102230 · Cited by 2
Musavi, N., Sun, D., Mitra, S., Dullerud, G. E., & Shakkottai, S. (2021) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta48906.2021.9659123 · Cited by 2
Particle Thompson Sampling with Static Particles
Zhou, Z., & Hajek, B. (2023) · Conference on Information Sciences and Systems · doi:10.1109/ciss56502.2023.10089653 · Cited by 2
Universal regression with adversarial responses
Blanchard, M., & Jaillet, P. (2023) · The Annals of Statistics · doi:10.1214/23-aos2299 · Cited by 2
Near Optimal Memory-Regret Tradeoff for Online Learning
Peng, B., & Rubinstein, A. (2023) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs57990.2023.00069 · Cited by 26
Fair Coexistence of Heterogeneous Networks: A Novel Probabilistic Multi-Armed Bandit Approach
Guo, Z., Zhang, C., Li, M., & Krunz, M. (2023) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt58741.2023.10349867 · Cited by 2
Cache content placement in the presence of fictitious requests in mmWave 5G IAB networks
Nazarifard, F. S. H., Rashidi, Z., & Hakami, V. (2024) · Ad Hoc Networks · doi:10.1016/j.adhoc.2024.103563 · Cited by 2
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603198 · Cited by 2
Algorithmic models of human decision making in Gaussian multi-armed bandit problems
Reverdy, P. B., Srivastava, V., & Leonard, N. E. (2014) · European Control Conference (ECC) · doi:10.1109/ecc.2014.6862580 · Cited by 2
Multi-armed bandits for efficient lifetime estimation in MPSoC design
Ma, C., Mahajan, A., & Meyer, B. H. (2017) · Design, Automation, and Test in Europe · doi:10.23919/date.2017.7927235 · Cited by 2
Adversarial Influence Maximization
Khim, J., Jog, V., & Loh, P. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849828 · Cited by 2
OWLS: Opportunistic Wireless Link Scheduling with SINR Constraints
Xu, X., Chen, Y., He, S., & Bobbie, P. O. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-23597-0_34 · Cited by 2
Response Prediction for Low-Regret Agents
Alaei, S., Badanidiyuru, A., Mahdian, M., & Yazdanbod, S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-35389-6_3 · Cited by 2
Ballooning Multi-Armed Bandits
Ghalme, G. S., Dhamal, S., Jain, S., Gujar, S., & Narahari, Y. (2020) · Artificial Intelligence · doi:10.1016/j.artint.2021.103485 · Cited by 2
Tampubolon, E., & Boche, H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3034874 · Cited by 2
Jiang, W., Xu, Z., Gao, C., Gu, J., & Wang, Y. (2020) · Software Practice and Experience · doi:10.1002/spe.2919 · Cited by 2
Algorithmic Monoculture and Social Welfare
Raghavan, M. (2023) · ACM eBooks · doi:10.1145/3603195.3603211 · Cited by 2
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.