A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps

We study stochastic approximation of fixed points of a non-expansive operator when the oracle samples originate from a continuing Markovian trajectory. A direct block-minibatch implementation of Halpern iteration attains an expected last-iterate residual of order O(\log N/N), but accrues a substantive complexity of \tilde O(ε^{-5}) Markovian samples. We therefore introduce a variance-reduced Markovian PAGE-Halpern method whose refresh and same-state difference blocks are analyzed through the Poisson equation. In Hilbert spaces, the cocoercivity of I-T results in an O(ε^{-3}) sample complexity. Our main result extends this construction to a general finite-dimensional Banach space. A displacement-level Halpern bound replaces the Hilbert-space potential and yields \tilde O(ε^{-3}) sample complexity in the original non-expansiveness norm. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm. Non-smooth sup and block-sup geometries are covered through norm smoothing.