Good arm identification via bandit feedback

DOI10.1007/S10994-019-05784-4zbMATH Open1491.68160arXiv1710.06360OpenAlexW2962902250WikidataQ128264264 ScholiaQ128264264MaRDI QIDQ2425222FDOQ2425222

Authors: Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, Masashi Sugiyama 

Publication date: 26 June 2019

Published in: Machine Learning (Search for Journal in Brave)

Abstract: We consider a novel stochastic multi-armed bandit problem called {em 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 that 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 {em exploration-exploitation dilemma of confidence}, which is different difficulty 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 $mathrmO(logfrac1delta)$ 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.

Full work available at URL: https://arxiv.org/abs/1710.06360

Recommendations

• On the complexity of best-arm identification in multi-armed bandit models
• Lower bounds on the sample complexity of exploration in the multi-armed bandit problem.
• Pure exploration in infinitely-armed bandit models with fixed-confidence
• The sample complexity of exploration in the multi-armed bandit problem
• Multi-armed bandits with simple arms

zbMATH Keywords

machine learningreinforcement learningmulti-armed banditsthresholding bandits

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• On the complexity of best-arm identification in multi-armed bandit models
• Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
• Asymptotically efficient adaptive allocation rules
• Finite-time analysis of the multiarmed bandit problem
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Reinforcement learning. An introduction
• A procedure for selecting a subset of size m containing the l best of k independent normal populations, with applications to simulation

Cited In (7)

• On the complexity of best-arm identification in multi-armed bandit models
• Pure exploration in infinitely-armed bandit models with fixed-confidence
• Best arm identification for contaminated bandits
• Best arm identification in generalized linear bandits
• Secure best arm identification in multi-armed bandits
• A bad arm existence checking problem: how to utilize asymmetric problem structure?
• A PAC algorithm in relative precision for bandit problem with costly sampling

This page was built for publication: Good arm identification via bandit feedback

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425222)