Accelerating Optimization and Reinforcement Learning with Quasi Stochastic Approximation
Shuhang Chen, Adithya M. Devraj, Andrey Bernstein, Sean Meyn · 2021
The paper sets out to obtain precise convergence rates for quasi-stochastic approximation (QSA), with applications to optimization and reinforcement learning. The main contributions are obtained for general nonlinear algorithms, under the assumption that there is a well defined linearization near the optimal parameter θ*, with Hurwitz linearization matrix A*. Subject to stability of the algorithm (general conditions are surveyed in the paper): (i)If the algorithm gain is chosen as at=g/(1+t)ρwith g > 0 and ρ ∈ (0,1), then a “finite-t” approximation is obtained at-1{Θt- θ*} = Y̅ + ΞtI+ o(1) where Θtis the parameter estimate, Y ∈ ℝdis a vector identified in the paper, and {ΞtI} is bounded with zero mean. (ii)The approximation continues to hold with at=g/(1+t) under the stronger assumption that I+gA* is Hurwitz. (iii)The Ruppert-Polyak averaging technique is extended to this setting, in which the estimates {Θt} are obtained using the gain in (i), and ΘtRPis defined to be the running average. The convergence rate is 1/t if and only if Y=0. (iv)The theory is illustrated with applications to gradient-free optimization, and policy gradient algorithms for reinforcement learning.