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

Problem Statement

The paper addresses the statistical efficiency of offline learning in Contextual Bandits (CBs) when the learning objective involves Forward-Kullback-Leibler (Forward-KL) regularization. The objective function is defined as:
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
where $r$ is the reward, $\eta$ is the inverse regularization intensity, and $\pi_{\text{ref}}$ is a reference (behavioral) policy.

While reverse-KL regularization ($\text{KL}(\pi \| \pi_{\text{ref}})$) has been extensively studied and shown to admit $\tilde{O}(\epsilon^{-1})$ sample complexity (fast rates) under single-policy concentrability (where the behavior policy covers only the optimal policy), the Forward-KL case remains an open problem. Existing analyses for Forward-KL either fail to apply or result in slow $\tilde{O}(\epsilon^{-2})$ rates. Furthermore, it is unclear whether single-policy concentrability is sufficient for Forward-KL, given that Forward-KL is "mass-covering" (penalizing $\pi \to 0$ where $\pi_{\text{ref}} > 0$) rather than "mode-seeking," potentially requiring stronger coverage assumptions.

The paper seeks to answer two core questions:

1. What is the statistical rate of decision-making for Forward-KL regularized objectives?
2. Is single-policy concentrability sufficient for rate-optimal offline learning in this setting?

Methodology

The authors propose a streamlined analysis for Forward-KL-Regularized Pessimistic Contextual Bandits (FKL-PCB). The methodology diverges significantly from previous works that rely on Taylor expansions and the Mean Value Theorem (MVT).

1. Rejection of Traditional MVT-Based Analysis:
Previous works analyzing regularized objectives often use a Taylor expansion around an intermediate point $\bar{u}$ (via the Mean Value Theorem) to decompose the suboptimality gap. For reverse-KL, the resulting terms exhibit a monotonicity property under pessimism that allows bounding the error using single-policy concentrability.
However, the authors demonstrate (via Lemma 5.3) that for Forward-KL, the derivative of the suboptimality decomposition term involves a "tilted skewness" of a centered random variable. The sign of this derivative is indefinite, meaning the monotonicity argument fails. Consequently, standard MVT-based routines cannot achieve fast rates without resorting to stronger (all-policy) concentrability assumptions.

2. Convex-Analytical Pipeline:
To bypass the limitations of MVT, the authors introduce a novel proof technique based on convex conjugates and Bregman divergences:

• Dual Perspective: They characterize the regularized objective via its convex conjugate over the probability simplex.
• Self-Bounding Argument: They derive an identity for the suboptimality gap (Lemma 5.5) that expresses the error directly in terms of the squared difference between the true reward and the pessimistic estimate, weighted by the ratio of the optimal policy to the reference policy.
• Key Identity: The core technical contribution is the inequality:
  $$\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$$
  This bound depends only on the single-policy concentrability coefficient $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$, avoiding the need for all-policy concentrability.

3. Algorithm Design:
The paper presents FKL-PCB, a pessimistic algorithm for both tabular and function approximation settings:

• Estimation: Uses least-squares to estimate the reward function.
• Pessimism: Subtracts a penalty term (confidence bound) to ensure the estimated reward $\hat{r}$ is lower-bounded by the true reward $r$ with high probability.
• Optimization: Outputs the policy maximizing the pessimistic regularized objective.

Key Contributions and Results

1. Fast Sample Complexity Upper Bounds:
The paper establishes the first $\tilde{O}(\epsilon^{-1})$ sample complexity bounds for Forward-KL regularized offline CBs under single-policy concentrability:

• Tabular Setting: $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$.
• Function Approximation: $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$, where $D^2_{\pi^*}$ is a $D^2$-type concentrability coefficient and $N_G$ is the covering number of the function class.
• These results improve upon the previous state-of-the-art $\tilde{O}(\epsilon^{-2})$ bound by Aminian et al. (2025) and relax the requirement from all-policy concentrability to single-policy concentrability.

2. Minimax Lower Bounds:
The authors provide matching lower bounds to demonstrate the tightness of their upper bounds:

• Tabular Lower Bound: $\Omega(\eta |S||A| \epsilon^{-1})$ in the high-regularization regime. This confirms that the linear dependence on $\eta$ and the $1/\epsilon$ rate are optimal.
• Phase Transition: The lower bounds reveal a "phase transition" similar to reverse-KL. In the low-regularization regime (large $\eta$), the sample complexity reverts to the slow $\tilde{O}(\epsilon^{-2})$ rate, indicating that regularization is necessary to achieve fast rates.

3. Technical Novelty:
The paper claims that the "convex-analytical pipeline" unifies tabular and function approximation settings and completely bypasses the proof routines based on the Mean Value Theorem. This approach is presented as being of independent interest for analyzing other divergence-regularized decision-making problems.

Significance and Claims

The paper positions itself as the first work to exactly characterize the statistical rates for Forward-KL regularization in offline learning. Its primary significance lies in:

• Resolving an Open Problem: It settles the question of whether single-policy concentrability is sufficient for Forward-KL, answering in the affirmative with fast rates.
• Unifying Theory: It demonstrates that the "mass-covering" nature of Forward-KL does not inherently require stronger coverage assumptions than the "mode-seeking" reverse-KL, provided a novel analytical approach is used.
• Algorithmic Simplicity: It shows that a minimalist pessimism-based algorithm (FKL-PCB) is sufficient to achieve these optimal rates, without needing complex algorithmic modifications.

The authors remain modest regarding future directions, noting that while they establish sufficiency, the necessity of single-policy concentrability for Forward-KL (even in multi-armed bandits) remains an open question. Additionally, deriving a lower bound that matches the upper bound specifically for the $D^2$-type concentrability in function approximation is left for future work.