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

arXiv: https://arxiv.org/abs/2608.15966 · HTML: https://mlsanity.com/paper/2608.15966/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 16 Aug 2026.

## Builds on (most cited first, 22 of 22)

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [An Analysis of Categorical Distributional Reinforcement Learning](https://mlsanity.com/paper/1802.08163/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise](https://mlsanity.com/paper/2409.19546/) (2024)
- [Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem](https://mlsanity.com/paper/2410.21704/) (2024)
- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2605.06866/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Mini-Batch Stochastic Halpern Algorithm for Nonexpansive Fixed Point Problems](https://mlsanity.com/paper/2604.21443/) (2026)
- [Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning](https://mlsanity.com/paper/2605.11289/) (2026)
- [Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation](https://mlsanity.com/paper/2605.15388/) (2026)

## Built on by (most cited first, 1 of 1)

- [Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps](https://mlsanity.com/paper/2609.09524/) (2026)

## Abstract (arXiv)

We study stochastic approximation of fixed points of a non-expansive operator T 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. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm.