Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

以下は、「単一方策集中性における前方 KL 正則化付きオフライン文脈バンディットのための高速レート」に関する論文の詳細な技術的要約である。

問題定義

本論文は、学習目的が前方カルバック・ライブラー情報量（Forward-KL）正則化を含む場合の、文脈バンディット（CB）におけるオフライン学習の統計的効率性に取り組む。目的関数は以下のように定義される：
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
ここで、$r$ は報酬、$\eta$ は正則化強度の逆数、$\pi_{\text{ref}}$ は参照（行動）方策である。

一方、逆 KL 正則化（$\text{KL}(\pi \| \pi_{\text{ref}})$）は広範に研究され、単一方策集中性（行動方策が最適方策のみをカバする状況）の下で $\tilde{O}(\epsilon^{-1})$ のサンプル複雑性（高速レート）を許容することが示されているが、前方 KL のケースは未解決の問題のまま残っている。前方 KL に対する既存の分析は、適用できないか、あるいは遅い $\tilde{O}(\epsilon^{-2})$ レートに留まる。さらに、前方 KL は「モード探索的」ではなく「質量カバリング的」（$\pi_{\text{ref}} > 0$ である場所で $\pi \to 0$ となることを罰する）であるため、より強力なカバリング仮定を必要とする可能性があることから、単一方策集中性が前方 KL に対して十分かどうかは不明である。

本論文は、以下の 2 つの核心的な問いに答えることを目指す：

1. 前方 KL 正則化された目的関数に対する意思決定の統計的レートは何か？
2. この設定において、最適レートを実現するオフライン学習のために単一方策集中性は十分か？

手法

著者は、**前方 KL 正則化付き悲観的文脈バンディット（FKL-PCB）**のための簡素化された分析を提案する。この手法は、テイラー展開と平均値定理（MVT）に依存する先行研究とは大きく異なる。

1. 従来の MVT に基づく分析の拒絶：
正則化された目的関数を分析する先行研究では、しばしば中間点 $\bar{u}$ 周りで（平均値定理を通じて）テイラー展開を行い、最適性ギャップを分解する。逆 KL の場合、得られる項は悲観性の下で単調性という性質を示し、これにより単一方策集中性を用いて誤差を有界化できる。
しかし、著者は（補題 5.3 により）前方 KL の場合、最適性分解項の微分が中心化された確率変数の「傾いた歪み」を含むことを示す。この微分の符号は不定であるため、単調性の議論は失敗する。その結果、標準的な MVT ベースの手順は、より強力な（全方策）集中性仮定に頼らない限り、高速レートを達成できない。

2. 凸解析的パイプライン：
MVT の限界を回避するため、著者は凸共役とブレグマン発散に基づく新しい証明技法を導入する：

• 双対視点： 確率単体上の凸共役を通じて正則化された目的関数を特徴づける。
• 自己有界性議論： 最適性ギャップの恒等式（補題 5.5）を導出し、誤差を真の報酬と悲観的推定値との二乗差、および最適方策と参照方策との比で重み付けされた形で直接表現する。
• 主要な恒等式： 核心的な技術的貢献は以下の不等式である：
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  この上界は、全方策集中性を必要とせず、単一方策集中性係数 $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$ のみ に依存する。

3. アルゴリズム設計：
本論文は、表形式および関数近似の両方の設定における悲観的アルゴリズムFKL-PCBを提示する：

• 推定： 報酬関数を推定するために最小二乗法を使用する。
• 悲観性： 推定報酬 $\hat{r}$ が真の報酬 $r$ に対して高い確率で下界となるよう、ペナルティ項（信頼区間）を減算する。
• 最適化： 悲観的正則化目的関数を最大化する方策を出力する。

主要な貢献と結果

1. 高速サンプル複雑性の上限：
本論文は、単一方策集中性の下での前方 KL 正則化付きオフライン CB に対する最初の $\tilde{O}(\epsilon^{-1})$ サンプル複雑性上限を確立する：

• 表形式設定： $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$。
• 関数近似： $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$。ここで、$D^2_{\pi^*}$ は $D^2$ 型の集中性係数、$N_G$ は関数クラスの覆い数である。
• これらの結果は、Aminian ら（2025）による以前の最先端である $\tilde{O}(\epsilon^{-2})$ 上限を改善し、全方策集中性の要件を単一方策集中性へと緩和する。

2. 最小最大下限：
著者は、上限の緊密性を示すための一致する下限を提供する：

• 表形式下限： 高正則化領域において $\Omega(\eta |S||A| \epsilon^{-1})$。これは、$\eta$ に対する線形依存性と $1/\epsilon$ レートが最適であることを確認する。
• 位相転移： 下限は、逆 KL と同様の「位相転移」を明らかにする。低正則化領域（大きな $\eta$）では、サンプル複雑性は遅い $\tilde{O}(\epsilon^{-2})$ レートに戻り、高速レートを達成するには正則化が必要であることを示唆している。

3. 技術的新規性：
本論文は、「凸解析的パイプライン」が表形式と関数近似の両方の設定を統一し、平均値定理に基づく証明手順を完全に回避すると主張している。このアプローチは、他の発散正則化された意思決定問題の分析に対しても独立した関心を持つものとして提示されている。

意義と主張

本論文は、オフライン学習における前方 KL 正則化の統計的レートを正確に特徴づけた最初の研究として位置づけられている。その主な意義は以下の点にある：

• 未解決問題の解決： 単一方策集中性が前方 KL に対して十分かどうかという問いを、高速レートを伴う肯定回答で解決する。
• 統一理論： 前方 KL の「質量カバリング的」性質は、新しい解析的手法を用いれば、「モード探索的」な逆 KL よりも強力なカバリング仮定を本質的に必要としないことを示す。
• アルゴリズムの簡素さ： 複雑なアルゴリズム的修正を必要とせず、最小限の悲観性に基づくアルゴリズム（FKL-PCB）だけでこれらの最適レートを達成できることを示す。

著者は将来の方向性については謙虚であり、十分性は確立されたものの、前方 KL に対する単一方策集中性の必要性（多腕バンディットにおいても）は未解決の問題であると指摘している。さらに、関数近似における $D^2$ 型集中性に対して上限と一致する下限を導出することは、今後の課題として残されている。