On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
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 Õ(ηSACπ*/ε) under large regularization η= Õ(ε−1), and a sample complexity of Ω̃(SACπ*/ε2) under small regularization η= Ω̃(ε−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 Õ and Ω̃ 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.
Related
- Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
- Expected Sample Complexity in Multi-Armed Bandits
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery
BibTeX
@misc{ji2026optimal,
title = {{On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization}},
author = {Kaixuan Ji and Qiwei Di and Heyang Zhao and Qingyue Zhao and Quanquan Gu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.02141},
eprint = {2605.02141},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.02141},
}
RIS
TY - UNPB
TI - On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
AU - Kaixuan Ji
AU - Qiwei Di
AU - Heyang Zhao
AU - Qingyue Zhao
AU - Quanquan Gu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2605.02141
UR - https://arxiv.org/abs/2605.02141
AB - 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 Õ(ηSAC^π^*/ε) under large regularization η= Õ(ε^−1), and a sample complexity of Ω̃(SAC^π^*/ε^2) under small regularization η= Ω̃(ε^−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 Õ and Ω̃ 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.
ER -