The ODE Method For Stochastic Approximation And Reinforcement Learning With Markovian Noise

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyliu2024the

Related papers

• Almost Sure Convergence Rates And Concentration Of Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00
• Simple And Optimal Methods For Stochastic Variational Inequalities, II: Markovian Noise And Policy Evaluation In Reinforcement Learning (2020)8.60
• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
• Federated Stochastic Approximation Under Markov Noise And Heterogeneity: Applications In Reinforcement Learning (2022)0.00
• On The Stability Of Random Matrix Product With Markovian Noise: Application To Linear Stochastic Approximation And TD Learning (2021)0.00
• Concentration Of Contractive Stochastic Approximation And Reinforcement Learning (2021)0.00
• Central Limit Theorem For Two-timescale Stochastic Approximation With Markovian Noise: Theory And Applications (2024)0.00