Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

技術要約：大規模アクション空間におけるオフポリシー学習：推定よりも最適化が重要である

問題提起
オフライン・コンテキスト・バンディットにおけるオフポリシー学習（OPL）は、期待報酬 $V(\pi)$ を最大化する方策 $\hat{\pi}$ を、ログデータ $D_n = \{(X_i, A_i, R_i)\}$ から学習することを目的としている。支配的なパラダイムは、逆傾向スコア（IPS）に基づく典型的なオフポリシー評価（OPE）推定器 $\hat{\pi} = \arg\max_\pi \hat{V}_{IPS}(\pi)$ を最適化することである。近年の研究は、期待値 $V(\pi)$ をより正確に近似するために、洗練された統計的特性（例：分散の低減やバイアスの抑制）を持つ推定器の開発に焦点を当ててきたが、本論文は、このような推定器中心のアプローチが、極めて重要な実用的障害である「最適化のランドスケープ」を見落としていると主張する。

大規模なアクション空間（アクション数 $K$ が数百万に達する場合がある）において、IPSベースの目的関数と標準的な方策パラメータ化（例：ソフトマックス）を組み合わせると、深刻な最適化の病理が発生する。これには、勾配上昇法が停滞する長いプラトー（平坦な領域）や、膨大な数の劣悪な局所解が含まれる。本論文は、たとえ優れた統計的保証を持つ推定器であっても、基礎となる最適化問題が $K$ の増加に伴って困難（intractable）になるため、良好な方策が得られない可能性があると断じている。

手法および分析
著者らは、大規模アクション空間においては、推定の正確性よりも最適化の安定性の方が重要であるという主張を裏付けるために、理論的分析と実証的エビデンスの両方を提供している。

1. IPSベースの目的関数の理論的分析:

   • 本論文では、標準的なIPS、Clipped IPS (cIPS)、Exponential Smoothing (ES)、Doubly Robust (DR)、Marginalized IPS (MIPS)、OffCEM、POTEC、およびPolicy Convolution (PC) を含む、様々なIPSベースの推定器における「オラクル方策」（期待目的関数の理論的な最大化因子）を分析している。
   • 最適化の病理: 著者らは、$\pi$ に関して線形な推定器とソフトマックス方策を用いた場合、勾配上昇法が $O(K_{eff})$ イテレーションの間、劣悪な領域に閉じ込められる可能性があることを証明している。ここで $K_{eff}$ は有効アクション空間のサイズである。さらに、ランドスケープには $K_{eff}$ に対して指数関数的な数の局所最大値が存在する。
   • $K_{eff}$ の役割: MIPSやOffCEMのように大規模アクション空間向けに設計された手法であっても、全アクション空間 $A$ に対して最適化を行う場合（$K_{eff} = K$）、この問題を軽減できないことが多い。唯一特定された例外は、最適化をクラスターレベルに制限することで $K_{eff}$ を実質的に減少させるPOTECである。
   • 目的関数を意識したパラメータ化: 著者らは、方策クラスを推定器の帰納バイアスに適合させることを提案している。例えば、IPSベースの手法に対しては方策のサポートをロギング方策のサポート $S_0$ に制限したり、クラスターベースの手法に対しては2段階の分解を用いたりすることで、統計的なターゲットを変更することなく、$K_{eff}$ を減少させ学習性を向上させることができる。しかし、これは症状を緩和するだけであり、IPSベースの目的関数が持つ根本的な非凹性を治療するものではない。

2. 方策重み付き対数尤度（PWLL）目的関数:

   • 基本的な代替案として、本論文は $\hat{U}_g(\pi) = \frac{1}{n} \sum g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$ という形式をとるPWLL目的関数を検討している。
   • 凹性: 線形ソフトマックス方策を使用する場合、IPS目的関数とは異なり、PWLL目的関数は本質的に凹（かつ $\ell_2$ 正則化により強凹）である。これは、スコアから対数確率への写像が凹であるためである。
   • 最適化の保証: 著者らは、PWLL目的関数に対する確率的勾配上昇法が、一般に $O(1/\sqrt{T})$ のグローバル収束率を達成し、正則化を伴う場合は幾何級数的な速度に加速することを確立している。
   • バリアント: 本研究では、Local Policy Improvement (LPI)、Clipped LPI (cLPI)、およびRegularized KL (RegKL) を含む特定のPWLLバリアントを評価している。特に、cLPIは、凸最適化問題を経由しながらも、cIPSと同じ貪欲な決定規則を誘導することが示されている。

主な貢献

1. アクション空間に伴う最適化理論のスケーリング: 本論文は、最適化の病理（プラトーと局所最大値）がアクション数 $K$ とどのようにスケールするかを定式化し、なぜIPSベースの目的関数が $K$ の増大に伴い最適化が困難になるのかを説明している。
2. 目的関数を意識したパラメータ化: 著者らは、様々な目的関数（オラクル方策から導出される）に対する最小限の十分な方策構造を特定し、方策をそれらの構造に一致するように制限または分解することが、学習性と性能を向上させることを示している。
3. 最適化に優しい目的関数としてのPWLL: 本論文は、線形ソフトマックス方策において、PWLL目的関数が挙動の良い凹な最適化ランドスケープを提供し、直接的な価値最大化に対する堅牢な代替手段となることを示している。
4. 大規模な実証的ストレス・テスト: 3つの大規模データセット（MovieLens $K=60k$、Twitch $K=200k$、GoodReads $K=1M$）を用いた広範な実験により、IPSベースの手法はハイパーパラメータ（バッチサイズ、学習率スケジュールの設定）に対して非常に敏感である一方、PWLL手法は堅牢であり、一貫して高い報酬を達成することが示された。
5. 実行可能なガイダンス: 大規模アクション空間のための設計指針をまとめている。すなわち、目的関数を意識したパラメータ化を用いて最適化の安定性を優先し、方策学習においては複雑なIPS推定器よりもPWLLスタイルの目的関数を好むべきである。

結果

• 最適化の感度: コントロールされたスイープ実験において、IPSベースの目的関数（最先端のPOTECを含む）は、劣悪なハイパーパラメータの下で高い分散と性能崩壊を示した。対照的に、PWLL手法（特にcLPI）は、あらゆる構成において高い性能を維持した。
• 推定 vs 学習: 本論文は、「価値の推定器として低い平均二乗誤差（MSE）を持つ手法（MIPSなど）が、必ずしもより良い方策を生み出すわけではない」という反直観的な発見を強調している。逆に、PWLL手法は（MSEが高いという意味で）価値の推定としては劣っているが、最も優れた方策を生成した。これは、大規模アクション空間においては、価値推定の統計的正確さよりも、目的関数の最適化能力の方が方策の質を予測する強力な要因であることを示唆している。
• パラメータ化の影響: 有効アクション空間を目的関数の帰納バイアスに一致するように制限すること（例：IPSに対するサポート制限付き方策の使用）は、IPS手法の安定性と性能を大幅に改善したが、依然としてPWLL手法には及ばなかった。
• 堅牢性: PWLL手法は、IPSベースのアプローチと比較して、報酬ノイズや異なるロギング方策のサポートに対して優れた堅牢性を示した。

意義と主張
本論文は、オフポリシー学習の分野が、推定器の精緻化に過度に集中する一方で、大規模アクション空間における決定的なボトルネックである最適化のランドスケープを軽視してきたと主張している。著者らは以下の通り述べている：

• 最適化がボトルネックである: 大規模アクション空間において、非凹なIPS目的関数の最適化の難しさが、最も統計的に洗練された推定器の実際的な有用性を損なわせる。
• シンプルさが勝る: シンプルで最適化しやすい目的関数であるPWLL（特にcLPI）は、複雑な分散低減型IPS推定器よりも優れた性能を示す。これは、安定した信頼できる収束を可能にするためである。
• 設計の転換: 大規模アクション空間のためのOPLアルゴリズムの開発は、明示的に最適化の考慮事項に対処しなければならない。本論文は、「推定器中心」の設計から「最適化中心」の設計へのシフトを提唱しており、方策を学習する目的においては、高精度な価値推定を実現することよりも、扱いやすい最適化ランドスケープを確保することの方が重要であると示唆している。

著者らは限界についても言及している。PWLL目的関数は、正確な価値推定が必要とされるオフポリシー評価（OPE）や方策選択には適していない。加えて、PWLLの凹性の保証は線形ソフトマックス方策に対して厳密に成り立つものである。ディープニューラルネットワークを使用すると形式的な凹性は失われる可能性があるが、その勾配構造はIPSベースの目的関数よりも依然として良好な性質を保っている。