Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning

DOI10.1016/J.AUTOMATICA.2022.110623MaRDI QIDQ2097782zbMATH OpenOpenAlexFDO

Authors Zaiwei Chen, Sheng Zhang, Thinh T. Doan, Siva Theja Maguluri, John-Paul B. Clarke

Publication date 14 November 2022

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.11425

zbMATH Keywords

\(Q\)-learningfinite-sample analysislinear function approximationMarkovian stochastic approximationreinforcement learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nonlinear systems in control theory (93C10) Stochastic systems in control theory (general) (93E03)

Abstract: 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., $alph{a}_{k}equivalpha$), the algorithm achieves exponential fast convergence to a neighborhood (with radius $O(alphalog(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 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.

Recommendations

• Asynchronous stochastic approximation and Q-learning
• Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
• Error bounds for constant step-size \(Q\)-learning
• Linear stochastic approximation driven by slowly varying Markov chains
• Two Time-Scale Stochastic Approximation with Controlled Markov Noise and Off-Policy Temporal-Difference Learning

Cites work

• \({\mathcal Q}\)-learning
• A concentration bound for stochastic approximation via Alekseev's formula
• A Dynamical System Approach to Stochastic Approximations
• A Stochastic Approximation Method
• A two Timescale Stochastic Approximation Scheme for Simulation-Based Parametric Optimization
• Analysis of recursive stochastic algorithms
• Analysis of Stochastic Approximation Schemes With Set-Valued Maps in the Absence of a Stability Guarantee and Their Stabilization
• Asynchronous stochastic approximation and Q-learning
• Average cost temporal-difference learning
• Ergodic mirror descent
• Error bounds for constant step-size \(Q\)-learning
• Extremum Problems With Total Variation Distance and Their Applications
• First-order and stochastic optimization methods for machine learning
• scientific article; zbMATH DE number 5957196 (Why is no real title available?)
• scientific article; zbMATH DE number 5347321 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Multiscale Stochastic Approximation for Parametric Optimization of Hidden Markov Models
• Nonlinear systems.
• Optimization methods for large-scale machine learning
• Reinforcement learning. An introduction
• Stability of Stochastic Approximations With “Controlled Markov” Noise and Temporal Difference Learning
• Stochastic Approximation With Iterate-Dependent Markov Noise Under Verifiable Conditions in Compact State Space With the Stability of Iterates Not Ensured
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning

Cited in

(11)

• Linear stochastic approximation driven by slowly varying Markov chains
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
• Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning
• Finite-time convergence rates of distributed local stochastic approximation
• On the sample complexity of actor-critic method for reinforcement learning with function approximation
• Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• An approximate policy iteration viewpoint of actor-critic algorithms
• Concentration of contractive stochastic approximation: additive and multiplicative noise
• Sample complexity of variance-reduced distributionally robust Q-learning
• Reinforcement learning for control with probabilistic stability guarantee: a finite-sample approach

This page was built for publication: Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097782)