cs.LGNov 12, 2026

Offline KL-Regularized Reinforcement Learning with Stochastic Transitions

Authors: Andrew Liu

Abstract

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.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Nov 10, 2026

Sharp Sample Complexity of KL-Regularized Reinforcement Learning

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.
May 9, 2026

Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Kullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms in the form of reverse or forward KL. Recent studies have demonstrated ε−1ε^{-1}-type fast rates for decision making under reverse KL regularization, in contrast to the standard ε−2ε^{-2}-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in O~(ε−2)\tilde{O}(ε^{-2}) slow rates. We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs. We give the first O~(ε−1)\tilde{O}(ε^{-1}) upper bounds in tabular and general function approximation settings, both under notions of single-policy concentrability. In particular, our convex-analytical pipeline unifies these settings by exploiting the pessimism principle in a novel way and completely bypasses the proof routines in previous works based on the mean value theorem, which might be of independent interest. Moreover, we provide rate-optimal lower bounds, manifesting the tightness of our upper bounds in terms of statistical rates. Our lower bounds also demonstrate that the forward-KL-regularized sample complexity recovers the unregularized slow rate in the low-regularization regime, similarly to the reverse-KL regularization.
May 4, 2026

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

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 O~(ηSACπ∗/ε)\tilde{O}(ηSAC^{π^*}/ε) under large regularization η=O~(ε−1)η= \tilde{O}(ε^{-1}), and a sample complexity of Ω~(SACπ∗/ε2)\tildeΩ(SAC^{π^*}/ε^2) under small regularization η=Ω~(ε−1)η= \tildeΩ(ε^{-1}), where ηη is the regularization parameter, SS is the number of contexts, AA is the number of arms, Cπ∗C^{π^*} policy coverage coefficient at the optimal policy π∗π^*, εε is the desired sub-optimality, and O~\tilde{O} and Ω~\tildeΩ 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.