mlsanityData to 7 Oct 2026

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

arXiv 2401.07844 ↗First posted 15 Jan 2024cs.LG cs.AIcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jan 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 7; 2026: 11.

23 papers.

Sort:

  1. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  2. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  3. 2024Doubly Optimal Policy Evaluation for Reinforcement Learningcited by 7
  4. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 6
  5. 2025Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iterationcited by 6
  6. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  7. 2024Efficient Policy Evaluation with Safety Constraint for Reinforcement Learningcited by 5
  8. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  9. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  10. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  11. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
  12. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
11 more
  1. 2026Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updatescited by 2
  2. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  3. 2025Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximationcited by 0
  4. 2025First and Second Order Approximations to Stochastic Gradient Descent Methods with Momentum Termscited by 0
  5. 2026Regularized Centered Emphatic Temporal Difference Learningcited by 0
  6. 2026On the Divergence of Differential Temporal Difference Learning without Local Clockscited by 0
  7. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  8. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
  9. 2026Online Policy Evaluation for MDPs with Dynamic UBSR Measurescited by 0
  10. 2026OR-Transformer: Scaling Real-Time Decision-Making to 1,000 Itemscited by 0
  11. 2026Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizescited by 0