The DOI matches its OpenAlex record; 27 of the 27 references it cites were found in a registry or an index.
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
Open accessAbstract
The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identifying the m best arms. We introduce generic notions of complexity for the two dominant frameworks considered in the literature: fixed-budget and fixed-confidence settings. In the fixed-confidence setting, we provide the first known distribution-dependent lower bound on the complexity that involves information-theoretic quantities and holds when m is larger than 1 under general assumptions. In the specific case of two armed-bandits, we derive refined lower bounds in both the fixed-confidence and fixed-budget settings, along with matching algorithms for Gaussian and Bernoulli bandit models. These results show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-confidence setting, contradicting the familiar behavior observed when testing fully specified alternatives. In addition, we also provide improved sequential stopping rules that have guaranteed error probabilities and shorter average running times. The proofs rely on two technical results that are of independent interest : a deviation lemma for self-normalized sums (Lemma 19) and a novel change of measure inequality for bandit models (Lemma 1).
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
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
THOMPSON, W. R. (1933) · Biometrika · doi:10.1093/biomet/25.3-4.285 · Cited by 2,712
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
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
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Sequential Tests of Statistical Hypotheses
Wald, A. (1992) · Springer Series in Statistics · doi:10.1007/978-1-4612-0919-5_18 · Cited by 1,345
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
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
Best Arm Identification in Multi-Armed Bandits
Audibert, J.-Y., Bubeck, S., & Munos, R. (2010) · HAL · Cited by 446
On Bayesian Upper Confidence Bounds for Bandit Problems
Kaufmann, E., Garivier, A., & Paristech, T. (2012) · HAL · Cited by 440
Self-citationThompson 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
Self-citationThe Sample Complexity of Exploration in the Multi-Armed Bandit Problem
Mannor, S., & Tsitsiklis, J. N. (2004) · doi:10.5555/1005332.1005355 · Cited by 307
Further Optimal Regret Bounds for Thompson Sampling
Agrawal, S., & Goyal, N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.3353 · Cited by 287
Almost Optimal Exploration in Multi-Armed Bandits
Karnin, Z. S., Koren, T., & Somekh, O. (2013) · Cited by 274
Statistical Methods Related to the Law of the Iterated Logarithm
Robbins, H. (1970) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177696786 · Cited by 245
lil' UCB : An Optimal Exploration Algorithm for Multi-Armed BanditsPreprint
Jamieson, K., Malloy, M., Nowak, R. D., & Bubeck, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.7308 · Cited by 230
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
PAC Subset Selection in Stochastic Multi-armed Bandits
Kalyanakrishnan, S., Tewari, A., Auer, P. L., & Stone, P. (2012) · Cited by 204
The Racing Algorithm: Model Selection for Lazy Learners
Maron, O., & Moore, A. W. (1997) · Artificial Intelligence Review · doi:10.1023/a:1006556606079 · Cited by 198
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
Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence
Gabillon, V., Ghavamzadeh, M., Lazaric, A., Lazaric, A., & Lazaric, R. (2012) · Cited by 144
Hoeffding and Bernstein races for selecting policies in evolutionary direct policy search
Heidrich-Meisner, V., & Igel, C. (2009) · International Conference on Machine Learning · doi:10.1145/1553374.1553426 · Cited by 126
Information Complexity in Bandit Subset Selection
Kaufmann, E., & Kalyanakrishnan, S. (2013) · Cited by 113
Self-citationAn asymptotically optimal policy for finite support models in the multiarmed bandit problem
Honda, J., & Akimichi Takemura, Y. (2011) · Machine Learning · doi:10.1007/s10994-011-5257-4 · Cited by 102
Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit ProblemsPreprint
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.2670 · Cited by 76
Bounded regret in stochastic multi-armed banditsPreprint
Bubeck, S., Perchet, V., & Rigollet, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.1611 · Cited by 54
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
Self-citation
Cited by
Sagi, O., & Rokach, L. (2018) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1249 · Cited by 3,103
All you need to know about model predictive control for buildings
Drgoňa, J., Arroyo, J., Cupeiro Figueroa, I., Blum, D., Arendt, K., Kim, D., Ollé, E. P., Oravec, J., Wetter, M., Vrabie, D. L., et al. (2020) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2020.09.001 · Cited by 1,020
Machine Learning Testing: Survey, Landscapes and Horizons
Zhang, J. M., Harman, M., Ma, L., & Liu, Y. (2022) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2019.2962027 · Cited by 897
A tutorial on kernel density estimation and recent advances
Chen, Y.-C. (2017) · Biostatistics & Epidemiology · doi:10.1080/24709360.2017.1396742 · Cited by 830
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Metadata
- Authors
- Kaufmann, E., Cappé, O., & Garivier, A.
- Venue
- arXiv (Cornell University)
- Publisher
- arXiv
- Published
- 2014
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1407.4443
- OpenAlex
- W1506859583
- Cited by
- 661
- References
- 27
- Type
- posted content
- Language
- en
- Open access
- green
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.