The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

2021/10/27 by Vivek S. Borkar, Vivek Borkar, Shuhang Chen +9 · 1 voice · 7 citations
Computer Science · #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2110.14427

Abstract

The paper concerns the d-dimensional stochastic approximation recursion, θ_n+1= θ_n + α_{n + 1} f(θ_n, Φ_n+1) where \ Φ_n \ is a stochastic process on a general state space, satisfying a conditional Markov property that allows for parameter-dependent noise. The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3): (i) An appropriate Lyapunov function is constructed that implies convergence of the estimates in L₄. (ii) A functional central limit theorem (CLT) is established, as well as the usual one-dimensional CLT for the normalized error. Moment bounds combined with the CLT imply convergence of the normalized covariance \textsfE[ z_n z_n^T ] to the asymptotic covariance in the CLT, where z_n =: (θ_n-θ^*)/√(α_n). (iii) The CLT holds for the normalized version z^PR_n =: √(n) [θ^PR_n -θ^*], of the averaged parameters θ^PR_n =:n^-1 ∑_k=1ⁿθ_k, subject to standard assumptions on the step-size. Moreover, the covariance in the CLT coincides with the minimal covariance of Polyak and Ruppert. (iv) An example is given where f and f are linear in θ, and Φ is a geometrically ergodic Markov chain but does not satisfy (DV3). While the algorithm is convergent, the second moment of θ_n is unbounded and in fact diverges. This arXiv version represents a major extension of the results in prior versions.The main results now allow for parameter-dependent noise, as is often the case in applications to reinforcement learning.

Cited by

• Faithful Decoding
• Reinforcement Learning for Optimal Stopping in POMDPs with Application to Quickest Change Detection
• Online Policy Evaluation for MDPs with Dynamic UBSR Measures
• Towards Formalizing Reinforcement Learning Theory
• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• Central Limit Theorems for Asynchronous Averaged Q-Learning
• Global Convergence and Acceleration for Single Observation Gradient Free Optimization

Discussions

• 🚨 Exciting work with Sean Meyn @supermeyn.bsky.social, Vivek Borkar, Shuhang Chen and Adithya Devraj. TL;DR: If you want to know how fast your reinforcement learning algorithm converges, only the CL [bsky, 17 points, 0 comments]

Related

• The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD\n Learning
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration