跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.13480 · v1

Sharp Sample Complexity of KL-Regularized Reinforcement Learning

首次提交 2026-11-10 10:42
版本更新 2026-11-10 10:42
雷达观测 2026-11-11 11:04
arXiv ↗PDF ↗

摘要

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/ε1/ε guarantees scale with H5H^5 in the effective horizon HH, and no lower bound for MDPs depends on the temperature ββ. In this work, we show that for a discounted MDP with KK state-action pairs, the plug-in estimator finds a policy that is εε-optimal from every initial state with O~(KH3/(εmax⁡{ε,β})+KH)\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH) samples, and that no algorithm, even one that chooses where to sample, can do with fewer when ε≲min⁡{H,H2/β}ε\lesssim \min\{H, H^2/β\}. For ε<βε< β this is a 1/ε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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-10 10:42 · 最新观测版本

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/ε1/ε guarantees scale with H5H^5 in the effective horizon HH, and no lower bound for MDPs depends on the temperature ββ. In this work, we show that for a discounted MDP with KK state-action pairs, the plug-in estimator finds a policy that is εε-optimal from every initial state with O~(KH3/(εmax⁡{ε,β})+KH)\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH) samples, and that no algorithm, even one that chooses where to sample, can do with fewer when ε≲min⁡{H,H2/β}ε\lesssim \min\{H, H^2/β\}. For ε<βε< β this is a 1/ε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.

查看此版本解读 →查看此版本原文 ↗