2024-03-29T17:02:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001424832024-03-29T05:26:34Z01164:05352:08218:08281
比較バンディット問題における最適なアルゴリズム~ランキング手法比較や選好情報学習を目的として~Optimal Algorithms in Dueling Bandit Problemjpnhttp://id.nii.ac.jp/1001/00142419/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=142483&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.東京大学東京大学京都大学東京大学小宮山, 純平本多, 淳也鹿島, 久嗣中川, 裕志バンディット問題 (multi-armed bandit problem) は,情報の活用と探索の間のトレードオフをモデル化した問題である.バンディット問題にはいくつかの亜種があるが,そのうち比較バンデイット問題 (dueling bandit problem) と呼ばれるものは,一対比較によるフィードバックを用いて最適化を行う.比較バンディット問題の枠組みを用いることによって,検索エンジンのランキング手法の比較や,人間の選好抽出の問題に対して,効率的な最適化を行うことができる.本研究では,比較バンディット問題における理論的な性能限界およびそれを達成するアルゴリズムを提案する.このアルゴリズムは,経験尤度を用いた通常のバンディット問題におけるアルゴリズム (本多,竹村,2010) の比較バンデイット問題への拡張である.提案手法を評価するため,検索エンジンの実データにおけるランキング手法の比較や,寿司データセット (神嶌,2003) などによる人間の選好抽出における性能を既存手法と比較する.We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. Algorithms that are inspired by the Deterministic Minimum Empirical Divergence algorithm (Honda and Takemura, 2010) are proposed. The proposed algorithms are found to have a regret upper bound that matches the lower bound. Experimental comparisons of dueling bandit algorithms show that the proposed algorithms significantly outperform existing ones.AA12055912研究報告バイオ情報学(BIO)2015-BIO-4214182015-06-162188-85902015-06-12