著者

三宅 悠介 栗林 健太郎

雑誌

インターネットと運用技術シンポジウム論文集

巻号頁・発行日

vol.2020, pp.1-8, 2020-11-26

---

多腕バンディット問題は,腕と呼ばれる複数の候補から得られる報酬を最大化する問題である.同問題の Web サービスにおける広告配信や推薦システムへの応用では,腕となる利用者の嗜好傾向が多様である課題に対処するため,利用者の文脈を考慮した線形な問題設定への拡張と解法が提案されている.一方で,時間の経過に従い報酬分布が変化する非定常な課題に対処するため,変化検出の手法を組み合わせ報酬の変化を観察することで変化に追従する解法が提案されている.しかしながら,線形な問題設定にこの解法を適用する場合,文脈の増加に伴い各文脈での報酬の観測回数が低下するため,文脈ごとに報酬の変化を観測する方式では,変化の検出と追従が遅れてしまう.加えて,変化の検出と追従に必要な文脈ごとの報酬の履歴データのサイズも文脈の増加に伴い肥大化する.本研究では,多様な文脈であっても腕の報酬分布の変化に迅速に追従可能な,線形かつ非定常な多腕バンディット問題の解法を提案する.提案手法では,文脈ごとの報酬からではなく,文脈の数によらない固定数の値の推移のみから報酬分布の変化を検出することで,腕の報酬分布の変化に迅速に追従する.さらに,過去期間の値を要約するデータ構造を導入することで,報酬分布の変化検出と追従に必要な履歴データのサイズの肥大化を抑制する.評価では,線形かつ非定常な多腕バンディット問題を設定し,提案手法を用いない場合と比較して変化への追従性が高いこと,履歴データのサイズの肥大化が抑えられることを確認した.