  The focus of this paper is on stochastic variational inequalities (VI) under
Markovian noise. A prominent application of our algorithmic developments is the
stochastic policy evaluation problem in reinforcement learning. Prior
investigations in the literature focused on temporal difference (TD) learning
by employing nonsmooth finite time analysis motivated by stochastic subgradient
descent leading to certain limitations. These encompass the requirement of
analyzing a modified TD algorithm that involves projection to an a-priori
defined Euclidean ball, achieving a non-optimal convergence rate and no clear
way of deriving the beneficial effects of parallel implementation. Our approach
remedies these shortcomings in the broader context of stochastic VIs and in
particular when it comes to stochastic policy evaluation. We developed a
variety of simple TD learning type algorithms motivated by its original version
that maintain its simplicity, while offering distinct advantages from a
non-asymptotic analysis point of view. We first provide an improved analysis of
the standard TD algorithm that can benefit from parallel implementation. Then
we present versions of a conditional TD algorithm (CTD), that involves periodic
updates of the stochastic iterates, which reduce the bias and therefore exhibit
improved iteration complexity. This brings us to the fast TD (FTD) algorithm
which combines elements of CTD and the stochastic operator extrapolation method
of the companion paper. For a novel index resetting policy FTD exhibits the
best known convergence rate. We also devised a robust version of the algorithm
that is particularly suitable for discounting factors close to 1.
