arXiv cs.AI· Yize Hao, Guangxin Jiang, Shuang Qiu·· 3 天前AI 评分15
离线 Q-Learning 结合 KL 正则化的快速收敛速率
Fast Rates for Offline Q-Learning with KL Regularization
AI 导读
该论文研究带 KL 正则化的有限时域马尔可夫决策过程中的离线 Q-learning，提出 KLQ 与 KLPQ 两种算法。KLQ 无需显式悲观机制即可达到 Õ(1/ε) 的样本复杂度，但依赖 KL 正则化参数与时域的指数项；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