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. The authors first propose KL-regularized Q-Learning KLQ, a simple variant of classical Q-learning. By exploiting KL regularization, they prove that KLQ achieves a sample complexity of Õ(1/ε) without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, they further propose KL-regularized Pessimistic Q-Learning KLPQ, which incorporates pessimism into KLQ. They prove that KLPQ retains the same Õ(1/ε) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of their knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs.
KL-regularized Q-Learning
KLQ is introduced as a straightforward modification of classical Q-learning that adds a KL regularization term to the update objective. The regularization penalizes updates that deviate significantly from a behavior policy, thereby incorporating a form of implicit offline evaluation. Under a local quadratic approximation of the Bellman error, the authors show that the regularized update yields a contraction property that depends on the KL radius. This contraction is sufficient to establish a sample complexity of Õ(1/ε) for finding an ε-optimal Q-function. The analysis does not require an explicit pessimistic correction term, which simplifies the algorithm but introduces the aforementioned exponential dependence on the KL parameter and the horizon length.
KL-regularized Pessimistic Q-Learning
To eliminate the exponential factor, the authors propose KLPQ, which combines KL regularization with a pessimistic value function lower bound. The pessimism term is constructed to overestimate the uncertainty of the learned Q-function under the KL-constrained policy distribution. By carefully bounding the combined effect of the KL penalty and the pessimistic bound, they show that the sample complexity remains Õ(1/ε) but the dependence on the KL regularization parameter and the horizon becomes polynomial rather than exponential. This improvement makes the theoretical guarantee significantly tighter, especially for long-horizon problems where the horizon factor previously dominated the sample complexity.
First fast-rate guarantees for offline Q-learning
The paper's main theoretical contribution is the establishment of fast-rate guarantees for offline Q-learning in tabular finite-horizon Markov decision processes with KL regularization. Prior work had either assumed explicit pessimism or suffered from sample complexity rates that scaled poorly with the problem parameters. KLQ and KLPQ provide the first results that achieve the Õ(1/ε) rate—a hallmark of fast rates in offline decision-making—without relying on problem-specific pessimistic function classes or distribution-shift correction terms that are difficult to instantiate in practice. The removal of the exponential dependence in KLPQ further extends the applicability of these guarantees to settings with large horizons or strong regularization.
- KLQ achieves Õ(1/ε) sample complexity without explicit pessimism, at the cost of an exponential dependence on the KL parameter and horizon.
- KLPQ achieves the same Õ(1/ε) rate while removing the exponential dependence, combining KL regularization with pessimistic value estimation.
- Both algorithms operate in the tabular setting and assume a finite-horizon MDP, making the results directly applicable to a wide class of offline reinforcement learning problems.