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

• Item type: Trans(1)
• 公開日: 2013-12-27
• タイトル: ロックアップ期間による制約を考慮した確率的バンディット問題
• タイトル / 言語: en
• タイトル: Multi-armed Bandit Problem with Lock-up Periods
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] バンディット問題，多腕バンディット，逐次最適化，確率的最適化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者名: 小宮山, 純平; 佐藤, 一誠; 中川, 裕志
• 著者名(英): Junpei, Komiyama; Issei, Sato; Hiroshi, Nakagawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: バンディット問題は，複数のアーム（選択肢）から最も報酬の高いものを探す問題であり，探索と活用のトレードオフの代表的なモデルの1つである．近年において，情報推薦，最適経路探索，最適化，モデル選択などの分野への応用を動機として，バンディット問題は機械学習やオペレーション・リサーチの分野において注目を浴びている．本研究はロックアップ期間（選択するアームを変更できない期間）の制約を考慮したバンディット問題を提案し，どのような方策をとればよいかを調べる．既存の多くの有益なアルゴリズムがロックアップ期間を含めた場合に自然に拡張可能であることを示し，そのregret（性能）を評価する．このregretがロックアップ期間の最大の大きさに依存することを示す．さらに，ロックアップ期間が大きい場合にregretを減らすことができるBalancing and Recommendation（BaR）メタアルゴリズムを提案する．また，計算機実験の結果を示し，理論的な結果と比較し考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The multi-armed bandit problem, which is widely used to model sequential decision making, has recently attracted much attention. Motivated by actual applications, we propose a version of the multi-armed bandit problem in which the forecaster's choice is restricted. In this problem, rounds are divided into lock-up periods and the forecaster must select the same arm throughout a period. While there has been much works on finding optimal algorithms for the stochastic multi-armed bandit problem, their use under restricted conditions is not obvious. We extend the application ranges of these algorithms by proposing their natural conversion from ones for the stochastic bandit problem to ones for the multi-armed bandit problem with lock-up periods. We prove that the regret of the converted algorithms is O(logT + Lmax), where T is the total number of rounds and Lmax is the maximum size of the lock-up periods. The regret is preferable, except for the case when the maximum size of the lock-up periods is large. For this cases, we propose a meta-algorithm that results in a smaller regret by using a empirical best arm for large periods. We empirically compare and discuss these algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 6, 号 3, p. 11-22, 発行日 2013-12-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会