- 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 , where 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
-
An explicit, reusable polynomial certificate. Choosing cancels the diagonal scaling in the derivative and yields The proof does not require differentiability of , and the sufficient polynomial degree is independent of the imbalance among the diagonal entries of . This provides a useful constructive alternative to direct infinity-norm arguments and supports the paper's value as an accessible stability result.
-
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 , is an infinity-norm contraction with factor at most , and . 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
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 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).
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.
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.
What advantage comes from the explicit polynomial?: The error measure is the finite sum Wp(e)=2p1∑idiei2p, where ei is the error in entry i and di 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.
Thank you again for helping us make the contribution and its relationship to existing theory more precise.