バンディット問題において観測情報のプライバシーを保護するための最適方策を構成した論文、報酬期待値最大の候補でなく報酬期待値の最大値そのものを探索する最適方策を構成した論文、ならびにバンディット問題における方策クラスであるFTPLについてその最適性の達成可能性の限界を議論した論文がNeurIPS 2025に採択されました。
医療データなど秘密性の高いデータを用いた意思決定では選んだ行動から元データが推測できないことが重要となり、このような問題は差分プライバシー制約つきバンディット問題として多く研究されています。この問題では達成可能な性能の理論限界と実際のアルゴリズムの性能に大きなギャップがありましたが、本研究では初めて精密な理論限界とそれを漸近的に達成するアルゴリズムを構築し、これが現実の試行回数でも大幅に性能を改善することを示しました。
Achraf Azize, Yulian Wu, Junya Honda, Francesco Orabona, Shinji Ito, Debabrota Basu, "Optimal Regret of Bandits under Differential Privacy", The 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025), San Diego, USA, Dec. 2-7, 2025.
バンディット問題の枠組みにおいては報酬期待値が最大となる選択肢を探索する問題が非常に多く研究されていますが、AIシステムの品質保証やメカニズムデザインの分野では最適候補そのものの探索は不要で最大期待値のみの推定が必要となる場合があります。本研究ではこのような問題の理論限界が非凸最適化問題として表されることを示し、それを達成する高速なアルゴリズムを提案しました。
Takayuki Osogami, Junya Honda, Junpei Komiyama, "Optimal Estimation of the Best Mean in Multi-Armed Bandits", The 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025), San Diego, USA, Dec. 2-7, 2025.
FTPLは最適化計算を行わず効率的に実行可能な方策であり、これまでランダムノイズとして非負値をとるほとんどのフレシェ型分布に対して両環境最適性とよばれる良い性質が達成可能であることが示されてきました。これに対して本研究では実数値全体をとるフレシェ型分布によるFTPLを考え、これが他の標準的な方策からのアナロジーなどから自然に現れるにも関わらず両環境最適性に重要となる性質を満たさないことを明らかにしました。また、裾が左右非対称な減衰速度のノイズ分布を用いると両環境最適性が達成可能となることを示し、FTPLにおいてノイズ分布の左右の裾の両方を考える重要性を明らかにしました。
Jongyeong Lee, Junya Honda, Shinji Ito, Min-hwan Oh, "Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems", The 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025), San Diego, USA, Dec. 2-7, 2025.