Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes offline Q-learning with KL regularization for finite-horizon MDPs, demonstrating that KL regularization can enable fast learning rates. The authors introduce KLQ, a variant of Q-learning, and prove it achieves $\widetilde{O}(1/ε)$ sample complexity without explicit pessimism, albeit with an exponential dependence on the KL parameter and horizon. By incorporating pessimism into KLQ to form KLPQ, they achieve the same $\widetilde{O}(1/ε)$ rate while removing this dependence, establishing the first fast-rate guarantees for tabular finite-horizon KL-regularized offline Q-learning.
Offline Q-learning can achieve $\widetilde{O}(1/ε)$ sample complexity in finite-horizon KL-regularized MDPs, even without explicit pessimism, by leveraging KL regularization.
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/ε)$ 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/ε)\) 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.