バンディット問題においてFTPLというランダムノイズを用いた最適化計算が不要の方策クラスにおいて
幅広い一般のフレシェ型分布を用いることで両環境最適性を達成可能であることを示した論文、ならびに、
FTRLという方策クラスで競合比解析を用いることで学習率を適応的に設計する手法を構築した論文が
学習理論の国際会議 Conference on Machine Learning (COLT) に採択されました。
フレシェ型とは統計学で古くから知られた確率分布クラスであり、FTPL方策が両環境最適性を達成可能となるのは
ノイズにフレシェ型分布を用いた場合という予想が以前から知られていました。
最近我々のグループはフレシェ分布によるFTPLが両環境最適性を達成することを示すことでこの予想を解決しましたが、
これはフレシェ分布の分布形に特化した解析をしており、本研究は統計学における極値分布の各種理論を用いることで
FTPLの両環境最適性が一般的なフレシェ型分布に拡張できることを示しました。
Jongyeong Lee, Junya Honda, Shinji Ito, Min-hwan Oh, "Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds", The 37th Annual Conference on Learning Theory (COLT 2024), 2024.
FTRLではデータに応じて適応的に学習率を変化させることで多くの問題クラスで両環境最適性が達成可能なことが知られていましたが、
本研究はそれを最適化する汎用的な枠組みを導出し、それにより多くのクラスで汎用的かつ優れた理論保証を達成可能とできることを示しました。
Shinji Ito, Taira Tsuchiya, Junya Honda, "Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Ratio Analysis and Best-of-Both-Worlds", The 37th Annual Conference on Learning Theory (COLT 2024), 2024.