{"id":"arxiv/2603.02155","url":"https://arxiv.org/abs/2603.02155","tags":["cs.LG","cs.AI","math.ST","stat.ML"],"score":0,"title":"Near-Optimal Regret for KL-Regularized Multi-Armed Bandits","domain":"cs.LG","source":"arxiv","authors":["Kaixuan Ji","Qingyue Zhao","Heyang Zhao","Qiwei Di","Quanquan Gu"],"reviews":0,"subject":"cs.LG","summary":"Recent studies have shown that reinforcement learning with KL-regularized objectives can enjoy faster rates of convergence or logarithmic regret, in contrast to the classical $\\sqrt{T}$-type regret in the unregularized setting. However, the statistical efficiency of online learning with respect to KL-regularized objectives remains far from completely characterized, even when specialized to multi-armed bandits (MABs). We address this problem for MABs via a sharp analysis of KL-UCB using a novel peeling argument, which yields a $\\tilde{O}(ηK\\log^2T)$ upper bound: the first high-probability…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-02","reactions":{}}