多腕バンディット問題における最適戦略の構成と発展

本研究は，知識の探索と活用のジレンマをモデル化したものである多腕バンディット問題において，達成可能な効率の理論限界を探り，またその理論限界を達成する戦略を具体的に構成することを目標に行った．この問題は古くから知られており，特に近年ではウェブ上の広告表示やネットワークルーティングといった問題に直接応用できることから盛んに研究されているが，一方，従来研究で提案された戦略でその最適性が保証されているのは一部の非常に単純な確率分布モデルに限られていた．そこで本年度の研究においては，報酬のサポートの下限のみが既知という極めて一般的なノンパラメトリックモデルにおける理論限界を導出し，さらにそれを達成する戦略の提案を行った．これまでに理論限界の達成可能性が知られていたのは確率分布のパラメータ空間が１次元あるいはコンパクトな場合に限られており，それらの手法を無限次元かつ非コンパクトである今回のモデルに直接適用するのは困難であったが，本研究ではダイバージェンス最小化の双対問題を経由して１次元モデルに近い問題への帰着を行うことにより証明を行った．さらに，従来示されていた漸近最適戦略は，プレイ回数nに対する損失のうちO(log n)の項までの意味では最適であったが，それより高次の項がo(log n)ではあるものの無限大に発散するものであった．一方，この高次項はO(1)とできることが様々な研究から実験的には示唆されており，この点で従来の理論研究と実験の間にはギャップがあった．そこで，本研究では確率過程の理論のうちマルチンゲールの停止時刻に関する結果を応用することで，O(1)の損失が達成可能であることを新たに示した．この研究の結果は機械学習の論文誌Journal of Machine Learning Researchに現在投稿中である．

本研究は，知識の探索と活用のジレンマをモデル化したものである多腕バンディット問題において，達成可能な効率の理論限界を探り，またその理論限界を達成する戦略を具体的に構成することを目標に行った．この問題は古くから知られており，特に近年ではウェブ上の広告表示やネットワークルーティングといった問題に直接応用できることから盛んに研究されているが，一方，従来研究で提案された戦略でその最適性が保証されているのは一部の非常に単純な確率分布モデルに限られていた．そこで本年度の研究においては，報酬のサポートの下限のみが既知という極めて一般的なノンパラメトリックモデルにおける理論限界を導出し，さらにそれを達成する戦略の提案を行った．これまでに理論限界の達成可能性が知られていたのは確率分布のパラメータ空間が１次元あるいはコンパクトな場合に限られており，それらの手法を無限次元かつ非コンパクトである今回のモデルに直接適用するのは困難であったが，本研究ではダイバージェンス最小化の双対問題を経由して１次元モデルに近い問題への帰着を行うことにより証明を行った．さらに，従来示されていた漸近最適戦略は，プレイ回数nに対する損失のうちO(log n)の項までの意味では最適であったが，それより高次の項がo(log n)ではあるものの無限大に発散するものであった．一方，この高次項はO(1)とできることが様々な研究から実験的には示唆されており，この点で従来の理論研究と実験の間にはギャップがあった．そこで，本研究では確率過程の理論のうちマルチンゲールの停止時刻に関する結果を応用することで，O(1)の損失が達成可能であることを新たに示した．この研究の結果は機械学習の論文誌Journal of Machine Learning Researchに現在投稿中である．