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

• URL: http://arxiv.org/abs/2605.02141v1
• Date: Mon, 04 May 2026 01:46:35 GMT
• Title: On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
• Abstract summary: Kullback-Leibler (KL) regularization is widely used in offline decision-making.<n>We show that it achieves a sample complexity of $tildeO(SAC*/)$ under large regularization.<n>We also provide a pair of sharper sample complexity lower bounds, which matches the upper bounds over the entire range of regularization strengths.
• Score: 54.77408659142336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\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.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  We study the complexity of smoothed learning of halfspaces on $pm 1n$ under uniform marginals in the model ofciteKM25.
  arXiv  Detail & Related papers  (2026-05-04T08:53:40Z)
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  We study the sample complexity of learning an $$-optimal policy in the Shortest Path (SSP) problem.<n>We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.<n>Surprisingly, this implies that whenever $c_min = 0$ an SSP problem may not be learnable.
  arXiv  Detail & Related papers  (2026-04-17T14:47:52Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
  We show a novel notion of sparsity that we dub $(lambda, beta)$-sparsity.<n>In short, there is a set of at most $beta$ groups whose risks at $theta$ all are at least $lambda$ larger than the risks of the other groups.<n>We show how to get a dimension-free semi-adaptive sample complexity bound with a computationally efficient method.
  arXiv  Detail & Related papers  (2024-10-01T13:45:55Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  We show a problem where the unknown reward $g(gamma, v)$ depends on the proposed threshold $gamma$ and latent value $v$ and it can be $only$ achieved if the threshold is lower than or equal to the unknown latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring.
  arXiv  Detail & Related papers  (2023-12-07T19:30:08Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  We develop an estimator for the optimal policy of average reward MDPs with a sample complexity of $widetilde O(|S||A|t_textmix2 epsilon-2)$. This marks the first algorithm and analysis to reach the literature's lower bound.
  arXiv  Detail & Related papers  (2023-10-13T03:08:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.