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.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Phase-type representations of stochastic interest rates with applications to life insurance
The purpose of the present paper is to incorporate stochastic interest rates into a matrix-approach to multi-state life insurance, where formulas for reserves, moments of future payments and equivalence premiums can be o…
A Neural RDE approach for continuous-time non-Markovian stochastic control problems
We propose a novel framework for solving continuous-time non-Markovian stochastic control problems by means of neural rough differential equations (Neural RDEs) introduced in Morrill et al. (2021). Non-Markovianity natur…
An Electrical Grid with Discrete Energy Levels
Minimizing both power fluctuations and energy waste in an electrical grid is a central challenge to energy policy. Any discrepancy between power production and loads may lead to inefficiencies and instability in the syst…
Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent
Characterizing and understanding the dynamics of stochastic gradient descent (SGD) around saddle points remains an open problem. We first show that saddle points in neural networks can be divided into two types, among wh…
Learning TheoryThe ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
Stochastic approximation is a class of algorithms that update a vector iteratively, incrementally, and stochastically, including, e.g., stochastic gradient descent and temporal difference learning. One fundamental challe…
reinforcement-learningReinforcement Learning