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

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

    Nov 14, 2026Matthew Zurek, Yudong ChenReinforcement LearningSample-Efficient RL

  2. Fast Rates for Offline Q-Learning with KL Regularization

    Oct 13, 2026Yize Hao, Guangxin Jiang, Shuang QiuOffline RLQ-Learning