Good arm identification via bandit feedback
Open Access
- 6 March 2019
- journal article
- research article
- Published by Springer Nature in Machine Learning
- Vol. 108 (5) , 721-745
Abstract
We consider a novel stochastic multi-armed bandit problem called good arm identification (GAI), where a good arm is defined as an arm with expected reward greater than or equal to a given threshold. GAI is a pure-exploration problem in which a single agent repeats a process of outputting an arm as soon as it is identified as a good one before confirming the other arms are actually not good. The objective of GAI is to minimize the number of samples for each process. We find that GAI faces a new kind of dilemma, the exploration-exploitation dilemma of confidence, which is different from the best arm identification. As a result, an efficient design of algorithms for GAI is quite different from that for the best arm identification. We derive a lower bound on the sample complexity of GAI that is tight up to the logarithmic factor $$\mathrm {O}(\log \frac{1}{\delta })$$ for acceptance error rate $$\delta $$ . We also develop an algorithm whose sample complexity almost matches the lower bound. We also confirm experimentally that our proposed algorithm outperforms naive algorithms in synthetic settings based on a conventional bandit problem and clinical trial researches for rheumatoid arthritis.
Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (KAKENHI 17H00757, KAKENHI 16H00881)
- Core Research for Evolutional Science and Technology (JPMJCR1662)
This publication has 13 references indexed in Scilit:
- Personalized Recommendation via Parameter-Free Contextual Bandits2015
- Determining the Minimally Important Difference in the Clinical Disease Activity Index for Improvement and Worsening in Early Rheumatoid Arthritis PatientsArthritis Care & Research, 2015
- Safety, tolerability, pharmacokinetics and pharmacodynamics of an anti- oncostatin M monoclonal antibody in rheumatoid arthritis: results from phase II randomized, placebo-controlled trialsArthritis Research & Therapy, 2013
- Kullback–Leibler upper confidence bounds for optimal sequential allocationThe Annals of Statistics, 2013
- Efficacy and safety of secukinumab in patients with rheumatoid arthritis: a phase II, dose-finding, double-blind, randomised, placebo controlled studyAnnals of the Rheumatic Diseases, 2013
- The BATTLE Trial: Personalizing Therapy for Lung CancerCancer Discovery, 2011
- Integrating Techniques from Statistical Ranking into Evolutionary AlgorithmsLecture Notes in Computer Science, 2006
- ASTIN: a Bayesian adaptive dose–response trial in acute strokeClinical Trials, 2005
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- A procedure for selecting a subset of size m containing the l best of k independent normal populations, with applications to simulationCommunications in Statistics - Simulation and Computation, 1985