| 講演名 | 2017-06-24 悪腕存在チェック問題のアルゴリズム 中村 篤祥(北大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 確率的$K$腕バンディット問題の設定で，期待報酬が閾値以上のものが存在するか否かをできる限り少ないプレイ回数で判定するtextbf{悪腕存在チェック問題}を考える．これは，$K$個の検査対象物の内１個でも異常なものがないかを，できるだけ少ない検査回数で判定する問題を定式化したものである．本稿では，まず，与えられたスロットマシン１台に対し，期待報酬が閾値以上であるか否かを判定するtextbf{腕識別問題}を考え，アルゴリズムを与えサンプル複雑度(プレイ回数)の上界を示す．悪腕存在チェック問題に関しては，腕識別問題のアルゴリズムをサブルーチンとして用いる逐次削除アルゴリズムと逐次検査アルゴリズムを示し，各々のサンプル複雑度の上界を示す． |
| 抄録(英) | 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. |
| キーワード(和) | バンディット問題 / 最適腕識別 |
| キーワード(英) | bandit problem / best arm identification |
| 資料番号 | IBISML2017-2 |
| 発行日 | 2017-06-17 (IBISML) |
| 研究会情報 | |
| 研究会 | NC / IPSJ-BIO / IBISML / IPSJ-MPS |
|---|---|
| 開催期間 | 2017/6/23(から3日開催) |
| 開催地（和） | 沖縄科学技術大学院大学 |
| 開催地（英） | Okinawa Institute of Science and Technology |
| テーマ（和） | 機械学習によるバイオデータマインニング、一般 |
| テーマ（英） | Machine Learning Approach to Biodata Mining, and General |
| 委員長氏名（和） | 萩原 将文(慶大) / / 福水 健次(統計数理研) |
| 委員長氏名（英） | Masafumi Hagiwara(Keio Univ.) / / Kenji Fukumizu(ISM) |
| 副委員長氏名（和） | 平田 豊(中部大) / / 杉山 将(東大) |
| 副委員長氏名（英） | Yutaka Hirata(Chubu Univ.) / / Masashi Sugiyama(Univ. of Tokyo) |
| 幹事氏名（和） | 青西 亨(東工大) / 吉川 大弘(名大) / / 鹿島 久嗣(京大) / 津田 宏治(東大) |
| 幹事氏名（英） | Toru Aonishi(Tokyo Inst. of Tech.) / Tomohiro Yoshikawa(Nagoya Univ.) / / Hisashi Kashima(Kyoto Univ.) / Koji Tsuda(Univ. of Tokyo) |
| 幹事補佐氏名（和） | 篠沢 佳久(慶大) / 稲垣 圭一郎(中部大) / / 竹内 一郎(名工大) / 神嶌 敏弘(産総研) |
| 幹事補佐氏名（英） | Yoshihisa Shinozawa(Keio Univ.) / Keiichiro Inagaki(Chubu Univ.) / / Ichiro Takeuchi(Nagoya Inst. of Tech.) / Toshihiro Kamishima(AIST) |
| 講演論文情報詳細 | |
| 申込み研究会 | 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 |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 悪腕存在チェック問題のアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithms for Bad Arm Existence Checking Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | バンディット問題 / bandit problem |
| キーワード(2)（和/英） | 最適腕識別 / best arm identification |
| 第 1 著者 氏名（和/英） | 中村 篤祥 / Atsuyoshi Nakamura |
| 第 1 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 発表年月日 | 2017-06-24 |
| 資料番号 | IBISML2017-2 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | IBISML-110 |
| ページ範囲 | pp.49-54(IBISML), |
| ページ数 | 6 |
| 発行日 | 2017-06-17 (IBISML) |