# A Smooth Polynomial Lyapunov Certificate for Convergence of Q-Learning and Its Smooth Variants

arXiv: https://arxiv.org/abs/2404.14442 · HTML: https://mlsanity.com/paper/2404.14442/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 20 Apr 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Built on by (most cited first, 1 of 1)

- [Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem](https://mlsanity.com/paper/2604.06837/) (2026)

## Abstract (arXiv)

Classical convergence analyses of Q-learning rely on the ∞-norm contraction of Bellman operators, and existing ordinary differential equation (ODE) arguments often use the non-differentiable ∞-norm directly. This paper develops a smooth polynomial Lyapunov-function-based stability certificate for convergence of Q-learning by transferring ∞-norm contraction to a weighted degree-2p polynomial Lyapunov function induced by a finite 2p-norm. The framework is conceptual and structural: it avoids non-differentiability, handles preconditioned dynamics arising in Q-learning and its variants, and gives a unified stability argument for standard Q-learning and smooth variants based on log-sum-exp (LSE), mellowmax, and Boltzmann softmax operators. For contractive operators, including the max, LSE, and mellowmax cases, the associated ODEs are globally exponentially stable and, under the stated independent and identically distributed (i.i.d.) sampling model, the stochastic approximation iterates converge almost surely. For the Boltzmann operator, which need not be contractive, the same framework yields convergence to an explicit invariant error set around the optimal Q-function. The resulting theory is not intended as a finite-time bound, but as a clean ODE foundation that unifies and simplifies asymptotic analyses of Q-learning and its smooth variants.