バンディット問題における最適性達成のためのランダム方策の発展と解析

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

本年度はバンディット問題におけるランダム方策のうち，特に敵対的バンディットとよばれる設定に対して頑健な方策の構築と解析を主に行った。敵対的バンディットとは報酬が一定の確率分布からではなく敵対者によって生成される設定で、確率的・敵対的両方の設定で同時に最適オーダーを達成する方策はBest-Of-Both-Worlds (BOBW)とよばれる。これらは敵対的設定に対応するためにランダム方策を用いることが本質的に必要となる。これらに対して、本研究では敵対的設定においても報酬の分散情報を活用可能なBOBW方策を新たに提案し、各設定に特化した方策に比べて損失が高々２倍程度で抑えられることを証明した。この結果は学習理論のトップ会議COLT2022に採録された。次に、バンディット問題を一般化した問題クラスとしてグラフフィードバック付きバンディットや部分観測問題とよばれる設定が知られている。本研究ではこれらの設定に対して「最適化による探索」とよばれる近年別の文脈で知られるようになった手法を取り入れることでBOBW方策を新たに構成した。この結果は機械学習のトップ会議NeurIPS2022および学習理論のトップ会議ALT2023に採録された。上記のBOBW方策はいずれもランダム選択の確率分布を時刻ごとに最適化計算によって求める必要があった。これに対して、最適化計算の不要なランダム方策であるFollow-The-Perturbed-Leader (FTPL)がBOBW性を達成可能であるかは長年未解決であったが、本研究では対称多項式に関する代数的な手法を用いることでこの問題を肯定的に解決した。この結果はALT2023に採録された。その他、最適腕識別とよばれる設定に対してランダム方策を含む一般の方策に対する理論限界を新たに構築した。この結果はNeurIPS2022に採録された。