Stochastic Halpern iteration in normed spaces and applications to reinforcement learning

arXiv 2403.12338 ↗First posted 19 Mar 2024math.OC cs.LG stat.MLcited by 12

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, 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 has uniformly bounded variance, our method exhibits an overall oracle complexity of tildeO(varepsilon-5), to obtain varepsilon expected fixed-point residual for nonexpansive operators, 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-γ)-3) complexity bound in the case in which the operator is a γ-contraction to obtain an approximation of the fixed-point. As an application, we propose new model-free algorithms for average and discounted reward MDPs. For the average reward case, our method applies to weakly communicating MDPs without requiring prior parameter knowledge.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 33 of its 67 references that are in the map. First posted on arXiv 19 Mar 2024.

Builds on

33 of 67 references.

References · 33

2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
2019Variance-reduced Q-learning is minimax optimalcited by 73
2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61

21 more

2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
2022Stochastic first-order methods for average-reward Markov decision processescited by 32
2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
2019Generalized monotone operators and their averaged resolventscited by 27
2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 21
2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
2021Optimal error bounds for nonexpansive fixed-point iterations in normed spacescited by 12
2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
2016Sharp convergence rates for averaged nonexpansive mapscited by 2
2021Universal bounds for fixed point iterations via optimal transport metricscited by 2
2024An Inexact Halpern Iteration with Application to Distributionally Robust Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 8.

12 papers.

2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
2025Faster Fixed-Point Methods for Multichain MDPscited by 2
2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
2025Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspectivecited by 0
2026Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Accelerationcited by 0
2026Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Mapscited by 0
2026Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexitycited by 0
2026Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Findingcited by 0

Similar, not cited

Close in wording, no citation either way