| Presentation | 2017-06-24 Algorithms for Bad Arm Existence Checking Problem Atsuyoshi Nakamura, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We study a bad arm existence checking problem, in which a solver algorithm must judge whether an arm with an expected reward at least a given threshold exists or not by drawing as small number of arms as possible in the framework of stochastic $K$-armed bandit problem. This is a formalization of the checking problem for the existence of a bad object among $K$ objects. In this manuscript, we first consider a simpler problem called an arm discrimination problem whose solver algorithm must discriminate whether a given slot machine has an expected reward at least a given threshold or not by drawing as small number of arms as possible. We give an algorithm for this problem and show an upper bound of the sample complexity (the number of arm draws). We construct a successive elimination algorithm and a successive checking algorithm that make use of the algorithm for the arm discrimination problem as a subroutine, and also show the sample complexity upper bounds of those algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | bandit problem / best arm identification |
| Paper # | IBISML2017-2 |
| Date of Issue | 2017-06-17 (IBISML) |
| Conference Information | |
| Committee | NC / IPSJ-BIO / IBISML / IPSJ-MPS |
|---|---|
| Conference Date | 2017/6/23(3days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Okinawa Institute of Science and Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Machine Learning Approach to Biodata Mining, and General |
| Chair | Masafumi Hagiwara(Keio Univ.) / / Kenji Fukumizu(ISM) |
| Vice Chair | Yutaka Hirata(Chubu Univ.) / / Masashi Sugiyama(Univ. of Tokyo) |
| Secretary | Yutaka Hirata(Tokyo Inst. of Tech.) / (Nagoya Univ.) / Masashi Sugiyama / (Kyoto Univ.) |
| Assistant | Yoshihisa Shinozawa(Keio Univ.) / Keiichiro Inagaki(Chubu Univ.) / / Ichiro Takeuchi(Nagoya Inst. of Tech.) / Toshihiro Kamishima(AIST) |
| Paper Information | |
| Registration To | Technical Committee on Neurocomputing / Special Interest Group on Bioinformatics and Genomics / Technical Committee on Infomation-Based Induction Sciences and Machine Learning / Special Interest Group on Mathematical Modeling and Problem Solving |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Algorithms for Bad Arm Existence Checking Problem |
| Sub Title (in English) | |
| Keyword(1) | bandit problem |
| Keyword(2) | best arm identification |
| 1st Author's Name | Atsuyoshi Nakamura |
| 1st Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| Date | 2017-06-24 |
| Paper # | IBISML2017-2 |
| Volume (vol) | vol.117 |
| Number (no) | IBISML-110 |
| Page | pp.pp.49-54(IBISML), |
| #Pages | 6 |
| Date of Issue | 2017-06-17 (IBISML) |