両立の妙：確率的・敵対的ベストアーム同定

arXiv stat.ML / 2026/4/17

📰 ニュースModels & Research

共有:

要点

本論文は、報酬が確率的である場合も敵対的である場合もあり得る状況での、多腕バンディットによる「ベストアーム同定」を扱います。
ランダム一様戦略は敵対的（adversarial）報酬のもとでは最適な誤り率を達成しますが、確率的報酬では最適ではありません。
著者らは、報酬がどちらのモデルかを知らないまま、両設定で最適な誤り率を同時に達成する学習器を一般には構成できないことを示します。
敵対的報酬に対するロバスト性を制約として課したときに、確率的問題で達成可能な最良の誤り率を特徴づける下限を導出します。
さらに、パラメータ不要の簡単なアルゴリズムを提案し、確率的問題では対数因子を除いて下限に一致する誤り確率を示しつつ、敵対的ケースにもロバストであることを示します。

Abstract

私たちは、報酬が任意で、かつ潜在的に敵対的である場合の、バンディットにおける最良腕の識別を研究します。単純な一様ランダム・ラーナーは、敵対的シナリオにおいて最適な誤り率を達成します。しかし、この種の戦略は、報酬が確率的にサンプリングされる場合には不適です。そこで次の問いを立てます。報酬の性質を知らないまま、確率的問題と敵対的問題の両方で最適に振る舞う学習器を設計できるでしょうか。まず、そのような学習器の設計は一般には不可能であることを示します。特に、敵対的報酬に対する頑健性を持つためには、確率的問題のうちある部分集合に対してのみ、誤り率の最適なオーダーを保証できます。さらに、戦略が敵対的報酬に対して頑健であることを制約されている場合に、確率的問題における最適な誤り率を特徴づける下界を与えます。最後に、パラメータ不要の単純なアルゴリズムを設計し、それが確率的問題において（対数因子まで）下界と一致する確率で誤りを起こすことを示します。加えて、そのアルゴリズムは敵対的な場合にも頑健です。