Tight Sample Complexity of KL-Regularized Reinforcement Learning: New Bounds and Lower Bounds

The plug-in estimator for KL-regularized RL achieves minimax-optimal sample complexity, reducing the exponent of H from 5 to 3 and revealing the role of temperature β.
This paper studies the sample complexity of KL-regularized reinforcement learning, the core objective of maximum entropy RL and RLHF. For discounted MDPs, the authors propose a plug-in estimator and prove a sample complexity upper bound of \widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH), reducing the exponent of the effective horizon H from 5 to 3. They also prove a matching lower bound, showing the estimator is minimax optimal for ε \lesssim \min\{H, H^2/β\}. In particular, when ε < β, the sample complexity is Θ(KH^3/ε), the same as unregularized RL, indicating that KL regularization does not increase learning difficulty. The authors also characterize the exact asymptotic constant (the Fisher-weighted variance of the soft Q-function) and give the optimal sample allocation strategy under adaptive design. Simulation experiments verify the theoretical results. This work deepens the understanding of the sample complexity of KL-regularized RL and provides theoretical guidance for RLHF and maximum entropy RL algorithm design.
Title
Tight Sample Complexity of KL-Regularized Reinforcement Learning: New Bounds and Lower Bounds
Meta Description
This article presents the latest theoretical advances in the sample complexity of KL-regularized reinforcement learning: the plug-in estimator achieves a sample complexity of O~(KH^3/(εmax{ε,β})+KH) and a matching lower bound is proven, improving the effective horizon dependence from H^5 to H^3, and revealing the influence of temperature β for the first time.
Article Content
KL-regularized reinforcement learning is the core objective function behind maximum entropy reinforcement learning and reinforcement learning from human feedback (RLHF); it is essentially a variational inference problem in the "control as inference" graphical model. In this framework, the regularized optimal policy is a posterior distribution over trajectory space, and the suboptimality of a policy equals β times the KL divergence between path measures. However, how to efficiently learn this posterior distribution from samples—even with access to a generative model—has not been precisely characterized in terms of sample complexity.
A recent theoretical study fills this gap: for discounted MDPs, the authors provide a tight sample complexity upper bound for the plug-in estimator and prove a matching lower bound, showing that the estimator is minimax optimal over a wide parameter range. This work not only reduces the exponent of the effective horizon H in previous guarantees from the fifth power to the third power, but also reveals for the first time the key role of the temperature parameter β in sample complexity.

Problem Background: From Control as Inference to Sample Complexity
Classical reinforcement learning seeks to maximize cumulative reward, whereas KL-regularized reinforcement learning adds an additional KL divergence penalty between the policy and a reference policy to the objective. This form is extremely common in maximum entropy RL and RLHF, and its optimal policy can be obtained via Bayesian inference: treating rewards as observations and the policy as the posterior. Mathematically, the regularized optimal policy p* satisfies p*(τ) ∝ p0(τ) exp(A(τ)/β), where A is the advantage function and β is the temperature parameter.
Although this inference perspective is elegant, in practice we can only approximate the posterior via sampling. Prior work gave a sample complexity guarantee of 1/ε, but its dependence on the effective horizon H was as high as H^5, and the lower bound did not reflect the influence of β. For practical algorithm design, understanding how sample complexity scales with H and β is crucial.
Variational Inference and Posterior Distribution: In the "control as inference" framework, the reinforcement learning problem is transformed into an inference problem on a probabilistic graphical model. Specifically, trajectories are treated as latent variables and rewards as observations, and the optimal policy corresponds to the posterior distribution over trajectories given the observations. Since the exact posterior is difficult to compute, variational inference is typically used, i.e., finding the distribution closest to the true posterior within a policy family by minimizing KL divergence. The resulting variational objective is exactly equivalent to the objective of KL-regularized reinforcement learning, where the KL penalty term corresponds to the KL term in the evidence lower bound (ELBO) of variational inference. This connection explains why the regularized optimal policy in maximum entropy RL and RLHF has a closed form, and provides a statistical inference perspective for sample complexity analysis.
Main Results: Upper and Lower Bounds Match
The paper considers a discounted MDP with K state-action pairs. The authors prove that the plug-in estimator—which first estimates the soft Q-function and then derives a greedy policy—can find a policy that is ε-optimal from every initial state using \widetilde{O}(KH^3/(ε\max{ε,β}) + KH) samples. This upper bound exhibits a 1/ε rate when ε < β, and its dependence on H is the same as in unregularized RL (H^3). When ε is large, the sample complexity is inversely proportional to β, reflecting the impact of regularization strength on learning difficulty.
More critically, the authors prove a matching lower bound: any algorithm, even if allowed to actively choose sampling locations, cannot use fewer samples when ε \lesssim \min{H, H^2/β}. This means the plug-in estimator is minimax optimal in this range. In particular, when ε < β, the sample complexity is exactly Θ(KH^3/ε), consistent with the unregularized case, indicating that KL regularization does not increase learning difficulty (when ε is small).
Minimax Optimality: In statistical decision theory, minimax optimality means that an estimator's worst-case risk (here, sample complexity) is optimal compared to any other estimator, i.e., it attains the lower bound. Specifically, in this paper, the authors prove that the sample complexity upper bound of the plug-in estimator matches the lower bound of any algorithm (even allowing adaptive sampling) up to constant factors, thereby establishing the minimax optimality of the estimator within the given parameter range. This property implies that no algorithm can significantly outperform the plug-in estimator, providing a theoretical guarantee for its practicality.
Exact Asymptotic Constant and Adaptive Design
Beyond rates, the authors also characterize the exact asymptotic constant of the plug-in estimator: it is the Fisher-weighted variance of the estimated soft Q-function. This constant reveals the distributional properties of the estimation error and shows that the estimator is locally asymptotically minimax optimal among methods that uniformly sample each state-action pair.
For adaptive design, the authors provide the optimal sample allocation strategy, i.e., allocating sampling counts according to the uncertainty of state-action pairs. Simulation experiments on small-scale MDPs verify the theoretical rates and constants, providing empirical support for the theoretical results.
Fisher-Weighted Variance: Fisher information measures the amount of information in the data about an unknown parameter, and its inverse gives the asymptotic variance lower bound for parameter estimation (the Cramér-Rao lower bound). In this paper, the exact asymptotic constant is the Fisher-weighted variance of the estimated soft Q-function, i.e., the variance of the estimation error at each state-action pair weighted by the Fisher information at that point. This constant characterizes the distributional properties of the plug-in estimator's error and shows that under uniform sampling, the estimator achieves local asymptotic minimax optimality, i.e., its asymptotic variance is of the same order as the smallest possible variance of any estimator.
Significance and Outlook
This work deepens our understanding of the sample complexity of KL-regularized reinforcement learning, improving the dependence on the effective horizon from H^5 to H^3 and revealing the role of β for the first time. This provides theoretical guidance for designing more efficient RLHF and maximum entropy RL algorithms. Future directions include extending the results to more general function approximation settings and exploring tight bounds for non-discounted MDPs.
For practitioners, this result suggests that when regularization is strong (β is large), learning the posterior may require more samples; when ε is small, regularization hardly affects sample efficiency. This helps in reasonably setting the temperature parameter and sampling budget in RLHF.
One-line Summary
The plug-in estimator for KL-regularized reinforcement learning achieves minimax-optimal sample complexity, reducing the exponent of H from 5 to 3 and revealing the role of the temperature parameter β.
Paragraph Summary
This paper studies the sample complexity of KL-regularized reinforcement learning, an objective that is central to maximum entropy RL and RLHF. For discounted MDPs, the authors propose a plug-in estimator and prove a sample complexity upper bound of \widetilde{O}(KH^3/(ε\max{ε,β}) + KH), reducing the exponent of the effective horizon H from the previous 5 to 3. They also prove a matching lower bound, showing that the estimator is minimax optimal when ε \lesssim \min{H, H^2/β}. In particular, when ε < β, the sample complexity is Θ(KH^3/ε), the same as unregularized RL, indicating that KL regularization does not increase learning difficulty. Furthermore, the authors characterize the exact asymptotic constant (the Fisher-weighted variance of the soft Q-function) and provide the optimal sample allocation strategy under adaptive design. Simulation experiments verify the theoretical results. This work deepens the understanding of the sample complexity of KL-regularized RL and provides theoretical guidance for the design of RLHF and maximum entropy RL algorithms.
Related articles

Azure HorizonDB + VS Code: A New Workbench for AI App Development
Azure Horizon DB is Microsoft's enterprise-grade Postgres service with deep VS Code integration: GitHub Copilot writes SQL, visual query plans, built-in vector indexes and AI models—database ops and AI app development in one workbench.

Apple Adds an AI Safety Valve to macOS: How New Permission Controls Address Agent Privacy Risks
Apple discloses new Mac security controls in macOS 27.3: fine-grained permissions for AI agents, runtime warnings, and operation transparency, and how they address the privacy risks of agents dynamically accessing sensitive data, plus impacts on developers and users.

Black Friday PS5 Game Sale: Major Titles Slashed
Black Friday sales start early with steep PS5 game discounts and deals on controllers and headsets. We break down the sale, top picks, and buying tips.