Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

技術的サマリー：分離型バンディットにおける Follow-the-Perturbed-Leader

問題設定
本論文は、**分離型多腕バンディット（MAB）問題を取り扱います。これは、学習者が各ラウンド $t$ に 2 つの異なる腕を選択する設定であり、1 つの腕 $i_t$ は活用（exploitation）のために選択され（損失 $\ell_{t, i_t}$ を被るが観測しない）、もう 1 つの腕 $j_t$ は探索（exploration）**のために選択され（損失 $\ell_{t, j_t}$ を観測するが被らない）ます。この枠組みは、送信チャネルとは異なるチャネルをセンシングする超広帯域通信システムや、ロボティクスにおけるシミュレーションから実世界への転移（sim-to-real transfer）などのシナリオをモデル化します。目的は、学習者の活用選択によって被った累積損失と、 hindsight（ hindsight）における最良の固定腕の累積損失との差として定義される疑似後悔（pseudo-regret）を最小化することです。

本論文は、**Best-of-Both-Worlds（BOBW）**保証を目標とし、以下の達成を目指します：

1. 敵対的レジーム（損失が適応的な敵によって決定される場合）における、$O(\sqrt{KT})$ の最適後悔。
2. 確率的制約付き敵対的（SCA）レジーム（標準的な確率的設定を含む）における、$O(K/\Delta_{\min})$ の準最適かつ時間非依存の後悔。ここで $\Delta_{\min}$ は最小の最適性ギャップです。

手法
著者は、既存の BOBW 方策が分離型設定において抱える計算上のボトルネックを克服するために特別に設計された、**Follow-the-Perturbed-Leader（FTPL）**フレームワークに基づく新しい方策を提案します。

• 活用戦略：学習者は、摂動された累積損失推定値を最小化することで活用腕 $i_t$ を選択します：
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  ここで、$\hat{L}_{t,i}$ は累積損失の推定値、$\eta_t$ は学習率、$r_{t,i}$ は形状パラメータ $\alpha > 1$ を持つパレート分布 $P_\alpha$ からサンプリングされた i.i.d. 摂動です。この摂動のタイプは、BOBW 保証を達成することで知られる $\beta$-Tsallis-INF 方策（$\alpha = 1/(1-\beta)$）に対応します。

• 探索戦略（主要な革新）：標準的な FTPL バンディットアルゴリズムでは、不偏な重要度重み付け（IW）損失推定値を構築するには、腕 $i$ を選択する正確な確率 $w_{t,i}$ を知る必要があります。分離型バンディットでは、探索確率 $p_{t,i}$ を $w_{t,i}$ に基づいて設定する必要があります。しかし、FTPL は FTRL とは異なり $w_{t,i}$ の閉形式式を提供せず、幾何学的リサンプリングを通じて完全なベクトルを推定することは計算コストが高く（$O(K^2)$ 以上）、非現実的です。
  これを解決するため、著者はリサンプリングや凸最適化なしに現在の損失推定値から直接計算可能な代理確率（surrogate probability） $q_{t,i}$ を導入します：
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  ここで、$\sigma_{t,i}$ はすべての腕の中での $\hat{L}_{t,i}$ のランクです。その後、探索腕 $j_t$ は正規化された分布 $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$ に従って選択されます。このアプローチは、明示的な $w_{t,i}$ 値を必要とせずに、BOBW 保証に必要な理論的性質を維持します。

主要な貢献

1. 分離型バンディットにおける最初の FTPL ベースの BOBW 方策：本論文は、FTRL ベースのアプローチ（Decoupled-Tsallis-INF など）が要求する凸最適化問題を解くことなく、また（通常 FTPL 確率推定に必要とされる）リサンプリング手順を採用することなく、分離型バンディットで BOBW 保証を達成する最初の方策を提示します。
2. 計算効率：完全な確率ベクトルの計算を、効率的に計算可能な代理 $q_{t,i}$ に置き換えることで、提案された方策はステップごとの計算複雑度を削減します。損失推定値のソートには $O(K \log K)$ が必要ですが、著者は最適化された実装により、ランクの変化を逐次的に追跡することで $O(K)$ の更新を達成できると指摘しています。これは、各ステップで反復的な凸最適化（ニュートン法など）を必要とする FTRL 方策とは対照的です。
3. 理論的保証：
   • 敵対的レジーム：方策は $O(\sqrt{KT})$ の後悔 bound を達成し、分離型バンディットに対する既知の下限と一致します。
   • 確率的/SCA レジーム：方策は $O(K/\Delta_{\min})$ の後悔 bound を達成します（$\alpha=3$ の場合、具体的には $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$）。これは準最適であり、標準的な確率的バンディットの時間依存 bound を改善します。

結果

• 理論的：本論文は、代理確率 $q_{t,i}$ が必要な後悔 bound を維持するために真の活用確率に十分に近いことを示す厳密な証明（後悔を安定性とペナルティ項に分解することによる）を提供します。
• 実証的：合成データ（敵対的および確率的レジームの両方）および MovieLens 100K データセットを使用した実世界シミュレーションにおける実験は、提案された FTPL 方策が以下のことを示しています：
  • 既存の BOBW 方策（Decoupled-Tsallis-INF/FTRL および EXP3）と比較して、より低い累積後悔を達成する。
  • 優れた計算効率を示す。敵対的レジームにおいて、提案された方策は FTRL ベースのベースラインよりも著しく高速に実行されます。$K=64$ の場合、FTRL から FTPL への実行時間の比率は約 1363 倍遅いことが観察されました。
  • 腕の数 $K$ に対して効果的にスケーリングし、さまざまなギャップサイズ $\Delta$ において堅牢性を維持する。

意義と主張
本論文は、その主要な貢献が、分離型バンディットの文脈において、FTRL ベースの BOBW 方策の理論的最適性と FTPL の計算効率との間のギャップを埋めることであると主張しています。凸最適化とリサンプリングの必要性を排除することで、提案された手法は、後悔性能を犠牲にすることなく FTPL がその効率性の利点を完全に実現することを可能にします。著者は、正確な確率ベクトルの代わりに効率的に計算可能な代理確率を使用する技術が、FTPL 以外の他のアルゴリズム的枠組み（Prod 族など）にも適用可能であり、より広範なバンディット設定における計算効率の向上を可能にする可能性があると示唆しています。この研究は、ステップごとの計算遅延が重要な通信システムやロボティクスにおける実用的な応用によって動機付けられています。