arXiv cs.AI· Kaixuan Ji, Qiwei Di, Heyang Zhao, Qingyue Zhao, Quanquan Gu·· 12 小时前AI 评分18
KL 正则化离线多臂老虎机的最优样本复杂度分析
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
AI 导读
研究给出 KL 正则化离线多臂老虎机样本复杂度的近乎完整刻画：在大正则化 η = Õ(ε⁻¹) 下 KL-PCB 达到 Õ(ηSAC^{π*}/ε) 的样本复杂度，在小正则化 η = Ω̃(ε⁻¹) 下则需 Ω̃(SAC^{π*}/ε²)。作者进一步给出更紧的下界，在整个正则化强度范围内与上界匹配。
正文 · AI 翻译
摘要：Kullback-Leibler（KL）正则化在离线决策中被广泛使用，并带来若干好处，这推动了近期关于 KL 正则化性能指标下离线学习样本复杂度的研究。然而，KL 正则化离线学习的精确样本复杂度在很大程度上仍未被完全刻画。本文在多臂老虎机（MAB）设定下研究这一问题。我们对 KL-PCB（Zhao et al., 2026）进行了精细分析，表明在大正则化 $\tilde{O}(\eta SAC^{\pi^*}/\epsilon)$ 下，其样本复杂度为 $\tilde{O}(\eta SAC^{\pi^*}/\epsilon)$，其中 $\eta = \tilde{O}(\epsilon^{-1})$；在小正则化 $\eta = \tilde{\Omega}(\epsilon^{-1})$ 下，其样本复杂度为 $\tilde{\Omega}(SAC^{\pi^*}/\epsilon^2)$，其中 $\eta$ 是正则化参数，$S$ 是上下文数量，$A$ 是臂的数量，$C^{\pi^*}$ 是最优策略 $\pi^*$ 处的策略覆盖系数，$\epsilon$ 是期望的次优性，$\tilde{O}$ 和 $\tilde{\Omega}$ 隐藏了所有多对数因子。我们进一步提供了一对更紧的样本复杂度下界，在整个正则化强度范围内与上界相匹配。总体而言，我们的结果对带 KL 正则化的离线多臂老虎机给出了近乎完整的刻画。
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；统计理论（math.ST）；机器学习（stat.ML） |
| 引用为： | arXiv:2605.02141 [cs.LG] |
| （或 arXiv:2605.02141v2 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2605.02141 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Kaixuan Ji [查看电子邮件]
[v1]
2026年5月4日星期一 01:46:35 UTC（160 KB）
[v2]
2026年10月26日星期一 22:28:23 UTC（163 KB）
来源：arXiv cs.AI · arxiv.org