  We analyze the oracle complexity of the stochastic Halpern iteration with
variance reduction, where we aim to approximate fixed-points of nonexpansive
and contractive operators in a normed finite-dimensional space. We show that if
the underlying stochastic oracle is with uniformly bounded variance, our method
exhibits an overall oracle complexity of $\tilde{O}(\varepsilon^{-5})$,
improving recent rates established for the stochastic Krasnoselskii-Mann
iteration. Also, we establish a lower bound of $\Omega(\varepsilon^{-3})$,
which applies to a wide range of algorithms, including all averaged iterations
even with minibatching. Using a suitable modification of our approach, we
derive a $O(\varepsilon^{-2}(1-\gamma)^{-3})$ complexity bound in the case in
which the operator is a $\gamma$-contraction. As an application, we propose new
synchronous algorithms for average reward and discounted reward Markov decision
processes. In particular, for the average reward, our method improves on the
best-known sample complexity.
