KL-regularized RL gets a sharp sample count: with a generative model, samples scale linearly in the effective horizon and temperature no longer slows learning
KL-regularized reinforcement learning, the objective behind maximum-entropy RL and RL fine-tuning of language models from human feedback, previously had guarantees whose sample counts grew with a worse power of the effective horizon, and no MDP lower bound depended on the temperature. For tabular discounted MDPs with a generative model, this work shows that a plug-in estimator, which draws a fixed number of samples per state-action pair and solves the empirical MDP, reaches KL suboptimality at the temperature scale with samples linear in the effective horizon, and that no algorithm, even one choosing where to sample, can do with fewer.