A Nonasymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms

Source 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 .