arXiv cs.AI· Qingyue Zhao, Kaixuan Ji, Heyang Zhao, Quanquan Gu·· 12 小时前AI 评分24
前向 KL 正则化离线上下文 Bandit 在单策略集中性下的快速收敛率
Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
AI 导读
针对前向 KL 正则化目标下现有分析只能得到 Õ(ε⁻²) 慢速率的问题，该研究首次在表格与一般函数逼近设定下、于单策略集中性条件下给出 Õ(ε⁻¹) 上界。其凸分析框架以新方式利用悲观原则，绕开此前基于中值定理的证明路线，并给出匹配的下界以证明速率紧致。下界还表明，前向 KL 正则化在低正则化区间会退化为无正则化的慢速率，与反向 KL 正则化类似。
正文 · 原文
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