mlsanityData to 14 Oct 2026

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

arXiv 2603.02155 ↗First posted 2 Mar 2026cs.LG cs.AI math.STcited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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 √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 tildeO(η Klog2T) 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 tildeO 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(η 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 tildeTheta(√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.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 28 of its 57 references that are in the map. First posted on arXiv 2 Mar 2026.

Builds on

28 of 57 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games15 Oct
  2. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning11 Feb
  3. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits9 Feb

Other references · 25

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  4. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  6. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  7. 2019A Theory of Regularized Markov Decision Processescited by 286
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  9. 2017A unified view of entropy-regularized Markov decision processescited by 182
  10. 2018Understanding the impact of entropy on policy optimizationcited by 176
  11. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  12. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
13 more
  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 36
  3. 2023Fast Rates for Maximum Entropy Explorationcited by 33
  4. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2024Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimizationcited by 22
  7. 2019Regularization Matters in Policy Optimizationcited by 13
  8. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  9. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  10. 2022Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Banditscited by 5
  11. 2025Improved Bounds for Private and Robust Alignmentcited by 5
  12. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  13. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 4
  2. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3
  3. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 1
  4. 2026Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectivescited by 0
  5. 2026Fast Rates for Offline Q-Learning with KL Regularizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
  2. 2026Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
  3. 2026Regret Analysis of Retry-Based Bandits
  4. 2025Regret Bounds for Robust Online Decision Making
  5. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences
  6. 2026Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
  7. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  8. 2026Vanishing L2 regularization for the softmax Multi Armed Bandit