  The Robbins-Monro stochastic approximation algorithm is a foundation of many
algorithmic frameworks for reinforcement learning (RL), and often an efficient
approach to solving (or approximating the solution to) complex optimal control
problems. However, in many cases practitioners are unable to apply these
techniques because of an inherent high variance. This paper aims to provide a
general foundation for "quasi-stochastic approximation," in which all of the
processes under consideration are deterministic, much like quasi-Monte-Carlo
for variance reduction in simulation. The variance reduction can be
substantial, subject to tuning of pertinent parameters in the algorithm. This
paper introduces a new coupling argument to establish optimal rate of
convergence provided the gain is sufficiently large. These results are
established for linear models, and tested also in non-ideal settings. A major
application of these general results is a new class of RL algorithms for
deterministic state space models. In this setting, the main contribution is a
class of algorithms for approximating the value function for a given policy,
using a different policy designed to introduce exploration.
