前向 KL 正则化在单策略集中度下实现离线上下文赌博机的快速速率
Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
AI 导读
一项 arXiv 研究针对前向 KL 正则化的离线上下文赌博机（CB），给出首个 Õ(ε⁻¹) 上界，覆盖表格型与一般函数逼近两种设定，且均在单策略集中度条件下成立。该方法借助凸分析与悲观原理统一处理两种设定，绕开了以往基于中值定理的证明路线，并给出速率最优的下界，同时表明低正则化区间的样本复杂度退化为未正则化的慢速率。
正文 · 原文
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 $\epsilon^{-1}$-type fast rates for decision making under reverse KL regularization, in contrast to the standard $\epsilon^{-2}$-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in $\tilde{O}(\epsilon^{-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}(\epsilon^{-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.
| Comments: | 36 pages, camera-ready version |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Information Theory (cs.IT); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2605.09214 [cs.LG] |
| (or arXiv:2605.09214v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.09214 arXiv-issued DOI via DataCite |
Submission history
From: Qingyue Zhao [view email]
[v1]
Sat, 9 May 2026 23:17:46 UTC (52 KB)
[v2]
Wed, 4 Nov 2026 23:30:31 UTC (71 KB)
来源：arXiv cs.AI · arxiv.org