Sharp Sample Complexity of KL-Regularized Reinforcement Learning
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 guarantees scale with in the effective horizon , and no lower bound for MDPs depends on the temperature . In this work, we show that for a discounted MDP with state-action pairs, the plug-in estimator finds a policy that is -optimal from every initial state with samples, and that no algorithm, even one that chooses where to sample, can do with fewer when . For this is a 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
| Reference | Setting | Upper bound | Lower bound |
|---|---|---|---|
| Gheshlaghi Azar et al. (2013) ; Li et al. (2024b) | generative, | ||
| Lan (2023) | generative | – | |
| Jia and Lan (2026) | generative | – | |
| Tiapkin et al. (2023) (remark) | generative | rate, no explicit | – |
| Tiapkin et al. (2024) | online, episodic | – | |
| Hao et al. (2026) | offline, episodic | – |
| instance | design | constant | measured | gain (theory / measured) | |
|---|---|---|---|---|---|
| gadget, | 5 | uniform | 888.4 | 899.8 23 | 2.50 / 2.57 |
| gadget, | 5 | optimal | 355.4 | 350.6 9.1 | |
| Garnet, , | 40 | uniform | 12.9 | 12.95 0.1 | 1.50 / 1.52 |
| Garnet, , | 40 | optimal | 8.625 | 8.539 0.052 | |
| Garnet, , | 40 | uniform | 13.62 | 13.92 0.21 | 2.19 / 2.23 |
| Garnet, , | 40 | optimal | 6.23 | 6.247 0.051 |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| fast, worst case over | fast, | Thm. 3 constant | slow | |
|---|---|---|---|---|
| 5 | 1.424 0.066 | 1.5458 0.0013 | 1.5469 | 0.047 0.003 |
| 10 | 16.31 0.78 | 18.505 0.015 | 18.51 | 0.054 0.004 |
| 20 | 184.5 9.5 | 177.79 0.15 | 177.68 | 0.059 0.004 |
| 40 | 1561 77 | 1551.1 1.3 | 1550.7 | 0.071 0.005 |
| 80 | 13200 600 | 12940 11 | 12945 | 0.071 0.004 |
| 160 | 103700 4800 | 105720 86 | 105770 | 0.071 0.004 |
| instance | constant | measured | ratio | |
|---|---|---|---|---|
| gadget, , , | 177.7 | 168.1 4 | 0.946 | |
| gadget, , , | 177.7 | 177.9 4.6 | 1.001 | |
| gadget, , , | 177.7 | 177.3 4.6 | 0.998 | |
| gadget, , , | 150.5 | 145.1 3.5 | 0.964 | |
| gadget, , , | 150.5 | 148.7 3.8 | 0.988 | |
| gadget, , , | 150.5 | 153.7 4.1 | 1.021 |
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,847 papers