acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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- polynomial Lyapunov function induced by a finite -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.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, TD learning, Q-learning, smooth Q-learning, convergence, Lyapunov function

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_bpPXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors construct an explicit smooth polynomial Lyapunov function for preconditioned operator dynamics x˙=D(F(x)−x)\dot x=D(F(x)-x), where DD is a diagonal matrix. The authors also derive an ultimate bound for operators uniformly close to a contraction. Applications cover standard, LSE and Boltzmann Q-learning. Under independent sampling and diminishing step-sizes, the contractive variants converge almost surely to their respective fixed points; the Boltzmann iterates approach a guaranteed neighborhood of the optimal Q-function. Validation consists primarily of proofs and small finite-state numerical illustrations. The stochastic illustrations use a Markov trajectory and a constant step-size, which the authors explicitly acknowledge fall outside the assumptions of the stochastic convergence theorems.

Critical strengths
  1. An explicit, reusable polynomial certificate. Choosing wi=1/diw_i=1/d_i cancels the diagonal scaling in the derivative and yields W˙p≤−(1−αn1/(2p))∥x−x⋆∥2p2p.\dot W_p\le-\bigl(1-\alpha n^{1/(2p)}\bigr)\|x-x^\star\|_{2p}^{2p}. The proof does not require differentiability of FF, and the sufficient polynomial degree is independent of the imbalance among the diagonal entries of DD. This provides a useful constructive alternative to direct infinity-norm arguments and supports the paper's value as an accessible stability result.

  2. A consistent treatment of contractive operators and bounded perturbations. The framework applies the same basic argument to standard and smooth Bellman updates, while correctly distinguishing fixed-point convergence from approach to an error set. The explicit sampling assumptions and separate verification of Boltzmann Lipschitz continuity and bounded iterates make the scope of the stochastic claims assessable. These features support the technical reliability of the submission.

Critical weaknesses

I have concerns on the novelty of the paper. The authors did not show novelty and significance relative to closely related work. The main proof combines finite-dimensional norm comparison with inverse-diagonal weighting. The construction is interesting, but the manuscript does not show a consequential conclusion or application that specifically requires the polynomial structure. Chen et al. (2020), Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes, already construct smooth Lyapunov functions for arbitrary-norm contraction, explicitly including the infinity-norm case. Chen et al. (2024), A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation, extend related methods to Markovian observations. Jeong and Lee (2025), Unified Finite-Time Error Analysis of Soft Q-Learning, analyze the same three smooth operators. The paper cites these works but does not adequately argue the additional capability of its construction.

Even the positive diagonal scaling admits a simple stability-level reduction: for 0<τ≤1/dmax⁡0<\tau\le1/d_{\max}, Tτ(x)=x+τD(F(x)−x)T_\tau(x)=x+\tau D(F(x)-x) is an infinity-norm contraction with factor at most 1−τdmin⁡(1−α)1-\tau d_{\min}(1-\alpha), and x˙=(Tτ(x)−x)/τ\dot x=(T_\tau(x)-x)/\tau. This does not reproduce the specific polynomial certificate, but it weakens the novelty claim associated with preconditioning. The paper therefore needs a stronger account of why the explicit certificate is consequential. A new algorithm or finite-time theorem is not intrinsically required; the current asymptotic contribution itself needs a clearer demonstrated advance.

Questions for authors

Clarification of the existing contributions: What specific conclusion or useful application becomes available because the Lyapunov function is an explicit polynomial, beyond what the smooth-envelope approaches of Chen et al. (2020, 2024) and the soft Q-learning analysis of Jeong and Lee (2025) provide? A precise comparison of assumptions, conclusions, and an actual advantage of the construction could change the novelty assessment.

2 comments

We sincerely thank you for the careful comparison with prior work and for highlighting the need to explain the construction's specific advantage. We appreciate your positive assessment of its explicit form and consistent treatment of the different operators. We have revised the contribution claims and comparison accordingly.

  1. Comparison of assumptions and conclusions: Related Work and Appendix M, Table 1 now give a direct comparison. Chen et al. (2020) already construct smooth error measures for contractive stochastic approximation and obtain finite-sample bounds. Chen et al. (2024) extend this line of analysis to Markovian observations. Jeong and Lee (2025) provide finite-time bounds for LSE, Boltzmann, and mellowmax Q-learning. Our stochastic results instead use independent samples and decreasing step-sizes to establish convergence in the limit. We explicitly acknowledge these earlier results and do not claim improved sample-complexity guarantees.

  2. What advantage comes from the explicit polynomial?: The error measure is the finite sum Wp(e)=12p∑iei2pdi,W_p(e)=\frac{1}{2p}\sum_i\frac{e_i^{2p}}{d_i}, where eie_i is the error in entry ii and did_i is its update frequency. Its value and derivatives are written down directly. Giving rarely updated entries more weight cancels their slower update frequency in the derivative calculation. The sufficient degree depends on the number of entries and the contraction factor, rather than on the imbalance between update frequencies. The proof also does not require differentiating the Bellman operator.

By comparison, the generalized Moreau envelope in the earlier work defines a smooth error measure through a minimization problem. Our advantage is the directly specified polynomial and shared derivative calculation across the four operators. This is a benefit in constructing and checking the proof. We have made clear in the Introduction, Conclusion, and Appendix M that we have not demonstrated a new application requiring the polynomial or a stronger convergence result than those earlier analyses.

  1. The reduction for unequal update frequencies: We agree with your observation and thank you for this useful simplification. We have included the reduction in Related Work. If FF contracts errors by a factor a<1a<1, then Tτ(x)=x+τD(F(x)−x)T_\tau(x)=x+\tau D(F(x)-x) contracts by at most 1−τdmin⁡(1−a)1-\tau d_{\min}(1-a) for 0<τ≤1/dmax⁡0<\tau\le1/d_{\max}, where dmin⁡d_{\min} and dmax⁡d_{\max} are the smallest and largest diagonal entries of DD. Thus unequal update frequencies can already be handled by a classical contraction argument. The revised paper emphasizes the explicit polynomial and reusable calculation, rather than treating the presence of DD alone as a new convergence principle.

Thank you again for helping us make the contribution and its relationship to existing theory more precise.

Reviewer_bpPXOpenReview ↗

response to the rebutal

Thank you for the revision. Section 1.1 and Appendix M address my questions about prior work and explain how a classical contraction argument handles unequal update frequencies. I also appreciate the new experiments under i.i.d. sampling and diminishing step sizes.

My remaining concern is the significance of the polynomial construction. The inverse-frequency weights make the cancellation in the Lyapunov derivative easy to verify, and the same calculation applies across all four operators. Removing the factor dmax⁡/dmin⁡d_{\max}/d_{\min} from the Boltzmann error radius is a good improvement, especially when update frequencies differ substantially. The proof of Theorem 8 obtains this sharper radius by tracking the largest coordinate error directly. I therefore see the polynomial’s demonstrated contribution as a simplification of the stability proof. I value that simplification, but its scope is too limited to change my overall assessment. Based on this and After reading other reviewers comments, I retain my rating of 2 (weak rejection).

Reviewer_zt2ROpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper addresses convergence of tabular Q-learning and some of its smooth variants. In particular, the paper proposes an analysis of these algorithms where the stability of the associated ODE is not established based on an ∞\infty-norm contraction argument, as is standard in existing analyses. Instead, the paper proposes a polynomial Lyapunov function WpW_p built on a weighted 2p2p-norm. The paper establishes this function to be a proper Lyapunov function for ODEs of the form dxtdt=DF(xt)−Dxt,\frac{dx_t}{dt}=DF(x_t)-Dx_t, where DD is a positive definite diagonal matrix and FF is a contraction in ∞\infty-norm. From this result, the paper establishes the convergence of tabular Q-learning and several of its smooth variants. The paper also establishes a milder convergence result under Boltzmann softmax operators.

Critical strengths

I must clearly state that I did not check all proofs in the appendices in detail and, as such, cannot fully assess every technical argument. That said, I found that the smooth Lyapunov framework was an interesting novel addition to the literature on convergence of Q-learning. It provides an elegant argument for the ODE analysis and avoids some of the difficulties posed by the use of ∞\infty-norm. I also found that the unifying analysis of several Q-learning variants under a common framework was an interesting contribution, as it highlights the common structure across these variants.

Critical weaknesses

My main concerns regarding the paper are two-fold:

  • On one hand, it seems to me that, as stated above, the formulation is interesting and elegant, the results obtained in the end are not particularly novel or groundbreaking. In other words, the paper introduces a new proof methodology rather than new algorithmic or theoretical guarantees, and it would be interesting to have a clearer understanding of whether the new methodology may open the door for novel convergence results for Q-learning in more difficult settings - most notably, with function approximation.
  • The appendices include some simple empirical results, but I'm not fully convinced that these are needed at all, as the contribution of the paper is theoretical and the setting of the simulations does not match the setup and assumptions considered in the theoretical results, making it hard for me to assess what added insight these intend to bring.
Questions for authors

What concrete advantages does the proposed Lyapunov framework provide over existing infinity-norm analyses? In particular, are there examples where the proposed framework enables analysis of algorithms or settings that are hard to handle with existing approaches (e.g., function approximation)?

2 comments

We sincerely thank you for recognizing the value of a smooth, unified proof and for asking how it helps beyond the existing analyses. Your comments also helped us clarify the purpose of the experiments. We have revised the manuscript in the following ways.

  1. Concrete advantage of the framework: A Lyapunov function is a measure of error that decreases along the continuous-time model of learning. The largest-error measure used in classical proofs is not differentiable when several entries tie. Our polynomial measure is smooth and can be differentiated directly, even when the Bellman operator itself is not differentiable. It adds even powers of the errors and gives more weight to entries updated less often; those weights cancel the update frequencies in the calculation.

This gives a directly evaluable construction and a common proof for max, log-sum-exp (LSE), and mellowmax, together with an error-region argument for Boltzmann. The benefit is a transparent proof that can be reused across these operators. We have made clear in the Introduction, Related Work, Conclusion, and Appendix M that the paper does not establish stronger classical convergence guarantees or exhibit a setting accessible only through this construction. Table 1 compares the method with earlier smooth error measures and finite-time analyses.

  1. Extension to function approximation: We agree that this is an important direction for testing the framework's wider usefulness. In a table, an update changes one entry; with shared parameters, such as a neural network, an update can change many values together. The contraction and separate-coordinate structure used in our proof may then fail. We therefore cannot claim a function-approximation result from the present theorem. We have stated this limitation in the Conclusion and Appendix M. Such an extension would require a separate argument showing how the shared-parameter errors decrease.

  2. Experiments and their role: Thank you for pointing out the mismatch with the stochastic assumptions. Appendix O, Figure 4 and Table 3 now contain experiments with independent state-action samples and a decreasing step-size, using 32 seeds and 200,000 updates. We compare this schedule with a constant step of 0.01 on the same samples. Each contractive variant uses its own target values; Boltzmann is also evaluated by distance to its guaranteed region.

The runs illustrate the distinction between reaching a target and approaching a region. Both schedules have similar terminal errors, and every Boltzmann run ends inside the region despite retaining error to the optimal Q-values. We present these as illustrations of the theorem's setting, not empirical proof of convergence. The original constant-step, single-trajectory plots remain clearly identified as outside the stochastic theorem assumptions.

Thank you again for helping us state both the usefulness and the limits of the approach more clearly.

Reviewer_zt2ROpenReview ↗

Thank you for the clarifications

I thank the authors for clarifying several of the issues that I pointed out in my review. The added experiments are a welcome addition, even if in the appendix. On the other hand, my concern that the results obtained in the end are not particularly novel or groundbreaking remains. As I mentioned, I appreciate the elegance of the proposed formulation, but given the primordial role that approximation architectures play in current day's RL research, the fact that the proposed formulation does not add much to our knowledge of convergence in function approximation settings renders the impact of the contributions somewhat limited.

Reviewer_8mkiOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops a smooth polynomial Lyapunov framework for analyzing the convergence of tabular Q-learning and several smooth Bellman-update variants.

The central technical idea is to study preconditioned nonlinear dynamics of the form

[ \dot{x}=D(F(x)-x), ]

where (D) is a positive diagonal matrix and (F) is a contraction or a uniformly bounded perturbation of a contraction.

The authors construct a weighted polynomial Lyapunov function,

[ W_p(x)=\frac{1}{2p}\sum_{i=1}^{n}d_i^{-1}x_i^{2p}, ]

and use finite-dimensional norm inequalities to transfer infinity-norm contraction into a smooth stability certificate.

For contractive Bellman operators, including max, log-sum-exp, and mellowmax, the framework establishes global exponential stability of the associated ODEs.

For the generally non-contractive Boltzmann softmax operator, the authors instead obtain an ultimate error bound around the optimal Q-function.

These ODE results are subsequently combined with classical stochastic-approximation arguments to establish almost-sure convergence to the corresponding fixed points or an invariant error set under i.i.d. sampling and diminishing step sizes.

The manuscript provides detailed proofs and small numerical illustrations.

My overall assessment is that the mathematical development is largely sound and clearly presented. However, the incremental theoretical contribution appears limited, and several quantitative guarantees are considerably more conservative than necessary.

Critical strengths

This paper develops a smooth polynomial Lyapunov framework for analyzing the convergence of tabular Q-learning and several smooth Bellman-update variants.

The central technical idea is to study preconditioned nonlinear dynamics of the form

[ \dot{x}=D(F(x)-x), ]

where (D) is a positive diagonal matrix and (F) is a contraction or a uniformly bounded perturbation of a contraction.

The authors construct a weighted polynomial Lyapunov function,

[ W_p(x)=\frac{1}{2p}\sum_{i=1}^{n}d_i^{-1}x_i^{2p}, ]

and use finite-dimensional norm inequalities to transfer infinity-norm contraction into a smooth stability certificate.

For contractive Bellman operators, including max, log-sum-exp, and mellowmax, the framework establishes global exponential stability of the associated ODEs.

For the generally non-contractive Boltzmann softmax operator, the authors instead obtain an ultimate error bound around the optimal Q-function.

These ODE results are subsequently combined with classical stochastic-approximation arguments to establish almost-sure convergence to the corresponding fixed points or an invariant error set under i.i.d. sampling and diminishing step sizes.

The manuscript provides detailed proofs and small numerical illustrations.

My overall assessment is that the mathematical development is largely sound and clearly presented. However, the incremental theoretical contribution appears limited, and several quantitative guarantees are considerably more conservative than necessary.

Critical weaknesses

This paper develops a smooth polynomial Lyapunov framework for analyzing the convergence of tabular Q-learning and several smooth Bellman-update variants.

The central technical idea is to study preconditioned nonlinear dynamics of the form

[ \dot{x}=D(F(x)-x), ]

where (D) is a positive diagonal matrix and (F) is a contraction or a uniformly bounded perturbation of a contraction.

The authors construct a weighted polynomial Lyapunov function,

[ W_p(x)=\frac{1}{2p}\sum_{i=1}^{n}d_i^{-1}x_i^{2p}, ]

and use finite-dimensional norm inequalities to transfer infinity-norm contraction into a smooth stability certificate.

For contractive Bellman operators, including max, log-sum-exp, and mellowmax, the framework establishes global exponential stability of the associated ODEs.

For the generally non-contractive Boltzmann softmax operator, the authors instead obtain an ultimate error bound around the optimal Q-function.

These ODE results are subsequently combined with classical stochastic-approximation arguments to establish almost-sure convergence to the corresponding fixed points or an invariant error set under i.i.d. sampling and diminishing step sizes.

The manuscript provides detailed proofs and small numerical illustrations.

My overall assessment is that the mathematical development is largely sound and clearly presented. However, the incremental theoretical contribution appears limited, and several quantitative guarantees are considerably more conservative than necessary.

Questions for authors
  1. Questions for the Authors

Q1. Novelty relative to existing convergence theory

What precise convergence or stability property is established by the proposed polynomial certificate that cannot be obtained using classical infinity-norm Lyapunov arguments or earlier finite-norm approaches?

Could the authors provide an example in which the polynomial framework yields a materially stronger or more informative result than existing analyses?

Q2. Tightness of the Boltzmann error bound

Is the factor (w_{\max}/w_{\min}) in the Boltzmann invariant-set radius necessary?

A direct upper-Dini-derivative argument appears to give the smaller invariant radius

[ \frac{\gamma\lambda\log|\mathcal A|}{1-\gamma} ]

for every positive diagonal (D).

Can the authors confirm this stronger result or explain why the argument would not apply?

Q3. Quantitative usefulness of the polynomial certificate

How should the polynomial degree (2p) be chosen when (\gamma) is close to one or the state-action space is large?

Can the authors characterize the trade-off between polynomial degree and the conservatism of the certified convergence rate?

Q4. Stochastic convergence experiments

Can the authors add a small numerical experiment satisfying the actual assumptions of Theorems 11 and 12?

In particular, it would be useful to compare the behavior under diminishing step sizes with the existing constant-step-size experiments.

2 comments

We sincerely thank you for your careful review and concrete suggestions. They helped us sharpen the Boltzmann bound, explain the contribution more clearly, and add experiments that match the stochastic assumptions. We address Q1-Q4 below.

Q1. What does the polynomial proof add?: Its practical advantage is an explicit, smooth measure of error that is easy to evaluate and differentiate. We add even powers of the individual errors, giving more weight to entries updated less often. For example, an entry updated half as often receives twice the weight. These weights cancel the update frequencies in the derivative calculation. The proof does not require differentiating the Bellman operator and provides a common argument for max, log-sum-exp (LSE), and mellowmax, with an error-region result for Boltzmann.

To answer the novelty question directly, the present paper does not demonstrate a stronger classical convergence guarantee or an application that specifically requires a polynomial. The contribution is the explicit construction and reusable stability calculation. We have clarified this scope in the Introduction and Related Work, and added an assumptions-methods-conclusions comparison in Appendix M, Table 1.

Q2. Is the smaller Boltzmann radius valid?: Yes. Thank you for identifying that the update-frequency ratio is unnecessary. We have strengthened Theorems 8 and 10 to use R=γλlog⁡∣A∣1−γ,R=\frac{\gamma\lambda\log|\mathcal A|}{1-\gamma}, where γ\gamma is the discount, λ\lambda is the smoothing parameter, and ∣A∣|\mathcal A| is the number of actions. The key observation is simple: above this radius, the largest error decreases; at the boundary, it cannot increase outward. Update frequencies affect how quickly the continuous-time error approaches the region, but not this radius. Section 6 and Theorem 12 now use the smaller region. Under the stated independent-sampling and decreasing-step assumptions, the sampled algorithm approaches this region with probability one; a unique Boltzmann fixed point is not assumed.

Q3. How should the degree be chosen?: Appendix N gives the rule: for nn table entries, choose an even degree q=2pq=2p with q>⌈log⁡n/log⁡(1/γ)⌉q>\lceil\log n/\log(1/\gamma)\rceil. Table 2 quantifies the trade-off. With 1,000 entries and discount 0.99, the smallest permitted degree is 690. Doubling it to 1,380 raises the certified decay rate from about 0.4% to 50.3% of its limiting value. Larger degrees also reduce the multiplicative constant in the error bound, but large powers can be difficult to evaluate numerically. This choice improves the proof's bound; it does not change the learning algorithm or make its updates faster.

Q4. Can experiments match Theorems 11 and 12?: We have added Appendix O, Figure 4 and Table 3: 32 independent seeds, 200,000 updates, independently sampled state-action pairs, and decreasing step-size αk=(1+k/100)−0.6\alpha_k=(1+k/100)^{-0.6}. A constant-step run with step-size 0.01 uses the same samples for comparison. Max, LSE, and mellowmax are measured against their own target values. For Boltzmann, we also report distance to the guaranteed region: every run ends inside it, while error to the optimal Q-values remains nonzero. Both step schedules have similar terminal errors at this horizon. These are finite-run observations, not a proof of almost-sure convergence or superiority of either schedule. The original constant-step trajectory figures remain labeled as illustrations outside the stochastic theorem assumptions.

Thanks. The revised bound helps, but no stronger guarantee over prior theory or polynomial-specific application is shown. My novelty concern remains.

Comments on the paper

1 comment
Area_Chair_iVWZOpenReview ↗

Engage with the authors response.

Reviewers, can you please acknowledge that you have read the authors response and comment to what extent it resolves your concerns?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.