# The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 15 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise](https://mlsanity.com/paper/2409.19546/) (2024)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Doubly Optimal Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2410.02226/) (2024)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Efficient Policy Evaluation with Safety Constraint for Reinforcement Learning](https://mlsanity.com/paper/2410.05655/) (2024)
- [Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration](https://mlsanity.com/paper/2504.10865/) (2025)
- [Offline Two-Player Zero-Sum Markov Games with KL Regularization](https://mlsanity.com/paper/2605.13025/) (2026)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2602.16629/) (2026)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [OR-Transformer: Scaling Real-Time Decision-Making to 1,000 Items](https://mlsanity.com/paper/2609.01933/) (2026)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)
- [First and Second Order Approximations to Stochastic Gradient Descent Methods with Momentum Terms](https://mlsanity.com/paper/2504.13992/) (2025)
- [Regularized Centered Emphatic Temporal Difference Learning](https://mlsanity.com/paper/2605.04100/) (2026)
- [On the Divergence of Differential Temporal Difference Learning without Local Clocks](https://mlsanity.com/paper/2605.06874/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)
- [Online Policy Evaluation for MDPs with Dynamic UBSR Measures](https://mlsanity.com/paper/2607.23030/) (2026)
- [Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes](https://mlsanity.com/paper/2609.19170/) (2026)
- [Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage](https://mlsanity.com/paper/2610.04997/) (2026)

## Abstract (arXiv)

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 challenge in analyzing a stochastic approximation algorithm is to establish its stability, i.e., to show that the stochastic vector iterates are bounded almost surely. In this paper, we extend the celebrated Borkar-Meyn theorem for stability from the Martingale difference noise setting to the Markovian noise setting, which greatly improves its applicability in reinforcement learning, especially in those off-policy reinforcement learning algorithms with linear function approximation and eligibility traces. Central to our analysis is the diminishing asymptotic rate of change of a few functions, which is implied by both a form of the strong law of large numbers and a form of the law of the iterated logarithm.