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

• URL: http://arxiv.org/abs/2605.09214v1
• Date: Sat, 09 May 2026 23:17:46 GMT
• Title: Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
• Abstract summary: emphKullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms.<n>Recent studies have demonstrated $-1$-type fast rates for decision making under reverse KL regularization.<n>We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs.
• Score: 54.40598524756038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: \emph{Kullback-Leibler} (KL) regularization is ubiquitous in reinforcement learning algorithms in the form of \emph{reverse} or \emph{forward} KL. Recent studies have demonstrated $ε^{-1}$-type fast rates for decision making under reverse KL regularization, in contrast to the standard $ε^{-2}$-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in $\tilde{O}(ε^{-2})$ slow rates. We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs. We give the first $\tilde{O}(ε^{-1})$ upper bounds in tabular and general function approximation settings, both under notions of \emph{single-policy concentrability}. In particular, our convex-analytical pipeline unifies these settings by exploiting the pessimism principle in a novel way and completely bypasses the proof routines in previous works based on the mean value theorem, which might be of independent interest. Moreover, we provide rate-optimal lower bounds, manifesting the tightness of our upper bounds in terms of statistical rates. Our lower bounds also demonstrate that the forward-KL-regularized sample complexity recovers the unregularized slow rate in the low-regularization regime, similarly to the reverse-KL regularization.

Related papers

• Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic [3.756550107432323]
  entropy regularization is widely used to stabilize and accelerate Natural Policy Gradient methods.<n>We analyze a single-loop, entropy-regularized Natural Actor-Critic.<n>By training an uncentered critic, our critic tracking can remain stable even as the training policy approaches determinism.
  arXiv  Detail & Related papers  (2026-08-20T03:08:33Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Optimal Rates in Continual Linear Regression via Increasing Regularization [39.30412893918111]
  We study realizable continual linear regression under random task orderings.<n>In this setup, the worst-case expected loss after $k$ learning admits a lower bound of $Omega (1/k)$.<n>We use two frequently used regularization schemes: explicit isotropic $ell$ regularization, and implicit regularization via finite step budgets.
  arXiv  Detail & Related papers  (2025-06-06T19:51:14Z)
• Logarithmic Regret for Online KL-Regularized Reinforcement Learning [51.113248212150964]
  KL-regularization plays a pivotal role in improving efficiency of RL fine-tuning for large language models.<n>Despite its empirical advantage, the theoretical difference between KL-regularized RL and standard RL remains largely under-explored.<n>We propose an optimistic-based KL-regularized online contextual bandit algorithm, and provide a novel analysis of its regret.
  arXiv  Detail & Related papers  (2025-02-11T11:11:05Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Shifted Composition III: Local Error Framework for KL Divergence [12.93725028754563]
  Coupling arguments are a central tool for bounding the deviation between two processes.<n>We adapt coupling arguments to the Kullback-Leibler (KL) divergence.
  arXiv  Detail & Related papers  (2024-12-23T21:40:01Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  We prove new convergence rates for a generalized version of Nesterov acceleration underrho conditions.<n>Our analysis reduces the dependence on the strong growth constant from $$ to $sqrt$ as compared to prior work.
  arXiv  Detail & Related papers  (2024-04-03T00:41:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.