2022/07/13 by Caio Kalil Lauand, Sean Meyn, Lauand, Caio Kalil +1 · 2 citations
Economics, Econometrics and Finance · Engineering · #34C29 #62L20 #93C10 #93C15 #93C73 #Extremum Seeking Control Systems #FOS: Mathematics #Optimization and Control (math.OC) #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.2207.06371
openalex publication_date 2022/07/13 · openalex created_date 2022/07/15 · openalex updated_date 2026/07/28
This paper concerns quasi-stochastic approximation (QSA) to solve root finding problems commonly found in applications to optimization and reinforcement learning. The general constant gain algorithm may be expressed as the time-inhomogeneous ODE (d)/(dt)Θt=αft (Θt), with state process Θ evolving on ℝd. Theory is based on an almost periodic vector field, so that in particular the time average of ft(θ) defines the time-homogeneous mean vector field f \colon ℝd → ℝd with f(θ^*)=0. Under smoothness assumptions on the functions involved, the following exact representation is obtained: (d)/(dt)Θt=α[f(Θt)-αΥt+α2Wt0+α(d)/(dt)Wt1+(d2)/(dt2)Wt2] along with formulae for the smooth signals \ Υt , Wti : i=0, 1, 2\. This new representation, combined with new conditions for ultimate boundedness, has many applications for furthering the theory of QSA and its applications, including the following implications that are developed in this paper: (i) A proof that the estimation error ‖Θt-θ^*‖ is of order O(α), but can be reduced to O(α2) using a second order linear filter. (ii) In application to extremum seeking control, it is found that the results do not apply because the standard algorithms are not Lipschitz continuous. A new approach is presented to ensure that the required Lipschitz bounds hold, and from this we obtain stability, transient bounds, and asymptotic bias of order O(α2), and asymptotic variance of order O(α4). (iii) It is in general possible to obtain better than O(α) bounds on error in traditional stochastic approximation when there is Markovian noise.