Offline KL-Regularized Reinforcement Learning with Stochastic Transitions

Andrew LiuarXiv 2026 · arXiv

TL;DR

This paper establishes the first tight sample complexity bounds for offline KL-regularized reinforcement learning in stochastic environments—the mathematical framework underpinning RL fine-tuning for large language models. The author proves that while stochastic transitions make data coverage more challenging, pessimistic algorithms can efficiently find optimal policies even when the reference data is sparse, whereas standard "plug-in" estimators may fail.

What Problem Does This Paper Address?

Reinforcement Learning from Human Feedback (RLHF) typically involves fine-tuning a language model to maximize rewards while staying close to a reference model ($\pi_{ref}$) via KL-regularization. While researchers have a good handle on how much data this requires for simple "bandit" problems (single-step decisions), real-world applications often involve multi-step sequences with stochastic transitions.

Until now, we didn't know the fundamental limits of how much offline data is needed to solve these multi-step problems. Specifically, if our data comes from the reference policy itself (which is common in LLM training), does it provide enough coverage to find the optimal policy? The challenge is that in stochastic environments, the probability of following an optimal path can be exponentially smaller than in the reference data, potentially leading to a "needle in a haystack" problem.

Methods

The author analyzes finite discounted Markov Decision Processes (MDPs) with $K$ state-action pairs and an effective horizon $H$. The study focuses on two data models:

  1. Fixed Design (D1): Data is sampled i.i.d. from a fixed distribution.
  2. Reference Trajectories (D2): Data consists of full trajectories generated by the reference policy $\pi_{ref}$.

The primary algorithm studied is Pessimistic Soft Value Iteration (PSVI). Unlike standard value iteration, PSVI subtracts a penalty term (a "pessimistic" bias) based on the variance of the estimated values. This prevents the agent from over-optimistically pursuing actions for which it has little data. The author specifically employs a "floored Bernstein penalty," which is variance-aware and allows for tighter bounds than simpler Hoeffding-based penalties.

Datasets

The paper is primarily theoretical, providing mathematical proofs for lower and upper bounds. However, the author validates these theories using:

  • Random MDPs: Small-scale environments with Dirichlet transition kernels and uniform rewards to test the tightness of the derived inequalities.
  • The "Loop Family": A specific MDP construction designed to test how sample complexity scales with the horizon $H$.
  • The "Plug-in Failure" Instance: A specially constructed MDP where many actions are rare, used to demonstrate that standard estimators fail at low temperatures while pessimistic ones succeed.

Key Insights and Ideas

  • Path-Space Pessimism: The author shows that suboptimality in regularized RL can be viewed as a KL divergence between the "path laws" of the learned policy and the optimal policy. This allows for a more global analysis of error than step-by-step approaches.
  • The Power Law of Coverage: A major finding is that even if the reference policy $\pi_{ref}$ doesn't perfectly cover the optimal policy $\pi^*$, it covers it "up to a power law." Specifically, a path event that is likely under $\pi^*$ will still have a non-negligible (polynomial, not exponentially small) probability under $\pi_{ref}$, provided the regularization temperature $\beta$ is high enough.
  • Pessimism is Essential: The "plug-in" estimator (which simply uses the empirical mean of observed data) is minimax optimal when you have a generative model (the ability to sample any state-action pair). However, in the offline setting where you only have reference data, the plug-in estimator can fail completely at low temperatures, whereas PSVI remains robust.
  • Temperature Threshold: The "fast" $H^3$ rate for sample complexity is achieved when the temperature $\beta \geq 1.4H$. Below this threshold, the problem starts to behave more like unregularized RL, which is significantly harder to analyze.

Key Results

The paper provides a comprehensive map of sample complexity, summarized in the table below:

Table 1: Sample complexities for offline KL-regularized RL. C represents concentrability (data coverage), K is the number of state-action pairs, H is the horizon, and $\beta$ is the temperature.
  • Lower Bound: The author proves that any estimator requires at least $\Omega(KCH^3 / (\epsilon \max\{\epsilon, \beta\}))$ samples to achieve $\epsilon$-suboptimality.
  • Matching Upper Bound: PSVI with a Bernstein penalty matches this lower bound (up to logarithmic factors) when $\beta \geq 1.4H$.
  • Scaling with Horizon: In simulations on the "loop family," the mean regularized loss for PSVI with Bernstein penalties grew as $H^2$, significantly outperforming the $H^3$ growth seen with simpler Hoeffding penalties.

Limitations and Future Work

  • Temperature Range: The tightest results currently require $\beta \geq 1.4H$. Extending the $H^3$ rate to lower temperatures without requiring a large "burn-in" period of samples remains an open challenge.
  • Constant Factors: The mathematical constants derived in the proofs are quite large. While they prove the rate of convergence is optimal, the bounds are not yet practical for predicting the exact number of samples needed in a real-world LLM training run.
  • Function Approximation: This work focuses on the "tabular" setting (finite states and actions). A natural next step is extending these path-level pessimistic analyses to linear or neural function approximation, which is more representative of modern deep RL.

Summary updated

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, $K$ state-action pairs and effective horizon $H$. For data that cover the regularized optimum with concentrability $C\geq 4$, every estimator needs $Ω(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 $β\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/β$; in the same temperature range, this power law alone gives the estimator a sample complexity polynomial in $1/ε$, with no coverage assumption. For $β\geq H$ the power can also increase the sample size needed by a factor polynomial in $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.
BibTeX
@misc{liu2026offline,
  author = {Andrew Liu},
  title = {{Offline KL-Regularized Reinforcement Learning with Stochastic Transitions}},
  year = {2026},
  eprint = {2611.17603},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17603},
}
Figure