統計学輪講 第9回

多腕バンディット問題を含むバンディット問題は、試行ごとに選択肢の中から一つを選び、対応する報酬を観測することで意思決定を行う枠組みであり、機械学習や意思決定理論において広く研究されてきた。従来の研究では、確率分布と独立同分布（i.i.d.）を仮定する確率的環境モデルと、より一般に非定常性や任意の報酬系列を含む敵対的環境モデルが独立に検討され、それぞれに特化したアルゴリズムが設計されてきた。特に、確率的環境用のアルゴリズムは敵対的環境では機能しないことが知られており、したがって実用上は環境についての事前知識を必要とする点が課題とされてきた。

一方、Follow-the-Regularized-Leader（FTRL）に代表されるオンライン凸最適化に基づくアプローチは、もともと敵対的環境モデルに対して発展してきたが、近年では確率的環境においても有効であり、事前に環境の性質を知らなくとも両者に対して最適な性能を達成できる枠組みとして注目されている。また、このアプローチは確率的・敵対的といった典型的な環境の中間的な設定においても良好な性能を示すことが示唆されている。

本発表では、このアプローチの代表例であるTsallis-INF方策[1]を紹介し、その原理と性能保証について概説する。さらに、これを線形バンディット問題などのより一般的な設定へと拡張する手法[2]についても解説する。

[1] Zimmert, J., & Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.

[2] Ito, S., Tsuchiya, T., & Honda, J. (2024). Adaptive learning rate for follow-the-regularized-leader: Competitive analysis and best-of-both-worlds. In The Thirty Seventh Annual Conference on Learning Theory (pp. 2522-2563). PMLR.