確率的マルチ目的バンディットは単一目的バンディットより難しいのか？

要旨: 多目的バンディットは、その広範な適用可能性と数学的な優美さから、近年ますます注目を集めている。ここでは各アームの報酬がスカラーではなく多次元ベクトルである。これにより、自然にパレート順序関係とパレート損失（Pareto regret）が導入される。この分野における長年の未解決問題は、この追加された複雑さによって性能の最適化が本質的に難しくなるのかどうかである。最近の驚くべき結果として、敵対的（adversarial）設定ではパレート損失が古典的な損失（classical regret）より大きくならないことが示されている。しかし、損失概念が異なる確率的（stochastic）設定では、その様子は依然として不明である。実際、既存の研究では、確率的場合におけるパレート損失が次元数とともに増大すると示唆されている。この、議論を呼びつつも微妙な現象が、私たちの中心的な問いを動機づける：
\emph{多目的バンディットは実際に単目的のものより難しいのだろうか？}
私たちはこの問いに完全に答える。確率的設定において、パレート損失は実際には最大の劣性ギャップ \(g^\dagger\) によって支配され、したがって \(\Omega(\frac{K\log T}{g^\dagger})\) の最小限界（marginal regret）によって決まることを示す。さらに、パレート損失が \(O(\frac{K\log T}{g^\dagger})\) のオーダーを達成する新しいアルゴリズムを開発し、それゆえ最適であることを保証する。このアルゴリズムは、上側および下側の信頼区間推定子を用いて、アームと目的の両方に対するネストされた二層の不確実性定量化を活用する。具体的には、アーム選択にはトップツー・レーシング戦略を用い、次元選択には不確実性に基づく貪欲則を組み合わせる。これらの構成要素が、二つの層にまたがって探索と活用のバランスをとる。加えて、提案アルゴリズムを検証するために包括的な数値実験を行い、望ましい損失保証と、ベンチマーク手法に対する顕著な改善を示す。