Stochastic Halpern iteration in normed spaces and applications to reinforcement learning

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 Õ(ε⁻⁵), improving recent rates established for the stochastic Krasnoselskii-Mann iteration. Also, we establish a lower bound of Ω(ε⁻³), 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(ε⁻²(1-γ)⁻³) complexity bound in the case in which the operator is a γ-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.