揭示了带KL正则的离线多臂赌博机最优样本复杂度
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
- 基于KL正则化分析离线多臂赌博机学习性能
- 在强/弱正则下分别达到近似最优样本复杂度
- 为离线决策提供理论完备性支持，适合算法研究者
KL正则化广泛用于离线决策，但其样本复杂度尚未完全厘清。本文研究多臂赌博机（MABs）场景下的KL正则化离线学习问题。我们对KL-PCB（Zhao et al., 2026）进行精确分析，发现当正则参数η = Õ(ε⁻¹)时，样本复杂度为Õ(ηSAC^{π*}/ε)；当η = Ω̃(ε⁻¹)时，样本复杂度为Ω̃(SAC^{π*}/ε²)，其中S为上下文数，A为动作数，C^{π*}为最优策略π*的策略覆盖系数，ε为期望次优性。此外，我们给出更紧致的下界，与上界在整个正则强度范围内一致。整体结果近乎完整刻画了带KL正则的离线多臂赌博机。
原文摘要 · Abstract (English)
Kullback-Leibler (KL) regularization is widely used in offline decision-making and offers several benefits, motivating recent work on the sample complexity of offline learning with respect to KL-regularized performance metrics. Nevertheless, the exact sample complexity of KL-regularized offline learning remains largely from fully characterized. In this paper, we study this question in the setting of multi-armed bandits (MABs). We provide a sharp analysis of KL-PCB (Zhao et al., 2026), showing that it achieves a sample complexity of $\tilde{O}(ηSAC^{π^*}/ε)$ under large regularization $η= \tilde{O}(ε^{-1})$, and a sample complexity of $\tildeΩ(SAC^{π^*}/ε^2)$ under small regularization $η= \tildeΩ(ε^{-1})$, where $η$ is the regularization parameter, $S$ is the number of contexts, $A$ is the number of arms, $C^{π^*}$ policy coverage coefficient at the optimal policy $π^*$, $ε$ is the desired sub-optimality, and $\tilde{O}$ and $\tildeΩ$ hide all poly-logarithmic factors. We further provide a pair of sharper sample complexity lower bounds, which matches the upper bounds over the entire range of regularization strengths. Overall, our results provide a nearly complete characterization of offline multi-armed bandits with KL regularization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。