Best-of-Both-Worlds保証付きのmセット半バンドット問題に対するさらなる高効率アルゴリズム
arXiv cs.LG / 2026/3/13
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、幾何再サンプリングを用いたFTPLをm-set半バンドット問題へ拡張し、敵対的設定で最適な後悔量を O(sqrt(mdT)) に達成することを示す。
- 同じ問題と分布（Fréchet分布およびPareto分布）に対して、確率的設定で対数的後悔を達成することでBest-of-Both-Worldsの性能を示す。
- 条件付き幾何再サンプリング拡張をm-set半バンドットへ導入し、元の幾何再サンプリングの計算量を O(d^2) から O(md(log(d/m)+1)) に削減しつつ、後悔性能を損なわない。
- 結果は特定の分布選択とパラメータ設定に依存しており、理論的最適性と実用的計算利得の両方を強調する。
要旨: 本論文は、Follow-the-Perturbed-Leader (FTPL) ポリシーの最適性と複雑さを、$m$-set 半バンドット問題において研究する。FTPL は、敵対的組合せ半バンドットにおいて、後悔の点で有利な効率的アルゴリズムの有望な候補として広く研究されてきた。しかし、最適性はオンライン学習のさまざまなタスクで最適性が証明された Follow-the-Regularized-Leader (FTRL) とは異なり、まだ未知のままである。本稿では、幾何再サンプリング（GR）を用いた FTPL の解析を $m$-set 半バンドットへ拡張する。これは組合せ半バンドット問題の特別なケースであり、Fréchet分布とPareto分布を用いた特定のパラメータの FTPL が、敵対的設定で可能な限り最良の後悔オーダー $O(
sqrt{mdT})$ を達成することを示す。また、Fréchet および Pareto 分布を特定のパラメータで用いた FTPL が確率的設定で対数的後悔を達成することを示し、$m$-set 半バンドット問題に対する Best-of-Both-Worlds の最適性を意味する。さらに、条件付き幾何再サンプリングを $m$-set 半バンドットへ拡張し、FTPL における効率的な損失推定のため、元の幾何再サンプリングの計算量 $O(d^2)$ を $O(md(
)$ に削減しつつ、後悔性能を損なわない。
