Optimal Matrix Momentum Stochastic Approximation and Applications to
  Q-learning
  Acceleration is an increasingly common theme in the stochastic optimization
literature. The two most common examples are Nesterov's method, and Polyak's
momentum technique. In this paper two new algorithms are introduced for root
finding problems: 1) PolSA is a root finding algorithm with specially designed
matrix momentum, and 2) NeSA can be regarded as a variant of Nesterov's
algorithm, or a simplification of PolSA. The PolSA algorithm is new even in the
context of optimization (when cast as a root finding problem).
  The research surveyed in this paper is motivated by applications to
reinforcement learning. It is well known that most variants of TD- and
Q-learning may be cast as SA (stochastic approximation) algorithms, and the
tools from general SA theory can be used to investigate convergence and bounds
on convergence rate. In particular, the asymptotic variance is a common metric
of performance for SA algorithms, and is also one among many metrics used in
assessing the performance of stochastic optimization algorithms. There are two
well known SA techniques that are known to have optimal asymptotic variance:
the Ruppert-Polyak averaging technique, and stochastic Newton-Raphson (SNR).
The former algorithm can have extremely bad transient performance, and the
latter can be computationally expensive. It is demonstrated here that parameter
estimates from the new PolSA algorithm couple with those of the ideal (but more
complex) SNR algorithm. The new algorithm is thus a third approach to obtain
optimal asymptotic covariance.
  These strong results require assumptions on the model. A linearized model is
considered, and the noise is assumed to be a martingale difference sequence.
Numerical results are obtained in a non-linear setting that is the motivation
for this work: In PolSA implementations of Q-learning it is observed that
coupling occurs with SNR in this non-ideal setting.
