On the Stability of Random Matrix Product with Markovian Noise:
  Application to Linear Stochastic Approximation and TD Learning
  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
value-function estimation in reinforcement learning. We provide finite-time
$p$-th moment bound for various members of temporal difference (TD) family of
algorithms.
