arXiv：cs.AI· Yize Hao, Guangxin Jiang, Shuang Qiu·· 23 小时前
离线 Q-Learning 结合 KL 正则化实现快速收敛率
Fast Rates for Offline Q-Learning with KL Regularization
AI 导读
该研究提出 KL 正则化 Q-Learning（KLQ），在有限时域 MDP 的离线设定下无需显式悲观机制即达到 Õ(1/ε) 样本复杂度，但该保证对 KL 正则化参数和时域呈指数依赖。为此进一步提出 KL 正则化悲观 Q-Learning（KLPQ），在保持 Õ(1/ε) 速率的同时消除了指数依赖，据称这是表格型有限时域 KL 正则化 MDP 中离线 Q-Learning 的首个快速率保证。
正文
Abstract:This paper investigates offline Q-learning for finite-horizon Markov decision processes with Kullback-Leibler (KL) regularization. Recent studies have shown that KL regularization can yield fast rates in offline decision-making problems. However, it remains unclear whether Q-learning, which adopts incremental stochastic approximation updates, can achieve such fast rates in the offline setting. We first propose KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning. By exploiting KL regularization, we prove that KLQ achieves a sample complexity of $\widetilde{O}(1/\epsilon)$ without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, we further propose KL-regularized Pessimistic Q-Learning (KLPQ), which incorporates pessimism into KLQ. We prove that KLPQ retains the same \(\widetilde O(1/\epsilon)\) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of our knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.18839 [cs.LG] |
| (or arXiv:2610.18839v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.18839 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yize Hao [view email]
[v1]
Tue, 13 Oct 2026 17:56:27 UTC (39 KB)
来源：arXiv：cs.AI · arxiv.org