文献

J-GLOBAL ID：201902236076635578   整理番号：19A0418973

非対称性を利用した悪腕存在チェックアルゴリズム

Algorithms for Checking Existence of a Bad Arm Utilizing Asymmetry

著者 (3件)： 田畑公次 (北大) ,  中村篤祥 (北大) ,  小松崎民樹 (北大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 284(IBISML2018 44-104)(Web)  ページ： 353-360 (WEB ONLY)  発行年： 2018年10月29日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 損失版の多腕バンディット問題設定において,与えられた二つの閾値θ_L,θ_U(>θ_L)と許容誤識別率δに対し,平均損失がθ_Uよりも大きな腕が一つでもあれば「正」,全ての腕の平均損失がθ_Lよりも小さければ「負」と少なくとも確率1-δで出力する悪腕存在チェック問題[5]を考える。できるだけ少ない試行回数で停止するアルゴリズムの検討を行い,「正」と「負」を出力する条件の非対称性を考慮したアルゴリズムを提案する。提案アルゴリズムは,各時刻においてどの腕を選択するかを決める腕選択方策と解を出力して停止するかどうかを決める停止条件で構成される。本研究では停止時刻に関する理論的な解析を行い,また人工データを用いたシミュレーション実験により腕選択方策と停止条件の組み合わせによる平均停止時刻の分析を行う。(著者抄録)

シソーラス用語： *系統損失 ,  *損失 ,  試行錯誤学習 ,  試行 ,  アルゴリズム ,  非対称性
準シソーラス用語： *悪腕存在チェックアルゴリズム ,  *平均損失

分類 (2件)： 計算理論  (JB02000A) ,  数値計算  (JE02000J)

引用文献 (6件)：

• Kalyanakrishnan, S., Tewari, A., Auer, P., Stone, P.: PAC Subset Selection in Stochastic Multi-armed Bandits, Proceedings of the 29th International Conference on Machine Learning, pp.655-662 (2012)
• Kano, H., Honda, J., Sakamaki, K., Matsuda, K., Nakamura, A., Sugiyama, M.: Good Arm Identification via Bandit Feedback, arXiv:1710.06360 (2017)
• Kaufmann, E., Cappé, O., Garivier, A.: On the Complexity of BestArm Identification in Multi-Armed Bandit Models, Journal of Machine Learning Research, Vol. 17, No. 1, pp.1-42 (2016)
• Locatelli, A., Gutzeit, M., Carpentier, A.: An optimal algorithm for the Thresholding Bandit Problem, Proceedings of The 33rd International Conference on Machine Learning, PMLR Vol.48, pp.1690-1698 (2016)
• 中村篤祥: 悪腕存在チェック問題のアルゴリズム, 信学技報 117(110), pp.49-54 (2017)

タイトルに関連する用語 (4件)： 非対称性 ,  腕 ,  チェック ,  アルゴリズム