KL 正则化强化学习的样本复杂度精确刻画
Sharp Sample Complexity of KL-Regularized Reinforcement Learning
AI 导读
一项 arXiv 研究给出了 KL 正则化强化学习的样本复杂度刻画。对于含 K 个状态-动作对的折扣 MDP，plug-in 估计器以 Õ(KH³/(ε·max{ε,β}) + KH) 样本找到每个初始状态都 ε-最优的策略，并证明了在 ε ≲ min{H, H²/β} 时该界不可改进。论文还给出估计器 Fisher 加权方差的精确渐近常数及自适应采样的最优分配方案，模拟结果与理论速率吻合。
正文 · 原文
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 $\beta$ 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 $1/\epsilon$ guarantees scale with $H^5$ in the effective horizon $H$, and no lower bound for MDPs depends on the temperature $\beta$. In this work, we show that for a discounted MDP with $K$ state-action pairs, the plug-in estimator finds a policy that is $\epsilon$-optimal from every initial state with $\widetilde{O}(KH^3/(\epsilon\max\{\epsilon,\beta\}) + KH)$ samples, and that no algorithm, even one that chooses where to sample, can do with fewer when $\epsilon \lesssim \min\{H, H^2/\beta\}$. For $\epsilon < \beta$ this is a $1/\epsilon$ 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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.13480 [cs.LG] |
| (or arXiv:2611.13480v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.13480 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Andrew Liu [view email]
[v1]
Tue, 10 Nov 2026 02:42:55 UTC (129 KB)
来源：arXiv cs.AI · arxiv.org