Skip to main content
Back to timeline
arXivSource publication:

KL-regularized offline RL closes the stochastic-transition gap: reference-policy data can learn without a coverage assumption

Synopsis

KL-regularized reinforcement learning is the objective behind RL fine-tuning of language models, and its offline data are often collected by the reference policy itself, yet the sample size needed was known mainly for bandits or deterministic transitions. This work gives lower and upper bounds for finite discounted MDPs with unknown stochastic transitions under two data models, a fixed design and reference-policy trajectories: pessimistic soft value iteration matches the minimax rate when the temperature is not too small, and reference-policy data covers the optimum's path events up to a power law, enough to learn with no coverage assumption.

Source-provided article image: Offline KL-Regularized Reinforcement Learning with Stochastic Transitions
arXiv

Interpretation

For offline KL-regularized learning in finite discounted MDPs with unknown stochastic transitions, the sample size now has an upper bound matching a lower bound, with coverage stated over whole paths rather than single-step bandit problems. Previous tight rates for offline KL-regularized learning covered only multi-armed bandits or deterministic transitions; existing stochastic-transition bounds multiplied per-step likelihood ratios and grew with the horizon. Under a fixed design, pessimistic soft value iteration attains the information-theoretic lower rate with high probability when the temperature is not too small, up to logarithmic factors.

The algorithm is pessimistic soft value iteration: it performs soft Bellman backups on empirical rewards and empirical transitions and subtracts a penalty at each state-action pair, biasing estimates toward caution. The penalty takes a floored Bernstein form, sized by the empirical standard deviation of observed values rather than a fixed magnitude, so well-sampled low-variance pairs are not over-penalized. The analysis writes suboptimality as a KL divergence between path laws and sums the estimation-error variance along the optimum's path; this path-level bound holds for both the fixed-design and reference-trajectory data models.

When data come from the reference policy itself, that policy covers the optimum's path events up to a power law whose exponent grows as the temperature falls. With deterministic transitions per-step likelihood ratios multiply directly into a coverage bound; with stochastic transitions that argument fails and the ratio can be unbounded. The power law is necessary on a chain construction and can multiply the sample size by a factor polynomial in temperature; yet in the same temperature range the coverage bound alone lets pessimistic soft value iteration learn from reference data with sample size polynomial in the number of state-action pairs and no coverage assumption.

Perspective

The results concern discounted MDPs with finitely many state-action pairs and unknown transitions, under two data models, fixed design and reference-policy trajectories, with sample size counted in transitions. When the temperature is not too small, pessimistic soft value iteration matches the lower bound; at smaller temperatures it needs a count burn-in or yields a slower rate. Whether rewards are known is not consistent in the source: the preliminaries list both the mean reward and the transition kernel as unknown, while the information calculation for reference trajectories and the lower-bound constructions treat rewards as known, so this report does not assert that scope.

At small temperatures the rate carries a constant that grows without bound as temperature falls, and the energy argument fails in that range. Guarantees on the reference-data side are loose: the subsampled estimator uses about a quarter of the data and treats pairs with fewer than order-one expected visits as uncovered, which can cost a polynomial factor. Whether pessimism is needed at large temperatures is unknown.