arXiv cs.AI· Andrew Liu·· 10 小时前AI 评分27
KL 正则化强化学习的精确样本复杂度
Sharp Sample Complexity of KL-Regularized Reinforcement Learning
AI 导读
研究证明，对含 K 个状态-动作对的折扣 MDP，plug-in 估计器以 Õ(KH³/(ε·max{ε,β}) + KH) 个样本从每个初始状态找到 ε-最优策略，并给出匹配下界：当 ε ≲ min{H, H²/β} 时任何算法（即使可自适应选择采样位置）都无法更少。
正文 · AI 翻译
摘要：KL 正则化强化学习——即最大熵强化学习与基于人类反馈的强化学习背后的目标——是“控制即推断”图模型中的变分推断：正则化后的最优策略是轨迹上的后验分布，而策略的次优性等于路径测度之间 KL 散度的 $\beta$ 倍。然而，即便拥有生成模型，也尚不清楚需要多少样本才能学到该后验。此前的 $1/\epsilon$ 保证在有效时域 $H$ 上按 $H^5$ 缩放，且 MDP 的下界均不依赖于温度 $\beta$。在本工作中，我们证明：对于具有 $K$ 个状态-动作对的折扣 MDP，插入式估计器用 $\widetilde{O}(KH^3/(\epsilon\max\{\epsilon,\beta\}) + KH)$ 个样本即可找到从每个初始状态出发都 $\epsilon$-最优的策略；并且当 $\epsilon \lesssim \min\{H, H^2/\beta\}$ 时，任何算法（即使可以选择采样位置）都无法用更少的样本做到。对于 $\epsilon < \beta$，这是一个 $1/\epsilon$ 速率，其时域依赖性与无正则化 RL 相同。我们还求出了插入式估计器的精确渐近常数，即估计的软 Q 函数的 Fisher 加权方差。该估计器在等频率采样每一对的方法中局部渐近极小极大，并且我们给出了自适应设计中样本的最优分配。在小规模 MDP 上的模拟与这些速率和常数相符。
| 学科： | 机器学习（cs.LG）；人工智能（cs.AI） |
| 引用为： | arXiv:2611.13480 [cs.LG] |
| （或 arXiv:2611.13480v1 [cs.LG] 获取此版本） | |
| https://doi.org/10.48550/arXiv.2611.13480 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Andrew Liu [查看邮箱]
[v1]
2026年11月10日 星期二 02:42:55 UTC（129 KB）
来源：arXiv cs.AI · arxiv.org