A Concentration Bound for Stochastic Approximation via Alekseev’s Formula

DOI10.1287/stsy.2018.0019zbMath1442.62187arXiv1506.08657OpenAlexW2964258803WikidataQ128308466 ScholiaQ128308466MaRDI QIDQ5113889

Vivek S. Borkar, Gugan Thoppe

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

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

zbMATH Keywords

stochastic approximationconcentration inequalityconcentration boundAlekseev's formulalocally asymptotically stable equilibrium (LASE)perturbed ODEsum of martingale-differences

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Stochastic approximation (62L20) Perturbations of ordinary differential equations (34D10) Computational methods for problems pertaining to systems and control theory (93-08)

Related Items

Stabilization under round-robin scheduling of control inputs in nonlinear systems ⋮ A concentration bound for \(\operatorname{LSPE}( \lambda )\) ⋮ On the sample complexity of actor-critic method for reinforcement learning with function approximation ⋮ Multi-agent natural actor-critic reinforcement learning algorithms ⋮ Finite sample performance of linear least squares estimation ⋮ A concentration bound for contractive stochastic approximation ⋮ Finite-Time Performance of Distributed Temporal-Difference Learning with Linear Function Approximation ⋮ Non-asymptotic error bounds for constant stepsize stochastic approximation for tracking mobile agents ⋮ Fundamental design principles for reinforcement learning algorithms ⋮ Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning ⋮ Concentration of Contractive Stochastic Approximation and Reinforcement Learning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes
• Concentration bounds for stochastic approximations
• Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment
• Stochastic approximation. A dynamical systems viewpoint.
• Stochastic approximation methods for constrained and unconstrained systems
• Stochastic approximation and its applications
• On the Convergence, Lock-In Probability, and Sample Complexity of Stochastic Approximation
• A generalized URN problem and its applications
• Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
• Acceleration of Stochastic Approximation by Averaging
• Recuit simulésans potentiel sur une variétériemannienne compacte
• Method of Variation of Parameters for Dynamic Systems
• A Stochastic Approximation Method
• Perturbations of nonlinear systems of differential equations