Near-Optimal Regret for KL-Regularized Multi-Armed Bandits

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 (Zhao et al., 2025b) using a novel peeling argument, which yields a $\tilde{O}(\eta K\log^2T)$ KL-regularized regret upper bound: the first high-probability regret bound with linear dependence on $K$. Here, $T$ is the time horizon, $K$ is the number of arms, $\eta^{-1}$ is the regularization intensity, and $\tilde{O}$ hides all logarithmic factors except those involving $\log T$. The near-tightness of our analysis is certified by the first non-constant lower bound $\Omega(\eta K \log T)$, which follows from subtle hard-instance constructions and a tailored decomposition of the Bayes prior. Moreover, in the low-regularization regime (i.e., large $\eta$), we show that the KL-regularized regret for MABs is $\eta$-independent and scales as $\tilde{\Theta}(\sqrt{KT})$. Overall, our results provide a thorough understanding of KL-regularized MABs across all regimes of $\eta$ and yield nearly optimal bounds in terms of $K$, $\eta$, and $T$.

Reinforcement learning with KL regularization is widely used in modern AI systems, including robotic learning, recommendation systems, and large language model alignment, because it encourages models to improve while remaining close to a reference behavior. Despite its practical success, the optimal strategy of learning with KL regularization is still poorly understood. In this paper, we study this question in the multi-armed bandit setting, a fundamental model of online decision making. We show that KL regularization fundamentally changes the difficulty of learning. When regularization is strong, the learner can achieve regret that grows only logarithmically with the number of interactions, a dramatic improvement over the classical square-root regret in standard bandits. When regularization is weak, the problem behaves similarly to standard bandits and admits the classical square-root regret. We develop a new analysis of an optimistic exploration algorithm and prove nearly matching upper and lower bounds on regret, providing the first near-complete theoretical characterizations of KL-regularized online learning.