Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go?
AISTATS, (February 2018)Abstract
In this paper we study study constant step-size averaged linear stochastic approximation. With an eye towards linear value estimation in reinforcement learning, we ask whether for a given class of linear estimation problems i) a single universal constant step-size with ii) a C/t worst-case expected error with a class-dependent constant C > 0 can be guaranteed when the error is measured via an appropriate weighted squared norm. Such a result has recently been obtained in the context of linear least squares regression. We give examples that show that the answer to these questions in general is no. On the positive side, we also characterize the instance dependent behavior of the error of the said algorithms, identify some conditions under which the answer to the above questions can be changed to the positive, and in particular show instance-dependent error bounds of magnitude O(1/t) for the constant step-size iterate averaged versions of TD(0) and a novel variant of GTD, where the stepsize is chosen independently of the value estimation instance. Computer simulations are used to illustrate and complement the theory.