On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization

arXiv:2605.02141v1 Announce Type: new Abstract: 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 ilde{O}(eta SAC^{pi^}/epsilon) under large regularization eta = ilde{O}(epsilon^{-1}), and a sample complexity of ilde{Omega}(SAC^{pi^}/epsilon^2) under small regularization eta = ilde{Omega}(epsilon^{-1}), where eta is the regularization parameter, S is the number of contexts, A is the number of arms, C^{pi^} policy coverage coefficient at the optimal policy pi^, epsilon is the desired sub-optimality, and ilde{O} and ilde{Omega} 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.

Source: arXiv cs.LG | 2026-05-05