Stochastic Halpern iteration in normed spaces and applications to reinforcement learning
<|reference_start|>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 $\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.<|reference_end|>
@article{bravo2024stochastic,
    title={Stochastic Halpern iteration in normed spaces and applications to
  reinforcement learning},
    author={Mario Bravo and Juan Pablo Contreras},
    journal={arXiv preprint arXiv:2403.12338},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12338},
    primaryClass={math.OC cs.LG stat.ML}
}