Stochastic Halpern iteration in normed spaces and applications to reinforcement learning

arXiv:2403.12338v1 Announce Type: cross
Abstract: 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 …

abstract aim analyze applications arxiv complexity cs.lg iteration math.oc operators oracle reinforcement reinforcement learning show space spaces stat.ml stochastic type variance