{"id":"arxiv/2605.02141","url":"https://arxiv.org/abs/2605.02141","tags":["cs.LG","cs.AI","math.ST","stat.ML"],"score":0,"title":"On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization","domain":"cs.LG","source":"arxiv","authors":["Kaixuan Ji","Qiwei Di","Heyang Zhao","Qingyue Zhao","Quanquan Gu"],"reviews":0,"subject":"cs.LG","summary":"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 $η=…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}