The DOI matches its Crossref record; 141 of the 141 references it cites were found in a registry or an index.
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Abstract
A multi-armed bandit problem - or, simply, a bandit problem - is a sequential allocation problem defined by a set of actions. At each time step, a unit resource is allocated to an action and some observable payoff is obtained. The goal is to maximize the total payoff obtained in a sequence of allocations. The name bandit refers to the colloquial term for a slot machine (a "one-armed bandit" in American slang). In a casino, a sequential allocation problem is obtained when the player is facing many slot machines at once (a "multi-armed bandit"), and must repeatedly choose where to insert the next coin. 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 payoff process associated with each option. In this book, the focus is on two extreme cases in which the analysis of regret is particularly simple and elegant: independent and identically distributed payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, it also analyzes some of the most important variants and extensions, such as the contextual bandit model. This monograph is an ideal reference for students and researchers with an interest in bandit problems.
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
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
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
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
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Bandit Based Monte-Carlo Planning
Kocsis, L., & Szepesvári, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11871842_29 · Cited by 2,855
THOMPSON, W. R. (1933) · Biometrika · doi:10.1093/biomet/25.3-4.285 · Cited by 2,712
A contextual-bandit approach to personalized news article recommendation
Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772758 · Cited by 2,562
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
Stochastic Estimation of the Maximum of a Regression Function
Kiefer, J., & Wolfowitz, J. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729392 · Cited by 2,133
Robust Stochastic Approximation Approach to Stochastic Programming
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070704277 · Cited by 1,945
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
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
(2003) · Cited by 1,733
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
Fundamentals of Convex Analysis
Hiriart-Urruty, J.-B., & Lemaréchal, C. (2001) · Springer eBooks · doi:10.1007/978-3-642-56468-0 · Cited by 1,402
Problem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,329
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
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Hart, S., & Mas-Colell, A. (2000) · Econometrica · doi:10.1111/1468-0262.00153 · Cited by 1,088
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A., & Teboulle, M. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00231-6 · Cited by 1,060
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
Sequential minimax search for a maximum
Kiefer, J. (1953) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1953-0055639-3 · Cited by 1,000
(2011) · Cited by 1,000
Multi-Armed Bandit Allocation Indices.
Bather, J. A., & Gittins, J. C. (1990) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2982809 · Cited by 998
Improved Algorithms for Linear Stochastic Bandits
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011) · Cited by 919
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
Near-optimal Regret Bounds for Reinforcement Learning
Jaksch, T., Ortner, R., & Auer, P. L. (2010) · Cited by 784
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
Contextual Bandits with Linear Payoff Functions
Chu, W., Li, L. C., Reyzin, L., & Schapire, R. E. (2011) · Cited by 633
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
(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
Herbster, M., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007424614876 · Cited by 560
Online convex optimization in the bandit setting: gradient descent without a gradient
Flaxman, A. D., Kalai, A. T., & McMahan, H. B. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408007 · Cited by 546
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
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
Kearns, M., Mansour, Y., & Ng, A. Y. (2002) · Machine Learning · doi:10.1023/a:1017932429737 · Cited by 488
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Bach, F., & Moulines, É. (2011) · Cited by 488
An Elementary Introduction to Modern Convex Geometry
Ball, K. (1997) · Cambridge University Press eBooks · doi:10.1017/9781009701853.002 · Cited by 483
Best Arm Identification in Multi-Armed Bandits
Audibert, J.-Y., Bubeck, S., & Munos, R. (2010) · HAL · Cited by 446
Self-citationOn 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
Theory of Classification: a Survey of Some Recent Advances
Boucheron, S., Bousquet, O., & Lugosi, G. (2005) · ESAIM: Probability and Statistics · doi:10.1051/ps:2005018 · Cited by 436
Linearly Parameterized Bandits
Rusmevichientong, P., & Tsitsiklis, J. N. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0446 · Cited by 427
Online Learning: Theory, Algorithms, and Applications
Shalev‐Shwartz, S. (2007) · Cited by 418
Multi-armed bandits in metric spaces
Kleinberg, R., Slivkins, A., & Upfal, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374475 · Cited by 396
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis
Kaufmann, E., Korda, N., & Munos, R. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-34106-9_18 · Cited by 365
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
Self-citationMinimax policies for adversarial and stochastic bandits
Audibert, J.-Y., Est, U. P., & Bubeck, S. (2009) · HAL · Cited by 346
Self-citationThe 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
The Epoch-Greedy algorithm for contextual multi-armed bandits
Langford, J. C., & Zhang, T. (2007) · Cited by 320
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
PAC Bounds for Multi-armed Bandit and Markov Decision Processes
Even-Dar, E., Mannor, S., & Mansour, Y. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45435-7_18 · 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
Nearly Tight Bounds for the Continuum-Armed Bandit Problem
Kleinberg, R. (2004) · Cited by 294
Modification of UCT with Patterns in Monte-Carlo Go
Gelly, S., Wang, Y., Munos, R., & Teytaud, O. (2006) · HAL · Cited by 290
Bayes and Minimax Solutions of Sequential Decision Problems
Arrow, K. J., Blackwell, D., & Girshick, M. A. (1949) · Econometrica · doi:10.2307/1905525 · Cited by 274
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.
Agarwal, A., Dekel, O., & Xiao, L. (2010) · Cited by 261
Parametric Bandits: The Generalized Linear Case
Filippi, S., Cappé, O., Garivier, A., & Szepesvári, C. (2010) · Cited by 259
A General Class of Adaptive Strategies
Hart, S., & Mas‐Colell, A. (2001) · Journal of Economic Theory · doi:10.1006/jeth.2000.2746 · Cited by 248
Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2277869 · Cited by 244
Self-citationOptimal 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
Bubeck, S., Munos, R., Stoltz, G., & Szepesvári, C. (2011) · Journal of Machine Learning Research · Cited by 214
Self-citationOn Bayesian Upper Confidence Bounds for Bandit Problems
Kaufmann, E., Garivier, A., & Paristech, T. (2012) · Cited by 213
The K-armed dueling bandits problem
Yue, Y., Broder, J., Kleinberg, R., & Joachims, T. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2011.12.028 · Cited by 212
Regret Bounds and Minimax Policies under Partial Monitoring
Audibert, J.-Y., & Bubeck, S. (2010) · HAL · Cited by 210
Self-citationNear-optimal Regret Bounds for Reinforcement Learning
(2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1859902 · Cited by 207
Foster, D. (1998) · Biometrika · doi:10.1093/biomet/85.2.379 · Cited by 204
Regret bounds for sleeping experts and bandits
Kleinberg, R., Niculescu-Mizil, A., & Sharma, Y. (2010) · Machine Learning · doi:10.1007/s10994-010-5178-7 · Cited by 198
Competing in the dark: An efficient algorithm for bandit linear optimization
Abernethy, J., Hazan, E., & Rakhlin, A. (2008) · Cited by 193
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
Awerbuch, B., & Kleinberg, R. D. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007367 · Cited by 190
Pure exploration in finitely-armed and continuous-armed bandits
Bubeck, S., Munos, R., & Stoltz, G. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.12.059 · Cited by 188
Self-citationMahajan, A., & Teneketzis, D. (2008) · Foundations and Applications of Sensor Management · doi:10.1007/978-0-387-49819-5_6 · Cited by 185
Improved Rates for the Stochastic Continuum-Armed Bandit Problem
Auer, P. L., Ortner, R., & Szepesvári, C. (2007) · Springer eBooks · doi:10.1007/978-3-540-72927-3_33 · Cited by 178
Contextual Bandit Algorithms with Supervised Learning Guarantees
Beygelzimer, A., Langford, J. C., Li, L. C., Reyzin, L., & Schapire, R. E. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.4058 · Cited by 175
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
Bandit Algorithms for Tree Search
Coquelin, P.-A., & Munos, R. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.2028 · Cited by 170
Efficient Optimal Learning for Contextual Bandits
Dudı́k, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J. C., Reyzin, L., & Zhang, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1106.2369 · Cited by 170
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
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
Self-citationThe Price of Bandit Information for Online Optimization
Dani, V., Kakade, S. M., & Hayes, T. P. (2007) · ScholarlyCommons (University of Pennsylvania) · Cited by 161
Algorithms for Infinitely Many-Armed Bandits
Wang, Y., Audibert, J.-Y., & Munos, R. (2008) · Cited by 160
The multi-armed bandit problem with covariatesPreprint
Perchet, V. (n.d.) · Cited by 160
Regularization Techniques for Learning with MatricesPreprint
Kakade, S. M., Shalev‐Shwartz, S., & Tewari, A. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.0610 · Cited by 157
Improved second-order bounds for prediction with expert advice
Cesa‐Bianchi, N., Mansour, Y., & Stoltz, G. (2006) · Machine Learning · doi:10.1007/s10994-006-5001-7 · Cited by 154
Online Bandit Learning against an Adaptive Adversary: from Regret to Policy RegretPreprint
Arora, R., Dekel, O., & Tewari, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.6400 · Cited by 150
Adapting to a Changing Environment: the Brownian Restless Bandits.
Slivkins, A., & Upfal, E. (2008) · Cited by 144
An Asymptotically Optimal Bandit Algorithm for Bounded Support Models.
Honda, J., & Akimichi Takemura, Y. (2010) · Cited by 139
On the Universality of Online Mirror DescentPreprint
Srebro, N., Sridharan, K., & Tewari, A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1107.4080 · Cited by 139
Chernoff-type bound for finite Markov chains
Lezaud, P. (1998) · The Annals of Applied Probability · doi:10.1214/aoap/1028903453 · Cited by 137
Relative Loss Bounds for Multidimensional Regression Problems
Kivinen, J., & Warmuth, M. K. (2001) · Machine Learning · doi:10.1023/a:1017938623079 · 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
Online Optimization in X-Armed Bandits
Bubeck, S., Stoltz, G., Szepesvári, C., & Munos, R. (2008) · Cited by 132
Self-citationBandit problems with side observations
Wang, C.-C., Kulkarni, S. R., & Poor, H. V. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.844079 · Cited by 129
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
The price of truthfulness for pay-per-click auctions
Devanur, N. R., & Kakade, S. M. (2009) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1566374.1566388 · Cited by 121
General Convergence Results for Linear Discriminant Updates
Grove, A. J., Littlestone, N., & Schuurmans, D. (2001) · Machine Learning · doi:10.1023/a:1010844028087 · Cited by 118
Introduction to Online Optimization
Bubeck, S. (2011) · Cited by 110
Self-citationMulticlass classification with bandit feedback using adaptive regularization
Crammer, K., & Gentile, C. (2012) · Machine Learning · doi:10.1007/s10994-012-5321-8 · Cited by 109
Path Kernels and Multiplicative Updates
Takimoto, E., & Warmuth, M. K. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45435-7_6 · Cited by 103
The Convex Optimization Approach to Regret Minimization
Hazan, E. (2011) · The MIT Press eBooks · doi:10.7551/mitpress/8996.003.0012 · Cited by 98
Characterizing truthful multi-armed bandit mechanisms: extended abstract
Babaioff, M., Sharma, Y., & Slivkins, A. (2009) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1566374.1566386 · Cited by 97
Markov Decision Processes with Arbitrary Reward Processes
Yu, J. Y., Mannor, S., & Shimkin, N. (2009) · Mathematics of Operations Research · doi:10.1287/moor.1090.0397 · Cited by 96
Random gradient-free minimization of convex functionsPreprint
Nesterov, Y. E. (2011) · RePEc: Research Papers in Economics · Cited by 89
Online Markov Decision Processes under Bandit Feedback
Neu, G., Antos, A., György, A., & Szepesvári, C. (2010) · Cited by 88
Minimizing Regret With Label Efficient Prediction
Cesa‐Bianchi, N., Lugosi, G., & Stoltz, G. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.847729 · Cited by 88
Algorithms for Adversarial Bandit Problems with Multiple Plays
Taishi, U., Nakamura, A., & Kudo, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16108-7_30 · Cited by 79
Truthful mechanisms with implicit payment computation
Babaioff, M., Kleinberg, R., & Slivkins, A. (2010) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1807342.1807349 · Cited by 79
Regret and Convergence Bounds for a Class of Continuum-Armed Bandit Problems
Cope, E. W. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2019797 · Cited by 79
Recursive Aggregation of Estimators by the Mirror Descent Algorithm with Averaging
Juditsky, A., Nazin, A., Tsybakov, A. B., & Vayatis, N. (2005) · Problems of Information Transmission · doi:10.1007/s11122-006-0005-2 · Cited by 77
Learning Permutations with Exponential Weights
Helmbold, D. P., & Warmuth, M. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1755841 · Cited by 75
Bubeck, S., & Munos, R. (2010) · Cited by 68
Self-citationRegret Bounds for Gaussian Process Bandit Problems
Grünewälder, S., Berlin, T. U., Shawe-Taylor, J. S., Audibert, J.-Y., & Paris-est, U. ́. (2010) · HAL · Cited by 64
Non-Stochastic Bandit Slate Problems
Kale, S., Reyzin, L., & Schapire, R. E. (2010) · Cited by 62
Associative Reinforcement Learning using Linear Probabilistic Concepts
Abe, N., & Long, P. M. (1999) · Cited by 60
Multi-Bandit Best Arm Identification
Gabillon, V., Ghavamzadeh, M., Lazaric, A., Gabillon, V., Lazaric, R., Bubeck, S., Hal, H. I., & Lazaric, A. (2011) · Cited by 57
Self-citationCreating an Upper-Confidence-Tree Program for Havannah
Teytaud, F., & Teytaud, O. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12993-3_7 · Cited by 55
Baños, A. (1968) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177698023 · Cited by 52
Active Learning in Multi-armed Bandits
Antos, A., Grover, V., & Szepesvári, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87987-9_25 · Cited by 49
Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards
Kanade, V., McMahan, H. B., & Bryan, B. (2009) · Cited by 47
Yu, J. Y., & Mannor, S. (2011) · International Conference on Machine Learning · Cited by 43
Fast boosting using adversarial bandits
Busa‐Fekete, R., & Kégl, B. (2010) · HAL · Cited by 39
PAC-Bayesian Analysis of Contextual Bandits
Seldin, Y., Auer, P. L., Laviolette, F., et al. (2011) · MPG.PuRe (Max Planck Society) · Cited by 38
Regret Bounds for Restless Markov Bandits
Ortner, R., Ryabko, D., Auer, P. L., & Munos, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34106-9_19 · Cited by 38
Better algorithms for benign bandits
Hazan, E., & Kale, S. (2009) · doi:10.5555/1496770.1496775 · Cited by 33
Thompson Sampling: An Asymptotically Optimal Finite Time AnalysisPreprint
Kaufmann, E., Korda, N., & Munos, R. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.4217 · Cited by 33
Deviations of Stochastic Bandit Regret
Salomon, A., & Audibert, J.-Y. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24412-4_15 · Cited by 28
Continuous Time Associative Bandit Problems ∗
György, A., Kocsis, L., Szabó, I., & Szepesvári, C. (2007) · Cited by 27
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
Arbitrary side observations in bandit problems
Wang, C.-C., Kulkarni, S. R., & Poor, H. V. (2005) · Advances in Applied Mathematics · doi:10.1016/j.aam.2004.10.004 · Cited by 23
Adaptive Bandits: Towards the best history-dependent strategy
Maillard, O.-A., & Munos, R. (2011) · HAL · Cited by 22
Oracle inequalities for computationally budgeted model selection
Agarwal, A., Duchi, J. C., Bartlett, P. L., & Levrard, C. (2011) · QUT ePrints (Queensland University of Technology) · Cited by 20
Optimally Sensing a Single Channel Without Prior Information: The Tiling Algorithm and Regret Bounds
Filippi, S., Cappé, O., & Garivier, A. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2058091 · Cited by 19
Bandits, Query Learning, and the Haystack Dimension
Amin, K., Kearns, M. J., & Syed, U. (2011) · Cited by 18
Bandit-Based Genetic Programming
Hoock, J., & Teytaud, O. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12148-7_23 · Cited by 16
Deviations of Stochastic Bandit Regret
Salomon, A., Audibert, J.-Y., Paristech, E. D. P., & Est, U. ́. P. (2011) · Cited by 1
Cited by
Taking the Human Out of the Loop: A Review of Bayesian Optimization
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & de Freitas, N. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2494218 · Cited by 6,049
Introduction to Online Convex Optimization
Hazan, E. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831719 · Cited by 813
Information-seeking, curiosity, and attention: computational and neural mechanisms
Gottlieb, J., Oudeyer, P.-Y., Lopes, M., & Baranes, A. (2013) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2013.09.001 · Cited by 784
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
Metadata
- Authors
- Bubeck, S.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2012
- OpenAlex
- W2049934117
- Cited by
- 1,404
- References
- 141
- FWCI
- 29.93
- 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.