all AI news
Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning. (arXiv:1905.11425v7 [math.OC] UPDATED)
cs.LG updates on arXiv.org arxiv.org
Motivated by applications in reinforcement learning (RL), we study a
nonlinear stochastic approximation (SA) algorithm under Markovian noise, and
establish its finite-sample convergence bounds under various stepsizes.
Specifically, we show that when using constant stepsize (i.e., $\alpha_k\equiv
\alpha$), the algorithm achieves exponential fast convergence to a neighborhood
(with radius $O(\alpha\log(1/\alpha))$) around the desired limit point. When
using diminishing stepsizes with appropriate decay rate, the algorithm
converges with rate $O(\log(k)/k)$. Our proof is based on Lyapunov drift
arguments, and to handle …
analysis applications arxiv learning math reinforcement learning stochastic