Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models

REFERENCES

• Audibert, J.-Y., S. Bubeck, and R. Munos. 2010. “Best Arm Identification in Multi-Armed Bandits.” In Proceedings of the 23rd Conference on Learning Theory.
   Google Scholar
• Bubeck, S., and N. Cesa-Bianchi. 2012. “Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems.” Foundations and Trends® in Machine Learning 5 (1):1–122.
   Google Scholar
• Cappé, O., A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. 2013. “Kullback-Leibler Upper Confidence Bounds for Optimal Sequential Allocation.” The Annals of Statistics 41 (3):1516–41.
   Web of Science ®Google Scholar
• Chernoff, H. 1959. “Sequential Design of Experiments.” The Annals of Mathematical Statistics 30 (3):755–70.
   Google Scholar
• Degenne, R., and W. M. Koolen. 2019. “Pure Exploration with Multiple Correct Answers.” In Advances in Neural Information Processing Systems (NeurIPS).
   Google Scholar
• Even-Dar, E.,. S. Mannor, and Y. Mansour. 2006. “Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems.” Journal of Machine Learning Research 7:1079–105.
   Web of Science ®Google Scholar
• Gabillon, V., M. Ghavamzadeh, and A. Lazaric. 2012. “Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence.” In Advances in Neural Information Processing Systems.
   Google Scholar
• Garivier, A., and E. Kaufmann. 2016. “Optimal Best Arm Identification with Fixed Confidence.” In Proceedings of the 29th Conference on Learning Theory.
   Google Scholar
• Garivier, A., P. Ménard, and G. Stoltz. 2019. “Explore First, Exploit Next: The True Shape of Regret in Bandit Problems.” Mathematics of Operations Research 44 (2):377–99.
   Web of Science ®Google Scholar
• Juneja, S., and S. Krishnasamy. 2019. “Sample Complexity of Partition Identification Using Multi-Armed Bandits.” In Proceedings of the 32nd Conference on Learning Theory.
   Google Scholar
• Kaufmann, E., and S. Kalyanakrishnan. 2013. “Information Complexity in Bandit Subset Selection.” In Proceeding of the 26th Conference on Learning Theory.
   Google Scholar
• Kaufmann, E., and W. Koolen. 2018. Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals. arXiv:1811.11419.
   Google Scholar
• Kaufmann, E., W. Koolen, and A. Garivier. 2018. “Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling.” In Advances in Neural Information Processing Systems (NeurIPS).
   Google Scholar
• Kim, S., and B. L. Nelson. 2001. “A Fully Sequential Procedure for Indifference-Zone Selection in Simulation.” ACM Transactions on Modeling and Computer Simulation 11 (3):251–73.
   Google Scholar
• Lai, T. 1988. “Boundary Crossing Problems for Samples Means.” The Annals of Probability 16 (1):375–96.
   Web of Science ®Google Scholar
• Lai, T., and H. Robbins. 1985. “Asymptotically Efficient Adaptive Allocation Rules.” Advances in Applied Mathematics 6 (1):4–22.
   Web of Science ®Google Scholar
• Mannor, S., and J. Tsitsiklis. 2004. “The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.” Journal of Machine Learning Research 5:623–48.
   Web of Science ®Google Scholar
• Robbins, H. 1952. “Some Aspects of the Sequential Design of Experiments.” Bulletin of the American Mathematical Society 58 (5):527–35.
   Web of Science ®Google Scholar
• Robbins, H., and D. Siegmund. 1974. “The Expected Sample Size of Some Tests of Power One.” The Annals of Statistics 2 (3):415–36.
   Web of Science ®Google Scholar
• Russo, D. 2016. “Simple Bayesian Algorithms for Best Arm Identification.” In Proceedings of the 29th Conference on Learning Theory.
   Google Scholar
• Tsybakov, A. B. 2008. Introduction to Nonparametric Estimation. 1st ed. New York: Springer Publishing Company, Incorporated.
   Google Scholar
• Wald, A. 1945. “Sequential Tests of Statistical Hypotheses.” The Annals of Mathematical Statistics 16 (2):117–86.
   Google Scholar
• Wilks, S. 1938. “The Large-Sample Distribution of the Likelihood Ratio for Testing Composite Hypotheses.” The Annals of Mathematical Statistics 9 (1):60–2.
   Google Scholar