The DOI matches its Crossref record; 244 of the 244 references it cites were found in a registry or an index.
Bandit Algorithms
Abstract
Decision-making in the face of uncertainty is a significant challenge in machine learning, and the multi-armed bandit model is a commonly used framework to address it. This comprehensive and rigorous introduction to the multi-armed bandit problem examines all the major settings, including stochastic, adversarial, and Bayesian frameworks. A focus on both mathematical intuition and carefully worked proofs makes this an excellent reference for established researchers and a helpful resource for graduate students in computer science, engineering, statistics, applied mathematics and economics. Linear bandits receive special attention as one of the most useful models in applications, while other chapters are dedicated to combinatorial bandits, ranking, non-stationary problems, Thompson sampling and pure exploration. The book ends with a peek into the world beyond bandits with an introduction to partial monitoring and learning in Markov decision processes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Prospect Theory: An Analysis of Decision under Risk
Kahneman, D., & Tversky, A. (1979) · Econometrica · doi:10.2307/1914185 · Cited by 48,524
Gelman, A., Carlin, J. B., Stern, H. S., & Rubin, D. B. (2003) · doi:10.1201/9780429258480 · Cited by 27,276
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
Mastering the game of Go with deep neural networks and tree search
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016) · Nature · doi:10.1038/nature16961 · Cited by 15,612
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Advances in neural information processing systems 7
(1996) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(96)90463-0 · Cited by 14,281
Advances in Neural Information Processing Systems 29
Teymur, O., Zygalakis, K., & Calderhead, B. (2016) · Cited by 13,887
Advances in Neural Information Processing Systems 25
Zhang, Y., Sutton, C. A., Storkey, A., & Zoubin Ghahramani, A. (2012) · Cited by 12,653
Proceedings of the 24th international conference on Machine learning
(2007) · doi:10.1145/1273496 · Cited by 11,630
(1995) · Cited by 10,558
Reinforcement Learning: An Introduction
Johnson, J. D., Li, J., & Chen, Z. (2000) · Neurocomputing · doi:10.1016/s0925-2312(00)00324-6 · Cited by 8,414
Statistical Decision Theory and Bayesian Analysis
Berger, J. O. (1985) · Springer Series in Statistics · doi:10.1007/978-1-4757-4286-2 · Cited by 7,722
Nelder, J. A., & Wedderburn, R. W. M. (1972) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344614 · Cited by 7,194
Optimization of conditional value-at-risk
Rockafellar, R. T., & Uryasev, S. (2000) · The Journal of Risk · doi:10.21314/jor.2000.038 · Cited by 6,725
Time Discounting and Time Preference: A Critical Review
Frederick, S., Loewenstein, G. F., & O’Donoghue, T. (2002) · Journal of Economic Literature · doi:10.1257/002205102320161311 · Cited by 6,381
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
Proceedings of the 25th international conference on Machine learning
Cohen, W. W., McCallum, A., & Roweis, S. T. (2008) · Cited by 5,691
Weak Convergence and Empirical Processes
van der Vaart, A. W., & Wellner, J. A. (1996) · Springer Series in Statistics · doi:10.1007/978-1-4757-2545-2 · Cited by 5,014
Information Theory, Inference, and Learning Algorithms
(2004) · Kybernetes · doi:10.1108/03684920410534506 · Cited by 4,937
Probability Theory: The Logic of Science
Jaynes, E. T. (2003) · doi:10.1017/cbo9780511790423 · Cited by 4,045
Theory of Games and Economic Behavior
Hawkins, D. (1945) · Philosophy of Science · doi:10.1086/286866 · Cited by 3,887
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
Bayes, T. (1763) · Philosophical Transactions of the Royal Society of London · doi:10.1098/rstl.1763.0053 · Cited by 2,995
Exposition of a New Theory on the Measurement of Risk
Bernoulli, D. (1954) · Econometrica · doi:10.2307/1909829 · Cited by 2,736
THOMPSON, W. R. (1933) · Biometrika · doi:10.1093/biomet/25.3-4.285 · Cited by 2,712
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
Proceedings of the 23rd international conference on Machine learning
Cohen, W. W., & Moore, A. (2006) · Cited by 2,647
Zur Theorie der Gesellschaftsspiele
v. Neumann, J. (1928) · Mathematische Annalen · doi:10.1007/bf01448847 · Cited by 2,572
Introduction to Nonparametric Estimation
Tsybakov, A. B. (2009) · Springer Series in Statistics · doi:10.1007/b13794 · Cited by 2,486
Foundations of Modern Probability
Kallenberg, O. (2002) · Probability and Its Applications · doi:10.1007/978-1-4757-4015-8 · Cited by 2,447
Asymptotically efficient adaptive allocation rules
Lai, T. L., & Robbins, H. (1985) · Advances in Applied Mathematics · doi:10.1016/0196-8858(85)90002-8 · Cited by 2,406
(2002) · doi:10.1137/s0097539701398375 · Cited by 2,275
Some 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
A Note on Measurement of Utility
Samuelson, P. A. (1937) · The Review of Economic Studies · doi:10.2307/2967612 · Cited by 2,164
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics 2016
Murray, I., & Graham, M. M. (2016) · Cited by 2,115
Box, G. E. P. (1976) · Journal of the American Statistical Association · doi:10.1080/01621459.1976.10480949 · Cited by 2,114
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16
Storkey, A. (2004) · neural information processing systems · Cited by 2,085
Proceedings of The 32nd International Conference on Machine Learning
Germain, M., Gregor, K., Murray, I., & Larochelle, H. (2015) · Cited by 2,020
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Advances in Neural Information Processing Systems 18
Murray, I., Mackay, D., Zoubin Ghahramani, A., & Skilling, J. (2006) · Cited by 1,927
Theory of Optimal Experiments.
Herzberg, A. M., Wynn, H. P., Fedorov, V. V., Studden, W. J., & Klimko, E. M. (1972) · Biometrika · doi:10.2307/2334826 · Cited by 1,897
Advances in Neural Information Processing Systems 21
Griffiths, T. L., Lucas, C. G., Williams, J. J., & Kalish, M. L. (2009) · neural information processing systems · Cited by 1,854
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. W. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2182033 · Cited by 1,850
Sion, M. (1958) · Pacific Journal of Mathematics · doi:10.2140/pjm.1958.8.171 · Cited by 1,843
Introduction to Derivative-Free Optimization
Conn, A. R., Scheinberg, K., & Vicente, L. N. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718768 · Cited by 1,840
Entropy and Information Theory
Gray, R. M. (2011) · Springer eBooks · doi:10.1007/978-1-4419-7970-4 · Cited by 1,803
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768
(1998) · Springer Texts in Statistics · doi:10.1007/b98854 · Cited by 1,719
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
Williams, D. (1991) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813658 · Cited by 1,691
Markov Chains and Stochastic Stability
Meyn, S., Tweedie, R. L., & Glynn, P. W. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511626630 · Cited by 1,680
Bogachev, V. I. (2007) · Springer eBooks · doi:10.1007/978-3-540-34514-5 · Cited by 1,621
Proceedings of the 20th conference on Uncertainty in artificial intelligence
Meek, C., Chickering, M., & Halpern, J. Y. (2004) · Cited by 1,574
Robustness in the Strategy of Scientific Model Building
Box, G. E. P. (1979) · Robustness in Statistics · doi:10.1016/b978-0-12-438150-6.50018-2 · Cited by 1,562
Bandit processes and dynamic allocation indices
Gittins, J. C. (1979) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1979.tb01068.x · Cited by 1,487
The Complexity of Markov Decision Processes
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.441 · Cited by 1,329
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S., & Cesa-Bianchi, N. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000024 · Cited by 1,295
Derivative-free optimization: a review of algorithms and comparison of software implementations
Rios, L. M., & Sahinidis, N. V. (2013) · Journal of Global Optimization · doi:10.1007/s10898-012-9951-y · Cited by 1,276
Online Learning and Online Convex Optimization
Shalev-Shwartz, S. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000018 · Cited by 1,246
Using confidence bounds for exploitation-exploration trade-offs
Auer, P. L. (2003) · Journal of Machine Learning Research · doi:10.5555/944919.944941 · Cited by 1,229
The definition of random sequences
Martin-Löf, P. (1966) · Information and Control · doi:10.1016/s0019-9958(66)80018-9 · Cited by 1,220
Sharot, T. (2011) · Current Biology · doi:10.1016/j.cub.2011.10.030 · Cited by 1,187
Restless bandits: activity allocation in a changing world
Whittle, P. (1988) · Journal of Applied Probability · doi:10.1017/s0021900200040420 · Cited by 1,173
THE PROBABILITY RANKING PRINCIPLE IN IR
ROBERTSON, S. E. (1977) · Journal of Documentation · doi:10.1108/eb026647 · Cited by 1,103
Large Deviations Techniques and Applications
Dembo, A., & Zeitouni, O. (2009) · Applications of mathematics · doi:10.1007/978-3-642-03311-7 · Cited by 1,056
Algorithms for Reinforcement Learning
Szepesvári, C. (2010) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.1007/978-3-031-01551-9 · Cited by 1,049
Self-citationHyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., & Talwalkar, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.06560 · Cited by 1,018
Markov Chains and Mixing Times
Levin, D., & Peres, Y. (2017) · American Mathematical Society eBooks · doi:10.1090/mbk/107 · Cited by 1,000
Elements of Information Theory
(2013) · Wireless Communications · doi:10.1002/9781118576618.ch7 · Cited by 999
Adaptive estimation of a quadratic functional by model selection
Laurent, B., & Massart, P. (2000) · The Annals of Statistics · doi:10.1214/aos/1015957395 · Cited by 995
On Relevance, Probabilistic Indexing and Information Retrieval
Maron, M. E., & Kuhns, J. L. (1960) · Journal of the ACM · doi:10.1145/321033.321035 · Cited by 907
The Equivalence of Two Extremum Problems
Kiefer, J., & Wolfowitz, J. (1960) · Canadian Journal of Mathematics · doi:10.4153/cjm-1960-030-4 · Cited by 879
Counterfactual reasoning and learning systems: the example of computational advertising
Bottou, L., Peters, J., Quiñonero-Candela, J., Charles, D. X., Chickering, D. M., Portugaly, E., Ray, D., Simard, P., & Snelson, E. (2013) · Journal of Machine Learning Research · Cited by 863
The accuracy of the Gaussian approximation to the sum of independent variates
Berry, A. C. (1941) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1941-0003498-3 · Cited by 854
Analysis of Thompson Sampling for the multi-armed bandit problem
Agrawal, S., & Goyal, N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.1797 · Cited by 819
An Introduction to Matrix Concentration Inequalities
Tropp, J. A. (2015) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000048 · Cited by 792
Near-Optimal Reinforcement Learning in Polynomial Time
Kearns, M., & Singh, S. (2002) · Machine Learning · doi:10.1023/a:1017984413808 · Cited by 792
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Introduction to Online Convex Optimization
Hazan, E. (2016) · Foundations and Trends in Optimization · doi:10.1561/2400000013 · Cited by 747
Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization
Chen, C.-H., Lin, J., Yücesan, E., & Chick, S. E. (2000) · Discrete Event Dynamic Systems · doi:10.1023/a:1008349927281 · Cited by 739
Multi‐Armed Bandit Allocation Indices
Gittins, J., Glazebrook, K., & Weber, R. (2011) · Wiley eBooks · doi:10.1002/9780470980033 · Cited by 684
On the Sample Complexity of Reinforcement Learning
Kakade, S. M. (2003) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 676
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding
O’Donoghue, B., Chu, E., Parikh, N., & Boyd, S. (2016) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-016-0892-3 · Cited by 664
Proceedings of the 24th International Conference on Artificial Intelligence
Yang, Q., & Wooldridge, M. (2015) · International Conference on Artificial Intelligence · Cited by 661
Problem Complexity and Method Efficiency in Optimization
Darzentas, J., Nemirovsky, A., & Yudin, D. B. (1984) · Journal of the Operational Research Society · doi:10.2307/2581380 · Cited by 650
Berry, D. A., & Fristedt, B. (1985) · Springer eBooks · doi:10.1007/978-94-015-3711-7 · Cited by 633
Agricultural Decision Analysis
Carlson, G. A. (1977) · Medical Entomology and Zoology · Cited by 604
Kaelbling, L. P. (1993) · doi:10.7551/mitpress/4168.001.0001 · Cited by 599
Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
Arapostathis, A., Borkar, V. S., Fernández-Gaucherand, E., Ghosh, M. K., & Marcus, S. I. (1993) · SIAM Journal on Control and Optimization · doi:10.1137/0331018 · Cited by 592
Efficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
Fundamentals of Nonparametric Bayesian Inference
Ghosal, S., & van der Vaart, A. (2017) · Cambridge University Press eBooks · doi:10.1017/9781139029834 · Cited by 590
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
(2023) · doi:10.1145/3564246 · Cited by 587
Cover, T. M. (1991) · Mathematical Finance · doi:10.1111/j.1467-9965.1991.tb00002.x · Cited by 587
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581
Exploration–exploitation tradeoff using variance estimates in multi-armed bandits
Audibert, J.-Y., Munos, R., & Szepesvári, C. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.01.016 · Cited by 569
Self-citationHerbster, M., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007424614876 · Cited by 560
Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
Agrawal, R. (1995) · Advances in Applied Probability · doi:10.2307/1427934 · Cited by 540
Proceedings of the 22nd international conference on Machine learning
Džeroski, S., Raedt, L. D., & Wrobel, S. (2005) · Cited by 534
A Tutorial on Thompson Sampling
Daniel, J. R., Benjamin, V. R., Abbas, K., Ian, O., & Zheng, W. (2018) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000070 · Cited by 524
Multi-Armed Bandits and the Gittins Index
Whittle, P. (1980) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1980.tb01111.x · Cited by 514
Great Expectations: The Theory of Optimal Stopping.
Brown, B. M., Chow, Y. S., Robbins, H., & Siegmund, D. (1972) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344690 · Cited by 510
Learning diverse rankings with multi-armed bandits
Radlinski, F., Kleinberg, R., & Joachims, T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390255 · Cited by 503
Learning to Optimize via Posterior Sampling
Russo, D., & Van Roy, B. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2014.0650 · Cited by 493
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Rakhlin, A., Shamir, O., & Sridharan, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.5647 · Cited by 492
Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability.
David, F. N., LeCam, L., Neyman, J., & Scott, E. L. (1973) · Biometrics · doi:10.2307/2529411 · Cited by 490
On an index policy for restless bandits
Weber, R., & Weiss, G. (1990) · Journal of Applied Probability · doi:10.1017/s0021900200039176 · Cited by 486
On Upper-Confidence Bound Policies for Switching Bandit Problems
Garivier, A., & Moulines, E. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-24412-4_16 · Cited by 442
Geometric Algorithms and Combinatorial Optimization
Leung, J. M. Y., Grötschel, M., Lovász, L., & Schrijver, A. (1989) · Journal of the Operational Research Society · doi:10.2307/2583689 · Cited by 435
Encyclopedia of Operations Research and Management Science
(2013) · Springer eBooks · doi:10.1007/978-1-4419-1153-7 · Cited by 429
An analysis of model-based Interval Estimation for Markov Decision Processes
Strehl, A. L., & Littman, M. L. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.009 · Cited by 428
Linearly Parameterized Bandits
Rusmevichientong, P., & Tsitsiklis, J. N. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0446 · Cited by 427
Convergence of Estimates Under Dimensionality Restrictions
LeCam, L. (1973) · The Annals of Statistics · doi:10.1214/aos/1193342380 · Cited by 422
Online Learning: Theory, Algorithms, and Applications
Shalev‐Shwartz, S. (2007) · Cited by 418
Gai, Y., Krishnamachari, B., & Jain, R. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2011.2181864 · Cited by 413
McDiarmid, C. (1998) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12788-9_6 · Cited by 405
Chuklin, A., Markov, I., & de Rijke, M. (2015) · Synthesis Lectures on Information Concepts, Retrieval, and Services · doi:10.1007/978-3-031-02294-4 · Cited by 398
Sequential Design of Experiments
Chernoff, H. (1959) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177706205 · Cited by 393
R-MAX: a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, R. I., & Tennenholtz, M. (2001) · Cited by 366
Pure Exploration in Multi-armed Bandits Problems
Bubeck, S., Munos, R., & Stoltz, G. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-04414-4_7 · Cited by 362
Anantharam, V., Varaiya, P., & Walrand, J. (1987) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1987.1104491 · Cited by 358
Minimax policies for adversarial and stochastic bandits
Audibert, J.-Y., Est, U. P., & Bubeck, S. (2009) · HAL · Cited by 346
Anscombe, F. J. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500851 · Cited by 339
(2003) · Lecture Notes in Computer Science · doi:10.1007/b12006 · Cited by 333
Axler, S. (1997) · Undergraduate Texts in Mathematics · doi:10.1007/b97662 · Cited by 331
Vovk, V. G. (1990) · Colt Proceedings 1990 · doi:10.1016/b978-1-55860-146-8.50032-1 · Cited by 328
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
Garivier, A., & Cappé, O. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.2490 · Cited by 326
Cesa-Bianchi, N., & Lugosi, G. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2012.01.001 · Cited by 319
The Sample Complexity of Exploration in the Multi-Armed Bandit Problem
Mannor, S., & Tsitsiklis, J. N. (2004) · doi:10.5555/1005332.1005355 · Cited by 307
Challenging the empirical mean and empirical variance: A deviation study
Catoni, O. (2012) · Annales de l'Institut Henri Poincaré, Probabilités et Statistiques · doi:10.1214/11-aihp454 · Cited by 298
UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem
Auer, P. L., & Ortner, R. (2010) · Periodica Mathematica Hungarica · doi:10.1007/s10998-010-3055-6 · Cited by 296
Extensions of the multiarmed bandit problem: The discounted case
Varaiya, P., Walrand, J., & Buyukkoc, C. (1985) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1985.1103989 · Cited by 279
Adaptive Treatment Allocation and the Multi-Armed Bandit Problem
Lai, T. L. (1987) · The Annals of Statistics · doi:10.1214/aos/1176350495 · Cited by 279
Keener, R. W. (2009) · Springer Texts in Statistics · doi:10.1007/978-0-387-93839-4_1 · Cited by 275
Online Decision Making with High-Dimensional Covariates
Bastani, H., & Bayati, M. (2020) · Operations Research · doi:10.1287/opre.2019.1902 · Cited by 263
On the Gittins Index for Multiarmed Bandits
Weber, R. (1992) · The Annals of Applied Probability · doi:10.1214/aoap/1177005588 · Cited by 259
Proceedings of the 2008 International Conference on Web Search and Data Mining
Najork, M., Broder, A., & Chakrabarti, S. (2008) · Cited by 252
Survey on Applications of Multi-Armed and Contextual Bandits
Bouneffouf, D., Rish, I., & Aggarwal, C. (2020) · 2020 IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec48606.2020.9185782 · Cited by 251
Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges
Villar, S. S., Bowden, J., & Wason, J. (2015) · Statistical Science · doi:10.1214/14-sts504 · Cited by 244
Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2277869 · Cited by 244
Conditioning as disintegration
Chang, J. T., & Pollard, D. (1997) · Statistica Neerlandica · doi:10.1111/1467-9574.00056 · Cited by 241
Non-stochastic Best Arm Identification and Hyperparameter Optimization
Jamieson, K., & Talwalkar, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.07943 · Cited by 232
Optimal Adaptive Policies for Markov Decision Processes
Burnetas, A. N., & Katehakis, M. N. (1997) · Mathematics of Operations Research · doi:10.1287/moor.22.1.222 · Cited by 232
Contextual Bandits with Similarity Information
Slivkins, A. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0907.3986 · Cited by 232
Jefferson, A., Bortolotti, L., & Kuzmanovic, B. (2017) · Consciousness and Cognition · doi:10.1016/j.concog.2016.10.005 · Cited by 232
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered ArmsPreprint
CHENWei, WangYajun, YuanYang, & WangQinshi (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.8339 · Cited by 223
(More) Efficient Reinforcement Learning via Posterior Sampling
Osband, I., Russo, D., & Roy, B. V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.0940 · Cited by 222
Optimal Adaptive Policies for Sequential Allocation Problems
Burnetas, A. N., & Katehakis, M. N. (1996) · Advances in Applied Mathematics · doi:10.1006/aama.1996.0007 · Cited by 219
Estimation des densit�s: risque minimax
Bretagnolle, J., & Huber, C. (1979) · Zeitschrift f�r Wahrscheinlichkeitstheorie und Verwandte Gebiete · doi:10.1007/bf00535278 · Cited by 218
Epsilon–First Policies for Budget–Limited Multi-Armed Bandits
Tran-Thanh, L., Chapman, A. C., de Cote, E. M., Rogers, A., & Jennings, N. R. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7758 · Cited by 216
Self-Normalized Processes: Limit Theory and Statistical Applications
de la Peña, V., Lai, T. L., & Shao, Q.-M. (2001) · Cited by 214
Optimistic bayesian sampling in contextual-bandit problems
May, B. C., Korda, N., Lee, A., & Leslie, D. S. (2012) · Lancaster EPrints (Lancaster University) · doi:10.82444/warw.33678499 · Cited by 213
Regret Bounds and Minimax Policies under Partial Monitoring
Audibert, J.-Y., & Bubeck, S. (2010) · HAL · Cited by 210
Regret in Online Combinatorial Optimization
Audibert, J.-Y., Bubeck, S., & Lugosi, G. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2013.0598 · Cited by 208
Near-optimal Regret Bounds for Reinforcement Learning
(2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1859902 · Cited by 207
Near-optimal Regret Bounds for Reinforcement Learning
Auer, P. L., Jaksch, T., & Ortner, R. (2008) · Cited by 197
Ionides, E. L. (2008) · Journal of Computational and Graphical Statistics · doi:10.1198/106186008x320456 · Cited by 188
Boundary Crossing Probabilities for the Wiener Process and Sample Sums
Robbins, H., & Siegmund, D. (1970) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177696787 · Cited by 187
Efficient Contextual Bandits in Non-stationary WorldsPreprint
Luo, H., Wei, C.-Y., Agarwal, A., & Langford, J. C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.01799 · Cited by 187
Kullback–Leibler upper confidence bounds for optimal sequential allocation
Cappé, O., Garivier, A., Maillard, O.-A., Munos, R., & Stoltz, G. (2013) · The Annals of Statistics · doi:10.1214/13-aos1119 · Cited by 181
Boundary Crossing of Brownian Motion
Lerche, H. R. (1986) · Lecture Notes in Statistics · doi:10.1007/978-1-4615-6569-7 · Cited by 175
Regret Minimization Under Partial Monitoring
Cesa‐Bianchi, N., Lugosi, G., & Stoltz, G. (2006) · Mathematics of Operations Research · doi:10.1287/moor.1060.0206 · Cited by 174
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary
McMahan, H. B., & Blum, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27819-1_8 · Cited by 172
Some Problems in the Theory of Dynamic Programming
Bellman, R. (1954) · Econometrica · doi:10.2307/1909830 · Cited by 171
A primal-dual perspective of online learning algorithms
Shalev-Shwartz, S., & Singer, Y. (2007) · Machine Learning · doi:10.1007/s10994-007-5014-x · Cited by 168
Efficient bandit algorithms for online multiclass prediction
Kakade, S. M., Shalev-Shwartz, S., & Tewari, A. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390212 · Cited by 168
Uniform Central Limit Theorems
Dudley, R. M. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139014830 · Cited by 166
Stochastic Convex Optimization with Bandit Feedback
Agarwal, A., Foster, D. P., Hsu, D., Kakade, S. M., & Rakhlin, A. (2013) · SIAM Journal on Optimization · doi:10.1137/110850827 · Cited by 162
The best of both worlds: stochastic and adversarial banditsPreprint
Bubeck, S., & Slivkins, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.4473 · Cited by 162
The multi-armed bandit problem with covariatesPreprint
Perchet, V. (n.d.) · Cited by 160
Foundations of computer science: what are they and how do we teach them?
Proulx, V. K., Rasala, R., & Fell, H. (1996) · ACM SIGCSE Bulletin · doi:10.1145/237477.237523 · Cited by 159
PAC Bounds for Discounted MDPs
Lattimore, T., & Hütter, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34106-9_26 · Cited by 156
Self-citationSolving two‐armed Bernoulli bandit problems using a Bayesian learning automaton
Granmo, O. (2010) · International Journal of Intelligent Computing and Cybernetics · doi:10.1108/17563781011049179 · Cited by 145
Adapting to a Changing Environment: the Brownian Restless Bandits.
Slivkins, A., & Upfal, E. (2008) · Cited by 144
A Short Proof of the Gittins Index Theorem
Tsitsiklis, J. N. (1994) · The Annals of Applied Probability · doi:10.1214/aoap/1177005207 · Cited by 143
On the Theory of Apportionment
Thompson, W. R. (1935) · American Journal of Mathematics · doi:10.2307/2371219 · Cited by 142
An Asymptotically Optimal Bandit Algorithm for Bounded Support Models.
Honda, J., & Akimichi Takemura, Y. (2010) · Cited by 139
The multi-armed bandit problem with covariates
Perchet, V., & Rigollet, P. (2013) · The Annals of Statistics · doi:10.1214/13-aos1101 · Cited by 136
Online Markov Decision Processes Under Bandit Feedback
Neu, G., György, A., Szepesvári, C., & Antos, A. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2292137 · Cited by 135
Self-citationA Minimum Relative Entropy Principle for Learning and Acting
Ortega, P. A., & Braun, D. A. (2010) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3062 · Cited by 135
Cascading Bandits for Large-Scale Recommendation ProblemsPreprint
Zong, S., Ni, H., Sung, K., Ke, N. R., Wen, Z., & Kveton, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.05359 · Cited by 135
Bandit problems with infinitely many arms
Berry, D. A., Chen, R. W., Zame, A., Heath, D. C., & Shepp, L. A. (1997) · The Annals of Statistics · doi:10.1214/aos/1069362389 · Cited by 133
An Asymptotic Minimax Theorem for the Two Armed Bandit Problem
Vogel, W. (1960) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177705907 · Cited by 127
Sequential choice from several populations.
Katehakis, M. N., & Robbins, H. E. (1995) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.92.19.8584 · Cited by 126
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence
Albrecht, S. V., & Ramamoorthy, R. (2014) · Cited by 126
A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler DivergencesPreprint
Maillard, O.-A., Munos, R., & Stoltz, G. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1105.5820 · Cited by 124
Minimal Exploration in Structured Stochastic BanditsPreprint
Combes, R., Magureanu, S., & Proutière, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.00400 · Cited by 124
Four proofs of Gittins’ multiarmed bandit theorem
Frostig, E., & Weiss, G. (2014) · Annals of Operations Research · doi:10.1007/s10479-013-1523-0 · Cited by 121
Partial Monitoring—Classification, Regret Bounds, and Algorithms
Bartók, G., Foster, D. P., Pál, D., Rakhlin, A., & Szepesvári, C. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2014.0663 · Cited by 118
Self-citationOn Bayesian index policies for sequential resource allocation
Kaufmann, E. (2018) · The Annals of Statistics · doi:10.1214/17-aos1569 · Cited by 117
Efficient learning by implicit exploration in bandit problems with side observationsPreprint
Kocák, T., Neu, G., Valko, M., & Munos, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.24555 · Cited by 116
Selective sampling and active learning from single and multiple teachers
Dekel, O., Gentile, C., & Sridharan, K. (2012) · Journal of Machine Learning Research · doi:10.5555/2503308.2503327 · Cited by 116
The max K-armed bandit: a new model of exploration applied to search heuristic selection
Cicirello, V. A., & Smith, S. F. (2005) · Cited by 112
On the concentration of the missing mass
Berend, D., & Kontorovich, A. (2013) · Electronic Communications in Probability · doi:10.1214/ecp.v18-2359 · Cited by 110
Multiclass classification with bandit feedback using adaptive regularization
Crammer, K., & Gentile, C. (2012) · Machine Learning · doi:10.1007/s10994-012-5321-8 · Cited by 109
Regret bounds for prediction problems
Gordon, G. J. (1999) · doi:10.1145/307400.307410 · Cited by 105
Cited by
Degenerate Feedback Loops in Recommender Systems
Jiang, R., Chiappa, S., Lattimore, T., György, A., & Kohli, P. (2019) · Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3306618.3314288 · Cited by 232
Self-citationA Survey of Reinforcement Learning from Human Feedback
Kaufmann, T., Weng, P., Bengs, V., & Hüllermeier, E. (2023) · arXiv · doi:10.48550/arxiv.2312.14925 · Cited by 43
Kadi, H. A., & Terzić, K. (2023) · Sensors · doi:10.3390/s23052389 · Cited by 27
“Some fundamental myopic exploration strategies are derived from the Multi-armed Bandit (MAB) formulation [196], then scaled to more complex MDP/POMDP settings.”
MethodConformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions
Lekeufack, J., Angelopoulos, A. N., Bajcsy, A., Jordan, M. I., & Malik, J. (2024) · 2024 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra57147.2024.10610041 · Cited by 18
Sublinear regret for learning POMDPs
Xiong, Y., Chen, N., Gao, X., & Zhou, X. (2022) · Production and Operations Management · doi:10.1111/poms.13778 · Cited by 6
Metadata
- Authors
- Lattimore, T., & Szepesvári, C.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2020-07-04
- OpenAlex
- W4206530644
- Cited by
- 976
- References
- 244
- FWCI
- 55.96
- Type
- book
- Language
- en
- Open access
- closed
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.