技術要約：Frequent Directionsを用いた効率的な多項ロジスティック・バンディット

問題設定

本論文は、エージェントが行動 $x_t \in \mathbb{R}^d$ を選択し、カテゴリカルなフィードバック $y_t \in \{0, \dots, K\}$ を観測する逐次的意思決定フレームワークである、多項ロジスティック・バンディット (Multinomial Logistic Bandits: MLogB) の課題に取り組んでいる。出力の確率分布は、未知の行列 $W^* \in \mathbb{R}^{K \times d}$ によってパラメータ化された多項ロジスティックモデルに従う。目的は、最適行動の期待報酬とエージェントが選択した行動との差として定義される累積リグレットを最小化することである。

OFUL-MLogB [Zhang and Sugiyama, 2023] のような既存の最先端アルゴリズムは、$\tilde{O}(Kd\sqrt{T})$ の近最適（near-optimal）なリグレット境界を達成しているが、高次元設定においては計算コストが極めて高いという問題がある。具体的には、OFUL-MLogBはパラメータ推定（オンライン・ニュートン・ステップ経由）および楽観的な報酬構築のために、フルサイズの $Kd \times Kd$ ヘシアン行列を維持・操作することに依存している。これにより、以下のコストが発生する：

• 時間計算量: 1ラウンドあたり $O(|A_t|K^3d^2 + K^3d^3)$。
• 空間計算量: 1ラウンドあたり $O(K^2d^2)$。

これらのコストにより、高次元のアクション空間 ($d$) や大きなアウトカム集合 ($K$) において、このアルゴリズムの実用性は困難となっている。

手法：EOFD-MLogB

著者らは、EOFD-MLogB (Efficient Optimism via Frequent Directions) を提案する。これは、理論的保証を維持しつつ計算複雑性を削減するために、Frequent Directions (FD) 行列スケッチングを OFUL-MLogB のフレームワークに統合したアルゴリズムである。

1. 適応型 FD によるスペクトル維持

ヘシアン $H_t$ 全体を保持する代わりに、EOFD-MLogB はスケッチされたヘシアン $Z_t$ の低ランクスペクトル分解を維持する：
$$Z_t = \lambda I_{Kd} + V_t \Lambda_t V_t^\top$$
ここで、$V_t \in \mathbb{R}^{Kd \times m}$ は直交列を持ち、$\Lambda_t \in \mathbb{R}^{m \times m}$ は対角行列であり、$m \ll d$ はスケッチサイズである。

• ブロック FD 更新: MLogB におけるヘシアン更新はランク $K$ の行列（$\nabla^2 \ell_t = \nabla \sigma(W_t x_t) \otimes x_t x_t^\top$）であるため、本アルゴリズムはブロック FD 更新を実行する。ランク $K$ の更新を $B_t B_t^\top$ に分解し、現在のスケッチ $[V_t \Lambda_t^{1/2}, B_t]$ に $B_t$ を追加する。その後、SVD（特異値分解）が計算され、上位 $m$ 個の特異方向が保持され、残りは累積スケッチ誤差項 $\rho_{1:t}$ へと破棄される。

2. 効率的なパラメータ更新

OFUL-MLogB におけるパラメータ更新は、ヘシアンによって定義される楕円体上の制約付き二次計画問題 (QCQP) を含む。

• 根求め問題への還元: サロゲート・ヘシアン $\tilde{Z}_t$ のスペクトル形式を利用することで、高次元の投影問題は、スカラーの単調関数 $f(\nu) = S^2$ の根 $\nu$ を見つける問題へと簡略化される。これにより、ウッドベリーの恒等式（Woodbury identity）を活用して、フル固有値分解を行うことなく、効率的に投影を計算できる。

3. 効率的な楽観的報酬の構築

MLogB における楽観的ボーナスには、高次元のスペクトルノルム、具体的には $\|H_t^{-1/2}(I_K \otimes x)\|_2$ の計算が含まれる。

• 次元削減: 著者らは、スケッチされた行列 $Z_t$ を使用することで、この $Kd \times Kd$ のスペクトルノルム計算が、$K \times K$ の対称行列 $A(x)$ のスペクトルノルム計算に還元されることを証明した（補題1）。これにより、スペクトルノルム計算における $d$ への依存性が排除され、計算コストが $O(K^3d^2)$ から $O(K^3 + K^2m + Kdm)$ へと減少する。

主な貢献

1. アルゴリズムの効率性: EOFD-MLogB は、支配的な 1 ラウンドあたりの時間計算量を $O(Kd(m+K)^2)$、空間計算量を **$O(Kd(m+K))$** と達成している。これは、従来手法における$d$ の 3 次依存性に対する大幅な改善であり、高次元設定へのスケーラビリティを実現している。
2. 理論的保証: 本論文は、累積スケッチ誤差 $\rho_{1:T}$ に依存するスケッチ係数 $\Delta_T = 1 + \rho_{1:T}/\lambda$ を用いたリグレット境界 $\tilde{O}(\Delta_T (Kd \ln \Delta_T + m)\sqrt{T})$ を確立している。
   • 誤差項 $\rho_{1:T}$ は、累積ヘシアンの $m$ 個に切り捨てられたスペクトル・テイルによって抑えられる。
   • 累積ヘシアンが近似的に低ランクである場合（すなわち、スペクトル・テイルが急速に減衰する場合）、$\Delta_T \approx 1$ となり、リグレット境界は元の OFUL-MLogB に近づく。
3. 汎用性: スペクトル削減技術（補題1および補題2）は、OFUL-MLogB だけでなく、ヘシアンベースの更新に依存する他の二次的 MLogB アルゴリズムや一般化線形バンディットにも適用可能であることが示されている。

実験結果

実験は、MNIST データセット（コンテキスト・バンディット問題に変換したもの）および高次元（$d=100, 400$）の合成データを用いて行われた。

• パフォーマンス: EOFD-MLogB は、多項およびバイナリの両方の設定において、OFUL-MLogB と同等の曲線を描き、競争力のあるリグレット性能を維持している。
• 効率性: 提案手法は大幅な高速化を示した。MNIST において、リグレットに約 10% のオーバーヘッドのみを課しながら、1 ラウンドあたりの計算時間を約 80% 削減した。合成データでは、時間削減率は多項設定で 35% 以上、バイナリ設定で 80% 以上 に達した。

意義と主張

本論文は、EOFD-MLogB が既存の二次的 MLogB アルゴリズムにおける「忌避すべき」フルヘシアン・コストの問題を解決したと主張している。Frequent Directions スケッチング技術を活用することで、以下のことが可能であることを著者らは示している：

• 二次的手法の理論的利点（曲率を考慮した更新およびタイトな信頼集合）を保持すること。
• 高次元レジームにおける計算オーバーヘッドを劇的に削減すること。
• 基盤となるヘシアン構造が近似的に低ランクである限り、ほぼ最適に近いリグレット保証を維持すること。

本研究は、標準的なスケッチ手法（線形バンディットで使用されるもの）は、多項ロジスティックモデル特有の構造ゆえに、非線形な MLogB 設定には直接適用できないことを浮き彫りにしている。しかし、多項ロジスティックモデルに特化したスペクトル削減を用いることで、これらのボトルネックを克服できることを示している。著者らは、今後の課題として、スケッチサイズ $m$ の適応的な選択や、スケッチ係数 $\Delta_T$ を直接制御するための条件の開発を挙げている。