Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

問題定式化
本論文は、単純後悔（simple-regret）目的の下での確率的ロジスティックバンディットを調査する。この設定において、学習者は $T$ ラウンドにわたり環境と相互作用し、行動集合 $\mathcal{A}$ から行動 $A_t$ を選択し、平均 $\mu(\phi(A_t)^\top \theta^*)$ を持つベルヌーイ報酬 $X_t$ を観測する。ここで、$\mu$ はシグモイド関数、$\phi$ は既知の特徴マップ、$\theta^*$ は $\mathbb{R}^d$ 内の未知パラメータである。探索中の報酬の合計を最大化することを目的とする累積後悔とは異なり、単純後悔目的は、$T$ ラウンド後の単一の最終推奨 $\hat{a}$ の品質のみで学習者を評価する。後悔は、最適行動の期待報酬と推奨された行動の期待報酬との差として定義される。

ロジスティックバンディットにおける重要な課題は、行動の情報量の不均一性である。シグモイドリンクにより、「飽和」領域（平均報酬が 0 または 1 に近い領域）における行動はほぼ決定論的な報酬をもたらすが、パラメータ $\theta^*$ に関する情報はほとんど提供しない。逆に、原点付近（シグモイドが最も急峻な領域）の行動は非常に情報量が多いが、直近の報酬は低くなる可能性がある。これにより、直近の報酬に最適（活用）な行動と、最適行動の特定に最適（探索）な行動が異なる幾何学的構造が生まれる。

手法
著者は、シグモイド関数の局所幾何を利用するように設計された、曲率を考慮した 2 つのアルゴリズムを提案する。

1. MULOG（Max-Uncertainty-Log）: 決定論的な純粋探索アルゴリズム。

   • メカニズム: MULOG は $\theta^*$ に対する信頼集合 $W_t$ を維持し、曲率重み付き設計行列 $L_t$ を構築する。行動 $a$ とパラメータ $\theta$ に対する不確実性スコアは、$U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$ と定義される。ここで $\dot{\mu}$ はシグモイドの微分（局所曲率を表す）である。
   • 選択: 各ラウンドにおいて、アルゴリズムはこの不確実性スコアを最大化する行動 - パラメータ対 $(A_t, \theta_t)$ を選択する。
   • 終了: $T$ ラウンド後、最終的な信頼集合からサンプリングされたパラメータベクトルに対して貪欲な行動を返す。
   • 最適化: 有限行動集合の場合、選択ステップは有限個の凸最適化問題を解くことに帰着される。

2. THATS（Try Hard Thompson Sampling）: ランダム化された、計算量が少ない代替手法。

   • メカニズム: 正確な最大不確実性を解く代わりに、THATS は共分散 $L_t^{-1}$ を持つゼロ中心ガウス分布から方向 $\tilde{\theta}_t$ をサンプリングする。
   • 選択: 確率化された不確実性スコア $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$ を最大化する行動を選択する。ここで $\bar{\theta}_t$ は制約付き最尤推定量である。
   • トレードオフ: このアプローチは MULOG が必要とする凸最適化を回避するが、統計的なコストを伴い、結果としてわずかに緩い後悔 bound をもたらす。

主要な貢献

• ミニマックス下限: 本論文は、$\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$ 次数の 1 次ミニマックス下限を確立する。ここで $\kappa^*$ は最適行動におけるシグモイドの逆傾き（すなわち $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$）である。
  • 固有の困難性メカニズム: 情報のコスト（学習者に準最適腕をプレイさせること）に依存する累積後悔の下限（例：Abeille et al., 2021）とは異なり、この下限は「シフトされた飽和ハイパーキューブ」の構成から導出される。この構成では、統計的情報と値の感度の両方が、飽和領域における同じ局所曲率によって制御される。これは、純粋に情報のためにサンプリングする自由があっても、最適行動がシグモイドの平坦な領域にあれば、問題が困難であることを示している。
• 最適アルゴリズム:
  • MULOG は、対数因子を除いて下限と一致する単純後悔上限 $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$ を達成する。これは、インスタンスごとのミニマックス最適性を達成する、ロジスティックバンディットに対する最初の直接的な純粋探索保証である。
  • THATS は $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$ の bound を達成する。追加の $\sqrt{d}$ 因子は、最大不確実性方向に対する幾何学を無視したランダム化近似を使用することから生じる。
• 幾何学的洞察: 著者は、最悪ケースの幾何学（シフトされた飽和インスタンス）が唯一のケースではないことを実証する。行動集合内に「情報豊富だが報酬の低い行動」（プローブ）が存在し得ることを示す。これらの行動はシグモイドの高曲率領域に位置し、期待報酬が低いにもかかわらず、最適方向に関する重要な情報を提供する。

結果

• 理論的: 導出された bound は、ロジスティック単純後悔の困難さが最適行動における曲率によって支配されることを確認する。アルゴリズムは、曲率重み付き特徴方向における不確実性を成功裡に制御する。
• 実証的: 「困難な」幾何学（シフトされた飽和ハイパーキューブ）と「容易な」幾何学（情報豊富なプローブ腕を追加したもの）の両方における実験は、理論的知見を支持する。
  • 困難なインスタンスでは、MULOG と THATS はミニマックス bound によって予測された通りに動作する。
  • プローブ腕を持つ容易なインスタンスでは、純粋探索手法（MULOG と THATS）は、累積後悔ベースライン（累積 Thompson サンプリングやオンライン・ツー・バッチ変換など）を大幅に上回る。純粋探索手法は、報酬が低く情報量の多いプローブを積極的にサンプリングし、低い単純後悔閾値に達するために必要なラウンド数を劇的に減少させる。
  • 累積後悔手法は、最終的な推奨分布への低報酬行動の組み込みをペナルティとするオンライン・ツー・バッチ変換により、これらのプローブを効果的に活用できない。

意義
本論文は、ロジスティックバンディットにおける純粋探索が、累積後悔問題とは異なる幾何学を持つと主張する。主な貢献は、**最適行動における局所曲率（$\kappa^*$）**が 1 次ミニマックス率を支配する要因であることを特定した点にある。この曲率を明示的に考慮するアルゴリズムを開発することで、著者は最悪ケースにおいてミニマックス最適な性能を達成する。さらに、この研究は実践的な示唆を浮き彫りにする。A/B テストや報酬モデルのデータ収集などの設定において、「情報豊富だが報酬の低い」行動を積極的に探すことは、最終的な最良の方策の特定を大幅に加速し得る。これは、標準的な累積後悔アルゴリズムが構造的に示すことができない振る舞いである。これらの結果は、非線形バンディットにおける意思決定に焦点を当てた探索の、より鋭い理論の起点となる。