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

References

• [1] Abounadi J, Bertsekas D, Borkar VS (2001) Learning algorithms for Markov decision processes with average cost. SIAM J. Control Optim. 40(3):681–698.Crossref, Google Scholar
• [2] Agrawal P, Agrawal S (2025) Optimistic Q-learning for average reward and episodic reinforcement learning extended abstract. Proc. Thirty Eighth Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 291 (PMLR, New York), 1.Google Scholar
• [3] Agrawal S, Maguluri ST (2024) Policy evaluation for variance in average reward reinforcement learning. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (PMLR, New York), 471–502.Google Scholar
• [4] Banach S (1922) Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae 3(1):133–181.Google Scholar
• [5] Bartels RH, Stewart GW (1972) Solution of the matrix equation AX+XB=C. Comm. ACM 15(9):820–826.Crossref, Google Scholar
• [6] Beck A (2017) First-Order Methods in Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [7] Benveniste A, Métivier M, Priouret P (2012) Adaptive Algorithms and Stochastic Approximations, vol. 22 (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• [8] Bertsekas DP (2007) Dynamic Programming and Optimal Control, vol. II, 3rd ed. (Athena Scientific, Raleigh, NC).Google Scholar
• [9] Bertsekas DP, Tsitsiklis JN (1996) Neuro-Dynamic Programming (Athena Scientific, Raleigh, NC).Google Scholar
• [10] Bhandari J, Russo D, Singal R (2021) A finite time analysis of temporal difference learning with linear function approximation. Oper. Res. 69(3):950–973.Google Scholar
• [11] Borkar VS (2009) Stochastic Approximation: A Dynamical Systems Viewpoint, vol. 48 (Cambridge University Press, Cambridge, UK).Google Scholar
• [12] Borkar VS, Meyn SP (2000) The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. 38(2):447–469.Crossref, Google Scholar
• [13] Bottou L (2010) Large-scale machine learning with stochastic gradient descent. Lechevallier Y, Saporta G, eds. Proc. COMPSTAT’2010 19th Internat. Conf. Comput. Statist. Invited Contributed Papers (Physica-Verlag HD, Heidelberg, Germany), 177–186.Google Scholar
• [14] Bourbaki N (2013) Topological Vector Spaces (Cambridge University Press, Cambridge, UK).Google Scholar
• [15] Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [16] Bravo M, Cominetti R (2024) Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. SIAM J. Control Optim. 62(1):191–219.Crossref, Google Scholar
• [17] Chandak S, Borkar VS, Dodhia P (2022) Concentration of contractive stochastic approximation and reinforcement learning. Stochastic Systems 12(4):411–430.Link, Google Scholar
• [18] Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2020) Finite-sample analysis of stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 8223–8234.Google Scholar
• [19] Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2024) A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Oper. Res. 72(4):1352–1367.Link, Google Scholar
• [20] Chen Z, Zhang S, Doan TT, Clarke JP, Maguluri ST (2022) Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica 146:110623.Crossref, Google Scholar
• [21] Conway JB (2019) A Course in Functional Analysis, vol. 96 (Springer, New York).Google Scholar
• [22] Davydov A, Jafarpour S, Bullo F (2022) Non-Euclidean contraction theory for robust nonlinear stability. IEEE Trans. Automatic Control 67(12):6667–6681.Crossref, Google Scholar
• [23] De Pasquale G, Smith KD, Bullo F, Valcher ME (2023) Dual seminorms, ergodic coefficients and semicontraction theory. IEEE Trans. Automatic Control 69(5):3040–3053.Crossref, Google Scholar
• [24] Devraj AM, Meyn SP (2021) Q-learning with uniformly bounded variance. IEEE Trans. Automatic Control 67(11):5948–5963.Crossref, Google Scholar
• [25] Douc R, Jacob PE, Lee A, Vats D (2026) Solving the Poisson equation using coupled Markov chains. Ann. Statist. 54(1):201–225.Google Scholar
• [26] Douc R, Moulines E, Priouret P, Soulier P, Douc R, Moulines E, Priouret P, Soulier P (2018) Markov Chains: Basic Definitions (Springer, Cham, Switzerland).Crossref, Google Scholar
• [27] Fudenberg D, Tirole J (1991) Game Theory (MIT Press, Cambridge, MA).Google Scholar
• [28] Ganesh S, Mondal WU, Aggarwal V (2025) A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach. Proc. 42nd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 267 (Curran Associates Inc., Red Hook, NY), 18206–18227.Google Scholar
• [29] Gaubert S, Qu Z (2013) Markov operators on cones and non-commutative consensus. 2013 Eur. Control Conf. (IEEE, Piscataway, NJ), 2693–2700.Google Scholar
• [30] Gosavi A (2004) Reinforcement learning for long-run average cost. Eur. J. Oper. Res. 155(3):654–674.Crossref, Google Scholar
• [31] Gupta A, Jain R, Glynn P (2024) Probabilistic contraction analysis of iterated random operators. IEEE Trans. Automatic Control 69(9):5947–5962.Crossref, Google Scholar
• [32] Haddad WM, Chellaboina V (2008) Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [33] Henderson SG, Glynn PW (2002) Approximating martingales for variance reduction in Markov process simulation. Math. Oper. Res. 27(2):253–271.Link, Google Scholar
• [34] Hinrichsen D, Pritchard AJ (2005) Mathematical Systems Theory I: Modeling, State Space Analysis, Stability and Robustness, vol. 48 (Springer Science & Business Media, Berlin, Heidelberg).Crossref, Google Scholar
• [35] Jafarpour S, Cisneros-Velarde P, Bullo F (2021) Weak and semi-contraction for network systems and diffusively coupled oscillators. IEEE Trans. Automatic Control 67(3):1285–1300.Crossref, Google Scholar
• [36] Khalil H (2002) Nonlinear Systems (Pearson Education Prentice Hall, Upper Saddle River, NJ).Google Scholar
• [37] Khalil HK (2009) Lyapunov stability. Control Systems, Robotics and Automation, vol. 12 (EOLSS, Oxford, UK), 115.Google Scholar
• [38] Kushner H, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications, vol. 35 (Springer Science & Business Media, New York).Google Scholar
• [39] Lakshminarayanan C, Szepesvari C (2018) Linear stochastic approximation: How far does constant step-size and iterate averaging go? Proc. Twenty-First Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 84 (PMLR, New York), 1347–1355.Google Scholar
• [40] Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning, vol. 1 (Springer, Cham, Switzerland).Crossref, Google Scholar
• [41] Levin DA, Peres Y (2017) Markov Chains and Mixing Times, vol. 107 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [42] Li Y, Ma T, Zhang H (2018) Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. Conf. Learn. Theory (PMLR, New York), 2–47.Google Scholar
• [43] Li T, Wu F, Lan G (2024) Stochastic first-order methods for average-reward Markov decision processes. Math. Oper. Res. 50(4):3125–3160. Link, Google Scholar
• [44] Li G, Cai C, Chen Y, Wei Y, Chi Y (2024) Is Q-learning minimax optimal? A tight sample complexity analysis. Oper. Res. 72(1):222–236.Link, Google Scholar
• [45] Lohmiller W, Slotine JJ (1998) On contraction analysis for non-linear systems. Automatica 34(6):683–696.Crossref, Google Scholar
• [46] Lohmiller W, Slotine JJ (2000) Control system design for mechanical systems using contraction theory. IEEE Trans. Automatic Control 45(5):984–989.Crossref, Google Scholar
• [47] Mahadevan S (1996) Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine Learn. 22(1):159–195.Crossref, Google Scholar
• [48] Manchester IR, Tang JZ, Slotine JJE (2018) Unifying robot trajectory tracking with control contraction metrics. Bicchi A, Burgard W, eds. Robotics Research, Springer Proceedings in Advanced Robotics, vol. 3 (Springer, Cham, Switzerland), 403–418.Crossref, Google Scholar
• [49] Megginson RE (2012) An Introduction to Banach Space Theory (Springer Science & Business Media, New York).Google Scholar
• [50] Meyn SP, Tweedie RL (2009) Markov Chains and Stochastic Stability (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [51] Mijatović A, Vogrinc J (2018) On the Poisson equation for Metropolis-Hastings chains. Bernoulli 24(3):2401–2428.Crossref, Google Scholar
• [52] Mou W, Khamaru K, Wainwright MJ, Bartlett PL, Jordan MI (2022) Optimal variance-reduced stochastic approximation in Banach spaces. Preprint, submitted January 21, https://arxiv.org/abs/2201.08518.Google Scholar
• [53] Mou W, Li CJ, Wainwright MJ, Bartlett PL, Jordan MI (2020) On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. Proc. Thirty Third Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 125 (PMLR, New York), 2947–2997.Google Scholar
• [54] Parks PC (1992) A. M. Lyapunov’s stability theory—100 years on. IMA J. Math. Control Inform. 9(4):275–303.Crossref, Google Scholar
• [55] Perko L (2013) Differential Equations and Dynamical Systems, vol. 7 (Springer Science & Business Media, New York).Google Scholar
• [56] Pham QC, Tabareau N, Slotine JJ (2009) A contraction theory approach to stochastic incremental stability. IEEE Trans. Automatic Control 54(4):816–820.Crossref, Google Scholar
• [57] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [58] Qu G, Wierman A (2020) Finite-time analysis of asynchronous stochastic approximation and Q-learning. Proc. Thirty Third Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 125 (PMLR, New York), 3185–3205.Google Scholar
• [59] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Crossref, Google Scholar
• [60] Rockafellar RT (1997) Convex Analysis, vol. 28 (Princeton University Press, Princeton, NJ).Google Scholar
• [61] Shah D, Song D, Xu Z, Yang Y (2020) Sample efficient reinforcement learning via low-rank matrix estimation. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 12092–12103.Google Scholar
• [62] Shub M (2013) Global Stability of Dynamical Systems (Springer Science & Business Media, New York).Google Scholar
• [63] Srikant R, Ying L (2019) Finite-time error bounds for linear stochastic approximation and TD-learning. Proc. Thirty-Second Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 99 (PMLR, New York), 2803–2830.Google Scholar
• [64] Sutton R, Barto A (2018) Reinforcement Learning: An Introduction, Adaptive Computation and Machine Learning Series (MIT Press, Cambridge, MA).Google Scholar
• [65] Tsitsiklis JN, Van Roy B (1997) An analysis of temporal-difference learning with function approximation. IEEE Trans. Automatic Control 42(5):674–690.Crossref, Google Scholar
• [66] Tsitsiklis JN, Van Roy B (1999) Average cost temporal-difference learning. Automatica 35(11):1799–1808.Crossref, Google Scholar
• [67] Tsukamoto H, Chung SJ, Slotine JJE (2021) Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview. Annual Rev. Control 52:135–169.Crossref, Google Scholar
• [68] Wan Y, Naik A, Sutton RS (2021) Learning and planning in average-reward Markov decision processes. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (PMLR, New York), 10653–10662.Google Scholar
• [69] Yu H, Bertsekas DP (2009) Convergence results for some temporal difference methods based on least squares. IEEE Trans. Automatic Control 54(7):1515–1531.Crossref, Google Scholar
• [70] Zhang S, Zhang Z, Maguluri ST (2021) Finite sample analysis of average-reward TD-learning and Q-learning. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 1230–1242.Google Scholar
• [71] Zhang S, Wan Y, Sutton RS, Whiteson S (2021) Average-reward off-policy policy evaluation with function approximation. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (PMLR, New York), 12578–12588.Google Scholar