arXiv (Cornell University) · 2019 · 31 citations · 30 references
Natural SciencesMathematicsMachine LearningProbability TheoryStochastic ProcessesOptimal ControlPolicy IterationPolicy LearningReinforcement LearningStochastic ControlStochastic OptimizationFinite Sample EstimationNonlinear Function ApproximationOnline Policy IterationPolicy Convergence AnalysisStability Of Stochastic ApproximationStochastic ApproximationStochastic Optimal Control
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., $α_k\equiv α$), the algorithm achieves exponential fast convergence to a neighborhood (with radius $O(α\log(1/α))$) 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 the Markovian noise, we exploit the fast mixing of the underlying Markov chain. To demonstrate the generality of our theoretical results on Markovian SA, we use it to derive the finite-sample bounds of the popular $Q$-learning with linear function approximation algorithm, under a condition on the behavior policy. Importantly, we do not need to make the assumption that the samples are i.i.d., and do not require an artificial projection step in the algorithm to maintain the boundedness of the iterates. Numerical simulations corroborate our theoretical results.
30
A Stochastic Approximation Method
Herbert Robbins, Sutton Monro · The Annals of Mathematical Statistics · 1951 · 9.6K citations · Full text
Mastering the game of Go without human knowledge
David Silver, Julian Schrittwieser, Karen Simonyan et al. · Nature · 2017 · 9.2K citations
Engineering, Educational Psychology, Cognitive Psychology +7
Analysis of recursive stochastic algorithms
Lennart Ljung · IEEE Transactions on Automatic Control · 1977 · 1.5K citations