arXiv 论文给出 KL 正则化强化学习的紧致样本复杂度界
Sharp Sample Complexity of KL-Regularized Reinforcement Learning
搞 RLHF 或最大熵 RL 的朋友可以看这篇。以前理论界是 H^5，现在证明 H^3 就够，还首次给出带温度 β 的下界。做 RLHF 训练时要估采样预算的话，这篇能直接告诉你该按什么规模分配样本。
arXiv 论文研究了 KL 正则化强化学习（最大熵 RL 和 RLHF 背后的目标函数）的样本复杂度问题。此前文献只有 1/ε 保证按有效视界 H 的 H^5 规模增长，且没有针对 MDP 的下界依赖于温度 β。论文证明：对于一个含 K 个状态-动作对的折扣 MDP，plug-in 估计器可以从每个初始状态找到 ε-最优策略，所需样本量为 O(KH^3/(ε·max{ε,β}) + KH)。论文同时给出匹配下界，证明即使可以自适应选点采样，当 ε ≲ min{H, H^2/β} 时任何算法都不能用更少样本。
技术机制上，该工作将 KL 正则化 RL 看作"control as inference"图模型中的变分推断：正则化最优策略是轨迹上的后验分布，策略的次优性等于 β 乘以路径测度之间的 KL 散度。当 ε < β 时，结果呈现 1/ε 速率，且视界依赖与未正则化 RL 相同。论文还推导出 plug-in 估计器的精确渐近常数——估计 soft Q 函数的 Fisher 加权方差，证明该估计器在均匀采样方法中是局部渐近 minimax 的，并给出了自适应设计中最优的样本分配方案。
这项工作首次给出了依赖温度 β 的下界，填补了 KL 正则化 RL 理论空白。对 RLHF 和最大熵 RL 的从业者来说，结果意味着采样预算应随 H^3 而非此前担心的 H^5 扩展，且在 β 较小时样本需求与未正则化 RL 同阶。仿真结果在小规模 MDP 上验证了速率和常数，理论结果对设计 RLHF 训练中的采样策略有直接参考价值。
Sharp Sample Complexity of KL-Regularized Reinforcement Learning
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 $1/ε$ guarantees scale with $H^5$ in the effective horizon $H$, and no lower bound for MDPs depends on the temperature $β$. In this work, we show that for a discounted MDP with $K$ state-action pairs, the plug-in estimator finds a policy that is $ε$-optimal from every initial state with $\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH)$ samples, and that no algorithm, even one that chooses where to sample, can do with fewer when $ε\lesssim \min\{H, H^2/β\}$. For $ε< β$ this is a $1/ε$ 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.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include RLHF, 强化学习, KL正则化, 采样复杂度.
Source attribution: curated from arXiv cs.LG (@Andrew Liu).
