Stochastic Approximation Target Tracking Quest: Finding the Optimal Step Size
by Kim Levy
Abstract: As a starting point, I propose to discuss the classic convergence results w.p.1 to a stationary target, the solution to the Ordinary
Differential Equation (ODE), using stochastic approximation with a decreasing step size. If the target changes with time, the step size must remain bounded away from 0 to allow tracking, so constant step sizes are often preferred. The next step is therefore to discuss the
convergence in distribution towards an Ornstein-Uhlenbeck process, which is one of the oldest example of Stochastic Differential Equations (SDE). This gives us an explicit expression for the variance around the ODE in 1 dimension and in multiple dimensions.
Our objective is to use these results to minimize the net loss of reward that occurs during transient (learning) phases of the algorithm while tracking the moving target. Our strategy is to maximize the step size to prepare for the changes while remaining
within acceptable error bound around the target. To finalize this quest, we need to improve the parameter estimations for the Ornstein-Uhlenbeck process and to control the step size reduction which happens too early when the regime changes.