Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation

Understand

The ODE method has been a workhorse for algorithm design and analysis since the introduction of the stochastic approximation.

• It is now understood that convergence theory amounts to establishing robustness of Euler approximations for ODEs, while theory of rates of convergence requires finer analysis.
• This paper sets out to extend this theory to quasi-stochastic approximation, based on algorithms in which the "noise" is based on deterministic signals.
• The main results are obtained under minimal assumptions: the usual Lipschitz conditions for ODE vector fields, and it is assumed that there is a well defined linearization near the optimal parameter $\theta^*$, with Hurwitz linearization matrix $A^*$.