mlsanityData to 14 Oct 2026

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

arXiv 2608.15966 ↗First posted 16 Aug 2026cs.LG math.OCcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

22 of 43 references.

References · 22

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  2. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  3. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  5. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  6. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  7. 2018An Analysis of Categorical Distributional Reinforcement Learningcited by 68
  8. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  9. 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
  10. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
  11. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  12. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
10 more
  1. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  2. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  3. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  4. 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theoremcited by 10
  5. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  6. 2026A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learningcited by 4
  7. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  8. 2026Mini-Batch Stochastic Halpern Algorithm for Nonexpansive Fixed Point Problemscited by 1
  9. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  10. 2026Unified High-Probability Analysis of Stochastic Variance-Reduced Estimationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Mapscited by 0