mlsanityData to 14 Oct 2026

Fast Rates for Offline Q-Learning with KL Regularization

arXiv 2610.18839 ↗First posted 13 Oct 2026cs.LG cs.AIcited by 0

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

Abstract (arXiv)

This paper investigates offline Q-learning for finite-horizon Markov decision processes with Kullback-Leibler (KL) regularization. Recent studies have shown that KL regularization can yield fast rates in offline decision-making problems. However, it remains unclear whether Q-learning, which adopts incremental stochastic approximation updates, can achieve such fast rates in the offline setting. We first propose KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning. By exploiting KL regularization, we prove that KLQ achieves a sample complexity of widetildeO(1/ε) without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, we further propose KL-regularized Pessimistic Q-Learning (KLPQ), which incorporates pessimism into KLQ. We prove that KLPQ retains the same (widetilde O(1/ε)) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of our knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 45 of its 51 references that are in the map. First posted on arXiv 13 Oct 2026.

Builds on

45 of 51 references.

Closest ancestors · 6

Same direction, newest first

  1. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification4 Jun
  2. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning20 Jan
  3. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning11 Feb
  4. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set31 Jan
  5. 2024Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach11 Mar
  6. 2024Regularized Q-Learning with Linear Function Approximation26 Jan

Other references · 39

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  5. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  6. 2019Behavior Regularized Offline Reinforcement Learningcited by 662
  7. 2018Is Q-learning Provably Efficient?cited by 487
  8. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  9. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  10. 2019A Theory of Regularized Markov Decision Processescited by 286
  11. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  12. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
27 more
  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  2. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  4. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  5. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  10. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  11. 2023Fast Rates for Maximum Entropy Explorationcited by 33
  12. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  13. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  14. 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescited by 15
  15. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  16. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 10
  17. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 10
  18. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 10
  19. 2023Demonstration-Regularized RLcited by 9
  20. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  21. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 6
  22. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 5
  23. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 5
  24. 2026Fast Rates in α-Potential Games via Regularized Mirror Descentcited by 5
  25. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 4
  26. 2026Model-based Offline RL via Robust Value-Aware Model Learning with Implicitly Differentiable Adaptive Weightingcited by 3
  27. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning
  2. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
  3. 2025Mildly Conservative Regularized Evaluation for Offline Reinforcement Learning
  4. 2023Offline Reinforcement Learning with On-Policy Q-Function Regularization
  5. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  6. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
  7. 2025Quantile Q-Learning: Revisiting Offline Extreme Q-Learning with Quantile Regression
  8. 2024ACL-QL: Adaptive Conservative Level in Q-Learning for Offline Reinforcement Learning