Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
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 Õ(ε−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 Õ(ε−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
- On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Diversified Multinomial Logit Contextual Bandits
- Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
BibTeX
@misc{zhao2026fast,
title = {{Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability}},
author = {Qingyue Zhao and Kaixuan Ji and Heyang Zhao and Quanquan Gu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.09214},
eprint = {2605.09214},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.09214},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
AU - Qingyue Zhao
AU - Kaixuan Ji
AU - Heyang Zhao
AU - Quanquan Gu
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.09214
UR - https://arxiv.org/abs/2605.09214
AB - \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 Õ(ε^−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 Õ(ε^−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.
ER -