On The Stability Of Random Matrix Product With Markovian Noise: Application To Linear Stochastic Approximation And TD Learning

Abstract

This paper studies the exponential stability of random matrix products driven by a general (possibly unbounded) state space Markov chain. It is a cornerstone in the analysis of stochastic algorithms in machine learning (e.g. for parameter tracking in online learning or reinforcement learning). The existing results impose strong conditions such as uniform boundedness of the matrix-valued functions and uniform ergodicity of the Markov chains. Our main contribution is an exponential stability result for the \(p\)-th moment of random matrix product, provided that (i) the underlying Markov chain satisfies a super-Lyapunov drift condition, (ii) the growth of the matrix-valued functions is controlled by an appropriately defined function (related to the drift condition). Using this result, we give finite-time \(p\)-th moment bounds for constant and decreasing stepsize linear stochastic approximation schemes with Markovian noise on general state space. We illustrate these findings for linear va

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydurmus2021on

Related papers

• The ODE Method For Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00
• Characterizing The Exact Behaviors Of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory (2019)0.00
• Almost Sure Convergence Rates And Concentration Of Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00
• Central Limit Theorem For Two-timescale Stochastic Approximation With Markovian Noise: Theory And Applications (2024)0.00
• Uncertainty Quantification For Markov Chain Induced Martingales With Application To Temporal Difference Learning (2025)0.00
• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Simple And Optimal Methods For Stochastic Variational Inequalities, II: Markovian Noise And Policy Evaluation In Reinforcement Learning (2020)8.60
• Exact Formulas For Finite-time Estimation Errors Of Decentralized Temporal Difference Learning With Linear Function Approximation (2022)0.00