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

arXiv: https://arxiv.org/abs/2603.02155 · HTML: https://mlsanity.com/paper/2603.02155/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 28 of 28)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Understanding the impact of entropy on policy optimization](https://mlsanity.com/paper/1811.11214/) (2018)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration](https://mlsanity.com/paper/2503.07453/) (2025)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization](https://mlsanity.com/paper/2410.09302/) (2024)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games](https://mlsanity.com/paper/2510.13060/) (2025)
- [Regularization Matters in Policy Optimization](https://mlsanity.com/paper/1910.09191/) (2019)
- [KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/2205.14211/) (2022)
- [Greedy Sampling Is Provably Efficient for RLHF](https://mlsanity.com/paper/2510.24700/) (2025)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2305.08359/) (2023)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)

## Built on by (most cited first, 5 of 5)

- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence](https://mlsanity.com/paper/2609.13564/) (2026)
- [Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectives](https://mlsanity.com/paper/2609.38666/) (2026)
- [Fast Rates for Offline Q-Learning with KL Regularization](https://mlsanity.com/paper/2610.18839/) (2026)

## 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.