# A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2025.

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

- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning](https://mlsanity.com/paper/2508.05984/) (2025)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotients](https://mlsanity.com/paper/2602.00474/) (2026)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Bridging the Gap Between Average and Discounted TD Learning](https://mlsanity.com/paper/2605.02103/) (2026)
- [Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning](https://mlsanity.com/paper/2610.15871/) (2026)

## Abstract (arXiv)

We study the problem of solving fixed-point equations for seminorm-contractive operators and establish foundational results on the non-asymptotic behavior of iterative algorithms in both deterministic and stochastic settings. Specifically, in the deterministic setting, we prove a fixed-point theorem for seminorm-contractive operators, showing that iterates converge geometrically to the kernel of the seminorm. In the stochastic setting, we analyze the corresponding stochastic approximation (SA) algorithm under seminorm-contractive operators and Markovian noise, providing a finite-sample analysis for various stepsize choices. A benchmark for equation solving is linear systems of equations, where 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 complete characterization of system stability with respect to a seminorm, linking it to the solution of a Lyapunov equation in terms of positive semi-definite 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 various reinforcement learning algorithms in the average reward setting, including TD(λ) for policy evaluation (which is a special case of solving a Poisson equation) and Q-learning for control.