Designing a Practical Algorithm for Linear Bandits

点击翻译按钮获取中文摘要

本年度の研究では，ノイズなどにより背後にあるモデルが仮定したモデルと異なる場合においても頑健に動くバンディットアルゴリズムの構築を目指して研究をおこなった．バンディット問題には，各アームの報酬が定常な確率分布に従う確率的バンディットの設定の他に，各アームの報酬が各時刻で有界な任意の値をとる敵対的バンディットと呼ばれる設定がある．確率的環境を仮定するのは非常に条件が強く，現実的な利用場面では，観測にノイズがのる，背後の分布が時刻変化する，などの要因によりこの仮定が満たされないことが多い．実際に，確率的環境に特化したアルゴリズムは，このような設定で性能が大きく低下することがあることが，理論的及び実験的に知られている．一方で，敵対的環境を仮定したアルゴリズムは，非常に悲観的に動作し，簡単な問題において，性能が実用的ではない場合が多い．これらの問題を解決するために近年Tsallis-INF アルゴリズムが考案された．Tsallis-INF アルゴリズムは，確率的環境と敵対的環境の両方で最適性を達成するアルゴリズムである．しかし，どのような条件下でアルゴリズムが確率的環境で良い性能を持ちつつ敵対的環境においても頑健に動作するのかについては十分知られていない．そこで，本年度の研究では，確率的環境において各アームの推定期待報酬を，確率的微分方程式の枠組みで定式化することで，アルゴリズムが頑健であるための条件の調査をおこなった．具体的には，単純化したTsallis-INFアルゴリズムに対して，対応する確率微分方程式を考えた．それを用いて，理論的側面からの解析をおこない，この単純化された設定では，各アームの推定期待報酬が特定の分布に分布収束し，結果として試行回数の意味での最適オーダを達成できることを確認できた．