A Nonasymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms
- 18 September 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Abstract
We study the problem of solving fixed-point equations for seminorm-contractive operators and establish foundational results on the nonasymptotic behavior of iterative algorithms in both deterministic and stochastic settings. In the deterministic setting, we present a fixed-point theorem for seminorm-contractive operators, showing that the iterates converge geometrically to the kernel of the seminorm. In the stochastic setting, which is our main focus, we analyze stochastic approximation (SA) algorithms under seminorm-contractive operators and Markovian noise, providing a finite-sample analysis for various step size choices. A benchmark for equation solving is linear systems of equations, in which the convergence behavior of fixed-point iteration is closely tied to the stability of linear dynamical systems. In this special case, our results provide a characterization of system stability with respect to a seminorm, linking it to the solution of a Lyapunov equation in terms of positive semidefinite matrices. In the stochastic setting, we establish a finite-sample analysis for linear Markovian SA without requiring the Hurwitzness assumption. Our theoretical results offer a unified framework for deriving finite-sample bounds for reinforcement learning algorithms in the average reward setting, including TD([Formula: see text]) for policy evaluation (which is a special case of solving a Poisson equation) and Q-learning for control. Funding: This work was partially supported by the National Science Foundation [Grants EPCN-2144316, CPS-2240982, CMMI-2112533], a seed grant from Georgia Tech, and an award from Raytheon Technologies. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2025.0920 .Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learningAutomatica, 2022
- Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overviewAnnual Reviews in Control, 2021
- First-order and Stochastic Optimization Methods for Machine Learning2020
- Markov Chains2018
- Unifying Robot Trajectory Tracking with Control Contraction MetricsSpringer Proceedings in Advanced Robotics, 2017
- Large-Scale Machine Learning with Stochastic Gradient Descent2010
- Mathematical Systems Theory I2005
- Reinforcement learning for long-run average costEuropean Journal of Operational Research, 2004
- Average cost temporal-difference learningAutomatica, 1999
- On Contraction Analysis for Non-linear SystemsAutomatica, 1998