mlsanityData to 7 Oct 2026

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

arXiv 2605.02141 ↗First posted 4 May 2026cs.LG cs.AI math.STcited by 2

Not on the map. Why?

Abstract (arXiv)

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 tildeO(η SACπ^*/ε) under large regularization η = tildeO(ε-1), and a sample complexity of tildeOmega(SACπ^*/ε2) under small regularization η = tildeOmega(ε-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 tildeO and tildeOmega 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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 50 of its 76 references that are in the map. First posted on arXiv 4 May 2026.

Builds on

50 of 76 references.

References · 50

  1. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  3. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  4. 2024SimPO: Simple Preference Optimization with a Reference-Free Rewardcited by 951
  5. 2019Behavior Regularized Offline Reinforcement Learningcited by 654
  6. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  7. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  8. 2016Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collectioncited by 312
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  10. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  11. 2024Step-DPO: Step-wise Preference Optimization for Long-chain Reasoning of LLMscited by 265
  12. 2024From r to Q^*: Your Language Model is Secretly a Q-Functioncited by 242
38 more
  1. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  2. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  5. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  6. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  8. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  9. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  10. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  11. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  12. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  13. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  14. 2019Pure Exploration with Multiple Correct Answerscited by 60
  15. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  16. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  17. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  18. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
  19. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  20. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  21. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  22. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  23. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  24. 2020On Regret with Multiple Best Armscited by 16
  25. 2021Bandits with many optimal armscited by 16
  26. 2018Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidencecited by 15
  27. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  28. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  29. 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescited by 11
  30. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  31. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  32. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  33. 2014On the Complexity of Bandit Linear Optimizationcited by 8
  34. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  35. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 3
  36. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  37. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  38. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 0
  2. 2026Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivitycited by 0