The paper studies the sample complexity of KL‑regularized reinforcement learning, which is equivalent to variational inference in the control‑as‑inference framework. It proves that a plug‑in estimator achieves ε‑optimality with ≥O(KH^3/(ε max{ε,β}) + KH) samples, and establishes a matching lower bound for ε ≤ min{H, H^2/β}. The authors also identify the exact asymptotic constant of the estimator and provide optimal sample allocations for adaptive designs, with simulations confirming the theoretical rates.
By Andrew Liu
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.
The paper presents the first ≥O(ε^{-1}) upper bounds for offline contextual bandits with forward-KL regularization under single-policy concentrability, covering both tabular and general function approximation settings. It introduces a convex-analytical approach that leverages pessimism in a novel way, avoiding previous mean value theorem-based proofs. The authors also provide matching lower bounds, showing the tightness of their rates and that the forward-KL sample complexity reverts to the unregularized slow rate when regularization is weak.
By Qingyue Zhao, Kaixuan Ji, Heyang Zhao, Quanquan Gu
arXiv:2610.08963v1 Announce Type: new
Abstract: Asynchronous reinforcement learning (RL) for large language model (LLM) agents trains one policy on trajectories generated by another: rollouts come fr...
By Yifan Zhang
arXiv:2605. 02141v2 Announce Type: replace-cross Abstract: 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.
By Kaixuan Ji, Qiwei Di, Heyang Zhao, Qingyue Zhao, Quanquan Gu
arXiv:2603. 02155v2 Announce Type: replace Abstract: Recent studies have shown that reinforcement learning with KL-regularized objectives can enjoy faster rates of convergence or logarithmic regret, in contrast to the classical $\sqrt{T}$-type regret in the unregularized setting.
By Kaixuan Ji, Qingyue Zhao, Heyang Zhao, Qiwei Di, Quanquan Gu