cs.LGNov 10, 2026

Sharp Sample Complexity of KL-Regularized Reinforcement Learning

Authors: Andrew Liu

Organizations: Columbia University

Abstract

KL-regularized reinforcement learning, the objective behind maximum-entropy RL and RL from human feedback, is variational inference in the graphical model of "control as inference": the regularized optimal policy is a posterior over trajectories, and the suboptimality of a policy is ββ times a KL divergence between path measures. However, it is not known how many samples it takes to learn this posterior, even with a generative model. Earlier 1/ε1/ε guarantees scale with H5H^5 in the effective horizon HH, and no lower bound for MDPs depends on the temperature ββ. In this work, we show that for a discounted MDP with KK state-action pairs, the plug-in estimator finds a policy that is εε-optimal from every initial state with O~(KH3/(εmax⁡{ε,β})+KH)\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH) samples, and that no algorithm, even one that chooses where to sample, can do with fewer when ε≲min⁡{H,H2/β}ε\lesssim \min\{H, H^2/β\}. For ε<βε< β this is a 1/ε1/ε rate with the same horizon dependence as unregularized RL. We also find the exact asymptotic constant of the plug-in estimator, a Fisher-weighted variance of the estimated soft Q-function. The estimator is locally asymptotically minimax among methods that sample every pair equally often, and we give the allocation of samples that is optimal among adaptive designs. Simulations on small MDPs match the rates and the constants.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Nov 12, 2026

Offline KL-Regularized Reinforcement Learning with Stochastic Transitions

KL-regularized reinforcement learning is the objective behind RL fine-tuning of language models, and its data are often collected by the reference policy itself. However, beyond bandits and deterministic transitions, little is known about how much offline data it needs. In this work, we study finite discounted Markov decision processes with unknown stochastic transitions, KK state-action pairs and effective horizon HH. For data that cover the regularized optimum with concentrability C≥4C\geq 4, every estimator needs Ω(KCH3/(εmax⁡{ε,β}))Ω(KCH^3/(ε\max\{ε,β\})) samples on some instances when εε is small, where ββ is the temperature. Under a fixed design, pessimistic soft value iteration with a variance-aware penalty attains this rate with high probability, up to logarithmic factors, when β≥1.4Hβ\geq 1.4H. When the data come from the reference policy itself, we show that it covers the optimum up to a power law whose exponent grows as H/βH/β; in the same temperature range, this power law alone gives the estimator a sample complexity polynomial in 1/ε1/ε, with no coverage assumption. For β≥Hβ\geq H the power can also increase the sample size needed by a factor polynomial in 1/ε1/ε. Finally, the plug-in estimator, which is minimax optimal with a generative model, can fail on reference data at small temperatures when many actions are rarely seen, while the pessimistic estimator does not.
Nov 14, 2026

Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an ε\varepsilon-optimal policy with O(SA(1−γ)−3ε−2log⁡(SA/δ))O(SA (1-γ)^{-3} \varepsilon^{-2} \log(SA/δ)) samples, where S,A,γ,δS, A, γ, δ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve O(SAHε−2log⁡(SA/δ))O(SAH\varepsilon^{-2}\log(SA/δ)) and O(SADε−2log⁡(SA/δ))O(SAD\varepsilon^{-2}\log(SA/δ)) complexities, respectively, where HH upper-bounds the optimal bias span and DD is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.
Oct 13, 2026

Fast Rates for Offline Q-Learning with KL Regularization

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 O~(1/ε)\widetilde{O}(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 O~(1/ε)\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.