# Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning

arXiv: https://arxiv.org/abs/1504.06043 · HTML: https://mlsanity.com/paper/1504.06043/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2015.

## Built on by (most cited first, 9 of 9)

- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [Gradient Temporal Difference with Momentum: Stability and Convergence](https://mlsanity.com/paper/2111.11004/) (2021)
- [n-Step Temporal Difference Learning with Optimal n](https://mlsanity.com/paper/2303.07068/) (2023)
- [Schedule Based Temporal Difference Algorithms](https://mlsanity.com/paper/2111.11768/) (2021)
- [STOPS: Short-Term-based Volatility-controlled Policy Search and its Global Convergence](https://mlsanity.com/paper/2201.09857/) (2022)
- [Learning to sample fibers for goodness-of-fit testing](https://mlsanity.com/paper/2405.13950/) (2024)

## Abstract (arXiv)

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.