Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning
We are interested in understanding stability (almost sure boundedness) of
stochastic approximation algorithms (SAs) driven by a controlled Markov'
process. Analyzing this class of algorithms is important, since many
reinforcement learning (RL) algorithms can be cast as SAs driven by a
controlled Markov' process. In this paper, we present easily verifiable
sufficient conditions for stability and convergence of SAs driven by a
`controlled Markov' process. Many RL applications involve continuous state
spaces. While our analysis readily ensures stability for such continuous state
applications, traditional analyses do not. As compared to literature, our
analysis presents a two-fold generalization (a) the Markov process may evolve
in a continuous state space and (b) the process need not be ergodic under any
given stationary policy. Temporal difference learning (TD) is an important
policy evaluation method in reinforcement learning. The theory developed
herein, is used to analyze generalized $TD(0)$, an important variant of TD. Our
theory is also used to analyze a TD formulation of supervised learning for
forecasting problems.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments
As a primary contribution, we present a convergence theorem for stochastic iterations, and in particular, Q-learning iterates, under a general, possibly non-Markovian, stochastic environment. Our conditions for convergen…
Q-LearningQuantizationConvergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-time…
Reinforcement LearningAsymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
Stochastic approximation is an important class of algorithms, and a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforc…
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 (…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning
We present for the first time an asymptotic convergence analysis of two time-scale stochastic approximation driven by `controlled' Markov noise. In particular, both the faster and slower recursions have non-additive cont…