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

Kaixuan Ji; Qingyue Zhao; Heyang Zhao; Qiwei Di; Quanquan Gu

cs.LGMar 2, 2026

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

Authors: Kaixuan Ji, Qingyue Zhao, Heyang Zhao, Qiwei Di, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

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 regret bound with linear dependence on $K$ . Here, $T$ is the time horizon, $K$ is the number of arms, $η^{-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 $Ω(η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 $η$ ), we show that the KL-regularized regret for MABs is $η$ -independent and scales as $\tildeΘ(\sqrt{KT})$ . Overall, our results provide a thorough understanding of KL-regularized MABs across all regimes of $η$ and yield nearly optimal bounds in terms of $K$ , $η$ , and $T$ .

Figures & tables

Type	Algorithm	Setting	Regret/Sample Complexity	Matching Lower Bound?
	Online Iterative GSHF
	( Xiong et al., 2024 )	Preference w/ Linear Reward	$O(d^{2}/\epsilon^{2})$	✗
	TMPS
	( Zhao et al., 2025a )	Data Coverage	$\widetilde{O}\big((\eta^{2}C_{\mathrm{GL}}^{2}+\eta/\epsilon)\log(N_{\mathcal{R}})\big)$	✗
Upper Bound	Greedy Sampling
	( Wu et al., 2025a )	Preference w/ Eluder Dimension	$\widetilde{O}\big(\exp(\eta)d_{\mathcal{R}}\log T\log(N_{\mathcal{R}})\big)$	✗

Table 1: Comparison of regret or sample complexity upper and lower bounds for KL-regularized bandits. In this table,

T

denotes total rounds of interactions,

\epsilon

the target suboptimality gap, and

\eta

the KL regularization coefficient. For linear setting,

d

denotes the dimension of the feature map. For general function approximation,

\mathcal{R}

is the function class, whose eluder dimension is

d_{\mathcal{R}}

and covering number is

N_{\mathcal{R}}

, and

C_{\mathrm{GL}}^{2}

is an instance-dependent constant that might be arbitrarily large. In the MAB setting,

K

denotes the number of arms.

\widetilde{O}(\cdot)

hides logarithmic factors except

\log T

and

\log(N_{\mathcal{R}})

. A checkmark (✓) indicates that a matching (up to logarithmic factors) lower bound is known for the corresponding setting, while a cross (✗) indicates that no tight lower bound is currently available in its original setting and cannot match the lower bound when specialized to MAB.

Figure 1: The near-comprehensive picture of KL-regularized MABs rendered in this paper. All logarithmic factors except

\log T

are omitted to avoid clutter.

\displaystyle{\bar{r}}_{t}(a)\leftarrow\frac{1}{N_{t}(a)\vee 1}\sum_{i=1}^{t}r_{i}\ind\{a_{i}=a\},\quad b_{t}(a)\leftarrow\sqrt{\frac{2\log(TK/\delta)}{N_{t}(a)\vee 1}}

Algorithm 1 KL-regularized Upper Confidence Bound Algorithm ( KL-UCB )

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 2: The shared uniform Bayes prior for every

t\geq\eta^{2}K

. The plot above takes

1

out of

K

axes of

\mathsf{Unif}\big([-\alpha,+\alpha]^{K}\big)

for illustration. The gray boxes denote the density of

\mathbf{x}

and hence the red boxes represent the density of

\mathbf{x}+{\bm{\mu}}\delta_{t}

Explore similar work

May 4, 2026

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

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

η= \tilde{O}(ε^{-1})

, and a sample complexity of

\tildeΩ(SAC^{π^*}/ε^2)

under small regularization

η= \tildeΩ(ε^{-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

\tilde{O}

and

\tildeΩ

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.

Kaixuan Ji, Qiwei Di, Heyang Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Sample Complexity Robust Multi-Armed Bandits Offline RL

Ask PDF

May 9, 2026

Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Kullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms in the form of reverse or forward KL. Recent studies have demonstrated

ε^{-1}

-type fast rates for decision making under reverse KL regularization, in contrast to the standard

ε^{-2}

-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in

\tilde{O}(ε^{-2})

slow rates. We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs. We give the first

\tilde{O}(ε^{-1})

upper bounds in tabular and general function approximation settings, both under notions of single-policy concentrability. In particular, our convex-analytical pipeline unifies these settings by exploiting the pessimism principle in a novel way and completely bypasses the proof routines in previous works based on the mean value theorem, which might be of independent interest. Moreover, we provide rate-optimal lower bounds, manifesting the tightness of our upper bounds in terms of statistical rates. Our lower bounds also demonstrate that the forward-KL-regularized sample complexity recovers the unregularized slow rate in the low-regularization regime, similarly to the reverse-KL regularization.

Qingyue Zhao, Kaixuan Ji, Heyang Zhao +1

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

KL-Regularized RL Contextual Bandits

Ask PDF

Sep 11, 2026

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

We study KL-regularized contextual bandits under both reward and preference feedback. While existing regret guarantees typically depend on the eluder dimension, we show that simple greedy sampling can achieve polylogarithmic regret without explicit dependence on this complexity measure. For reward feedback, we analyze a greedy algorithm that samples directly from the Gibbs policy induced by the estimated reward. We extend the result to preference feedback under both general preference and Bradley--Terry models, while also sharpening existing dimension-dependent guarantees. Our analysis reveals a trade-off between greedy sampling and upper confidence bound-style exploration: greedy sampling enjoys stronger regret guarantees when KL regularization is sufficiently strong, whereas additional exploration yields sharper bounds as the regularization weakens.

Zichen Wang, Haoyang Hong, Huazheng Wang

Department of ECE and CSL, University of Illinois Urbana-Champaign · School of Electrical Engineering and Computer Science, Oregon State University

Contextual Bandits

Ask PDF