ロックアップ期間による制約を考慮した確率的バンディット問題

概要

論文の詳細を見る
バンディット問題は,複数のアーム (選択肢) から最も報酬の高いものを探す問題であり,探索と活用のトレードオフの代表的なモデルの1つである.近年において,情報推薦,最適経路探索,最適化,モデル選択などの分野への応用を動機として,バンディット問題は機械学習やオペレーション・リサーチの分野において注目を浴びている.本稿はロックアップ期間 (選択するアームを変更できない期間) の制約を考慮したバンディット問題を提案し,どのような方策を取れば良いかを調べる.既存の多くの有益なアルゴリズムがロックアップ期間を含めた場合に自然に拡張可能であることを示し,その regret (性能) を評価する.この regret がロックアップ期間の最大の大きさに依存することを示す.さらに,ロックアップ期間が大きい場合に regret を減らすことができる Balancing and Recommendation (BaR) メタアルゴリズムを提案する.また,計算機実験の結果を示し,理論的な結果と比較し考察する.
2013-02-20