2024-03-29T22:30:48Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000904292024-03-29T05:26:34Z01164:02735:07088:07089
ロックアップ期間による制約を考慮した確率的バンディット問題Multi-armed bandit problem with restricted selectionsjpnhttp://id.nii.ac.jp/1001/00090412/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=90429&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan東京大学東京大学東京大学小宮山, 純平佐藤, 一誠中川, 裕志バンディット問題は,複数のアーム (選択肢) から最も報酬の高いものを探す問題であり,探索と活用のトレードオフの代表的なモデルの1つである.近年において,情報推薦,最適経路探索,最適化,モデル選択などの分野への応用を動機として,バンディット問題は機械学習やオペレーション・リサーチの分野において注目を浴びている.本稿はロックアップ期間 (選択するアームを変更できない期間) の制約を考慮したバンディット問題を提案し,どのような方策を取れば良いかを調べる.既存の多くの有益なアルゴリズムがロックアップ期間を含めた場合に自然に拡張可能であることを示し,その regret (性能) を評価する.この regret がロックアップ期間の最大の大きさに依存することを示す.さらに,ロックアップ期間が大きい場合に regret を減らすことができる Balancing and Recommendation (BaR) メタアルゴリズムを提案する.また,計算機実験の結果を示し,理論的な結果と比較し考察する.The multi-armed bandit problem, which is widely used to model sequential decision making, has recently attracted much attention, which has led to proposals for a wide range of apprications, such as recommendation, adaptive routing, optimization, tree search, and model selection. In actual applications, the choice of the forecaster is often restricted. This paper aims to model this restriction. The results of both theoretical analysis and empirical evaluation are presented.AN10505667研究報告数理モデル化と問題解決(MPS)2013-MPS-9210162013-02-202013-02-15